K-Means Clustering
How does K-Means work?
Pick k centroids, then loop two steps until nothing changes: assign each point to its nearest centroid, then move each centroid to the mean of its assigned points. It minimizes within-cluster squared distance (inertia).
- “Does it always converge?” — Yes, to a local optimum — not necessarily the global one, hence multiple restarts.
- “What's inertia?” — The total squared distance from points to their assigned centroid; K-Means minimizes it.
- “K-Means vs KNN?” — Unrelated: K-Means is unsupervised clustering; KNN is supervised classification.
How do you choose k?
k is an input you must set. The elbow method plots inertia against k and looks for the bend where adding clusters stops helping much. The silhouette score is a more principled alternative.
Inertia always falls as k rises, so you can't just minimize it. The “elbow” — where the curve bends and gains flatten — is the sweet-spot k.
What are its limitations?
K-Means assumes round, similarly-sized clusters and is sensitive to where the centroids start. Knowing these failure modes — and their fixes — is the real interview content.
Fails on elongated or differently-sized clusters. For arbitrary shapes use DBSCAN; for elliptical clusters, Gaussian mixtures.
Bad starts give bad local optima. k-means++ spreads initial centroids; run several times and keep the best.
Distance-based, so scale features first; means are dragged by outliers.
- “K-Means vs GMM?” — GMM does soft assignments with covariance, so it handles elliptical clusters and overlap.
How do you scale K-Means to large datasets?
Standard K-Means recomputes assignments over the whole dataset each iteration. Mini-batch K-Means updates centroids using small random batches, trading a little quality for a big speed-up on millions of points.
- “Complexity?” — Roughly O(n·k·d) per iteration, so cost grows with points, clusters, and dimensions.
Can K-Means handle non-numeric or mixed data?
Not directly — it relies on a mean and Euclidean distance, which don't make sense for categories. Use k-modes for categorical data or k-prototypes for mixed, or encode features carefully first.
- “Why not one-hot then K-Means?” — It can work but inflates dimensionality and distorts distances; purpose-built methods are usually better.