KNN classification: Complete Guide — Classification by Proximity

Summary — KNN (K-Nearest Neighbors) is the most intuitive classification algorithm there is: to classify a new point, you look at the k closest points in the training set and take a majority vote. It is a lazy learner: it learns nothing during training, it simply memorizes the data. All the analysis happens at prediction time. This simplicity makes it a powerful tool for tabular data and a fundamental pedagogical tool.

Mathematical Principle

1. Fundamental Principle

KNN is based on the following assumption: points that are close in feature space tend to belong to the same class.

To classify a new point x, the process involves three steps:
1. Calculate the distance between x and all training points.
2. Identify the k nearest neighbors (those with the smallest distances).
3. Vote: the predicted class is the majority class among these k neighbors.

2. Distance Metrics

The choice of distance is crucial in KNN. Here are the main metrics:

Euclidean Distance (L2):
$$d(x, y) = \sqrt{\sum_{i=1}^{p} (x_i – y_i)^2}$$

This is the “straight line” distance in space. It is the most intuitive and most commonly used by default.

Manhattan Distance (L1):
$$d(x, y) = \sum_{i=1}^{p} |x_i – y_i|$$

This is the grid-like distance (like city blocks in Manhattan). It is more robust to outliers than Euclidean distance.

Minkowski Distance (generalization):
$$d(x, y) = \left(\sum_{i=1}^{p} |x_i – y_i|^q\right)^{1/q}$$

With q=1 it’s Manhattan, with q=2 it’s Euclidean. q=3 or q=4 offer a compromise.

Cosine Similarity (for text and sparse features):
$$\text{sim}(x, y) = \frac{x \cdot y}{||x|| \cdot ||y||} = \frac{\sum x_i y_i}{\sqrt{\sum x_i^2} \sqrt{\sum y_i^2}}$$

Cosine measures the angle between two vectors rather than their distance. It is ideal for text classification (TF-IDF).

Mahalanobis Distance (takes correlations into account):
$$d_M(x, y) = \sqrt{(x – y)^T \Sigma^{-1} (x – y)}$$

where Σ is the covariance matrix. This distance automatically normalizes features and corrects for correlations.

3. Prediction Formula

The predicted class is the most frequent class among the k neighbors:

$$\hat{y} = \arg\max_{v} \sum_{i \in N_k(x)} I(y_i = v)$$

where N_k(x) is the set of k nearest neighbors of x, and I is the indicator function.

4. Distance Weighting

Instead of a simple vote (1 vote per neighbor), each neighbor can be weighted by the inverse of its distance:

$$\hat{y} = \arg\max_{v} \sum_{i \in N_k(x)} w_i \cdot I(y_i = v)$$

where w_i = 1/d(x, x_i). This variant gives more weight to very close neighbors and less to farther neighbors, which generally improves performance.

Intuition

“Tell me who your neighbors are, and I’ll tell you who you are.”

Imagine you arrive in a new city and you’re trying to guess whether a neighborhood is residential or commercial. You look at the nearby buildings: if most of them are shops, it’s probably commercial. If they’re houses, it’s residential. The more nearby buildings you look at (large k), the more stable but perhaps fuzzier the decision. The fewer you look at (small k), the more precise but volatile the decision.

The neighborhood vote analogy: KNN is like a neighborhood ballot. Each training point is a voter who shouts “I’m class A!” or “I’m class B!” The new point listens to the k nearest voters and adopts the loudest class.

Python Implementation

Example 1: KNN from scratch with brute-force search

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

class KNNClassifier:
    """K-Nearest Neighbors Classifier."""

    def __init__(self, n_neighbors=5, weights='uniform', metric='euclidean'):
        self.n_neighbors = n_neighbors
        self.weights = weights  # 'uniform' or 'distance'
        self.metric = metric

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
        return self

    def _compute_distances(self, X):
        if self.metric == 'euclidean':
            # Vectorized trick: ||x-y||^2 = ||x||^2 + ||y||^2 - 2xy
            X2 = np.sum(X ** 2, axis=1, keepdims=True)
            T2 = np.sum(self.X_train ** 2, axis=1, keepdims=True).T
            dists = np.sqrt(np.maximum(X2 + T2 - 2 * X @ self.X_train.T, 0))
        elif self.metric == 'manhattan':
            dists = np.zeros((X.shape[0], self.X_train.shape[0]))
            for i in range(X.shape[0]):
                dists[i] = np.sum(np.abs(X[i] - self.X_train), axis=1)
        return dists

    def predict(self, X):
        dists = self._compute_distances(X)
        predictions = []
        for i in range(X.shape[0]):
            # Indices of k nearest
            nn_idx = np.argsort(dists[i])[:self.n_neighbors]
            nn_labels = self.y_train[nn_idx]
            nn_dists = dists[i, nn_idx]

            if self.weights == 'distance':
                # Weighting by 1/distance
                unique_classes = np.unique(self.y_train)
                scores = np.zeros(len(unique_classes))
                for c in unique_classes:
                    mask = nn_labels == c
                    scores[np.where(unique_classes == c)[0][0]] = np.sum(1 / (nn_dists[mask] + 1e-8))
                predictions.append(unique_classes[np.argmax(scores)])
            else:
                # Simple majority vote
                counts = np.bincount(nn_labels)
                predictions.append(np.argmax(counts))

        return np.array(predictions)

# Loading Iris data
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.3, random_state=42
)

# Standardization (crucial for KNN!)
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_train_sc = scaler.fit_transform(X_train)
X_test_sc = scaler.transform(X_test)

# Our KNN
for k in [1, 3, 5, 7, 11]:
    knn = KNNClassifier(n_neighbors=k, weights='distance')
    knn.fit(X_train_sc, y_train)
    acc = accuracy_score(y_test, knn.predict(X_test_sc))
    print(f"k={k:2d} | Acc: {acc:.3f}")

Example 2: scikit-learn’s KNeighborsClassifier

from sklearn.neighbors import KNeighborsClassifier

# Comparing metrics
metrics_to_test = ['euclidean', 'manhattan', 'cosine']
for metric in metrics_to_test:
    knn_sk = KNeighborsClassifier(n_neighbors=5, metric=metric)
    knn_sk.fit(X_train_sc, y_train)
    acc = accuracy_score(y_test, knn_sk.predict(X_test_sc))
    print(f"Métrique: {metric:12s} | Acc: {acc:.3f}")

# Optimizing k with cross-validation
import matplotlib.pyplot as plt
k_range = range(1, 31)
train_scores = []
test_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train_sc, y_train)
    train_scores.append(accuracy_score(y_train, knn.predict(X_train_sc)))
    test_scores.append(accuracy_score(y_test, knn.predict(X_test_sc)))

plt.figure(figsize=(8, 5))
plt.plot(k_range, train_scores, 'b-o', label='Train', markersize=4)
plt.plot(k_range, test_scores, 'r-o', label='Test', markersize=4)
plt.axvline(x=k_range[np.argmax(test_scores)], color='green', linestyle='--',
    label=f'Optimal k={k_range[np.argmax(test_scores)]}')
plt.title('Impact of k on KNN performance')
plt.xlabel('Number of neighbors (k)')
plt.ylabel('Accuracy')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('knn_k_impact.png', dpi=150)

Example 3: Impact of standardization

# KNN without standardization
knn_raw = KNeighborsClassifier(n_neighbors=5)
knn_raw.fit(X_train, y_train)
raw_acc = accuracy_score(y_test, knn_raw.predict(X_test))

# KNN with standardization
knn_sc = KNeighborsClassifier(n_neighbors=5)
knn_sc.fit(X_train_sc, y_train)
sc_acc = accuracy_score(y_test, knn_sc.predict(X_test_sc))

print(f"\nKNN without standardization: {raw_acc:.3f}")
print(f"KNN with standardization:  {sc_acc:.3f}")
print("Note: KNN is extremely sensitive to feature scale.")

Hyperparameters

Advantages of KNN

1. Conceptual simplicity: No model training needed, no complex math, no optimization. The algorithm fits in a few lines.
2. Adaptability to new classes: Adding a new class requires no retraining — just add examples to the dataset.
3. Naturally non-linear boundaries: KNN automatically captures non-linear relationships between features, without needing manual transformations.
4. No distributional assumption: Unlike Naive Bayes (Gaussian distribution) or LDA (equal covariance), KNN makes no assumptions about the shape of the data.
5. Good practical performance: For moderate-sized tabular data, KNN is often competitive with more sophisticated models.

Limitations of KNN

1. High prediction cost: Each prediction requires computing the distance to all training points (O(n)). On large datasets, this is prohibitive.
2. Curse of dimensionality: In high dimensions, all distances become similar, making the notion of “nearest neighbor” uninformative. Performance drops after ~50-100 features.
3. Sensitivity to outliers and noise: A single outlier can attract distant neighbors and bias local predictions.
4. Need for standardization: Features with large scales dominate the distance. All features must be normalized. This is an unavoidable step.
5. Large storage requirement: KNN must keep all training data in memory. You can’t discard the dataset after training like you can with a parametric model.

4 Concrete Use Cases

1. Product Recommendation System

“Collaborative filtering” recommendation systems are essentially KNN: “Users who liked the same products as you (your neighbors) also liked X, so we recommend X to you.” Amazon, Netflix, and Spotify all use variants of this principle.

2. Document Classification by Similarity

In natural language processing, KNN with cosine similarity is used to classify documents: each text is represented in TF-IDF, and cosine similarity between vectors measures thematic similarity. It’s simple but effective for quick corpus categorization.

3. Anomaly Detection (Reverse KNN)

By computing the average distance to the k nearest neighbors for each point, you can identify anomalies: points with a high average distance are isolated in feature space and therefore potentially anomalous. This is an alternative approach to Isolation Forest.

4. Handwriting Recognition

Historically, KNN was one of the first methods used for handwritten digit recognition (MNIST). A new digit is compared to all training examples, and the k most similar ones vote for the class. With good standardization and k=3-5, KNN already achieves 96-97% on MNIST — competitive without neural networks.

Conclusion

KNN is the algorithm that embodies the principle “keep it simple.” It performs no explicit learning, computes no gradients, minimizes no cost function. It simply memorizes and compares. And yet, it remains competitive on many problems, especially for tabular data.

The prediction cost and the curse of dimensionality limit its use to moderate-sized datasets and reasonable dimensions. But within that scope, KNN remains a reference tool that should always be in your toolbox.

See Also

• Maîtriser la Manipulation des Chiffres dans les Carrés avec Python : Guide Complet et Astuces
• Python & expressions régulières : un duo gagnant pour traiter les données