基于自适应Nystr?m采样的大数据谱聚类算法

• 作者: 丁世飞 史忠植 贾洪杰
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 大数据 谱聚类 特征分解 Nystr?m扩展 自适应采样
• 年，卷（期）: 2014,（9）
• 所属期刊栏目: 大数据分析专刊
• 页码范围: 2037-2049
• 页数: 13页
• 分类号: TP181
• 字数: 10984字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004643

摘要

面对结构复杂的数据集，谱聚类是一种灵活而有效的聚类方法，它基于谱图理论，通过将数据点映射到一个由特征向量构成的低维空间，优化数据的结构，得到令人满意的聚类结果.但在谱聚类的过程中，特征分解的计算复杂度通常为O(n3)，限制了谱聚类算法在大数据中的应用.Nystr?m扩展方法利用数据集中的部分抽样点，进行近似计算，逼近真实的特征空间，可以有效降低计算复杂度，为大数据谱聚类算法提供了新思路.抽样策略的选择对Nystr?m 扩展技术至关重要，设计了一种自适应的 Nystr?m 采样方法，每个数据点的抽样概率都会在一次采样完成后及时更新，而且从理论上证明了抽样误差会随着采样次数的增加呈指数下降.基于自适应的Nystr?m采样方法，提出一种适用于大数据的谱聚类算法，并对该算法的可行性和有效性进行了实验验证.

作者信息

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