K-means clustering
K-means splits unlabelled data into k groups by putting each point with its nearest centre, then moving each centre to the average of its group, over and over.
K-means is a clustering method: it sorts examples that carry no labels into k groups, and you choose k in advance. Each group has a centroid, the mean of its members, which usually is not one of the data points. The method tries to make inertia as small as possible. Inertia adds up the squared distance from every point to its nearest centroid, so a low value means tight groups. Finding the best possible grouping exactly is NP-hard, even with two clusters. The usual method, often called Lloyd’s algorithm, is a fast local search instead. Clustering of this kind is used for market segmentation, finding subgroups of people who might respond to the same advert. K-means can also pick 8 grey levels to redraw a photo that used 256, and group embeddings, which place similar items close together.
The loop is short: assign every point to its closest centroid, move each centroid to its group’s mean, and repeat until the centroids stop moving. Neither step can raise inertia, so the loop always settles, but possibly on a poor local minimum that depends on where it started. For this reason the algorithm is often run several times from different starts. k-means++, published in 2007, chooses each new starting centre with a probability that grows with its squared distance from the nearest centre already chosen. That tends to spread the starting centres apart. Its authors reported gains in both speed and accuracy, often by a wide margin. scikit-learn starts KMeans with a greedy k-means++ by default; with random starts it runs 10 times and keeps the lowest inertia.
You must choose k yourself. One heuristic runs k-means for increasing k and plots the total distance of points from their centroids. That total keeps falling, so look for the elbow, where the slope first changes sharply. Silhouette scores are another guide: each point gets a value from -1 to +1. Values near +1 mean the point is far from the neighbouring cluster, and negative values suggest it may be in the wrong one. K-means works best on compact, round groups and copes badly with long or irregular shapes. Outliers can drag a centroid or end up in a cluster of their own. Because it measures distance, put features on the same scale first; otherwise the units chosen for one feature can greatly change the result.
Finding groups in unlabelled data is hard to do by eye or by brute force.
Follow six points through one round of k-means.
- 1 · startChoose k, the number of groups, and pick k starting centres, most simply k points taken from the data.
- 2 · assignPut every point in the group of its nearest centre.
- 3 · updateMove each centre to the mean of the points now in its group.
- 4 · repeatRepeat assign and update until the centres stop moving.
Neither step can raise inertia, the sum of squared distances from points to their centres, so the loop settles.
| Who | What they ask | What it works with |
|---|---|---|
| Marketing team | “Which groups of customers might respond to the same advert?” | Measurements about each person, such as income, occupation and distance from a city |
| Image tool | “Can this photo use 8 grey levels instead of 256?” | The brightness value of every pixel |
| Recommendation team | “Which of these videos cover similar topics?” | Embedding vectors, where similar items end up close together |
- It groups unlabelled data into a set number of clusters with a simple two-step loop.
- It scales to large datasets, since its cost grows with the number of points times k.
- It always converges, because each step can only keep inertia the same or lower it.
- Each cluster gets a readable summary, its centroid, the mean of its members.
- It does not pick k for you. The elbow plot and silhouette scores only guide the choice.
- It can settle on a poor local optimum, so the answer depends on the starting centres.
- It assumes compact, round groups and struggles with stretched, uneven or differently dense clusters.
- Outliers can drag a centre away, and a feature measured on a bigger scale can swamp the others unless you rescale first.
Sources used
This explainer is written in original language. The links below support its factual claims.
- docs2.3. Clustering (User Guide), scikit-learn · read 27 Sept 2026
- docsKMeans (API reference), scikit-learn · read 27 Sept 2026
- docsSelecting the number of clusters with silhouette analysis on KMeans clustering, scikit-learn · read 27 Sept 2026
- docsVector Quantization Example, scikit-learn · read 27 Sept 2026
- docsWhat is k-means clustering? (Clustering course), Google for Developers · read 27 Sept 2026
- docsEvaluating results (Clustering course), Google for Developers · read 27 Sept 2026
- docsAdvantages and disadvantages of k-means (Clustering course), Google for Developers · read 27 Sept 2026
- docsData preparation (Clustering course), Google for Developers · read 27 Sept 2026
- docsSupervised similarity measure (Clustering course), Google for Developers · read 27 Sept 2026
- paperk-means++: The Advantages of Careful Seeding, Arthur and Vassilvitskii, SODA 2007 · read 27 Sept 2026
- paperAn Introduction to Statistical Learning, seventh printing (section 10.3.1, K-means clustering), James, Witten, Hastie and Tibshirani (Springer) · read 27 Sept 2026