云環(huán)境下并行DBSCAN聚類算法研究

鄧 青，楊 寧

(1.山西輕工職業(yè)技術(shù)學(xué)院,山西 太原 030013；2.山西云時(shí)代技術(shù)有限公司，山西 太原 030006)

云環(huán)境下并行DBSCAN聚類算法研究

鄧 青1，楊 寧2

(1.山西輕工職業(yè)技術(shù)學(xué)院,山西 太原 030013；2.山西云時(shí)代技術(shù)有限公司，山西 太原 030006)

DBSCAN算法是一種基于密度的快速聚類算法，雖然在處理大規(guī)模數(shù)據(jù)時(shí)可以發(fā)現(xiàn)其中的噪聲數(shù)據(jù)，但聚類效率不高，輸入/輸出消耗大，聚類結(jié)果準(zhǔn)確率低。本文在云計(jì)算平臺(tái) Hadoop環(huán)境下，將MapReduce編程模型的高并行性引入該算法，設(shè)計(jì)出一種并行 DBSCAN算法，提高傳統(tǒng)DBSCAN算法的執(zhí)行效率，通過(guò)對(duì)比實(shí)驗(yàn)結(jié)果證明了該算法聚類的準(zhǔn)確性和時(shí)效性。

聚類分析；云計(jì)算；DBSCAN；HDFS； MapReduce

聚類分析作為數(shù)據(jù)挖掘與統(tǒng)計(jì)分析的重要研究領(lǐng)域，近年來(lái)倍受關(guān)注。所謂聚類就是將物理或抽象對(duì)象的集合組成為由類似的對(duì)象組成的多個(gè)類的過(guò)程?，F(xiàn)代社會(huì)各行各業(yè)產(chǎn)生的數(shù)據(jù)是海量的，如何從中挖掘出有用的信息，需要借助有效的聚類算法。傳統(tǒng)的聚類算法在處理海量數(shù)據(jù)時(shí)，在時(shí)間復(fù)雜度和空間復(fù)雜度方面很高。而基于云計(jì)算的Mapreduce模型具有較高的并行性，可以與聚類算法進(jìn)行有效結(jié)合，提高聚類算法處理海量數(shù)據(jù)時(shí)的性能。

云計(jì)算作為一種新興的商業(yè)計(jì)算模型，是并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算機(jī)的發(fā)展[1]。Hadoop作為一種能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布式處理的軟件框架，具有伸縮性強(qiáng)、成本低、效率高、可靠性好等優(yōu)點(diǎn)。Hadoop平臺(tái)的核心框架有：分布式文件系統(tǒng)HDFS[2]和計(jì)算模型MapReduce[3]。

HDFS是一個(gè)主從結(jié)構(gòu)，一個(gè)HDFS集群是由一個(gè)名稱節(jié)點(diǎn)(Namenode)和多個(gè)數(shù)據(jù)節(jié)點(diǎn)(Datanode)組成。名稱節(jié)點(diǎn)是一個(gè)管理文件命名空間和調(diào)節(jié)客戶端訪問(wèn)文件的主服務(wù)器，管理對(duì)應(yīng)數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)。在使用上，HDFS與單機(jī)上的文件系統(tǒng)非常類似，同樣可以建目錄，創(chuàng)建、復(fù)制、刪除文件，查看文件內(nèi)容等[4]。

MapReduce是一種并行計(jì)算與運(yùn)行軟件框架，用于大規(guī)模數(shù)據(jù)集(大于1TB)的并行運(yùn)算，也是一種基于集群的高性能并行計(jì)算平臺(tái)。它將數(shù)據(jù)處理分為Map和Reduce兩個(gè)階段，用Map和Reduce兩個(gè)函數(shù)編程實(shí)現(xiàn)基本的并行計(jì)算任務(wù)，提供了抽象的操作和并行編程接口。Map過(guò)程處理接受一個(gè)鍵值對(duì)(key-value對(duì))，產(chǎn)生一組中間鍵值對(duì)，以[key，value]對(duì)方式輸出；Reduce過(guò)程接受一個(gè)鍵，以及相關(guān)的一組值，將這組值進(jìn)行合并產(chǎn)生一組規(guī)模更小的值，最后輸出結(jié)果。所以實(shí)現(xiàn)DBSCAN算法的并行化處理，需要對(duì)Map和Reduce過(guò)程進(jìn)行改進(jìn)設(shè)計(jì)。

1 基于Hadoop的并行DBSCAN聚類算法設(shè)計(jì)

1.1 DBSCAN算法描述

DBSCAN算法是一種簡(jiǎn)單、有效的基于密度的聚類算法，該算法可以過(guò)濾密度較低的樣本點(diǎn)，發(fā)現(xiàn)密度較高樣本點(diǎn)區(qū)域，可以快速發(fā)現(xiàn)任意形狀的類?；舅枷胧牵簩?duì)于一個(gè)類中的每個(gè)樣本，在其給定半徑的鄰域中包含的樣本數(shù)不能少于某個(gè)給定的值。

DBSCAN算法涉及到幾個(gè)重要概念：

Eps鄰域：對(duì)于任意點(diǎn)p，以p為中心，Eps為半徑的區(qū)域構(gòu)成p點(diǎn)的Eps鄰域。

核心點(diǎn)：對(duì)于任意點(diǎn)，如果該點(diǎn)的Eps鄰域內(nèi)的點(diǎn)個(gè)數(shù)超過(guò)給定的閾值MinPts，則該點(diǎn)為核心點(diǎn)。

邊界點(diǎn)：空間中任意點(diǎn)，本身不是核心點(diǎn)，但是落在某個(gè)核心點(diǎn)的Eps鄰域內(nèi)，該點(diǎn)被稱為邊界點(diǎn)。邊界點(diǎn)可能落在多個(gè)核心點(diǎn)的鄰域內(nèi)。

直接密度可達(dá)：對(duì)于樣本集合D，如果樣本點(diǎn)q在p的Eps鄰域內(nèi)，且p為核心點(diǎn)，那么樣本點(diǎn)q從p直接密度可達(dá)。

密度可達(dá)：對(duì)于樣本集合D，給定一串樣本點(diǎn)p1，p2……pn，p=p1，q=pn，如果pi從pi-1直接密度可達(dá)，則q從p密度可達(dá)。密度可達(dá)是直接密度可達(dá)的一個(gè)擴(kuò)展，密度可達(dá)是可以傳遞的，但密度可達(dá)不對(duì)稱。

密度相連：對(duì)于樣本集合D中的任意一點(diǎn)O，若存在點(diǎn)P到O密度可達(dá)，并且點(diǎn)q到O密度可達(dá)，那么q到p密度相連。密度相連是一個(gè)對(duì)稱關(guān)系。

噪聲點(diǎn)：既不是核心點(diǎn)也不是邊界點(diǎn)的任何點(diǎn)。

DBSCAN發(fā)現(xiàn)類的過(guò)程如下：step1，確定算法運(yùn)行所需的兩個(gè)參數(shù)：Eps和MinPts；step2，從樣本集D中選取任意一個(gè)樣本點(diǎn)p，判斷其Eps鄰域內(nèi)點(diǎn)的數(shù)目，如果點(diǎn)數(shù)大于或等于參數(shù)MinPts，則p為核心點(diǎn)；step3，如果p為核心點(diǎn)，構(gòu)建以p為中心的簇，依次將p的Eps鄰域內(nèi)的各點(diǎn)標(biāo)記為與p相同的類標(biāo)識(shí)。如果該鄰域內(nèi)的點(diǎn)q也為核心點(diǎn)，那么q是p的密度可達(dá)點(diǎn)，將點(diǎn)q及其Eps鄰域內(nèi)的點(diǎn)也標(biāo)記為p的類p的E標(biāo)識(shí)；如果q不為核心點(diǎn)，則直接將其標(biāo)記為p的類標(biāo)識(shí)。如果p為邊界點(diǎn)，則p的Eps鄰域包含點(diǎn)數(shù)小于參數(shù)MinPts，沒(méi)有點(diǎn)從p密度可達(dá)，則p標(biāo)記為噪聲點(diǎn)。step4，從樣本集D中選擇下一個(gè)樣本點(diǎn)，重復(fù)進(jìn)行step2、step3，直到樣本集D中沒(méi)有未遍歷的點(diǎn)，聚類過(guò)程結(jié)束。

在數(shù)據(jù)空間中，存在一個(gè)邊界點(diǎn)的鄰域內(nèi)可能包含多個(gè)核心點(diǎn)，這些核心點(diǎn)可能屬于不同的簇。DBSCAN算法沒(méi)有對(duì)這樣的邊界點(diǎn)歸屬問(wèn)題進(jìn)行進(jìn)一步甄別，而采取簡(jiǎn)單的“誰(shuí)發(fā)現(xiàn)歸誰(shuí)所有的策略”[6]。為了提高聚類精度，可以使用基于距離的方法處理邊界點(diǎn)，將邊界點(diǎn)劃入離它距離最近的核心點(diǎn)所屬類中。

DBSCAN算法的思路是通過(guò)對(duì)樣本集D中每個(gè)點(diǎn)Eps鄰域來(lái)判斷其是否為核心點(diǎn)，進(jìn)而決定如何進(jìn)行簇?cái)U(kuò)展。該算法中對(duì)每個(gè)樣本點(diǎn)進(jìn)行計(jì)算，計(jì)算每個(gè)點(diǎn)的時(shí)間復(fù)雜度為O(n)，因此，算法的時(shí)間復(fù)雜度為O(n2)。隨著n的數(shù)量級(jí)增大，串行DBSCAN算法的運(yùn)行時(shí)間也增大，因此對(duì)于串行DBSCAN算法不適合大數(shù)據(jù)量的環(huán)境。而采用并行化處理方式可以提高算法執(zhí)效率?？梢詫?duì)樣本集D均分為q個(gè)子樣本集，對(duì)每個(gè)q進(jìn)行獨(dú)立局部DBSCAN聚類，然后通過(guò)通信輸出全局聚類結(jié)果。

1.2 DBSCAN的MapReduce實(shí)現(xiàn)

MapReduce是一種高效的分布式編程模型，也是一種用于處理和生成大規(guī)模數(shù)據(jù)集的實(shí)現(xiàn)方式。它將數(shù)據(jù)處理分為Map和Reduce兩個(gè)階段。Map過(guò)程處理輸入的對(duì)，產(chǎn)生一些臨時(shí)中間結(jié)果，以對(duì)方式輸出；Reduce過(guò)程合并臨時(shí)對(duì)，集中具有相同key值的value部分，最后輸出結(jié)果。所以要實(shí)現(xiàn)DBSCAN算法的并行化，需要對(duì)Map和Reduce過(guò)程進(jìn)行設(shè)計(jì)。

1.2.1 Map過(guò)程

各節(jié)點(diǎn)將收到的子樣本集歸并為對(duì)，作為Map函數(shù)的輸入。點(diǎn)標(biāo)識(shí)pid作為key值，向量(coretag, usedtag, cid, xi)作為value值，其中coretag表示樣本點(diǎn)是否是核心點(diǎn)，usedtag表示樣本點(diǎn)是否有過(guò)類標(biāo)識(shí)，cid表示類標(biāo)識(shí)，xi表示樣本點(diǎn)各維坐標(biāo)組成的字符串。輸出結(jié)果為，key1存放點(diǎn)標(biāo)識(shí)pid，value1存放類標(biāo)識(shí)cid。

函數(shù)的偽碼為：

Map ( ， ) {

輸入；

調(diào)用initial Cluster ( )函數(shù)； //initial Cluster ( )為初始聚類函數(shù)；

輸出；

}

當(dāng)樣本集很大，劃分后的每個(gè)子樣本集中的樣本較相近時(shí)， Map過(guò)程會(huì)產(chǎn)生成千上萬(wàn)的中間輸出結(jié)果[ key1，value1]記錄，這些龐大的數(shù)據(jù)量將增加網(wǎng)絡(luò)傳送過(guò)程中的通訊代價(jià)。所以，設(shè)計(jì)一個(gè)Combine函數(shù)，對(duì)每個(gè)Map函數(shù)的輸出結(jié)果進(jìn)行本地分類和合并，可以降低網(wǎng)絡(luò)通訊延遲，提高I/O性能。

1.2.2 Combine過(guò)程

Combine函數(shù)將Map函數(shù)的輸出作為輸入，輸出對(duì)，其中key2值為點(diǎn)標(biāo)識(shí)pid，value2值為具有相同pid的樣本序列。函數(shù)偽碼為：

Combine(，){

輸入Map函數(shù)輸出的值；

將pid值相同的點(diǎn)歸為一組，存儲(chǔ)為中間鍵值對(duì)；

Maple在求解推廣的Clairaut型方程中的應(yīng) 用 …………………………………………… 呂曉靜，趙向東（47）

利用分區(qū)函數(shù)hash mod R將中間鍵值對(duì)分成R個(gè)不同的分區(qū)；

輸出不同分區(qū)的鍵值對(duì)；

}

1.2.3 Reduce過(guò)程

執(zhí)行Reduce任務(wù)的處理機(jī)收到Combine過(guò)程分配給自己的那部分?jǐn)?shù)據(jù)后，首先調(diào)用層次合并函數(shù)Hierarchical Merge ( )，對(duì)包含一個(gè)或多個(gè)共享核心點(diǎn)的這些類合并為一類，并賦予統(tǒng)一的類標(biāo)識(shí)。如果其公共點(diǎn)均為共享邊界點(diǎn)，對(duì)比該公共點(diǎn)與其Eps鄰域內(nèi)核心點(diǎn)的距離，將其劃入距離最近的核心點(diǎn)所在類中。直到所有點(diǎn)都具有唯一的類標(biāo)識(shí)。函數(shù)偽碼為：

Reduce ( ， ) {

輸入收到的；

While (存在公共點(diǎn)) {

}

輸出結(jié)果；// key3對(duì)應(yīng)pid，value3對(duì)應(yīng)cid；

}

2 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證基于Hadoop平臺(tái)的DBSCAN算法準(zhǔn)確性和時(shí)效性，分別從標(biāo)準(zhǔn)數(shù)據(jù)集KDD Cup’99和UCI數(shù)據(jù)集中選取兩組數(shù)據(jù)分別進(jìn)行驗(yàn)證。

表1給出單機(jī)環(huán)境和基于Hadoop平臺(tái)下算法對(duì)數(shù)據(jù)樣本集Dataset1(KDD Cup’99選取)的聚類結(jié)果。對(duì)比兩種模式下聚類正確率差異，驗(yàn)證了基于Hadoop平臺(tái)的聚類準(zhǔn)確性不差。

為驗(yàn)證基于Hadoop平臺(tái)算法的時(shí)效性，將從UCI數(shù)據(jù)集中選擇的樣本集Dataset2進(jìn)行多次復(fù)制獲得大規(guī)模數(shù)據(jù)，并在單機(jī)和平臺(tái)上進(jìn)行運(yùn)行。其對(duì)比結(jié)果如圖1所示。

表1 單機(jī)和基于Hadoop平臺(tái)聚類準(zhǔn)確率比較

圖1 單機(jī)和基于Hadoop平臺(tái)聚類時(shí)效性對(duì)比

從圖上看出，基于Hadoop平臺(tái)的DBSCAN算法執(zhí)行時(shí)效性很高，特別是數(shù)據(jù)量越大，優(yōu)勢(shì)越明顯，因此更適合于對(duì)大數(shù)據(jù)的挖掘和分析。

3 總結(jié)

本文介紹了云平臺(tái)Hadoop的MapReduce分布式編程模型，并對(duì)基于密度的DBSCAN算法的思想和流程進(jìn)行了描述，給出基于MapReduce的并行DBSCAN算法的實(shí)現(xiàn)思路并給出Map、Combine、Reduce過(guò)程的偽代碼設(shè)計(jì)，通過(guò)實(shí)驗(yàn)數(shù)據(jù)證明了算法的正確性和時(shí)效性。

[1] Kai Hwang,Geoffrey C.Fox ,Jack J.Dongarra.云計(jì)算與分布式系：從并行處理到物聯(lián)網(wǎng)[M].北京：機(jī)械工業(yè)出版社,2013.

[2] Ghemawat S,Gobioff H,Leung S.The Google File System[J].SACM SIGOPS Operating Systems Review,2003,37(5)：29-40.

[3] Dean J,Ghemawat S.Map Reduce: Simplified Data Processing on Large Clusters[C]//Proceedings of Operating Systems Design and Implementation.San Francisco,CA,2004:137-150.

[4] 趙衛(wèi)中,馬慧芳.基于云計(jì)算平臺(tái)Hadoop的并行k-means聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué)，2011(10)：166-168，+176.

[5] 謝雪蓮,李蘭友.基于云計(jì)算的并行K-means聚類算法研究[J].計(jì)算機(jī)測(cè)量與控制，2014，22(5)：1510-1512.

[6] 蔡穎琨,謝昆青.屏蔽了輸入?yún)?shù)敏感性的DBSCAN改進(jìn)算法[J].北京大學(xué)學(xué)報(bào)(自然科學(xué)版)，2004，40(3)：480-486.

ResearchonParallelDBSCANClusteringAlgorithminCloudEnvironment

Deng Qing1， Yang Ning2

(1.ShanxiLightIndustryCareerTechnicalCollege,TaiyuanShanxi030013,China;2.ShanxiCloudTechnologyCo.,Ltd.,TaiyuanShanxi030006,China)

DBSCAN algorithm is a density-based fast clustering algorithm. Although the noise data can be found when dealing with large-scale data, the clustering efficiency is not high, the input / output consumption is large and the accuracy of clustering results is low. In this paper, the parallelism of the MapReduce programming model is introduced into the Hadoop environment, and a parallel DBSCAN algorithm is designed to improve the efficiency of the traditional DBSCAN algorithm. The accuracy of the algorithm is proved by comparing the experimental results and timeliness.

clustering analysis; cloud computing; DBSCAN; HDFS; MapReduce

2017-10-10

鄧 青(1983- )，女，山西大同人，講師，碩士研究生，研究方向：數(shù)據(jù)挖掘、智能算法。

1674- 4578(2017)06- 0087- 04

TP311.13；TP301.6

A