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

347 papers33 papers in the last four weeks, up 18% on the four weeks before. 0.2% of all new papers.

Jul 17, 2026

Cluster-Aware Matching via Laplacian Optimal Transport

In many applications of matching, the point clouds to be matched are not merely unstructured sets of points but rather samples from distributions with an intrinsic cluster structure. In such cases, as individual points are often interchangeable within a coherent region, finding a robust region-to-region alignment is more desirable than establishing a precise point-to-point correspondence. To this end, we propose a novel approach for cluster-aware matching based on Laplacian Optimal Transport (LapOT). The key idea is to regularize the optimal transport problem with quadratic Laplacian terms constructed from similarity graphs of the point clouds, which encourages the optimal coupling to respect the cluster structure of both point sets. We also introduce Refined Simultaneous Clustering (RSC), a method that leverages the cluster-aware coupling obtained from LapOT to produce consistent partitions across the point sets, which can overcome the limitations of independent clustering and yield more stable and interpretable results. We demonstrate the effectiveness of our approach through theoretical analysis and empirical experiments, showing that LapOT indeed produces cluster-aware matching that leads to more consistent and meaningful alignments between point clouds.

Gabriel Samberg, YoonHaeng Hur, Yuehaw Khoo +1

Department of Applied Mathematics, Tel Aviv University · Department of Statistics, Columbia University · Department of Statistics, University of Chicago

Clustering Graph Matching Point Cloud Registration Optimal Transport

Jul 17, 2026

Data-Native Global Optimization for Big Data K-means Clustering

Big data clustering remains challenging: the Minimum Sum-of-Squares Clustering (MSSC) problem underlying K-means is NP-hard, and existing methods either reach poor local minima or require prohibitive metaheuristic hybrids. We target arbitrarily tall data: a fixed feature space may contain arbitrarily many, possibly infinitely many, observations, while the algorithm accesses only finite random samples. We propose Big-means++, an algorithm achieving scalability and global-search quality by curating inputs to MSSC optimization on big data. It orchestrates local K-means refinements into a data-native global search for big data clustering. Rather than optimizing the full-data MSSC objective, Big-means++ traverses sample-induced surrogate landscapes. Each sample defines a distinct empirical MSSC approximation with a perturbed local-optimum structure, turning sample-to-sample variation into a global-search mechanism. Unlike Big-means, a flowing-incumbent strategy propagates centroid state across empirical landscapes through K-means refinements on fresh samples without rollback to a best-so-far solution. This increases mobility and favors stable, high-quality configurations across approximations of the full-data structure. A new shaking mechanism varies sample size geometrically, broadening the surrogate landscapes explored across resolution scales, accounting for cluster imbalance, and improving solution quality. A competitive multi-agent system asynchronously explores independent sampled landscapes, transforming diverse stochastic trajectories into collective search intelligence. Automatic convergence detection stops each agent after attaining a high-quality solution but before further search risks degrading it, while providing a universal speed-quality control. Experiments on 22 datasets against 11 competing algorithms demonstrate the effectiveness, efficiency, and robustness of Big-means++.

Ravil Mussabayev, Rustam Mussabayev, Zukhra Yerdaliyeva +1

AI Research Lab, Satbayev University, Almaty, 050000, Kazakhstan · Laboratory for Analysis and Modeling of Information Processes, Institute of Information and Computational Technologies, Almaty, 050010, Kazakhstan

Clustering Unsupervised Clustering Global Optimization

Jul 16, 2026

Measuring Spatial Clustering via Metropolis-Hastings Diffusion Distance

We propose a novel measure of the discrepancy between two probability distributions

f

and

g

on a graph - which we call the diffusion distance - that measures the rate of convergence of

f

to

g

under a graph-constrained Markov chain with stationary distribution

g

. As a default choice for this Markov chain, we use the Metropolis-Hastings transition matrix targeting

g

with proposals given by a random walk on the graph. Our primary case of interest is when the second distribution

g

is uniform, in which case the diffusion distance becomes a measure of spatial clustering in

f

. Used in this way, (Metropolis-Hastings) diffusion distance to uniformity extends Moran's

I

-type measures of spatial autocorrelation by incorporating global graph geometry rather than just local patterns. Indeed, Moran's

I

, the most well-known measure of spatial autocorrelation, can be viewed as a one-step heuristic for diffusion distance, so long as specific spatial weights are used. We establish theoretical bounds and a stability result for our measure, connecting it to graph spectra and optimal transport. We then turn our attention to outlining a statistical test for spatial clustering using diffusion distance. Under permutation null models, we derive high-probability bounds on diffusion distance underpinned by exact spectral formulas for convergence of distributions, enabling an efficient statistical test for spatial clustering on large datasets. We empirically compare diffusion distance to Moran's

I

both as a numerical measure and as a statistical test. We show that diffusion distance exhibits higher power on synthetic data using a stochastic block model. Empirical analysis of Black population distributions for 100 U.S. cities shows that diffusion distance detects subtle differences in urban segregation patterns that Moran's

I

does not.

Thomas Weighill, Chidinma Williams

Department of Mathematics and Statistics, University of North Carolina at Greensboro, Greensboro, NC 27402

Clustering Graph Diffusion Statistical Hypothesis Testing

Jul 16, 2026

Counterfactuals for Feature-Weighted Clustering

Counterfactual explanations provide local, interpretable insight by identifying changes to an input that would alter its assigned outcome. Although well established in supervised learning, their extension to clustering is less direct, since cluster assignments are unlabeled and governed by the geometry of the partition. This paper introduces VoICE, a Voronoi-Induced Counterfactual Explainability framework for feature-weighted

k

-means clustering. Rather than treating cluster change as a crossing of a single pairwise centroid boundary, VoICE formulates counterfactual generation as projection onto the full weighted Voronoi region of a target cluster, incorporating feature weights directly into both the clustering geometry and the counterfactual objective to yield least-cost and parsimonious explanations under actionability constraints. Target regions are further intersected with data-derived bounds and homothetically contracted towards their centroids, limiting extrapolation and boundary sensitivity. VoICE consistently produces valid target-cluster membership, across several benchmark datasets, where the leading pairwise baseline does not.

Richard J. Fawley, Renato Cordeiro de Amorim

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

Counterfactual Explanations Clustering

Jul 14, 2026

Deployable Human Preference Alignment in Robotics: Learning Representative Rewards from Diverse Human Preferences

Aligning robot policies with human preferences is essential for deployment to diverse end users. In per-user alignment approach, preference feedback is often sparse, so learning becomes unstable and vulnerable to human preference noise, and a growing number of individualized policies makes validation difficult before deployment. A single shared policy approach to user alignment avoids this cost but fails to capture heterogeneous preferences and often neglects minority preferences. To address these challenges, we introduce Preference-based REward Clustering (PREC), a novel framework that learns a compact set of policies from binary preference labels provided by diverse users. From a dataset of user trajectories and their preference labels, PREC first sets the labels aside and aggregates trajectories across users to learn a population-level shared trajectory encoder, alleviating limited per-user coverage and avoiding label noise during representation learning. Using this representation, PREC jointly assigns users to preference-coherent clusters and learns a representative reward model per cluster using preference labels, from which a policy is optimized for each cluster. Clustering similar users compensates for the limited number of labels available from each user and mitigates the effect of label noise. At the same time, maintaining a manageable number of reward models reduces the validation burden at deployment. Experiments across diverse simulated locomotion environments show that PREC groups users who label different trajectory subsets into preference-coherent clusters more accurately than baseline methods. Under sparse and noisy feedback, policies trained with PREC improve all three social welfare metrics over an existing single shared-policy user-alignment approach and even outperform per-user alignment approaches.

Taehyung Kim, Gwangmo Lee, Minjun Chang +2

Yonsei University, Seoul, South Korea · Georgia Institute of Technology, United States of America · Hyundai Motor Company, Seoul, South Korea

Clustering Preference Alignment User Preference Modeling Preference-Based RL

Jul 14, 2026

Cluster-Weighted EDMD

Extended Dynamic Mode Decomposition (EDMD) approximates Koopman operators from data, but a single global operator is inefficient when different state-space regions exhibit distinct local dynamics. We introduce Cluster-Weighted EDMD (CW-EDMD), which jointly learns a soft phase-space partition and a per-cluster EDMD operator. Its Expectation-Maximization (EM) objective assigns each transition based on both geometric proximity and prediction residuals, so clusters specialize where local Koopman models are accurate rather than where the data are dense. On Lorenz, damped pendulum, and Duffing systems, across 36 configurations and 10 seeds, CW-EDMD improves matched-degree EDMD in one-step and 5s-rollout prediction. Across 288 paired comparisons, there are significant error reductions in 258 cases, increases in 4, and no differences in 26. Median one-step error reductions are 57x, 2.7x, and 12x on pendulum, Duffing, and Lorenz, respectively.

Lorenzo Tomaz, Judd Rosenblatt, Flavio Kicis +2

AE Studio

Koopman Operator Learning Latent Dynamics Modeling Extended Dynamic Mode Decomposition Clustering Nonlinear System Identification Dynamic Mode Decomposition

Jul 12, 2026

Beyond Looking Up, Try Looking Around: Harmonizing Global Structure and Local Consistency in Optimal Transport for Short Text Clustering

Pseudo-labeling based on Optimal Transport (OT) has become an effective mechanism for enhancing short text clustering. Existing OT methods are short in modeling semantic consistencies between samples, which may assign different pseudo-labels to semantically similar samples. These erroneous pseudo-labels can cause the model to produce inferior clusters. This paper proposes a novel short text clustering framework, which remedies the neglect of semantic consistency in existing OT methods, generating reliable pseudo-labels to facilitate clustering. Specifically, the proposed approach first designs an instance-level attention mechanism to capture semantic relationships between samples, which are then integrated into the OT formulation to endow the transport process with neighborhood semantic awareness. By solving the proposed OT formulation, reliable pseudo-labels are obtained that simultaneously account for sample-to-sample semantic consistency and sample-to-cluster global structure information. These pseudo-labels are then used as supervisory signals to guide the model to achieve accurate clustering. Extensive experiments demonstrate that the proposed approach outperforms state-of-the-art methods. The code is available at: https://github.com/YZH0905/CAOT-STC.

Zhihao Yao, Yuxuan Gu, Jixuan Yin +1

Harbin Engineering University, China · Harbin Institute of Technology, China

Clustering Unsupervised Clustering Pseudo-Labeling Optimal Transport Text Clustering

Jul 11, 2026

Graph Representation of RaagBase: A Unique Dataset for Hindustani Music

Raag classification is a fundamental MIR task for Hindustani Music, with applications in recommendation, education, archiving, and intelligent search. However, raag clustering remains underexplored, as most existing approaches rely on annotated audio or labeled datasets. While annotated melodic phrases capture characteristic patterns, complete note sequences preserve temporal structure and contextual dependencies, making them more suitable for data-driven modeling. In this work, we introduce RaagBase, a notation-based text dataset consisting of note sequences from compositions by Pt. Bhatkhande. Furthermore we propose a novel graph-based representation of raag structures by modeling the dominance and absence of notes in compositions. Each composition is represented as a node, and the edges between two compositions corresponds the similarities between them based on the note frequency distribution. Further, we apply established graph clustering techniques to identify groups of similar raag compositions. Experimental results demonstrate highly coherent clusters with strong agreement to ground-truth raag labels, thereby validating both the dataset and the proposed representation. The dataset is publicly available at https://anonymous.4open.science/r/RaagBase-5427.

Chandan Misra, Swarup Chattopadhyay

Clustering Music Information Retrieval

Jul 10, 2026

Performance Benchmarking and Optimisation of Clustering Algorithms for Local and Non-Local Similarity Measure in Medical Image Analysis

Medical imaging generates high-resolution images posing significant storage, transmission, and computational challenges. While low-rank matrix approximation (LoRMA) techniques offer efficient compression by exploiting structural redundancy, global approaches often fail to preserve local details critical for diagnosis. This paper focuses on clustering techniques that exploit non-local self-similarity to identify structurally similar regions in medical images. These clusters can be used for post-processing tasks such as adaptive image compression. We evaluate five clustering techniques: k-means, mini-batch k-means, agglomerative hierarchical clustering, balanced iterative reducing and clustering using hierarchies (BIRCH), and bisecting k-means across MRI, ultrasound, and chest X-ray modalities. All clustering techniques were optimised using random search, and cluster quality was assessed using the Silhouette score, the Davies-Bouldin (DB) index, and the Calinski-Harabasz (CH) index. Results demonstrate that standard k-means and bisecting k-means generally achieve strong cluster cohesion and separation across modalities. However, they tend to form a small number of clusters with high intra-cluster variability, limiting their effectiveness for post-processing tasks such as adaptive compression. Agglomerative clustering outperformed other techniques for MRI and ultrasound in terms of intra-cluster homogeneity, making it more suitable for preserving fine diagnostic details. For chest X-rays, mini-batch k-means achieved the best balance between clustering quality and intra-cluster compactness. BIRCH consistently underperformed across all modalities.

Sisipho Hamlomo, Marcellin Atemkeng

Department of Mathematics, Rhodes University, PO Box 94, Makhanda, 6140, South Africa · Department of Statistics, Rhodes University, PO Box 94, Makhanda, 6140, South Africa · National Institute for Theoretical and Computational Sciences (NITheCS), Stellenbosch 7600, South Africa

Medical Image Analysis Clustering Hierarchical Clustering

Jul 9, 2026

An interpretable Good--Turing restart criterion for k-means++

The k-means++ algorithm is commonly restarted multiple times to avoid poor local optima, yet the number of restarts is almost always chosen arbitrarily and applied uniformly regardless of data set difficulty. This undermines any comparison relying on such a choice and wastes computation on easy data sets while potentially under-serving hard ones. We introduce GTRC, a restart criterion combining a Good-Turing estimate, a proven unconditional bound, and a confidence-based bound on the probability that a further restart would improve on the current result, stopping once this probability falls below a user-specified tolerance

\varepsilon

. Across 36 data sets, GTRC reached clustering quality competitive with well-chosen fixed restart counts, while the number of restarts used varied considerably and appropriately with data set difficulty, governed by an interpretable, data-dependent signal rather than a fixed rule. GTRC offers a principled and reportable alternative to fixing the number of

k

-means++ restarts in advance. Software:https://github.com/RCdeAmorim/Good-Turing-Restart-Criterion.

Renato Cordeiro de Amorim

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

Early Stopping Clustering

Jul 9, 2026

Equivariant Quantum Clustering with Differential Privacy: Parameter-Efficient Privacy-Preserving Analysis Across Heterogeneous Sensitive Datasets

Privacy-preserving clustering is critical for analyzing sensitive data in healthcare, cybersecurity, and enterprise applications, where maintaining data confidentiality must be balanced with analytical performance. This paper presents Equivariant Quantum Clustering (EQC), a parameter-efficient framework that integrates symmetry-aware quantum circuits with differential privacy to improve the privacy-utility tradeoff. EQC employs p4m equivariant parameter sharing to reduce circuit complexity while preserving informative feature representations. The framework is evaluated on three privacy-sensitive datasets: NSL-KDD, CERT Insider Threat v6.2, and a synthetic MIMIC-III clinical dataset. On the NSL-KDD benchmark, EQC achieves 79.3% clustering accuracy while reducing membership inference attack success to 38.3% under a privacy budget of ε = 1.0 and δ = 10^-5, outperforming representative classical and quantum baselines. Ablation studies indicate that the performance gains primarily arise from parameter-efficient circuit design combined with differential privacy. The results demonstrate that EQC provides a practical quantum-ready framework for secure and privacy-preserving clustering across heterogeneous sensitive datasets.

B. M. Taslimul Haq, Md Arifur Rahman, Tawfiq Al Islam Foysal +2

Department of Information Systems, Central Michigan University, Mount Pleasant, MI, USA. · Department of Computer and Information Sciences, Trine University, Angola, IN, USA. · Department of Computer Science and Engineering, American International University–Bangladesh (AIUB), Dhaka, Bangladesh. +2

Clustering Quantum Machine Learning Privacy-Preserving ML Differential Privacy

Jul 8, 2026

FMMVCC: Fuzzy Mamba-based Multi-View Contrastive Clustering for Univariate Time Series

In many realistic scenarios, large volumes of time series data are generated with limited or expensive annotations. This limitation makes supervised learning methods difficult to apply and leads to the use of unsupervised approaches capable of discovering meaningful structures directly from raw data. Clustering therefore plays a crucial role in organizing time series into groups that share similar temporal patterns, enabling exploratory analysis and downstream tasks without requiring manual labeling. However, existing deep clustering methods often struggle to capture long-range temporal dependencies or rely on architectures with high computational cost. This paper introduces FMMVCC, a Mamba-based deep clustering framework for time series that leverages state space sequence modeling to efficiently learn temporal representations with linear complexity. Additionally, it utilizes multi-view self-supervised learning with temporal masking and augmentations. Experimental evaluation in 15 benchmark datasets proves that FMMVCC consistently outperforms state-of-the-art baselines, achieving the best overall performance in 29 of 60 total metric evaluations and the highest average rank in all tested scenarios.

Donato Cerciello, Leonardo Schiavo, Angel Panizo-LLedot +2

Departamento de Sistemas Inform´aticos, Universidad Polit´ecnica de Madrid Madrid, Spain

Self-Supervised Time Series Representation Learning Clustering Unsupervised Clustering Multi-View Clustering Time Series Clustering

Jul 8, 2026

Converge to Surprise: Evolutionary Self-supervised Image Clustering

A variety of self-supervised image clustering approaches are invented in the past years. However, all dominant approaches are exploitative: The direction of parameter updates is determined by known states (observed input samples and existing parameters). We propose an explorative self-supervised learning framework that steps out of this zone. We define a surprise score that measures how unlikely the model's output representation is, assuming that all pixels are i.i.d. random noise. Maximizing the surprise score forces the deep learning model to reject the random noise null hypothesis, or equivalently, to discover non-randomness from data. Also, we propose a fundamental assumption: a surprise score cannot, in general, be fully optimized by exploitative optimization approaches. Thus, we propose the converge-to-surprise scheme to optimize a model: an evolution-strategy (ES) outer loop, which maximizes the surprise score using the mutation-selection mechanism, paired with a periodic gradient-descent inner loop, which uses the surprising clusters already discovered by ES as surrogate targets. On simple image benchmarks, our framework trained from scratch achieves new state-of-the-art results in non-parametric self-supervised image clustering --- the strictest deep-clustering setting, where the number of classes is unknown during training.

Canlin Zhang, Xiuwen Liu

Independent Researcher · Department of Computer Science Florida State University

Unsupervised Learning Self-Supervised Learning Clustering Unsupervised Clustering Deep Clustering Image Clustering+1

Jul 6, 2026

Sensitivity Sampling with Predictions for k-Means Clustering

We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.

Cristian Boldrin, Fabio Vandin

University of Padova, Padova, Italy

Clustering Importance Sampling Coreset Selection Learning-Augmented Algorithms

Jul 6, 2026

Framework for Grouping Local Process Models

Local Process Models (LPMs) are an underexplored concept in process mining. LPMs describe patterns in event data considering sequence, choice, concurrency, and loop. In recent years, process mining has proved successful in the analysis and improvement of operational processes. More often than not, surprising findings are found when one does not consider the full process, making LPMs and their discovery highly valuable. However, similar to other pattern mining approaches, LPM discovery algorithms face the problems of model explosion and model repetition, i.e., the algorithms may create hundreds if not thousands of LPMs, and subsets of them are close in structure or behavior. Practically, no analyst would be able to comb through thousands of LPMs leading to using a sample of LPMs that are easily accessible. The current sentiment is that the top-scoring LPMs form the optimal sample to be presented. However, different applications should demand a different optimal sample. With this work, we show that if the goal of the mined LPMs is to understand a process, using the top-scoring LPMs as an optimal sample is a poor choice because of high repetition. We propose a framework for grouping LPMs and creating an optimal sample by taking one representative LPM for each group. We measure similarity between models via established process model similarity measures or by comparing the context in which an LPM appears. The context is formed using data attributes available in the underlying event logs. We demonstrate the usefulness of grouping on multiple event logs by comparing repetition and coverage between samples comprised of the top-scoring models and the representatives of discovered groups.

Viki Peeva, Wil M. P. van der Aalst

Chair of Process and Data Science (PADS), RWTH Aachen University, Ahronstrasse 55, Aachen, 52074, North Rhine-Westphalia, Germany.

Process Mining Clustering

Jul 6, 2026

Learnable Weighting of Intra-Attribute Distances for Categorical Data Clustering with Nominal and Ordinal Attributes

The success of categorical data clustering generally much relies on the distance metric that measures the dissimilarity degree between two objects. However, most of the existing clustering methods treat the two categorical subtypes, i.e. nominal and ordinal attributes, in the same way when calculating the dissimilarity without considering the relative order information of the ordinal values. Moreover, there would exist interdependence among the nominal and ordinal attributes, which is worth exploring for indicating the dissimilarity. This paper will therefore study the intrinsic difference and connection of nominal and ordinal attribute values from a perspective akin to the graph. Accordingly, we propose a novel distance metric to measure the intra-attribute distances of nominal and ordinal attributes in a unified way, meanwhile preserving the order relationship among ordinal values. Subsequently, we propose a new clustering algorithm to make the learning of intra-attribute distance weights and partitions of data objects into a single learning paradigm rather than two separate steps, whereby circumventing a suboptimal solution. Experiments show the efficacy of the proposed algorithm in comparison with the existing counterparts.

Yiqun Zhang, Yiu-ming Cheung

Clustering Metric Learning

Jul 2, 2026

Scalable and Distributed Silhouette Approximation

The silhouette is one of the most widely used measures to assess the quality of a

k

-clustering of a dataset of

n

elements. Its evaluation requires no information beyond the clustering assignment. In addition, the silhouette is extremely easy to interpret, providing a score to measure the quality of a clustering as a whole or for each element. The exact computation of the: (i) silhouette of each element of a dataset; and (ii) the global silhouette of the clustering; require

Θ(n^2)

distance calculations, under general metrics. The quadratic complexity

Θ(n^2)

is extremely prohibitive, especially on massive modern datasets. Surprisingly, existing approximate methods using

O(n^2)

distance calculations are heuristics not offering provable and controllable guarantees on the quality of their results. We introduce the first rigorous and efficient algorithms to estimate: (i) the (local) silhouette of each element of a dataset; and (ii) the (global) silhouette; of any metric

k

-clustering. Our methods, based on sampling, perform

O(nk\varepsilon^{-2}\ln (nk/δ))

distance computations, and provide estimates with additive error

O(\varepsilon)

with probability at least

1-δ

. That is, parameters

\varepsilon

and

δ

in

(0,1)

control the trade-off between accuracy and efficiency. We also introduce a scalable and distributed design of our methods for the MapReduce and Massively Parallel Computing (MPC) frameworks. Our distributed algorithms use a constant number of rounds and sublinear local memory. Finally, we perform extensive experiments against state-of-the-art approaches. The results show that our new techniques yield the best trade-off between accuracy and efficiency for both local and global silhouette estimation. In addition, our methods scale efficiently to massive datasets for which an exact computation of the silhouette is not practical.

Ilie Sarpe, Federico Altieri, Andrea Pietracaprina +2

KTH Royal Institute of Technology · University of Padova

Jul 2, 2026

Statistical Properties of $k$ -means Clustering for Data Missing Completely at Random

The classical

k

-means clustering cannot be directly used to incomplete data, and existing

k

-means-based clustering for missing data primarily focus on improving the practical accuracy of clustering, whereas most of them lack theoretical guarantees in the asymptotic sense. In this paper, we investigate the statistical properties of

k

-means clustering in the presence of missing data. We first establish the

\sqrt{n}

-excess risk bound and prove the consistency of the estimated cluster centers under general missing mechanisms. For the Missing Completely at Random (MCAR) mechanism, we further derive the

\sqrt{n}

-convergence rate and asymptotic normality of the estimated cluster centers. Moreover, we study in what cases the cluster centers estimated by incomplete data converge to the true cluster centers of original fully observed data, and give a sufficient condition about the missing probability and the separation among true clusters. These results provide a theoretical guarantee for missing-data-

k

-means. Notably, our analysis reveal that under MCAR mechanism, both achieving the

\sqrt{n}

-rate and converging to the true cluster centers require

k

true centers to be distinct in every dimension, highlighting the significant challenges of application in high-dimensional regimes. Finally, we conduct numerical simulations on synthetic incomplete datasets to support our theoretical analysis results.

Xin Guan

Graduate School of Information Sciences Tohoku University Sendai, Miyagi 980-8579, Japan

Clustering Unsupervised Clustering Statistical Learning Theory

Jul 2, 2026

UT-AISTimprt submission for ICME 2026 Grand Challenge on Academic Text-to-Music Generation

This work investigates the effect of batch sampling strategies during training for text-to-audio music generation under low-data and small-scale model settings. This paper describes our approach and findings for the ICME 2026 Grand Challenge on Academic Text-to-Music Generation. Training data are clustered using either text embeddings or audio embeddings, and samples with similar characteristics are grouped within the same mini-batch to mitigate gradient interference. The effects of modality and cluster granularity on clustering are analyzed. Results show that clustering based on text embeddings achieves better performance on objective evaluation metrics than clustering based on audio embeddings. In addition, different cluster granularity leads to different behaviors across evaluation criteria: a moderate number of clusters performs best on objective metrics, while a larger number of clusters tends to exhibit music with more coherent structure in listening tests.

Shunsuke Yoshida, Yu-Hua Chen, Satoru Fukayama

University of Tokyo, Japan · National Institute of Advanced Industrial Science and Technology (AIST), Japan

Text-to-Music Generation Clustering Music Generation

Jul 1, 2026

GSRQ: Gain-Shape Residual Quantization for Sub-1-bit KV Cache

The deployment of Large Language Models (LLMs) with extended context windows is increasingly constrained by the linear growth of Key-Value (KV) cache memory. Vector Quantization (VQ), particularly Residual Quantization (RQ), is a promising approach for pushing KV cache storage toward the sub-1-bit regime by progressively encoding residuals with small codebooks. However, most VQ methods still rely on standard

\ell_2

K

-means as the core codebook-learning primitive. We identify a subtle high-dimensional issue of this primitive: Euclidean centroid averaging can induce centroid shrinkage, which weakens the angular alignment term in the

\ell_2

distortion and makes directional preservation harder. To address this issue, we propose Gain-Shape

K

-means (GSKM), a drop-in replacement for

K

-means that improves directional fidelity while matching, and in some regimes improving,

\ell_2

distortion. We then build Gain-Shape Residual Quantization (GSRQ) by incorporating a weighted extension of GSKM into an RQ pipeline. On LLaMA-3-8B, GSRQ substantially improves over strong KV cache quantization baselines across bit rates. At 1-bit, it improves the average accuracy across LongBench tasks from 11.34 to 33.54, a gain of 22.20 percentage points over VQLLM.

Soosung Kim, Minjae Park, Eui-Young Chung +1

Department of Electrical and Electronic Engineering, Yonsei University, Seoul, Republic of Korea · Department of Systems Semiconductor Engineering, Yonsei University, Seoul, Republic of Korea

LLM Compression Residual VQ KV Caching Clustering Vector Quantization KV-Cache Quantization+1

Jun 30, 2026

MNAR- $k$ -means: A $k$ -means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability

The classical

k

-means clustering, based on distances computed from all data features, cannot be directly applied to incomplete data with missing values. A natural extension of

k

-means to missing data is to involve only the observed positions in clustering, which is equivalent to imputing missing values by corresponding cluster means. However, for data missing not at random (MNAR), since missingness is related to data values, such a mean-imputation-based method may lead to the distortion of estimated cluster centers, resulting in a poor clustering result. Since MNAR mechanisms are very common in reality, it is necessary to improve the performance of

k

-means-based clustering methods for such data. In this paper, we focus on a magnitude-decaying MNAR scenario where data is more likely to be missing at positions with smaller absolute values, and we propose a novel

k

-means clustering method based on the constraint of the size of imputation values, which enjoys a good mathematical interpretation. Moreover, we establish the statistical consistency of the estimated cluster centers of the proposed method to the true cluster centers of fully observed data, and solve the optimization of the proposed loss function via an alternative minimization algorithm. Simulation experiments verify the effect of the proposed method in improving clustering results and reducing the bias of estimated cluster centers. Applications to real-world missing data further show the utility of the proposed method.

Xin Guan

Graduate School of Information Sciences Tohoku University Sendai, Miyagi 980-8579, Japan

Clustering Learning with Missing Data Unsupervised Clustering

Jun 29, 2026

Consensus Clustering of Free-Viewing Gaze Data: New Insights into Human-Information Interaction

Free-viewing gaze data provides a rich, task-free window into human visual attention. Conventional exploratory data analysis of the data provides user attention patterns through fixations and areas of interest. However, despite the richness of this gaze data, its human-information interaction (HII) patterns are understudied. We address this gap using consensus clustering of gaze data with respect to users and stimulus characteristics. We present a novel end-to-end unsupervised ensemble learning system for consensus clustering of free-viewing gaze datasets, EnsembleGaze. With a goal of characterizing the user behavior and stimulus type, we propose a feature engineering step based on statistical descriptors of fixation-based distributions. EnsembleGaze involves consensus voting of selected clustering methods implemented on the feature vector to compute the co-association matrix. Using the separate consensus clustering of users and stimuli as a baseline, we further propose two high-dimensional clustering strategies for determining gaze clusters based on joint user and image characterization. They are consensus subspace clustering and spectral biclustering. Clustering performance is evaluated using selected standard metrics and is further interpreted through image-level properties. Our system provides a replicable method for the unsupervised analysis of fixation behavior in scene perception research. Our results show that image stimuli groupings are highly consistent across methods, reflecting a robust ambient-versus-focal viewing mode distinction, whereas user groupings are image-context-dependent, a structure that only biclustering and the two-step conditional approaches are architecturally capable of recovering. Testing on the publicly available datasets revealed dataset-specific patterns, with each offering complementary insights through distinct clustering strategies.

Beryl Gnanaraj, Jaya Sreevalsan-Nair, Saqib Alam Ansari +1

Graphics-Visualization-Computing Lab, International Institute of Information Technology Bangalore, Karnataka 560100, India. · 2PSG College of Technology, Coimbatore, Tamin Nadu, India.

Ensemble Learning Clustering Unsupervised Clustering Eye Tracking

Jun 28, 2026

Nonlinear mixture model motivated subspace clustering

We derive the linear union-of-subspaces (UoS) model for subspace clustering (SC) from the nonlinear mixture model (NMM) used in blind source separation (BSS) to represent a D-dimensional observation vector as an unknown multivariate nonlinear mapping of C latent variables. Assuming the mapping is differentiable up to an unknown order K, we approximate NMM by a K-th order Taylor expansion, yielding a model equivalent to the linear UoS framework underlying SC. This establishes that: (i) the smoothness order K corresponds to the unknown subspace dimension d; (ii) KC equals the number of anchors; and (iii) the sparsity of the representation vector equals K (i.e., d). These relationships enable estimation of bounds on subspace dimension, and that is validated on six benchmark datasets using five established SC algorithms. Established theoretical results are important for post-processing of self-representation matrices estimated by SC algorithms.

Ivica Kopriva

Division of Computing and Data Science, Ruđer Bošković Instute, Zagreb, Croatia

Jun 26, 2026

scKDGM: KAN-guided Dynamic Graph Masked Learning for Single-Cell RNA-seq Clustering

Single-cell RNA sequencing (scRNA-seq) clustering is essential for identifying cell types, but high dimensionality, sparsity, dropout, and technical noise hinder robust expression representation and cell graph construction. Existing masked autoencoders mainly use expression recovery for feature reconstruction, while graph clustering methods usually depend on fixed KNN graphs and do not feed recovered expression back into graph optimization. We propose scKDGM, a KAN-guided dynamic graph masked learning framework for scRNA-seq clustering. scKDGM uses graph-aware distribution preserving gene masking (GDP-Mask) to perturb cell identity, a KAN-based TAKGCN encoder to learn masked-view representations, mask-guided expression recovery to construct a dynamic graph, and cross-view contrastive learning to transfer recovery signals into topology updates. A ZINB loss models overdispersion and zero inflation. Experiments on 12 real scRNA-seq datasets show that scKDGM outperforms 10 baselines in average NMI and ARI.

Jun Tang, Pengwei Hu, Sicong Gao +3

College of Computer and Information Science, Southwest University, Chongqing, China · Xinjiang Technical Institute of Physics and Chemistry, Chinese Academy of Sciences, Urumqi, China

Graph SSL Clustering Dynamic Graph Learning Graph Clustering Single-Cell RNA Sequencing

Jun 25, 2026

How to evaluate clustering with ground truth?

External indexes can be used for cluster evaluation when ground truth is available. We review the most common external validity indexes focusing on set-matching-based measures. We recommend centroid index (CI), because it is an intuitive cluster-level measure with an explainable result. If we need a more fine-tuned, point-level measure, there are more choices. Pair-set index (PSI) provides a normalized score which is not biased by cluster sizes. If all points should matter equally, then clustering accuracy (ACC) or any other set-matching measure is suitable.

Pasi Fränti

School of Computing University of Eastern Finland Joensuu, Finland

Jun 25, 2026

Term-Centric Hierarchy Induction from Heterogeneous Corpora

Organizing knowledge from diverse text sources into interpretable hierarchies is crucial for tasks such as policy analysis, innovation monitoring, and exploratory domain mapping. Existing taxonomy induction methods typically rely on document-level representations that capture entire documents rather than the specific domain concepts relevant for knowledge organization, limiting their ability to generalize across heterogeneous sources. We propose a term-centric framework for inducing hierarchical taxonomies from heterogeneous corpora that scales to massive document collections. Our approach maps documents from diverse sources into a shared representation space using automatic term extraction, enabling robust cross-source alignment. Based on these representations, we construct interpretable hierarchies that integrate domain priors with datadriven clustering. Experiments on a novel English and German multi-source benchmark of over one million documents demonstrate that our method improves cross-source coherence and hierarchy quality over text- and summarybased baselines. A case study on German regional innovation analysis further demonstrates its practical utility for technology landscape mapping.

Elena Senger, Yuri Campbell, Jan-Peter Bergmann +2

1MaiNLP, Center for Information and Language Processing, LMU Munich, Germany · 2Fraunhofer Institute for Systems and Innovation Research ISI, Germany · Department of Computer Science, IT University of Copenhagen, Denmark

Clustering Hierarchical Clustering Taxonomy Induction

Jun 23, 2026

Universal Guideline-Driven Image Clustering via a Hybrid LLM Agent

Unifying image clustering across different clustering scenarios remains challenging due to fundamental gaps among tasks. We introduce a Guideline-Driven Image Clustering Agent, the first universal framework that bridges these gaps through textual guidelines. To incorporate complex guidelines without task-specific training, we propose Generative Concept Proxy Modeling, which generates guideline-aware embeddings via concept proxy extraction. For scenarios requiring automatic cluster discovery, we introduce LLM Traversal based on Minimum Spanning Tree that selectively applies LLM reasoning for complex semantic judgments. Our method generalizes across diverse clustering scenarios spanning from general to fine-grained categorization, from global to local criteria, and from balanced to long-tail distributions. Our framework consistently outperforms specialized methods across diverse clustering tasks.

Wenliang Zhong, Rob Barton, Lucas Goncalves +7

1The University of Texas at Arlington · 2Amazon

Clustering Unsupervised Clustering Image Clustering Semantic Clustering

Jun 22, 2026

Fursee: Hybrid YOLO-DINOv3 Framework for Fursuit Identity Retrieval and Clustering

Global furry conventions produce massive fursuit photographs, while manual sorting brings heavy labor costs and calls for automatic identity retrieval and clustering solutions. General multimodal models lack dedicated optimization for complex fursuit scenes, and no public benchmark dataset exists for this task. To fill this gap, we build a specialized fursuit image dataset and present a three-stage hybrid pipeline Fursee for fursuit identity retrieval and clustering. First, YOLO detects and crops high-resolution fursuit head patches to improve localization of small and overlapping targets. Second, ArcFace optimizes DINOv3 embeddings to enlarge angular separation between different identities on the feature hypersphere. Third, DBSCAN performs unsupervised clustering, with silhouette-coefficient-driven search automatically selecting optimal hyperparameters rather than fixed manual radius. Retrieval and clustering experiments verify that our pipeline outperforms mainstream multimodal models including GPT5.5, Claude Opus 4.8 and Qwen3.7-Plus on all evaluation metrics, achieving competitive performance for fursuit head retrieval and grouping.

Jundi Wu

Shandong University Qingdao, China

Vision Foundation Models Image Matching Clustering Image Clustering Image Retrieval

Jun 22, 2026

Noise is Signal: Density-Based Outliers as Leading Indicators of Occupational Emergence in Labor Market Text

Standard NLP pipelines for occupational clustering discard the 10-15% of job postings that density-based methods assign to noise. We argue this is an error: in rapidly evolving domains, low posting density signals novelty, not incoherence. We formalize this as the Emergence-Density Inversion (EDI) hypothesis and test it longitudinally on 84,988 job postings across eight quarters (Q4 2022-Q3 2024). EDI is partially confirmed: high-EOS outlier groups transition to stable clusters in 1.4 +/- 0.6 quarters vs. 4.1 +/- 1.2 for low-EOS groups (p < 0.001), though the signal fails in approximately 19% of cases, which we characterize as a failure analysis. We extend the Emerging Occupation Score (EOS) with Temporal Velocity and Cross-Platform Convergence, improving 2-quarter cluster-formation prediction from F1 = 0.61 to 0.74, outperforming Isolation Forest, LOF, GLOSH, and BERTrend baselines. A retrospective study on three now-established roles (MLOps Engineer, DevOps/SRE, Data Engineer) confirms EOS signalled 2-3 quarters before cluster formation, providing held-out validation. A held-out annotator panel (kappa = 0.74) rates EOS > 0.75 as coherent emerging occupations with 77% precision. Prompt Engineer, AI Safety Researcher, Foundation Model Engineer, and Agent Systems Engineer, all absent from O*NET, are top-4 in Q3 2024 and form stable clusters by Q1 2025.

Shreyash Rawat

Independent Researcher · Redmond, WA, USA

Clustering Computational Social Science Anomaly Detection

Jun 19, 2026

Cohort Organized Learning: Clustering Through Agreement

In this article we describe Cohort Organized Learning (CoOL), a method for clustering data without explicit distance or similarity computations. Herein, we will describe CoOL, derive the gradients determined by expectation maximization to train the networks, show how to monitor convergence during training and evaluate the clusters after training, and discuss a series of examples and use cases. We also discuss CoOL's limitations and future prospects on related tasks. Because CoOL uses neural networks to estimate the clusters, it can be used to cluster any data that can be made compatible and we illustrate this on vector data and images.

Finn Henry O'Shea, Maria Elena Monzani

SLAC National Accelerator Laboratory, 2575 Sand Hill Road, Menlo Park, CA 94025-7015, USA · Kavli Institute for Particle Astrophysics and Cosmology, Stanford University, Stanford, CA 94305-4085 USA

Unsupervised Learning Clustering Unsupervised Clustering Deep Clustering