k-means clustering
Also known as: k-means
A method that splits data into a chosen number of groups by moving each group's centre until every point sits with its nearest centre.
Draft - this entry has not been reviewed yet.
Formal
A method for clustering that picks k starting centres, puts each data point with its nearest centre, moves each centre to the average of its points, and repeats until the groups stop changing.
In plain English
Like placing three ice cream stands on a beach; each person walks to the closest stand, each stand then moves to the middle of its crowd, and you repeat until no one changes stand.
In practice
A Danish supermarket chain splits loyalty card customers into five groups by what and when they buy, then names them, for example "weekend family shoppers", and plans offers for each.
Why it matters
It is the simplest and fastest way to find groups in data without answers given in advance, but you must choose the number of groups, and a bad choice gives groups that mean little.
Technical deep dive
k-means minimises the within-cluster sum of squares (inertia), the sum over all points of the squared Euclidean distance to their assigned centroid. The standard procedure, Lloyd's algorithm, alternates an assignment step (each point to its nearest centroid) and an update step (each centroid to the mean of its points). Each step cannot increase inertia, so the algorithm converges, but only to a local minimum; finding the global optimum is NP-hard. Stuart Lloyd described the method in a 1957 Bell Labs report that was published in 1982 (IEEE Transactions on Information Theory); the name k-means comes from MacQueen (1967).
Results depend heavily on initialisation. k-means++ (Arthur and Vassilvitskii, 2007) picks each new starting centre with probability proportional to its squared distance from the centres already chosen, which spreads them out and gives an O(log k) approximation guarantee in expectation; it is scikit-learn's default, and the algorithm is usually run several times keeping the lowest inertia. Mini-batch k-means updates centroids from small random batches to scale to very large datasets.
The number of clusters k must be chosen in advance, commonly with the elbow method on the inertia curve, the silhouette score, or the gap statistic, and ideally checked against domain meaning. Because it uses squared Euclidean distance, k-means implicitly assumes convex, roughly spherical clusters of similar size and is sensitive to feature scale and to outliers, so features are normally standardised first. In high dimensions distances become less informative, and reducing dimensionality first, for example with PCA, often helps.
For clusters of arbitrary shape, density-based methods such as DBSCAN or HDBSCAN are more suitable; Gaussian mixture models are a soft, probabilistic generalisation of k-means; and k-medoids restricts centres to actual data points for robustness. k-means is also used for vector quantisation, for example to build the codebooks in product quantisation for nearest-neighbour search.
What to learn first
Everything this builds on, foundations first.
- Training data
- →Feature
- →Unsupervised learning
- →k-means clustering
Relationships
- Requires
- FeatureUnsupervised learning
- Implements
- Clustering
- Used with
- Dimensionality reduction
Sources & further reading
Official documentation
- scikit-learn User Guide, 2.3 Clustering (K-means) · scikit-learn
Reference works
- Lloyd (1982), Least Squares Quantization in PCM · IEEE Transactions on Information Theory
- Arthur & Vassilvitskii (2007), k-means++: The Advantages of Careful Seeding · ACM-SIAM Symposium on Discrete Algorithms
- k-means clustering · Wikipedia
Where this data comes from
This entry was drafted by an AI from the sources above and has not yet been checked by a person. Treat it as a starting point, and check anything important against the sources.
See the review queueSuggest a correction on GitHubThis term as JSON
Check yourself
Loading…