Beyond the Nystrom Approximation: Speeding up Spectral Clustering using Uniform Sampling and Weighted Kernel k-means
Beyond the Nystrom Approximation: Speeding up Spectral Clustering using Uniform Sampling and Weighted Kernel k-means
复制标题
DOI：
10.24963/ijcai.2017/347
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Mahesh Mohan;C. Monteleoni
中科院分区：
文献类型：
--
作者：
Mahesh Mohan;C. Monteleoni
在本文中，我们提出了一个基于以下简单方案的谱聚类框架：对输入点的子集进行采样，使用加权核 k 均值（Dhillon 等人，2004 年）计算采样子集的聚类，并使用生成的中心来计算剩余数据点的聚类。对于点不放回地随机均匀采样的情况，我们表明所需的样本数量主要取决于簇的数量和核空间中点集的直径。实验表明，所提出的框架在精度和计算时间方面都优于基于 Nystrom 近似的方法。
In this paper we present a framework for spectral clustering based on the following simple scheme: sample a subset of the input points, compute the clusters for the sampled subset using weighted kernel k-means (Dhillon et al. 2004) and use the resulting centers to compute a clustering for the remaining data points. For the case where the points are sampled uniformly at random without replacement, we show that the number of samples required depends mainly on the number of clusters and the diameter of the set of points in the kernel space. Experiments show that the proposed framework outperforms the approaches based on the Nystrom approximation both in terms of accuracy and computation time.