48  Clustering

Clustering divides cases into groups, clusters, so that cases within a group are similar to each other and different from cases in other groups, without an outcome to define what the groups should predict. Every clustering algorithm finds groups in any dataset, whether or not the data contain distinct groups, so the questions of how many clusters there are and whether they are meaningful are part of the analysis. This chapter presents partitioning, probabilistic, hierarchical, density-based and spectral methods, and the criteria used to choose and assess a clustering.

48.1 Similarity

Clustering requires a measure of similarity or distance between cases, usually the Euclidean distance between feature vectors (AMDS: Distance). As for nearest neighbors (Section 24.2), the distance depends on the scale of each feature and on which features are included: standardizing the features gives each the same weight, and adding features unrelated to the structure of interest blurs it. The choice of features and of distance defines what “similar” means, and therefore which clusters can be found.

48.2 Partitioning methods

k-means partitions the cases into \(k\) clusters to minimize the within-cluster sum of squared distances to the cluster means, the centroids:

\[ \min_{C_1, \dots, C_k} \sum_{j=1}^{k} \sum_{i \in C_j} \lVert x_i - \mu_j \rVert^2 . \tag{48.1}\]

Lloyd’s algorithm alternates between assigning each case to the nearest centroid and recomputing the centroids, until the assignments stop changing (Lloyd 1982; MacQueen 1967). It converges to a local minimum that depends on the starting centroids, so it is run from several starts. k-means finds convex, roughly spherical clusters of similar spread.

Partitioning around medoids (PAM) uses medoids, actual cases, as cluster centers, and minimizes the sum of distances rather than squared distances (Kaufman and Rousseeuw 1990). It accepts any dissimilarity and is less influenced by outlying cases. Hard competitive learning and neural gas are online vector quantization methods that move prototypes toward each case presented, the latter by an amount that decreases with the prototype’s rank in distance (Martinetz et al. 1993).

48.3 Probabilistic methods

A Gaussian mixture model assumes that the cases are drawn from a mixture of \(k\) multivariate normal distributions, each with its own mean and covariance matrix (AMDS: Mixtures). Its parameters are estimated by the expectation–maximization algorithm (Dempster et al. 1977), and each case receives a posterior probability of membership in each component, a soft clustering. Constraints on the covariance matrices, from spherical and equal to unconstrained, define a family of models, and the number of components and the covariance model can be chosen by the Bayesian information criterion (Fraley and Raftery 2002). Fuzzy c-means also assigns degrees of membership, by a weighted version of the k-means objective (Bezdek 1981).

48.4 Hierarchical methods

Agglomerative hierarchical clustering starts with each case as a cluster and repeatedly merges the two closest clusters, where the distance between clusters is defined by a linkage: the minimum (single), maximum (complete) or average distance between their members, or the increase in within-cluster variance (Ward’s method). The sequence of merges forms a tree, the dendrogram, and cutting it at a height gives a partition (Hastie et al. 2009). HOPACH builds a hierarchy by alternating divisive steps, which split clusters with PAM, and collapsing steps, which merge similar clusters, and selects the number of clusters at each level by a silhouette criterion (van der Laan and Pollard 2003).

48.5 Density-based and spectral methods

DBSCAN defines clusters as regions of high density: a case with at least min_points cases within distance \(\varepsilon\) is a core point, clusters are sets of core points connected through such neighborhoods together with the points within reach of them, and cases outside every cluster are labeled noise (Ester et al. 1996). It finds clusters of arbitrary shape and determines their number, and requires the choice of \(\varepsilon\).

Spectral clustering builds a similarity graph of the cases, for example with Gaussian kernel weights \(\exp(-\lVert x_i - x_j \rVert^2 / 2\sigma^2)\), computes the leading eigenvectors of its normalized graph Laplacian, and clusters the cases in the space of those eigenvectors with k-means (Ng et al. 2002; von Luxburg 2007) (AMDS: Eigenvalues and Eigenvectors). Clusters connected in the graph can have any shape. The kernel width \(\sigma\) can be set per case from the distance to its \(k\)-th nearest neighbor, so that clusters of different density are found together (Zelnik-Manor and Perona 2005).

Figure 48.1: Two interleaved half circles clustered by k-means with \(k = 2\) (top) and by DBSCAN with \(\varepsilon = 0.15\) and 5 points (bottom).

In Figure 48.1, k-means divides the data by a straight boundary between two centroids, and assigns parts of each half circle to the wrong cluster; DBSCAN follows the connected regions of high density.

48.6 Choosing the number of clusters

Most methods require the number of clusters, and the within-cluster sum of squares decreases with every added cluster. Internal criteria balance compactness and separation:

  • The silhouette of case \(i\) is \(s_i = (b_i - a_i)/\max(a_i, b_i)\), where \(a_i\) is its mean distance to the other cases of its cluster and \(b_i\) its mean distance to the cases of the nearest other cluster; values near 1 indicate a well-placed case, near 0 a case between clusters (Rousseeuw 1987). The average silhouette width is maximized over \(k\).
  • The Calinski–Harabasz index is the ratio of between-cluster to within-cluster dispersion, adjusted for the number of clusters (Caliński and Harabasz 1974).
  • For mixture models, the BIC compares models with different numbers of components by their likelihood penalized for their number of parameters.

The criteria often disagree, and when the data have no clear cluster structure, all of them select among partitions that are equally arbitrary.

48.7 Assessing a clustering

A clustering is assessed by its stability, whether similar clusters are found in resamples of the data; by external variables not used in the clustering, such as outcomes or known groups, compared with the adjusted Rand index (Hubert and Arabie 1985), which is 0 for agreement expected by chance and 1 for identical partitions; and by interpretation of the cluster profiles. Clusters found in data are a description of that data under the chosen features and distance. They are evidence of distinct subtypes only when they are stable, reproducible in independent data, and separated in the original feature space rather than only in a low-dimensional projection (Section 46.4).

48.8 Summary

  • Clustering groups similar cases without an outcome; the features and distance define similarity.
  • k-means and PAM find compact clusters around centers; Gaussian mixtures give probabilistic memberships; hierarchical methods give nested partitions.
  • DBSCAN finds dense regions of any shape and labels noise; spectral clustering finds connected groups in a similarity graph.
  • The number of clusters is chosen by internal criteria such as the silhouette, which can disagree.
  • Clusters are assessed by stability, external variables and reproducibility; every algorithm returns clusters even in their absence.

48.9 Further reading