Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering
Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering
复制标题
DOI：
--
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Yubo Zhuang;Xiaohui Chen;Yun Yang
中科院分区：
文献类型：
--
作者：
Yubo Zhuang;Xiaohui Chen;Yun Yang
半定规划（SDP）是一个强大的工具，用于解决各种各样的计算困难的问题，如聚类。尽管有很高的准确性，半定的程序在实践中往往太慢，在大型（甚至中等）数据集上的可扩展性差。在本文中，我们介绍了一个线性时间复杂度算法近似的SDP放松$K$-均值聚类。所提出的草图和升降机（SL）的方法解决了一个二次采样数据集上的SDP，然后传播的解决方案的所有数据点的最近的质心舍入过程。结果表明，SL的方法享有类似的确切的恢复阈值的$K$-意味着SDP的完整的数据集，这是已知的高斯混合模型下的信息理论紧密。SL方法可以自适应增强的理论性能时，集群大小是不平衡的。我们的模拟实验表明，所提出的方法的统计精度优于国家的最先进的快速聚类算法，而不会牺牲太多的计算效率，并与原来的$K$-means SDP大大减少运行时间。
Semidefinite programming (SDP) is a powerful tool for tackling a wide range of computationally hard problems such as clustering. Despite the high accuracy, semidefinite programs are often too slow in practice with poor scalability on large (or even moderate) datasets. In this paper, we introduce a linear time complexity algorithm for approximating an SDP relaxed $K$-means clustering. The proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset and then propagates the solution to all data points by a nearest-centroid rounding procedure. It is shown that the SL approach enjoys a similar exact recovery threshold as the $K$-means SDP on the full dataset, which is known to be information-theoretically tight under the Gaussian mixture model. The SL method can be made adaptive with enhanced theoretic properties when the cluster sizes are unbalanced. Our simulation experiments demonstrate that the statistical accuracy of the proposed method outperforms state-of-the-art fast clustering algorithms without sacrificing too much computational efficiency, and is comparable to the original $K$-means SDP with substantially reduced runtime.