Nearest neighbor methods are based on a simple idea. We consider our training set as the model and make predictions on new points based on how close they are to points in the training set. The most naïve way is to make the prediction as the closest training data point class. But since most datasets contain a degree of noise, a more common method would be to take a weighted average of a set of k nearest neighbors. This method is called k-nearest neighbors (k-NN).

Given a training dataset , with corresponding targets , we can make a prediction on a point, z, by looking at a set of nearest neighbors. The actual method of prediction depends on whether or not we are doing regression (continuous ) or classification (discrete ).

For discrete classification targets, the prediction may be given by a maximum voting scheme weighted by the distance to the prediction point:

Here, our prediction, f(z) is the maximum weighted value over all classes, j, where the weighted distance from the prediction...