基于Spark的BIRCH算法并行化的设计与实现

计算机工程与科学

基于Spark的BIRCH算法并行化的设计与实现

李帅1，吴斌2，杜修明3，陈玉峰3

(1.北京邮电大学智能通信软件与多媒体北京重点实验室，北京 100876);

2.北京邮电大学计算机学院，北京 100876;3.国网山东省电力公司电力科学研究院，山东济南 250000)

收稿日期:2016-09-05 修回日期:2016-11-12 出版日期:2017-01-25 发布日期:2017-01-25
基金资助:
国家863计划（2015AA050204）；国网科技项目（60873120）

Design and implementation of BIRCH algorithm

parallelization based on Spark

LI Shuai1，WU Bin2，DU Xiuming3，CHEN Yufeng3

(1.Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia,

Beijing University of Posts and Telecommunicaions,Beijing 100876;

2.School of Computer Science,Beijing University of Posts and Telecommunications,Beijing 100876;

3.State Gride Shandong Electric Power Research Institute,Jinan 250000,China)

Received:2016-09-05 Revised:2016-11-12 Online:2017-01-25 Published:2017-01-25

摘要/Abstract

摘要：

在分布式计算和内存为王的时代，Spark作为基于内存计算的分布式框架技术得到了前所未有的关注与应用。着重研究BIRCH算法在Spark上并行化的设计和实现，经过理论性能分析得到并行化过程中时间消耗较多的Spark转化操作，同时根据并行化BIRCH算法的有向无环图DAG，减少shuffle和磁盘读写频率，以期达到性能优化。最后，将并行化后的BIRCH算法分别与单机的BIRCH算法和MLlib中的KMeans聚类算法做了性能对比实验。实验结果表明，通过Spark对BIRCH算法并行化，其聚类质量没有明显的损失，并且获得了比较理想的运行时间和加速比。

关键词: Spark, BIRCH并行化, 性能优化

Abstract:

In the era when distributed computing and memory highly count, the technology of memorybased distributed computing framework, such as Spark, has gained unprecedented attention and is widely applied. We design and implement the BIRCH algorithm parallelization based on Spark, which can maximize performance optimization and reduce the frequency of shuffling and disk accessing. We do some theory analysis and describe the DAG of the BIRCH based on Spark. Finally, we compare the performance of the parallelized BIRCH algorithm with the BIRCH algorithm of a single machine and the MLlib KMeans clustering algorithm. Experimental results show that the parallel BIRCH algorithm based on Spark obtains ideal running time and speedup without obvious clustering quality loss.

Key words: Spark, BIRCH parallelization, performance optimization

李帅1，吴斌2，杜修明3，陈玉峰3. 基于Spark的BIRCH算法并行化的设计与实现[J]. 计算机工程与科学.

LI Shuai1，WU Bin2，DU Xiuming3，CHEN Yufeng3.

Design and implementation of BIRCH algorithm

parallelization based on Spark

[J]. Computer Engineering & Science.

参考文献［15］

［1］	Jain A K,Murty M N,Flynn P J.Data clustering: A review［J］.ACM Computing Surveys (CSUR),1999,31(3):264323.
［2］	Ester M,Kriegel H P,Sander J,et al.A densitybased algorithm for discovering clusters in large spatial databases with noise［C］∥Proc of Kdd,1996:226231.
［3］	Zhang T, Ramakrishnan R, Livny M. BIRCH: An efficient data clustering method for very large databases［C］∥Proc of ACM Sigmod Record,1996: 103114.
［4］	Wang W,Yang J,Muntz R.STING: A statistical information grid approach to spatial data mining［C］∥Proc of VLDB,1997: 186195.
［5］	Tsapanos N,Tefas A,Nikolaidis N,et al.Efficient MapReduce kernel kmeans for big data clustering［C］∥Proc of the 9th ACM Hellenic Conference on Artificial Intelligence,2016: 28.
［6］	Patwary M M A,Palsetia D,Agrawal A,et al.A new scalable parallel DBSCAN algorithm using the disjointset data structure［C］∥Proc of
20	12 IEEE International Conference on High Performance Computing,Networking,Storage and Analysis (SC 2012),2012:111.
［7］	Chierichetti F, Dalvi N, Kumar R. Correlation clustering in MapReduce［C］∥Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2014:641650.
［8］	Jin C,Chen Z,Hendrix W,et al.Incremental,distributed singlelinkage hierarchical clustering algorithm using MapReduce［C］∥Proc of the Symposium on High Performance Computing,2015:8392.
［9］	MLlib \| Spark ［EB/OL］.［201605］.http:∥spark.apache.org/mllib/.
［10］	Liu Zhiqiang,Gu Rong,Yuan Chunfeng,et al.Parallelization of classification algorithms based on SparkR［J］.Journal of Frontiers of Computer Science and Technology,2015,9(11):12811294.(in Chinese)
［11］	Meng X,Bradley J,Yavuz B,et al.MLlib:Machine learning in apache spark［J］.The Journal of Machine Learning Research,2016,17(1):12351241.
［12］	Garg A,Mangla A,Gupta N,et al.PBIRCH:A scalable parallel clustering algorithm for incremental data［C］∥Proc of 2006 10th International Database Engineering and Applications Symposium (IDEAS’06),2006:315316.
［13］	Yu Xiaoshan, Wu Yangyang. Parallel text hierarchical clustering based on MapReduce［J］.Journal of Computer Applications,2014,34(6):15951599.(in Chinese)
［14］	Zhu Yinghui,Jiang Yuzhen.Research of BIRCH clustering algorithm optimization and parallelism［J］.Computer Engineering and Design,2007,28(18):43454346.(in Chinese)
［15］	Wei Xiang.Improved BIRCH clustering algorithm based on density［J］.Computer Engineering and Applications,2013,49（10）：201205.(in Chinese)
［16］	Holden K,Andy K,Patrick W,et al.Learning spark:Lightingfast data analysis［M］. New York: O’Reilly Media,2015.
［17］	Zaharia M,Chowdhury M,Franklin M J,et al.Spark:Cluster computing with working sets［C］∥Proc of HotCloud’10, 2010:10.
［18］	Veenman C J,Reinders M J T,Backer E.A maximum variance cluster algorithm［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(9):12731280.
［19］	Gionis A, Mannila H, Tsaparas P. Clustering aggregation［J］.ACM Transactions on Knowledge Discovery from Data (TKDD),2007,1(1):130.
	附中文参考文献：
［10］	刘志强,顾荣,袁春风,等.基于 SparkR 的分类算法并行化研究［J］.计算机科学与探索,2015,9(11):12811294.
［13］	余晓山,吴扬扬.基于 MapReduce 的文本层次聚类并行化［J］.计算机应用,2014,34(6):15951599.
［14］	朱映辉,江玉珍.BIRCH 聚类算法优化及并行化研究［J］.计算机工程与设计,2007,28(18):43454346.
［15］	韦相. 基于密度的改进BIRCH聚类算法［J］. 计算机工程与应用，2013,49（10）：201205.

[1]	陈侨安1，李峰1，曹越1，龙明盛1,2. 基于运行数据分析的Spark任务参数优化[J]. J4, 20160101, 38(01): 11-19.
[2]	王星苏, 熊文, 张瑞. 海量地铁乘客轨迹相似性连接方法：以深圳地铁为例[J]. 计算机工程与科学, 2023, 45(08): 1383-1392.
[3]	康宇晗, 时洋, 陈照云, 文梅. 面向迈创+MatrixZone异构系统的深度学习编程框架[J]. 计算机工程与科学, 2023, 45(07): 1149-1158.
[4]	莫舒恒, 卢圣有, 黄聃, 卢宇彤. 基于即时编译的GNU Octave性能优化[J]. 计算机工程与科学, 2022, 44(12): 2091-2101.
[5]	胡艳芳, 熊文, 高炜. 基于 Spark 平台的网络游戏用户流失预测方法[J]. 计算机工程与科学, 2022, 44(10): 1730-1737.
[6]	沈佳杰, 卢修文, 向望, 赵泽宇, 王新, . 分布式存储系统读写一致性算法性能优化研究综述[J]. 计算机工程与科学, 2022, 44(04): 571-583.
[7]	卞琛, 修位蓉, 于炯. 异构Spark集群数据倾斜修正调度策略[J]. 计算机工程与科学, 2022, 44(04): 620-630.
[8]	张驭洲, 曹武迪, 卜景德, 谭光明, 吉青. GROMACS 2020在ROCm平台上的移植与优化[J]. 计算机工程与科学, 2021, 43(11): 1901-1909.
[9]	周静, 关玉蓉. 基于SDN的DWSN技术分析及性能优化研究[J]. 计算机工程与科学, 2021, 43(08): 1413-1421.
[10]	朱良杰, 沈佳杰, 周扬帆, 王新, . 云际存储系统性能优化研究现状与展望[J]. 计算机工程与科学, 2021, 43(05): 761-772.
[11]	徐海坤, 匡邓晖, 刘杰, 龚春叶, . 基于RMC的蒙特卡罗程序性能优化[J]. 计算机工程与科学, 2021, 43(04): 634-640.
[12]	胡亚红1，盛夏2，毛家发1. 资源不均衡Spark环境任务调度优化算法研究[J]. 计算机工程与科学, 2020, 42(02): 203-209.
[13]	何登平1，2，3，何宗浩1,2，李培强1,2. 基于Spark的并行化高效用项集挖掘算法[J]. 计算机工程与科学, 2019, 41(10): 1723-1730.
[14]	王武1，王舒扬1,2，姜金荣1,孟虹松3. 快速多极子方法在申威众核处理器上的实现和优化[J]. 计算机工程与科学, 2019, 41(07): 1161-1167.
[15]	杨杰超，许江淳，岳秋燕，曾德斌，陆万荣. 基于SPARK与随机森林的短信诈骗用户识别研究[J]. 计算机工程与科学, 2019, 41(06): 1136-1144.