k Nearest Neighbors (Classification): Complete Guide

Summary — The k nearest neighbors (k-NN) algorithm is one of the most intuitive and widely used supervised classification methods in machine learning. This guide explores in depth the mathematical principle, Python implementation with scikit-learn, hyperparameter selection, and concrete use cases.

Mathematical Principle

The k nearest neighbors algorithm is based on a remarkably elegant principle: to classify a new data point, we examine the k points in the training set that are closest to it, and assign it the majority class among these neighbors.

Euclidean Distance

The most commonly used distance metric is the Euclidean distance. For two points x and y in an n-dimensional space, it is calculated as:

$$d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i – y_i)^2}$$

This formula simply measures the length of the segment connecting the two points in the feature space. Each dimension corresponds to an explanatory variable of the problem.

Other Distance Metrics

Although the Euclidean distance is the most popular, the k nearest neighbors algorithm supports other metrics:

• Manhattan distance (L1): $$d(x, y) = \sum_{i=1}^{n}|x_i – y_i|$$ — useful when dimensions have very different scales or for sparse data.
• Minkowski distance: a parametric generalization that includes Euclidean (p=2) and Manhattan (p=1) as special cases.
• Hamming distance: for categorical or binary data.
• Cosine distance: for measuring angular similarity, widely used in natural language processing.

Decision Function

Once the k nearest neighbors are identified, the predicted class (\hat{y}) is obtained by majority vote:

$$\hat{y} = \text{argmax}{c \in C} \sum(y_i = c)$$}^{k} \mathbb{I

where C is the set of possible classes and (\mathbb{I}) is the indicator function that equals 1 if the condition is true, 0 otherwise.

In the weighted variant, each neighbor i receives a weight (w_i = 1/d(x, x_i)), giving more influence to the closest neighbors.

Intuition

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

This maxim perfectly summarizes the philosophy of k nearest neighbors. Imagine you move to a new neighborhood and want to know if it’s residential or commercial. The most natural thing would be to look at the buildings around you. If the majority are restaurants and shops, you’re probably in a commercial area. This is exactly the algorithm’s reasoning.

The Lazy Learning Algorithm

The term lazy learner perfectly describes k nearest neighbors. Why? Because during the training phase, the algorithm does… absolutely nothing. It simply memorizes the entire training dataset. All the computation work happens at prediction time, when it’s necessary to find the nearest neighbors of a new point.

This approach has a definite advantage: training is nearly instantaneous, regardless of the dataset size. On the other hand, prediction can become expensive because it requires computing distances between the new point and all training points.

The Bias-Variance Tradeoff and the Choice of k

The parameter k is the algorithm’s main control lever:

• k = 1: each point is its own classifier. The decision boundary perfectly fits the training data. Result: low bias but high variance. We overfit the noise in the data.
• k very large (close to n): the prediction tends toward the global majority class. The model becomes too smooth, too rigid. High bias, low variance (underfitting).
• k optimal: the sweet spot, generally between 3 and 21, often odd for binary problems to avoid ties during voting.

In practice, the optimal value of k is determined by cross-validation, systematically testing several values and retaining the one that maximizes performance on a validation set.

Python Implementation

Let’s dive into code with the scikit-learn library, which offers a robust and optimized implementation of k nearest neighbors via KNeighborsClassifier.

Basic Example with the Iris Dataset

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, accuracy_score

# Load the Iris dataset
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=42
)

# Create and train the model
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)

# Prediction and evaluation
y_pred = knn.predict(X_test)
print(f"Accuracy (k=5): {accuracy_score(y_test, y_pred):.4f}")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Comparing Multiple Values of k

It is essential to find the optimal value of k. Here’s how to systematically explore a range of values:

import matplotlib.pyplot as plt
import numpy as np

from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score

# Generate a synthetic dataset
X, y = make_classification(
    n_samples=1000, n_features=10, n_informative=5, n_redundant=2,
    n_clusters_per_class=1, random_state=42
)

# Explore k from 1 to 50
k_range = range(1, 51)
accuracies = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X, y, cv=5, scoring='accuracy')
    accuracies.append(scores.mean())

# Visualization
plt.figure(figsize=(10, 6))
plt.plot(k_range, accuracies, marker='o', linestyle='-', color='steelblue')
plt.axvline(x=k_range[np.argmax(accuracies)], color='red', linestyle='--',
            label=f"Optimal k = {k_range[np.argmax(accuracies)]}")
plt.xlabel('Number of neighbors (k)')
plt.ylabel('Mean accuracy (5-fold cross-validation)')
plt.title('Accuracy as a function of k — k nearest neighbors')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

Visualizing Decision Boundaries

Decision boundaries visually illustrate how the algorithm separates classes depending on the value of k:

from matplotlib.colors import ListedColormap
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=300, noise=0.15, random_state=42)

# Create a grid for visualization
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                     np.linspace(y_min, y_max, 200))

fig, axes = plt.subplots(1, 3, figsize=(18, 5))
cmap = ListedColormap(['#FF6B6B', '#4ECDC4'])

for ax, k in zip(axes, [1, 5, 15]):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X, y)

    # Prediction on the grid
    Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    ax.contourf(xx, yy, Z, alpha=0.3, cmap=cmap)
    ax.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap, edgecolor='white', s=40)
    ax.set_title(f'Decision boundaries — k = {k}')
    ax.set_xlim(x_min, x_max)
    ax.set_ylim(y_min, y_max)

plt.suptitle('Impact of k on decision boundaries of k nearest neighbors', fontsize=14)
plt.tight_layout()
plt.show()

Impact of Scaling

k nearest neighbors are particularly sensitive to the scale of features. If one variable is measured in thousands and another in decimals, the former will entirely dominate the distance calculation. It is therefore crucial to normalize or standardize the data:

from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

# Pipeline with integrated standardization
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(n_neighbors=5))
])

# The pipeline automatically applies scaling before training
pipeline.fit(X_train, y_train)
y_pred = pipeline.predict(X_test)
print(f"Accuracy with scaling: {accuracy_score(y_test, y_pred):.4f}")

Hyperparameters

Here is a summary table of the main hyperparameters of KNeighborsClassifier in scikit-learn:

Practical Recommendations

• Always start by varying n_neighbors between 1 and (\sqrt{n}) (where n is the training set size).
• If your data is not balanced, prefer weights=”distance” to reduce the influence of the majority class.
• For large datasets (> 10,000 samples), test algorithm=”ball_tree” for better performance.
• If prediction time is critical, consider approximate indexing structures like Approximate Nearest Neighbors (ANN).

Advantages and Limitations

Advantages

• Conceptual simplicity: the algorithm is easy to understand and explain, which is a major asset for projects where transparency is required.
• No distributional assumption: unlike logistic regression or discriminant analysis, k nearest neighbors make no assumption about the underlying distribution of the data. It naturally adapts to complex nonlinear decision boundaries.
• Native multi-class: directly handles problems with more than two classes, without resorting to one-vs-all strategies.
• Instant training: the learning phase boils down to storing the data, which is useful when training data arrives continuously.
• Easy updates: adding new training data requires no retraining of the model.

Limitations

• Curse of dimensionality: in high dimensions, all pairs of points tend to have similar distances, making the notion of “nearest neighbor” less discriminative. Performance degrades significantly beyond a few dozen dimensions.
• Slow prediction: for each new prediction, the algorithm must compute distances to all training points. On a dataset of 1 million samples, this can take several seconds per query.
• Memory consumption: the model must keep the entire training set in memory, which can be prohibitive for very large databases.
• Sensitivity to unscaled variables: as mentioned above, the absence of scaling can completely distort the results.
• Sensitivity to noise and outliers: with a small k, a single aberrant neighbor can change the prediction. This is why the choice of k is so critical.

Use Cases

1. Content Recommendation System

Streaming platforms use k nearest neighbors to suggest movies or series. Each user is represented by a preference vector (genres watched, ratings given, viewing time). When recommending content to a given user, the k most similar users are identified, and the titles they enjoyed but our user hasn’t discovered yet are suggested. This collaborative approach is particularly effective for large catalogs.

2. Handwritten Character Recognition

The classification of handwritten digits (MNIST dataset) is a historical textbook case for k nearest neighbors. Each 28×28 pixel image is flattened into a 784-dimensional vector. By applying prior dimensionality reduction (PCA) and judiciously choosing the distance metric, recognition rates above 96% are achieved. Although convolutional neural networks now surpass this approach, k-NN remains a valuable pedagogical reference.

3. Medical Diagnosis by Analogy

In some diagnostic assistance systems, a new patient case is compared to medical records stored in the database. k nearest neighbors identify patients with the most similar clinical profiles (symptoms, test results, medical history). The majority diagnosis among these neighbors constitutes a diagnostic lead that the doctor can explore. This approach is particularly useful for rare diseases where similar cases are few but highly informative.

4. Anomaly and Fraud Detection

By reversing the logic, k nearest neighbors can be used to detect unusual observations. If the average distance from a point to its k nearest neighbors is abnormally high, the point is likely an anomaly. This technique is used in banking fraud detection: a transaction whose profile significantly deviates from the customer’s usual transactions and those of their peers will be flagged for manual review. Variants like the Local Outlier Factor (LOF) extend this fundamental idea.

Summary of Best Practices

1. Always standardize your data before applying k-NN (StandardScaler or MinMaxScaler).
2. Use cross-validation to determine the optimal k — never rely on a single default value.
3. Reduce dimensionality (PCA, t-SNE, UMAP) if the number of features is high, to combat the curse of dimensionality.
4. Prefer weights=”distance” when classes are imbalanced.
5. Limit the training set size if prediction speed is critical (condensing, editing, or sampling).
6. Test multiple distance metrics: Manhattan can outperform Euclidean for certain data distributions.

See Also

• Multiplying Strings with Python
• Master the Art of Reverse Engineering in Python: Complete Guide for Beginners and Experts