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

叶 茂 刘文芬



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

叶 茂*刘文芬

(解放军信息工程大学 郑州 450002) (数学工程与先进计算国家重点实验室 郑州 450002)

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

地标点采样；大数据；谱聚类；近似奇异值分解

1 引言

聚类分析可将数据集按照相似性分成子集，使得人们能根据分类结果找出数据的内在联系，是模式识别、数据挖掘的主要方法之一[1]。传统聚类算法(如均值等)在非凸数据集上效果不佳，这使得适用于非凸数据集和能检测线性不可分簇的谱聚类算法[2,3]成为了聚类分析中的研究热点。但是，传统的谱聚类算法涉及构造相似度矩阵和对相应的拉普拉斯矩阵特征分解，需要的空间复杂度和的时间复杂度，这对于大规模数据集来说是难以承受的计算负担。

为提升谱聚类算法的扩展性，一个自然的想法就是设计可以减少特征分解复杂度的算法。2004年，Fowlkes等人[4]改进Nyström方法并将其用于谱聚类，实现了快速近似特征分解。随后，Li等人[5,6]又用近似奇异值分解(Singular Value Decomposition, SVD)方法提升了Nyström方法中特征分解的效率。而丁世飞等人[7]则设计了一种自适应采样的方法，改进了Nyström谱聚类的聚类效果。此外，Yan等人[8]还提出了一个快速近似谱聚类的框架：先选择代表点，然后对代表点进行谱聚类，并将分类关系扩展到与代表点关联的其他点上。

2011年，Chen等人[9]提出了基于地标点的谱聚类(Landmark-based Spectral Clustering, LSC)算法，指出该方法适用于大规模数据集，并且性能要比Nyström方法和Yan的方法[8]好，并在随后给出了相关理论分析[10]。LSC算法通过数据集点与地标点之间的相似度矩阵的乘积来近似得到整体的相似度矩阵，然后利用近似性质实现快速特征分解。但该方法用随机采样确定地标点，抽样结果不稳定，在大数据集时容易出现样本点集中于某一区域的情况。

当前，随机映射由于可在降低数据规模的同时保持大部分原始信息而被广泛用于聚类算法中。本文利用随机映射得到近似SVD算法，然后由分解得到的近似奇异向量矩阵的行向量长度确定各点在数据集中的权重并计算抽样概率，以此得到快速抽样算法。通过理论分析，得出该抽样算法的抽样误差被限制在一个较小的界内，保证了抽样结果对原始数据的信息保持性。实验结果表明基于该抽样方法的LSC算法聚类结果要比基于随机抽样的算法稳定且聚类精度更高，比基于均值中心点的方法运行速度快，从而验证了新方法的性能。

2 基础知识

本节先给出本文所用的一些矩阵相关符号，然后简述LSC算法和应用于快速采样的近似SVD算法。

2.1 矩阵的相关符号

2.2 基于地标表示的谱聚类算法

LSC算法[9]主要思想是通过地标点来实现相似度矩阵的快速构造和特征分解。具体算法流程如表1的算法1所示。

表1 LSC算法

从算法流程可以看出，步骤3实现了相似度矩阵的近似构造：对计算右奇异向量矩阵，此过程等价于对矩阵进行特征分解得到特征向量。由于，所以相似度矩阵分解的时间复杂度从的特征分解时间减少到了的SVD时间，空间复杂度从存储所需的减少到了存储所需的，时间、空间复杂度均比原始谱聚类算法显著减少。

2.3 近似SVD算法

基于矩阵重构的采样始于1988年Frieze等人[14]的开创性成果：给定矩阵，通过与列向量欧几里得长度平方成比例的概率抽样少的列，可快速得到原始矩阵的低秩近似。随后，文献[15,16]以与奇异向量矩阵的整行长度成比例的概率抽样矩阵的列，使得近似效果得到明显提升。2014年，Boutsidis等人[17]通过基于随机映射的近似SVD算法[18]来改进抽样算法效率，并得到了渐近最优抽样算法。本文所用的快速采样算法就是基于近似SVD算法得到的，SVD具体流程如表2的算法2所示。

表2 近似SVD算法

算法2的思想在于用随机映射对数据进行压缩，并使得在降低矩阵规模后仍保持原始矩阵的主要信息。Sarlos[19]指出，经过随机映射压缩数据，若压缩后数据规模满足特定参数，则该近似SVD算法所得到的近似奇异向量在最优低秩近似上能保持与精确的奇异向量接近的效果。

引理1[19]令,是在2.1节定义的投影算子。如果,，其中是满足算法2所要求的矩阵，且，则至少以的概率，有

成立。

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

相比于传统谱聚类算法，LSC算法在时间和空间复杂度上均有很大优势，并且在聚类效果上也令人满意。作为算法的关键，地标点的选取在很大程度上影响了聚类效果。常用的方式是均匀随机采样，在大规模数据集上随机抽样的不稳定性很可能会导致所抽样本点集中于某一区域，这将使得算法聚类效果变差。

LSC算法的思想是通过地标点的线性组合来实现所有数据点的表示，然后通过地标点与数据点的相似性度量来给出各个数据点之间的相似性度量，因此地标点的特征在于“代表性”。文献[15,16]提出了一种可抽取具有“代表性”数据点的方法：采用以与奇异向量矩阵整行长度平方成比例的概率抽样数据，使得较少数量的样本可以构造原始数据矩阵的一个低秩近似。在此基础上，本文采用近似SVD算法，在降低采样过程时间复杂度的同时，得到与精确SVD相近的采样结果，产生有“代表性”的点。本节首先给出基于近似SVD的快速采样算法，然后分析通过该算法得到的数据样本点在形成原始数据矩阵低秩近似时的误差，最后给出完整的基于快速地标点采样的谱聚类算法。

3.1 基于近似SVD的快速采样算法及误差分析

根据矩阵SVD分解结果进行抽样的相关理论分析已由文献[15]给出，而虽然文献[17,19]指出基于近似SVD分解结果进行抽样可使矩阵低秩近似的误差保持在小的界内，但并没有给出严格证明，本小节给出一个简洁的证明。

首先给出基于近似SVD的抽样算法3如表3所示。

表3 近似SVD的抽样算法

成立。

从定理1可知，对于通过算法3所得到的矩阵的行样本，其所能得到的最优原始矩阵近似误差与相差一个较小的因子，保持了原始矩阵的大部分信息。在证明定理前，先给出两个相关的引理：

引理2[20]令,且,是由算法3依据产生的抽样矩阵。若抽样个数，则对于，至少以的概率，有

引理2指出，如果抽样规模足够，算法3通过列正交矩阵产生的抽样矩阵，作用于原矩阵后仍得到奇异值接近于1的矩阵，即将一个列正交矩阵抽样为一个近似的列正交矩阵。

引理3[11]令，任意是算法3步骤1所需的矩阵，对于算法3所产生的抽样矩阵，对于任意，任意，至少以的概率，有

成立。

引理3说明根据算法3的抽样方法，对任意矩阵抽样并适当调整样本尺寸后，所产生的矩阵与原始矩阵在Frobenius范数平方上接近，即该抽样算法对矩阵的Frobenius范数没有产生太大的影响。

利用上述引理，给出定理1的证明：

利用矩阵的近似奇异向量矩阵，将其分解为：，则有

(3)

而由性质1可知

(5)

定理1表明，采用基于近似SVD的抽样可以保证抽样误差在特定的界内，这使得采样的样本具有较好的代表性。因此，利用该方法所得到的采样样本，其与数据点形成的相似度矩阵能较好地描述数据之间的关系。

3.2 基于快速地标点采样的谱聚类算法

3.1节从矩阵低秩近似误差的角度在理论上分析了基于近似SVD的抽样样本的代表性，根据3.1节结论，我们提出了使用基于近似SVD的抽样方法来采样地标点的LSC算法，称为基于快速地标点采样的谱聚类算法(Landmark-based Spectral Clustering with Fast Sampling, LSC-FS)，该算法的具体流程如表4所示。

LSC-FS算法主要分为地标点采样和基于地标点的谱聚类两部分，因为基于地标点的谱聚类算法复杂度已经在2.2节给出，所以我们主要对地标点采样部分进行算法复杂度分析。

表4 基于快速地标点采样的谱聚类算法(LSC-FS)

对于抽样过程，第1步是计算矩阵的近似奇异向量。根据算法2的计算流程，计算近似奇异向量的时间为，其中算法2步骤2矩阵乘积需的时间，步骤3列标准正交化需，步骤4矩阵乘积和SVD需。抽样算法剩余步骤为确定抽样概率并进行抽样，计算复杂度为。由于在实际中常出现且，所以本文所设计的新算法在采样阶段的计算复杂度为。

地标点的生成方法常见的是随机采样，而另外一种地标点的生成方法是用均值的中心点代替。如果用均值的中心点作为地标点，其生成过程计算复杂度为，其中为迭代次数。由定理1的要求可知，，所以新算法的采样过程计算量通常要比基于均值的采样过程要小(当时)。并且当数据规模极大，超出系统的内存时，均值聚类算法需要不断地执行数据读取操作，而新算法的抽样过程对数据的读取次数至多需要3次，更高效。

4 实验结果与分析

本节进行实验分析，对算法的有效性和运行时间两类指标进行评估。

我们对两个较大数据集进行实验。第1个被称为MNIST，是一个手写数字的数据集1)MNIST数据可从http://yann.lecun.com/exdb/mnist/上下载。该数据集共有70000个对象，每个对象是像素的属于数字0到9的图像，其中每个像素是从中取出的整数。实验时，我们将每个对象视为784维的向量。第2个被称为RCV1，是路透社的新闻文档集。为方便实验对比，我们采用与文献[21]一致的处理方式，对其中的103类共计193844个有47236个特征的文档进行聚类分析。实验算法在英特尔Core i7-4790 @ 3.60 GHz CPU, 16 GB内存的计算机上运行，实验代码在MATLAB环境下编写。

为验证新算法的聚类有效性和效率，本文对原始谱聚类(记为SC), Nyström近似谱聚类(记为Nyström)、基于随机采样的地标点谱聚类(记为LSC-R)和基于均值中心的地标点谱聚类(记为LSC-K)与本文算法(记为LSC-FS)进行实验比较。对于Nyström算法，我们采用文献[21]给出的带正交化的MATLAB代码，对于LSC算法，我们采用文献[9]给出的实现代码。

在实验过程中，通过改变抽样个数来比较不同个数的采样点对实验结果的影响。为避免算法中随机化过程对实验结果的影响，对每一个采样点数，各个算法都独立进行20次并取平均值作为算法结果；为比较的公平性，所有相似度矩阵构造过程中的近邻个数都选为5。

4.1 评价指标

算法有效性描述的是聚类算法对数据进行划分的正确程度，通过对算法聚类结果和预定义的类标签进行相似性比对得出。本文用聚类精确性(Cluster Accuracy, CA)[22]和标准化互信息(Normalized Mutual Information, NMI)[23]两种指标。

CA度量了聚类结果中被正确划分到预定义类标签的数据点的比例，按式(7)计算：

其中，是聚类结果中簇的个数，是数据量，是第个簇，表示聚类结果中第个簇中标签所对应的样本点个数的最大值。从CA定义可知CA越大，聚类效果越好，CA最大值为1。

NMI也评估了聚类算法的划分质量。将各个簇所占数据总量的比率视为随机变量取值该簇标签的概率，那么可得到两个概率分布，NMI度量的是两个概率分布之间共享的信息量。将两个随机变量分别记为和，按式(8)来计算NMI：

4.2 实验结果

4种快速谱聚类算法加上原始谱聚类算法在两个数据集上的性能表现如表5所示，从左往右依次从运行时间(s), CA(%)，NMI(%)3个方面进行对比。为便于比较，4种快速算法的抽样个数均设为1000。需要指出的是，由于原始谱聚类算法在RCV1上运行时间太久，所以只运行了两次，不求方差。

从表5可以看出，在聚类有效性方面，本文算法的聚类精度要比LSC-R算法和Nyström近似算法要高，比LSC-K算法低；在算法效率方面，新算法比LSC-K算法运行时间明显少，并且随着数据集及数据维数的增大，运行时间并没有比LSC-R算法差别很大。对算法有效性和效率综合考虑，虽然LSC-K算法在聚类效果上来讲表现很好，但随着数据集及其维数的增大，该算法将会越来越慢；从表中的方差项中可以看出新算法通常比LSC-R算法要更为稳定。因此，从聚类效果、算法效率及稳定性方面均衡考虑，本文算法有优势。从算法流程可以看出，算法还可以较好地实现并行化处理，这使得新算法更有吸引力。

为了研究抽样个数对各个快速谱聚类方法的影响，我们在MNIST数据集上固定其他参数，令抽样个数从100到1100每隔100进行变化，实验结果如图1-图3所示。

从图1，图2中可以看出，不同于Nyström近似算法有效性指标变化不大的情况，本文算法的聚类效果随着抽样个数的增多而变好。这说明地标点个数也是新算法的重要参数之一，地标点个数越多，本文算法能获得更多的数据点间的关系信息，聚类效果越好。再结合图3可知，在保持运行时间相差不大的情况下，本文算法比LSC-R算法的聚类效果要好；虽然聚类效果没有LSC-K算法好，但新算法的运行时间要短得多。因此新算法在效率和聚类效果上取得了较好的平衡。

表5 不同聚类算法的性能对比

5 结束语

基于地标表示的谱聚类算法可通过地标点快速实现相似度矩阵的构造和相应拉普拉斯矩阵的分解，是一种适用于大数据集的谱聚类算法。针对随机抽样地标点效果不稳定，用均值中心作为地标点运行时间长的问题，本文设计了一种快速地标点采样算法。本文算法基于近似奇异值分解，可使每个地标点的抽样概率对应于其在数据集中的权重。本文不仅从理论上分析了该抽样算法结果对原始信息的保持性，还从公开数据集上验证了新算法在效率和有效性上的优势。

[1] 何清, 李宁, 罗文娟, 等. 大数据下的机器学习算法综述[J]. 模式识别与人工智能, 2014, 27(4): 327-336.

HE Qing, LI Ning, LUO Wenjuan,. A survey of machine learning algorithms for big data[J]., 2014, 27(4): 327-336.

[2] DING S, JIA H, ZHANG L,. Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J]., 2014, 24(1): 211-219. doi: 10.1007/s00521-012-1207-8.

[3] NG A Y, JORDAN M I, and WEISS Y. On spectral clustering: Analysis and an algorithm[C]. Neural Information Processing Systems: Natural and Synthetic, Vancouver, Canada, 2001: 849-856.

[4] FOWLKES C, BELONGIE S, CHUNG F,. Spectral grouping using the Nystrom method[J]., 2004, 26(2): 214-225. doi: 10.1109/TPAMI.2004.1262185.

[5] LI M, KWOK J T, and LU B L. Making large-scale Nyström approximation possible[C]. Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010: 631-638.

[6] LI M, BI W, KWORK J T,. Large-scale Nyström kernel matrix approximation using randomized SVD[J]., 2015, 26(1): 152-164. doi: 10.1109/TNNLS.2014.2359798.

[7] 丁世飞, 贾洪杰, 史忠植. 基于自适应Nyström 采样的大数据谱聚类算法[J]. 软件学报, 2014, 25(9): 2037-2049. doi: 10.13328/j.cnki.jos.004643.

DING Shifei, JIA Hongjie, and SHI Zhongzhi. Spectral clustering algorithm based on adaptive Nyström sampling for big data analysis[J]., 2014, 25(9): 2037-2049.doi: 10.13328/j.cnki.jos.004643.

[8] YAN D, HUANG L, and JORDAN M I. Fast approximate spectral clustering[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 907-916. doi: 10.1145/1557019.1557118.

[9] CHEN X and CAI D. Large scale spectral clustering with landmark-based representation[C]. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 313-318.

[10] CAI D and CHEN X. Large scale spectral clustering via landmark-based sparse representation[J]., 2015, 45(8): 1669-1680. doi: 10.1109/TCYB. 2014.2358564.

[11] BOUTSIDIS C, ZOUZIAS A, MAHONEY M W,. Randomized dimensionality reduction for-means clustering[J]., 2015, 61(2): 1045-1062. doi: 10.1109/TIT.2014.2375327.

[12] COHEN M, ELDER S, MUSCO C,. Dimensionality reduction for-means clustering and low rank approximation[C]. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, OR, USA, 2015: 163-172. doi: 10.1145/2746539.2746569.

[13] KHOA N L D and CHAWLA S. A scalable approach to spectral clustering with SDD solvers[J]., 2015, 44(2): 289-308. doi: 10.1007/ s10844-013-0285-0.

[14] FRIEZE A, KANNAN R, and VEMPALA S. Fast Monte-Carlo algorithms for finding low-rank approximations[C]. Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 1998: 370-378. doi: 10.1109/SFCS. 1998.743487.

[15] DRINEAS P, MAHONEY M W, and MUTHUKRISHNAN S. Sampling algorithms for l2 regression and applications[C]. Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, Miami, Florida, USA, 2006: 1127-1136.

[16] DRINES P, MAHONEY M W, and MUTHUKRISHNAN S. Subspace sampling and relative-error matrix approximation: Column-based methods[C]. 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 10th International Workshop on Randomization and Computation, Barcelona, Spain, 2006: 316-326. doi: 10.1007/11830924_30.

[17] BOUTSIDIS C, DRINEAS P, and MAGDON-ISMAIL M. Near-optimal column-based matrix reconstruction [J]., 2014, 43(2): 687-717. doi: 10.1137/12086755X.

[18] HALKO N, MARTINSSON P G, and TROPP J A. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions[J]., 2011, 53(2): 217-288. doi: 10.1137/090771806.

[19] SARLOIS T. Improved approximation algorithms for large matrices via random projections[C]. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, USA, 2006: 143-152. doi: 10.1109/FOCS.2006.37.

[20] MAGDON-ISMAIL M. Row sampling for matrix algorithms via a non-commutative Bernstein bound[OL]. http:// arxiv.org/ abs/1008.0587, 2015.10.

[21] CHEN W Y, SONG Y, BAI H,. Parallel spectral clustering in distributed systems[J]., 2011, 33(3): 568-586. doi: 10.1109/TPAMI.2010.88.

[22] AFAHAD A, ALSHATRI N, TARI Z,. A survey of clustering algorithms for big data: Taxonomy and empirical analysis[J]., 2014, 2(3): 267-279. doi: 10.1109/TETC. 2014.2330519.

[23] STREHL A and GHOSH J. Cluster ensemblesA knowledge reuse framework for combining multiple partitions[J]., 2003, 3: 583-617. doi: 10.1162/153244303321897735.

Large Scale Spectral Clustering Based on Fast Landmark Sampling

YE Mao LIU Wenfen

(,450002,) (,450002,)

The applicability of traditional spectral clustering is limited by its high complexity in large-scale data sets. Through construction of affinity matrix between landmark points and data points, the Landmark-based Spectral Clustering (LSC) algorithm can significantly reduce the computational complexity of spectral embedding. It is vital for clustering results to apply the suitable strategies of the generation of landmark points. While considering big data problems, the existing generation strategies of landmark points face some deficiencies: the unstable results of random sampling, along with the unknown convergence time and the repeatability of data reading in-means centers method. In this paper, a rapid landmark-sampling spectral clustering algorithm based on the approximate singular value decomposition is designed, which makes the sampling probability of each landmark point decided by the row norm of the approximate singular vector matrix. Compared with LSC algorithm based on random sampling, the clustering result of new algorithm is more stable and accurate; compared with LSC algorithm based on-means centers, the new algorithm reduces the computational complexity. Moreover, the preservation of information in original data is analyzed for the landmark-sampling results theoretically. At the same time, the performance of new approach is verified by the experiments in some public data sets.

Landmark sampling; Big data; Spectral clustering; Approximate singular value decomposition

TP181

A

1009-5896(2017)02-0278-07

10.11999/JEIT160260

2016-03-21；改回日期：2016-07-18，

2016-09-30

叶茂 yemaoxxgc@163.com

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

The National 973 Program of China (2012CB315905), The National Natural Science Foundation of China (61502527, 61379150)

叶 茂： 男，1988年生，博士生，研究方向为数据挖掘.

刘文芬： 女，1965 年生，教授，博士生导师，研究方向包括概率统计、网络通信、信息安全.