k-Nearest Neighbors Algorithm

The k-nearest neighbors algorithm (k-NN) is a supervised Machine Learning algorithm. It's a classification algorithm, determining the class of a sample vector using a sample data.

In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor.

The idea is to calculate the similarity between two data points on the basis of a distance metric. Euclidean distance is used mostly for this task.

Image source: Wikipedia

The algorithm is as follows:

Check for errors like invalid data/labels.
Calculate the euclidean distance of all the data points in training data with the classification point
Sort the distances of points along with their classes in ascending order
Take the initial K classes and find the mode to get the most similar class
Report the most similar class

Here is a visualization of k-NN classification for better understanding:

Image source: Wikipedia

The test sample (green dot) should be classified either to blue squares or to red triangles. If k = 3 (solid line circle) it is assigned to the red triangles because there are 2 triangles and only 1 square inside the inner circle. If k = 5 (dashed line circle) it is assigned to the blue squares (3 squares vs. 2 triangles inside the outer circle).

Another k-NN classification example:

Image source: GeeksForGeeks

Here, as we can see, the classification of unknown points will be judged by their proximity to other points.

It is important to note that K is preferred to have odd values in order to break ties. Usually K is taken as 3 or 5.

Code

kNN.js

/**
 * Classifies the point in space based on k-nearest neighbors algorithm.
 *
 * @param {number[][]} dataSet - array of data points, i.e. [[0, 1], [3, 4], [5, 7]]
 * @param {number[]} labels - array of classes (labels), i.e. [1, 1, 2]
 * @param {number[]} toClassify - the point in space that needs to be classified, i.e. [5, 4]
 * @param {number} k - number of nearest neighbors which will be taken into account (preferably odd)
 * @return {number} - the class of the point
 */

import euclideanDistance from '../../math/euclidean-distance/euclideanDistance';

export default function kNN(
  dataSet,
  labels,
  toClassify,
  k = 3,
) {
  if (!dataSet || !labels || !toClassify) {
    throw new Error('Either dataSet or labels or toClassify were not set');
  }

  // Calculate distance from toClassify to each point for all dimensions in dataSet.
  // Store distance and point's label into distances list.
  const distances = [];
  for (let i = 0; i < dataSet.length; i += 1) {
    distances.push({
      dist: euclideanDistance([dataSet[i]], [toClassify]),
      label: labels[i],
    });
  }

  // Sort distances list (from closer point to further ones).
  // Take initial k values, count with class index
  const kNearest = distances.sort((a, b) => {
    if (a.dist === b.dist) {
      return 0;
    }
    return a.dist < b.dist ? -1 : 1;
  }).slice(0, k);

  // Count the number of instances of each class in top k members.
  const labelsCounter = {};
  let topClass = 0;
  let topClassCount = 0;
  for (let i = 0; i < kNearest.length; i += 1) {
    if (kNearest[i].label in labelsCounter) {
      labelsCounter[kNearest[i].label] += 1;
    } else {
      labelsCounter[kNearest[i].label] = 1;
    }
    if (labelsCounter[kNearest[i].label] > topClassCount) {
      topClassCount = labelsCounter[kNearest[i].label];
      topClass = kNearest[i].label;
    }
  }

  // Return the class with highest count.
  return topClass;
}

References

k-nearest neighbors algorithm on Wikipedia

Code

References

Practice

Top K Elements

On this page

k-Nearest Neighbors Algorithm

CodeCopy Anchor Link

ReferencesCopy Anchor Link

Practice

Top K Elements

On this page

Code

References