# clustering *Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-08. [HTML](https://dictionaryofml.org/terms/clustering.html) · [typeset PDF](https://dictionaryofml.org/terms/clustering.pdf) · [LaTeX](https://dictionaryofml.org/terms/clustering.tex) · [Python demo](https://dictionaryofml.org/terms/clustering.py) · [notebook](https://dictionaryofml.org/terms/clustering.ipynb)* Math is LaTeX with the book's macros expanded, so no notation package is needed to read it. ## Abstract 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 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. ## Definition A photograph taken in the Wachau shows sky, clouds, forested slopes, sunlit vineyards and rock (Fig. 1(a)). Cutting it into patches of $5 \times 5$ pixels gives $12288$ data points, each characterized by a feature vector ${\mathbf x} \in \mathbb{R}^{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). Painting each patch in the mean color of its cluster divides the photograph into regions, an image segmentation. Fig. 1(b)–(f) shows the segmentations delivered by five clustering methods, k-means, a Gaussian mixture model, density-based spatial clustering of applications with noise, spectral clustering and convex clustering. The number $k$ of clusters is either an input, as in k-means, or determined by the method from its other hyperparameters, as in density-based spatial clustering of applications with noise. ![Figure 1 of the entry clustering](https://dictionaryofml.org/terms/fig/clustering-fig1.svg) *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 Gaussian mixture model, both with $k = 5$; (d) density-based spatial clustering of applications with noise with $\varepsilon = 0.03$ and $m^{*} = 32$, noise patches in black; (e) spectral clustering with $k = 5$ and (f) convex clustering with $\alpha \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): - 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; - 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 - 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 Gaussian mixture model; 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](https://dictionaryofml.org/terms/fig/clustering-fig2.svg) *Figure 2: Three families of clustering methods, sketched for data points with feature vectors in $\mathbb{R}^{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 Gaussian mixture model: two overlapping ellipses (dashed and dotted ellipses), 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 edges) 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 approaches by alternating assignment and averaging (Lloyd, 1982): each step lowers the average, and the iterates converge to a local minimum, not necessarily the global one (Bishop, 2006, Sect. 9.1). On the photograph, the five cluster centroids of k-means with $k = 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. A Gaussian mixture model 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 algorithm learns the model parameters by maximum likelihood (Bishop, 2006, Sect. 9.2). The result is a soft clustering whose clusters are ellipsoids, the level sets of a multivariate normal distribution (Bishop, 2006, Sect. 2.3); hard clustering is the extreme case in which every degree of belonging is $0$ or $1$, reached when all clusters share the covariance matrix $\epsilon \mathbf{I}$ and $\epsilon \to 0$ (Bishop, 2006, Sect. 9.3.2). 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$. Density-based spatial clustering of applications with noise 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 the two hyperparameters of Fig. 1(d), 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 $r = 1, \ldots, m$ of a graph whose edge weights express the similarity between data points, e.g., the k-nearest-neighbor 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). Spectral 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 ${\mathbf x}^{(r)}$, $r = 1, \ldots, m$: convex clustering combines the connectivity of the nodes with the node-wise feature vectors. Graph clustering methods suit 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, as Euclidean vectors or as the nodes of a similarity graph, and of a cluster; the penalty term of convex clustering is weighted by the edges of that graph. ![Figure 3 of the entry clustering](https://dictionaryofml.org/terms/fig/clustering-fig3.svg) *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 Gaussian mixture model delivers ellipsoids and density-based spatial clustering of applications with noise 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 uses both representations: 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 uses both representations of Fig. 3. It gives every data point ${\mathbf x}^{(r)}$ its own cluster centroid ${{\mathbf w}}^{(r)}$, which avoids the non-convexity of the clustering error. The method minimizes the convex objective function $$ \sum_{r=1}^{m} \left\lVert {\mathbf x}^{(r)} - {{\mathbf w}}^{(r)} \right\rVert_{2}^{2} + \alpha \sum_{1 \le r < r' \le m} A_{r,r'} \left\lVert {{\mathbf w}}^{(r)} - {{\mathbf w}}^{(r')} \right\rVert_{2} \text{.} $$ The penalty term fuses cluster centroids with weights $A_{r,r'} \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. At $\alpha = 0$ every cluster centroid equals its data point, so distinct data points form $m$ clusters. Once $\alpha$ is large enough, all cluster centroids of a connected component of the graph with the weights $A_{r,r'}$ as its edge weights coincide, so the number of clusters is set indirectly through $\alpha$. 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 the $\alpha$ of Fig. 1(f), the fused cluster centroids leave $65$ clusters, four of them with at least $80$ patches; like density-based spatial clustering of applications with noise, 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 (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). 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). **Synonyms:** segmentation. **See also:** cluster, cluster centroid, clustering error, degree of belonging, hard clustering, soft clustering, [$k$-means](https://dictionaryofml.org/terms/kmeans.html), [Gaussian mixture model](https://dictionaryofml.org/terms/gmm.html), [expectation–maximization](https://dictionaryofml.org/terms/em.html), density-based spatial clustering of applications with noise, spectral clustering, graph clustering, flow-based clustering, convex clustering, coreset, [hyperparameter](https://dictionaryofml.org/terms/hyperparameter.html), anomaly detection, image segmentation, similarity graph, Laplacian matrix, $k$-nearest-neighbor graph, [unsupervised learning](https://dictionaryofml.org/terms/unsupervisedlearning.html). ## References - Bishop (2006). Pattern Recognition and Machine Learning. *Springer Science+Business Media*. - Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. - Jain et al. (1999). Data clustering: a review. *ACM Computing Surveys*. - Lloyd (1982). Least squares quantization in PCM. *IEEE Trans. Inf. Theory*. - 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*. - Luxburg (2007). A tutorial on spectral clustering. *Statist. Comput.*. - Ng et al. (2001). On Spectral Clustering: Analysis and an Algorithm. *Adv. Neural Inf. Process. Syst.*. - SarcheshmehPour et al. (2021). Flow-Based Clustering and Spectral Clustering: A Comparison. *2021 55th Asilomar Conf. Signals, Syst., Comput.*. - Hocking et al. (2011). Clusterpath: An Algorithm for Clustering using Convex Fusion Penalties. *Proc. of the 28th International Conference on Machine Learning,*. - Sun et al. (2021). Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm. *J. Mach. Learn. Res.*. - Lindsten et al. (2011). Clustering using sum-of-norms regularization: With application to particle filter output computation. *2011 IEEE Statistical Signal Processing Workshop (SSP)*. - Wedel and Kamakura (2000). Market Segmentation: Conceptual and Methodological Foundations. *Kluwer Academic Publishers*. - Manning et al. (2008). Introduction to Information Retrieval. *Cambridge University Press*. - Fortunato (2010). Community detection in graphs. *Physics Reports*. - Chandola et al. (2009). Anomaly Detection: A Survey. *ACM Comput. Surv.*. - Coates and Ng (2012). Learning Feature Representations with K-Means. *Neural Networks: Tricks of the Trade*. - Späth (1979). Algorithm 39: Clusterwise linear regression. *Computing*. - Har-Peled and Mazumdar (2004). On coresets for $k$-means and $k$-median clustering. *Proc. 36th Annual ACM Symp. Theory of Computing (STOC)*. ## Cite this entry ```bibtex @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-11-11}, url = {https://dictionaryofml.org/terms/clustering.html} } ```