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

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

作　　者：范敏[1] 王芬[1] 李泽明[1] 李志勇[2] 张晓波[2] 

机构地区：[1]重庆大学自动化学院,重庆400030 [2]国网重庆市电力公司江北供电分公司,重庆401147

出　　处：《重庆大学学报（自然科学版）》2015年第6期147-152,共6页Journal of Chongqing University

基　　金：国家电网公司科技资助项目(SGZQJB00FZJS1400341);重庆市科技攻关资助项目(CSTC2012GG-YYJS40008)~~

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

关 键 词：谱聚类 K近邻 稀疏矩阵 自适应 快速算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]