基于快速地标采样的大规模谱聚类算法

来源：电子与信息学报杂志2017年第2期北京时间：

作者：叶茂, 刘文芬

摘要：为避免传统谱聚类算法高复杂度的应用局限，基于地标表示的谱聚类算法利用地标点与数据集各点间的相似度矩阵，有效降低了谱嵌入的计算复杂度。在大数据集情况下，现有的随机抽取地标点的方法会影响聚类结果的稳定性，k均值中心点方法面临收敛时间未知、反复读取数据的问题。该文将近似奇异值分解应用于基于地标点的谱聚类，设计了一种快速地标点采样算法。该算法利用由近似奇异向量矩阵行向量的长度计算的抽样概率来进行抽样，同随机抽样策略相比，保证了聚类结果的稳定性和精度，同k均值中心点策略相比降低了算法复杂度。同时从理论上分析了抽样结果对原始数据的信息保持性，并对算法的性能进行了实验验证。

关键词：地标点采样, 大数据, 谱聚类, 近似奇异值分解

基金资助：国家973计划(2012CB315905)， 国家自然科学基金(61502527, 61379150)