k-means clustering
K-means partitions a dataset into K groups by repeatedly assigning each point to its nearest center and then moving each center to the average of the points assigned to it, with no labels involved at all — one of the clearest demonstrations is color quantization, where a 24-bit photograph with up to 16.7 million possible colors gets reduced to a palette of just 16 or 256 representative colors by treating each pixel as a point and each palette entry as a cluster center, which is literally how early GIF images compressed photographs onto limited color palettes. Stuart Lloyd described the core algorithm in a 1957 Bell Labs technical report that wasn't formally published until 1982, and James MacQueen coined the name "k-means" in his own 1967 paper — both independently arrived at the same simple two-step loop.
Where those K starting centroids begin decides which of several different answers k-means lands on, and a bad start can trap it in a visibly worse one. Because each iteration only ever moves centroids toward a local average, k-means can converge to a clustering that looks clearly wrong to a human eye simply because the random starting points happened to land badly — two starting centroids placed too close together, for instance, can end up splitting one real cluster in half while merging two separate ones together. Arthur and Vassilvitskii's 2007 k-means++ initialization fixed much of this by choosing starting centroids that are deliberately spread far apart from each other rather than placed uniformly at random, and it's now the default initialization in scikit-learn and most other k-means implementations specifically because it so reliably avoids the worst-case outcomes below.
K-means never tells you what K should be, and picking it wrong silently produces a confident, wrong answer. The elbow method plots the within-cluster variance against different values of K and looks for the point where adding another cluster stops reducing the error much — a visible "elbow" in the curve; the silhouette score, an alternative that scores how well-separated each clustering actually is on a scale that doesn't require eyeballing a bend in a line, is often preferred because it gives a single comparable number rather than a judgment call about where a curve bends. Neither method replaces domain knowledge entirely — if there's an independent reason to expect exactly 4 customer segments or exactly 10 defect types, that prior knowledge is often more reliable than either diagnostic.
K-means assumes clusters are roughly round and roughly the same size, and it will cheerfully produce a wrong answer when that assumption fails. Because the algorithm only ever measures distance to a single centroid per cluster, it struggles with elongated, crescent-shaped, or wildly different-sized groups — a large diffuse cluster sitting next to a small tight one will often get sliced apart to roughly equalize their sizes rather than respecting their true shapes, a known failure mode that algorithms like DBSCAN (density-based clustering) handle differently by not assuming any particular cluster shape at all. This is also why k-means is commonly run after dimensionality reduction on high-dimensional data such as text or image embeddings, for the same curse-of-dimensionality reason covered under k-nearest-neighbors — distances between points stop being meaningful in very high dimensions, and k-means, like KNN, depends entirely on distance to do its job.
The color-quantization example is worth holding onto because it strips away every bit of mystery from what k-means is actually optimizing: given a fixed budget of K representative points, place them so that every data point ends up as close as possible to the representative it's assigned — whether those data points are pixel colors, customer purchase histories, or sensor readings, the algorithm is doing exactly the same arithmetic either way, which is both its power and the source of every limitation above.