一種YARN和Spark框架的網格聚類方法

王志剛，陳名輝，趙振凱

（湖南師范大學數學與計算機學院，長沙 410081）

一種YARN和Spark框架的網格聚類方法

王志剛，陳名輝，趙振凱

（湖南師范大學數學與計算機學院，長沙 410081）

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

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

0 引言

分布式計算平臺具有易于擴展、學習、使用和部署等特點，是一種簡潔抽象的并行編程環境。用戶只需要關注解決自己的并行計算任務，而不需關注細節實現。

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

本文基于HDFS+Tachyon+YARN+Spark平臺研究了DBSCAN算法，在此基礎上構建了YARN數據挖掘系統的模型結構；在基于MapReduce編程模式上，根據算法的特點采用相應的并行策略將讓算法運行到Spark分布式計算平臺上。

1 DBSCAN簡介

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

●Eps鄰域：數據對象半徑為Eps內的全部空間區域；

●核心對象：如果數據對象p的Eps鄰域內的對象數大于等于MinPts值，則p是核心對象；

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

●直接密度可達：設在樣本集合D中，p為核心對象，如果樣本點q在p的Eps領域之內，則對象q到p直接密度可達；

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

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

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

圖1 概念示意圖

算法描述：

（1）若數據集中的對象p還未被處理，標記為簇或者噪聲，若其Eps鄰域包含的對象數大于等于MinPts，則創建新簇C，并將其中的所有點放入候選集N；

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

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

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

DBSCAN算法也存在一些問題：

（1）當不使用索引時，算法的時間復雜度為O（n2），面對大數據進行聚類時，需要的內存和I/O開銷都很大。

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

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

2 改進的并行設計

基于Spark平臺的DBSCAN算法存在數據和任務雙并行化。任務并行化由YARN平臺根據節點資源情況來自動分配。

2.1 網格劃分

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

網格單元：即邊長為Eps的網格矩形單元：

如圖2所示。

圖2 DBSCAN網格

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

鄰接網格集合：與網格單元相鄰的8個單元格所構成的矩形區域。

2.2 算法描述

算法首先獲取對象的本網格及其鄰接網格集合，如果這9個網格中的數據對象數小于MinPts，則標記數據對象為噪聲；否則繼續進行下一步的運算。基于網格單元的DBSCAN改進算法步驟如下：

（1）將空間劃分為n×m個網格單元；

（2）建立數據對象到網格單元的映射關系；

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

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

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

（6）重復（3）～（5）步，直到所有的數據對象都被歸到了某個簇或被標記為噪聲。

2.3 聚類合并

在各分區的數據聚類之后，再對各分區上的局部簇進行聚合。此時存在兩種情況：一是兩個沒有交叉點的獨立簇，不需要對兩個簇進行操作；二是有交叉點，此時邊界點的二次聚類結果決定是否進行合并。

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

經過聚類處理，各分區塊上的數據對象都已經打上了簇標記。不同分區塊上的簇的合并則跟各分區塊上邊界點的二次聚類結果相關。需要根據兩次簇標記的不同情況來做出不同的處理。

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

圖3 邊界點聚類合并示意

圖4 邊界點聚類合并流程

3 平臺的并行實現

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

在Spark平臺上，可以利用彈性分布式數據集（RDD）的Transformation和Action操作實現數據并行，RDD的mapPartition能按指定的分區方式進行數據加載，在各個分區上進行數據運算，之后對各分區的運算結果進行聚合。

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

4 結語

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

圖5 基于Spark的DBSCAN

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

[2]孫雨冰.基于MapReduce化的數據聚類算法的研究、設計與應用[D].上海：華東理工大學,2013.

[3]王雅光.基于Hadoop平臺的DBSCAN算法應用研究[D].廣州：廣東工業大學,2013.

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

[5]張楓.基于網格的DBSCAN算法和聚類邊界技術的研究[D].鄭州：鄭州大學,2007.

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

[7]孫思.利用遺傳思想進行數據劃分的DBSCAN算法研究[D].重慶：重慶大學,2005.

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

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

[10]馮琳.集群計算引擎Spark中的內存優化研究與實現[D].北京：清華大學,2013.

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

[12]孫吉貴,劉杰,等.聚類算法研究[J].軟件學報,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]阿斯力別克.流數據挖掘算法在金融領域的應用研究[D].廣州:華南理工大學,2012.

[18]鄭洪英.數據挖掘聚類算法的分析和應用研究[D].重慶:重慶大學,2002.

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

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

[21]Barry Wilkinson,Michael Allen.并行程序設計[M].北京:機械工業出版社,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的云存儲服務系統研究[D].大連:大連海事大學,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技術內幕:深入解析YARN架構設計與實現原理[M].北京:機械工業出版社,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-），男，湖南沅江人，教授，研究方向為軟件工程、計算機網絡

2016-11-01

2016-12-01