无需预设聚类数，通过图分割实现满足约束的半监督聚类
A Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems
- 将聚类建模为带缩放参数的图分割问题，放宽对簇数的要求
- 提出块坐标下降算法求解，理论保证收敛性并满足必须共现约束
- 适用于簇数未知且存在约束的场景，适合实际应用中的聚类任务
半监督聚类是众多应用中的基础问题。现有方法通常需要预先知道理想聚类数量，这在实践中难以获得；同时满足必须共现约束仍是主要挑战。本文将半监督聚类视为与数据集相关图上的分割问题，其中相似度矩阵包含反映必须共现约束的缩放参数。通过松弛技术，将图分割问题转化为不需精确簇数、仅需过估计的连续优化模型。进而提出块坐标下降算法高效求解该模型，并建立其收敛性理论。基于所得解，可在弱假设下构造出理论上满足必须共现约束的聚类。通过全面数值实验验证了所提方法的有效性与高效性。
原文摘要 · Abstract (English)
Semi-supervised clustering is a basic problem in various applications. Most existing methods require knowledge of the ideal cluster number, which is often difficult to obtain in practice. Besides, satisfying the must-link constraints is another major challenge for these methods. In this work, we view the semi-supervised clustering task as a partitioning problem on a graph associated with the given dataset, where the similarity matrix includes a scaling parameter to reflect the must-link constraints. Utilizing a relaxation technique, we formulate the graph partitioning problem into a continuous optimization model that does not require the exact cluster number, but only an overestimate of it. We then propose a block coordinate descent algorithm to efficiently solve this model, and establish its convergence result. Based on the obtained solution, we can construct the clusters that theoretically meet the must-link constraints under mild assumptions. Furthermore, we verify the effectiveness and efficiency of our proposed method through comprehensive numerical experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。