Machine Learning
What is KNN?
KNN (K-Nearest Neighbors) classifies an example by the majority of its k nearest neighbors.
What is KNN?
K nearest neighbours (KNN) decides an example's class by the majority vote of the K training examples closest to it. It is the algorithm of the idea "tell me who your friends are and I'll tell you who you are".
from sklearn.neighbors import KNeighborsClassifier
X = [[1, 1], [1, 2], [6, 6], [6, 7]]
y = ["A", "A", "B", "B"]
m = KNeighborsClassifier(n_neighbors=3).fit(X, y)
print(m.predict([[2, 2]])) # ['A']
KNN can be said to have no training: fit only stores the data and the real work happens at prediction time. That's why it is called a "lazy learner".
Strengths and weaknesses
KNN is simple and can learn complex boundary shapes. But:
- Prediction is slow: for every query the distance to all training examples is computed.
- It is scale-sensitive: a feature with large units (salary) overwhelms one with small units (age).
- In high-dimensional data the notion of "nearest" loses its meaning (the curse of dimensionality).
That's why scaling is usually done before KNN.
Exercise First KNN
Train a KNeighborsClassifier(n_neighbors=3) and print the classes of the points [[2, 2]] and [[6, 5]] with a single predict call.
Show example solution
from sklearn.neighbors import KNeighborsClassifier
X = [[1, 1], [1, 2], [2, 1], [6, 6], [6, 7], [7, 6]]
y = ["A", "A", "A", "B", "B", "B"]
m = KNeighborsClassifier(n_neighbors=3).fit(X, y)
print(m.predict([[2, 2], [6, 5]]))
Test yourself
-
What does the <code>fit</code> call do in KNN?
- It clusters the data
- It stores the training data
- It learns weights
- It fits a line
Show answer
It stores the training data — Distances are computed at prediction time against all stored examples.
-
Create a KNN classifier with 5 neighbours.
m = KNeighborsClassifier(____=5)
Show answer
m = KNeighborsClassifier(n_neighbors=5)
-
Match the concepts.
- K
- Number of voting neighbours
- majority vote
- Class decision
- lazy learner
- Only stores during training
- curse of dimensionality
- Distance problem in many dimensions
Next lesson: The K parameter
