王志剛，陳名輝，趙振凱

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

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

王志剛，陳名輝，趙振凱

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

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

分布式計(jì)算；DBSCAN；Spark；YARN；Tachyon

0 引言

分布式計(jì)算平臺(tái)具有易于擴(kuò)展、學(xué)習(xí)、使用和部署等特點(diǎn)，是一種簡(jiǎn)潔抽象的并行編程環(huán)境。用戶只需要關(guān)注解決自己的并行計(jì)算任務(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對(duì)聚類算法進(jìn)行封裝，提高了算法的效率。文獻(xiàn)[5]利用數(shù)據(jù)分箱和網(wǎng)格劃分技術(shù)，通過對(duì)核心點(diǎn)生成無向圖后進(jìn)行廣度優(yōu)先搜索生成聚類，是一種效率較高的網(wǎng)格DBSCAN算法。文獻(xiàn)[6]對(duì)各個(gè)局部數(shù)據(jù)集采取不同的參數(shù)值分別進(jìn)行聚類，最后合并各局部聚類結(jié)果。文獻(xiàn)[7]的DPDGA算法在數(shù)據(jù)劃分時(shí)利用遺傳算法獲得較優(yōu)的初始聚類中心，據(jù)此中心點(diǎn)劃分?jǐn)?shù)據(jù)集，對(duì)各局部數(shù)據(jù)集分別使用DBSCAN算法進(jìn)行聚類，最后合并各局部數(shù)據(jù)集的聚類結(jié)果。文獻(xiàn)[8]在Spark平臺(tái)用ACURE算法實(shí)現(xiàn)了數(shù)據(jù)和任務(wù)同時(shí)并行。文獻(xiàn)[9]基于Spark平臺(tái)設(shè)計(jì)和實(shí)現(xiàn)了并行化的線性回歸、向量機(jī)和聚類算法。文獻(xiàn)[10]研究了Spark并行計(jì)算集群對(duì)于內(nèi)存的使用行為。通過對(duì)Spark內(nèi)存行為進(jìn)行建模與分析,對(duì)Spark內(nèi)存的使用進(jìn)行了決策自動(dòng)化以及替換策略優(yōu)化。雖然針對(duì)DBSCAN算法的優(yōu)化研究很多，針對(duì)Spark的研究也有，但針對(duì)Spark平臺(tái)的DBSCAN聚類算法分析目前相對(duì)較少。

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

1 DBSCAN簡(jiǎn)介

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

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

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

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

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

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

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

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

圖1 概念示意圖

算法描述：

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

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

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

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

DBSCAN算法也存在一些問題：

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

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

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

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

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

2.1 網(wǎng)格劃分

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

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

如圖2所示。

圖2 DBSCAN網(wǎng)格

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

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

2.2 算法描述

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

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

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

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

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

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

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

2.3 聚類合并

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

圖5 基于Spark的DBSCAN

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

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

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

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

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

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

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

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

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

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

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

[12]孫吉貴,劉杰,等.聚類算法研究[J].軟件學(xué)報(bào),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è)計(jì)[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的云存儲(chǔ)服務(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è)計(jì)與實(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)檐浖こ獭⒂?jì)算機(jī)網(wǎng)絡(luò)

2016-11-01

2016-12-01