Dictionary of Applied Machine Learning: 107 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here

clustering

Updated on 2026-10-22

Readiness 100/100

▶ Run the Python demo Open in Colab Typeset PDF LaTeX source Cite this entry

See also $k$-means Gaussian mixture model expectation–maximization hyperparameter unsupervised learning

Clustering decomposes a dataset into subsets, called clusters, such that data points within the same cluster are more similar to each other than to data points in other clusters. Clustering methods differ in the measure of similarity between data points, in the representation of a cluster, and in whether each data point is assigned to exactly one cluster (hard clustering) or to several with varying degrees of belonging (soft clustering). $k$-means represents a cluster by a cluster centroid and a Gaussian mixture model (GMM) by a multivariate normal distribution, so their clusters are convex regions and ellipsoids. Graph clustering represents the data points as the nodes of a similarity graph and uses its weighted edges to determine the clusters.

Figure produced by the Python demo of the entry clustering
Figure written by the entry's Python demo clustering.py, which recomputes what the entry states: the script block by block · open in Colab

Definition

B-patchesA photograph taken in the Wachau shows sky, clouds, forested slopes, sunlit vineyards and rock (Fig. 1(a)). Cutting it into $96 \times 128$ patches of $5 \times 5$ pixels gives $12288$ data points, each characterized by a feature vector $\featurevec \in \reals^{3}$ that holds the mean red, green and blue values of the patch. Clustering is the task of decomposing such a dataset into clusters, such that data points within the same cluster are more similar to each other than to data points in other clusters (Bishop, 2006, Sect. 9.1; Hastie et al., 2009, Sect. 14.3). Fig. 1(b)–(f) shows the segmentations delivered by five clustering methods, $k$-means, a Gaussian mixture model (GMM), density-based spatial clustering of applications with noise (DBSCAN), spectral clustering and convex clustering. The number $\nrcluster$ of clusters is either an input, as in $k$-means, or determined by the method from its other hyperparameters, as in DBSCAN.

Figure 1 of the entry clustering
Figure 1: Image segmentation by clustering. (a) A photograph taken in the Wachau, cut into $96 \times 128$ patches of $5 \times 5$ pixels; the feature vector of a patch holds its mean red, green and blue values. (b)–(f) Each patch painted in the mean color of its cluster, with white lines between clusters: (b) $k$-means and (c) a GMM, both with $\nrcluster = 5$; (d) DBSCAN with $\varepsilon = 0.03$ and $m^{*} = 32$, noise patches in black; (e) spectral clustering with $\nrcluster = 5$ and (f) convex clustering with $\regparam \approx 18$, both using, for each patch, the ten patches of most similar color as its neighbors. Data generated by pythondemos/clustering.py
Clustering methods differ in three design choices (Jain et al., 1999):
  1. the measure of similarity between data points (Hastie et al., 2009, Sect. 14.3), e.g., the Euclidean distance between their feature vectors, which makes the feature space a metric space, or the edge weights of a graph whose nodes are the data points;
  2. the representation of a cluster, e.g., a cluster centroid, a multivariate normal distribution, a set of data points connected by short hops, or a well-connected subset of the nodes of a graph; and
  3. whether each data point is assigned to exactly one cluster (hard clustering) or to several with varying degrees of belonging (soft clustering).
Fig. 2 illustrates three families of clustering methods: hard clustering, such as $k$-means; soft clustering, such as a GMM; and graph clustering, where the data points are the nodes of a graph and a cluster is a densely connected subset of nodes.
Figure 2 of the entry clustering
Figure 2: Three families of clustering methods, sketched for data points with feature vectors in $\reals^{2}$. (a) Hard clustering as in $k$-means: each data point belongs to exactly one cluster, the one with the nearest cluster centroid (crosses). (b) Soft clustering as in a GMM: two overlapping ellipses (dashed and dotted), crosses at their means and thin double arrows along their principal directions; a data point in the overlap belongs to both clusters with a degree of belonging between $0$ and $1$. (c) Graph clustering: the data points are the nodes of a graph whose edges connect similar data points, and a cluster is a densely connected subset of nodes with few edges (dashed) to the rest
$k$-means represents a cluster by a point of the feature space, referred to as cluster centroid. Each data point is assigned to the cluster whose cluster centroid is nearest in Euclidean distance. The cluster centroids are chosen to minimize the average squared Euclidean distance between a data point and its nearest cluster centroid, which Lloyd's algorithm does by alternating assignment and averaging (Lloyd, 1982). For a large dataset, $k$-means is run on a coreset: a small weighted subset of the data points whose weighted average squared Euclidean distance to the nearest cluster centroid approximates that of the full dataset for every choice of the cluster centroids (Har-Peled and Mazumdar, 2004).

On the photograph, the five cluster centroids of $k$-means with $\nrcluster = 5$ are five representative colors, and each cluster consists of the patches whose color is nearest to one of them: sky, cloud, shaded forest, sunlit slopes and rock (Fig. 1(b)). Painting each patch in the color of its cluster centroid also compresses the photograph to five colors. A clustering learned from one photograph is judged by how it assigns new patches: in $k$-means, a new data point joins the cluster of the nearest cluster centroid, so the cluster centroids are the learned hypothesis.

B-gmmA GMM represents each cluster by a multivariate normal distribution: a cluster index is drawn first, then the feature vector from that cluster's multivariate normal distribution. The degree of belonging of a data point to a cluster is the posterior distribution of its cluster index, and the expectation–maximization (EM) algorithm learns the model parameters by maximum likelihood (Bishop, 2006, Sect. 9.2). The result is a soft clustering whose clusters are ellipsoids; hard clustering is the extreme case in which every degree of belonging is $0$ or $1$. On the photograph, each surface type becomes a multivariate normal distribution over colors, and the degree of belonging of a patch to the sky cluster is the probability that its color was drawn from the multivariate normal distribution of the sky. Painting each patch by the cluster with the largest degree of belonging gives Fig. 1(c); one in eight patches, mostly along the horizon and the cloud edges, has no degree of belonging above $0.8$.

B-dbscanDBSCAN defines a cluster through two hyperparameters, a distance $\varepsilon$ and a minimum size $m^{*}$ of a cluster (Ester et al., 1996). A data point is a core point if at least $m^{*}$ data points lie within Euclidean distance $\varepsilon$ of it. A cluster is a maximal set of data points that are connected through a chain of core points at most $\varepsilon$ apart, and data points that are neither core points nor within $\varepsilon$ of one are noise. A cluster can therefore have any shape that a chain of nearby data points can trace, and the number of clusters is an output, not an input. On the photograph, $\varepsilon$ is a distance between colors. With $\varepsilon = 0.03$ and $m^{*} = 32$, the blue of the sky and the white of the clouds are joined by a chain of intermediate colors, so sky and cloud form one cluster and the land another. The patches along the horizon, whose mixed colors are rare, are noise (Fig. 1(d)).

Graph clustering methods represent the dataset as the nodes $\sampleidx = 1, \ldots, \samplesize$ of a graph whose edge weights express the similarity between data points, e.g., the $k$-nearest-neighbor graph ($k$-NN graph) that connects each data point to its nearest neighbors (Luxburg, 2007, Sect. 2). The clusters are determined by the connectivity of the nodes: a cluster is a subset of nodes whose total edge weight to the rest of the graph, divided by the number of nodes in the subset, is small. The sum of this ratio over the clusters is the ratio cut that spectral clustering minimizes approximately (Luxburg, 2007, Sect. 5).

B-convexSpectral clustering computes the clusters from eigenvectors of the Laplacian matrix of the graph (Luxburg, 2007; Ng et al., 2001) and flow-based clustering from network flows between selected nodes (SarcheshmehPour et al., 2021). There are also graph clustering methods that incorporate node-wise feature vectors $\featurevec^{(\sampleidx)}$, $\sampleidx = 1, \ldots, \samplesize$: convex clustering combines the connectivity of the nodes with the node-wise feature vectors. Graph clustering methods are appealing for data points without an obvious choice for numeric feature vectors: scientific papers connected by citations, users of a social network connected by friendships, or web pages connected by links. On the photograph in Fig. 1(a), the nodes are the patches and each patch is connected to the ten patches of most similar color; spectral clustering then separates the five surface types (Fig. 1(e)), since the patches of one surface type are neighbors in color. Fig. 3 arranges the methods by the representation of the data points and of a cluster.

Figure 3 of the entry clustering
Figure 3: Clustering methods arranged by the representation of the data points: as Euclidean vectors, or as the nodes of a graph with weighted edges. Methods on the left branch differ in the cluster shapes they can represent: $k$-means delivers isotropic clusters, round regions around a cluster centroid; a GMM delivers ellipsoids and DBSCAN any shape a chain of nearby data points can trace. Methods on the right branch determine the clusters from the connectivity of the nodes: spectral clustering from eigenvectors of the Laplacian matrix, flow-based clustering from network flows between selected nodes. Convex clustering draws on both branches: its data-fidelity term needs the feature vectors of the data points, and its penalty term is weighted by the edge weights of the graph
Convex clustering draws on both branches of Fig. 3. It gives every data point $\featurevec^{(\sampleidx)}$ its own cluster centroid $\clustercentroid{\sampleidx}$, which avoids the non-convexity of the clustering error. The method minimizes the convex objective function \[ \sum_{\sampleidx=1}^{\samplesize} \normgeneric{\featurevec^{(\sampleidx)} - \clustercentroid{\sampleidx}}{2}^{2} + \regparam \sum_{1 \le \sampleidx < \sampleidx' \le \samplesize} \edgeweight_{\sampleidx,\sampleidx'} \normgeneric{\clustercentroid{\sampleidx} - \clustercentroid{\sampleidx'}}{2} \text{.} \] The penalty term fuses cluster centroids with weights $\edgeweight_{\sampleidx,\sampleidx'} \geq 0$ (Hocking et al., 2011; Sun et al., 2021, Eq. (1); Lindsten et al., 2011). The data points that share a cluster centroid at the unique minimizer form a cluster, and their number falls from $\samplesize$ to $1$ as $\regparam$ grows, so the number of clusters is set indirectly through $\regparam$. With the edge weights of a similarity graph as weights, the penalty term fuses only neighboring data points and the clusters follow the graph (Hocking et al., 2011). On the photograph, with the edge weights of the color graph of the patches and $\regparam \approx 18$, the fused cluster centroids leave $65$ clusters, four of them with at least $80$ patches; like DBSCAN, the method fuses sky with cloud along the gradual color transition (Fig. 1(f)).

Beyond image segmentation, clustering is used for customer segmentation (Wedel and Kamakura, 2000), for grouping documents by topic in natural language processing (NLP) (Manning et al., 2008, Sect. 16.1), for community detection in social networks (Fortunato, 2010), and for anomaly detection, where a data point that falls into no cluster or into a tiny one is an outlier (Chandola et al., 2009). As a preprocessing step for supervised learning, clustering reduces a dataset to its cluster centroids as prototypes (Hastie et al., 2009, Sect. 13.2.1), or adds the distances of a data point to the cluster centroids as new features (Coates and Ng, 2012). It can also split the dataset so that a separate hypothesis is learned per cluster, e.g., one linear regression per cluster (Späth, 1979).

Synonyms: segmentation.

See also: cluster, cluster centroid, clustering error, degree of belonging, hard clustering, soft clustering, $k$-means, Gaussian mixture model, expectation–maximization, density-based spatial clustering of applications with noise, spectral clustering, graph clustering, flow-based clustering, convex clustering, coreset, hyperparameter, anomaly detection, image segmentation, similarity graph, Laplacian matrix, $k$-nearest-neighbor graph, unsupervised learning.

References

  1. Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media. doi.org/10.1007/978-0-387-45528-0
  2. Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science+Business Media. doi.org/10.1007/978-0-387-84858-7
  3. Jain et al. (1999). Data clustering: a review. ACM Computing Surveys. doi.org/10.1145/331499.331504
  4. Lloyd (1982). Least squares quantization in PCM. IEEE Trans. Inf. Theory. doi.org/10.1109/TIT.1982.1056489
  5. Har-Peled and Mazumdar (2004). On coresets for $k$-means and $k$-median clustering. Proc. 36th Annual ACM Symp. Theory of Computing (STOC). doi.org/10.1145/1007352.1007400
  6. Ester et al. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining.
  7. Luxburg (2007). A tutorial on spectral clustering. Statist. Comput.. doi.org/10.1007/s11222-007-9033-z
  8. Ng et al. (2001). On Spectral Clustering: Analysis and an Algorithm. Adv. Neural Inf. Process. Syst.. papers.nips.cc/paper_files/paper/2001/hash/801272ee79cfde7fa5960571fee36b9b-Abstract.html
  9. SarcheshmehPour et al. (2021). Flow-Based Clustering and Spectral Clustering: A Comparison. 2021 55th Asilomar Conf. Signals, Syst., Comput.. doi.org/10.1109/IEEECONF53345.2021.9723162
  10. Hocking et al. (2011). Clusterpath: An Algorithm for Clustering using Convex Fusion Penalties. Proc. of the 28th International Conference on Machine Learning,.
  11. Sun et al. (2021). Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm. J. Mach. Learn. Res.. jmlr.org/papers/v22/18-694.html
  12. Lindsten et al. (2011). Clustering using sum-of-norms regularization: With application to particle filter output computation. 2011 IEEE Statistical Signal Processing Workshop (SSP). doi.org/10.1109/SSP.2011.5967659
  13. Wedel and Kamakura (2000). Market Segmentation: Conceptual and Methodological Foundations. Kluwer Academic Publishers.
  14. Manning et al. (2008). Introduction to Information Retrieval. Cambridge University Press.
  15. Fortunato (2010). Community detection in graphs. Physics Reports. doi.org/10.1016/j.physrep.2009.11.002
  16. Chandola et al. (2009). Anomaly Detection: A Survey. ACM Comput. Surv.. doi.org/10.1145/1541880.1541882
  17. Coates and Ng (2012). Learning Feature Representations with K-Means. Neural Networks: Tricks of the Trade. doi.org/10.1007/978-3-642-35289-8_30
  18. Späth (1979). Algorithm 39: Clusterwise linear regression. Computing. doi.org/10.1007/BF02265317

Cite this entry

@misc{dictml_clustering,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {clustering},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-10-27},
  url = {https://dictionaryofml.org/terms/clustering.html}
}