K Nearest Neighbor

About

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.

Can be used for K-NN classification and regression.

Can use the distance of neighbots to weight the contribution.

To classify node 9, we consider node 2,6,7,8 value weighted by distance.

Data Structures

By default scikit-learn, uses brute force.

The most naive neighbor search implementation involves the brute-force computation of distances between all pairs of points in the dataset: for N samples in D dimensions, this approach scales as O(DN^2)

K-D tree runtime is O(D Nlogn(n)).