基于spark框架的DBSCAN文本聚類算法

寧建飛

（羅定職業(yè)技術(shù)學院電子信息系，廣東 羅定 527200）

0 引言

隨著互聯(lián)網(wǎng)以及計算機存儲技術(shù)的發(fā)展，每天產(chǎn)生的數(shù)據(jù)正在以PB級的速度增長，文本數(shù)據(jù)是一類非常重要的數(shù)據(jù)格式，包含了非常多的信息，將文本數(shù)據(jù)分門別類將有助于人們快速的進行信息檢索.在大數(shù)據(jù)技術(shù)日漸成熟的環(huán)境下，將機器學習算法應用于分布式環(huán)境中已經(jīng)成為了一種趨勢，通過分布式的計算力將算法的效率提高.機器學習中的聚類算法是處理文本的一種經(jīng)典解決方案，其中，基于密度的DBSCAN算法以其收斂速度快，易于發(fā)現(xiàn)噪聲的優(yōu)點而常常被應用于內(nèi)容過濾、異常數(shù)據(jù)檢測等各種場景.

近年來，針對DBSCAN算法在單機上的計算瓶頸，國內(nèi)外學者對DBSCAN聚類算法進行并行化的研究.何中勝等[1]提出了在主機集群上運行基于數(shù)據(jù)分區(qū)的并行化PDBSCAN，降低了算法運行的時間，提升了聚類的性能，但是I/O消耗仍然比較嚴重.宋明等[2]提出了基于數(shù)據(jù)交疊分區(qū)的并行OPDBSCAN，減少了節(jié)點之間局部簇合并時的通信量，但是聚類質(zhì)量下降.但是以上兩類并行化算法在高緯度數(shù)據(jù)時效率不明顯.為了應對高維數(shù)據(jù)，MR-DBSCAN[3]提出了基于MapReduce平臺下的DBSCAN并行算法，通過數(shù)據(jù)劃分的方法，解決了海量的低維數(shù)據(jù)集，在進行數(shù)據(jù)劃分時產(chǎn)生的負載問題，然而，高維數(shù)據(jù)的問題還是沒有能夠得到解決.SNN相似矩陣的出現(xiàn)解決了高維度數(shù)據(jù)相似度定義模糊的問題，JP[4]聚類算法就是利用了SNN相似矩陣進行聚類.本文結(jié)合SNN相似度的定義以及MapReduce計算模型將DBSCAN聚類算法在Spark平臺上進行改進，并且應用于文本聚類上.

本文主要研究DBSCAN聚類算法在spark數(shù)據(jù)處理平臺的應用，在進行文本處理時，引入了SNN相似度的概念使得DBSCAN聚類在文本數(shù)據(jù)上有效，并且將SNN相似度結(jié)合到DBSCAN中并行化.SNN相似度算法并行化將形成多個K近鄰子矩陣，將其合并后能夠計算出SNN密度，從而得到文檔之間相似度的度量，再進行DBSCAN算法的聚類并行化，通過數(shù)據(jù)劃分，使得每一個工作節(jié)點進行DBSCAN局部聚類，在將局部聚類結(jié)果合并，從而達到DBSCAN文本聚類的目的.本文算法將DBSCAN聚類算法應用在spark平臺上，速度相比于單機的DBSCAN聚類[17]以及基于Hadoop平臺的DBSCAN聚類均有不錯的提升.

1 相關(guān)工作

1.1 SNN相似度圖

共享最近鄰（SNN）相似度適用于高維數(shù)據(jù)之間的相似度計算.它的核心思想是：兩個數(shù)據(jù)對象假設(shè)互為共享最近鄰，則相似度為兩個數(shù)據(jù)對象的K近鄰鄰居對象中相同數(shù)據(jù)的數(shù)目.如果兩個對象共享最近鄰點的數(shù)目越多，那么這兩個對象的相似度就越高，這兩個對象歸為同一類的可能性越大；如果兩個對象不是在對方的最近鄰表中，那么這兩個對象的相似度為0.相似度的計算公式如式（1）.

NN（p）和NN（q）分別是對象p和對象q的最近K鄰近表.

SNN相似度只依賴于兩個數(shù)據(jù)對象間共享的最近鄰對象個數(shù)，而不是最近鄰對象的距離，由于SNN相似度反映了數(shù)據(jù)空間中點的局部結(jié)構(gòu)，因此它對密度的變化和空間維度不敏感，所以SNN相似度可以用來作為新的密度，尤其是在高維數(shù)據(jù)的相似性比較上，SNN非常適用.

1.2 DBSCAN聚類算法

DBSCAN聚類算法是經(jīng)典的基于密度的聚類算法，該算法有兩個重要的參數(shù)，一個是全局密度半徑Eps，一個是密度閾值MinPts，它的核心思想是聚類中的每一個核心對象，在某個密度半徑內(nèi)數(shù)據(jù)對象大于某個密度閾值.給定一個數(shù)據(jù)集0，1，2，…n}，對于任意點 p（i），計算點 p（i）到集合中的剩余點 p（1），p（2），…，p（i-1），p（i+1），…p（n）的距離，將距離按照從小到大的順序進行排列，則第k個點的距離稱為k-dist，對集合中的每個點都需要計算k-dist，最后得到一個所有點的k-dist集合.在得到k-dist集合之后，對k-dist集合進行升序排序，然后擬合一條排序后的k-dist集合中k-dist的變化曲線，畫出曲線進行觀察，將曲線突變的位置所對應的的k-dist的值作為半徑Eps的值.根據(jù)經(jīng)驗定義一個密度閾值MinPts來作為計算使用.在迭代結(jié)束之后，如果聚類結(jié)果不理想可以適當?shù)卣{(diào)整Eps和MinPts的值，再進行迭代計算，在進行多次迭代計算對比之后，選擇比較合適的參數(shù).如果Eps取值過大，則會導致同一個聚類簇中包含太多的點，如果Eps取值過小，則會導致聚類簇過多；如果MinPts取值過大，則會發(fā)現(xiàn)同一簇中的點被標記為噪聲點，如果MinPts取值過小，則會導致核心點的數(shù)目增多.因此，合理的選擇兩個參數(shù)是這個算法的關(guān)鍵步驟之一.

DBSCAN算法的具體步驟是：

（1）預處理數(shù)據(jù)文件；

（2）計算每個點與其他所有點之間的距離；

（3）計算每個點的k-dist值，并且對所有點的k-dist集合進行升序排序，輸出排序后的k-dist值；

（4）繪制 k-dist圖；

（5）根據(jù)k-dist圖確定密度半徑Eps；

（6）給定MinPts，計算核心點，并且建立核心點與核心點距離小于密度半徑Eps的點的映射；

（7）計算連通的核心點，并且將噪聲點去除；

（8）將每一組核心點和到該點距離小于半徑Eps的點，放在一起形成一個聚類簇.

DBSCAN算法通過將高密度的區(qū)域聚成簇，并且可以發(fā)現(xiàn)任意形狀的簇，有效地處理噪聲數(shù)據(jù).但是在DBSCAN算法中也有著明顯的缺陷，即參數(shù)Eps的選擇對聚類結(jié)果的影響非常大，并且目前還沒有完善的解決方案.在繪制k-dist圖時，DBSCAN算法將會耗費大量的時間，并且當數(shù)據(jù)量增大時，內(nèi)存和I/O消耗將會激增.

1.3 Spark框架

Spark是UC Berkeley AMP lab（加州大學伯克利分校的AMP實驗室）所開源的并行計算框架.Spark框架的計算基于內(nèi)存運行，并且提供了一種分布式的并行的數(shù)據(jù)結(jié)構(gòu)-彈性數(shù)據(jù)集RDD（Resilient Distributed Datasets）.Spark使用Scala編寫，Spark可以和Scala集成，使得Scala可以靈活的操作分布式數(shù)據(jù)集.Spark支持分布式數(shù)據(jù)集的迭代算法，可以集成于Hadoop的文件系統(tǒng)之上，因而構(gòu)建于Spark上的算法處理大規(guī)模的數(shù)據(jù)非常方便和迅速.

在Spark框架被設(shè)計出來之前，處理大數(shù)據(jù)的解決方案是Hadoop，Hadoop以其分布式的MapReduce程序著稱，可以計算PB級別的數(shù)據(jù)，但是Hadoop也存在著明顯的瓶頸，當算法的復雜度增加，迭代次數(shù)上升，那么基于Hadoop的MapReduce框架就會不停的進行磁盤的IO，因為每一次迭代的計算結(jié)果都需要寫回磁盤然后再讀到內(nèi)存做下一次的迭代計算，這無疑提高了時間成本，而新一代的計算框架Spark則大大的節(jié)省了時間成本，它在迭代計算過程中并不將數(shù)據(jù)寫回磁盤，而是保存在內(nèi)存中供下一次計算使用，減少了磁盤IO，并且Spark框架并不僅僅在于內(nèi)存計算，它還可以將整個執(zhí)行計劃解析成一個DAG（Directed Acyclic Graph）圖，每個節(jié)點是一個stage，然后可以自動的對stage進行優(yōu)化，使得效率提升.

RDD是Spark一切的基礎(chǔ).RDD是一個分布式的內(nèi)存抽象，數(shù)據(jù)在各節(jié)點中分區(qū)，而RDD則是分區(qū)的集合.RDD來源廣泛，可以從集合中轉(zhuǎn)換而來，也能從HBase數(shù)據(jù)庫中讀取，更可以從Hadoop文件系統(tǒng)中讀取.在每一個分區(qū)數(shù)據(jù)上都會有一個程序函數(shù)去對這些數(shù)據(jù)進行計算，并且RDD之間會產(chǎn)生依賴關(guān)系，RDD可以生成新的RDD.Spark的設(shè)計延續(xù)了Hadoop許多優(yōu)秀的理念，比如數(shù)據(jù)就近讀取等等.Spark處理數(shù)據(jù)的流程圖如圖1所示.首先從文件系統(tǒng)中讀取數(shù)據(jù)集，然后Spark程序兩個核心步驟：轉(zhuǎn)換和執(zhí)行.轉(zhuǎn)換是一個延遲執(zhí)行過程，程序只被記錄但是不執(zhí)行，知道Action真正觸發(fā)才會執(zhí)行程序.

隨著Spark的發(fā)展，Spark框架已經(jīng)漸漸超過Hadoop成為大數(shù)據(jù)的首選解決方案，將機器學習算法并行化到Spark上已經(jīng)有許多的成功的例子，例如Kmeans，SVM，貝葉斯分類等等，這些算法很多都已經(jīng)成為Spark MLlib的工具類.在國內(nèi)外學者的推動下，Spark MLlib庫也將會越來越豐富.

圖1 Spark程序執(zhí)行步驟

2 DBSCAN算法的并行化實現(xiàn)

傳統(tǒng)DBSCAN聚類算法計算速度快，但是在處理多維度的數(shù)據(jù)時，密度定義模糊，因此DBSCAN算法在高維數(shù)據(jù)上的聚類效果不佳，并且隨著數(shù)據(jù)量提高，運算時間激增，會影響聚類的質(zhì)量.針對以上的問題，本文引入了文獻[4]中的SNN相似度來改進DBSCAN算法，使之能夠適應高維的文本數(shù)據(jù)，并且通過生成SNN密度，每個節(jié)點計算數(shù)據(jù)集的子連通圖，也就是進行DBSCAN局部聚類，每個節(jié)點計算完了之后進行一次全局的合并，從而達到算法的并行化，使用Spark的RDD可以減少大量的I/O，并且大大的提升了迭代的速度.

2.1 基于SNN相似度的DBSCAN聚類

SNN相似度是基于JP[4]算法實現(xiàn)的，根據(jù)文本的數(shù)據(jù)，JP算法的數(shù)據(jù)輸入文檔-權(quán)重矩陣，每一行都是一個文本形成的向量，每個向量中的元素等于特征項的權(quán)重.基于SNN相似度的DBSCAN算法采用SNN相似度來作為聚類的依據(jù)，具體步驟如下：

（1）計算相似度構(gòu)造鄰近度矩陣；

（2）根據(jù)K最近鄰將鄰近度矩陣稀疏化；

（3）構(gòu)造SNN圖；

（4）根據(jù)SNN圖計算SNN密度；

（5）使用DBSCAN聚類算法根據(jù)SNN密度進行聚類算法的核心點在于SNN最近鄰表的創(chuàng)建.

2.2 DBSCAN算法的并行化

Spark框架中的RDD底層接口中有非常多的接口是基于迭代器的，在Spark中運行程序能夠避免非常多的磁盤I/O操作，計算效率大大的提高.并且Spark提供了緩存和分區(qū)供用戶對RDD控制，例如將某些數(shù)據(jù)緩存起來，從而提高執(zhí)行的性能.

由于文本數(shù)據(jù)量比較大，本文對一些細節(jié)進行了優(yōu)化，采用了Kryo序列化方式來取代默認的Java序列化方式，提高了效率.

算法是基于MapReduce模型的，master服務(wù)器負責分配數(shù)據(jù)塊，map任務(wù)之間互不影響，并且以[key，value]的形式傳遞給reduce，reduce對中間結(jié)果進行進一步的計算.

本文針對DBSCAN算法主要并行化的過程分為兩步：一是構(gòu)建SNN相似度，二是DBSCAN算法的并行化.文本數(shù)據(jù)預先進行分詞、去除停用詞等等清洗工作.

2.2.1 SNN相似度算法并行化

Map階段每一個map完成一部分數(shù)據(jù)的鄰近度計算，假設(shè)INDEX是起始文檔的下標，SIZE是該map中處理的文檔個數(shù).Map階段的偽代碼如下：

reduce階段所做的工作比較簡單，只需要將部分的KNN矩陣合并在一起，最終輸出一個全局的稀疏化矩陣K，生成的稀疏化矩陣可以計算出SNN密度，可供下一階段的DBSCAN算法中使用，并且在spark中，可以利用廣播變量將SNN密度在每一臺節(jié)點上做一個只讀的緩存，從而在下一步，節(jié)點內(nèi)部可以進行局部的DBSCAN聚類.因為文檔與文檔之間的相似度已經(jīng)得到了度量，因而在接下來的聚類中，文檔聚類等價于點聚類.

2.2.2 DBSCAN聚類并行化

數(shù)據(jù)劃分：為了提高計算效率，是DBSCAN算法并行化，對數(shù)據(jù)進行均勻的劃分是非常必要的，由于在上一步已經(jīng)得到了SNN密度，文檔空間的特征不明顯，因而選擇均勻地劃分，這樣犧牲了一點性能，但是對總的運行速度影響不大.

局部聚類：數(shù)據(jù)劃分好以后，每一個劃分好的數(shù)據(jù)會由master節(jié)點分發(fā)到一個計算節(jié)點worker上，worker節(jié)點根據(jù)廣播變量SNN密度，選取一個局部的Eps值.再通過SNN密度得到文檔之間的相似度，然后采用DBSCAN算法對節(jié)點中的數(shù)據(jù)進行局部DBSCAN的聚類.

局部聚類合并：在所有數(shù)據(jù)分區(qū)聚類完成了之后，必然會存在著全局性不足的問題，因此，需要對局部聚類進行合并.有以下三類的數(shù)據(jù)需要進行合并：

（1）兩個類本屬于同一個類，但是由于在不同分區(qū)，被分成了兩個類.這種情況需要滿足：兩個類的數(shù)據(jù)處于相鄰分區(qū)中并且兩個類別中任意兩個的邊界區(qū)域點之間的相似度應當不小于兩個類的Eps.

（2）某類中的噪聲點本應屬于另一個類，但是由于處于另一個分區(qū)而導致被判別為噪聲數(shù)據(jù).假設(shè)A類中的噪聲點p屬于另一個類B，則應該滿足B類中的任意數(shù)據(jù)點q與p的相似度不小于B類的Eps，并且A，B類處于相鄰的分區(qū).

（3）一些小類中的數(shù)據(jù)由于被分散而且數(shù)量少，導致都被視作成了噪聲數(shù)據(jù)，那么這些數(shù)據(jù)應該被歸為新的一類.歸類的條件應當滿足：假設(shè)A，B是兩個相鄰分區(qū)的類，EA，EB分別為他們的邊界區(qū)域點集，S為EA，EB的噪聲點集.如果存在S中的某個點p，p與S中點相似度不小于A，B的Eps的數(shù)量大于MinPts，那么可以認為p是新的核心對象，其他數(shù)據(jù)與p歸為一類新類.

在并行化過程中，相鄰分區(qū)之間需要互相發(fā)送邊界區(qū)域點集以完成最后的局部聚類合并.在完成最終的聚類之后，需要根據(jù)結(jié)果調(diào)整Eps參數(shù)，得出最佳的聚類結(jié)果.

3 實驗結(jié)果與分析

3.1 實驗環(huán)境與數(shù)據(jù)集

本實驗采用的云計算數(shù)據(jù)平臺是apache開源的spark1.6.2版本以及Hadoop2.6.2版本，Hadoop提供HDFS存儲以及yarn資源調(diào)度，spark提供計算框架.硬件環(huán)境為5個節(jié)點，1個 Namemode（spark的 Master節(jié)點），4個Datanode（spark的 Worker節(jié)點）.Namenode節(jié)點的機器配置為：Intel Core I7-4720HQ，8G內(nèi)存，500G硬盤，Datanode節(jié)點的機器配置為：Intel Core I5-4430，4G內(nèi)存，500G硬盤.軟件環(huán)境配置為：CentOS 6.5版本，JDK1.8.0_60，Scala2.11.8，InteliJ IDEA 14.1.5版本.Hadoop的安裝配置方式為HDFS+HA的方式.

本實驗的語料數(shù)據(jù)來源于網(wǎng)絡(luò)新聞數(shù)據(jù)，通過爬蟲抓取國際，體育，社會，娛樂等18個頻道的新聞數(shù)據(jù)，共8 236篇文檔.為了能夠進行聚類分析，必須對語料數(shù)據(jù)進行預處理，通過分詞、停用詞過濾、特征降維和文本表示模型，轉(zhuǎn)化成聚類算法能夠處理的向量形式.文本預處理中采用的分詞工具為中科院的自然語言處理工具HanLP，停用詞表使用的是HanLP項目中的數(shù)據(jù)，文本表示采用向量空間模型對每個文本進行表示.

3.2 實驗結(jié)果與分析

在Spark計算框架中對已經(jīng)預處理的預料數(shù)據(jù)進行DBSCAN文本聚類處理，并且在聚類過程中對比不同的Eps值和MinPts值來選取最佳的聚類效果，最后通過單節(jié)點和多節(jié)點的運行時間、以及與Hadoop平臺上相同節(jié)點數(shù)算法的加速比來檢驗算法的性能.加速比定義為算法在一個節(jié)點上的運行時間與算法在N個節(jié)點上的運行時間的比值.

從聚類結(jié)果分析，如表1，有部分文檔并沒有成功歸類，被DBSCAN列為了噪點，并且有一部分文檔歸類不準確.通過表格可以看出，數(shù)據(jù)量過大，會導致聚類簇的增多.娛樂類的準確率較低，可能的原因有文檔的特征代表性不夠，使得區(qū)分度不夠，使得娛樂類的文檔歸到了社會類之中；體育類的準確度較高，可能的原因是體育類的特征詞代表性比較強，例如裁判，比賽，球員等等.但從總體來看，DBSCAN算法在spark平臺上進行文本聚類還是可行并且有效的，能夠?qū)⑾嗨频奈谋練w為一類.

表1 聚類結(jié)果

通過圖2的曲線可以看出，隨著數(shù)據(jù)量的增大，spark環(huán)境下的運行時間消耗明顯少于單機的時間消耗，并且多節(jié)點的運行時間隨著數(shù)據(jù)量的增加并沒有呈現(xiàn)出快速增長的趨勢而單節(jié)點在隨著數(shù)據(jù)量的增大出現(xiàn)了運行時間激增的情況，表明算法的并行化處理效率更高，性能更好.

由圖3可得數(shù)據(jù)集在Spark框架下的加速比明顯優(yōu)于數(shù)據(jù)集在Hadoop框架下的加速比，并且隨著節(jié)點數(shù)的增加，數(shù)據(jù)集在Spark框架下的加速比上升趨勢也隨著變換，這是由于節(jié)點間的通信量增加以及I/O次數(shù)增加導致的.由此可見，相比于Hadoop，DBSCAN算法在Spark框架下的表現(xiàn)更能適應大數(shù)據(jù)的環(huán)境，并且算法還有值得優(yōu)化的地方，因而DBSCAN算法在Spark框架下的性能是可觀的.

圖2 單節(jié)點和多節(jié)點環(huán)境下的算法執(zhí)行效率對比

圖3 兩種架構(gòu)加速比比較

4 結(jié)語

本文針對基于密度的DBSCAN聚類算法內(nèi)存和I/O消耗嚴重的問題以及當前的大數(shù)據(jù)背景，提出了基于Spark框架的并行化DBSCAN算法，并且對DBSCAN算法進行了改進，采用SNN相似度使其能夠適應高維數(shù)據(jù)的聚類，有效的減少了內(nèi)存消耗的問題以及提高了算法運行的性能.實驗結(jié)果表明本文提出的算法相較于傳統(tǒng)的DBSCAN聚類算法能夠處理高維度的數(shù)據(jù)集，并且與Hadoop平臺下的DBSCAN算法相比在文本聚類的時間有了明顯的下降.但是由實驗步驟可知，算法并未完全的并行化，數(shù)據(jù)的預處理步驟以及數(shù)據(jù)的存儲在HBase上等步驟都需要額外執(zhí)行，本文單從DBSCAN算法的運行時間分析，有明顯的速度提升，下一階段的工作希望能夠?qū)BSCAN算法完全并行化，并且減少算法對參數(shù)的敏感度，增加自適應性.

[1]何中勝，劉宗田，莊燕濱.給予數(shù)據(jù)分區(qū)的并行DBSCAN算法[J].小型微型計算機系統(tǒng)，2006，27（1）：114-116.

[2]宋明，劉宗田.基于數(shù)據(jù)交疊分區(qū)的并行DBSCAN算法[J].計算機應用研究，2007，21（7）：17-20.

[3]HE Y B，TAN H Y，LUO W M，et al.MR-DBSCAN：An efficient parallel density-based clustering algorithm using MapReduce[C]//2011 IEEE 17th International Conference on Parallel and Distributed Systems，2011：473-480.

[4]JARVIS R A，PATRICK E A.Clustering using a similarity measure based on shared nearest neighbors[J].IEEE Transaction on Computer，1973，22（11）：1025-1034.

[5]周水庚，周傲英，曹晶.給予數(shù)據(jù)分區(qū)的DBSCAN算法[J].計算機研究與發(fā)展，2000，37（10）：1153-1159.

[6]郗洋.基于云計算的并行聚類算法研究[D].南京：南京郵電大學，2012.

[7]BECKMANN N，KRIEGEL H，SCHNEIDER R，et al.The R*-tree：an efficient and robust accross method for points and rectangles[J].International Conference on Management of Data，1990，19（2）：322-331.

[8]于蘋蘋，倪建成，姚彬修，等.基于Spark框架的高效KNN中文文本分類算法[J].計算機應用，2016，36（12）：3292-3297.

[9]鄒艷春.基于DBSCAN算法的文本聚類研究[J].軟件導刊，2016，15（8）：36-38.