K-Nearest Neighbors: The Simplest ML Algorithm

Juan Luis Ramirez8 min read
Machine LearningKNNClassificationPython

If you had to guess which movie a friend might enjoy, you'd likely look at what they and their closest inner circle have watched lately. This is the essence of K-Nearest Neighbors (KNN)—it makes predictions based on the company a data point keeps. It's brilliantly intuitive, requires no formal training phase, and remains one of the most powerful "low-effort, high-reward" algorithms in the data scientist's toolkit.

The Intuition Behind KNN

Imagine you're at a party and you want to guess someone's music taste. The most logical approach? Look at the people standing closest to them and assume they share similar preferences. KNN works exactly like this.

The algorithm follows a simple principle: similar things exist in close proximity. When classifying a new data point, KNN finds the K closest points in the training data and assigns the majority class among those neighbors.

No complex math. No gradient descent. Just measuring distances and counting votes.

How KNN Works: A Visual Explanation

Let's walk through the algorithm step by step:

  1. Choose K: Decide how many neighbors to consider (e.g., K=5)
  2. Calculate distances: Measure the distance from the new point to all training points
  3. Find neighbors: Identify the K closest training points
  4. Vote: For classification, take the majority class; for regression, take the average value
  5. Predict: Assign the result to the new point

Here's a visual representation:

    Class A (●)    Class B (■)    New Point (★)
 
         ●
              ●
    ■              ★
         ■    ●
              ■
 
    If K=3, the 3 nearest neighbors are: ●, ●, ■
    Majority vote: Class A wins (2 vs 1)
    Prediction: ★ belongs to Class A

Distance Metrics: Measuring Similarity

The choice of distance metric significantly impacts KNN's performance. Here are the three most common:

Euclidean Distance

The straight-line distance between two points. Think of it as the length of a ruler connecting them.

import numpy as np
 
def euclidean_distance(point1, point2):
    """Calculate the straight-line distance between two points."""
    return np.sqrt(np.sum((point1 - point2) ** 2))
 
# Example
a = np.array([1, 2])
b = np.array([4, 6])
print(f"Euclidean distance: {euclidean_distance(a, b):.2f}")  # Output: 5.00

Formula: $d = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$

Best for: Continuous features with similar scales.

Manhattan Distance

Also called "city block" or "taxicab" distance. It measures distance along axes at right angles, like navigating a grid of city streets.

def manhattan_distance(point1, point2):
    """Calculate the sum of absolute differences."""
    return np.sum(np.abs(point1 - point2))
 
# Example
print(f"Manhattan distance: {manhattan_distance(a, b)}")  # Output: 7

Formula: $d = \sum_{i=1}^{n}|x_i - y_i|$

Best for: High-dimensional data, or when features represent different units.

Minkowski Distance

A generalization that includes both Euclidean (p=2) and Manhattan (p=1) as special cases.

def minkowski_distance(point1, point2, p):
    """Generalized distance metric with parameter p."""
    return np.sum(np.abs(point1 - point2) ** p) ** (1/p)
 
# p=1 gives Manhattan, p=2 gives Euclidean
print(f"Minkowski (p=1): {minkowski_distance(a, b, 1)}")  # Manhattan
print(f"Minkowski (p=2): {minkowski_distance(a, b, 2):.2f}")  # Euclidean
print(f"Minkowski (p=3): {minkowski_distance(a, b, 3):.2f}")  # Cubic

Formula: $d = \left(\sum_{i=1}^{n}|x_i - y_i|^p\right)^{1/p}$

Choosing the Right K Value

The choice of K is crucial and involves a bias-variance tradeoff:

  • Small K (e.g., K=1): Low bias, high variance. The model is sensitive to noise and outliers.
  • Large K (e.g., K=50): High bias, low variance. The model becomes too general and may miss local patterns.

Finding the Optimal K

Use cross-validation to find the sweet spot:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
 
# Load sample data
X, y = load_iris(return_X_y=True)
 
# Test different K values
k_range = range(1, 31)
cv_scores = []
 
for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())
 
# Find the best K
best_k = k_range[np.argmax(cv_scores)]
print(f"Optimal K: {best_k} with accuracy: {max(cv_scores):.3f}")
 
# Visualize
plt.figure(figsize=(10, 6))
plt.plot(k_range, cv_scores, marker='o', linewidth=2, markersize=4)
plt.xlabel('K (Number of Neighbors)', fontsize=12)
plt.ylabel('Cross-Validation Accuracy', fontsize=12)
plt.title('Finding the Optimal K Value', fontsize=14)
plt.axvline(x=best_k, color='r', linestyle='--', label=f'Best K = {best_k}')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

Pro tip: Use odd K values for binary classification to avoid ties.

The Curse of Dimensionality

KNN struggles with high-dimensional data. As dimensions increase, distances become less meaningful—all points appear roughly equidistant.

Consider this: in 1D, your neighbors are clearly close. In 1000D, the concept of "nearest" loses significance because the volume of space grows exponentially.

Symptoms of the Curse

  • Performance degrades with more features
  • Distance metrics become unreliable
  • More data is needed to maintain density

Solutions

  1. Dimensionality reduction: Use PCA or t-SNE before applying KNN
  2. Feature selection: Keep only the most relevant features
  3. Feature weighting: Give more importance to discriminative features
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline
 
# Create a pipeline with PCA + KNN
pipeline = Pipeline([
    ('pca', PCA(n_components=10)),  # Reduce to 10 dimensions
    ('knn', KNeighborsClassifier(n_neighbors=5))
])
 
# Fit and predict
pipeline.fit(X_train, y_train)
predictions = pipeline.predict(X_test)

Python Implementation with Scikit-Learn

Let's build a complete, runnable example:

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report, confusion_matrix
from sklearn.datasets import load_breast_cancer
import matplotlib.pyplot as plt
import seaborn as sns
 
# Load the breast cancer dataset
data = load_breast_cancer()
X, y = data.data, data.target
feature_names = data.feature_names
target_names = data.target_names
 
print(f"Dataset shape: {X.shape}")
print(f"Classes: {target_names}")
 
# Split the data
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)
 
# Scale features (critical for KNN!)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
 
# Train KNN classifier
knn = KNeighborsClassifier(
    n_neighbors=5,
    weights='uniform',  # or 'distance' for weighted voting
    metric='euclidean'
)
knn.fit(X_train_scaled, y_train)
 
# Make predictions
y_pred = knn.predict(X_test_scaled)
 
# Evaluate
print("\nClassification Report:")
print(classification_report(y_test, y_pred, target_names=target_names))
 
# Confusion matrix
plt.figure(figsize=(8, 6))
cm = confusion_matrix(y_test, y_pred)
sns.heatmap(cm, annot=True, fmt='d', cmap='Blues',
            xticklabels=target_names, yticklabels=target_names)
plt.xlabel('Predicted')
plt.ylabel('Actual')
plt.title('KNN Confusion Matrix')
plt.tight_layout()
plt.show()
 
# Predict probabilities for a new sample
sample = X_test_scaled[0].reshape(1, -1)
probabilities = knn.predict_proba(sample)
print(f"\nPrediction probabilities: {dict(zip(target_names, probabilities[0]))}")

KNN for Classification vs Regression

KNN works for both tasks with a simple modification:

Classification (Majority Vote)

from sklearn.neighbors import KNeighborsClassifier
 
clf = KNeighborsClassifier(n_neighbors=5)
clf.fit(X_train, y_train)
prediction = clf.predict(X_test)  # Returns class labels

Regression (Average Value)

from sklearn.neighbors import KNeighborsRegressor
 
reg = KNeighborsRegressor(n_neighbors=5)
reg.fit(X_train, y_train)
prediction = reg.predict(X_test)  # Returns continuous values

For regression, instead of voting, we average the target values of the K neighbors:

# Weighted regression (closer neighbors have more influence)
reg_weighted = KNeighborsRegressor(
    n_neighbors=5,
    weights='distance'  # Weight by inverse of distance
)

Feature Scaling: Why It's Essential

KNN is distance-based. Features with larger ranges will dominate the distance calculation, making other features irrelevant.

The Problem

# Without scaling
point_a = np.array([170, 70000])  # height (cm), salary ($)
point_b = np.array([175, 71000])
point_c = np.array([172, 30000])
 
# Salary dominates the distance calculation
print(f"Distance A-B: {euclidean_distance(point_a, point_b):.0f}")  # ~1000
print(f"Distance A-C: {euclidean_distance(point_a, point_c):.0f}")  # ~40000

The Solution

Always scale your features:

from sklearn.preprocessing import StandardScaler, MinMaxScaler
 
# StandardScaler: zero mean, unit variance
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
 
# MinMaxScaler: scale to [0, 1] range
minmax = MinMaxScaler()
X_normalized = minmax.fit_transform(X)

Remember: Fit the scaler on training data only, then transform both training and test sets.

Pros and Cons of KNN

Advantages

  • Simplicity: Easy to understand and implement
  • No training phase: Just store the data (lazy learning)
  • Naturally handles multi-class: No modification needed
  • Non-parametric: Makes no assumptions about data distribution
  • Adaptable: Decision boundaries can be complex and non-linear

Disadvantages

  • Slow predictions: Must compute distances to all training points
  • Memory intensive: Stores the entire training dataset
  • Sensitive to irrelevant features: Every feature affects distance
  • Curse of dimensionality: Struggles with high-dimensional data
  • Sensitive to imbalanced data: Majority class dominates predictions

When to Use KNN

KNN is a great choice when:

  1. Your dataset is small to medium-sized: Under 100,000 samples
  2. Features are meaningful distances: Geographic data, image pixels, embeddings
  3. You need a baseline model: Quick to implement and interpret
  4. Non-linear decision boundaries: KNN naturally handles complex shapes
  5. You need interpretability: "This patient is similar to these 5 recovered patients"

Avoid KNN when:

  • You have millions of data points (prediction becomes slow)
  • You have hundreds of features (curse of dimensionality)
  • Your features have different meanings (distances become meaningless)
  • Real-time prediction is required (consider approximate neighbors)

Conclusion

K-Nearest Neighbors embodies the elegance of simplicity in machine learning. Its "tell me who your neighbors are, and I'll tell you who you are" approach is intuitive, requires no training, and often provides surprisingly competitive results.

The key takeaways:

  • Scale your features before applying KNN
  • Choose K wisely using cross-validation
  • Be mindful of dimensionality—reduce features when necessary
  • Consider weighted voting for better predictions

While KNN may not win Kaggle competitions, it remains invaluable for quick baselines, interpretable predictions, and educational purposes. Every data scientist should have it in their toolkit.

Start with KNN, understand why it works (or doesn't), and you'll build intuition that transfers to more complex algorithms.

Back to Blog