A new theoretical framework for K-means-type clustering
A new theoretical framework for K-means-type clustering
复制标题
K-means型聚类的新理论框架
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Yu Xia
中科院分区：
文献类型：
--
作者：
Jiming Peng;Yu Xia
最基本的聚类问题之一是基于最小平方和（MSSC）将n个点分配到k个聚类中，这是已知的NP-难问题。在本文中，通过使用矩阵参数，我们首先模型MSSC作为一个所谓的0-1半定规划（SDP）。经典的K-means算法可以被解释为一种特殊的算法，用于底层的0-1 SDP。此外，0-1 SDP模型可以进一步近似的松弛和多项式可解的线性和半定规划。这为解决MSSC开辟了新的途径。0-1 SDP模型不仅适用于MSSC，也适用于其他集群场景。特别是，我们表明，最近提出的归一化k-割和谱聚类也可以嵌入到0-1 SDP模型中的各种核空间。
One of the fundamental clustering problems is to assign n points into k clusters based on the minimal sum-of-squares(MSSC), which is known to be NP-hard. In this paper, by using matrix arguments, we first model MSSC as a so-called 0-1 semidefinite programming (SDP). The classical K-means algorithm can be interpreted as a special heuristics for the underlying 0-1 SDP. Moreover, the 0-1 SDP model can be further approximated by the relaxed and polynomially solvable linear and semidefinite programming. This opens new avenues for solving MSSC. The 0-1 SDP model can be applied not only to MSSC, but also to other scenarios of clustering as well. In particular, we show that the recently proposed normalized k-cut and spectral clustering can also be embedded into the 0-1 SDP model in various kernel spaces.