What are the key differences between KNN and K-means?
Answer
KNN (K-Nearest Neighbors) is a supervised algorithm that classifies data using the labels of its nearest neighbors: prediction from historical labeled data. K-means is an unsupervised clustering technique that groups data purely by similarity, using no labels at all. Despite the shared “K”, they solve different problems.
(1) Learning Type: KNN is supervised (classification/regression); K-means is unsupervised (clustering).
(2) Objective: KNN predicts a new sample’s label from the majority vote (or average) of its K nearest neighbors; K-means partitions the dataset into K clusters by minimizing intra-cluster distance.
(3) Training: KNN has no explicit training: it stores the entire dataset; K-means iteratively learns cluster centroids.
(4) Prediction Cost: KNN is expensive at prediction (distance to every training point, sort, take the top K, then vote/average); K-means is cheap: distances to K centroids, assign the nearest.
(5) Distance Use And Output: KNN uses distance to find neighbors and outputs a label or value; K-means uses distance to assign points to centroids and outputs cluster assignments plus centroids.
| Feature | K-Nearest Neighbors (KNN) | K-Means |
|---|---|---|
| Type | Supervised Learning | Unsupervised Learning |
| Task | Classification, Regression | Clustering |
| Data Required | Labeled data | Unlabeled data |
| Training Phase | Stores all training data (lazy learner) | Iterative centroid calculation |
| Prediction Phase | Finds K nearest neighbors and assigns label/value | Assigns new points to closest cluster centroid |
| Compute Cost | High at prediction (distance calculations for each new point) | High at training (iterative updates); low at prediction (centroid assignment) |
| Goal | Predict label/value for new data | Group data into K clusters |
| Output | Class label or predicted value | Data points assigned to clusters |
Mathematical Formulation:
Where:
- KNN (first line):
is the predicted class, 
the class set, 
the label of the 
-th nearest neighbor, and 
the vote-counting indicator. - K-means (second line):
is cluster and 
its centroid; the algorithm minimizes total within-cluster squared distance: no labels appear anywhere.
is the predicted class, 
the class set, 
the label of the 
-th nearest neighbor, and 
the vote-counting indicator.
is cluster 
and 
its centroid; the algorithm minimizes total within-cluster squared distance: no labels appear anywhere.
Figure 1: Same data, different goals: with labels, KNN’s local votes trace the two crescents perfectly (left); without labels, K-means can only split by nearest-centroid geometry and slices through both moons (right). KNN performs well here thanks to local decision-making; K-means fails because it assumes spherical clusters with linear boundaries.
Leave a Reply