1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
(function(){
var distances = {
euclidean: function(v1, v2) {
var total = 0;
for (var i = 0; i < v1.length; i++) {
total += Math.pow(v2[i] - v1[i], 2);
}
return Math.sqrt(total);
},
manhattan: function(v1, v2) {
var total = 0;
for (var i = 0; i < v1.length ; i++) {
total += Math.abs(v2[i] - v1[i]);
}
return total;
},
max: function(v1, v2) {
var max = 0;
for (var i = 0; i < v1.length; i++) {
max = Math.max(max , Math.abs(v2[i] - v1[i]));
}
return max;
}
}
function KMeans(centroids) {
this.centroids = centroids || [];
}
KMeans.prototype.randomCentroids = function(points, k) {
var centroids = points.slice(0); // copy
centroids.sort(function() {
return (Math.round(Math.random()) - 0.5);
});
return centroids.slice(0, k);
}
KMeans.prototype.classify = function(point, distance) {
var min = Infinity,
index = 0;
distance = distance || "euclidean";
if (typeof distance == "string") {
distance = distances[distance];
}
for (var i = 0; i < this.centroids.length; i++) {
var dist = distance(point, this.centroids[i]);
if (dist < min) {
min = dist;
index = i;
}
}
return index;
}
KMeans.prototype.cluster = function(points, k, distance, snapshotPeriod, snapshotCb) {
k = k || Math.max(2, Math.ceil(Math.sqrt(points.length / 2)));
distance = distance || "euclidean";
if (typeof distance == "string") {
distance = distances[distance];
}
this.centroids = this.randomCentroids(points, k);
var assignment = new Array(points.length);
var clusters = new Array(k);
var iterations = 0;
var movement = true;
while (movement) {
// update point-to-centroid assignments
for (var i = 0; i < points.length; i++) {
assignment[i] = this.classify(points[i], distance);
}
// update location of each centroid
movement = false;
for (var j = 0; j < k; j++) {
var assigned = [];
for (var i = 0; i < assignment.length; i++) {
if (assignment[i] == j) {
assigned.push(points[i]);
}
}
if (!assigned.length) {
continue;
}
var centroid = this.centroids[j];
var newCentroid = new Array(centroid.length);
for (var g = 0; g < centroid.length; g++) {
var sum = 0;
for (var i = 0; i < assigned.length; i++) {
sum += assigned[i][g];
}
newCentroid[g] = sum / assigned.length;
if (newCentroid[g] != centroid[g]) {
movement = true;
}
}
this.centroids[j] = newCentroid;
clusters[j] = assigned;
}
if (snapshotCb && (iterations++ % snapshotPeriod == 0)) {
snapshotCb(clusters);
}
}
return clusters;
}
KMeans.prototype.toJSON = function() {
return JSON.stringify(this.centroids);
}
KMeans.prototype.fromJSON = function(json) {
this.centroids = JSON.parse(json);
return this;
}
function kmeans(vectors, k) {
return (new KMeans()).cluster(vectors, k);
}
// expose
this.KMeans = KMeans;
// expose to commonJS
if (typeof module !== 'undefined' && module.exports) {
module.exports = kmeans;
}
}).call(this);
|
