I want to explain KNN the way I understood it when I first started learning machine learning. K-Nearest Neighbors is a simple but powerful algorithm used for classification and regression, where I predict the label or value of a new data point based on the “k” closest data points to it in the training set. I find this algorithm appealing because it requires no explicit training phase — it just compares new data directly against stored examples, which makes the underlying idea very intuitive: things that are similar to each other tend to belong to the same category.
History and Background
I learned that KNN traces back to work by Evelyn Fix and Joseph Hodges in 1951, who developed the nonparametric method for pattern classification while working for the United States Air Force School of Aviation Medicine. Their work was later expanded by Thomas Cover and Peter Hart in 1967, who formalized the nearest neighbor classification rule and analyzed its error bounds. Since then, KNN has remained a foundational algorithm taught in almost every introductory machine learning course because of its simplicity and intuitive geometric interpretation.
Problem Statement
The problem I need KNN to solve is classifying or predicting a value for a new, unseen data point when I don’t have (or don’t want to build) a complex parametric model. I want an approach that uses the existing labeled data directly, assuming that similar inputs usually produce similar outputs, without assuming any particular mathematical form for the relationship between features and labels.
Core Concepts
- Distance metric – a way of measuring similarity between data points, most commonly Euclidean distance.
- k value – the number of nearest neighbors I consider when making a prediction.
- Majority voting (classification) – the predicted class is whichever class appears most often among the k nearest neighbors.
- Averaging (regression) – the predicted value is the average of the k nearest neighbors’ values.
- Lazy learning – KNN doesn’t build a model in advance; all computation happens at prediction time.
- Feature scaling – normalizing features so no single feature dominates the distance calculation.
How It Works
- I store all labeled training data points without building any model.
- When I need to classify a new data point, I calculate the distance between it and every point in the training set.
- I select the $k$ training points with the smallest distances to the new point.
- For classification, I take a majority vote among the labels of those $k$ neighbors. For regression, I average their values.
- I assign the resulting label or value as the prediction for the new data point.
Working Principle
The internal logic relies on the assumption that data points close to each other in feature space tend to share similar outcomes. Since KNN doesn’t learn any parameters ahead of time, all the “work” happens during prediction, comparing the new point against every stored example. This is why it’s called a “lazy” learning algorithm — it defers computation until it actually needs to make a prediction.
Mathematical Foundation
The most common distance metric I use is Euclidean distance between two points $x$ and $y$ with $n$ features:
$$d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i – y_i)^2}$$
For classification, the predicted class $\hat{y}$ for a new point $x$ is:
$$\hat{y} = \text{mode}{y_i : x_i \in N_k(x)}$$
where $N_k(x)$ is the set of $k$ nearest neighbors to $x$. For regression, the prediction is:
$$\hat{y} = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i$$
Diagrams
flowchart TD
A[New Data Point] --> B[Calculate Distance to All Training Points]
B --> C[Sort Distances Ascending]
C --> D[Select K Nearest Neighbors]
D --> E{Classification or Regression?}
E -->|Classification| F[Majority Vote of Labels]
E -->|Regression| G[Average of Values]
F --> H[Predicted Output]
G --> HPseudocode
function KNN_PREDICT(training_data, new_point, k):
distances = []
for point in training_data:
d = EUCLIDEAN_DISTANCE(point.features, new_point)
distances.append((d, point.label))
SORT(distances by d ascending)
nearest_k = distances[0:k]
if TASK == "classification":
return MAJORITY_VOTE(nearest_k.labels)
else:
return AVERAGE(nearest_k.labels)
Step-by-Step Example
Suppose I have training data of fruit weight (grams) and label (Apple/Orange): (150, Apple), (170, Apple), (140, Apple), (200, Orange), (220, Orange), (180, Orange). I want to classify a new fruit weighing 160 grams, using k=3.
- I compute distances: |150-160|=10, |170-160|=10, |140-160|=20, |200-160|=40, |220-160|=60, |180-160|=20.
- Sorting ascending: 150 (10, Apple), 170 (10, Apple), then a tie between 140 and 180 at distance 20.
- Taking the 3 nearest: 150 (Apple), 170 (Apple), and one of the distance-20 points, say 140 (Apple).
- Majority vote among these 3 neighbors: Apple, Apple, Apple → predicted label is Apple.
Time Complexity
For $n$ training points with $d$ features, computing distances to a new point takes $O(n \cdot d)$, and sorting or partially selecting the $k$ smallest distances takes $O(n \log n)$ or $O(n \log k)$ using a heap, giving overall prediction time of roughly $O(n \cdot d + n \log k)$ per query.
Space Complexity
Space complexity is $O(n \cdot d)$, since I must store the entire training dataset (all $n$ points with $d$ features each) in memory to make predictions, unlike algorithms that discard training data after building a compact model.
Correctness Analysis
I trust KNN’s correctness in the sense that, given enough training data, its predictions converge to the theoretically optimal Bayes classifier as $n \to \infty$ and $k$ grows appropriately (Cover and Hart proved that the nearest-neighbor error rate is bounded by at most twice the Bayes error rate as $n \to \infty$). The algorithm’s core logic — assigning labels based on the closest matching examples — directly reflects the assumption that similar inputs share similar outputs, and its correctness depends heavily on this assumption holding for the given dataset.
Advantages
- Extremely simple to understand and implement, with no training phase required.
- Naturally handles multi-class classification and regression problems.
- Adapts well to complex decision boundaries since it makes no assumptions about the underlying data distribution.
- New training data can be added without retraining a model.
Disadvantages
- Prediction is slow for large datasets since it requires comparing against every training point.
- Sensitive to irrelevant or unscaled features, which can distort distance calculations.
- Requires storing the entire training dataset in memory.
- Performance degrades in high-dimensional spaces due to the “curse of dimensionality,” where distances between points become less meaningful.
Applications
I’ve seen KNN used in recommendation systems, image recognition, medical diagnosis (classifying diseases based on symptom similarity), credit scoring, anomaly detection, and as a baseline algorithm for comparing against more complex machine learning models.
Implementation in C
Here is a simple KNN classifier implementation in C for a 2-feature dataset.
#include <stdio.h>
#include <math.h>
#include <string.h>
#define TRAIN_SIZE 6
#define K 3
typedef struct {
double weight;
char label[10];
} Fruit;
Fruit training_data[TRAIN_SIZE] = {
{150, "Apple"}, {170, "Apple"}, {140, "Apple"},
{200, "Orange"}, {220, "Orange"}, {180, "Orange"}
};
typedef struct {
double distance;
char label[10];
} Neighbor;
double euclidean_distance(double a, double b) {
return fabs(a - b); // 1D feature simplification
}
void knn_predict(double new_point) {
Neighbor neighbors[TRAIN_SIZE];
for (int i = 0; i < TRAIN_SIZE; i++) {
neighbors[i].distance = euclidean_distance(training_data[i].weight, new_point);
strcpy(neighbors[i].label, training_data[i].label);
}
// simple bubble sort by distance
for (int i = 0; i < TRAIN_SIZE - 1; i++) {
for (int j = 0; j < TRAIN_SIZE - i - 1; j++) {
if (neighbors[j].distance > neighbors[j + 1].distance) {
Neighbor temp = neighbors[j];
neighbors[j] = neighbors[j + 1];
neighbors[j + 1] = temp;
}
}
}
int apple_count = 0, orange_count = 0;
for (int i = 0; i < K; i++) {
if (strcmp(neighbors[i].label, "Apple") == 0) apple_count++;
else orange_count++;
}
printf("Prediction for weight %.1f: %s\n", new_point,
apple_count > orange_count ? "Apple" : "Orange");
}
int main() {
knn_predict(160.0);
return 0;
}
Sample Input and Output
Input: Training data of fruit weights labeled Apple/Orange, predicting for a new fruit weighing 160 grams with k=3.
Output:
Prediction for weight 160.0: Apple
Optimization Techniques
I improve KNN performance by using spatial data structures like KD-trees or Ball trees to speed up nearest neighbor search from $O(n)$ to roughly $O(\log n)$ per query in lower dimensions, normalizing/standardizing features before computing distances, reducing dimensionality with techniques like PCA when the feature count is large, and using approximate nearest neighbor methods for very large datasets.
Common Mistakes
I’ve noticed people forget to scale features, letting one large-magnitude feature dominate distance calculations, choose an even value of k in binary classification which can cause ties, pick k too small (overfitting/noisy predictions) or too large (oversmoothing, ignoring local structure), and apply KNN directly to very high-dimensional data without addressing the curse of dimensionality.
Further Reading
- Cover, T. & Hart, P., “Nearest Neighbor Pattern Classification” – https://ieeexplore.ieee.org/document/1053964
- Fix, E. & Hodges, J., “Discriminatory Analysis, Nonparametric Discrimination” – https://apps.dtic.mil/sti/citations/ADA800276
- “An Introduction to Statistical Learning” by James, Witten, Hastie, Tibshirani – https://www.statlearning.com/
- scikit-learn KNN Documentation – https://scikit-learn.org/stable/modules/neighbors.html
