kNearestNeighbors

JavaScript, Algorithm, Array

Classifies a data point relative to a labelled data set, using the k-nearest neighbors algorithm.

  • Use Array.prototype.map() to map the data to objects. Each object contains the euclidean distance of the element from point, calculated using Math.hypot(), Object.keys() and its label.
  • Use Array.prototype.sort() and Array.prototype.slice() to get the k nearest neighbors of point.
  • Use Array.prototype.reduce() in combination with Object.keys() and Array.prototype.indexOf() to find the most frequent label among them.
const kNearestNeighbors = (data, labels, point, k = 3) => {
  const kNearest = data
    .map((el, i) => ({
      dist: Math.hypot(...Object.keys(el).map(key => point[key] - el[key])),
      label: labels[i]
    }))
    .sort((a, b) => a.dist - b.dist)
    .slice(0, k);

  return kNearest.reduce(
    (acc, { label }, i) => {
      acc.classCounts[label] =
        Object.keys(acc.classCounts).indexOf(label) !== -1
          ? acc.classCounts[label] + 1
          : 1;
      if (acc.classCounts[label] > acc.topClassCount) {
        acc.topClassCount = acc.classCounts[label];
        acc.topClass = label;
      }
      return acc;
    },
    {
      classCounts: {},
      topClass: kNearest[0].label,
      topClassCount: 0
    }
  ).topClass;
};
const data = [[0, 0], [0, 1], [1, 3], [2, 0]];
const labels = [0, 1, 1, 0];

kNearestNeighbors(data, labels, [1, 2], 2); // 1
kNearestNeighbors(data, labels, [1, 0], 2); // 0

Recommended snippets

  • kMeans

    JavaScript, Algorithm

    Groups the given data into k clusters, using the k-means clustering algorithm.

  • binarySearch

    JavaScript, Algorithm

    Finds the index of a given element in a sorted array using the binary search algorithm.

  • linearSearch

    JavaScript, Algorithm

    Finds the first index of a given element in an array using the linear search algorithm.