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.

Mar 19, 2026

Statistical Testing Framework for Clustering Pipelines by Selective Inference

A data analysis pipeline is a structured sequence of steps that transforms raw data into meaningful insights by integrating multiple analysis algorithms. In many practical applications, analytical findings are obtained only after data pass through several data-dependent procedures within such pipelines. In this study, we address the problem of quantifying the statistical reliability of results produced by data analysis pipelines. As a proof of concept, we focus on clustering pipelines that identify cluster structures from complex and heterogeneous data through procedures such as outlier detection, feature selection, and clustering. We propose a novel statistical testing framework to assess the significance of clustering results obtained through these pipelines. Our framework, based on selective inference, enables the systematic construction of valid statistical tests for clustering pipelines composed of predefined components. We prove that the proposed test controls the type I error rate at any nominal level and demonstrate its validity and effectiveness through experiments on synthetic and real datasets.

Yugo Miyata, Tomohiro Shiraishi, Shuichi Nishino +1

Nagoya University · RIKEN

Statistical Hypothesis Testing Clustering Selective Inference

Mar 18, 2026

From Noise to Signal: When Outliers Seed New Topics

Outliers in dynamic topic modeling are typically treated as noise, yet we show that some can serve as early signals of emerging topics. We introduce a temporal taxonomy of news-document trajectories that defines how documents relate to topic formation over time. It distinguishes anticipatory outliers, which precede the topics they later join, from documents that either reinforce existing topics or remain isolated. By capturing these trajectories, the taxonomy links weak-signal detection with temporal topic modeling and clarifies how individual articles anticipate, initiate, or drift within evolving clusters. We implement it in a cumulative clustering setting using document embeddings from eleven state-of-the-art language models and evaluate it retrospectively on HydroNewsFr, a French news corpus on the hydrogen economy. Inter-model agreement reveals a small, high-consensus subset of anticipatory outliers, increasing confidence in these labels. Qualitative case studies further illustrate these trajectories through concrete topic developments.

Evangelia Zve, Gauvain Bourgne, Benjamin Icard +1

Sorbonne Université, CNRS, LIP6, France · Infopro Digital, France

Topic Modeling Clustering Anomaly Detection

Mar 18, 2026

Efficient Dense Crowd Trajectory Prediction Via Dynamic Clustering

Crowd trajectory prediction plays a crucial role in public safety and management, where it can help prevent disasters such as stampedes. Recent works address the problem by predicting individual trajectories and considering surrounding objects based on manually annotated data. However, these approaches tend to overlook dense crowd scenarios, where the challenges of automation become more pronounced due to the massiveness, noisiness, and inaccuracy of the tracking outputs, resulting in high computational costs. To address these challenges, we propose and extensively evaluate a novel cluster-based approach that groups individuals based on similar attributes over time, enabling faster execution through accurate group summarisation. Our plug-and-play method can be combined with existing trajectory predictors by using our output centroid in place of their pedestrian input. We evaluate our proposed method on several challenging dense crowd scenes. We demonstrated that our approach leads to faster processing and lower memory usage when compared with state-of-the-art methods, while maintaining the accuracy

Antonius Bima Murti Wijaya, Paul Henderson, Marwa Mahmoud

University of Glasgow, Glasgow G12 8QQ, United Kingdom

Pedestrian Trajectory Prediction Clustering

Mar 18, 2026

Learning-Augmented Algorithms for $k$ -median via Online Learning

The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic

k

-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed

k

-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

Anish Hebbar, Rong Ge, Amit Kumar +1

Duke University · IIT Delhi

Learning-Augmented Algorithms Clustering Online Learning

Mar 18, 2026

Weight Clustering Reveals the Importance of Relative Rank in Large Language Models

Large language models (LLMs) contain billions of parameters, but many exact weight values are not essential. We apply scalar

K

-means clustering to pretrained models, replacing each weight matrix with only 16--64 shared values. For Llama~3.1-8B-Instruct and SmolLM2-135M, this preserves strong accuracy without retraining, providing a simple way to compress LLMs on disk. Fine-tuning only the cluster centroids further recovers 30--40% of the remaining accuracy loss. Using clustering as an analysis tool, we then keep the cluster assignments fixed and perturb only the shared values, to study which of their properties matter most. We find that preserving their relative rank (which connections are stronger or weaker than others) is more important than preserving their exact magnitudes. Breaking this ordering greatly increases perplexity, while changing the values but keeping the ordering causes little loss in many middle and late layers. However, rank preservation alone is not sufficient. Model performance also depends on maintaining the variance of the reconstructed weights, while early layers remain more sensitive; perturbing the cluster assignments themselves shows that their spatial geometry is also load-bearing. We observe the same behavior across four LLMs from two architecture families. These results suggest that the ordering of weights, together with their overall variance, plays a central role in LLM compression and robustness.

Borja Aizpurua, Sukhbinder Singh, Román Orús

Multiverse Computing, San Sebasti´an, Spain · Department of Basic Sciences, Tecnun - University of Navarra, San Sebasti´an, Spain · Multiverse Computing, Toronto, Ontario, Canada +2

LLM Compression LLM Quantization Clustering

Mar 18, 2026

Discovering Decoupled Functional Modules in Large Language Models

Understanding the internal functional organization of Large Language Models (LLMs) is crucial for improving their trustworthiness and performance. However, how LLMs organize different functions into modules remains highly unexplored. To bridge this gap, we formulate a functional module discovery problem and propose an Unsupervised LLM Cross-layer MOdule Discovery (ULCMOD) framework that simultaneously disentangles the large set of neurons in the entire LLM into modules while discovering the topics of input samples related to these modules. Our framework introduces a novel objective function and an efficient Iterative Decoupling (IterD) algorithm. Extensive experiments show that our method discovers high-quality, disentangled modules that capture more meaningful semantic information and achieve superior performance in various downstream tasks. Moreover, our qualitative analysis reveals that the discovered modules show semantic coherence, correspond to interpretable specializations, and a clear spatial and hierarchical organization within the LLM. Our work provides a novel tool for interpreting the functional modules of LLMs, filling a critical blank in LLM's interpretability research.

Yanke Yu, Jin Li, Ying Sun +3

Thrust of AI, Hong Kong University of Science and Technology (Guangzhou) · Huawei Technologies Ltd.

LLM Interpretability Circuits in Language Models Clustering

Mar 17, 2026

Behavior-Centric Extraction of Scenarios from Highway Traffic Data and their Domain-Knowledge-Guided Clustering using CVQ-VAE

Approval of ADS depends on evaluating its behavior within representative real-world traffic scenarios. A common way to obtain such scenarios is to extract them from real-world data recordings. These can then be grouped and serve as basis on which the ADS is subsequently tested. This poses two central challenges: how scenarios are extracted and how they are grouped. Existing extraction methods rely on heterogeneous definitions, hindering scenario comparability. For the grouping of scenarios, rule-based or ML-based methods can be utilized. However, while modern ML-based approaches can handle the complexity of traffic scenarios, unlike rule-based approaches, they lack interpretability and may not align with domain-knowledge. This work contributes to a standardized scenario extraction based on the Scenario-as-Specification concept, as well as a domain-knowledge-guided scenario clustering process. Experiments on the highD dataset demonstrate that scenarios can be extracted reliably and that domain-knowledge can be effectively integrated into the clustering process. As a result, the proposed methodology supports a more standardized process for deriving scenario categories from highway data recordings and thus enables a more efficient validation process of automated vehicles.

Niklas Roßberg, Sinan Hasirlioglu, Mohamed Essayed Bouzouraa +2

Technische Hochschule Ingolstadt, 85049 Ingolstadt, Germany · AUDI AG, 85045 Ingolstadt, Germany · Technische Universität München, 80333 München, Germany

Intelligent Transportation Systems Clustering

Mar 16, 2026

Orthogonal Subspace Clustering: Enhancing High-Dimensional Data Analysis through Adaptive Dimensionality Reduction and Efficient Clustering

This paper presents Orthogonal Subspace Clustering (OSC), an innovative method for high-dimensional data clustering. We first establish a theoretical theorem proving that high-dimensional data can be decomposed into orthogonal subspaces in a statistical sense, whose form exactly matches the paradigm of Q-type factor analysis. This theorem lays a solid mathematical foundation for dimensionality reduction via matrix decomposition and factor analysis. Based on this theorem, we propose the OSC framework to address the "curse of dimensionality" -- a critical challenge that degrades clustering effectiveness due to sample sparsity and ineffective distance metrics. OSC integrates orthogonal subspace construction with classical clustering techniques, introducing a data-driven mechanism to select the subspace dimension based on cumulative variance contribution. This avoids manual selection biases while maximizing the retention of discriminative information. By projecting high-dimensional data into an uncorrelated, low-dimensional orthogonal subspace, OSC significantly improves clustering efficiency, robustness, and accuracy. Extensive experiments on various benchmark datasets demonstrate the effectiveness of OSC, with thorough analysis of evaluation metrics including Cluster Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI) highlighting its advantages over existing methods.

Qing-Yuan Wen, Da-Qing Zhang

School of Science, University of Science and Technology Liaoning, Anshan, Liaoning Province, 114051, PR China

Clustering Dimensionality Reduction

Mar 15, 2026

$K-$ means with learned metrics

We study the Fréchet

k-

means of a metric measure space when both the measure and the distance are unknown and have to be estimated. We prove a general result that states that the

k-

means are continuous with respect to the measured Gromov-Hausdorff topology. In this situation, we also prove a stability result for the Voronoi clusters they determine. We do not assume uniqueness of the set of

k-

means, but when it is unique, the results are stronger. This framework provides a unified approach to proving consistency for a wide range of metric learning procedures. As concrete applications, we obtain new consistency results for several important estimators that were previously unestablished, even when

k=1

. These include

k-

means based on: (i) Isomap and Fermat geodesic distances on manifolds, (ii) difussion distances, (iii) Wasserstein distances computed with respect to learned ground metrics. Finally, we consider applications beyond the statistical inference paradigm like (iv) first passage percolation and (v) discrete approximations of length spaces.

Pablo Groisman, Matthieu Jonckheere, Jordan Serres +1

Clustering Metric Learning

Mar 13, 2026

Federated Hierarchical Clustering with Automatic Selection of Optimal Cluster Numbers

Federated Clustering (FC) is an emerging and promising solution in exploring data distribution patterns from distributed and privacy-protected data in an unsupervised manner. Existing FC methods implicitly rely on the assumption that clients are with a known number of uniformly sized clusters. However, the true number of clusters is typically unknown, and cluster sizes are naturally imbalanced in real scenarios. Furthermore, the privacy-preserving transmission constraints in federated learning inevitably reduce usable information, making the development of robust and accurate FC extremely challenging. Accordingly, we propose a novel FC framework named Fed-

k^*

-HC, which can automatically determine an optimal number of clusters

k^*

based on the data distribution explored through hierarchical clustering. To obtain the global data distribution for

k^*

determination, we let each client generate micro-subclusters. Their prototypes are then uploaded to the server for hierarchical merging. The density-based merging design allows exploring clusters of varying sizes and shapes, and the progressive merging process can self-terminate according to the neighboring relationships among the prototypes to determine

k^*

. Extensive experiments on diverse datasets demonstrate the FC capability of the proposed Fed-

k^*

-HC in accurately exploring a proper number of clusters.

Yue Zhang, Chuanlong Qiu, Xinfa Liao +1

School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, China · School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China · Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China

Cluster Number Estimation Clustering Hierarchical Clustering

Mar 12, 2026

In the LLM era, Word Sense Induction remains unsolved

In the absence of sense-annotated data, word sense induction (WSI) is a compelling alternative to word sense disambiguation, particularly in low-resource or domain-specific settings. In this paper, we emphasize methodological problems in current WSI evaluation. We propose an evaluation on a SemCor-derived dataset, respecting the original corpus polysemy and frequency distributions. We assess pre-trained embeddings and clustering algorithms across parts of speech, and propose and evaluate an LLM-based WSI method for English. We evaluate data augmentation sources (LLM-generated, corpus and lexicon), and semi-supervised scenarios using Wiktionary for data augmentation, must-link constraints, number of clusters per lemma. We find that no unsupervised method (whether ours or previous) surpasses the strong "one cluster per lemma" heuristic (1cpl). We also show that (i) results and best systems may vary across POS, (ii) LLMs have troubles performing this task, (iii) data augmentation is beneficial and (iv) capitalizing on Wiktionary does help. It surpasses previous SOTA system on our test set by 3.3%. WSI is not solved, and calls for a better articulation of lexicons and LLMs' lexical semantics capabilities.

Anna Mosolova, Marie Candito, Carlos Ramisch

Université Paris Cité, CNRS, LLF, Paris, France · Aix Marseille Univ, CNRS, LIS, Marseille, France

Clustering Distributional Semantics

Mar 12, 2026

Unsupervised LiDAR-Based Multi-UAV Detection and Tracking Under Extreme Sparsity

Non-repetitive solid-state LiDAR scanning leads to an extremely sparse measurement regime for detecting airborne UAVs: a small quadrotor at 10-25 m typically produces only 1-2 returns per scan, which is far below the point densities assumed by most existing detection approaches and inadequate for robust multi-target data association. We introduce an unsupervised, LiDAR-only pipeline that addresses both detection and tracking without the need for labeled training data. The detector integrates range-adaptive DBSCAN clustering with a three-stage temporal consistency check and is benchmarked on real-world air-to-air flight data under eight different parameter configurations. The best setup attains 0.891 precision, 0.804 recall, and 0.63 m RMSE, and a systematic minPts sweep verifies that most scans contain at most 1-2 target points, directly quantifying the sparsity regime. For multi-target tracking, we compare deterministic Hungarian assignment with joint probabilistic data association (JPDA), each coupled with Interacting Multiple Model filtering, in four simulated scenarios with increasing levels of ambiguity. JPDA cuts identity switches by 64% with negligible impact on MOTA, demonstrating that probabilistic association is advantageous when UAV trajectories approach one another closely. A two-environment evaluation strategy, combining real-world detection with RTK-GPS ground truth and simulation-based tracking with identity-annotated ground truth, overcomes the limitations of GNSS-only evaluation at inter-UAV distances below 2 m.

Nivand Khosravi, Rodrigo Ventura, Meysam Basiri

Instituto Superior T´ecnico, University of Lisbon, Lisbon, Portugal

UAV Detection Aerial Object Detection Multi-Object Tracking Lidar-Based 3D Object Detection Data Association Clustering

Mar 11, 2026

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions

In this paper, we investigate the learning-augmented

k

-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate

α\in [0,1)

. This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented

k

-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.

Kangke Cheng, Shihong Song, Guanlin Mo +1

University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK

Clustering Learning-Augmented Algorithms

Mar 11, 2026

TractoRC: A Unified Probabilistic Learning Framework for Joint Tractography Registration and Clustering

Diffusion MRI tractography enables in vivo reconstruction of white matter (WM) pathways. Two key tasks in tractography analysis include: 1) tractogram registration that aligns streamlines across individuals, and 2) streamline clustering that groups streamlines into compact fiber bundles. Although both tasks share the goal of capturing geometrically similar structures to characterize consistent WM organization, they are typically performed independently. In this work, we propose TractoRC, a unified probabilistic framework that jointly performs tractogram registration and streamline clustering within a single optimization scheme, enabling the two tasks to leverage complementary information. TractoRC learns a latent embedding space for streamline points, which serves as a shared representation for both tasks. Within this space, both tasks are formulated as probabilistic inference over structural representations: registration learns the distribution of anatomical landmarks as probabilistic keypoints to align tractograms across subjects, and clustering learns streamline structural prototypes that capture geometric similarity to form coherent streamline clusters. To support effective learning of this shared space, we introduce a transformation-equivariant self-supervised strategy to learn geometry-aware and transformation-invariant embeddings. Experiments demonstrate that jointly optimizing registration and clustering significantly improves performance in both tasks over state-of-the-art methods that treat them independently. Code will be made publicly available at https://github.com/yishengpoxiao/TractoRC .

Yijie Li, Xi Zhu, Junyi Wang +3

University of Electronic Science and Technology of China, Chengdu, China · Nanjing University of Science and Technology, Nanjing, China · Harvard Medical School and Brigham and Women’s Hospital, Boston. USA

Clustering Diffusion MRI Geometric Representation Learning

Mar 11, 2026

MultiwayPAM: Multiway Partitioning Around Medoids for LLM-as-a-Judge Score Analysis

LLM-as-a-Judge is a flexible framework for text evaluation, which allows us to obtain scores for the quality of a given text from various perspectives by changing the prompt template. Two main challenges in using LLM-as-a-Judge are computational cost of inference using a large language model (LLM), especially when evaluating a large number of instances, and inherent bias of an LLM evaluator. To address these issues and reveal the structure of score bias caused by an LLM evaluator, we propose to apply a tensor clustering method to a given LLM-as-a-Judge score tensor, whose entries are the scores for different combinations of questions, answerers, and evaluators. Specifically, we develop a new tensor clustering method MultiwayPAM, with which we can simultaneously estimate the cluster membership and the medoids for each mode of a given data tensor. By observing the medoids obtained by MultiwayPAM, we can gain knowledge about the membership of each question/answerer/evaluator cluster. We experimentally show the effectiveness of MultiwayPAM by applying it to the score tensors for two practical datasets.

Chihiro Watanabe, Jingyu Sun

NTT Computer and Data Science Laboratories, 3-9-11, Midori-cho, Musashino-shi, Tokyo, Japan

LLM-as-a-Judge Clustering Language Model Bias Evaluation Bias in LLM-as-a-Judge

Mar 6, 2026

AdaBox: Adaptive Density-Based Box Clustering with Parameter Generalization

Density-based clustering algorithms like DBSCAN and HDBSCAN are foundational tools for discovering arbitrarily shaped clusters, yet their practical utility is undermined by acute hyperparameter sensitivity -- parameters tuned on one dataset frequently fail to transfer to others, requiring expensive re-optimization for each deployment. We introduce AdaBox (Adaptive Density-Based Box Clustering), a grid-based density clustering algorithm designed for robustness across diverse data geometries. AdaBox features a six-parameter design where parameters capture cluster structure rather than pairwise point relationships. Four parameters are inherently scale-invariant, one self-corrects for sampling bias, and one is adjusted via a density scaling stage, enabling reliable parameter transfer across 30-200x scale factors. AdaBox processes data through five stages: adaptive grid construction, liberal seed initialization, iterative growth with graduation, statistical cluster merging, and Gaussian boundary refinement. Comprehensive evaluation across 111 datasets demonstrates three key findings: (1) AdaBox significantly outperforms DBSCAN and HDBSCAN across five evaluation metrics, achieving the best score on 78% of datasets with p < 0.05; (2) AdaBox uniquely exhibits parameter generalization. Protocol A (direct transfer to 30-100x larger datasets) shows AdaBox maintains performance while baselines collapse. (3) Ablation studies confirm the necessity of all five architectural stages for maintaining robustness.

Ahmed Elmahdi

Independent Researcher

Density-Based Clustering Clustering Unsupervised Clustering Cross-Dataset Generalization

Mar 6, 2026

Single-pass Possibilistic Clustering with Damped Window Footprints

Streaming clustering is a domain that has become extremely relevant in the age of big data, such as in network traffic analysis or in processing continuously-running sensor data. Furthermore, possibilistic models offer unique benefits over approaches from the literature, especially with the introduction of a "fuzzifier" parameter that controls how quickly typicality degrades as one gets further from cluster centers. We propose a single-pass possibilistic clustering (SPC) algorithm that is effective and easy to apply to new datasets. Key contributions of SPC include the ability to model non-spherical clusters, closed-form footprint updates over arbitrarily sized damped windows, and the employment of covariance union from the multiple hypothesis tracking literature to merge two cluster mean and covariance estimates. SPC is validated against five other streaming clustering algorithm on the basis of cluster purity and normalized mutual information.

Jeffrey Dale, James Keller, Aquila Galusha

Electrical Engineering and Computer Science Department, University of Missouri, Columbia, MO 65211

Clustering Streaming Algorithms

Mar 6, 2026

Cluster-R1: Large Reasoning Models Are Instruction-following Clustering Agents

General-purpose embedding models excel at recognizing semantic similarities but fail to capture the characteristics of texts specified by user instructions. In contrast, instruction-tuned embedders can align embeddings with textual instructions yet cannot autonomously infer latent corpus structures, such as determining the optimal number of clusters. To address both limitations, we reframe instruction-following clustering as a generative task and train large reasoning models (LRMs) as autonomous clustering agents. Our reasoning-driven training pipeline enables LRMs to interpret high-level clustering instructions and then infer the corresponding latent groupings. To evaluate this paradigm, we introduce ReasonCluster, a comprehensive benchmark comprising 28 diverse tasks spanning daily dialogue, legal cases, and financial reports. Experiments across diverse datasets and clustering scenarios show that our approach consistently outperforms strong embedding-based methods and LRM baselines, demonstrating that explicit reasoning fosters more faithful and interpretable instruction-based clustering.

Peijun Qing, Puneet Mathur, Nedim Lipka +5

Dartmouth College, USA · Adobe Research, San Jose, USA

Clustering Unsupervised Clustering Large Reasoning Models

Mar 5, 2026

GALACTIC: Global and Local Agnostic Counterfactuals for Time-series Clustering

Time-series clustering is a fundamental tool for pattern discovery, yet existing explainability methods, primarily based on feature attribution or metadata, fail to identify the transitions that move an instance across cluster boundaries. While Counterfactual Explanations (CEs) identify the minimal temporal perturbations required to alter the prediction of a model, they have been mostly confined to supervised settings. This paper introduces GALACTIC, the first unified framework to bridge local and global counterfactual explainability for unsupervised time-series clustering. At instance level (local), GALACTIC generates perturbations via a cluster-aware optimization objective that respects the target and underlying cluster assignments. At cluster level (global), to mitigate cognitive load and enhance interpretability, we formulate a representative CE selection problem. We propose a Minimum Description Length (MDL) objective to extract a non-redundant summary of global explanations that characterize the transitions between clusters. We prove that our MDL objective is supermodular, which allows the corresponding MDL reduction to be framed as a monotone submodular set function. This enables an efficient greedy selection algorithm with provable

(1-1/e)

approximation guarantees. Extensive experimental evaluation on the UCR Archive demonstrates that GALACTIC produces significantly sparser local CEs and more concise global summaries than state-of-the-art baselines adapted for our problem, offering the first unified approach for interpreting clustered time-series through counterfactuals.

Christos Fragkathoulas, Eleni Psaroudaki, Themis Palpanas +1

University of Ioannina Ioannina, Greece · Archimedes, Athena Research Center Athens, Greece · Université Paris Cité, LIPADE, F-75006 Paris, France

Counterfactual Explanations Time Series Clustering Clustering

Mar 5, 2026

Synchronization-based clustering on the unit hypersphere

Clustering on the unit hypersphere is a fundamental problem in various fields, with applications ranging from gene expression analysis to text and image classification. Traditional clustering methods are not always suitable for unit sphere data, as they do not account for the geometric structure of the sphere. We introduce a novel algorithm for clustering data represented as points on the unit sphere

\mathbf{S}^{d-1}

. Our method is based on the

d

-dimensional generalized Kuramoto model. The effectiveness of the introduced method is demonstrated on synthetic and real-world datasets. Results are compared with some of the traditional clustering methods, showing that our method achieves similar or better results in terms of clustering accuracy.

Zinaid Kapić, Aladin Crnkić, Goran Mauša

Faculty of Technical Engineering, University of Bihać, Bihać

Kuramoto Model Clustering Unsupervised Clustering

Mar 4, 2026

K-Means as the Zero-Temperature Limit of Normalized RBF Assignments: Rates, Trajectories, and Exact Recovery with Entmax

K-Means is usually treated as a discrete procedure outside gradient-based learning, whereas normalized radial basis function (RBF) layers are smooth. We make precise the sense in which K-Means is the zero-temperature limit of such a layer. Relaxing the K-Means assignments to the simplex with a Shannon entropy penalty yields the normalized Gaussian RBF responsibilities and a reduced objective

F_σ

with

0\le J-F_σ\le 2nσ^2\log k

, so

F_σ

Γ

-converges to the K-Means distortion

J

. We keep four levels of statement apart. For the objective, minimal values and minimizers converge, and above the critical temperature

σ^2=λ_{\max}

all centroids at the mean form a strict local minimizer. For optimization, alternating minimization is a preconditioned gradient method on

F_σ

whose hard limit is Lloyd's algorithm. For one update, under a margin

Δ_{\min}>0

, the soft centroid map approaches Lloyd's at rate

O(e^{-Δ_{\min}/2σ^2})

. For fixed points and trajectories, every nondegenerate Lloyd fixed point has a nearby soft local minimizer, and soft iterates keep Lloyd's partitions while Lloyd's path keeps a margin. With the Tsallis entropy of order 3/2, Entmax-1.5 recovers the hard assignments, the Lloyd update and, along a path with margin, Lloyd's trajectory exactly for

σ\le\sqrt{Δ_{\min}}/2

, a sharp threshold. Experiments on sixteen datasets confirm every bound, rate and threshold, and the trajectory statements at the edge of their hypotheses. As a differentiable K-Means term,

F_σ

shows the predicted effects: its gradients do not vanish at low temperature, its closed-form centroid update needs no learning rate, a fixed temperature crosses the critical one as representations contract, and soft responsibilities keep a vector-quantized codebook in use.

Felipe de Jesus Felix Arredondo, Manuel Alejandro Ucan Puc, Carlos Astengo Nouguez

School of Engineering and Sciences, Tecnológico de Monterrey, Monterrey, Mexico · School of Engineering and Sciences, Tecnológico de Monterrey, Guadalajara, Mexico

Clustering Radial Basis Function Networks

Mar 3, 2026

Transport Clustering: Solving Low-Rank Optimal Transport via Clustering

Optimal transport (OT) finds a least cost transport plan between two probability distributions using a cost matrix defined on pairs of points. Unlike standard OT, which infers unstructured pointwise mappings, low-rank optimal transport explicitly constrains the rank of the transport plan to infer latent structure. This improves statistical stability and robustness, yields sharper parametric rates for estimating Wasserstein distances adaptive to the intrinsic rank, and generalizes

K

-means to co-clustering. These advantages, however, come at the cost of a non-convex and NP-hard optimization problem. We introduce transport clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a clustering problem on correspondences obtained from a full-rank

\textit{transport registration}

step. We prove that this reduction yields polynomial-time, constant-factor approximation algorithms for low-rank OT: specifically, a

(1+γ)

approximation for negative-type metrics and a

(1+γ+\sqrt{2γ}\,)

approximation for kernel costs, where

γ\in [0,1]

denotes the approximation ratio of the optimal full-rank solution relative to the low-rank optimal. Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.

Henri Schmidt, Peter Halmos, Ben Raphael

Department of Computer Science, Princeton University, NJ, USA.

Optimal Transport Clustering

Mar 3, 2026

The elbow statistic: Multiscale clustering statistical significance

Selecting the number of clusters remains a fundamental challenge in unsupervised learning. Existing approaches typically focus on identifying a single "optimal" partition, often overlooking statistically meaningful structure present across multiple resolutions. We introduce ElbowSig, a general inferential framework for assessing clustering structure over a range of resolutions. The method formalizes the elbow heuristic by defining a normalized discrete curvature statistic based on the sequence of within-cluster heterogeneity values, and evaluates its significance relative to a null distribution of unstructured data. This yields hypothesis tests across resolutions, enabling simultaneous inference at multiple clustering scales. We derive the asymptotic behavior of the null statistic in both large-sample and high-dimensional regimes, characterizing its limiting form and variability. Because it depends only on the heterogeneity sequence, ElbowSig is compatible with a wide range of clustering algorithms, including hard, fuzzy, and model-based methods. Experiments on synthetic and real datasets show that the procedure controls Type-I error under unstructured data while providing power to detect multiscale organization, revealing structure that is often missed by single-resolution selection criteria.

Francisco J. Perez-Reche

School of Natural and Computing Sciences, University of Aberdeen, Fraser Noble Building, AB24 3UE, United Kingdom

Cluster Number Estimation Clustering Statistical Hypothesis Testing

Mar 3, 2026

Scalable Posterior Uncertainty for Flexible Density-Based Clustering

Density-based clustering is a well-established framework that defines clusters through topological or geometric features of the data-generating density, yielding flexible procedures that have proven effective on large and complex datasets. We address the problem of obtaining scalable Bayesian-style uncertainty quantification by combining density-based clustering with martingale posterior distributions. Density uncertainty is first quantified through a fully parallelized predictive resampling scheme driven by model score functions, naturally accommodating modern differentiable density estimators such as normalizing flows. Posterior samples of the clustering are then obtained by applying density-based clustering to each random density sampled from the martingale posterior, enabling inference on any clustering-related quantity. Casting the estimand as a density functional also enables a rigorous frequentist convergence analysis. We illustrate the method through applications to image and single-cell RNA sequencing data, where it recovers meaningful clustering structures, including the assignment of previously unseen data and biologically interpretable cell grouping, while running in minutes on a single GPU.

Nicola Bariletto, Stephen G. Walker

Department of Statistics and Data Sciences, UT Austin

Density-Based Clustering Clustering Uncertainty Quantification Bayesian Inference

Mar 3, 2026

Incremental Graph Construction Enables Robust Spectral Clustering of Texts

Neighborhood graphs are a critical but often fragile step in spectral clustering of text embeddings. On realistic text datasets, standard

k

-NN graphs can contain many disconnected components at practical sparsity levels (small

k

), making spectral clustering degenerate and sensitive to hyperparameters. We introduce a simple incremental

k

-NN graph construction that preserves connectivity by design: each new node is linked to its

k

nearest previously inserted nodes, which guarantees a connected graph for any

k

. We provide an inductive proof of connectedness and discuss implications for incremental updates when new documents arrive. We validate the approach on spectral clustering of SentenceTransformer embeddings using Laplacian eigenmaps across six clustering datasets from the Massive Text Embedding Benchmark. Compared to standard

k

-NN graphs, our method outperforms in the low-

k

regime where disconnected components are prevalent, and matches standard

k

-NN at larger

k

.

Marko Pranjić, Boshko Koloski, Nada Lavrač +2

Joˇzef Stefan Institute and International Postgraduate School, Ljubljana, Slovenia. · University of Ljubljana, Faculty of Computer and Information Science, Ljubljana, Slovenia.

Text Clustering Clustering Spectral Clustering k-Nearest Neighbors

Mar 3, 2026

Learning Unified Distance Metric for Heterogeneous Attribute Data Clustering

Datasets composed of numerical and categorical attributes (also called mixed data hereinafter) are common in real clustering tasks. Differing from numerical attributes that indicate tendencies between two concepts (e.g., high and low temperature) with their values in well-defined Euclidean distance space, categorical attribute values are different concepts (e.g., different occupations) embedded in an implicit space. Simultaneously exploiting these two very different types of information is an unavoidable but challenging problem, and most advanced attempts either encode the heterogeneous numerical and categorical attributes into one type, or define a unified metric for them for mixed data clustering, leaving their inherent connection unrevealed. This paper, therefore, studies the connection among any-type of attributes and proposes a novel Heterogeneous Attribute Reconstruction and Representation (HARR) learning paradigm accordingly for cluster analysis. The paradigm transforms heterogeneous attributes into a homogeneous status for distance metric learning, and integrates the learning with clustering to automatically adapt the metric to different clustering tasks. Differing from most existing works that directly adopt defined distance metrics or learn attribute weights to search clusters in a subspace. We propose to project the values of each attribute into unified learnable multiple spaces to more finely represent and learn the distance metric for categorical data. HARR is parameter-free, convergence-guaranteed, and can more effectively self-adapt to different sought number of clusters

k

. Extensive experiments illustrate its superiority in terms of accuracy and efficiency.

Yiqun Zhang, Mingjie Zhao, Yizhou Chen +2

School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, 510006, Guangdong, China · Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, Xiamen, 361102, Fujian, China · Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China

Clustering Unsupervised Clustering Metric Learning

Mar 3, 2026

Learning Order Forest for Qualitative-Attribute Data Clustering

Clustering is a fundamental approach to understanding data patterns, wherein the intuitive Euclidean distance space is commonly adopted. However, this is not the case for implicit cluster distributions reflected by qualitative attribute values, e.g., the nominal values of attributes like symptoms, marital status, etc. This paper, therefore, discovered a tree-like distance structure to flexibly represent the local order relationship among intra-attribute qualitative values. That is, treating a value as the vertex of the tree allows to capture rich order relationships among the vertex value and the others. To obtain the trees in a clustering-friendly form, a joint learning mechanism is proposed to iteratively obtain more appropriate tree structures and clusters. It turns out that the latent distance space of the whole dataset can be well-represented by a forest consisting of the learned trees. Extensive experiments demonstrate that the joint learning adapts the forest to the clustering task to yield accurate results. Comparisons of 10 counterparts on 12 real benchmark datasets with significance tests verify the superiority of the proposed method.

Mingjie Zhao, Sen Feng, Yiqun Zhang +3

School of Computer Science and Technology, Guangdong University of Technology, Guangzhou, China · Department of Computer Science, Hong Kong Baptist University, Hong Kong, China · Guangdong Laboratory of Artiﬁcial Intelligence and Digital Economy (SZ), Shenzhen, China +3

Clustering Metric Learning

Feb 27, 2026

Unsupervised Baseline Clustering and Incremental Adaptation for IoT Device Traffic Profiling

The growth and heterogeneity of IoT devices create security challenges where static identification models can degrade as traffic evolves. This paper presents a two-stage, flow-feature-based pipeline for unsupervised IoT device traffic profiling and incremental model updating, evaluated on selected long-duration captures from the Deakin IoT dataset. For baseline profiling, density-based clustering (DBSCAN) isolates a substantial outlier portion of the data and produces the strongest alignment with ground-truth device labels among tested classical methods (NMI 0.78), outperforming centroid-based clustering on cluster purity. For incremental adaptation, we evaluate stream-oriented clustering approaches and find that BIRCH supports efficient updates (0.13 seconds per update) and forms comparatively coherent clusters for a held-out novel device (purity 0.87), but with limited capture of novel traffic (share 0.72) and a measurable trade-off in known-device accuracy after adaptation (0.71). Overall, the results highlight a practical trade-off between high-purity static profiling and the flexibility of incremental clustering for evolving IoT environments.

Sean M. Alderman, John D. Hastings

The Beacom College of Computer & Cyber Sciences, Dakota State University, Madison, SD, USA

Internet of Things Clustering Unsupervised Clustering

Feb 27, 2026

Universal NP-Hardness of Clustering under General Utilities

Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.

Angshul Majumdar

Indraprastha Institute of Information Technology, New Delhi, India

Clustering Unsupervised Clustering Combinatorial Optimization

Feb 26, 2026

Neural Operators Can Discover Functional Clusters

Operator learning is reshaping scientific computing by amortizing inference across infinite families of problems. While neural operators (NOs) are increasingly well understood for regression, far less is known for classification and its unsupervised analogue: clustering. We prove that sample-based neural operators can learn any finite collection of classes in an infinite-dimensional reproducing kernel Hilbert space, even when the classes are neither convex nor connected, under mild kernel sampling assumptions. Our universal clustering theorem shows that any

K

closed classes can be approximated to arbitrary precision by NO-parameterized classes in the upper Kuratowski topology on closed sets, a notion that can be interpreted as disallowing false-positive misclassifications. Building on this, we develop an NO-powered clustering pipeline for functional data and apply it to unlabeled families of ordinary differential equation (ODE) trajectories. Discretized trajectories are lifted by a fixed pre-trained encoder into a continuous feature map and mapped to soft assignments by a lightweight trainable head. Experiments on diverse synthetic ODE benchmarks show that the resulting practical SNO recovers latent dynamical structure in regimes where classical methods fail, providing evidence consistent with our universal clustering theory.

Yicen Li, Jose Antonio Lara Benitez, Ruiyang Hong +3

McMaster University and the Vector Institute, Main St., Hamilton, L8S 4L8, Ontario, Canada · Rice University, Main St., Houston, 77005, Texas, United States

Clustering Unsupervised Clustering Neural Operators Scientific ML