提出可扩展的约束聚类全局优化算法，处理百万级数据仍保最优解。
A Scalable Global Optimization Algorithm For Constrained Clustering
- 将必须相连样本合并为伪中心，用几何规则剪枝不能相连对
- 支持20万样本含不可连接约束，150万样本含必须连接约束
- 保证全局最优且避免启发式方法在大数据上失效
约束聚类利用有限领域知识提升聚类性能与可解释性，但引入成对必须相连和不能相连约束是NP难问题，导致全局优化不可行。现有混合整数优化方法仅限小规模数据集。本文提出样本驱动的基于分组的分支定界（SDC-GBB），通过将必须相连样本压缩为基于中心的伪样本，并利用几何规则剪枝不能相连对，同时保持收敛性和全局最优性。结合分组样本拉格朗日分解与高效下界/上界计算，实现可并行的高可扩展成对k-Means约束聚类。实验表明，该方法可在含不可连接约束的数据集上处理20万样本，含必须连接约束的数据集上处理150万样本，较当前最先进方法扩大200至1500倍，且最优性差距小于3%。该方法提供确定性全局保证，避免了现有启发式方法在大规模数据上的搜索失败。
原文摘要 · Abstract (English)
Constrained clustering leverages limited domain knowledge to improve clustering performance and interpretability, but incorporating pairwise must-link and cannot-link constraints is an NP-hard challenge, making global optimization intractable. Existing mixed-integer optimization methods are confined to small-scale datasets, limiting their utility. We propose Sample-Driven Constrained Group-Based Branch-and-Bound (SDC-GBB), a decomposable branch-and-bound (BB) framework that collapses must-linked samples into centroid-based pseudo-samples and prunes cannot-link through geometric rules, while preserving convergence and guaranteeing global optimality. By integrating grouped-sample Lagrangian decomposition and geometric elimination rules for efficient lower and upper bounds, the algorithm attains highly scalable pairwise k-Means constrained clustering via parallelism. Experimental results show that our approach handles datasets with 200,000 samples with cannot-link constraints and 1,500,000 samples with must-link constraints, which is 200 - 1500 times larger than the current state-of-the-art under comparable constraint settings, while reaching an optimality gap of less than 3%. In providing deterministic global guarantees, our method also avoids the search failures that off-the-shelf heuristics often encounter on large datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。