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

寧建飛

（羅定職業技術學院電子信息系，廣東 羅定 527200）

0 引言

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

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

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

1 相關工作

1.1 SNN相似度圖

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

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

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

1.2 DBSCAN聚類算法

DBSCAN聚類算法是經典的基于密度的聚類算法，該算法有兩個重要的參數，一個是全局密度半徑Eps，一個是密度閾值MinPts，它的核心思想是聚類中的每一個核心對象，在某個密度半徑內數據對象大于某個密度閾值.給定一個數據集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的值.根據經驗定義一個密度閾值MinPts來作為計算使用.在迭代結束之后，如果聚類結果不理想可以適當地調整Eps和MinPts的值，再進行迭代計算，在進行多次迭代計算對比之后，選擇比較合適的參數.如果Eps取值過大，則會導致同一個聚類簇中包含太多的點，如果Eps取值過小，則會導致聚類簇過多；如果MinPts取值過大，則會發現同一簇中的點被標記為噪聲點，如果MinPts取值過小，則會導致核心點的數目增多.因此，合理的選擇兩個參數是這個算法的關鍵步驟之一.

DBSCAN算法的具體步驟是：

（1）預處理數據文件；

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

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

（4）繪制 k-dist圖；

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

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

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

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

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

1.3 Spark框架

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

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

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

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

圖1 Spark程序執行步驟

2 DBSCAN算法的并行化實現

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

2.1 基于SNN相似度的DBSCAN聚類

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

（1）計算相似度構造鄰近度矩陣；

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

（3）構造SNN圖；

（4）根據SNN圖計算SNN密度；

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

2.2 DBSCAN算法的并行化

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

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

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

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

2.2.1 SNN相似度算法并行化

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

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

2.2.2 DBSCAN聚類并行化

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

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

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

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

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

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

在并行化過程中，相鄰分區之間需要互相發送邊界區域點集以完成最后的局部聚類合并.在完成最終的聚類之后，需要根據結果調整Eps參數，得出最佳的聚類結果.

3 實驗結果與分析

3.1 實驗環境與數據集

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

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

3.2 實驗結果與分析

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

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

表1 聚類結果

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

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

圖2 單節點和多節點環境下的算法執行效率對比

圖3 兩種架構加速比比較

4 結語

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

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

[2]宋明，劉宗田.基于數據交疊分區的并行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]周水庚，周傲英，曹晶.給予數據分區的DBSCAN算法[J].計算機研究與發展，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.