基于凯姆佩交换的聚类算法，高效处理约束聚类问题。
Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering
- 用凯姆佩链交换优化约束下的聚类分配
- 在大规模数据上接近最优且计算高效
- 适合需要约束聚类的工业级应用
本文提出一种新型基于中心点的启发式算法——凯姆佩交换K均值（Kempe Swap K-Means），用于在严格的必须连接（ML）和不能连接（CL）约束下的受限聚类。该算法采用双阶段迭代过程：第一阶段利用凯姆佩链交换在约束解空间中精炼当前聚类结果；第二阶段通过计算最优簇中心更新聚类中心。为增强全局搜索能力并避免局部最优，更新阶段引入受控扰动机制。实验表明，该方法在保持高计算效率和可扩展性的同时，实现了接近最优的聚类划分。结果表明，该算法在大规模数据集上的聚类准确率和算法效率均持续优于当前最先进的基准方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。