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
Because the boundary follows wherever local neighborhoods flip majority class, KNN can carve out irregular shapes that a straight-line model like logistic regression simply can't represent.
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 selectedPython 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.
