提出新算法解决大规模聚类问题，比现有方法更快更准。
A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering
- 用列生成结合动态约束聚合，减少计算中约束数量。
- 在多个数据集上求解速度提升显著，最优解精度高。
- 适合需要精确解的大规模聚类场景，如生物信息学分析。
最小平方和聚类问题（MSSC），又称k-means聚类，旨在将n个数据点划分为k个簇，使每个点与其所属簇中心的欧氏距离平方和最小。本文提出一种高效算法，用于求解大规模MSSC实例，结合列生成（CG）与动态约束聚合（DCA），有效减少列生成主问题中的约束数量。DCA最初用于通过将集合划分约束分组为不相交块来降低集合划分问题的退化性。本文首次将DCA引入MSSC的列生成框架中以求解精确解。通过一系列消融实验优化DCA设计，结果表明该方法显著优于文献中现有的最先进精确求解方法。
原文摘要 · Abstract (English)
The minimum sum-of-squares clustering problem (MSSC), also known as $k$-means clustering, refers to the problem of partitioning $n$ data points into $k$ clusters, with the objective of minimizing the total sum of squared Euclidean distances between each point and the center of its assigned cluster. We propose an efficient algorithm for solving large-scale MSSC instances, which combines column generation (CG) with dynamic constraint aggregation (DCA) to effectively reduce the number of constraints considered in the CG master problem. DCA was originally conceived to reduce degeneracy in set partitioning problems by utilizing an aggregated restricted master problem obtained from a partition of the set partitioning constraints into disjoint clusters. In this work, we explore the use of DCA within a CG algorithm for MSSC exact solution. Our method is fine-tuned by a series of ablation studies on DCA design choices, and is demonstrated to significantly outperform existing state-of-the-art exact approaches available in the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。