面向大數據的并行聚類算法

劉解放，張志輝

(1.湖北交通職業技術學院 交通信息學院，湖北 武漢 430079； 2.武漢科技大學 計算機科學與技術學院，湖北 武漢 430081)

0 引 言

大數據對社會具有潛在價值，它正在推動行業研究人員重新思考計算方案來獲取有用信息。但由于高計算成本，使得分析和檢索操作非常耗時。因此，高性能計算，如并行計算[1]、分布式計算[2]、云計算[3]和網格計算[4]等無疑是未來解決上述問題的重要手段。

聚類本質上是一種典型的“無監督”數據分析方法，但到目前為止，已提出的所有經典算法都需要用戶的大量指導，例如K-means需要預先指定聚類個數和終止條件。最近提出的CLUBS[5]，是一種非常有效的聚類算法，無需用戶任何指導，通過4個階段的不斷完善，自動完成聚類任務。它不但能夠容忍一定程度的過度分割，而且能夠處理異常點的檢測及橢圓簇的生成。遺憾的是，該算法針對大數據應用場景無能為力。

本文結合高性能計算提出了CLUBS的并行版本，稱為CLUBS‖，類似CLUBS，CLUBS‖時間復雜度關于數據集大小線性縮放，并基于Ad-hoc消息傳遞實現了所提聚類算法。實驗結果表明，隨著越來越多的并行節點加入運算，加速比幾乎是線性的。CLUBS‖的特性使它可以有效聚類大規模數據，且不要求節點間交換原始數據，僅需交換摘要信息。

1 相關工作

大數據的出現重新激發了研究人員對數據挖掘基礎工具的興趣，例如聚類。為克服聚類的計算復雜度，研究人員已經提出許多方法，無論是單機還是聯機方案。

單機版的大數據聚類經典方法大都基于采樣、降維和分塊技術，例如，文獻[6]提出了一種基于加速比和勢分布的采樣方法，通過使用采樣技術減少求解搜索空間，極大地提高了大數據處理的性能；文獻[7]基于隨機投影技術降低數據維度提出了一種聚類方法WOMP-GS-FIS，該方法盡可能保持了樣本點間的距離；文獻[8]通過將貝葉斯模糊聚類與分塊技術相結合，提出了一種面向大規模數據的快速單趟貝葉斯模糊聚類算法SPBFC。

盡管以上方法顯著減少了大規模數據聚類的計算時間，但是，在給定的時間內，數據量的增長遠遠快于單機處理能力的增長。這使得必須使用并行技術，但是，并行技術由于某些關鍵因素而帶來極大挑戰，例如協同工作、網絡通信、資源共享和容錯能力等，實現難度較大。目前，有些經典算法被改寫實現了并行化，其中K-means‖[9]是一個非常成功的案例，它采用播種算法，即使在單機上運行，也優于K-means。

2 CLUBS

最近提出的CLUBS[5]是一種基于快速分層的無參數中心聚類算法。它融合了分裂和凝聚兩種優點。首先，使用二叉空間分割技術對數據集進行定義，并生成一系列的初始簇，其次，對生成的簇進行調整，然后，對簇進行凝聚，最后再完善。在完善階段，異常點被標記，其余的點被分配到最近的簇。圖1展示了CLUBS在二維數據上的執行過程，圖1(a)為原始圖，圖1(b)～圖1(e)為各步驟的執行結果。下面簡要介紹它4個核心步驟。

圖1 CLUBS在二維數據上的執行過程

2.1 分裂階段

CLUBS采用自頂向下二叉空間分割技術將數據集分割成為一系列的超矩形塊，使得各塊內部點盡可能靠近，這等價于最小化簇內平方和(WCSS)。CLUBS要求分割的超平面正交與坐標軸，并使用貪婪準則，塊被迭代分割為成對的簇。

給定一個數據集，該算法將其作為一個簇S，S進入優先級隊列Q，Q包含所有迭代分割的塊。如果Q非空，從中出隊一個塊B， 并將其劃分為一對塊，如果劃分有效，該對塊替代B并進入隊列，否則，B成為最終的塊。

將所有屬于塊B， 且第i維坐標值等于x的點p求和，該函數可以表示為圖或數組。文獻[5]表明最小化WCSS的分割可以通過圖或數組的線性掃描產生。

該階段選擇了CH指標[10]評估聚類質量。每次分割之后，都會重新計算CH值，如果CH值增加，則分裂階段有效并繼續，若降低到70%以下，則停止本次分割。

2.2 調整階段

分裂階段結束后，整個數據空間被分割為兩類塊：一類是每塊僅含有一個簇，另一類是每塊僅含噪聲。調整階段，CLUBS力求實現兩個任務：①將含有簇的塊分離出來；②將分離出來的塊生成一個橢圓簇。

因僅含有噪聲塊的密度較低，因此可以通過觀察實施第一個任務。CLUBS首先基于密度對所有塊進行遞增排序，并檢測相鄰塊間的密度跳躍，從而確定噪聲塊的候選子集。然后，測試候選子集，例如，在塊的中心生成一個較小的超立方體，如果超立方體的密度明顯大于整個塊的密度，則表明該塊屬于異常塊，否則屬于簇塊。例如，圖1中J、K、L和M都是異常塊。

2.3 凝聚階段

凝聚階段，通過合并上一階段產生的簇，改進聚類質量。如果合并一對簇導致WCSS較小增加，而CH指標顯著增加，實施合并，并將合并后的簇替代原有的兩個簇。如果合并導致CH指標嚴重降低，則取消，凝聚階段結束。實際上，僅有相鄰簇才考慮是否合并，因為相鄰簇的合并才有可能導致WCSS較小增加和CH指標顯著增加。圖1(d) 展示了簇B是由圖1(c)中簇B和簇I合并而成。

2.4 完善階段

由于前期采用了近似和貪婪準則，凝聚階段通常會產生形狀稍不規則的簇。例如，圖1(d)中簇B，它是由圖1(c) 中簇B和簇I合并而成。由于調整階段，圖1(b)中塊K被認定為異常塊，其左上角的點被塊B和I非對稱吸附，因此導致明顯不對稱。完善階段重構橢圓簇，不僅提高了聚類質量，并且還確定了最終異常點。

3 CLUBS‖∶CLUBS的并行化

假設有N個從節點，它們都具有相同的硬件特性，并具有本地存儲和計算能力，數據分布在從節點上，能存儲在分布式文件系統上或本地文件系統上。

多個從節點高效運行的關鍵問題是如何協同訪問數據，其中包括：①分裂階段邊緣分布的計算；②調整階段候選離群塊的局部密度計算；③完善階段將點分配給最近簇計算。

下面將重點分析上述3個關鍵計算的并行化，關于其它計算，如摘要信息的計算，則使用CLUBS原有方法通過主節點處理。

3.1 邊緣分布的并行計算

邊緣分布的并行計算，也即是向量C和S的計算，它們是分裂階段唯一需要訪問數據的計算。由于計數運算和求和運算的結合性和可交換性，該計算可高效地并行執行。因此，給定一個數據集的塊劃分 {B1,…,Bk}， 可獨立計算各塊Bk上C和S向量，最終，求和各塊上的向量得到數據集的全局向量。根據MapReduce范式，各塊Bk被映射為一系列向量對，表示各塊每個維度的C和S， 通過求和相同維度的向量，這些向量隨后被約簡。

3.2 塊局部密度的并行計算

為實現調整階段第一個任務，需計算塊的局部密度。在分裂階段，主節點獲得所有劃分塊的信息，因此，主節點可以獲得各塊的全局密度和范圍。為檢查塊質心附近的局部密度是否明顯高于全局密度，需要計算質心附近小范圍內的局部密度(例如，整塊的1/10)，然后并行計算落入“受限”范圍內的點數。盡管在這種情況下，該計算涉及到的唯一數學運算是求和，因此，計算完全可并行化。實際上，對于數據塊的各個部分，都可以獨立計算點數，然后，將各部分的點數相加求和即可得到總的點數。因此，主節點可以計算局部密度。

3.3 點到簇的并行分配計算

將點分配給最近的簇或者將其作為異常點，每一個從節點在調整和完善階段都可以獨立執行該操作。首先主節點將關于簇的摘要信息發送給每一個從節點，并要求它們計算點到簇的距離。至此，每個從節點都能計算摘要信息，然后，綜合來自從節點的所有數據，主節點即可獲得簇中心的全局值、各簇的點個數、簇的半徑，并更新簇的信息。

下面，針對所提并行算法CLUBS‖，提出一種基于Ad-hoc消息傳遞的實現。

4 基于Ad-hoc消息傳遞實現CLUBS‖

本節基于Ad-hoc消息傳遞實現了CLUBS‖算法，并基于標準Java套接字的信息交換實現網絡節點間的通信。

該算法實現如下：

步驟1 聚類開始時，主節點向從節點發送LoadDataSetRequest，為加載的數據集指定標識符。各從節點將數據加載到內存中，并通過LoadDataSetResponse答復主節點，該響應消息包含自身加載數據的范圍。當主節點收到所有從節點的答復時，即可計算全局數據集的范圍。

步驟2 主節點向從節點發送InitRootRequest，指定全局域。每個從節點計算本地數據邊緣分布，并通過InitRoo-tResponse答復主節點，該消息包含本地數據的C和S。 主節點即可計算全局數據集的C和S， 以及WCSS，從而實現塊的分割，并將塊初始化劃隊列。當隊列非空時，出隊一個塊，開始計算它的全局邊緣分布。通過將所有節點本地邊緣分布分別相加求和即可獲得全局邊緣分布。

首先，假設全局邊緣分布在N個從節點間傳遞。主節點選擇一半的從節點發送它的邊緣分布給其余從節點，然后迭代累加邊緣分布。當全局邊緣分布被傳遞到N/2個從節點上，主節點再次選擇一半的從節點發送邊緣分布給其余從節點。這個操作被重復，直到整個邊緣分布被存儲在一個節點上。圖2展示了邊緣分布的計算過程，圖2(a)每個從節點wi計算它本地的邊緣分布mi； 圖2(b)從節點w2發送m2到從節點w1， 從節點w4發送m4到從節點w3； 圖2(c)w1和w3分別將收到的邊緣分布和自身的邊緣分布相加，然后，w3發送m3+m4到w1上；圖2(d)w1再次將收到的邊緣分布和自身當前的邊緣分布相加，從而獲取了全局邊緣分布。

圖2 邊緣分布計算過程

為了平衡負載，將分別計算各維度的邊緣分布，統籌各維度，整體考慮各節點的負載。該過程形式化如下，假設 (w1,w2,…,wN) 是一組從節點，對于第i維，從i-1的位置左旋轉初始化從節點。因此，對于第i維，從節點的列表可表示為li=(wi,…,wN,w1,…,wi-1)。

然后，主節點發送ComputeBestSplitRequest給節點wi， 該節點通過掃描第i維的邊緣分布，即可獨立計算出第i維最好的分割。節點wi通過ComputeBestSplitResponse答復主節點，消息中包含分割位置和WCSS下降值。

當主節點獲取各維度ComputeBestSplitResponse后，即可優選全局分割。此時，通過CH指標判斷分割是否有效，如果有效，則主節點發送SplitRequest到每個從節點，含有劃分維度和位置；當從節點收到SplitRequest時，生成兩個新塊，相應的數據也被劃分到兩個塊中，然后，計算邊緣分布，并向主節點發送SplitResponse，該消息含有兩個新塊的C和S， 當主節點收到了SplitResponse，計算兩個塊的WCSS，并將其加入隊列；如果無效，將該塊添加到最終塊列表中。然后，再從隊列中移出一塊，開始計算其全局邊緣分布。如果隊列為空，開始調整階段。

步驟3 此時主節點有一個列表，其含有劃分好的塊和塊的摘要信息。主節點存有每塊的范圍和包含的點數，因此，能夠計算塊的密度，通過密度即可檢測出候選異常塊。對于這些塊，需計算受限密度。為此，一個包含候選受限塊標識、相應受限范圍的RestrictedCountRequest發送給所有從節點，從節點在指定塊中掃描本地數據，并計算每個受限范圍的點數，然后將計算結果通過RestrictedCountResponse發送給主節點。

當主節點收到所有從節點發來的RestrictedCountResponse，即可確定哪些是異常塊。然后，主節點向從節點發送RefinementRequest，它包含簇的中心和半徑。從節點掃描所有樣本點，并將其分配到最近的簇中，否則，標記異常點。同時更新每個簇的C和S，并將結果通過RefinementResponse發送給主節點。

步驟4 當主節點收到所有從節點發來RefinementResponse后，即可計算全局C和S。此消息為凝聚階段奠定基礎，合并形成新簇。

步驟5 然后，主節點向從節點發送PerfectRequest消息，并包含新簇的中心和半徑。完善階段，每個從節點進行再調整處理，類似首次調整階段，通過PerfectResponse向主節點發送更新后的C和S。 當主節點收到來自從節點的所有消息后，聚類完成。

5 實驗與分析

由于CLUBS‖和CLUBS采用了相同的理念，因此，CLUBS‖的精度等同于CLUBS。CLUBS的精度已經驗證比現有的聚類方法優越，因此，這里不展示精度，而是重點驗證并行聚類算法CLUBS‖應用于大數據場景的有效性。

5.1 數據集及參數設置

實驗采用了3個合成數據集，其數據點個數分別為107，108和109，維度在 [2,4,…,12] 范圍內，簇數在 [20,21,…,25] 范圍內。各數據集根據域寬(如2000)、維度和簇數隨機生成符合高斯分布的簇；為了測試算法的魯棒性，數據集隨機添加了噪聲點，數量在總點數的0至0.1倍。實驗運行環境包含16個計算機節點，節點配置為Intel Xeon 6230*2顆2.1 GHz CPU，64 GB內存。

實驗每次僅改變一個參數，測試使用1、2、4、8或16個節點的運行時間。為了便于展示，在每次實驗中，非變化參數默認設置為：總點數為108，維度為16，簇數為32，噪聲比率為0.1，因為該設置被驗證是最嚴格的測試。

5.2 參數敏感性及性能分析

圖3展示了CLUBS‖算法的運行時間。正如預期，運行時間隨著節點個數的增加而顯著減少，并且加速比幾乎與節點個數成線性關系，如運行時間曲線所示。

圖3(a)展示了針對大規模數據，隨著節點個數的增加，加速比幾乎保持恒定。實際上，采用1至2個節點是無法運行109數據集，但是，在108規模上的結果清楚地表明了該算法針對相對較多的點具有很好的擴展性，相反，如果數據點不太多(例如107)，相比本地計算，網絡通信對總開銷的影響更大，因此，節點從8到16，加速比降低。

圖3 CLUBS‖的敏感性測試

圖3(b)表明隨著節點個數的增加，加速比不受數據維度的影響，因為不同維度的曲線斜率幾乎相同。但是，運行時間隨著維數的增加而增加，這也符CLUBS算法，與現存許多其它聚類算法一樣，計算成本隨著維度線性增加。

圖3(c)表明隨著節點個數的增加，簇數對加速比影響不大。具體來說，簇數少的數據集，加速比效果稍好，這是因為簇數多的數據集在分裂階段將花費更多時間，此外，分裂階段也是節點間通信最多的階段。因此，雖然節點的本地工作負載沒有變化，但隨著簇數的增加，交換邊緣分布所需時間增加，因為必須進行更多的分割。此外，運行時間也隨著簇數的增加而增加。

圖3(d)展示了算法的抗噪能力非常優秀，且運行時間和加速比都對不同比例的噪聲不敏感。這是因為加速比主要受節點間的通信影響，而節點間不需要交換數據，僅交換摘要信息(邊緣分布)，因此，加速比不依賴于處理的數據(噪聲或簇)。

5.3 CLUBS‖、K-means‖和Spark PIC的對比分析

為進一步驗證CLUBS‖的性能，實驗將其與經典的K-means 并行版K-means‖[9]和PIC的并行版Spark PIC[11]進行了比較分析。圖4展示了3種算法處理大小不同數據集時的加速比。3個數據集均為16維，32簇，噪聲比為0.1。

圖4 CLUBS‖、K-means‖和Spark PIC的性能對比

如圖4所示，CLUBS‖的擴展性更好，隨著節點個數的增加其運行時間縮短得更快，也即加速比更大，尤其針對大數據集；并且CLUBS‖的表現總是優于K-means‖和Spark PIC。這主要因為CLUBS‖是基于Ad-hoc消息傳遞的算法，它通過使用針對該算法量身定制的協議，可以充分利用分布式計算資源。測試結果符合我們的理論目標。

6 結束語

由于現實世界的需求和并行計算的盛行，傳統經典的單機版聚類算法已無法適應大數據時代的需要。因此，為了使得許多優秀的聚類算法可擴展并利用，本文基于并行計算和CLUBS算法提出了一種面向大數據的并行聚類算法CLUBS‖，并基于Ad-hoc消息傳遞給出了實現。結果表明所提改進算法具有很好的擴展性和魯棒性。同時，它的改進超越經典的并行聚類算法K-means‖和Spark PIC。作為未來的一項工作，我們計劃測試其它的高性能計算策略，以便進一步改善算法的性能。