K-Nearest Neighbors

Machine Learning · Beginner

Definition

KNN predicts a label by taking a majority vote of the k closest training points.

Simple, no training phase, and a great intuition builder.

Diagram

Flowchart

Example: 1D KNN

data = [(1, 'A'), (2, 'A'), (8, 'B'), (9, 'B')]
x = 3
near = sorted(data, key=lambda p: abs(p[0] - x))[:3]
labels = [l for _, l in near]
print(max(set(labels), key=labels.count))

Output: A

Complexity

Prediction O(n·d) per query

Key points

Scale features first
Odd k avoids ties
Slow on large datasets

Interview questions

Effect of small k?

Low bias, high variance — sensitive to noise.