论文标题
关于软k-均值的全球解决方案
On the Global Solution of Soft k-Means
论文作者
论文摘要
本文提出了一种算法来解决全球柔软的K-均值问题。与模糊的c均值不同，软k-均值（SKM）具有基质分解型物镜，并且已被证明与流行的概率分解型聚类方法（例如左随机聚类（LSC））有着密切的关系。尽管已经完成了一些解决软K-均值问题的工作，但他们通常使用交替的最小化方案或预计的梯度下降方法，由于SKM的非量化性，因此无法保证全局最优性。在本文中，我们提出了足够的条件，可以使软K-均值问题的可行解决方案在全球范围内成为最佳状态，并显示所提出的算法的输出可以满足它。此外，对于软k-均值问题，我们提供了有关稳定性，解决方案非唯一性和与LSC的联系的有趣讨论。然后，提出了一个新模型，称为最小体积软K-均值（MVSKM），以解决解决方案的非唯一性问题。最后，实验结果支持我们的理论结果。
This paper presents an algorithm to solve the Soft k-Means problem globally. Unlike Fuzzy c-Means, Soft k-Means (SkM) has a matrix factorization-type objective and has been shown to have a close relation with the popular probability decomposition-type clustering methods, e.g., Left Stochastic Clustering (LSC). Though some work has been done for solving the Soft k-Means problem, they usually use an alternating minimization scheme or the projected gradient descent method, which cannot guarantee global optimality since the non-convexity of SkM. In this paper, we present a sufficient condition for a feasible solution of Soft k-Means problem to be globally optimal and show the output of the proposed algorithm satisfies it. Moreover, for the Soft k-Means problem, we provide interesting discussions on stability, solutions non-uniqueness, and connection with LSC. Then, a new model, named Minimal Volume Soft k-Means (MVSkM), is proposed to address the solutions non-uniqueness issue. Finally, experimental results support our theoretical results.
