K-Nearest Neighbor using JavaScript

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

K-Nearest neighbor classifier

A General purpose k-nearest neighbor classifier algorithm based on the k-d tree Javascript library develop by Ubilabs:

• k-d trees
  

Methodsnew NaiveBayes()

Constructor that takes no arguments.

Example

var knn = new KNN();
train(trainingSet, predictions)

Train the Naive Bayes model to the given training set, predictions, and some options.

Arguments

• trainingSet - A matrix of the training set.
• trainingLabels - An array of value for each case in the training set.
• options - Object with the options for the training.
  

Options

• k - number of nearest neighbor (Default, number of label + 1).
• distance - distance function for the algorithm, the argument is a function, not an String (by default is euclidean, you can use the functions of this repository distance).
  

Example

var trainingSet = [[0, 0, 0], [0, 1, 1], [1, 1, 0], [2, 2, 2], [1, 2, 2], [2, 1, 2]];var predictions = [0, 0, 0, 1, 1, 1];knn.train(trainingSet, predictions);
predict(dataset)

Predict the values of the dataset.

Arguments

• dataset - A matrix that contains the dataset.
  

Example

var dataset = [[0, 0, 0],               [2, 2, 2]];var ans = knn.predict(dataset);
export()

Exports the actual K-Nearest Neighbor model to an Javascript Object.

load(model)

Returns a new K-Nearest Neighbor Classifier with the given model.

Arguments

• model - Javascript Object generated from export() function.
  

Authors

• Jefferson Hernandez
  

License

MIT

本帖隐藏的内容

knn-master.zip (8.27 KB)

2016-6-27 00:08:00 上传

扫码加我 拉你入群

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

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

分享0 收藏1 回帖

关键词：Javascript script Using scrip Java training library General develop purpose

1. 'use strict';
   
2. 
   
3. /**
   
4. * k-d Tree JavaScript - V 1.01
   
5. *
   
6. * https://github.com/ubilabs/kd-tree-javascript
   
7. *
   
8. * @author Mircea Pricop <pricop@ubilabs.net>, 2012
   
9. * @author Martin Kleppe <kleppe@ubilabs.net>, 2012
   
10. * @author Ubilabs http://ubilabs.net, 2012
    
11. * @license MIT License <http://www.opensource.org/licenses/mit-license.php>
    
12. */
    
13. 
    
14. 
    
15. function Node(obj, dimension, parent) {
    
16.     this.obj = obj;
    
17.     this.left = null;
    
18.     this.right = null;
    
19.     this.parent = parent;
    
20.     this.dimension = dimension;
    
21. }
    
22. 
    
23. function kdTree(points, metric, dimensions) {
    
24. 
    
25.     var self = this;
    
26. 
    
27.     function buildTree(points, depth, parent) {
    
28.         var dim = depth % dimensions.length,
    
29.             median,
    
30.             node;
    
31. 
    
32.         if (points.length === 0) {
    
33.             return null;
    
34.         }
    
35.         if (points.length === 1) {
    
36.             return new Node(points[0], dim, parent);
    
37.         }
    
38. 
    
39.         points.sort(function (a, b) {
    
40.             return a[dimensions[dim]] - b[dimensions[dim]];
    
41.         });
    
42. 
    
43.         median = Math.floor(points.length / 2);
    
44.         node = new Node(points[median], dim, parent);
    
45.         node.left = buildTree(points.slice(0, median), depth + 1, node);
    
46.         node.right = buildTree(points.slice(median + 1), depth + 1, node);
    
47. 
    
48.         return node;
    
49.     }
    
50. 
    
51.     // Reloads a serialied tree
    
52.     function loadTree (data) {
    
53.         // Just need to restore the `parent` parameter
    
54.         self.root = data;
    
55. 
    
56.         function restoreParent (root) {
    
57.             if (root.left) {
    
58.                 root.left.parent = root;
    
59.                 restoreParent(root.left);
    
60.             }
    
61. 
    
62.             if (root.right) {
    
63.                 root.right.parent = root;
    
64.                 restoreParent(root.right);
    
65.             }
    
66.         }
    
67. 
    
68.         restoreParent(self.root);
    
69.     }
    
70. 
    
71.     // If points is not an array, assume we're loading a pre-built tree
    
72.     if (!Array.isArray(points)) loadTree(points, metric, dimensions);
    
73.     else this.root = buildTree(points, 0, null);
    
74. 
    
75.     // Convert to a JSON serializable structure; this just requires removing
    
76.     // the `parent` property
    
77.     this.toJSON = function (src) {
    
78.         if (!src) src = this.root;
    
79.         var dest = new Node(src.obj, src.dimension, null);
    
80.         if (src.left) dest.left = self.toJSON(src.left);
    
81.         if (src.right) dest.right = self.toJSON(src.right);
    
82.         return dest;
    
83.     };
    
84. 
    
85.     this.insert = function (point) {
    
86.         function innerSearch(node, parent) {
    
87. 
    
88.             if (node === null) {
    
89.                 return parent;
    
90.             }
    
91. 
    
92.             var dimension = dimensions[node.dimension];
    
93.             if (point[dimension] < node.obj[dimension]) {
    
94.                 return innerSearch(node.left, node);
    
95.             } else {
    
96.                 return innerSearch(node.right, node);
    
97.             }
    
98.         }
    
99. 
    
100.         var insertPosition = innerSearch(this.root, null),
     
101.             newNode,
     
102.             dimension;
     
103. 
     
104.         if (insertPosition === null) {
     
105.             this.root = new Node(point, 0, null);
     
106.             return;
     
107.         }
     
108. 
     
109.         newNode = new Node(point, (insertPosition.dimension + 1) % dimensions.length, insertPosition);
     
110.         dimension = dimensions[insertPosition.dimension];
     
111. 
     
112.         if (point[dimension] < insertPosition.obj[dimension]) {
     
113.             insertPosition.left = newNode;
     
114.         } else {
     
115.             insertPosition.right = newNode;
     
116.         }
     
117.     };
     
118. 
     
119.     this.remove = function (point) {
     
120.         var node;
     
121. 
     
122.         function nodeSearch(node) {
     
123.             if (node === null) {
     
124.                 return null;
     
125.             }
     
126. 
     
127.             if (node.obj === point) {
     
128.                 return node;
     
129.             }
     
130. 
     
131.             var dimension = dimensions[node.dimension];
     
132. 
     
133.             if (point[dimension] < node.obj[dimension]) {
     
134.                 return nodeSearch(node.left, node);
     
135.             } else {
     
136.                 return nodeSearch(node.right, node);
     
137.             }
     
138.         }
     
139. 
     
140.         function removeNode(node) {
     
141.             var nextNode,
     
142.                 nextObj,
     
143.                 pDimension;
     
144. 
     
145.             function findMin(node, dim) {
     
146.                 var dimension,
     
147.                     own,
     
148.                     left,
     
149.                     right,
     
150.                     min;
     
151. 
     
152.                 if (node === null) {
     
153.                     return null;
     
154.                 }
     
155. 
     
156.                 dimension = dimensions[dim];
     
157. 
     
158.                 if (node.dimension === dim) {
     
159.                     if (node.left !== null) {
     
160.                         return findMin(node.left, dim);
     
161.                     }
     
162.                     return node;
     
163.                 }
     
164. 
     
165.                 own = node.obj[dimension];
     
166.                 left = findMin(node.left, dim);
     
167.                 right = findMin(node.right, dim);
     
168.                 min = node;
     
169. 
     
170.                 if (left !== null && left.obj[dimension] < own) {
     
171.                     min = left;
     
172.                 }
     
173.                 if (right !== null && right.obj[dimension] < min.obj[dimension]) {
     
174.                     min = right;
     
175.                 }
     
176.                 return min;
     
177.             }
     
178. 
     
179.             if (node.left === null && node.right === null) {
     
180.                 if (node.parent === null) {
     
181.                     self.root = null;
     
182.                     return;
     
183.                 }
     
184. 
     
185.                 pDimension = dimensions[node.parent.dimension];
     
186. 
     
187.                 if (node.obj[pDimension] < node.parent.obj[pDimension]) {
     
188.                     node.parent.left = null;
     
189.                 } else {
     
190.                     node.parent.right = null;
     
191.                 }
     
192.                 return;
     
193.             }
     
194. 
     
195.             // If the right subtree is not empty, swap with the minimum element on the
     
196.             // node's dimension. If it is empty, we swap the left and right subtrees and
     
197.             // do the same.
     
198.             if (node.right !== null) {
     
199.                 nextNode = findMin(node.right, node.dimension);
     
200.                 nextObj = nextNode.obj;
     
201.                 removeNode(nextNode);
     
202.                 node.obj = nextObj;
     
203.             } else {
     
204.                 nextNode = findMin(node.left, node.dimension);
     
205.                 nextObj = nextNode.obj;
     
206.                 removeNode(nextNode);
     
207.                 node.right = node.left;
     
208.                 node.left = null;
     
209.                 node.obj = nextObj;
     
210.             }
     
211. 
     
212.         }
     
213. 
     
214.         node = nodeSearch(self.root);
     
215. 
     
216.         if (node === null) { return; }
     
217. 
     
218.         removeNode(node);
     
219.     };
     
220. 
     
221.     this.nearest = function (point, maxNodes, maxDistance) {
     
222.         var i,
     
223.             result,
     
224.             bestNodes;
     
225. 
     
226.         bestNodes = new BinaryHeap(
     
227.             function (e) { return -e[1]; }
     
228.         );
     
229. 
     
230.         function nearestSearch(node) {
     
231.             var bestChild,
     
232.                 dimension = dimensions[node.dimension],
     
233.                 ownDistance = metric(point, node.obj),
     
234.                 linearPoint = {},
     
235.                 linearDistance,
     
236.                 otherChild,
     
237.                 i;
     
238. 
     
239.             function saveNode(node, distance) {
     
240.                 bestNodes.push([node, distance]);
     
241.                 if (bestNodes.size() > maxNodes) {
     
242.                     bestNodes.pop();
     
243.                 }
     
244.             }
     
245. 
     
246.             for (i = 0; i < dimensions.length; i += 1) {
     
247.                 if (i === node.dimension) {
     
248.                     linearPoint[dimensions[i]] = point[dimensions[i]];
     
249.                 } else {
     
250.                     linearPoint[dimensions[i]] = node.obj[dimensions[i]];
     
251.                 }
     
252.             }
     
253. 
     
254.             linearDistance = metric(linearPoint, node.obj);
     
255. 
     
256.             if (node.right === null && node.left === null) {
     
257.                 if (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1]) {
     
258.                     saveNode(node, ownDistance);
     
259.                 }
     
260.                 return;
     
261.             }
     
262. 
     
263.             if (node.right === null) {
     
264.                 bestChild = node.left;
     
265.             } else if (node.left === null) {
     
266.                 bestChild = node.right;
     
267.             } else {
     
268.                 if (point[dimension] < node.obj[dimension]) {
     
269.                     bestChild = node.left;
     
270.                 } else {
     
271.                     bestChild = node.right;
     
272.                 }
     
273.             }
     
274. 
     
275.             nearestSearch(bestChild);
     
276. 
     
277.             if (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1]) {
     
278.                 saveNode(node, ownDistance);
     
279.             }
     
280. 
     
281.             if (bestNodes.size() < maxNodes || Math.abs(linearDistance) < bestNodes.peek()[1]) {
     
282.                 if (bestChild === node.left) {
     
283.                     otherChild = node.right;
     
284.                 } else {
     
285.                     otherChild = node.left;
     
286.                 }
     
287.                 if (otherChild !== null) {
     
288.                     nearestSearch(otherChild);
     
289.                 }
     
290.             }
     
291.         }
     
292. 
     
293.         if (maxDistance) {
     
294.             for (i = 0; i < maxNodes; i += 1) {
     
295.                 bestNodes.push([null, maxDistance]);
     
296.             }
     
297.         }
     
298. 
     
299.         if(self.root)
     
300.             nearestSearch(self.root);
     
301. 
     
302.         result = [];
     
303. 
     
304.         for (i = 0; i < Math.min(maxNodes, bestNodes.content.length); i += 1) {
     
305.             if (bestNodes.content[i][0]) {
     
306.                 result.push([bestNodes.content[i][0].obj, bestNodes.content[i][1]]);
     
307.             }
     
308.         }
     
309.         return result;
     
310.     };
     
311. 
     
312.     this.balanceFactor = function () {
     
313.         function height(node) {
     
314.             if (node === null) {
     
315.                 return 0;
     
316.             }
     
317.             return Math.max(height(node.left), height(node.right)) + 1;
     
318.         }
     
319. 
     
320.         function count(node) {
     
321.             if (node === null) {
     
322.                 return 0;
     
323.             }
     
324.             return count(node.left) + count(node.right) + 1;
     
325.         }
     
326. 
     
327.         return height(self.root) / (Math.log(count(self.root)) / Math.log(2));
     
328.     };
     
329. }
     
330. 
     
331. // Binary heap implementation from:
     
332. // http://eloquentjavascript.net/appendix2.html
     
333. 
     
334. function BinaryHeap(scoreFunction){
     
335.     this.content = [];
     
336.     this.scoreFunction = scoreFunction;
     
337. }
     
338. 
     
339. BinaryHeap.prototype = {
     
340.     push: function(element) {
     
341.         // Add the new element to the end of the array.
     
342.         this.content.push(element);
     
343.         // Allow it to bubble up.
     
344.         this.bubbleUp(this.content.length - 1);
     
345.     },
     
346. 
     
347.     pop: function() {
     
348.         // Store the first element so we can return it later.
     
349.         var result = this.content[0];
     
350.         // Get the element at the end of the array.
     
351.         var end = this.content.pop();
     
352.         // If there are any elements left, put the end element at the
     
353.         // start, and let it sink down.
     
354.         if (this.content.length > 0) {
     
355.             this.content[0] = end;
     
356.             this.sinkDown(0);
     
357.         }
     
358.         return result;
     
359.     },
     
360. 
     
361.     peek: function() {
     
362.         return this.content[0];
     
363.     },
     
364. 
     
365.     remove: function(node) {
     
366.         var len = this.content.length;
     
367.         // To remove a value, we must search through the array to find
     
368.         // it.
     
369.         for (var i = 0; i < len; i++) {
     
370.             if (this.content[i] == node) {
     
371.                 // When it is found, the process seen in 'pop' is repeated
     
372.                 // to fill up the hole.
     
373.                 var end = this.content.pop();
     
374.                 if (i != len - 1) {
     
375.                     this.content[i] = end;
     
376.                     if (this.scoreFunction(end) < this.scoreFunction(node))
     
377.                         this.bubbleUp(i);
     
378.                     else
     
379.                         this.sinkDown(i);
     
380.                 }
     
381.                 return;
     
382.             }
     
383.         }
     
384.         throw new Error("Node not found.");
     
385.     },
     
386. 
     
387.     size: function() {
     
388.         return this.content.length;
     
389.     },
     
390. 
     
391.     bubbleUp: function(n) {
     
392.         // Fetch the element that has to be moved.
     
393.         var element = this.content[n];
     
394.         // When at 0, an element can not go up any further.
     
395.         while (n > 0) {
     
396.             // Compute the parent element's index, and fetch it.
     
397.             var parentN = Math.floor((n + 1) / 2) - 1,
     
398.                 parent = this.content[parentN];
     
399.             // Swap the elements if the parent is greater.
     
400.             if (this.scoreFunction(element) < this.scoreFunction(parent)) {
     
401.                 this.content[parentN] = element;
     
402.                 this.content[n] = parent;
     
403.                 // Update 'n' to continue at the new position.
     
404.                 n = parentN;
     
405.             }
     
406.             // Found a parent that is less, no need to move it further.
     
407.             else {
     
408.                 break;
     
409.             }
     
410.         }
     
411.     },
     
412. 
     
413.     sinkDown: function(n) {
     
414.         // Look up the target element and its score.
     
415.         var length = this.content.length,
     
416.             element = this.content[n],
     
417.             elemScore = this.scoreFunction(element);
     
418. 
     
419.         while(true) {
     
420.             // Compute the indices of the child elements.
     
421.             var child2N = (n + 1) * 2, child1N = child2N - 1;
     
422.             // This is used to store the new position of the element,
     
423.             // if any.
     
424.             var swap = null;
     
425.             // If the first child exists (is inside the array)...
     
426.             if (child1N < length) {
     
427.                 // Look it up and compute its score.
     
428.                 var child1 = this.content[child1N],
     
429.                     child1Score = this.scoreFunction(child1);
     
430.                 // If the score is less than our element's, we need to swap.
     
431.                 if (child1Score < elemScore)
     
432.                     swap = child1N;
     
433.             }
     
434.             // Do the same checks for the other child.
     
435.             if (child2N < length) {
     
436.                 var child2 = this.content[child2N],
     
437.                     child2Score = this.scoreFunction(child2);
     
438.                 if (child2Score < (swap == null ? elemScore : child1Score)){
     
439.                     swap = child2N;
     
440.                 }
     
441.             }
     
442. 
     
443.             // If the element needs to be moved, swap it, and continue.
     
444.             if (swap != null) {
     
445.                 this.content[n] = this.content[swap];
     
446.                 this.content[swap] = element;
     
447.                 n = swap;
     
448.             }
     
449.             // Otherwise, we are done.
     
450.             else {
     
451.                 break;
     
452.             }
     
453.         }
     
454.     }
     
455. };
     
456. 
     
457. this.kdTree = kdTree;
     
458. 
     
459. exports.kdTree = kdTree;
     
460. exports.BinaryHeap = BinaryHeap;

复制代码

1. 'use strict';
   
2. 
   
3. module.exports = KNN;
   
4. 
   
5. var KDTree = require('./kdtree').kdTree;
   
6. var Distances = require('ml-distance');
   
7. 
   
8. /**
   
9. * K-Nearest neighboor constructor.
   
10. *
    
11. * @param reload - loading purposes.
    
12. * @param model - loading purposes
    
13. * @constructor
    
14. */
    
15. function KNN(reload, model) {
    
16.     if(reload) {
    
17.         this.kdtree = model.kdtree;
    
18.         this.k = model.k;
    
19.         this.classes = model.classes;
    
20.     }
    
21. }
    
22. 
    
23. /**
    
24. * Function that trains the KNN with the given trainingSet and trainingLabels.
    
25. * The third argument is an object with the following options.
    
26. *  * distance: that represent the distance function applied (default: euclidean)
    
27. *  * k: the number of neighboors to take in count for classify (default: number of features + 1)
    
28. *
    
29. * @param trainingSet
    
30. * @param trainingLabels
    
31. * @param options
    
32. */
    
33. KNN.prototype.train = function (trainingSet, trainingLabels, options) {
    
34.     if(options === undefined) options = {};
    
35.     if(options.distance === undefined) options.distance = Distances.distance.euclidean;
    
36.     if(options.k === undefined) options.k = trainingSet[0].length + 1;
    
37. 
    
38.     var classes = 0;
    
39.     var exist = new Array(1000);
    
40.     var j = 0;
    
41.     for(var i = 0; i < trainingLabels.length; ++i) {
    
42.         if(exist.indexOf(trainingLabels[i]) === -1) {
    
43.             classes++;
    
44.             exist[j] = trainingLabels[i];
    
45.             j++;
    
46.         }
    
47.     }
    
48. 
    
49.     // copy dataset
    
50.     var points = new Array(trainingSet.length);
    
51.     for(i = 0; i < points.length; ++i) {
    
52.         points[i] = trainingSet[i].slice();
    
53.     }
    
54. 
    
55.     this.features = trainingSet[0].length;
    
56.     for(i = 0; i < trainingLabels.length; ++i) {
    
57.         points[i].push(trainingLabels[i]);
    
58.     }
    
59. 
    
60.     var dimensions = new Array(trainingSet[0].length);
    
61.     for(i = 0; i < dimensions.length; ++i) {
    
62.         dimensions[i] = i;
    
63.     }
    
64. 
    
65.     this.kdtree = new KDTree(points, options.distance, dimensions);
    
66.     this.k = options.k;
    
67.     this.classes = classes;
    
68. };
    
69. 
    
70. /**
    
71. * Function that returns the predictions given the dataset.
    
72. *
    
73. * @param dataset
    
74. * @returns {Array}
    
75. */
    
76. KNN.prototype.predict = function (dataset) {
    
77.     var predictions = new Array(dataset.length);
    
78.     for(var i = 0; i < dataset.length; ++i) {
    
79.         predictions[i] = this.getSinglePrediction(dataset[i]);
    
80.     }
    
81. 
    
82.     return predictions;
    
83. };
    
84. 
    
85. /**
    
86. * function that returns a prediction for a single case.
    
87. * @param currentCase
    
88. * @returns {number}
    
89. */
    
90. KNN.prototype.getSinglePrediction = function (currentCase) {
    
91.     var nearestPoints = this.kdtree.nearest(currentCase, this.k);
    
92.     var pointsPerClass = new Array(this.classes);
    
93.     var predictedClass = -1;
    
94.     var maxPoints = -1;
    
95.     var lastElement = nearestPoints[0][0].length - 1;
    
96. 
    
97.     for(var i = 0; i < pointsPerClass.length; ++i) {
    
98.         pointsPerClass[i] = 0;
    
99.     }
    
100. 
     
101.     for(i = 0; i < nearestPoints.length; ++i) {
     
102.         var currentClass = nearestPoints[i][0][lastElement];
     
103.         var currentPoints = ++pointsPerClass[currentClass];
     
104.         if(currentPoints > maxPoints) {
     
105.             predictedClass = currentClass;
     
106.             maxPoints = currentPoints;
     
107.         }
     
108.     }
     
109. 
     
110.     return predictedClass;
     
111. };
     
112. 
     
113. /**
     
114. * function that returns a KNN classifier with the given model.
     
115. *
     
116. * @param model
     
117. */
     
118. KNN.load = function (model) {
     
119.     if(model.modelName !== "KNN")
     
120.         throw new RangeError("The given model is invalid!");
     
121. 
     
122.     return new KNN(true, model);
     
123. };
     
124. 
     
125. /**
     
126. * function that exports the current KNN classifier.
     
127. */
     
128. KNN.prototype.export = function () {
     
129.     return {
     
130.         modelName: "KNN",
     
131.         kdtree: this.kdtree,
     
132.         k: this.k,
     
133.         classes: this.classes
     
134.     };
     
135. };

复制代码