The Ratio-Cut Polytope and K-Means Clustering
The Ratio-Cut Polytope and K-Means Clustering
复制标题
比率切割多面体和 K 均值聚类
DOI：
10.1137/20m1348601
复制
发表时间：
2022
影响因子：
3.1
通讯作者：
Khajavirad, Aida
中科院分区：
文献类型：
--
作者：
De Rosa, Antonio;Khajavirad, Aida
我们引入了比率割多面体，定义为对应于至多簇中所有点划分的比率割向量的凸船体。该多面体与K均值聚类、谱聚类等聚类问题的可行域的凸船体密切相关。研究了比例割多面体的面结构，并导出了几类定义面的不等式。然后，我们考虑了K-means聚类问题，提出了一种新的线性规划（LP）松弛算法，并针对两个聚类的情形，给出了LP松弛算法能够精确恢复聚类的充分条件。也就是说，我们考虑随机球模型，一个流行的生成模型的K-均值聚类，我们表明，如果聚类中心之间的分离距离满足，那么LP松弛恢复种植集群的概率很高。这是对K均值聚类的LP松弛的唯一现有恢复保证的重大改进，该恢复保证声明当且仅当恢复可能具有高概率。我们的数值实验表明，建议的LP松弛显着优于一个流行的半定规划松弛恢复种植集群。
We introduce the ratio-cut polytope defined as the convex hull of ratio-cut vectors corresponding to all partitions ofpoints ininto at mostclusters. This polytope is closely related to the convex hull of the feasible region of a number of clustering problems such as K-means clustering and spectral clustering. We study the facial structure of the ratio-cut polytope and derive several types of facet-defining inequalities. We then consider the problem of K-means clustering and introduce a novel linear programming (LP) relaxation for it. Subsequently, we focus on the case of two clusters and derive sufficient condition under which the proposed LP relaxation recovers the underlying clusters exactly. Namely, we consider the stochastic ball model, a popular generative model for K-means clustering, and we show that if the separation distance between cluster centers satisfies, then the LP relaxation recovers the planted clusters with high probability. This is a major improvement over the only existing recovery guarantee for an LP relaxation of K-means clustering stating that recovery is possible with high probability if and only if. Our numerical experiments indicate that the proposed LP relaxation significantly outperforms a popular semidefinite programming relaxation in recovering the planted clusters.
登录
查看更多内容
DOI：
--
发表时间：
2019
期刊：
Soft Computing - A Fusion of Foundations, Methodologies and Applications
影响因子：
--
作者：
Francesca Marzi;F. Rossi;S. Smriglio
通讯作者：
S. Smriglio
澳大利亚国立大学数学分析中心混沌小型会议论文集
DOI：
--
发表时间：
1991
期刊：
影响因子：
--
作者：
N. Joshi;R. Dewar
通讯作者：
R. Dewar
影响因子：
2.5
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming
DOI：
10.1287/moor.2022.1282
发表时间：
2020
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Alberto Del Pia;Aida Khajavirad;Dmitriy Kunisky
通讯作者：
Dmitriy Kunisky
K-means型聚类的新理论框架
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Jiming Peng;Yu Xia
通讯作者：
Yu Xia