K-Nearest Neighbors (KNN)

K-Nearest Neighbors is perhaps the most intuitive machine learning algorithm ever conceived. The idea is beautifully simple: to classify a new data point, look at the K closest examples in your training data and let them vote. If most of your nearest neighbors are cats, you are probably a cat too. This "guilt by association" approach requires no training phase at all — the algorithm simply memorizes the training data and makes decisions at prediction time.

The Core Intuition

Imagine you move to a new city and want to know if a neighborhood is safe. One natural approach: look at the 5 nearest houses. If 4 out of 5 have well-maintained gardens and nice cars, you would guess it is a good neighborhood. That is KNN in action — classification by proximity.

More formally, KNN is an instance-based (or lazy) learning algorithm. Unlike logistic regression or decision trees that build an explicit model during training, KNN stores all training examples and defers computation until prediction time. When a new point arrives, it computes distances to all stored examples, finds the K nearest ones, and takes a majority vote.

How KNN Works Step by Step

The algorithm is straightforward:

1. Store all training data points with their labels
2. Receive a new, unlabeled data point to classify
3. Calculate the distance from this point to every training example
4. Select the K nearest training examples (neighbors)
5. Vote — assign the majority class among those K neighbors

Distance Metrics: How to Measure Closeness

The choice of distance metric fundamentally affects which points are considered "neighbors." The most common options are:

Euclidean Distance (L2)

The straight-line distance between two points — what you would measure with a ruler:

This is the default in most implementations and works well when features have similar scales and are continuous.

Manhattan Distance (L1)

The sum of absolute differences — like walking along city blocks:

Manhattan distance is less sensitive to outliers in individual features and works better in high-dimensional spaces.

Minkowski Distance

A generalization that includes both Euclidean (p=2) and Manhattan (p=1):

Choosing the Right K

The value of K is the single most important hyperparameter in KNN, and it controls the bias-variance tradeoff:

• K=1: The model predicts based on the single nearest neighbor. This is highly sensitive to noise — one mislabeled training point creates an error. Low bias, high variance.
• K=large (e.g., K=50): The model considers many neighbors, smoothing out noise but potentially ignoring local patterns. High bias, low variance.
• K=n (all data): Always predicts the majority class — useless.

The sweet spot is typically between 3 and 20, found through cross-validation. A common heuristic is K = sqrt(n) where n is the number of training samples. Always use odd K for binary classification to avoid ties.

Complete Implementation with Scikit-Learn

Why Feature Scaling Is Non-Negotiable

Here is a critical insight that trips up beginners: KNN uses distance calculations, so features on larger scales completely dominate the distance computation. If one feature ranges from 0 to 1000 (like income) and another from 0 to 1 (like a probability), the income feature effectively determines all distances while the probability feature is ignored.

Always standardize or normalize your features before applying KNN. StandardScaler (zero mean, unit variance) is the most common choice:

Weighted KNN: Not All Neighbors Are Equal

Standard KNN gives equal weight to all K neighbors. But should a neighbor at distance 0.1 count the same as one at distance 5.0? Weighted KNN assigns higher importance to closer neighbors:

This often improves performance, especially when the choice of K is not optimal. Even with K=20, if the 3 nearest neighbors are all class A and the remaining 17 are class B at greater distances, weighted voting can still correctly predict class A.

The Curse of Dimensionality

KNN suffers more than most algorithms from high-dimensional data. Here is why: as dimensions increase, all points become approximately equidistant from each other. In 1000 dimensions, the concept of "nearest neighbor" loses meaning because the nearest and farthest points are nearly the same distance away.

Practical solutions include:

• Dimensionality reduction with PCA before applying KNN
• Feature selection to keep only the most relevant features
• Use Manhattan distance which degrades more gracefully in high dimensions

Computational Complexity Concerns

KNN's biggest practical limitation is prediction speed. For each new point, it must calculate distances to ALL training examples. With n training points and d features, each prediction costs O(n × d). For large datasets, this becomes prohibitively slow.

Solutions include KD-trees and Ball-trees (spatial data structures that speed up neighbor search), approximate nearest neighbor algorithms, and simply reducing the training set through sampling or prototype selection.

When to Use KNN

KNN excels when you have relatively small datasets (under 100,000 samples), non-linear decision boundaries, few features (under 20 after preprocessing), and when you need a simple baseline. It struggles with high-dimensional data, large datasets, imbalanced classes, and irrelevant features that add noise to distance calculations.

Key Takeaways

KNN classifies by proximity — simple, intuitive, and surprisingly effective. Always scale your features, use cross-validation to find the best K, prefer weighted voting over uniform voting, and be aware of the curse of dimensionality. KNN is a perfect starting algorithm for learning ML because its behavior is transparent and predictable, making it easy to debug and understand. While not always the most accurate choice, it provides an excellent baseline and teaches fundamental concepts about instance-based reasoning that apply throughout machine learning.