求解大规模谱聚类的近似加权核k-means算法

来源：软件学报杂志2015年第11期北京时间：

作者：贾洪杰,丁世飞,史忠植

单位：贾洪杰，中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;中国科学院 计算技术研究所 智能信息处理重点实验室, 北京 10019011,丁世飞，中国矿业大学 计算机科学与技术学院, 江苏 徐州 221116;中国科学院 计算技术研究所 智能信息处理重点实验室, 北京 10019002,史忠植，中国科学院 计算技术研究所 智能信息处理重点实验室, 北京 10019003

摘要：谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n2),对Laplacian矩阵特征分解的时间复杂度一般为O(n3),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n2).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.

关键词：谱聚类;迹最大化;加权核k-means;近似核矩阵;大数据

基金资助：国家重点基础研究发展计划(973)(2013CB329502); 国家自然科学基金(61379101); 江苏省普通高校研究生科研创新计划(KYLX15_1442)