Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

• URL: http://arxiv.org/abs/2603.27417v1
• Date: Sat, 28 Mar 2026 21:33:06 GMT
• Title: Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering
• Abstract summary: This paper presents a novel centroid-based algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link constraints.<n>The algorithm consistently outperforms state-of-the-art benchmarks in both clustering accuracy and algorithmic efficiency for large-scale datasets.
• Score: 5.478764356647438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a novel centroid-based heuristic algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link (ML) and cannot-link (CL) constraints. The algorithm employs a dual-phase iterative process: an assignment step that utilizes Kempe chain swaps to refine current clustering in the constrained solution space and a centroid update step that computes optimal cluster centroids. To enhance global search capabilities and avoid local optima, the framework incorporates controlled perturbations during the update phase. Empirical evaluations demonstrate that the proposed method achieves near-optimal partitions while maintaining high computational efficiency and scalability. The results indicate that Kempe Swap K-Means consistently outperforms state-of-the-art benchmarks in both clustering accuracy and algorithmic efficiency for large-scale datasets.

Related papers

• When Fireflies Cluster; Enhancing Automatic Clustering via Centroid-Guided Firefly Optimization [2.929391519312015]
  This work presents a novel variant of the Firefly Algorithm (FA) for data clustering.<n>It addresses limitations of traditional methods like K-Means that struggle with non-uniform cluster shapes, densities, and the need for pre-defining the number of clusters.<n>Experiments show improved clustering quality and reduced intra-cluster path distances compared to K-Means.
  arXiv  Detail & Related papers  (2026-05-18T14:22:13Z)
• CavMerge: Merging K-means Based on Local Log-Concavity [2.579311291240392]
  K-means clustering is known to exhibit suboptimal performance when applied to non-linearly separable data.<n>We present emphCavMerge, a novel K-means merging algorithm that is intuitive, free of parameter tuning, and computationally efficient.
  arXiv  Detail & Related papers  (2026-04-05T22:47:36Z)
• Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach [10.257446766550862]
  We study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge.<n>We propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2.
  arXiv  Detail & Related papers  (2026-01-17T02:39:41Z)
• CAS Condensed and Accelerated Silhouette: An Efficient Method for Determining the Optimal K in K-Means Clustering [0.0]
  This paper presents strategies for selecting the optimal value of k in clustering.<n>It focuses on achieving a balance between clustering precision and computational efficiency in complex data environments.<n>The proposed approach achieves up to 99 percent faster execution times on high-dimensional datasets.
  arXiv  Detail & Related papers  (2025-07-11T05:03:16Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-means is a novel clustering algorithm that eliminates the need to set k or any other parameters.<n>It uses the minimum description length principle to automatically determine the optimal number of clusters, k*, by splitting and merging clusters.<n>We prove that k*-means is guaranteed to converge and demonstrate experimentally that it significantly outperforms existing methods in scenarios where k is unknown.
  arXiv  Detail & Related papers  (2025-05-17T08:41:07Z)
• Nearest Neighbour Equilibrium Clustering [6.635604919499181]
  A novel and intuitive nearest neighbours based clustering algorithm is introduced, in which a cluster is defined in terms of an equilibrium condition which balances its size and cohesiveness.<n>The formulation of the equilibrium condition allows for a quantification of the strength of alignment of each point to a cluster, with these cluster alignment strengths leading naturally to a model selection criterion which renders the proposed approach fully automatable.
  arXiv  Detail & Related papers  (2025-03-27T12:16:54Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.