On Robustness of Kernel Clustering
On Robustness of Kernel Clustering
复制标题
论核聚类的鲁棒性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Purnamrita Sarkar
中科院分区：
文献类型：
--
作者：
Bowei Yan;Purnamrita Sarkar
聚类是机器学习和统计学中最重要的无监督问题之一。在众多现有算法中，核k-means算法由于其发现非线性聚类边界的能力和其固有的简单性而引起了广泛的研究关注。核k-means方法主要有两种：核矩阵的SVD和凸松弛。尽管注意核聚类已收到来自理论和应用季度，不太知道的方法的鲁棒性。在本文中，我们首先介绍了一个半定规划松弛核聚类问题，然后证明了在适当的模型规格，K-SVD和SDP方法是一致的限制，虽然SDP是强一致的，即实现精确的恢复，而K-SVD是弱一致的，即错误分类的节点的分数为零。
Clustering is one of the most important unsupervised problems in machine learning and statistics. Among many existing algorithms, kernel k-means has drawn much research attention due to its ability to find non-linear cluster boundaries and its inherent simplicity. There are two main approaches for kernel k-means: SVD of the kernel matrix and convex relaxations. Despite the attention kernel clustering has received both from theoretical and applied quarters, not much is known about robustness of the methods. In this paper we first introduce a semidefinite programming relaxation for the kernel clustering problem, then prove that under a suitable model specification, both the K-SVD and SDP approaches are consistent in the limit, albeit SDP is strongly consistent, i.e. achieves exact recovery, whereas K-SVD is weakly consistent, i.e. the fraction of misclassified nodes vanish.