一種YARN和Spark框架的網(wǎng)格聚類方法

王志剛，陳名輝，趙振凱

（湖南師范大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院，長沙 410081）

一種YARN和Spark框架的網(wǎng)格聚類方法

王志剛，陳名輝，趙振凱

（湖南師范大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院，長沙 410081）

分布式計算為大數(shù)據(jù)的處理提供一種新的平臺，能有效提升算法的執(zhí)行速度。在DBSCAN算法基礎(chǔ)上提出一種數(shù)據(jù)分網(wǎng)格算法，該算法將每個分區(qū)上的數(shù)據(jù)集劃分成以Eps半徑為邊長的單元格數(shù)據(jù)塊，將查找Eps鄰域的范圍縮小到數(shù)據(jù)對象的八個相鄰單元格之內(nèi)，從而提高查找Eps鄰域的速度及聚類速度，具有較好的加速比和擴(kuò)展率。同時還優(yōu)化分區(qū)聚類合并方法。

分布式計算；DBSCAN；Spark；YARN；Tachyon

0 引言

分布式計算平臺具有易于擴(kuò)展、學(xué)習(xí)、使用和部署等特點(diǎn)，是一種簡潔抽象的并行編程環(huán)境。用戶只需要關(guān)注解決自己的并行計算任務(wù)，而不需關(guān)注細(xì)節(jié)實(shí)現(xiàn)。

加州伯克利大學(xué)AMP實(shí)驗(yàn)室最先推出Spark，但直到2014年才開始大幅度發(fā)展。目前，較流行運(yùn)用Hadoop的MapReduce[1]實(shí)現(xiàn)并行數(shù)據(jù)挖掘，算法K-means和DBSCAN是其主要代表。文獻(xiàn)[2]提出了基于Hadoop的K-means、DBSCAN、近鄰傳播算法和譜聚類算法的MapReduce編輯模型。文獻(xiàn)[3]提出了DBSCAN增量聚類算法的MapReduce實(shí)現(xiàn)。文獻(xiàn)[4]提出了網(wǎng)格控制因子的DBSCAN聚類算法，并用MapReduce對聚類算法進(jìn)行封裝，提高了算法的效率。文獻(xiàn)[5]利用數(shù)據(jù)分箱和網(wǎng)格劃分技術(shù)，通過對核心點(diǎn)生成無向圖后進(jìn)行廣度優(yōu)先搜索生成聚類，是一種效率較高的網(wǎng)格DBSCAN算法。文獻(xiàn)[6]對各個局部數(shù)據(jù)集采取不同的參數(shù)值分別進(jìn)行聚類，最后合并各局部聚類結(jié)果。文獻(xiàn)[7]的DPDGA算法在數(shù)據(jù)劃分時利用遺傳算法獲得較優(yōu)的初始聚類中心，據(jù)此中心點(diǎn)劃分?jǐn)?shù)據(jù)集，對各局部數(shù)據(jù)集分別使用DBSCAN算法進(jìn)行聚類，最后合并各局部數(shù)據(jù)集的聚類結(jié)果。文獻(xiàn)[8]在Spark平臺用ACURE算法實(shí)現(xiàn)了數(shù)據(jù)和任務(wù)同時并行。文獻(xiàn)[9]基于Spark平臺設(shè)計和實(shí)現(xiàn)了并行化的線性回歸、向量機(jī)和聚類算法。文獻(xiàn)[10]研究了Spark并行計算集群對于內(nèi)存的使用行為。通過對Spark內(nèi)存行為進(jìn)行建模與分析,對Spark內(nèi)存的使用進(jìn)行了決策自動化以及替換策略優(yōu)化。雖然針對DBSCAN算法的優(yōu)化研究很多，針對Spark的研究也有，但針對Spark平臺的DBSCAN聚類算法分析目前相對較少。

本文基于HDFS+Tachyon+YARN+Spark平臺研究了DBSCAN算法，在此基礎(chǔ)上構(gòu)建了YARN數(shù)據(jù)挖掘系統(tǒng)的模型結(jié)構(gòu)；在基于MapReduce編程模式上，根據(jù)算法的特點(diǎn)采用相應(yīng)的并行策略將讓算法運(yùn)行到Spark分布式計算平臺上。

1 DBSCAN簡介

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是Ester Martin等人提出的一個基于密度的聚類算法。密度相連點(diǎn)的最大集合稱之為簇，簇可以產(chǎn)生任意形狀的聚類，甚至在含有噪聲的空間數(shù)據(jù)中。該算法根據(jù)給定的密度閾值（Eps和MinPts）識別一個類，Eps和MinPts分別代表半徑和在此半徑范圍內(nèi)核心點(diǎn)至少應(yīng)該含有的點(diǎn)的數(shù)量。以下是關(guān)于DBSCAN的一些基本定義：

●Eps鄰域：數(shù)據(jù)對象半徑為Eps內(nèi)的全部空間區(qū)域；

●核心對象：如果數(shù)據(jù)對象p的Eps鄰域內(nèi)的對象數(shù)大于等于MinPts值，則p是核心對象；

●噪聲對象：如果數(shù)據(jù)對象p的Eps鄰域內(nèi)的對象數(shù)小于MinPts值，并且p不在其他核心對象的Eps鄰域內(nèi)，則p是噪聲對象；

●直接密度可達(dá)：設(shè)在樣本集合D中，p為核心對象，如果樣本點(diǎn)q在p的Eps領(lǐng)域之內(nèi)，則對象q到p直接密度可達(dá)；

●密度可達(dá)：設(shè)在樣本集合D中，給定一串樣本點(diǎn)p1，p2,…,pn，p=p1，q=pn，如果對象pi到pi-1直接密度可達(dá)，則對象q到p密度可達(dá)；

●密度相連：設(shè)樣本集合D中某對象o，如果o到p和q都是密度可達(dá)，則p和q密度相連。

DBSCAN聚類算法是尋找密度相連對象的最大集合。如圖1所示。

圖1 概念示意圖

算法描述：

（1）若數(shù)據(jù)集中的對象p還未被處理，標(biāo)記為簇或者噪聲，若其Eps鄰域包含的對象數(shù)大于等于MinPts，則創(chuàng)建新簇C，并將其中的所有點(diǎn)放入候選集N；

（2）對候選集N中還尚未被處理的對象q，檢查其Eps鄰域，如果包含至少M(fèi)inPts個數(shù)據(jù)對象，則將這些對象加入數(shù)據(jù)集N；如果q還未歸入一個簇，則將q放入數(shù)據(jù)集C；

（3）重復(fù)步驟（2），直到候選集N為空；

（4）重復(fù)步驟（1）～（3），直到數(shù)據(jù)集中的數(shù)據(jù)對象都被處理完畢。

DBSCAN算法也存在一些問題：

（1）當(dāng)不使用索引時，算法的時間復(fù)雜度為O（n2），面對大數(shù)據(jù)進(jìn)行聚類時，需要的內(nèi)存和I/O開銷都很大。

（2）算法需要傳入Eps和MinPts全局參數(shù)且對這兩個參數(shù)敏感，它們的變化會影響聚類結(jié)果，尤其是在密度分布不均勻的情況。

（3）算法處理邊界對象時根據(jù)“先到先得”的原則決定所屬簇，這使聚類的精度受到處理順序的影響。

2 改進(jìn)的并行設(shè)計

基于Spark平臺的DBSCAN算法存在數(shù)據(jù)和任務(wù)雙并行化。任務(wù)并行化由YARN平臺根據(jù)節(jié)點(diǎn)資源情況來自動分配。

2.1 網(wǎng)格劃分

網(wǎng)格劃分：通過在數(shù)據(jù)集中不斷查詢獲取數(shù)據(jù)對象的Eps鄰域，并返回區(qū)域中的所有對象，DBSCAN算法的時間復(fù)雜度O（n2）較大。故此，以Eps為邊長，將數(shù)據(jù)空間在X、Y兩個維度上劃分成n×m個矩形單元組成的網(wǎng)格，在此網(wǎng)格上進(jìn)行聚類操作。雖然此方法表面上是將數(shù)據(jù)分片并行化，但是由于每一個矩形單元都有統(tǒng)計信息及相應(yīng)特征，所以不僅是對數(shù)據(jù)進(jìn)行分片并行化，也提高了查詢速度。

網(wǎng)格單元：即邊長為Eps的網(wǎng)格矩形單元：

如圖2所示。

圖2 DBSCAN網(wǎng)格

這是一個左上封閉、右下開放的矩形區(qū)間，對于邊長不足Eps的單元，按實(shí)際的邊長計算，在保證計算一致性前提下不影響計算的準(zhǔn)確性。

鄰接網(wǎng)格集合：與網(wǎng)格單元相鄰的8個單元格所構(gòu)成的矩形區(qū)域。

2.2 算法描述

算法首先獲取對象的本網(wǎng)格及其鄰接網(wǎng)格集合，如果這9個網(wǎng)格中的數(shù)據(jù)對象數(shù)小于MinPts，則標(biāo)記數(shù)據(jù)對象為噪聲；否則繼續(xù)進(jìn)行下一步的運(yùn)算?；诰W(wǎng)格單元的DBSCAN改進(jìn)算法步驟如下：

（1）將空間劃分為n×m個網(wǎng)格單元；

（2）建立數(shù)據(jù)對象到網(wǎng)格單元的映射關(guān)系；

（3）查找數(shù)據(jù)集中未被標(biāo)識為簇或噪聲的對象，如果p未被處理，則檢查該網(wǎng)格及鄰接網(wǎng)格共9個網(wǎng)格中的對象數(shù)，如果對象數(shù)大于等于MinPts，則將其標(biāo)記為新簇C，并將其中的所有點(diǎn)放入候選集M；否則將該數(shù)據(jù)對象標(biāo)記為噪聲；

（4）選取候選集M中還未被處理的對象q，檢查其鄰接網(wǎng)格集合，若包含的對象數(shù)大于等于MinPts，則將這些對象放入候選集M；如果q未被歸入某一個簇，則將q標(biāo)記為簇C；

（5）若候選集M不為空，重復(fù)步驟（4）；

（6）重復(fù)（3）～（5）步，直到所有的數(shù)據(jù)對象都被歸到了某個簇或被標(biāo)記為噪聲。

2.3 聚類合并

在各分區(qū)的數(shù)據(jù)聚類之后，再對各分區(qū)上的局部簇進(jìn)行聚合。此時存在兩種情況：一是兩個沒有交叉點(diǎn)的獨(dú)立簇，不需要對兩個簇進(jìn)行操作；二是有交叉點(diǎn)，此時邊界點(diǎn)的二次聚類結(jié)果決定是否進(jìn)行合并。

邊界點(diǎn)是指數(shù)據(jù)集中有特定意義的一類數(shù)據(jù)對象，位于一個或多個分區(qū)的邊緣地帶，可能屬于一到多個簇；但也可是歸屬性并不確定的孤立數(shù)據(jù)對象。它是不同分區(qū)簇合并的關(guān)鍵點(diǎn)。本文的邊界點(diǎn)是指在分區(qū)邊界邊長Eps區(qū)域內(nèi)的點(diǎn)，如圖3所示。

經(jīng)過聚類處理，各分區(qū)塊上的數(shù)據(jù)對象都已經(jīng)打上了簇標(biāo)記。不同分區(qū)塊上的簇的合并則跟各分區(qū)塊上邊界點(diǎn)的二次聚類結(jié)果相關(guān)。需要根據(jù)兩次簇標(biāo)記的不同情況來做出不同的處理。

對于任意邊界點(diǎn)，在各分區(qū)內(nèi)首次聚類的時候，會存在三種類型：核心、非核心和噪聲點(diǎn)。在進(jìn)行二次聚類時，同樣可能存這三種類型的點(diǎn)。求兩者的笛卡爾積，得到九種組合。算法流程如圖4所示。

圖3 邊界點(diǎn)聚類合并示意

圖4 邊界點(diǎn)聚類合并流程

3 平臺的并行實(shí)現(xiàn)

基于YARN的Spark分布式計算平臺將大的任務(wù)劃分成若干小任務(wù)，然后分配給不同平臺執(zhí)行，并依靠HDFS上的Tachyon分布式文件系統(tǒng)存放中間數(shù)據(jù)結(jié)果。HDFS負(fù)責(zé)存放待處理的原始數(shù)據(jù)集和聚類分析結(jié)果。并行算法運(yùn)行流程如圖5所示。

在Spark平臺上，可以利用彈性分布式數(shù)據(jù)集（RDD）的Transformation和Action操作實(shí)現(xiàn)數(shù)據(jù)并行，RDD的mapPartition能按指定的分區(qū)方式進(jìn)行數(shù)據(jù)加載，在各個分區(qū)上進(jìn)行數(shù)據(jù)運(yùn)算，之后對各分區(qū)的運(yùn)算結(jié)果進(jìn)行聚合。

Spark平臺把作業(yè)分成若干個階段，根據(jù)服務(wù)器資源情況，任務(wù)由不同的機(jī)器處理。①從Tachyon文件系統(tǒng)讀取數(shù)據(jù)并進(jìn)行區(qū)塊劃分，將不同的點(diǎn)存放到不同的分區(qū)上加以標(biāo)記。②分別對各分區(qū)做聚類運(yùn)算，給數(shù)據(jù)點(diǎn)做簇標(biāo)記，獲得局部聚類；提取分區(qū)邊界點(diǎn)，根據(jù)區(qū)塊編號做二次聚類運(yùn)算，獲取邊界點(diǎn)的二次簇標(biāo)記。③比較邊界點(diǎn)前后兩次簇標(biāo)記，根據(jù)簇合并規(guī)則進(jìn)行局部簇合并。④更新合并后的簇標(biāo)記，保存結(jié)果至HDFS分布式文件系統(tǒng)。

4 結(jié)語

Spark是一個正在不斷發(fā)展的平臺，通過對其深入的學(xué)習(xí)和了解，能有效的運(yùn)用好并行運(yùn)算平臺，提升HDFS+Tachyon+YARN+Spark平臺的性能并發(fā)揮其價值，對大數(shù)據(jù)的處理將會更快更好。

圖5 基于Spark的DBSCAN

[1]王愷.基于MapReduce的聚類算法并行化研究[D].南京：南京師范大學(xué),2014.

[2]孫雨冰.基于MapReduce化的數(shù)據(jù)聚類算法的研究、設(shè)計與應(yīng)用[D].上海：華東理工大學(xué),2013.

[3]王雅光.基于Hadoop平臺的DBSCAN算法應(yīng)用研究[D].廣州：廣東工業(yè)大學(xué),2013.

[4]羅啟福.基于云計算的DBSCAN算法研究[D].武漢：武漢理工大學(xué),2013.

[5]張楓.基于網(wǎng)格的DBSCAN算法和聚類邊界技術(shù)的研究[D].鄭州：鄭州大學(xué),2007.

[6]熊忠陽,孫思,張玉芳,王秀瓊.一種基于劃分的不同參數(shù)值的DBSCAN算法[J].計算機(jī)工程與設(shè)計,2005.

[7]孫思.利用遺傳思想進(jìn)行數(shù)據(jù)劃分的DBSCAN算法研究[D].重慶：重慶大學(xué),2005.

[8]邱榮財.基于Spark平臺的CURE算法并行化設(shè)計與應(yīng)用[D].廣州：華南理工大學(xué),2014.

[9]梁彥.基于分布式平臺Spark和YARN的數(shù)據(jù)挖掘算法的并行化研究[D].中山：中山大學(xué),2014.

[10]馮琳.集群計算引擎Spark中的內(nèi)存優(yōu)化研究與實(shí)現(xiàn)[D].北京：清華大學(xué),2013.

[11]遲學(xué)斌.高性能并行計算[D].武漢:華中科技大學(xué)圖書館,2007.

[12]孫吉貴,劉杰,等.聚類算法研究[J].軟件學(xué)報,2008,19（1）:48-61.

[13]Pang-Ning T,Michael S,Vipin K.Introduction to Data Mining[M].Addison Wesley,2005.

[14]Michael A,Armando F,et al.Above the Clouds:A Berkeley Vew of Cloud Computing[J].Communications of the ACM,2010,53（4）: 50-58.

[15]Ralf L.Google's MapReduce Programming Model-Revisited[J].Science of C Programming,2008,70（1）:1-30.

[16]Oliveira B C,Gibbons J.Scala for Generic Programmers.Proceedings of Proceedings of the ACM SIGPLAN Workshop on GenericProgramming,New York,NY,USA:ACM,2008:25-36.

[17]阿斯力別克.流數(shù)據(jù)挖掘算法在金融領(lǐng)域的應(yīng)用研究[D].廣州:華南理工大學(xué),2012.

[18]鄭洪英.數(shù)據(jù)挖掘聚類算法的分析和應(yīng)用研究[D].重慶:重慶大學(xué),2002.

[19]徐軍莉.分布式聚類算法研究及其應(yīng)用[D].南昌:南昌大學(xué),2009.

[20]祁小麗.一種改進(jìn)的快速聚類算法及并行化研究[D].蘭州:蘭州大學(xué),2009.

[21]Barry Wilkinson,Michael Allen.并行程序設(shè)計[M].北京:機(jī)械工業(yè)出版社,2005.

[22]Wikipedia.Tachyon.https://en.wikipedia.org/wiki/Tachyon,2015.

[23]Borthakur D.HDFS Architecture Guide.Hadoop Apache Project.http://hadoop.apache.org/common/docs/current/hdfs_design.pdf, 2008.

[24]Ghemawat S,Gobioff H,Leung S T.The Google File System.Proceedings of Proceedings of the Nineteenth ACM symposium on Operating systems principles,New York,NY,USA:ACM,2003：29-43.

[25]黃曉云.基于HDFS的云存儲服務(wù)系統(tǒng)研究[D].大連:大連海事大學(xué),2010.

[26]Uavilapalli V K,Murthy A C,Konar M,Shah H,Seth S,Saha B,O'Malley O,Radia S,Baldeschwieler E,Douglas C,Curino C,Agarwal S,Evans R,Graves T,Lowe J,Reed B.Apache hadoop yarn:Yet Another Resource Negotiator.In Proceedings of the 4th Annual Symposium on Cloud Computing.ACM,2013:5.

[27]董西成.Hadoop技術(shù)內(nèi)幕:深入解析YARN架構(gòu)設(shè)計與實(shí)現(xiàn)原理[M].北京:機(jī)械工業(yè)出版社,2013:153-184.

[29]Dean J,Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters[J].Communications of the ACM,2008,51（1）:107-113.

A Grid Clustering Method of YARN and Spark Framework

WANG Zhi-gang，CHEN Ming-hui，ZHAO Zhen-kai

（College of Math and Computer Science,Hunan Normal University,Changsha 410081）

Distributed computing for large data processing provides a new platform which can effectively improve the speed of the algorithm.Based on DBSCAN algorithm,proposes a data sub-grid algorithm,which divides the data of each partition into cell data block with Eps radius as the side length,to reduce the search for Eps neighborhood range data objects within eight adjacent cells,so as to improve the speed of Eps neighborhood search and the clustering speed,good speed ratio and extension ratio.At the same time,optimizes the partition clustering consolidation methods.

Distributed Computing;DBSCAN;Spark;YARN;Tachyon

1007-1423（2016）35-0033-05

10.3969/j.issn.1007-1423.2016.35.007

王志剛（1962-），男，湖南沅江人，教授，研究方向?yàn)檐浖こ獭⒂嬎銠C(jī)網(wǎng)絡(luò)

2016-11-01

2016-12-01