k-Nearest-Neighbors¶

k-NN is a straightforward prediction method that has no model parameters. Predictions are made directly from the data. Because k-NN is different from most other models, it is useful to include as a baseline model.

The Algorithm¶

To make a prediction for a new data point:

Choose the hyperparameter k

Calculate the distance of the new data point to all training data points

Identify the k closest ones by a distance metric

Calculate the most frequent target value (classification) or their average (regression)

Output the result of step 3 as a prediction

Distance Metrics¶

The performance of k-NN strongly depends on the choice of the distance metric. Here are some options:

Euclidean Distance (default)
Manhattan Distance
Cosine Similarity
Minkowski Distance

k-NN in scikit-learn¶

from sklearn.neighbors import KNeighborsClassifier

m = KNeighborsClassifier(n_neighbors=5, metric='euclidean')
m.fit(...)

There is also a KNeighborsRegressor.

Pros and Cons¶

Pros	Cons
easy to understand	slow, O(N) for each prediction
easy to explain
good baseline model