K-NN vs K-means:

Aspect	K-NN (K-Nearest Neighbors)	K-means (Clustering)
Type	Supervised, instance-based, lazy classifier/regressor	Unsupervised clustering
Purpose	Predict label $y$ for query using labeled neighbors	Group unlabeled data into $k$ clusters minimizing SSE
Input	Labeled training $(x_i,y_i)$	Unlabeled $x_i$ only, need $k$ preset
Working	For query $x_q$, find $k$ nearest labeled points by distance, majority vote / average: $\hat y = \arg\max_c \sum \mathbb{I}(y_i=c)$	Iteratively assign points to nearest centroid $\mu_j$, recompute $\mu_j=$ mean, repeat until convergence
Training	No model building, stores data	Builds model (centroids)
Prediction cost	$O(n d)$ per query (slow)	$O(k d)$ after training (fast assign)
Output	Single label per query	Cluster id for all points
Choosing $k$	$k$ = neighborhood size via CV (bias-variance)	$k$ = number clusters via elbow/silhouette
Example	Classify email as spam using 5 nearest labeled emails	Segment customers into 3 groups without labels

Common confusion: Both use distance and $k$, but meanings completely different: $k$ in K-NN = neighbors to vote, $k$ in K-means = clusters. K-NN needs labels, K-means does not. K-NN predicts new point, K-means discovers structure.

When to use: Labels available + need classification → K-NN. No labels + need grouping → K-means.