Hard classification · geometry

Ask the neighbours

Classify a new point by asking the k closest points what they are.

k nearest neighbours is a model with no training at all: to label a new point, find the k labelled points closest to it and go with the most common label among them.

Write knn(points, labels, query, k): points is an array of [x, y] pairs, labels is an array of strings the same length, query is an [x, y] pair, and k is a whole number from 1 up. Use straight-line distance. Pick the k nearest points; on a distance tie, the lower index counts as nearer. Return the label that appears most among them. On a vote tie, return the tied label whose closest member is nearest to the query. If k is bigger than the number of points, use them all. With no points, return null.

Call show(path) where path starts at the query and visits each chosen neighbour from nearest to farthest, going back to the query after each one: [query, n1, query, n2, query, ...]. The stage draws the spokes.

Example: knn([[0, 0], [5, 5], [1, 0]], ["a", "b", "a"], [0, 1], 1) returns "a".

Tests you can see

knn([[0,0],[5,5],[1,0]], ["a","b","a"], [0,1], 1)"a"
knn([[0,0],[1,1],[2,2],[8,8],[9,9]], ["cat","dog","dog","cat","cat"], [1,2], 3)"dog"
knn([[0,0],[1,0],[9,9]], ["x","y","y"], [0,0], 10)"y"

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptknn()

function knn(points, labels, query, k) {
  // sort by distance, take k, count labels
  return labels[0];
}

function knn(points, labels, query, k) {
  // sort by distance, take k, count labels
  return labels[0];
}

Tab indents · Cmd/Ctrl+Enter runs