spark框架优化的大规模谱聚类并行算法

(*通信作者电子邮箱wxiaol351@ 163. com)摘要:为解决谱聚类在大规模数据集上存在的计算耗时和无法聚类等性能瓶颈制约，提出了基于Spark技术的 大规模数据集谱聚类的并行化算法。首先，通过单向循环迭代优化相似矩阵的构建，避免重复计算；然后，通过位置变

换和标量乘法替换来优化Laplacian矩阵的构建与正规化，降低存储需求;最后，采用近似特征向量计算来进一步减少

计算量。不同测试数据集上的实验结果表明：随着测试数据集的规模增加，所提算法的单向循环迭代和近似特征值

计算的运行时间呈线性增长，增长缓慢,其近似特征向量计算与精确特征向量计算取得相近的聚类效果，并且算法在

大规模数据集上表现出良好的可扩展性。在获得较好的谱聚类性能的基础上，改进算法提高了运行效率，有效缓解

了谱聚类的计算耗时及无法聚类问题。关键词：大规模谱聚类；相似矩阵稀疏化；单向循环迭代;近似特征向量；分布式Spark并行计算中图分类号：TP181； TP311.13 文献标志码:ASpark framework based optimized large-scale spectral clustering parallel algorithmCUI Yixin\\ CHEN Xiaodong(Network and Information Center, Taiyuan Institute qf Technology, Taiyuan Shanxi 030008, China)Abstract： To solve the performance bottlenecks such as time-consuming computation and inability of clustering in

spectral clustering on large-scale datasets, a spectral clustering parallelization algorithm suitable for large-scale datasets was proposed based on Spark technology. Firstly, the similar matrices were constructed through one-way loop iteration to avoid double counting. Then, the construction and normalization of Laplacian matrices were optimized by position transformation and scalar multiplication replacement in order to reduce the storage requirements. Finally, the approximate eigenvector calculation

was used to further reduce the computational cost. The experimental results on different test datasets show that, as the size of test dataset increases, the proposed algorithm has the running time of one-way loop iteration and the approximate eigenvector calculation increased linearly with slow speed, the clustering effects o£ approximate eigenvector calculation are similar to those of exact eigenvector calculation, and the algorithm shows good extensibility on large-scale datasets. On the basis of obtaining

better spectral clustering performance, the improved algorithm increases operation efficiency, and effectively alleviates highcomputational cost and the problem o£ clustering.Key words： large-scale spectral clustering; similar matrix sparsification; one-way loop iteration; approximateeigenvector; distributed Spark parallel computingo引言谱聚类以非线性核距离进行图相似性分割,相比于传统 fc-means等基于欧氏距离的聚类算法,能够对非凸等任意形状

MapReduce框架并行优化谱聚类，聚类速率随数据规模的增

大呈现近似线性增长;张文杰等〔回在数据的初始聚类后采用

MapReduce框架并行地对数据进行\"-means细化聚类，实现

大数据集快速高效聚类;李晓瑜等以初始聚类缓解局部最

数据集实现全局最优解，成为近年研究热点,但随着大规 模数据集的普及,经典谱聚类的相似性计算和特征分解时间

优解问题，采用MapReduce模型对改进后算法进行并行实 现,算法获得较好的准确率和扩展性;刘鹏等利用轮廓系

开销和存储代价太高⑶，且随着数据规模的不断膨胀，计算

数及形态学相似距离改进聚类算法，并基于Spark框架实现

算法并行计算，具有较好计算效率和并行能力。性能瓶颈越来越突出。为此,基于采样核心点集⑷、基于加权核k均值⑸、基于 Nystrom近似技术⑷及其改进巾、基于共享近邻约束⑷等各

已有并行算法大多与主流Hadoop分布式文件系统

(Hadoop Distributed File System, HDFS) Spark 等的兼容性较

种改进的大规模数据集谱聚类算法被提出。近年，随着MapReduce、Hadoop及Spark等分布式并行框 架的兴起，大规模集并行谱聚类开始广泛应用。Jin等⑼以差为此，基于Spark并行框架，提出了用于大规模数据

集谱聚类的并行化算法,算法主要研究了相似矩阵的单向循

环构建、Laplacian矩阵的构建与正规化及近似特征向量计算收稿日期：2019-06-21；修回日期=2019-09-22；录用日期：2019-09-24。作者简介:崔艺馨(1981-),女，山西忻州人，实验师，硕士，主要研究方向:数据挖掘、计算机网络；陈晓东(1978-),男，河北唐山人，副 教授，博士，主要研究方向:计算机网络。第1期崔艺馨等:Spark框架优化的大规模谱聚类并行算法169等步骤的并行优化。实验结果验证了算法在大规模数据集下

良好聚类性能和可扩展性。1谱聚类并行优化1.1 Spark并行框架Spark 并行框架是 AMP 实验室(Algorithms Machines and People lab)为简化计算机集群程序的并行编写而设计，其对

相同数据的多次调用、资源任务的调度执行和节点并行通信

等底层内在操作都进行抽象，具有更高级API调用，其分布式

结构的灵活、编程接口的多样和容错性能的强大，使其适于高 性能迭代计算，通过节点内存分布式缓存计算和低延迟任务

启动减少磁盘的I/O时间。如图1所示为Spark并行计算的 运行框架，通常部署在数千节点之间，支持standalone、Yarn等 集群管理器。相对于Hadoop等并行架构,Spark框架在内存

中直接缓存中间结果，具有极大的运行速度和通用性能优势。图1 Spark并行框架示意图Fig. 1 Schematic diagram ofSpark parallel framework1.2单向迭代相似矩阵并行计算相似矩阵主要描述两样本的相似信息,为实现Spark并

行框架的优化计算，需要对数据进行合理划分，并行数据划分

时通常采用网络、KD( K-Dimensional)树及二叉树等方法。为

平衡各节点间的任务负载，提高有效数据的使用和相似度计 算的质量,对大规模数据集进行分块时采用依据数据对象的

二叉树索引网格划分，并进行二次扩展,算法采用自项而下的

二分法对数据格网进行分割,直到网络尺寸小于预设阈值,根 节点记录网络总大小及数据点数，各级子节点记录最小外包

矩形(Minimal Bounding Rectangle, MBR)值及其数据点。 Spark架构在进行并行计算时,统计网格点数，并遍历二叉树

节点，对于非平衡实际数据分布,先根据点将分区进行排序，

然后采用贪心算法重组集合，从而得到\"组分区样本。分区

不可避免地会将同一聚类数据分配到不同的二叉树节点，即

边界点划分问题,对此,在二叉树划分后,需进行二次划分扩

展,即对于每个分区,将边界扩展,使处于边界点的数据划分 到两个分块中，这样通过少量的计算增加获得更合理的数据 分块。在大规模数据集下,提出基于单向循环迭代的分布式相

似度并行计算方法,先完成节点内样本相似计算，再完成分区

间相似计算，在计算过程中主节点分区不参与,当前分区仅与 序号更大的分区样本进行单向相似计算，以避免重复计算，单

向循环迭代如图2所示。大规模数据集生成的稠密相似度矩阵对数据存储的开销

极大，为此，对其采用t近邻算法进行稀疏化。初始化 |石(a)初始分区内相似计算］轮迭代|分创Jg兰2| |分区3|2轮迭代I分耳画(b)循环迭代分区间相似计算 图2单向循环迭代相似度计算过程Fig. 2 One-way loop iterative similarity

calculation process1.3 Laplacian矩阵并行计算由相似矩阵W =

计算对角矩阵D = iA.J :ND“ =工叫\" ⑴

j则Laplacian矩阵L的构建及正规化为：L = D - W = D12 - L • D12

(2)传统并行构建矩阵L的方法首先计算相似矩阵W的行

元素和,然后同位置元素值相减，其计算和存储空间需求较

大。对矩阵》和W的元素分析发现，由于相似度定义中元素

与其自身的相似度为0,因此W的对角元素均为0,而Q的非

对角元素均为0,于是,首先并行计算W每行元素的和，得到

对角矩阵然后为W每行增加一个对角索引号，并将D中非

零对角元素添加到W矩阵的相应对角线位置;最后对W矩阵

每行非对角元素值根据索引号进行取反操作，则可以构建 Laplacian 矩阵。Laplacian矩阵L正规化过程的矩阵连乘复杂度很高，因

此,根据对角矩阵右乘某矩阵的操作等价于将对角线位置的

非零元素与该矩阵相应的行向量相乘，将式(2)中的矩阵连 乘以标量乘矩阵的方式进行并行优化,其过程如下。首先,根据式(2)计算后，将其对角元素值以数组

A(n-1/2)的形式发送到分布式节点中，在分布式节点内分

D 1/2 x Z和2/ x D 1/2两步完成L的正则化。O 12 xZ优化：如图3所示，各节点按其Z行号提取

A(.D~1/2)中对应的元素值进行相乘，各节点并行进行可快速

得到中间结果Q = D、 1/2 xLoAiL\\-ri ；=10 •■wln。220行元素相乘厶2一厂20£闷•■i-l W2n:0L„—rnW„1Wn2 ■•X•i—1数据分发|D厶-口DL、—％i=l节点疋\\DLe DLn-r„-d””w”2 ... d”加〜图3构建的中间过程示意Fig. 3 Schematic diagram of intermediate process of

constructingL' x Z) 1/2优化:如图4所示，其过程与图3相似,节点并

行地以其获得的Z'的行号提取Arr(.D~1/2)中对应的对角元

素值，并进行相乘，则得到z的正规化矩阵厶= r xD1/20170计算机应用第40卷实际应用中，为加速近似特征向量的求解，根据拉普拉

—c/iiWi2 …—t/nWi)?-i斯矩阵z = z -。\"勺“\y = d-1/2sd12的前 人个最大特征值对应的特征向量，然后对特征向量组成的矩

(=1dnn^nl—dnltWn2 ••- dnn^WniA 2 DLfi-r,

—dnWndn ■■- —dnWindii列元素乘［〉1Ai£>22阵进行式(3)标准化，以保证矩阵的正常聚类，最后通过

fc-means算法对标准化矩阵进行聚类，则得到的k个特征向量

0DLJJ—rn—dnnwni dni —dnnwnidn2 …□.与直接计算L矩阵的最小特征值对应向量是等价的⑷。0Dm节点1 …节点広对于矩阵S，最大特征值对应的特征向量的计算，设以向

量形式表示的目标函数为：图4 构建Lnorm并行化过程示意图Fig. 4Schematic diagram of parallelization process of

constructing ^normJ = max tr(yT( - S')Y) ； YTDY = I

为迭代形式的计算式，即：产=SM

(4)则根据文献［15］中方法，可将式(4)通过拉格朗日乘子转化

1.4近似特征向量计算并行化理想情况下上矩阵中对角零子矩阵会以块形式存在,相应的L特征分解后得到k个零特征值⑼，其对应的特征向量

(5)其中,SInv '为矩阵S取反，则根据式(5)可以通过迭代方式近 似计算S'的前k个特征向量，进而得到拉普拉斯矩阵的近似

组成的矩阵卩将具有明显的非零元分布，此时可以使用经典

聚类算法将特征向量矩阵y聚类。但实际应用中/个最小特

特征向量。1.5改进并行谱聚类计算流程征向量对就的特征向量的矩阵形式通常为V'=也,式中,Q

为某个正交矩阵，则此时的V'无法直接进行聚类，需要对其

进行标准化处理，即：改进并行化谱聚类算法对输入的大规模集数据首先进行 分块并分配到各节点通过单向循环迭代计算相似矩阵，并进

行f稀疏化，然后对稀疏存储的相似矩阵通过位置替换和矩 阵矢量乘计算和正则化Laplacian矩阵，最后将正则化

其中:i = 1,2,…，\"冷=l,2,-,n0由于@为正交的，因而标 准化后的矩阵U = ( U,\"｝在高维空间可形成相互正交的$个 簇,从而保证标准化处理后矩阵U的可聚性。

I输入数据丨 幾囂 T节点1,2,刁Laplacian矩阵表示为图形式，通过消息传递并行迭代计算近

似特征向量和#mean聚类实现最终大规模谱聚类，整个算法

的计算流程如图5所示。T相似矩阵护哗西H稀疏相似矩阵护卜按行分发对角索引Q-1/2否00-0(+1)—10讦1>匚A*］ GjiI节声y节点

是代结束?MiJXv

Gm H~| Anv|L'XD~112 D~1I2XLI取反|氐-means| Dm

点“Z谱聚类输出|Laplacian矩阵打图5本文改进谱聚类算法流程Fig. 5 Flowchart of the proposed improved spectral clustering algorithm2算法性能实验验证本章从聚类性能、运行效率和数据集可扩展性三个方面

对本文提出的算法(记为ApEigSC)的性能进行测试,实验用

算法(记为SpPic )［9］进行实验比较，以归一化互信息 (Normalized Mutual Information, NMI)作为性能评价指标。=I(X,X')(6)计算机群由1个主控节点和8个分布式节点组成，CPU为

Intel Xeon 2. 10 GHz,总内存 192 GB, Spark 版本为 V2. 0. 1, MPI版本为开源VI. & 8,实验数据如表1所示。其中:X、X，待计算互信息的两个向量,I(X,X')为其互信息。2.1聚类效果比较实验为测试算法的聚类效果,实验选取不同类别数的新闻集NG2(类别数2)、NG10(类别数10)及NG20 (类别数20)为数

表1实验所用的数据集Tab. 1 Datasets used in experiment据，实验中对各实验算法进行20次测试实验，其NMI结果的

平均值如表2所示。数据集NG［⑸内容新闻语料网络攻击样本数17 846特征数15类别数20从表2实验结果中可以看出:EigSC算法采用ScaLAPCK 线性库进行精确特征向量计算,在各实验数据集上都取得最

KDD［⑹

4000004123好的聚类效果性能;ApEigSC方法采用近似计算求解特征向

以精确特征向量计算的本文算法(简记为EigSC)、基于Spark框架的\"-means并行聚类(记为SpK-means) ［12］及PIC量，其聚类性能有稍许下降,但仍比SpK-means和SpPic算法

的聚类效果有明显的性能优势。实验结果一方面验证了

第1期崔艺馨等:Spark框架优化的大规模谱聚类并行算法171ApEigSC算法的并行优化算法对提高大规模谱聚类性能是有 效的;另一方面也说明近似特征向量相比精确的特征向量计

算，其聚类性能损失不大,但结合后面运行时间比较实验结果

可知，近似特征矩阵可以明显提升谱聚类在大规模聚类时的 运算效率。表2稀疏化后的NMI实验结果Tab. 2 NMI experimental results after sparsification算法NG2NG10NG20EigSC0.471 ±0.120.805 ±0.080.375 土0.12ApEigSC0.610 ±0.020.860 ±0.130.463 土0.10SpK-means0.515 ±0.140.857 ±0.090.401 ±0.03SpPic0.275 ±0.170.839 ±0.100.289 ±0.102.2特征向量求解时间实验从KDD数据集中抽取不同数量的样本数据，并存储于 HDFS中。在数据集上以不同的特征规模，分析ApEigSC算

法的近似特征向量运算时间，并与EigSC算法中的精确特征 向量计算及ArPack算法的特征向量计算方法进行对比,结果

如图6所示。Fig. 6 Running time varies with feature scale从实验结果可见，各算法的特征向量的运算时间随着特 征求解规模增加出现不同速度的增长:ApEigSC算法的运算

时间增长最为缓慢，性能最优，反映出特征向量并行近似计算

的运行时间优势;EigSC算法呈现一定的时间增长,但增长缓

慢且近似线性增加，主要因为特征规模的增加使得EigSC算

法需要更多的迭代完成收敛，但迭代次数增加带来总运行时

间的近似线性增长;ArPack算法的高复杂度单机计算模式随

特征规模的增长，运行时间呈现指数增长。2.3算法可扩展性实验以KDD数据集生成不同样本规模的实验数据集,分析各 算法的运行时间,每组数据进行20次实验，取结果的平均值,

实验结果如图7所示。从图7可以看出,4种算法在不同规模数据集上的运行

时间都在增长，但都呈现线性增长，表现出较好的可扩展性,

ApEigSC和SpPic算法对不同规模的数据集，算法的运行时间

变化幅度不大，说明其数据可扩展性更优,这主要是因为这两

种算法通过迭代计算近似特征向量,在并行化基础上迭代次

数越多，近似特征向量计算的运行效率优势越明显，因而算法

的聚类时间增加较缓慢，而ApEigSC算法的可扩展性更优。 SpK-means算法的时间开销主要集中在距离计算上,在聚类

数一定时其聚类时间受样本规模的影响,EigSC具有精确的

特征向量计算，但随着样本规模的增加,其样本间精确的相似 计算时间开销也随之增大，因而运行时间受样本影响最大。…—ApEigSC 一—-• SpPicSpK-means—b- EigSC图7样本规模增加时算法运行总时间Fig. 7 Total running time of algorithm runs assample size increases综合所有实验结果可以看出，文中算法通过并行优化和

近似特征向量求解，在取得与精确特征向量计算方法相近的

聚类效果基础上，进一步减少了算法的聚类时间开销,在大规 模数据集上具有较好的扩展性。3结语针对并行谱聚类在大规模集上难以避免的计算耗时或无

法聚类等性能瓶颈，基于Spark技术，提出了适用于大规模集

的并行谱聚类优化算法,算法通过相似矩阵的单向循环并行

计算、Laplacian矩阵的并行构建及正则化以及近似特征向量

的使用，在获得较好的谱聚类性能基础上，有效减少了算法的

计算量和存储空间需求，提高了算法的运行效率。实验结果 验证了所提算法在大规模数据集下良好的聚类性能和可扩展

性。在后续工作中，将继续研究近似特征向量提取后，4

means算法对近似特征向量聚类过程的并行优化，以进一步

实现大规模谱聚类算法的并行优化性能。参考文献(References)[1]

MIJANGOS V, SIERRA G, MONTES A. Sentence level matrix rep­resentation for document spectral clustering[ J] . Pattern Recognition

Letters, 2017, 85: 29 - 34.

[2]

WANG Y, WU L, LIN X, et al. Multi view spectral clustering via

structured low-rank matrix factorization [ J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29 ( 10): 4833 - 4843.[3] JIA H, DING S, DU M. Self-tuning p-spectral clustering based on

shared nearest neighbors[ J]. Cognitive Computation, 2015, 7(5): 622 -632.[4]

杨艺,马儒宁•基于核心点的大数据谱聚类算法[J] •中国科学技

术大学学报,2016,46(9):757 -763. (YANG Y, MA R N. Core­points based spectral clustering for big data analysis [ J]. Journal of University of Science and Technology of China, 2016, 46(9): 757 -

763.)[5] 金海,张劲松，吴睿.一种基于抽样改进加权核/f-means的大数

据谱聚类算法测绘通报，2018 ( 11): 78 - 82. (JIN H, ZHANG J S, WU R. A large scale spectral clustering algorithm u- sing sampling improved weighted kernel fc-means [ J] . Bulletin of Surveying and Mapping, 2018( 11): 78 - 82.)[6]

FOWLKES C, BELONGIE S, CHUNG F, et al. Spectral grouping using the Nystrom method[ J]. IEEE Transactions on Pattern Analy­

sis and Machine Intelligence, 2004, 26(2): 214 -225.172计算机应用第40卷[7]

丁世飞，贾洪杰,史忠植•基于自适应Nystriim采样的大数据谱

聚类算法[J] •软件学报,2014, 25(9): 2037 - 2049. ( DING S F,

JIA H J, SHI Z Z. Spectral clustering algorithm based on adaptive Nystrom sampling for big data analysis [ J] . Journal of Software,

2014, 25(9):2037 - 2049.)[8]

王小玉，丁世飞.基于共享近邻的成对约束谱聚类算法[J].计算 机工程与应用,2019,55(2): 142-147. (WANG X Y, DING S F.

Pairwise constrained spectral clustering algorithm based on shared

nearest neighborhood[ J]. Computer Engineering and Applications, 2019, 55(2):142 -147.)[9] JIN R, KOU C, LIU R, et al. Efficient parallel spectral clustering algorithm design for large data sets under cloud computing environ- ment[ J]. Journal of Cloud Computing: Advances, Systems and Ap­

plications, 2013, 2(1)： No. 47.[10] 张文杰，蒋烈辉.一种基于MapReduce并行化计算的大数据聚

类算法[J/OL].计算机应用研究，[2019- 05-05] http: //www. arocmag. com/article/02- 2020- 01- 055. html. ( ZHANG W J,

JIANG L H. Parallel computation algorithm for big data clustering based on MapReduce] J/OL]. Application Research of Computers,

[2019- 05- 05] http: //www. arocmag. com/article/02- 2020- 01- 055. html.)[11]

李晓瑜，俞丽颖，雷航，等.一种K-means改进算法的并行化实 现与应用[J].电子科技大学学报,2017,46(1):61 -68. (LI X

Y, YU L Y, LEI H, et al. The parallel implementation and appli­

cation of an improved K-means algorithm[ J]. Journal of University of Electronic Science and Technology of China, 2017, 46( 1): 61

-68.)[12] 刘鹏，滕家雨,丁恩杰,等.基于Spark的大规模文本/c-means并

行聚类算法[J].中文信息学报,2017,31(4)： 145 - 153. (UU

P, TENG J Y, DING E J, et al. Parallel k-means algorithm for

massive texts on Spark[ J] . Journal of Chinese Information Process­

ing, 2017, 31(4)： 145 -153.)[13] 魏彩娜，钱鹏江，奚臣•域间F-范数正则化迁移谱聚类方法[J].

计算机科学与探索,2018,12(3):472 -483. (WEI C N, QIAN PJ, XI C. Transfer spectral clustering based on inter domain F-norm regularization[ J]. Journal of Frontiers of Computer Science and Technology, 201& 12(3):472 -483.)[14] WU S, SONG H, CHENG G, et al. Civil engineering supervision video retrieval method optimization based on spectral clustering and

R-tree[ J]. Neural Computing and Applications, 2019, 31(9): 4513 -4525.[15] 朱书伟，周治平，张道文.融合并行混沌萤火虫算法的K调和

均值聚类[J].智能系统学报,2015, 10(6):872 -880. (ZHU S

W, ZHOU Z P, ZHANG D W. K-harmonic means clustering mer­

ged with parallel chaotic firefly algorithm [ J]. CAAI Transactions

on Intelligent Systems. 2015, 10(6) : 872 -880.)[16]

LU C, YAN S, LIN Z. Convex sparse spectral clustering single­view to multi-view [ J]. IEEE Transactions on Image Processing,

2016, 25(6)： 2833 -2843.CUI Yixin, bom in 1981, M. S. , experimentalist. Her research in­terests include data mining, computer network.CHEN Xiaodong, bom in 1978, Ph. D. , associate professor. His research interests include computer network.