How does K-Nearest Neighbors (K-NN) work in machine learning?
K-Nearest Neighbors (K-NN) is a supervised learning algorithm that predicts a target by examining the k training examples closest to a new observation. It solves classification and regression problems using a majority vote for classification or an average for regression. Its main trade-off is simplicity and interpretability versus slow prediction on large datasets and declining performance in high-dimensional spaces.
Read full answerHide full answer
Applies tomachine learning concepts; examples use scikit-learn 1.5+ (Python 3.12, NumPy 2.x)
How It Works
K-NN is a lazy learning algorithm: it does not build a predictive model during training. Instead, it stores the training examples and performs the expensive computation when a prediction is requested.
-
Given a new observation
x, calculate its distance from each stored training observation. -
Select the
ksmallest distances. -
For classification, return the most common class among those neighbors.
-
For regression, return the mean target value among those neighbors.
The Euclidean distance formula is:
d(x, x_i) = sqrt(sum((x_j - x_ij)^2))
-
xis the new observation. -
x_iis a stored training observation. -
jindexes the features. -
x_jandx_ijare feature values for the new and training observations. -
The sum measures the squared difference across all features.
With weights="distance", closer neighbors contribute more than distant neighbors. With weights="uniform", every neighbor contributes equally.
Distance Metrics and Feature Scaling
| Metric | Formula or Idea | Best Used When |
|---|---|---|
| Euclidean | Straight-line distance | Features are numeric and scaled |
| Manhattan | Sum of absolute differences | Feature differences should contribute linearly |
| Minkowski | Generalized distance with parameter p |
You need to tune the balance between Euclidean and Manhattan distance |
| Cosine | Compares vector direction using 1 - cosine similarity |
Direction matters more than magnitude |
Feature scaling is essential for K-NN because the algorithm relies on distance calculations. A feature measured in thousands can dominate one measured in units even when the latter is more informative. Standardization or normalization should therefore occur inside a Pipeline, ensuring the scaler is fitted only on training data.
Choosing k and Performance
-
Small
k: Low bias but high variance; sensitive to noise and outliers. -
Large
k: Higher bias and smoother decisions, but may underfit. -
Binary classification: An odd
koften avoids tie votes, although it does not guarantee an unbalanced result. -
Model selection: Use cross-validation, such as
GridSearchCV, to test values ofn_neighborsandweights.
Complexity depends on the nearest-neighbor implementation:
-
Training: Effectively
O(1)beyond storing or indexing the training data. -
Brute-force prediction:
O(n * d)per query, wherenis the number of training examples anddis the number of features. -
Memory: Typically
O(n * d)for the stored training data. -
Tree indexes: KD-trees and ball trees can accelerate exact searches in low-dimensional spaces, but become ineffective as dimensionality grows.
-
Large or high-dimensional data: Approximate nearest-neighbor libraries such as FAISS, Annoy, and HNSW-based implementations trade exactness for speed.
Code Example
This example tunes n_neighbors and neighbor weighting on the Iris dataset. StandardScaler is inside the pipeline so it is fitted separately within each cross-validation fold, preventing data leakage.
from sklearn.datasets import load_iris
from sklearn.model_selection import GridSearchCV, train_test_split, StratifiedKFold
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score
# Load a bundled dataset and create a reproducible train/test split.
X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.25, random_state=42, stratify=y
)
# Prevent scaling leakage by placing the scaler inside the pipeline.
pipeline = Pipeline([
("scaler", StandardScaler()),
("classifier", KNeighborsClassifier())
])
parameter_grid = {
"classifier__n_neighbors": [1, 3, 5, 7, 9, 11, 15, 21],
"classifier__weights": ["uniform", "distance"]
}
cross_validation = StratifiedKFold(
n_splits=5, shuffle=True, random_state=42
)
search = GridSearchCV(
estimator=pipeline,
param_grid=parameter_grid,
scoring="accuracy",
cv=cross_validation,
n_jobs=-1
)
search.fit(X_train, y_train)
predictions = search.predict(X_test)
test_accuracy = accuracy_score(y_test, predictions)
print("Best parameters:", search.best_params_)
print("Best cross-validation accuracy:", search.best_score_)
print("Test accuracy:", test_accuracy)
Practical Limitations
-
Slow prediction: Every query may require many distance calculations.
-
Memory usage: The complete training dataset generally remains in memory.
-
Curse of dimensionality: In high-dimensional spaces, distances become less discriminative and most neighbors may be similarly distant.
-
Irrelevant features: Uninformative features can distort distances unless they are removed or appropriately scaled.
-
Class imbalance: A majority class can dominate the vote, especially with large
k; balanced sampling, suitable weights, and imbalance-aware metrics may be needed. -
Missing values: Most K-NN implementations require missing values to be imputed before prediction.
-
Hardware: Scikit-learn’s CPU implementation is straightforward, while specialized approximate-neighbor libraries can better support large-scale workloads.
Common Pitfalls
-
Fitting preprocessing before splitting: This leaks test information into training. Use a
Pipeline. -
Forgetting to scale features: Unscaled features can produce incorrect neighbor selections.
-
Using accuracy for imbalanced data: Prefer macro F1, balanced accuracy, precision, recall, ROC-AUC, or PR-AUC as appropriate.
-
Choosing
kon the test set: Tune it with cross-validation and reserve the test set for final evaluation. -
Assuming linear relationships: K-NN captures local patterns but can be ineffective when the target depends on broad global trends.
-
Ignoring dimensionality: For many features, dimensionality reduction, relevant-feature selection, or an approximate-neighbor index may be necessary.
-
Common follow-up questions: Why does K-NN use lazy learning? How does
weights="distance"change predictions? When are KD-trees preferable to brute-force search? How would class imbalance affect a majority vote?