【JavaScript】kmeans using JavaScript

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

kmeans

K-means clustering in JavaScript

K-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean.

Installation

npm install ml-kmeans

API Documentation

本帖隐藏的内容

kmeans-master.zip (1.18 MB)

2017-4-16 04:18:31 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Javascript script kmeans scrip means

1. 'use strict';
   
2. 
   
3. const utils = require('./utils');
   
4. const init = require('./initialization');
   
5. const KMeansResult = require('./KMeansResult');
   
6. const squaredDistance = require('ml-distance-euclidean').squared;
   
7. 
   
8. const defaultOptions = {
   
9.     maxIterations: 100,
   
10.     tolerance: 1e-6,
    
11.     withIterations: false,
    
12.     initialization: 'mostDistant',
    
13.     distanceFunction: squaredDistance
    
14. };
    
15. 
    
16. /**
    
17. * Each step operation for kmeans
    
18. * @ignore
    
19. * @param {Array<Array<number>>} centers - K centers in format [x,y,z,...]
    
20. * @param {Array<Array<number>>} data - Points [x,y,z,...] to cluster
    
21. * @param {Array<number>} clusterID - Cluster identifier for each data dot
    
22. * @param {number} K - Number of clusters
    
23. * @param {object} [options] - Option object
    
24. * @param {number} iterations - Current number of iterations
    
25. * @return {KMeansResult}
    
26. */
    
27. function step(centers, data, clusterID, K, options, iterations) {
    
28.     clusterID = utils.updateClusterID(data, centers, clusterID, options.distanceFunction);
    
29.     var newCenters = utils.updateCenters(data, clusterID, K);
    
30.     var converged = utils.converged(newCenters, centers, options.distanceFunction, options.tolerance);
    
31.     return new KMeansResult(clusterID, newCenters, converged, iterations, options.distanceFunction);
    
32. }
    
33. 
    
34. /**
    
35. * Generator version for the algorithm
    
36. * @ignore
    
37. * @param {Array<Array<number>>} centers - K centers in format [x,y,z,...]
    
38. * @param {Array<Array<number>>} data - Points [x,y,z,...] to cluster
    
39. * @param {Array<number>} clusterID - Cluster identifier for each data dot
    
40. * @param {number} K - Number of clusters
    
41. * @param {object} [options] - Option object
    
42. */
    
43. function* kmeansGenerator(centers, data, clusterID, K, options) {
    
44.     var converged = false;
    
45.     var stepNumber = 0;
    
46.     var stepResult;
    
47.     while (!converged && (stepNumber < options.maxIterations)) {
    
48.         stepResult = step(centers, data, clusterID, K, options, ++stepNumber);
    
49.         yield stepResult.computeInformation(data);
    
50.         converged = stepResult.converged;
    
51.         centers = stepResult.centroids;
    
52.     }
    
53. }
    
54. 
    
55. /**
    
56. * K-means algorithm
    
57. * @param {Array<Array<number>>} data - Points in the format to cluster [x,y,z,...]
    
58. * @param {number} K - Number of clusters
    
59. * @param {object} [options] - Option object
    
60. * @param {number} [options.maxIterations = 100] - Maximum of iterations allowed
    
61. * @param {number} [options.tolerance = 1e-6] - Error tolerance
    
62. * @param {boolean} [options.withIterations = false] - Store clusters and centroids for each iteration
    
63. * @param {function} [options.distanceFunction = squaredDistance] - Distance function to use between the points
    
64. * @param {string|Array<Array<number>>} [options.initialization = 'moreDistant'] - K centers in format [x,y,z,...] or a method for initialize the data:
    
65. *  * `'random'` will choose K random different values.
    
66. *  * `'mostDistant'` will choose the more distant points to a first random pick
    
67. * @return {KMeansResult} - Cluster identifier for each data dot and centroids with the following fields:
    
68. *  * `'clusters'`: Array of indexes for the clusters.
    
69. *  * `'centroids'`: Array with the resulting centroids.
    
70. *  * `'iterations'`: Number of iterations that took to converge
    
71. */
    
72. function kmeans(data, K, options) {
    
73.     options = Object.assign({}, defaultOptions, options);
    
74. 
    
75.     if (K <= 0 || K > data.length || !Number.isInteger(K)) {
    
76.         throw new Error('K should be a positive integer smaller than the number of points');
    
77.     }
    
78. 
    
79.     var centers;
    
80.     if (Array.isArray(options.initialization)) {
    
81.         if (options.initialization.length !== K) {
    
82.             throw new Error('The initial centers should have the same length as K');
    
83.         } else {
    
84.             centers = options.initialization;
    
85.         }
    
86.     } else {
    
87.         switch (options.initialization) {
    
88.             case 'random':
    
89.                 centers = init.random(data, K);
    
90.                 break;
    
91.             case 'mostDistant':
    
92.                 centers = init.mostDistant(data, K, utils.calculateDistanceMatrix(data, options.distanceFunction));
    
93.                 break;
    
94.             default:
    
95.                 throw new Error('Unknown initialization method: "' + options.initialization + '"');
    
96.         }
    
97.     }
    
98. 
    
99.     // infinite loop until convergence
    
100.     if (options.maxIterations === 0) {
     
101.         options.maxIterations = Number.MAX_VALUE;
     
102.     }
     
103. 
     
104.     var clusterID = new Array(data.length);
     
105.     if (options.withIterations) {
     
106.         return kmeansGenerator(centers, data, clusterID, K, options);
     
107.     } else {
     
108.         var converged = false;
     
109.         var stepNumber = 0;
     
110.         var stepResult;
     
111.         while (!converged && (stepNumber < options.maxIterations)) {
     
112.             stepResult = step(centers, data, clusterID, K, options, ++stepNumber);
     
113.             converged = stepResult.converged;
     
114.             centers = stepResult.centroids;
     
115.         }
     
116.         return stepResult.computeInformation(data);
     
117.     }
     
118. }
     
119. 
     
120. module.exports = kmeans;

复制代码

1. Example
   
2. 
   
3. const kmeans = require('ml-kmeans');
   
4. 
   
5. let data = [[1, 1, 1], [1, 2, 1], [-1, -1, -1], [-1, -1, -1.5]];
   
6. let centers = [[1, 2, 1], [-1, -1, -1]];
   
7. 
   
8. let ans = kmeans(data, 2, {initialization: centers});
   
9. console.log(ans);
   
10. /*
    
11. KMeansResult {
    
12.   clusters: [ 0, 0, 1, 1 ],
    
13.   centroids:
    
14.    [ { centroid: [ 1, 1.5, 1 ], error: 0.25, size: 2 },
    
15.      { centroid: [ -1, -1, -1.25 ], error: 0.0625, size: 2 } ],
    
16.   converged: true,
    
17.   iterations: 1
    
18. }
    
19. */

复制代码