徐航帆，刘 丛，唐坚刚，彭敦陆

(上海理工大学 光电信息与计算机工程学院,上海 200082)

现今世界数据量爆炸增长，对大数据进行高效地分析将在各行各业起到关键性作用。聚类分析[1]是一种无监督学习方法，也是数据挖掘和机器学习中一个重要的研究方向。聚类是指将数据在不需要先验知识的情况下根据某种相似度划分为多个簇的过程。传统的聚类算法，例如K-means算法[2]具有简单高效的特点，在球形结构的数据上有着较高的聚类精确度。但是，其缺乏处理复杂结构数据的能力[3]。当样本空间为非凸时，K-means算法往往达不到理想的效果[4]。

为了能在任意形状的样本空间上聚类，且收敛于全局最优解，研究人员开始研究新型的聚类算法，也被称为谱聚类[5]算法(Spectral Clustering Algorithm，SC)。谱图理论[6]是该算法的理论基础，其本质是将聚类问题转化为图的最优划分问题。近几十年来，研究人员提出了多种谱聚类算法，例如Ratio Cut算法[7]和Normalized Cut算法[8]。这两种算法将数据转换为基于相似性的加权无向图， 然后通过图优化算法进行求解。文献[9]提出了NJW算法，该算法是一种应用比较广泛的谱聚类算法。然而谱聚类算法在面对大规模数据集时，其构建相似度矩阵所需的空间复杂度(O(n2))和拉普拉斯矩阵特征分解所需的时间复杂度(O(n3))十分庞大，产生的计算成本将难以承受。

为了克服谱聚类的在大数据集上的可扩展性问题，一些加速谱聚类的算法被提出来，其中最自然的想法就是降低拉普拉斯矩阵的特征分解时间。……