Clustering

🔒 Full text at this link requires payment or institutional access. Unmarked links may be unchecked.

Overviews

  • An Impossibility Theorem for Clustering - No clustering function satisfies scale invariance, richness, and consistency together under the paper’s definitions. The result concerns these axioms, not every clustering formulation. Kleinberg 2002.
  • Data Clustering: 50 Years Beyond K-Means - Survey of clustering objectives, algorithms, representation choices, and validation; similarity and the intended grouping determine which methods are appropriate. Jain 2010.

Partitions and Prototypes

  • K-means - Alternates nearest-centroid assignment and centroid updates to reduce squared Euclidean distortion. Requires a cluster count; initialization affects the local solution. Lloyd 1982; docs.
    • Spherical k-means - Clusters normalized document vectors using unit-length centroids and cosine similarity. Groups vector directions rather than magnitudes. Dhillon and Modha 2001.
    • K-means++ - Seeds centers using squared distance from existing centers; provides an expected approximation bound for the k-means objective, without guaranteeing the global optimum. Arthur and Vassilvitskii 2007.
    • Mini-batch k-means - Updates centroids from small random batches instead of full passes. Trades optimization accuracy for cheaper updates; supports incremental fitting in scikit-learn. Sculley 2010; docs.
  • Fuzzy c-means - Optimizes weighted distances to centroids with graded memberships controlled by a fuzzifier. These memberships are not posterior probabilities from a fitted mixture model. Bezdek et al. 1984.
  • Bregman clustering - Generalizes hard and soft centroid clustering to Bregman divergences and connects these objectives to exponential-family mixtures; squared Euclidean k-means is one special case. Banerjee et al. 2005.
  • Affinity propagation - Exchanges messages between observations to select exemplars from pairwise similarities. Exemplar preferences influence the number of clusters, replacing a fixed cluster-count input. Frey and Dueck 2007.
  • K-medoids / FastPAM - Uses observed objects as representatives and minimizes dissimilarity to them. FastPAM accelerates PAM’s swap search; unlike k-means, medoids support non-Euclidean dissimilarities. Schubert and Rousseeuw 2019.

Mixture Models

  • Gaussian mixtures and EM - EM alternates posterior component responsibilities and parameter updates. Gaussian covariance choices control component shapes; fitting can reach local optima. Dempster et al. 1977; docs.
  • Dirichlet process mixtures - Variational inference for mixtures with an unbounded component model. Practical truncated approximations retain a component cap; priors influence active components. Blei and Jordan 2006; docs.

Hierarchical Clustering

  • Agglomerative linkage - Single, complete, and average linkage merge clusters using minimum, maximum, or average cross-cluster distances. The linkage defines the dendrogram; cutting it selects a partition. docs.
  • Ward’s method - Merges the pair giving the smallest increase in within-cluster sum of squares. Its variance interpretation requires Euclidean geometry. Ward 1963; docs.
  • BIRCH - Compresses observations into a tree of clustering-feature summaries, then clusters the summaries. Threshold and memory choices control compression. Zhang et al. 1996, Zhang et al. 1997.

Density and Modes

  • DBSCAN - Groups density-connected regions using a neighborhood radius and minimum neighbor count; leaves other points as noise. A single radius can struggle with unequal cluster densities. Ester et al. 1996.
    • OPTICS - Produces an ordering and reachability distances exposing density structure across neighborhood scales. Extracting a partition is a separate step. Ankerst et al. 1999; docs.
    • HDBSCAN - Builds a density hierarchy and selects persistent clusters, allowing different densities and noise. Minimum cluster size and density settings still affect the result. Campello et al. 2013 🔒; docs.
  • Mean shift - Moves candidate centers toward modes of a kernel density estimate. Bandwidth sets the scale of grouping; the number of clusters is not specified directly. Comaniciu and Meer 2002; docs.

Spectral, Subspace, and Graph Methods

  • Spectral clustering - Clusters an eigenvector representation of an affinity graph. Graph construction determines the geometry; different normalizations lead to different objectives. Ng et al. 2001, von Luxburg 2007.
  • Louvain - Alternates local node moves and graph aggregation to optimize modularity. A graph-community heuristic; the result depends on the supplied edges and weights. Blondel et al. 2008.
    • Leiden - Adds partition refinement to avoid the disconnected communities Louvain can produce. Supports modularity and other objectives; connectivity guarantees do not imply a global optimum. Traag et al. 2019.
  • Infomap - Finds communities by compressing descriptions of random walks on a network. Flow between modules determines the partition, supporting weighted and directed graphs. Rosvall and Bergstrom 2008.
  • Sparse subspace clustering - Represents each point sparsely using other points, builds an affinity from the coefficients, and applies spectral clustering. Targets unions of low-dimensional subspaces. Elhamifar and Vidal 2013.

Categorical Data, Time Series, and Constraints

  • K-modes / k-prototypes - K-modes uses categorical mismatch counts and modes. K-prototypes combines categorical mismatch with numeric squared distances; their relative weight affects the partition. Huang 1998.
  • COP-KMeans - Incorporates must-link and cannot-link pairs into k-means assignments. Uses supervision through constraints; assignment can fail when no feasible cluster is available. Wagstaff et al. 2001.
  • Cluster ensembles - Combines multiple partitions into a consensus without requiring the original features. Agreement across input partitions is the objective, not independent evidence of correctness. Strehl and Ghosh 2002.
  • Correlation clustering - Partitions a signed similarity graph to minimize pairwise disagreements or maximize agreements. The number of clusters is an outcome rather than a required input; unlike hard constraints, conflicting pair labels can incur a cost. Bansal et al. 2004.
  • k-Shape - Uses normalized cross-correlation and shape-based centroids for time-series clustering, aligning sequences through shifts rather than local time warping. Paparrizos and Gravano 2015.

Learned Representations and Semantic Clustering

  • Deep Embedded Clustering (DEC) - Initializes an encoder with an autoencoder, then jointly refines its features and cluster centers using a sharpened target distribution and a KL-divergence objective. Xie et al. 2016.
  • DeepCluster - Alternates k-means on image features with network training to predict those assignments. Clustering supplies pseudo-labels for representation learning. Caron et al. 2018; code.
  • SCAN - Separates self-supervised feature learning from semantic image clustering; encourages neighboring representations to share assignments, followed by self-labeling. Van Gansbeke et al. 2020.
  • Pretrained embeddings - CLUBench (2026, preprint) finds conventional clustering on pretrained image/text features competitive in its experiments. Treat encoder, layer, pooling, normalization, and clustering settings as parts of the comparison. Xiao et al. 2026.
  • Clustering after UMAP - UMAP can support clustering preprocessing, but can distort density and create apparent separations. A two-dimensional display alone is insufficient evidence for distinct groups. docs.

Choosing and Evaluating a Partition

  • Adjusted Rand index - Measures pairwise agreement between partitions, adjusted for chance and invariant to cluster-label permutations. With reference classes, measures agreement with those classes rather than all possible useful groupings. Hubert and Arabie 1985 🔒; docs.
  • Silhouette - Compares a point’s mean within-cluster distance with its nearest alternative cluster. Favors compact, separated groups; scores depend on distance and representation. Rousseeuw 1987; docs.
  • Gap statistic - Compares within-cluster dispersion with its expectation under a reference null distribution across cluster counts. The reference distribution is part of the method. Tibshirani et al. 2001.
  • Mixture model selection - BIC compares Gaussian component counts and covariance structures with a complexity penalty. Baudry et al. 2010; docs.
  • Adjusted mutual information - Corrects mutual information between partitions for chance agreement. Unadjusted mutual information can reward extra clusters, especially with small samples. Vinh et al. 2010.
  • Resampling stability - Examines whether partitions persist under data perturbations. Stability depends on the algorithm and sampling scheme; high stability alone does not establish the correct cluster count. von Luxburg 2010.
  • New observations - K-means assigns points to fitted centroids. HDBSCAN’s approximate prediction holds the existing clustering fixed; it does not discover new clusters by refitting. docs, docs.
  • CLUBench - Compares 24 algorithms on 131 tabular, text and image datasets. Methods needing a cluster count receive the true count; DBSCAN noise is scored as one extra cluster. Rankings therefore depend on these evaluation choices. Xiao et al. 2026.

Software

  • scikit-learn - Prototype, hierarchical, density, and spectral methods; Gaussian mixtures and clustering metrics. SciPy provides linkage, dendrograms, and tree cuts. docs, docs, docs.
  • hdbscan - Density hierarchies, soft membership, and approximate prediction. scikit-learn HDBSCAN counts the point itself in min_samples; the contrib package excludes it. Equal settings are not equivalent. docs, code.
  • kmedoids - PAM and accelerated medoid algorithms. kmodes implements k-modes and k-prototypes for categorical and mixed data. code, code.
  • tslearn - Time-series clustering with Euclidean, dynamic-time-warping, and soft-DTW objectives; also provides k-Shape. docs, docs.
  • Faiss - K-means and spherical clustering using its nearest-neighbor index machinery, with GPU options. ELKI provides clustering algorithms and distance functions in Java. docs, code.
  • mclust - Gaussian mixture clustering and model selection in R. dbscan provides DBSCAN, HDBSCAN, OPTICS, and related density methods. code, code.
  • leidenalg - Leiden community detection for igraph graphs, with multiple quality functions and multiplex support. code.