一種改進的CLIQUE算法及其并行化實現

林鵬 ，陳曦 ，龍鵬飛 ，傅明

（1.長沙理工大學綜合交通運輸大數據智能處理湖南省重點實驗室，湖南長沙410114；2.長沙理工大學計算機與通信工程學院，湖南長沙410114）

CLIQUE（Clustering In QUEst）[1]算法是一種典型的基于網格的聚類算法，具有聚類效率高，對數據輸入順序不敏感，可以隨輸入數據的大小線性的擴展等優點[2]。因此，CLIQUE算法經常被用于處理數據規模較大的數據集，也吸引了眾多研究人員的關注。Sun Shaopeng等提出動態增量的方法改進了網格劃分和剪枝算法[3]。王飛等將網格劃分的思想代入密度峰值聚類，提出一種自適應分辨率的網格劃分方法[4]。黃紅偉等針對多密度數據集提出了一種Rn-近鄰估計網格劃分方法[5]。向柳明等在CLIQUE算法的基礎上增加了采用高維隨機采樣的方法快速查找每個聚類簇中最密集的網格單元[6]。Lin JiaQin在文獻[7]中提出采用高維分解技術和自適應網格的方法改善CLIQUE算法的局限性并提出了新算法在MapReduce[8]上的并行化實現方案。

針對CLIQUE算法采用固定寬度劃分的缺陷，提出邊界修正和滑動網格的方法對劃分后的網格單元進行分析，填補聚類的邊界，尋回被剪枝的稠密網格，提高聚類結果的準確性；然后結合Hadoop[9]和MapReduce實現了改進算法的分布式并行化并進行了相關實驗。

1 CLIQUE算法的改進

1.1 問題描述

傳統的CLIQUE算法在處理問題空間時，根據給定的劃分參數將問題空間每一維等分為若干分，然后使用 MDL（Minimum Description Length）[10]算法對劃分后的網格單元進行剪枝，剔除網格密度低于給定的密度閾值的網格單元。但是當給定的劃分參數不恰當時，會導致算法忽略稠密區域的邊界甚至整個稠密區域，使得聚類結果呈鋸齒狀或丟失聚類，降低聚類結果的準確性。圖1（a）和圖1（b）分別展示了采用固定寬度劃分問題空間的缺陷。

圖1 采用固定寬度劃分的缺陷

針對該缺陷提出邊界修正方法和滑動網格方法，通過對劃分后的網格單元進行分析處理，尋回丟失的稠密網格，從而提升算法的聚類效果。

1.2 邊界修正方法

邊界修正的基本思路是對聚類邊界的稀疏網格單元做進一步劃分，考察其子單元是否滿足一定條件，將滿足條件的子單元合并到相鄰的稠密單元，補全聚類邊界。該方法針對CLIQUE算法采用固定寬度劃分的缺點，對所有位于聚類邊界的稀疏網格單元進行處理，將它們等分為2n個子單元，統計每個子單元中數據點的數量，判斷這些子單元的密度是否大于或等于給定的密度閾值且緊鄰于某一個稠密單元，如果條件成立，則將子單元合并到鄰近的稠密單元，否則不作處理。具體步驟如下：

（1）假設數據集 D={x1，x2，…，xn}的維數為d，網格u為邊界稠密網格，考察其鄰近網格單元是否存在稀疏網格單元u′，若存在則進行步驟（2），否則不作處理；

（2）對稀疏網格單元u′的每一維都做進一步二等劃分，得到 2d個子單元 us={us1，us2，…，us2d，}；

（3）統計落入到子單元 usi|i=1，2，…，2d中的數據點的數量，判斷條件 density（usi|i=1，2，…，2d）是否成立，若條件成立則進行步驟（4），否則不作處理；

（4）合并滿足條件的子單元 usi|i=1，2，…，2d到稠密網格u，重復步驟（1）至（4），完成所有稀疏網格的處理。圖2為在二維空間使用邊界修正進行網格修正。

圖2 采用邊界修正處理低密度網格單元

1.3 滑動網格方法

滑動網格方法是對邊界修正方法的一個補充，改進算法對稠密區域進行邊界修正，僅僅確定了聚類的邊界，而對于沒有相鄰稠密單元的低密度網格單元，其中的數據點會被作為孤立點處理，使得聚類的準確性降低。該方法采用滑動網格的思想，搜索沒有鄰近稠密網格的稀疏網格單元，對可以組成田字格的網格單元做進一步劃分，將新劃分的網格沿特定方向滑動，盡可能尋回稀疏區域的稠密網格。具體方法為計算各網格的矢量坐標以及網格滑動的方向矢量其中c為0田字格中所有網格的公共頂點，gi為網格ui的重心，計算公式如下：

xj|j=1，2，…，N={xj1，xj1，…，xjd}為網格 u 中的數據點，N為網格中數據點的數量。以c0為中心重新劃分網格，將新劃分的網格沿著矢量方向滑動，統計落入新網格中數據點的數量，判斷其密度是否大于或等于給定的密度閾值，若條件成立，則將新網格標記為稠密網格，否則不作處理。滑動網格方法的具體實現步驟如下：

（1）假設數據集的維數為d，SU={u1，u2，…，u2d}為沒有鄰近稠密網格的稀疏網格單元，計算各網格的重心點坐標 gi|i=1，2，…，2d；

（2）計算網格 ui|i=1，2，…，2d的矢量坐標，記為c0-gi，c0為SU={u1，u2，…，u2d}中網格的公共頂點，根據各網格的矢量坐標計算網格滑動的方向矢量

（3）c0以為中心點重新劃分一個與原網格大小相同的網格u′，將網格u′沿著矢量的方向滑動，滑動距離為

（4）統計落入網格u′中數據點的數量，判斷其是否滿足 density（u′）≥ τ，若滿足則將網格 u′標記為稠密網格，考察其余稀疏網格單元。圖3為在二維空間中使用滑動網格方法進行網格修正。

圖3 采用滑動網格處理低密度網格單元

1.4 時間復雜度分析

改進算法與原算法相比，增加了網格修正的過程。在網格修正過程中，算法將掃描一次所有存在數據點的網格，然后稀疏網格中的數據點進行操作，因此該過程的時間復雜度為O（m×w×d），其中m為存在數據點的網格個數，w為每個稀疏網格中包含數據點的個數，在正常情況下，稀疏網格中包含的數據點的數量應遠小于數據集中所有數據點的數量，因此m×w≤n。在CLIQUE算法中，采用自底向上的方法進行聚類，算法的時間復雜度為O（nd+cd），c是一個常數。在本文算法中，增加了網格修正的過程，因此時間復雜度為O（n′d+cd），其中n′=n+m×w，又因為m×w≤n，所以 n′≈n。

1.5 改進算法的聚類效果分析

本文分別測試了CLIQUE算法、文獻[10]中的GP-CLIQUE算法和本文算法對不同大小、不同形狀的二維數據進行聚類的聚類效果。使用二維數據進行實驗可以更直觀的看到聚類結果，也便于比較不同算法的聚類效果。圖4為使用三種算法對同一個數據集進行聚類的效果對比圖。

圖4 算法聚類效果對比圖

從圖4可以看出，對于該數據集，使用CLIQUE算法聚類時，外部圓環部分缺失大量邊界，圓心部分被聚類成兩個不同的類，雖然GPCLIQUE算法的聚類質量有所提升，但效果也不理想，使用改進算法聚類時，成功找回外部圓環的邊界和圓心，聚類效果明顯。因此，使用本文提出的方法改進CLIQUE算法，能夠有效的提高聚類結果的準確率。

圖5為使用3種算法對4個不同形狀不同規模的數據集進行聚類的準確率比較，可以明顯看出改進后算法的聚類準確率保持在90%以上，聚類效果明顯優于GP-CLIQUE算法和CLIQUE算法。這是因為使用本文方法對劃分后的網格進行處理后，尋回了丟失的稠密區域，提高了聚類質量。而GPCLIQUE算法的準確率比CLIQUE算法略有提高，這是因為雖然GP-CLIQUE算法采用高斯隨機采樣的方法提升了聚類性能，但還是采用固定寬度劃分方法，所以算法性能的提升低于本文算法。準確率計算公式為：Accuracy=ncorrect/n。

圖5 聚類準確率比較

2 改進算法的并行化實現

改進的CLIQUE算法并行化的思想：將算法的并行化分為網格劃分和聚類兩個階段，在每個階段啟動1個Job完成網格劃分和聚類操作。圖6為改進算法的并行化實現流程圖。

初始階段。對數據集進行預處理操作，由Job－Client把數據集切片為的形式并發送到JobTracker，Job1啟動時從InputSplit中加載切片信息作為Map函數的輸入。

Job 1網格劃分階段。Job1的主要任務為對問題空間進行網格劃分，然后采用改進算法提升網格劃分質量，最后輸出劃分結果。其中每次計算都需要調用多個Map和Reduce函數，Map函數負責計算數據點所屬網格的編號，將網格的編號和其中包含的數據點作為中間值輸出；Reduce函數負責匯集各個網格中的數據點并計算各網格的網格密度，將網格密度與給定的密度閾值進行比較，若大于密度閾值則將網格標記為稠密網格，否則使用第2章所述方法進行調整，最后輸出最終的網格劃分結果。

Job 2聚類階段。Job2的主要任務為遍歷Job1生成的稠密網格，以深度優先的方法搜索連通的最大單元簇，輸出聚類結果。Map函數以Job1的輸出作為輸入，從中解析出網格編號和各網格包含的數據點，創建一個哈希表Cells用于存儲網格信息并初始化，哈希表的key即為網格編號，value為網格中包含的信息，包括網格中包含的數據點，網格所屬類簇編號和網格的狀態信息；Reduce函數接收Map函數輸出的中間值，隨機選取一個網格，檢索其連通的所有網格并更新哈希表中這些網格的所屬類簇和狀態信息，選取下一個尚未聚類的網格進行聚類，直到所有網格都屬于某個類簇或所有網格的狀態信息均為已讀。

3 實驗與結果分析

3.1 實驗環境和數據

本文實驗環境為Linux操作系統，搭建了一主四從的小型分布式集群，各節點虛擬機處理器配置為Intel Xeon CPU E5-2650 v2，內存 4GB，軟件為Hadoop-2.6.0版本。實驗數據采用從UCI機器學習庫中選取的美國1990年的人口普查數據，該數據集的維度為68，共有2458285條數據，通過人工處理，將數據集抽樣為6個大小不同的數據集，使得每個數據集的數據量以接近2倍大小的速度增長。

3.2 實驗結果與分析

3.2.1 算法時間效率分析

為確保實驗的準確性，每組實驗都重復進行5次，最終的實驗結果取5次實驗的平均時間。由表1的結果可以看出，當數據量較小時，串行算法的處理效率要比算法在MapReduce運行的效率高。這是由于在MapReduce并行框架下運行程序會啟動一個新的Job，新Job的啟動和交互過程中會增加時間消耗。但是隨著數據量的逐漸增加，串行算法的性能會隨之下降，最終拋出內存不足的異常，而并行算法的效率隨著數據量的增加逐漸優于串行算法，因此在處理海量數據時，有必要采用分布式集群模式。

為測試算法的并行效率，分別選擇1，2，3，4個計算節點處理數據，考察在增加節點的情況下，集群運行算法需要的時間。如表1所示，在數據規模較小的情況下，增加計算節點，對算法運行加速效果不明顯。如對于數據集USCensus-1，隨著計算節點的增加，算法的處理時間在1190s上下浮動，這是由于Hadoop集群啟動和調用計算節點需要花費時間；而當數據規模變大時，隨著計算節點數量的增加，算法處理數據所消耗的時間也隨之減少，且數據量越大加速效果越明顯。由此可見，當數據規模較大時，增加處理節點可以顯著提高算法對相同規模的數據集的計算能力，同時體現了改進算法具有良好的擴展性。

表1 算法處理時間

3.2.2 集群加速比性能實驗

實驗1加速比是衡量算法串行處理和并行處理效率的一項重要指標，本文計算了處理表1中不同大小數據集的加速比，實驗使用單個節點的Hadoop集群即一個主節點和一個從節點的情況代替算法串行處理時間的近似值。由圖7的結果可以看出，隨著數據規模的逐漸擴大，算法的加速比性能越來越好。

圖7 加速比分析

實驗2并行算法的可擴展率是評價算法并行計算效率的重要指標之一，可以有效反映集群的利用率情況，隨著計算節點數的增加，若算法的可擴展率保持在1.0附近或者更低，則表示算法對數據集的大小具有很好的適應性。從圖8中可以看出，算法的可擴展率曲線一直保持在1.0以下，且隨著計算節點數的增加可擴展率曲線總體呈下降趨勢，當數據集越大時，可擴展率曲線就越平穩，因此可以得出，數據集規模越大，算法的可擴展率性能就越好。

圖8 可擴展性分析

4 結束語

提出了一種改進的CLIQUE算法，根據給定的劃分參數對數據空間進行劃分，然后提出邊界修正方法和滑動網格方法對劃分后的網格進行處理，提升網格劃分的質量；同時在Hadoop分布式平臺上，利用MapReduce實現了改進后算法的并行化。文中使用人工生成的數據集和UCI數據集對改進算法進行了一系列實驗，測試了算法的聚類精度、時間效率、加速比、數據伸縮率和可擴展性。實驗結果表明，使用本文方法改進CLIQUE聚類算法并在MapReduce上實現并行化，使得聚類結果的準確率提升了17%～26%，同時也表現出良好的數據伸縮率和可擴展性，算法具有處理海量數據的能力。下一步將著力于解決CLIQUE算法依賴密度閾值與劃分參數的輸入的問題。