Clustering

Follow this topic Ask about this topic

Clustering seeks useful groupings when labels are absent or incomplete, helping reveal structure in data such as text, images, graphs, time series, and scientific measurements. Methods include centroid-based k-means, density and hierarchical clustering, graph and spectral methods, mixture models, and newer approaches that learn embeddings or use optimal transport; fairness, privacy, streaming, and federated settings add further constraints. Work also studies how to choose the number of clusters and assess stability, uncertainty, interpretability, and statistical significance. No single method works best across data types: deep methods do not consistently beat strong conventional algorithms, and reliable validation remains a central challenge.

Latest papers

345 papers31 papers in the last four weeks, up 11% on the four weeks before. 0.2% of all new papers.

Sep 4, 2025

DRtool: An Interactive Tool for Analyzing High-Dimensional Clusterings

When faced with new data, we often conduct a cluster analysis to obtain a better understanding of the data's structure and the archetypical samples present in the data. However, the increases in data complexity and dimensionality have made this step very tricky. The large proportion of noise in high-dimensional data blurs patterns and trends, making clusters difficult to distinguish. As such, cluster-discovery tools and cluster-verification tools must be adapted to address the difficulties of high-dimensional data. Nonlinear dimension reduction is a step in the right direction, but even these methods are known to produce false structures, especially when mishandled. A common phenomenon that often goes undetected by the untrained eye is over-clustering of the data. In continuation of these efforts, we developed new cluster verification techniques, including visual assessments and a hypothesis test, that help analysts distinguish false clusters and better interpret their high-dimensional clustering results. For ease of use, these new methods are provided in an interactive toolbox available via R package DRTool.

Justin Lin, Julia Fukuyama

Department of Mathematics, Indiana University · Department of Statistics, Indiana University

Aug 11, 2025

Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters

Clustering algorithms often assume all features contribute equally to the data structure, an assumption that usually fails in high-dimensional or noisy settings. Feature weighting methods can address this, but most require additional parameter tuning. We propose SHARK (Shapley Reweighted

k

-means), a feature-weighted clustering algorithm motivated by the use of Shapley values from cooperative game theory to quantify feature relevance, which requires no additional parameters beyond those in

k

-means. We prove that the

k

-means objective can be decomposed into a sum of per-feature Shapley values, providing an axiomatic foundation for unsupervised feature relevance and reducing Shapley computation from exponential to polynomial time. SHARK iteratively re-weights features by the inverse of their Shapley contribution, emphasising informative dimensions and down-weighting irrelevant ones, and is equivalent to replacing the arithmetic mean of feature dispersions with their harmonic mean. Experiments on synthetic and real-world data sets show that SHARK consistently matches or outperforms existing methods, achieving superior robustness and accuracy, particularly in scenarios where noise may be present. Software: https://github.com/rickfawley/SHARK.

Richard J. Fawley, Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Clustering Unsupervised Clustering

Jul 31, 2025

funOCLUST: Clustering Functional Data with Outliers

Functional data present unique challenges for clustering due to their infinite-dimensional nature and potential sensitivity to outliers. An extension of the OCLUST algorithm to the functional setting is proposed to address these issues. The approach leverages the OCLUST framework, creating a robust method to cluster curves and trim outliers. The methodology is evaluated on both simulated and real-world functional datasets, demonstrating strong performance in clustering and outlier identification.

Katharine M. Clark, Paul D. McNicholas

Department of Mathematics & Statistics, Trent University, Ontario, Canada. · Department of Mathematics & Statistics, McMaster University, Ontario, Canada.

Functional Data Analysis Clustering Unsupervised Clustering

Jun 6, 2025

Scalable unsupervised feature selection via weight stability

Unsupervised feature selection is critical for improving clustering performance in high-dimensional data, where irrelevant features can obscure meaningful structure. In this work, we propose the Minkowski weighted

k

-means++, a novel initialisation strategy for the Minkowski Weighted

k

-means. Our initialisation selects centroids probabilistically using feature relevance estimates derived from the data itself. Building on this, we propose two new feature selection algorithms, FS-MWK++, which aggregates feature weights across a range of Minkowski exponents identifying stable and informative features, and SFS-MWK++, a scalable variant based on subsampling. We support our approach with a theoretical analysis, demonstrating that, under explicit assumptions on noise features and cluster structure, relevant features are assigned consistently higher weights than noise features across a range of Minkowski exponents. Our software can be found at https://github.com/xzhang4-ops1/FSMWK.

Xudong Zhang, Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Unsupervised Learning Clustering Unsupervised Clustering Feature Selection

May 21, 2025

Clustering and Pruning in Causal Data Fusion

Data fusion, the process of combining observational and experimental data, can enable the identification of causal effects that would otherwise remain non-identifiable. Although identification algorithms have been developed for specific scenarios, do-calculus remains the only general-purpose tool for causal data fusion, particularly when variables are present in some data sources but not others. However, approaches based on do-calculus may encounter computational challenges as the number of variables increases and the causal graph grows in complexity. Consequently, there exists a need to reduce the size of such models while preserving the essential features. For this purpose, we propose pruning (removing unnecessary variables) and clustering (combining variables) as preprocessing operations for causal data fusion. We generalize earlier results on a single data source and derive conditions for applying pruning and clustering in the case of multiple data sources. We give sufficient conditions for inferring the identifiability or non-identifiability of a causal effect in a larger graph based on a smaller graph and show how to obtain the corresponding identifying functional for identifiable causal effects. Examples from epidemiology and social science demonstrate the use of the results.

Otto Tabell, Santtu Tikka, Juha Karvanen

Department of Mathematics and Statistics FI-40014 University of Jyvaskyla, Finland

Clustering Causal Identifiability

Sep 17, 2024

Clustering with Non-adaptive Subset Queries

Recovering the underlying

k

-clustering of a set

U

of

n

points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query

S \subset U

,

|S|=2

, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be

Θ(nk)

, while non-adaptive algorithms are extremely limited: even for

k=3

, such algorithms require

Ω(n^2)

queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for

|S|>2

, where the oracle returns the number of clusters intersecting

S

. Previous work obtained an

O(n)

query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making

O(n \log k \cdot (\log k + \log\log n)^2)

queries, improving to

O(n \log \log n)

when

k

is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound,

s

, on the query size. We show

Ω(\max(n^2/s^2,n))

queries are necessary and obtain algorithms making

\smash{\widetilde{O}(n^2k/s^2)}

queries for any

s \leq \sqrt{n}

and

\smash{\widetilde{O}(n^2/s)}

queries for any

s \leq n

. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.

Hadley Black, Euiwoong Lee, Arya Mazumdar +1

CUNY Baruch College · University of Michigan · UC San Diego

Query Complexity Clustering

Sep 1, 2024

Interpretable Clustering: A Survey

In recent years, much of the research on clustering algorithms has primarily focused on enhancing their accuracy and efficiency, frequently at the expense of interpretability. However, as these methods are increasingly being applied in high-stakes domains such as healthcare, finance, and autonomous systems, the need of transparent and interpretable clustering outcomes has become a critical concern. This is not only necessary for gaining user trust but also for satisfying the growing ethical and regulatory demands in these fields. Ensuring that decisions derived from clustering algorithms can be clearly understood and justified is now a fundamental requirement. To address this need, this paper provides a comprehensive and structured review of the current state of explainable clustering algorithms, identifying key criteria to distinguish between various methods. These insights can effectively assist researchers in making informed decisions about the most suitable explainable clustering methods for specific application contexts, while also promoting the development and adoption of clustering algorithms that are both efficient and transparent. For convenient access and reference, an open repository organizes representative and emerging interpretable clustering methods under the taxonomy proposed in this survey, available at https://hulianyu.xyz/Interpretable-Clustering-Repository

Lianyu Hu, Mudi Jiang, Junjie Dong +2

College of Information Science and Engineering, Henan University of Technology, China · School of Software, Dalian University of Technology, China · Xinchang Power Supply Company, State Grid Corporation of China, China

Clustering Interpretable ML

Aug 6, 2024

Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping

Clustering is a fundamental task in machine learning and data science, and similarity graph-based clustering is an important approach within this domain. Doubly stochastic symmetric similarity graphs provide numerous benefits for clustering problems and downstream tasks, yet learning such graphs remains a significant challenge. Marcus theorem states that a strictly positive symmetric matrix can be transformed into a doubly stochastic symmetric matrix by diagonal matrices. However, in clustering, learning sparse matrices is crucial for computational efficiency. We extend Marcus theorem by proposing the Marcus mapping, which indicates that certain sparse matrices can also be transformed into doubly stochastic symmetric matrices via diagonal matrices. Additionally, we introduce rank constraints into the clustering problem and propose the Doubly Stochastic Adaptive Neighbors Clustering algorithm based on the Marcus Mapping (ANCMM). This ensures that the learned graph naturally divides into the desired number of clusters. We validate the effectiveness of our algorithm through extensive comparisons with state-of-the-art algorithms. Finally, we explore the relationship between the Marcus mapping and optimal transport. We prove that the Marcus mapping solves a specific type of optimal transport problem.

Jinghui Yuan, Chusheng Zeng, Fangyuan Xie +5

School of Artificial Intelligence, OPtics and ElectroNics (iOPEN), Northwestern Polytechnical University, Xi’an 710072, Shaanxi, China · Institute of Artificial Intelligence (TeleAI), China Telecom, P. R. China

Clustering Graph Clustering Matrix Optimization

Jul 15, 2024

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means

Clustering problems such as

k

-means and

k

-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.

Max Dupré la Tour, David Saulpic

Clustering Approximation Algorithms

Feb 3, 2024

Sample-Efficient "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection

This work aims to improve the sample efficiency of parallel large-scale ranking and selection (R&S) problems by leveraging correlation information. We modify the commonly used "divide and conquer" framework in parallel computing by adding a correlation-based clustering step, transforming it into "clustering and conquer". Theoretically, we develop a novel gradient-based analysis framework and show that this seemingly simple modification substantially improves the performance of large-scale R&S procedures. Our approach enjoys two key advantages: (1) it does not require highly accurate correlation estimation or precise clustering, and (2) it can be seamlessly integrated with various existing fixed-precision and fixed-budget R&S procedures while achieving optimal sample complexity. We also introduce a new parallel clustering algorithm tailored to large-scale settings. Finally, in large-scale AI applications such as neural architecture search, our methods demonstrate superior performance.

Zishi Zhang, Yijie Peng

Guanghua School of Management, Peking University, Beijing 100871, China · School of Management and Engineering, Nanjing University, Nanjing 210008, China

Nov 27, 2023

Optimal Clustering of Multi-layer Networks under Mixture Block Models

We study clustering for multi-layer networks, where each observation is an undirected network measured on the same set of vertices. Under the mixture multi-layer stochastic block model (MMSBM), each network is generated from one of two stochastic block models, and the goal is to recover the latent network labels. We establish the minimax optimal network clustering error rate, which takes an exponential form and is characterized by the Chernoff information between the edge probability distributions of the component networks. We propose a novel two-stage estimator that combines tensor-based initialization, node and sample splitting, and a likelihood-based refinement. The refinement step exploits estimated node communities and achieves the minimax rate with high probability under extreme network sparsity. We further extend the likelihood-refinement framework to count-weighted networks through a mixture multi-layer Poisson block model. Numerical studies and two real-data analyses illustrate the finite-sample behavior of the proposed method and its use for both external-label benchmarking and unlabeled exploratory network clustering.

Zhongyuan Lyu, Ting Li, Dong Xia

Department of Mathematics, Hong Kong University of Science and Technology · Department of Applied Mathematics, The Hong Kong Polytechnic University

Clustering Stochastic Block Model Multi-View Clustering

Oct 8, 2023

Clustering Three-Way Data with Outliers

Matrix-variate distributions are a relatively recent addition to the model-based clustering literature, thereby making it possible to analyze data in matrix form with complex structure such as images and time series. Due to its recent appearance, there is limited literature on matrix-variate data, with even less on dealing with outliers in these models. An approach for clustering matrix-variate normal data with outliers is discussed. The approach, which uses the distribution of subset log-likelihoods, extends the OCLUST algorithm to matrix-variate normal data and uses an iterative approach to detect and trim outliers.

Katharine M. Clark, Paul D. McNicholas

Department of Mathematics & Statistics, Trent University, Ontario, Canada. · Department of Mathematics & Statistics, McMaster University, Ontario, Canada.

Jun 22, 2023

Reinforcement Federated Learning Method Based on Adaptive OPTICS Clustering

Federated learning is a distributed machine learning technology, which realizes the balance between data privacy protection and data sharing computing. To protect data privacy, feder-ated learning learns shared models by locally executing distributed training on participating devices and aggregating local models into global models. There is a problem in federated learning, that is, the negative impact caused by the non-independent and identical distribu-tion of data across different user terminals. In order to alleviate this problem, this paper pro-poses a strengthened federation aggregation method based on adaptive OPTICS clustering. Specifically, this method perceives the clustering environment as a Markov decision process, and models the adjustment process of parameter search direction, so as to find the best clus-tering parameters to achieve the best federated aggregation method. The core contribution of this paper is to propose an adaptive OPTICS clustering algorithm for federated learning. The algorithm combines OPTICS clustering and adaptive learning technology, and can effective-ly deal with the problem of non-independent and identically distributed data across different user terminals. By perceiving the clustering environment as a Markov decision process, the goal is to find the best parameters of the OPTICS cluster without artificial assistance, so as to obtain the best federated aggregation method and achieve better performance. The reliability and practicability of this method have been verified on the experimental data, and its effec-tiveness and superiority have been proved.

Tianyu Zhao, Junping Du, Yingxia Shao +1

Beijing Key Laboratory of Intelligent Communication Software and Multimedia, School of Computer Science (National Pilot Software Engineering School), Beijing University of Posts and Telecommunications, Beijing, China

Federated Learning Aggregation Clustering Unsupervised Clustering Non-IID Federated Learning Clustered Federated Learning

Apr 27, 2023

Proportionally Representative Clustering

In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering--one of the fundamental tasks in unsupervised machine learning. We propose a new axiom ``proportionally representative fairness'' (PRF) that is designed for clustering problems where the selection of centroids reflects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair clustering algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom. Our algorithm for the discrete setting also matches the best known approximation factor for PF.

Haris Aziz, Barton E. Lee, Sean Morota Chu +1

UNSW Sydney · ETH Zürich · Northwestern University

Clustering Algorithmic Fairness Group Fairness Approximation Algorithms

Jun 10, 2022

Anisotropic View Distance Metric for High-Dimensional Data: Theory, Geometry, and Fast Computation

K-Means clustering algorithm is one of the most commonly used clustering algorithms because of its simplicity and efficiency. K-Means clustering algorithm based on Euclidean distance only pays attention to the linear distance between Euclidean distance is an efficient and interpretable similarity measurement, but its effectiveness may deteriorate in sample spaces with anisotropic structures, redundant features, or complex feature interactions. In this paper, we propose a novel distance metric called View distance. Inspired by orthographic projection, the proposed metric projects the sample space onto

n(n-1)/2

two-dimensional planes and defines the final distance as the sum of the Euclidean distances across the projected planes. Theoretical derivations verify that the View distance strictly satisfies the metric axioms and norm constraints. Beyond that, the View distance achieves feature coupling through projection and not only enables constant features to indirectly participate in distance calculation, but also suppresses interference from redundant features while exhibiting anisotropic geometric properties. Furthermore, to address the high computational complexity and poor scalability of full-projection View distance, we propose a two-dimensional projection plane selection strategy based on iterative Maximum Weight Matching, which reduces the computational complexity of distance calculation from

\mathcal{O}(n^2)

to

\mathcal{O}(k)

. Extensive experiments on 12 diverse datasets demonstrate that View distance and the deterministic selection strategy provide competitive or superior performance compared with Euclidean distance and other

L_{p}

metrics while maintaining strong interpretability and computational efficiency. The View distance provides a new perspective and option for similarity measurements.

Yiqun Zhang, Hou-biao Li

School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China