K近邻的自适应谱聚类快速算法

谱聚类算法建立在谱图划分理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。然而,谱聚类算法涉及如何选取合适的尺度参数σ构造相似度矩阵的问题。并且,在处理大规模数据集时,聚类的过程需要较大的时间和内存开销。研究从构造相似度矩阵入手,以传统NJW算法为基础,提出一种基于K近邻的自适应谱聚类快速算法FA-SC。该算法能自动确定尺度参数σ;同时,对输入数据集分块处理,并用基于K近邻的稀疏相似度矩阵保存样本信息,减少计算的内存开销,提高了运行速度。通过实验,与传统谱聚类算法比较,FA-SC算法在人工数据集和UCI数据集上能够取得更好的聚类效果。

A fast algorithm for adaptive spectral clustering based on K-nearest neighbors

Based on spectral partition theory, spectral clustering algorithms are effective to solve the clustering of arbitrary sphere of sample spaces, and they can converge to global optimal solution. However, spectral clustering algorithms have to adopt the appropriate scaling parameter to calculate the whole similarity matrix, which may have a great impact on the clustering results. Moreover, when the number of data instances is large, computational complexity and memory use of the algorithm will greatly increase. So, we propose a fast algorithm for adaptive spectral clustering based on K-nearest neighbors, which can choose the scaling parameter automatically. Meantime, we divide the data set into different blocks and compute it separately. We also construct sparse matrix via retaining nearest neighbors to overcome the computational and the memory difficulties. Compared with traditional spectral clustering algorithms, experimental results show this algorithm can achieve better clustering effect on artificial datasets and UCI public databases.