Nearest Neighbor Algorithm

Overview


The nearest neighbor algorithm is an algorithm designed to estimate a datapoints properties, including possibly the category to which the point belongs, by examining the points near to the given point. For example, one might look at the nearest k neighbors to the point in question, and then assign a category to the point based on which category appears the most in the examined neighbors.

The algorithm depends on having a function, called a metric, which measures the "distance" between points in order to determine which points are closest to the point in question.

Example


The following example sorts a dataset by the distance from each point to the given point. 


let data = $url('/lib/machine-learning/nearest-neighbor/v1.0.0/site/sample.json');

var metric = (p,q) =>{ 
  //return a distance meaure between p and q	
  return Math.sqrt((p.point1 - q.point1)*(p.point1 - q.point1) + (p.point2 - q.point2)*(p.point2 - q.point2))
};

let q = data[0];
let neighbors = $list(data).map(p => {
  return {
    item: p,
    distance: metric(p, q)
  }
}).sort(p => p.distance);
Try it!

Contents