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

• 作者: 丁世飞 史忠植 贾洪杰
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 谱聚类 迹最大化 加权核k-means 近似核矩阵 大数据
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: 大数据时代的机器学习研究专刊
• 页码范围: 2836-2846
• 页数: 11页
• 分类号: TP181
• 字数: 9889字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004888

摘要

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用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算法是相似的,但是极大地减小了时间和空间复杂性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	史忠植	中国科学院计算技术研究所智能信息处理重点实验室	232	9166	52.0	89.0
2	丁世飞	中国矿业大学计算机科学与技术学院	83	2735	17.0	52.0
6	贾洪杰	中国矿业大学计算机科学与技术学院	3	64	3.0	3.0