41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
# File 'lib/kmeans.rb', line 41
def self.clusters items, keys, options = {}
options = {
:k => 10,
:delta => 0.001,
:init => [],
:random => true
}.merge options
cs = []
if not options[:init].empty?
options[:init].each do |centre|
cs << {:centre => centre, :items => []}
end
end
if options[:random]
options[:k].times do
idx = (items.length * rand).to_i
cs << {:centre => take_keys(items[idx], keys), :items => []}
end
end
puts cs
while true
items.each do |item|
min_distance = Float::MAX
selected_cluster = nil
cs.each do |cluster|
distance = ndist(item, cluster[:centre], keys)
if distance < min_distance
min_distance = distance
selected_cluster = cluster
end
end
selected_cluster[:items] << item
end
cs = cs.reject { |cluster| cluster[:items].empty? }
max_delta = Float::MIN
cs.each do |cluster|
old_centre = cluster[:centre]
centre = cluster_centre cluster
cluster[:centre] = centre
max_delta = [ndist(old_centre, centre, keys), max_delta].max
end
if max_delta <= options[:delta]
break
else
cs.each do |cluster|
cluster[:items] = []
end
end
end
cs
end
|