k-Nearest Neighbors
Description
Given a list of training points X (each a d-dimensional feature vector), a parallel list y of integer class labels, a query point with the same number of features, and an integer k, classify the query with the k-nearest-neighbors rule using Euclidean distance. Return the most frequent label among the k closest training points. If two or more labels are tied for most frequent, return the smallest of the tied labels. If a distance tie affects which points fall in the k nearest, prefer the point that appears earlier in X.
Examples
[[7,2],[5,3],[0,4],[3,2],[5,1],[9,8]], [0,0,0,0,1,0], [8,8], 30Among the 3 nearest training points by Euclidean distance, label 0 appears 3 times, more than any other label, so the majority result is 0.
[[3,7,8,9],[4,8,9,7],[7,7,7,9],[9,8,7,7],[4,1,5,1],[3,2,1,6],[6,4,6,7],[6,1,3,4]], [0,2,2,0,2,1,0,1], [7,6,2,1], 11With k = 1 the single nearest training point by Euclidean distance carries label 1, so the majority result is 1.
[[6,5,4,4],[5,5,2,4],[9,9,7,4],[4,7,6,1],[5,9,7,5],[5,2,5,0],[4,9,3,1]], [2,2,0,0,0,0,1], [0,7,3,3], 30Among the 3 nearest training points by Euclidean distance the labels split evenly with no single majority, so the smaller-label rule selects 0 and the majority result is 0.
Constraints
- •
1 ≤ k ≤ X.length ≤ 100 - •
X.length == y.length - •
All points and the query share the same dimension - •
Each label is a non-negative integer