--- title: "Clustering" aliases: ["Cluster analysis", "Unsupervised classification"] tags: - unsupervised - clustering --- # 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]( "An Impossibility Theorem for Clustering; NeurIPS"). - **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]( "Data clustering: 50 years beyond K-means; Pattern Recognit. Lett."). ## 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]( "Least squares quantization in PCM; IEEE Trans. Inform. Theory"); [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]( "Concept Decompositions for Large Sparse Text Data Using Clustering; Mach. Learn."). - **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]( "k-means++: the advantages of careful seeding; SODA"). - **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]( "Web-Scale K-Means Clustering; WWW"); [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]( "FCM: The fuzzy c-means clustering algorithm; Comput. Geosci."). - **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]( "Clustering with Bregman Divergences; JMLR"). - **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]( "Clustering by Passing Messages Between Data Points; Science"). - **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]( "Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms; LNCS"). ## 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]( "Maximum Likelihood from Incomplete Data Via the EM Algorithm; JRSS B"); [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]( "Variational inference for Dirichlet process mixtures; Bayesian Anal."); [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]( "Hierarchical Grouping to Optimize an Objective Function; JASA"); [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]( "BIRCH: an efficient data clustering method for very large databases; SIGMOD"), [Zhang et al. 1997]( "BIRCH: A new data clustering algorithm and its applications; Data Mining and Knowledge Discovery"). ## 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]( "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise; KDD"). - **OPTICS** - Produces an ordering and reachability distances exposing density structure across neighborhood scales. Extracting a partition is a separate step. [Ankerst et al. 1999]( "OPTICS: ordering points to identify the clustering structure; SIGMOD"); [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 🔒]( "Density-Based Clustering Based on Hierarchical Density Estimates; LNCS"); [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]( "Mean shift: a robust approach toward feature space analysis; TPAMI"); [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]( "On Spectral Clustering: Analysis and an algorithm; NeurIPS"), [von Luxburg 2007]( "A Tutorial on Spectral Clustering; Statistics and Computing"). - **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]( "Fast unfolding of communities in large networks; J. Stat. Mech."). - **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]( "From Louvain to Leiden: guaranteeing well-connected communities; Scientific Reports"). - **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]( "Maps of random walks on complex networks reveal community structure; PNAS"). - **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]( "Sparse Subspace Clustering: Algorithm, Theory, and Applications; IEEE Transactions on Pattern Analysis and Machine Intelligence"). ## 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]( "Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values; Data Min. Knowl. Discov."). - **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]( "Constrained K-means Clustering with Background Knowledge; ICML"). - **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]( "Cluster Ensembles --- A Knowledge Reuse Framework for Combining Multiple Partitions; JMLR"). - **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]( "Correlation Clustering; Mach. Learn."). - **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]( "k-Shape; SIGMOD"). ## 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]( "Unsupervised Deep Embedding for Clustering Analysis; ICML"). - **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]( "Deep Clustering for Unsupervised Learning of Visual Features; ECCV"); [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]( "SCAN: Learning to Classify Images without Labels; ECCV"). - **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]( "CLUBench: A Clustering Benchmark; KDD"). - **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 🔒]( "Comparing partitions; Journal of Classification"); [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]( "Silhouettes: A graphical aid to the interpretation and validation of cluster analysis; JCAM"); [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]( "Estimating the Number of Clusters in a Data Set Via the Gap Statistic; JRSS B"). - **Mixture model selection** - BIC compares Gaussian component counts and covariance structures with a complexity penalty. [Baudry et al. 2010]( "Combining Mixture Components for Clustering; Journal of computational and graphical statistics : a joint publication of American Statistical Association, Institute of Mathematical Statistics, Interface Foundation of North America"); [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]( "Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance; JMLR"). - **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]( "Clustering Stability: An Overview; Found. Trends ML"). - **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]( "CLUBench: A Clustering Benchmark; KDD"). ## 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](). ## Related topics - [Feature Extraction](https://mlpapers.org/feature-extraction/) - [Modeling](https://mlpapers.org/models/)