Skip to content
Last Dictionary
Plane
Machine LearningMathematics & Statistics

k-means clustering

nounAlso: k-means, Lloyd's algorithm, Lloyd–Forgy algorithm, k-means++

In plain wordsA simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.

  1. A clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size. method that divides a dataset into a preset number k of groups by minimizing the within-cluster sum of squared Euclidean distancesEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length. between each point and its cluster's mean (centroid). The standard heuristic, Lloyd's algorithm, alternates two steps until assignments stop changing: assign every point to its nearest centroid, then recompute each centroid as the mean of its points. Neither step can increase the objective, so the procedure converges, but only to a local optimum that depends on the starting centers; finding the global optimum is NP-hard. The k-means++ seeding rule, which picks initial centers far apart with probability proportional to squared distance, gives an expected O(log k) approximation guarantee. K-means assumes compact, roughly spherical clusters of similar size, is sensitive to outliers and to feature scalefeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units., and can be seen as a limiting case of fitting a Gaussian mixture modelGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it. with the expectation–maximization algorithmexpectation–maximization algorithm, n.: A method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes..

    We ran k-means with k = 8 on the customer embeddings and named the clusters after reading samples from each.

min⁡C1,…,Ck∑j=1k∑x∈Cj∥x−μj∥2\min_{C_1,\dots,C_k} \sum_{j=1}^{k} \sum_{\mathbf{x} \in C_j} \lVert \mathbf{x} - \boldsymbol{\mu}_j \rVert^2

Origin

Hugo Steinhaus described the partitioning idea in 1956. At Bell Labs in 1957 Stuart Lloyd proposed the alternating algorithm for designing pulse-code-modulation quantizers, in an internal report not formally published until 1982; Edward Forgy described the same procedure in 1965, hence the name Lloyd–Forgy. The name 'k-means' comes from James MacQueen (1967). David Arthur and Sergei Vassilvitskii added k-means++ seeding in 2007.

Usage note

Choosing k is a model selectionmodel selection, n.: Choosing, from several candidate models or settings, the one most likely to work best on new data, rather than the one that merely fits the existing data best. problem; common aids are the elbow plot of the objective against k and the silhouette scoresilhouette score, n.: A number between −1 and 1 that grades a grouping of data by checking, for each point, whether it sits closer to its own group than to the next-nearest group.. Variants include k-medoids (centers must be actual data points) and mini-batch k-means for very large datasets. Not to be confused with k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average., a supervised method.

Related

See also
  • clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size.
  • Gaussian mixture modelGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it.
  • expectation–maximization algorithmexpectation–maximization algorithm, n.: A method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes.
  • silhouette scoresilhouette score, n.: A number between −1 and 1 that grades a grouping of data by checking, for each point, whether it sits closer to its own group than to the next-nearest group.
  • feature scalingfeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units.
  • hierarchical clusteringhierarchical clustering, n.: A way of grouping data that builds a family tree of clusters, joining the most similar items step by step, so you can cut the tree at whatever level of detail you need.
  • DBSCANDBSCAN, n.: A clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise.
Contrast with
  • k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average.

Sources

  1. MacQueen, J. (1967). Some Methods for Classification and Analysis of Multivariate Observations. Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability.
  2. Lloyd, S. P. (1982). Least Squares Quantization in PCM. IEEE Transactions on Information Theory 28(2).
  3. Arthur, D. & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA).

Mentioned in

clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size., DBSCANDBSCAN, n.: A clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise., Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length., expectation–maximization algorithmexpectation–maximization algorithm, n.: A method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes., FAISSFAISS, prop. n.: A free software library from Meta for searching huge collections of embeddings very fast, on ordinary processors or graphics cards. Many AI search systems use it under the hood., feature scalingfeature scaling, n.: Putting input measurements on comparable scales, so that income in dollars and age in years, say, both span similar ranges and no feature dominates just because of its units., Gaussian mixture modelGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it., hierarchical clusteringhierarchical clustering, n.: A way of grouping data that builds a family tree of clusters, joining the most similar items step by step, so you can cut the tree at whatever level of detail you need., k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average., scikit-learnscikit-learn, prop. n.: A free, widely taught Python library of classic machine-learning methods — such as decision trees, regression and clustering — that all work in the same simple way., silhouette scoresilhouette score, n.: A number between −1 and 1 that grades a grouping of data by checking, for each point, whether it sits closer to its own group than to the next-nearest group., unsupervised learningunsupervised learning, n.: Machine learning without answer keys: the computer looks at unlabeled data and finds structure on its own, such as groups of similar customers or the main ways in which data vary., product quantizationproduct quantization, n.: A compression trick for embeddings: chop each long list of numbers into short pieces and replace each piece with the ID of its closest typical piece, shrinking storage many times over while keeping search workable., radial basis function networkradial basis function network, n.: A three-layer network whose hidden neurons each respond to inputs near a particular reference point, like bells placed across the data; the output is a weighted mix of the bells., self-organizing mapself-organizing map, n.: A neural network that arranges data on a flat grid so that similar items end up in neighboring cells, producing a map of how the data is organized., spectral clusteringspectral clustering, n.: A clustering method that treats data points as a network linked by similarity and finds natural groups by cutting the network where its links are weakest., vector quantizationvector quantization, n.: Compressing data by replacing each item with the nearest entry from a small catalog of representative examples, so that only the catalog number needs to be stored or sent.