Hierarchical Clustering in JavaScript

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

hclust

Hierarchical clustering algorithms in JavaScript

Installation

npm install ml-hclust

Methods

Generate a clustering hierarchy.

new agnes(data,[options])

AGNES (AGglomerative NESting): Continuously merge nodes that have the least dissimilarity.

Arguments

• data: Array of points to be clustered, are an array of arrays, as [[x1,y1],[x2,y2], ... ]
• options: Is an object with the parameters sim and kind, where sim is a distance function between vectors (the default function is the euclidean), and kind is the string name for the function to calculate distance between clusters, and it could be single(default), complete, average, centroid or ward
  

getDendogram([input])

Returns a phylogram (a dendogram with weights) and change the leaves values for the values in input, if it's given.

Example

var hclust = require('ml-hclust')var data = [[2,6], [3,4], [3,8]];var HC = new hclust.agnes(data);var dend1 = HC.getDendogram();var dend2 = HC.getDendogram([{a:1},{b:2},{c:3}]);
nClusters(N)

Returns at least N clusters based in the clustering tree if it's possible

new diana(data,[options])

DIANA (Divisive ANAlysis): The process starts at the root with all the points as one cluster and recursively splits the higher level clusters to build the dendrogram.

Arguments

• data: Array of points to be clustered, are an array of arrays, as [[x1,y1],[x2,y2], ... ]
• options: Is an object with the parameters sim and kind, where sim is a distance function between vectors (the default function is the euclidean), and kind is the string name for the function to calculate distance between clusters, and it could be single(default), complete, average, centroid or ward
  

getDendogram([input])

Returns a phylogram (a dendogram with weights) and change the leaves values for the values in input, if it's given.

Example

var hclust = require('ml-hclust')var data = [[2,6], [3,4], [3,8]];var HC = new hclust.diana(data);var dend1 = HC.getDendogram();var dend2 = HC.getDendogram([{a:1},{b:2},{c:3}]);
nClusters(N)

Returns at least N clusters based in the clustering tree if it's possible

new birch(data,[options])

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies): Incrementally construct a CF (Clustering Feature) tree, a hierarchical data structure for multiphase clustering

new cure(data,[options])

CURE (Clustering Using REpresentatives):

new chameleon(data,[options])

CHAMELEON

Test$ npm install$ npm test
Authors

• Miguel Asencio
  

License

MIT

本帖隐藏的内容

hclust-master.zip (9.5 KB)

2016-6-27 00:16:41 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：Hierarchical Clustering Javascript Cluster script function default distance between points

1. 'use strict';
   
2. 
   
3. var euclidean = require('ml-euclidean-distance');
   
4. var ClusterLeaf = require('./ClusterLeaf');
   
5. var Cluster = require('./Cluster');
   
6. 
   
7. /**
   
8. * @param {Array <Array <number>>} cluster1
   
9. * @param {Array <Array <number>>} cluster2
   
10. * @param {function} disFun
    
11. * @returns {number}
    
12. */
    
13. function simpleLink(cluster1, cluster2, disFun) {
    
14.     var m = 10e100;
    
15.     for (var i = 0; i < cluster1.length; i++)
    
16.         for (var j = i; j < cluster2.length; j++) {
    
17.             var d = disFun(cluster1[i], cluster2[j]);
    
18.             m = Math.min(d,m);
    
19.         }
    
20.     return m;
    
21. }
    
22. 
    
23. /**
    
24. * @param {Array <Array <number>>} cluster1
    
25. * @param {Array <Array <number>>} cluster2
    
26. * @param {function} disFun
    
27. * @returns {number}
    
28. */
    
29. function completeLink(cluster1, cluster2, disFun) {
    
30.     var m = -1;
    
31.     for (var i = 0; i < cluster1.length; i++)
    
32.         for (var j = i; j < cluster2.length; j++) {
    
33.             var d = disFun(cluster1[i], cluster2[j]);
    
34.             m = Math.max(d,m);
    
35.         }
    
36.     return m;
    
37. }
    
38. 
    
39. /**
    
40. * @param {Array <Array <number>>} cluster1
    
41. * @param {Array <Array <number>>} cluster2
    
42. * @param {function} disFun
    
43. * @returns {number}
    
44. */
    
45. function averageLink(cluster1, cluster2, disFun) {
    
46.     var m = 0;
    
47.     for (var i = 0; i < cluster1.length; i++)
    
48.         for (var j = 0; j < cluster2.length; j++)
    
49.             m += disFun(cluster1[i], cluster2[j]);
    
50.     return m / (cluster1.length * cluster2.length);
    
51. }
    
52. 
    
53. /**
    
54. * @param {Array <Array <number>>} cluster1
    
55. * @param {Array <Array <number>>} cluster2
    
56. * @param {function} disFun
    
57. * @returns {number}
    
58. */
    
59. function centroidLink(cluster1, cluster2, disFun) {
    
60.     var x1 = 0,
    
61.         y1 = 0,
    
62.         x2 = 0,
    
63.         y2 = 0;
    
64.     for (var i = 0; i < cluster1.length; i++) {
    
65.         x1 += cluster1[i][0];
    
66.         y1 += cluster1[i][1];
    
67.     }
    
68.     for (var j = 0; j < cluster2.length; j++) {
    
69.         x2 += cluster2[j][0];
    
70.         y2 += cluster2[j][1];
    
71.     }
    
72.     x1 /= cluster1.length;
    
73.     y1 /= cluster1.length;
    
74.     x2 /= cluster2.length;
    
75.     y2 /= cluster2.length;
    
76.     return disFun([x1,y1], [x2,y2]);
    
77. }
    
78. 
    
79. /**
    
80. * @param {Array <Array <number>>} cluster1
    
81. * @param {Array <Array <number>>} cluster2
    
82. * @param {function} disFun
    
83. * @returns {number}
    
84. */
    
85. function wardLink(cluster1, cluster2, disFun) {
    
86.     var x1 = 0,
    
87.         y1 = 0,
    
88.         x2 = 0,
    
89.         y2 = 0;
    
90.     for (var i = 0; i < cluster1.length; i++) {
    
91.         x1 += cluster1[i][0];
    
92.         y1 += cluster1[i][1];
    
93.     }
    
94.     for (var j = 0; j < cluster2.length; j++) {
    
95.         x2 += cluster2[j][0];
    
96.         y2 += cluster2[j][1];
    
97.     }
    
98.     x1 /= cluster1.length;
    
99.     y1 /= cluster1.length;
    
100.     x2 /= cluster2.length;
     
101.     y2 /= cluster2.length;
     
102.     return disFun([x1,y1], [x2,y2])*cluster1.length*cluster2.length / (cluster1.length+cluster2.length);
     
103. }
     
104. 
     
105. /**
     
106. * Returns the most distant point and his distance
     
107. * @param {Array <Array <number>>} splitting - Clusters to split
     
108. * @param {Array <Array <number>>} data - Original data
     
109. * @param {function} disFun - Distance function
     
110. * @returns {{d: number, p: number}} - d: maximum difference between points, p: the point more distant
     
111. */
     
112. function diff(splitting, data, disFun) {
     
113.     var ans = {
     
114.         d:0,
     
115.         p:0
     
116.     };
     
117. 
     
118.     var Ci = new Array(splitting[0].length);
     
119.     for (var e = 0; e < splitting[0].length; e++)
     
120.         Ci[e] = data[splitting[0][e]];
     
121.     var Cj = new Array(splitting[1].length);
     
122.     for (var f = 0; f < splitting[1].length; f++)
     
123.         Cj[f] = data[splitting[1][f]];
     
124. 
     
125.     var dist, ndist;
     
126.     for (var i = 0; i < Ci.length; i++) {
     
127.         dist = 0;
     
128.         for (var j = 0; j < Ci.length; j++)
     
129.             if (i !== j)
     
130.                 dist += disFun(Ci[i], Ci[j]);
     
131.         dist /= (Ci.length - 1);
     
132.         ndist = 0;
     
133.         for (var k = 0; k < Cj.length; k++)
     
134.             ndist += disFun(Ci[i], Cj[k]);
     
135.         ndist /= Cj.length;
     
136.         if ((dist - ndist) > ans.d) {
     
137.             ans.d = (dist - ndist);
     
138.             ans.p = i;
     
139.         }
     
140.     }
     
141.     return ans;
     
142. }
     
143. 
     
144. var defaultOptions = {
     
145.     dist: euclidean,
     
146.     kind: 'single'
     
147. };
     
148. 
     
149. /**
     
150. * Intra-cluster distance
     
151. * @param {Array} index
     
152. * @param {Array} data
     
153. * @param {function} disFun
     
154. * @returns {number}
     
155. */
     
156. function intrDist(index, data, disFun) {
     
157.     var dist = 0,
     
158.         count = 0;
     
159.     for (var i = 0; i < index.length; i++)
     
160.         for (var j = i; j < index.length; j++) {
     
161.             dist += disFun(data[index[i].index], data[index[j].index]);
     
162.             count++
     
163.         }
     
164.     return dist / count;
     
165. }
     
166. 
     
167. /**
     
168. * Splits the higher level clusters
     
169. * @param {Array <Array <number>>} data - Array of points to be clustered
     
170. * @param {json} options
     
171. * @constructor
     
172. */
     
173. function diana(data, options) {
     
174.     options = options || {};
     
175.     for (var o in defaultOptions)
     
176.         if (!(options.hasOwnProperty(o)))
     
177.             options[o] = defaultOptions[o];
     
178.     if (typeof options.kind === "string") {
     
179.         switch (options.kind) {
     
180.             case 'single':
     
181.                 options.kind = simpleLink;
     
182.                 break;
     
183.             case 'complete':
     
184.                 options.kind = completeLink;
     
185.                 break;
     
186.             case 'average':
     
187.                 options.kind = averageLink;
     
188.                 break;
     
189.             case 'centroid':
     
190.                 options.kind = centroidLink;
     
191.                 break;
     
192.             case 'ward':
     
193.                 options.kind = wardLink;
     
194.                 break;
     
195.             default:
     
196.                 throw new RangeError('Unknown kind of similarity');
     
197.         }
     
198.     }
     
199.     else if (typeof options.kind !== "function")
     
200.         throw new TypeError('Undefined kind of similarity');
     
201.     var tree = new Cluster();
     
202.     tree.children = new Array(data.length);
     
203.     tree.index = new Array(data.length);
     
204.     for (var ind = 0; ind < data.length; ind++) {
     
205.         tree.children[ind] = new ClusterLeaf(ind);
     
206.         tree.index[ind] = new ClusterLeaf(ind);
     
207.     }
     
208. 
     
209.     tree.distance = intrDist(tree.index, data, options.dist);
     
210.     var m, M, clId,
     
211.         dist, rebel;
     
212.     var list = [tree];
     
213.     while (list.length > 0) {
     
214.         M = 0;
     
215.         clId = 0;
     
216.         for (var i = 0; i < list.length; i++) {
     
217.             m = 0;
     
218.             for (var j = 0; j < list[i].length; j++) {
     
219.                 for (var l = (j + 1); l < list[i].length; l++) {
     
220.                     m = Math.max(options.dist(data[list[i].index[j].index], data[list[i].index[l].index]), m);
     
221.                 }
     
222.             }
     
223.             if (m > M) {
     
224.                 M = m;
     
225.                 clId = i;
     
226.             }
     
227.         }
     
228.         M = 0;
     
229.         if (list[clId].index.length === 2) {
     
230.             list[clId].children = [list[clId].index[0], list[clId].index[1]];
     
231.             list[clId].distance = options.dist(data[list[clId].index[0].index], data[list[clId].index[1].index]);
     
232.         }
     
233.         else if (list[clId].index.length === 3) {
     
234.             list[clId].children = [list[clId].index[0], list[clId].index[1], list[clId].index[2]];
     
235.             var d = [
     
236.                 options.dist(data[list[clId].index[0].index], data[list[clId].index[1].index]),
     
237.                 options.dist(data[list[clId].index[1].index], data[list[clId].index[2].index])
     
238.             ];
     
239.             list[clId].distance = (d[0] + d[1]) / 2;
     
240.         }
     
241.         else {
     
242.             var C = new Cluster();
     
243.             var sG = new Cluster();
     
244.             var splitting = [new Array(list[clId].index.length), []];
     
245.             for (var spl = 0; spl < splitting[0].length; spl++)
     
246.                 splitting[0][spl] = spl;
     
247.             for (var ii = 0; ii < splitting[0].length; ii++) {
     
248.                 dist = 0;
     
249.                 for (var jj = 0; jj < splitting[0].length; jj++)
     
250.                     if (ii !== jj)
     
251.                         dist += options.dist(data[list[clId].index[splitting[0][jj]].index], data[list[clId].index[splitting[0][ii]].index]);
     
252.                 dist /= (splitting[0].length - 1);
     
253.                 if (dist > M) {
     
254.                     M = dist;
     
255.                     rebel = ii;
     
256.                 }
     
257.             }
     
258.             splitting[1] = [rebel];
     
259.             splitting[0].splice(rebel, 1);
     
260.             dist = diff(splitting, data, options.dist);
     
261.             while (dist.d > 0) {
     
262.                 splitting[1].push(splitting[0][dist.p]);
     
263.                 splitting[0].splice(dist.p, 1);
     
264.                 dist = diff(splitting, data, options.dist);
     
265.             }
     
266.             var fData = new Array(splitting[0].length);
     
267.             C.index = new Array(splitting[0].length);
     
268.             for (var e = 0; e < fData.length; e++) {
     
269.                 fData[e] = data[list[clId].index[splitting[0][e]].index];
     
270.                 C.index[e] = list[clId].index[splitting[0][e]];
     
271.                 C.children[e] = list[clId].index[splitting[0][e]];
     
272.             }
     
273.             var sData = new Array(splitting[1].length);
     
274.             sG.index = new Array(splitting[1].length);
     
275.             for (var f = 0; f < sData.length; f++) {
     
276.                 sData[f] = data[list[clId].index[splitting[1][f]].index];
     
277.                 sG.index[f] = list[clId].index[splitting[1][f]];
     
278.                 sG.children[f] = list[clId].index[splitting[1][f]];
     
279.             }
     
280.             C.distance = intrDist(C.index, data, options.dist);
     
281.             sG.distance = intrDist(sG.index, data, options.dist);
     
282.             list.push(C);
     
283.             list.push(sG);
     
284.             list[clId].children = [C, sG];
     
285.         }
     
286.         list.splice(clId, 1);
     
287.     }
     
288.     return tree;
     
289. }
     
290. 
     
291. module.exports = diana;

复制代码

1. 'use strict';
   
2. 
   
3. var euclidean = require('ml-euclidean-distance');
   
4. var ClusterLeaf = require('./ClusterLeaf');
   
5. var Cluster = require('./Cluster');
   
6. 
   
7. /**
   
8. * @param cluster1
   
9. * @param cluster2
   
10. * @param disFun
    
11. * @returns {number}
    
12. */
    
13. function simpleLink(cluster1, cluster2, disFun) {
    
14.     var m = 10e100;
    
15.     for (var i = 0; i < cluster1.length; i++)
    
16.         for (var j = i; j < cluster2.length; j++) {
    
17.             var d = disFun(cluster1[i], cluster2[j]);
    
18.             m = Math.min(d,m);
    
19.         }
    
20.     return m;
    
21. }
    
22. 
    
23. /**
    
24. * @param cluster1
    
25. * @param cluster2
    
26. * @param disFun
    
27. * @returns {number}
    
28. */
    
29. function completeLink(cluster1, cluster2, disFun) {
    
30.     var m = -1;
    
31.     for (var i = 0; i < cluster1.length; i++)
    
32.         for (var j = i; j < cluster2.length; j++) {
    
33.             var d = disFun(cluster1[i], cluster2[j]);
    
34.             m = Math.max(d,m);
    
35.         }
    
36.     return m;
    
37. }
    
38. 
    
39. /**
    
40. * @param cluster1
    
41. * @param cluster2
    
42. * @param disFun
    
43. * @returns {number}
    
44. */
    
45. function averageLink(cluster1, cluster2, disFun) {
    
46.     var m = 0;
    
47.     for (var i = 0; i < cluster1.length; i++)
    
48.         for (var j = 0; j < cluster2.length; j++)
    
49.             m += disFun(cluster1[i], cluster2[j]);
    
50.     return m / (cluster1.length * cluster2.length);
    
51. }
    
52. 
    
53. /**
    
54. * @param cluster1
    
55. * @param cluster2
    
56. * @param disFun
    
57. * @returns {*}
    
58. */
    
59. function centroidLink(cluster1, cluster2, disFun) {
    
60.     var x1 = 0,
    
61.         y1 = 0,
    
62.         x2 = 0,
    
63.         y2 = 0;
    
64.     for (var i = 0; i < cluster1.length; i++) {
    
65.         x1 += cluster1[i][0];
    
66.         y1 += cluster1[i][1];
    
67.     }
    
68.     for (var j = 0; j < cluster2.length; j++) {
    
69.         x2 += cluster2[j][0];
    
70.         y2 += cluster2[j][1];
    
71.     }
    
72.     x1 /= cluster1.length;
    
73.     y1 /= cluster1.length;
    
74.     x2 /= cluster2.length;
    
75.     y2 /= cluster2.length;
    
76.     return disFun([x1,y1], [x2,y2]);
    
77. }
    
78. 
    
79. /**
    
80. * @param cluster1
    
81. * @param cluster2
    
82. * @param disFun
    
83. * @returns {number}
    
84. */
    
85. function wardLink(cluster1, cluster2, disFun) {
    
86.     var x1 = 0,
    
87.         y1 = 0,
    
88.         x2 = 0,
    
89.         y2 = 0;
    
90.     for (var i = 0; i < cluster1.length; i++) {
    
91.         x1 += cluster1[i][0];
    
92.         y1 += cluster1[i][1];
    
93.     }
    
94.     for (var j = 0; j < cluster2.length; j++) {
    
95.         x2 += cluster2[j][0];
    
96.         y2 += cluster2[j][1];
    
97.     }
    
98.     x1 /= cluster1.length;
    
99.     y1 /= cluster1.length;
    
100.     x2 /= cluster2.length;
     
101.     y2 /= cluster2.length;
     
102.     return disFun([x1,y1], [x2,y2])*cluster1.length*cluster2.length / (cluster1.length+cluster2.length);
     
103. }
     
104. 
     
105. var defaultOptions = {
     
106.     disFunc: euclidean,
     
107.     kind: 'single'
     
108. };
     
109. 
     
110. /**
     
111. * Continuously merge nodes that have the least dissimilarity
     
112. * @param {Array <Array <number>>} data - Array of points to be clustered
     
113. * @param {json} options
     
114. * @constructor
     
115. */
     
116. function agnes(data, options) {
     
117.     options = options || {};
     
118.     for (var o in defaultOptions)
     
119.         if (!(options.hasOwnProperty(o)))
     
120.             options[o] = defaultOptions[o];
     
121.     var len = data.length;
     
122. 
     
123.     // allows to use a string or a given function
     
124.     if (typeof options.kind === "string") {
     
125.         switch (options.kind) {
     
126.             case 'single':
     
127.                 options.kind = simpleLink;
     
128.                 break;
     
129.             case 'complete':
     
130.                 options.kind = completeLink;
     
131.                 break;
     
132.             case 'average':
     
133.                 options.kind = averageLink;
     
134.                 break;
     
135.             case 'centroid':
     
136.                 options.kind = centroidLink;
     
137.                 break;
     
138.             case 'ward':
     
139.                 options.kind = wardLink;
     
140.                 break;
     
141.             default:
     
142.                 throw new RangeError('Unknown kind of similarity');
     
143.         }
     
144.     }
     
145.     else if (typeof options.kind !== "function")
     
146.         throw new TypeError('Undefined kind of similarity');
     
147. 
     
148.     var list = new Array(len);
     
149.     for (var i = 0; i < data.length; i++)
     
150.         list[i] = new ClusterLeaf(i);
     
151.     var min  = 10e5,
     
152.         d = {},
     
153.         dis = 0;
     
154. 
     
155.     while (list.length > 1) {
     
156. 
     
157.         // calculates the minimum distance
     
158.         d = {};
     
159.         min = 10e5;
     
160.         for (var j = 0; j < list.length; j++)
     
161.             for (var k = j + 1; k < list.length; k++) {
     
162.                 var fData, sData;
     
163.                 if (list[j] instanceof ClusterLeaf)
     
164.                     fData = [data[list[j].index]];
     
165.                 else {
     
166.                     fData = new Array(list[j].index.length);
     
167.                     for (var e = 0; e < fData.length; e++)
     
168.                         fData[e] = data[list[j].index[e].index];
     
169.                 }
     
170.                 if (list[k] instanceof ClusterLeaf)
     
171.                     sData = [data[list[k].index]];
     
172.                 else {
     
173.                     sData = new Array(list[k].index.length);
     
174.                     for (var f = 0; f < sData.length; f++)
     
175.                         sData[f] = data[list[k].index[f].index];
     
176.                 }
     
177.                 dis = options.kind(fData, sData, options.disFunc).toFixed(4);
     
178.                 if (dis in d) {
     
179.                     d[dis].push([list[j], list[k]]);
     
180.                 }
     
181.                 else {
     
182.                     d[dis] = [[list[j], list[k]]];
     
183.                 }
     
184.                 min = Math.min(dis, min);
     
185.             }
     
186. 
     
187.         // cluster dots
     
188.         var dmin = d[min.toFixed(4)];
     
189.         var clustered = new Array(dmin.length);
     
190.         var aux,
     
191.             count = 0;
     
192.         while (dmin.length > 0) {
     
193.             aux = dmin.shift();
     
194.             for (var q = 0; q < dmin.length; q++) {
     
195.                 var int = dmin[q].filter(function(n) {
     
196.                     //noinspection JSReferencingMutableVariableFromClosure
     
197.                     return aux.indexOf(n) !== -1
     
198.                 });
     
199.                 if (int.length > 0) {
     
200.                     var diff = dmin[q].filter(function(n) {
     
201.                         //noinspection JSReferencingMutableVariableFromClosure
     
202.                         return aux.indexOf(n) === -1
     
203.                     });
     
204.                     aux = aux.concat(diff);
     
205.                     dmin.splice(q-- ,1);
     
206.                 }
     
207.             }
     
208.             clustered[count++] = aux;
     
209.         }
     
210.         clustered.length = count;
     
211. 
     
212.         for (var ii = 0; ii < clustered.length; ii++) {
     
213.             var obj = new Cluster();
     
214.             obj.children = clustered[ii].concat();
     
215.             obj.distance = min;
     
216.             obj.index = new Array(len);
     
217.             var indCount = 0;
     
218.             for (var jj = 0; jj < clustered[ii].length; jj++) {
     
219.                 if (clustered[ii][jj] instanceof ClusterLeaf)
     
220.                     obj.index[indCount++] = clustered[ii][jj];
     
221.                 else {
     
222.                     indCount += clustered[ii][jj].index.length;
     
223.                     obj.index = clustered[ii][jj].index.concat(obj.index);
     
224.                 }
     
225.                 list.splice((list.indexOf(clustered[ii][jj])), 1);
     
226.             }
     
227.             obj.index.length = indCount;
     
228.             list.push(obj);
     
229.         }
     
230.     }
     
231.     return list[0];
     
232. }
     
233. 
     
234. module.exports = agnes;

复制代码

1. 'use strict';
   
2. 
   
3. function Cluster () {
   
4.     this.children = [];
   
5.     this.distance = -1;
   
6.     this.index = [];
   
7. }
   
8. 
   
9. /**
   
10. * Creates an array of values where maximum distance smaller than the threshold
    
11. * @param {number} threshold
    
12. * @return {Array <Cluster>}
    
13. */
    
14. Cluster.prototype.cut = function (threshold) {
    
15.     if (threshold < 0) throw new RangeError('Threshold too small');
    
16.     var root = new Cluster();
    
17.     root.children = this.children;
    
18.     root.distance = this.distance;
    
19.     root.index = this.index;
    
20.     var list = [root];
    
21.     var ans = [];
    
22.     while (list.length > 0) {
    
23.         var aux = list.shift();
    
24.         if (threshold >= aux.distance)
    
25.             ans.push(aux);
    
26.         else
    
27.             list = list.concat(aux.children);
    
28.     }
    
29.     return ans;
    
30. };
    
31. 
    
32. /**
    
33. * Merge the leaves in the minimum way to have 'minGroups' number of clusters
    
34. * @param {number} minGroups
    
35. * @return {Cluster}
    
36. */
    
37. Cluster.prototype.group = function (minGroups) {
    
38.     if (minGroups < 1) throw new RangeError('Number of groups too small');
    
39.     var root = new Cluster();
    
40.     root.children = this.children;
    
41.     root.distance = this.distance;
    
42.     root.index = this.index;
    
43.     if (minGroups === 1)
    
44.         return root;
    
45.     var list = [root];
    
46.     var aux;
    
47.     while (list.length < minGroups && list.length !== 0) {
    
48.         aux = list.shift();
    
49.         list = list.concat(aux.children);
    
50.     }
    
51.     if (list.length === 0) throw new RangeError('Number of groups too big');
    
52.     for (var i = 0; i < list.length; i++)
    
53.         if (list[i].distance === aux.distance) {
    
54.             list.concat(list[i].children.slice(1));
    
55.             list[i] = list[i].children[0];
    
56.         }
    
57.     for (var j = 0; j < list.length; j++)
    
58.         if (list[j].distance !== 0) {
    
59.             var obj = list[j];
    
60.             obj.children = obj.index;
    
61.         }
    
62.     return root;
    
63. };
    
64. 
    
65. module.exports = Cluster;

复制代码