What's the difference between k-means and k-nearest neighbors? People confuse them.

How to think about it

The crisp answer

K-means and KNN solve different problems. K-means is unsupervised: it discovers k groups in data with no target labels. KNN, or k-nearest neighbors, is supervised: it predicts a new point’s label or numeric value from the k closest labeled training examples.

They share a distance calculation and the letter k. That is almost where the similarity ends. In k-means, k means the number of clusters. In KNN, k means the number of neighbors allowed to vote.

Why people confuse them

Both algorithms represent an observation as a feature vector, meaning a list of measurements such as income, age, or number of visits. Both decide that points close together are more similar than points far apart. Usually, “close” means Euclidean distance: the straight-line distance between two points.

The learning setup is different:

• Supervised learning uses examples with a known target, such as churn = yes or price = 425000.
• Unsupervised learning receives only the input features and tries to find structure without a known answer.

That distinction determines the algorithm’s job. K-means cannot learn “churn” because churn labels are not part of its objective. It can discover a group of customers who look alike, but a human still has to inspect that group and decide whether it represents “high-value customers,” “at-risk customers,” or merely “people who happened to share two measurements.”

KNN, by contrast, cannot discover a new category. It can only predict the target categories already present in its labeled examples.

K-means discovers groups

Suppose six customers are represented by two already-standardized features: annual spending and monthly visits. Their coordinates look like this:

Customer	Features	Observed churn
A	(2, 1)	no
B	(3, 1)	no
C	(2, 2)	no
D	(8, 7)	yes
E	(9, 8)	yes
F	(8, 9)	no

For k-means, ignore the churn column. It is not used.

Set k = 2. Start with A and D as the two initial centroids. A centroid is the average position of the points assigned to a cluster.

The first assignment puts A, B, and C near A, and D, E, and F near D. K-means then recomputes the centroids:

• First cluster: ((2 + 3 + 2) / 3, (1 + 1 + 2) / 3) = (2.33, 1.33)
• Second cluster: ((8 + 9 + 8) / 3, (7 + 8 + 9) / 3) = (8.33, 8.00)

It assigns every point again using these new centroids, recomputes the means again, and stops when the assignments no longer change or the improvement becomes negligible.

The algorithm is minimizing the within-cluster sum of squared distances: points should be as close as possible to the centroid of their assigned cluster. This objective explains both its usefulness and its limitations. It prefers compact groups around their averages. It does not know whether those groups are meaningful to the business.

A new customer at (7.5, 7.2) would be assigned to the second cluster because it is closer to (8.33, 8.00) than to (2.33, 1.33). That is a cluster assignment, not a churn prediction. Cluster numbers are arbitrary: “cluster 1” in one run may become “cluster 2” in another.

K-means performs upfront work to learn the centroids. That makes future assignment cheap: compare a new point with only k centroids. The trade-off is that the centroids throw away detail about individual points.

KNN predicts from labeled examples

Now use the same six customers, but this time keep their churn labels. A new customer arrives at Q = (7.5, 7.2). Choose k = 3, meaning three neighbors will vote.

The relevant distances are:

Q to D: sqrt((7.5 - 8)^2 + (7.2 - 7)^2) = 0.54
Q to E: sqrt((7.5 - 9)^2 + (7.2 - 8)^2) = 1.70
Q to F: sqrt((7.5 - 8)^2 + (7.2 - 9)^2) = 1.87

D, E, and F are the three nearest labeled examples. D and E churned; F did not. A majority vote therefore predicts churn = yes.

Notice what KNN did not do. It did not calculate a centroid. It did not move points into groups. It looked up nearby historical cases and copied the dominant observed outcome.

For classification, KNN uses a majority vote. For regression, it averages the neighbors’ numeric target values. A common refinement is distance-weighted voting, where a neighbor at distance 0.54 counts more than one at distance 1.87.

KNN is called a lazy learner because it does little parameter fitting before prediction. A typical implementation stores the training examples and performs the expensive neighbor search when a query arrives. Calling a library’s fit method may still validate and store data, but it does not mean KNN has learned a set of weights like linear regression or a neural network.

The difference at a glance

Question	K-means	KNN
Main job	Discover groups	Predict a known target
Training data	Usually unlabeled	Labeled
Meaning of k	Number of clusters	Number of neighbors
What it learns or stores	k centroids	Training examples
When most computation happens	During fitting	During prediction
Output	Cluster membership	Class or numeric estimate
Typical use	Customer segmentation	Churn or price prediction

The senior-level nuance

The two k values are unrelated

A k-means model with k = 2 is not conceptually related to a KNN model with k = 2. The first says, “partition the whole dataset into two groups.” The second says, “let two nearby examples vote on this one prediction.”

The effect of changing k is also different:

• Increasing k-means k creates more, smaller clusters and can reveal finer structure, but may simply fragment noise.
• Increasing KNN k smooths predictions across a larger neighborhood. Small k can follow noisy individual examples; large k can wash out genuine local patterns.

For KNN, this is a bias-variance trade-off. k = 1 has low bias but can be unstable because one mislabeled point controls the answer. A large k has lower variance but may ignore a small, meaningful class. Cross-validation is usually the sensible way to choose it.

Distance is only useful when the features make it useful

A common production failure has an obvious symptom: k-means clusters line up almost perfectly with annual spending, or KNN predictions barely change when monthly visits change.

Suppose the features are raw values:

• Customer A: (80000, 2)
• Customer B: (81000, 18)
• Customer C: (20000, 2)

The distance from A to B is approximately 1000.13. The difference in visits contributes only 16^2 = 256 to the squared distance, while the spending difference contributes 1000^2 = 1,000,000. Spending dominates.

The usual fix is to standardize numeric features using statistics fitted on the training or reference data, then apply that same transformation at serving time. But blind scaling is not automatically correct. If spending should intentionally matter five times as much as visits, that business weighting should be encoded deliberately rather than erased.

The same warning applies to categorical data. Feeding category codes such as basic = 1, premium = 2, and enterprise = 3 into Euclidean distance falsely implies that the gap from basic to premium has the same meaning as the gap from premium to enterprise.

Their operational costs point in opposite directions

With n records, d features, and i k-means iterations, a rough brute-force k-means fitting cost is O(n k d i). Once fitted, assigning one new point costs about O(kd).

A brute-force KNN query costs about O(nd) because it compares the new point with every stored example before selecting the nearest ones. A million-row dataset with 200 features therefore touches roughly 200 million feature values per query. Approximate-nearest-neighbor indexes can reduce latency, but they add index maintenance and may return approximate rather than exact neighbors.

K-means is often attractive when a compact representation is valuable. KNN is attractive when the dataset is modest and nearby labeled examples genuinely provide a useful answer.

When the textbook answer is wrong

K-means is a poor choice when the groups are elongated, have very different densities, or are dominated by outliers. The mean is pulled toward extreme points, and the algorithm will produce k partitions even when the data contains no natural clusters. It is also awkward for mixed numeric and categorical data.

KNN is a poor choice when the feature space is very high-dimensional, irrelevant features overwhelm the useful ones, or prediction latency and memory are tight. In high dimensions, distances can become less informative because the nearest and farthest points are relatively similar in distance. KNN also inherits errors in the labels; nearby bad examples create bad predictions.

Neither algorithm should be selected because it is easy to explain. First ask whether the distance metric represents similarity in the real problem. If it does not, a more sophisticated implementation merely produces a more confidently wrong answer.

What they’ll ask next

“Can k-means classify new customers?”

Not by itself. K-means can assign a new customer to the nearest learned centroid, but that output is only a cluster ID. You can manually label clusters afterward, but that is a two-stage workaround and the original clustering objective never used the target label. If the goal is churn prediction, a supervised method such as KNN is solving the stated problem directly.

“How would you choose k?”

For k-means, I would combine business usefulness with diagnostics such as the elbow method, silhouette score, and stability across different initializations. The elbow method looks for where additional clusters stop substantially reducing within-cluster distance. A silhouette score compares how close a point is to its own cluster with how close it is to other clusters. None of these proves that a particular k is the truth.

For KNN, I would select k with cross-validation after choosing a sensible distance metric and scaling procedure. I would also check class balance and whether a distance-weighted vote improves validation performance.

“Which one is lazy, and where is the cost?”

KNN is the lazy learner: it stores labeled examples and pays the neighbor-search cost at prediction time. K-means is comparatively eager: it pays an iterative fitting cost to produce centroids, then makes fast centroid-based assignments. KNN usually needs more memory and can have higher query latency; k-means is cheaper to query but loses local detail.

Say this in the interview

K-means discovers k unlabeled clusters by learning centroids, while KNN predicts a labeled target from its k nearest examples; they share distance calculations, but their problems, training behavior, and meanings of k are different.