mljs / knn

A k-nearest neighboor classifier algorithm.

knn

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

• k-d trees

Installation

$ npm i ml-knn

API

new KNN(dataset, labels[, options])

Instantiates the KNN algorithm.

Arguments:

• dataset - A matrix (2D array) of the dataset.
• labels - An array of labels (one for each sample in the dataset).
• options - Object with the options for the algorithm.

Options:

• k - number of nearest neighbors (Default: number of labels + 1).
• distance - distance function for the algorithm (Default: euclidean distance).

Example:

var train_dataset = [
  [0, 0, 0],
  [0, 1, 1],
  [1, 1, 0],
  [2, 2, 2],
  [1, 2, 2],
  [2, 1, 2],
];
var train_labels = [0, 0, 0, 1, 1, 1];
var knn = new KNN(train_dataset, train_labels, { k: 2 }); // consider 2 nearest neighbors

predict(newDataset)

Predict the values of the dataset.

Arguments:

• newDataset - A matrix that contains the dataset.

Example:

var test_dataset = [
  [0.9, 0.9, 0.9],
  [1.1, 1.1, 1.1],
  [1.1, 1.1, 1.2],
  [1.2, 1.2, 1.2],
];

var ans = knn.predict(test_dataset);

console.log(ans);
// classification result:
// ans = [ 0, 0, 1, 1 ]
// Based on the training data, the first two points of the test dataset are classified as "0" (type 0, perhaps),
// the third and fourth data points are classified as "1".

toJSON()

Returns an object representing the model. This function is automatically called if JSON.stringify(knn) is used.
Be aware that the serialized model takes about 1.3 times the size of the input dataset (it actually is the dataset in a tree structure). Stringification can fail if the resulting string is too large.

KNN.load(model[, distance])

Loads a model previously exported by knn.toJSON(). If a custom distance function was provided, it must be passed again.

External links

Check this cool blog post for a detailed example: https://hackernoon.com/machine-learning-with-javascript-part-2-da994c17d483

License

MIT

knn's Issues

Saving KNN Model

@maasencioh @targos what's the best way to save a trained model for later use?

Uncaught TypeError: Cannot read property 'nearest' of undefined at O.getSinglePrediction (knn.js:91)

when i use web version, it pops me this error.
Uncaught TypeError: Cannot read property 'nearest' of undefined at O.getSinglePrediction (knn.js:91)

Why are error and accuracy not returned?

Default k value

The default k value is the dimensionality of the data points + 1

Is there a motivation behind this? I can see how it would fail if the dimensionality of the points is comparable or higher than the number of data points.

I would have rather made the option mandatory for the user of the library.

Cannot read property 'length' of undefined

at new KDTree (/Users/DBRSJ/node_modules/ml-knn/lib/index.js:36:51)
at new KNN (/Users/DBRSJ/node_modules/ml-knn/lib/index.js:323:23)
at train (/Users/DBRSJ/Desktop/JS_Color/Knn.js:55:11)
at dressData (/Users/DBRSJ/Desktop/JS_Color/Knn.js:51:5)
at Converter.csv.fromFile.on.on (/Users/DBRSJ/Desktop/JS_Color/Knn.js:22:9)
at emitOne (events.js:121:20)
at Converter.emit (events.js:211:7)
at Timeout._onTimeout (/Users/DBRSJ/node_modules/csvtojson/v2/Converter.js:41:23)
at ontimeout (timers.js:498:11)
at tryOnTimeout (timers.js:323:5)
at Timer.listOnTimeout (timers.js:290:5)

Label not random when k=1 and multiple nodes within distance

In a situation where 2 different nodes are the same distance from the test node, the returned label is always the last one.
For example:

import KNN from 'ml-knn';

var train_dataset = [
    [1, 1, 1],
    [1, 1, 1],
    [0, 0, 0],
];
var train_labels = ["A", "B", "C"];
var knn = new KNN(train_dataset, train_labels, { k: 1 });

var test_data = [1, 1, 1];

var ans = knn.predict(test_data);

console.log(ans);
// > B

There are 2 nodes with the same coordinates, $(1, 1, 1)$. The test node has the same coordinates. Expected results would be to randomly choose between node A and node B, but instead, B is always chosen. If the labels A and B er switched, the output will be A every time.

knn.predict(dataset) of sample code causes exception

Was attempting to use the basic sample code provided on the npm page for this package:

const KNN = require('ml-knn')

var dataset = [[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];
var knn = new KNN(dataset, predictions);

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

The above code caused the following exception:

/node_modules/ml-knn/lib/index.js:91
                if (bestNodes.size() < maxNodes || ownDistance < bestNodes.peek()[1]) {
                                                                                 ^

TypeError: Cannot read property '1' of undefined
    at nearestSearch (/home/stefano/coding/CS4404/CS4404-Project-1/node_modules/ml-knn/lib/index.js:91:82)
    at nearestSearch (/home/stefano/coding/CS4404/CS4404-Project-1/node_modules/ml-knn/lib/index.js:109:13)
    at nearestSearch (/home/stefano/coding/CS4404/CS4404-Project-1/node_modules/ml-knn/lib/index.js:109:13)
    at KDTree.nearest (/home/stefano/coding/CS4404/CS4404-Project-1/node_modules/ml-knn/lib/index.js:134:13)
    at getSinglePrediction (/home/stefano/coding/CS4404/CS4404-Project-1/node_modules/ml-knn/lib/index.js:384:36)
    at KNN.predict (/home/stefano/coding/CS4404/CS4404-Project-1/node_modules/ml-knn/lib/index.js:374:38)
    at Object.<anonymous> (/home/stefano/coding/CS4404/CS4404-Project-1/test.js:9:15)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)

Instantiating the model seems to work okay, but any use of the predict(dataset) function seems to cause the problem.

Cannot instantiate classifier if options is undefined

const KNN = require('ml-knn');
const dataset = [[0, 0, 0], [0, 1, 1], [1, 1, 0], [2, 2, 2], [1, 2, 2], [2, 1, 2]];
const labels = [0, 0, 0, 1, 1, 1];
const knn = new KNN(dataset, labels); // it will throw here because options is expected to be an object

Serialise/Deserialise not working?

When running the reproduction code:

Reproduction

The following error occurs when loading from JSON:

node_modules\ml-distance-euclidean\euclidean.js:6
d += (p[i] - q[i]) * (p[i] - q[i]);
^
TypeError: Cannot read property '0' of undefined
at squaredEuclidean (\node_modules\ml-distance-euclidean\euclidean.js:6:23)
at euclidean (\node_modules\ml-distance-euclidean\euclidean.js:12:22)
at nearestSearch (\node_modules\ml-knn\lib\index.js:66:33)
at KDTree.nearest (\node_modules\ml-knn\lib\index.js:134:13)
at getSinglePrediction (\node_modules\ml-knn\lib\index.js:384:36)
at KNN.predict (\node_modules\ml-knn\lib\index.js:374:38)
at Object. (index.js:30:23)
at Module._compile (internal/modules/cjs/loader.js:689:30)
at Object.Module._extensions..js (internal/modules/cjs/loader.js:700:10)
at Module.load (internal/modules/cjs/loader.js:599:32)