申 锐，吴 睿

（1.山西交通职业技术学院，山西 晋中 030600；2.西安交通大学软件学院，陕西 西安 710061）

1 引言

随着科技与互联网的发展以及信息传输量的急速提高，以大数据为主要特性的网络结构日益凸显出来，TB 甚至PB 级的海量信息数据已经成为常态。但是网络在方便我们日常工作和丰富我们生活的同时，如何提取有价值的知识显得尤为重要。聚类能够根据数据特征，将相似特征数据进行归类，从而高效组织数据[1]。现有k-means 等聚类算法依赖于初始值的选取，并且基于欧氏距离和梯度下降进行的搜索常常使算法陷入局部最优，而基于非线性核距离且对任意形状样本集都具有全局最优解的谱聚类，成为近年研究热点[2]。

但是，传统的谱聚类算法涉及构造相似度矩阵和对相应的拉普拉斯矩阵特征分解，需要的空间复杂度和的时间复杂度对于大规模数据集来说是难以承受的计算负担[3]。为此，文献[4]通过计算数据的低维嵌入，提出基于拐点估计的谱聚类中心数自动确定方法，对分布复杂数据集的谱聚类效果较好；文献[5]通过在选取的核心点集上分组和谱聚类，并根据数据集与核心点集的一致性实现大数据谱聚类。文献[6]提出使用Nystro¨m 近似技术来避免计算整个相似性矩阵，加速大数据谱聚类；随后文献[7]又用近似奇异值分解方法提升了Nystro¨m 方法中特征分解的效率；而文献[8]则设计了一种自适应采样的方法，改进了Nystro¨m 谱聚类的聚类效果。文献[9]根据 Nystro¨m 误差界分析，采用集成Nystro¨m以牺牲数据计算准确性换来大数据谱聚类的快速计算，具有更快的收敛速度。……