%0 Journal Article
%T 求解大规模谱聚类的近似加权核k-means算法
%A 贾洪杰？
%A 丁世飞？
%A 史忠植？
%J 软件学报
%P 2836-2846
%D 2015
%R 10.13328/j.cnki.jos.004888
%X 谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用rayleigh熵的性质,通过计算laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是o(n2),对laplacian矩阵特征分解的时间复杂度一般为o(n3),这样的复杂度在处理大规模数据时是无法接受的.理论证明,normalizedcut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化normalizedcut的目标函数,这就避免了对laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是o(n2).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.
%K 谱聚类
%K 迹最大化
%K 加权核k-means
%K 近似核矩阵
%K 大数据
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=4888&flag=1