KNN Classification

For classification, KNN predicts a class by majority vote among the k nearest labeled neighbors — the simplest possible aggregation rule, and the reason KNN's decision boundaries look nothing like a linear model's.

Formula

\(y_{(1)}, \dots, y_{(k)}\) are the labels of the \(k\) nearest neighbors, sorted by distance. The predicted class is simply whichever label appears most often among them — see How KNN Works for this computed by hand.

Decision Boundaries — Jagged, Not Straight

This flexibility is a genuine advantage for genuinely non-linear class boundaries — but it's also exactly why small k can overfit: a lower k lets the boundary bend around individual noisy points, producing an unnecessarily jagged, unstable shape.

Weighted Voting — A Common Refinement

Plain majority voting treats the nearest and the k-th nearest neighbor equally. Distance-weighted voting gives closer neighbors more say:

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(n_neighbors=5, weights="distance")
# closer neighbors contribute more to the vote than farther ones within the k selected

Python Implementation

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score, classification_report
from sklearn.datasets import load_breast_cancer

data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.2, random_state=42, stratify=data.target
)

scaler = StandardScaler().fit(X_train)
X_train_scaled = scaler.transform(X_train)
X_test_scaled = scaler.transform(X_test)

model = KNeighborsClassifier(n_neighbors=5)
model.fit(X_train_scaled, y_train)

predictions = model.predict(X_test_scaled)
print(accuracy_score(y_test, predictions))
print(classification_report(y_test, predictions))

Practical Use Cases

• Image classification on small datasets, using raw or extracted pixel features
• Recommendation systems ("users like you also bought...")
• Any problem where the true decision boundary is genuinely irregular, not a straight line or smooth curve

Common Mistakes

• Using plain majority voting on imbalanced data — a common class can dominate votes even among the nearest neighbors, unless weights="distance" or class-aware sampling is used.
• Not scaling features before classification, letting distance calculations be skewed by feature magnitude rather than genuine similarity.

Interview Relevance

Q: "Why does KNN's decision boundary look different from logistic regression's?" Logistic regression's boundary is constrained to be linear (a straight line/plane) by its equation; KNN's boundary is defined implicitly by wherever local neighborhoods flip majority class, letting it take on arbitrarily irregular shapes that follow the actual local data structure.

Practice Question

Using distance-weighted voting instead of plain majority voting, would a tied vote (equal count of each class among neighbors) still be possible? Explain why or why not.

Related ML Notes

• KNN Regression
• Confusion Matrix
• Decision Tree