提出一种贪心图切割算法，高效求解聚类问题。
A Greedy Strategy for Graph Cut
- 从单样本聚类开始，贪心合并使目标函数下降最多的相邻聚类。
- 计算复杂度近线性，比传统两阶段方法更优。
- 结果唯一无随机性，适合追求稳定性能的场景。
我们提出一种解决图切割问题的贪心策略 GGC。该方法从每个数据样本视为独立聚类的状态出发，动态合并使全局目标函数值下降最多的两个聚类，直至达到所需聚类数，且证明了目标函数值序列的单调性。为降低计算复杂度，仅考虑聚类与其邻居之间的合并，使 GGC 的计算复杂度接近与样本数成线性关系。与其他算法不同，由于采用贪心策略，该算法的解具有唯一性，不受随机性影响。我们将该方法应用于广泛研究的归一化切割（normalized cut）问题，大量实验表明，相比传统的两阶段优化算法（特征分解 + k-means），GGC 能获得更优解；同时在多个前沿聚类算法中也表现出优势。
原文摘要 · Abstract (English)
We propose a Greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters which reduces the value of the global objective function the most until the required number of clusters is obtained, and the monotonicity of the sequence of objective function values is proved. To reduce the computational complexity of GGC, only mergers between clusters and their neighbors are considered. Therefore, GGC has a nearly linear computational complexity with respect to the number of samples. Also, unlike other algorithms, due to the greedy strategy, the solution of the proposed algorithm is unique. In other words, its performance is not affected by randomness. We apply the proposed method to solve the problem of normalized cut which is a widely concerned graph cut problem. Extensive experiments show that better solutions can often be achieved compared to the traditional two-stage optimization algorithm (eigendecomposition + k-means), on the normalized cut problem. In addition, the performance of GGC also has advantages compared to several state-of-the-art clustering algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。