一種基于自適應網格劃分和決策圖的聚類算法研究

蔡 莉，江 芳，許衛霞，梁 宇

1(復旦大學 計算機科學技術學院，上海 200433) 2(云南大學 軟件學院，昆明 650091)E-mail：lcai@fudan.edu.cn

1 引 言

作為數據挖掘中的一類重要算法，聚類廣泛應用于數據分析、圖像處理、市場研究、用戶劃分、Web文檔分類等.目前，聚類算法大致可以劃分為四種類型.第一種是以K-means、K-medoids等算法為代表的基于劃分的聚類算法[1，2].第二種是以CURE和BIRCH[3]等算法為代表的基于層次的聚類算法，它們通過計算不同類別數據點間的相似度來創建一棵有層次的嵌套聚類樹.第三種則是以DBSCAN、OPTICS等算法為代表的基于密度的聚類算法[4，5].這類算法核心思想是將簇定義為密度相連的點的最大集合，能夠把在一定范圍內，具有足夠高密度的區域劃分為簇.第四種是以Clique算法[6]為代表的基于網格的聚類算法.這類算法對數據輸入順序不敏感，無需假設任何規范的數據分布，當數據維數增加時具有良好的可伸縮性[7，8].

每一類算法都有各自的適用場合和優缺點.基于劃分的聚類算法實現簡單，應用非常廣泛，但是，其最大缺陷是需要提前確定簇的數量.基于層次的聚類算法的缺陷在于當數據集較大時，樹形圖的規模會變得非常巨大，效率較為低下.基于密度的聚類算法不僅可以發現任意形狀的類，而且可以對噪聲數據和孤立數據進行過濾.但是，此類算法的最大問題是如何選擇有效的參數.像大多數基于密度的聚類算法一樣，基于網格的聚類非常依賴于密度閾值的選擇.閾值太高會導致簇丟失，閾值太低又會使本應該分開的簇被合并在一起.2014年Alex Rodriguez和Alessandro Laio在Science上發表了一篇基于密度峰值的聚類算法(Clustering by fast search and find of density peaks，簡稱為DPC算法)[9]，其思想是尋找被低密度區域分離的高密度區域.DPC算法通過決策圖尋找具有較高的密度ρ且與更高密度點具有較大的距離δ的聚類中心.計算局部密度ρ需要用到截斷距離(Cut-off distance，簡稱為dC).參數dC是指一個距離值，它從一個有序距離序列中選出.例如，對數據集中任意兩點計算距離值并得到一個距離矩陣，然后升序排序.由用戶自己設置一個參數百分比，dC為該排列的參數百分比.針對距離閾值人工選取問題，Wang等人[10]提出了一種利用原始數據集中數據場的潛在熵自動提取閾值最優值的新方法，其對比實驗結果表明，與經驗閾值相比，具有數據場閾值的算法可以獲得更好的聚類結果，但該方法在大數據集上尚未驗證.在處理海量數據集時，DPC算法的計算工作量非常龐大.Xie等人[11]提出了FKNN-DPC(簡稱為FDPC)算法.對于任何獨立于dC的數據集，計算點i相對于其K近鄰的局部密度ρi，并使用兩種新的點分配策略將剩余的點分配給最可能的簇.FDPC算法比DPC算法的性能要好，但是，算法中的K值需要預先確定，這對于無監督的聚類來說比較困難.何熊熊等人提出了一種基于密度和網格的簇心可確定聚類算法，簡稱為DGCCD算法[12].DGCCD算法采用網格化數據集來減少聚類過程中的計算復雜度，其劃分網格的依據是：網格對象集中網格對象數量NG在大于或等于數據集中數據量N的1/6的情況下最好.

使用網格劃分來減少聚類過程的計算量是一種較好的方法[13]，但是，傳統基于網格的聚類算法是采用固定網格的方法區分稠密區域和稀疏區域，一些稀疏區域會被刪減掉，導致原本屬于某個聚類簇的數據點被刪除，或者被分割到了相鄰的區間，破壞了聚類簇的完整性.為了解決相關算法存在的問題，本文提出了一種基于自適應網格劃分的聚類算法，稱之為AGPCA(Adaptive Grid Partition Clustering Algorithm)算法.該算法結合網格劃分和距離判斷的優點，適用于大規模數據的聚類計算.

2 AGPCA聚類算法原理

2.1 相對熵

1948年Shannon將熵的概念引入信息論，它是用來度量信息價值高低的一種方法[14].熵可以表示為：

(1)

其中，x為隨機變量，S(x)為x可以取值的集合，p(x)為x的概率函數.

相對熵[15]是從熵衍生出來的概念，可以反映數據點分布趨近于均勻分布的程度.當數據分布越趨于均勻，相對熵值越大；當數據分布越趨于集中，相對熵值越小.本文利用相對熵來區分子空間中的密集數據區域和稀疏數據區域，做到自適應網格劃分[16].

定義1.第i維上直方圖中的單個直方格(bin)的相對熵可以用如下公式表示：

(2)

其中，xij為第i維上第j個直方圖格，d(xij)為直方圖格里的數據數量占整個數據空間數據集的比例，Ti為第i維上的直方圖格的數量.

定義2.第i維上直方圖的相對熵可以用如下公式表示：

(3)

其中，Xi為第i維上直方圖格的集合.

本文利用相對熵自適應劃分網格的過程如下：

Step1.根據輸入的網格步長ε參數等長劃分Di，構造第i維的直方圖；

Step2.計算第i維的每一個直方圖格Hb的相對熵；

Step3.計算第i維直方圖的相對熵以及相對熵閾值θh；

Step4.順序掃描第i維的所有Hb，若Hb的相對熵≥θh，則繼續掃描后一個Hb，直至遇到Hb<θh，則將之前掃描的Hb進行合并，并繼續掃描至結束；

Step5.重復Step 1-Step 4，直到多維網格掃描完成.

2.2 決策圖與簇心網格

為了加快查找速度，本文在這一處理階段使用了Kd-Tree[17]來創建索引.Kd-Tree是K-dimension Tree的縮寫，是一種平衡二叉樹的具體實現.它可以根據數據點的維度，在k維數據空間(如三維(x，y，z))中劃分出對應的索引結構.Kd-Tree主要應用于多維空間關鍵數據的搜索，如最近鄰搜索等[18].確定簇心網格的過程為：

Step1.根據相對熵自適應地將數據集空間中的每一維k劃分為互不重疊的n個網格；

Step2.掃描所有網格，刪除數據點為0的網格，形成新的非空網格并記為Np；

Step3.確定網格的對象集Np和網格對象數NG；

Step4.確定每一個網格對象的密度參數ρi和距離值δi.

參數ρi和δi的定義分別如下：

定義3.每一個網格celli中的密度為ρi.ρi=Count(Celli).

定義4.以網格對象celli到更高密度網格對象cellj的最近距離作為網格對象的距離值，記為δi，公式如下：

(4)

其中，dij為網格對象celli中心位置到網格對象cellj中心位置之間的歐氏距離.

假設網格集合中密度最高的網格對象為ex，其距離值δex=max(δi)，j為除ex以外的所有網格對象.位于簇心位置的網格對象會同時具有較高的密度ρ和較大距離值δ，如圖1所示.可以看出：編號為5和9的網格對象具有較高的密度ρ和較大的距離δ，將它們作為簇心網格對象.

圖1 決策圖(密度與距離的分布圖)Fig.1 Decision diagrams(den-sity and distance distribution)

2.3 聚類過程

在簇心網格對象確定之后，采用基于密度的劃分方式來完成聚類，具體步驟為：

Step1.給每個簇心網格celli分配不同類別Ci；

Step2.遍歷簇心網格的相鄰網格，若相鄰網格密度值大于2，則給相鄰網格分配簇心類標；

Step3.將剩下未分配的網格進行鄰接網格遍歷，若鄰接網格有類標，則將該類標分配給該網格；

Step4.將剩下仍未分配的網格，利用Kd-Tree索引，找到離它最近的K個網格(K為數據集大小的3‰)，將最近有類標的點且距離小于K近鄰點的平均距離的點的類標賦予該網格，反之，該網格標記為噪聲點網格，類標賦值0.

Step5.重復Step 4，直到所有網格已經分配類標，則整個聚類工作結束.

3 AGPCA算法描述

本小節介紹AGPCA算法的實現過程，為了更好地描述本算法，對算法中涉及到的變量進行說明，如表1所示.

表1 AGPCA算法中使用的變量Table 1 Notations for AGPCA algorithm

AGPCA算法的偽代碼描述如下：

Input：有k維的數據集D，ε

Output：聚類結果C

/* Step 1：劃分網格*/

1.for eachi，i=(1，…，k)

2.Hbi= SplitGrid(Di，ε) /*根據輸入的參數等長劃分Di，構造第i維的直方圖*/

3.hr(xij) = Compute_entropy(xi) /* 計算第i維的每一個直方圖格的相對熵hr(xij) */

4.θh=CalThreshold()/*計算第i維相對熵閾值θh*/

5. MergeGrid()/*將熵值大于閾值的網格進行合并 */

6.end for

7.GridQueue=Get_grid()/*得到多維自適應劃分網格*/

/*Step 2：確定簇心網格*/

8.for eachCelliinGridQueue

9.Np=DelEmptyGrid[Celli] /*刪除空網格Celli*/

10.end for

11.KD=CreateKd(GridQueue) /*非空網格建立kd樹*/

12.gc=Determine_center(Np) /* 確定簇心網格gc，并遍歷簇心網格的鄰接網格*/

13.addgcinC

/* Step 3：確定聚類結果*/

14.Nearest_neighbor(gc)/*遍歷簇心網格的鄰接網格*/

15.NearestCluster(Np) /*遍歷未分配網格的鄰接網格*/

16.KNearestGrid(Np) /*遍歷未分配網格的K近鄰網格，返回滿足條件的K近鄰網格的類標，反之返回0*/

17.returnC

4 實驗及分析

本小節通過實驗來驗證AGPCA算法的有效性.

4.1 實驗數據集

實驗數據集包括5個基準數據集和1個真實數據集.數據集Aggregation和Compound具有明顯的聚類簇大小不均衡的特征；數據集R15具有聚類簇數量繁多并且高度重合的特征.數據集Flame和Spiral是經典的流型數據集.出租車GPS數據集則是真實、無監督的數據集.表2表示相關數據集的具體特征，圖2表示6個數據集的初始效果.

表2 實驗數據集Table 2 Experimental data sets

圖2 數據集分布圖Fig.2 Distribution of six data sets

4.2 實驗結果與評估

4.2.1 標準數據集對比實驗

本小節先使用AGPCA算法對5個基準數據集進行聚類，并將AGPCA算法與DBSCAN算法、DPC算法、DGCCD和FKNN-DPC等四種算法進行對比.聚類結果的有效性可以通過一些評價方法進行測量，這些評價方法可以分為：外部評價、內部評價和相對評價三種類型[19].常用的外部評價法指標有F-measure、Rand指數、Purity和NMI(Normalized Mutual Information，標準互信息)等.內部評價法對應的評價指標有CP(Compactness，緊密性)，SP(Separation，間隔性)[20].相對評價法的評價指標包括DBI(Davies-Bouldin Index，戴維森堡丁指數)和DVI(Dunn Validity Index，鄧恩指數)等[21].

由于5個基準數據集的分類已知，本文采用F-measure、Rand指數和Purity三種指標來評價五種算法的聚類結果.

圖3 五種算法在標準數據集上的聚類評估結果Fig.3 Clustering assessment results of five algorithms on standard data sets

圖3(a)-圖3(c)顯示了5種算法在不同數據集上的RI、Purity、F-measure值對比結果.如圖3(a)-圖3(c)所示，在Aggregation、R15和Spiral這3個數據集上，FKNN-DPC算法的結果優于其他算法.DPC算法的聚類效果易受截斷距離的影響，因此在不同數據集上的聚類評估指標會有一定差異.AGPCA算法在5個數據集上的平均RI、平均Purity、平均F-measure值都為最優且達到96%以上.

4.2.2 真實數據集對比實驗

本文也采用真實數據集對五種算法進行實驗對比，表3和表4分別統計了兩個不同日期(工作日和休息日)在四個不同時段下的聚類結果.

表3 GPS數據聚類結果統計Table 3 Number of clusters for GPS trajectory data on Monday and Sunday

本文以周一的09：00-11：00時段為例，對5種不同算法的聚類結果進行分析，其中圖3(a)-圖3(e)分別展示5種不同算法在該時段的聚類結果.圖2(f)顯示了GPS的原始數據分布圖，可知所有軌跡點分布緊密，無法直接識別出聚類的個數.圖4(a)-圖4(b)分別顯示了AGPCA、DBSCAN的聚類結果，可以發現這兩種算法的聚類簇特征相似，但在聚類簇分布位置不盡相同.AGPCA算法的聚類結果是以相對熵劃分網格，且先以聚類中心的鄰接網格進行聚類，分配剩余點的策略是以K近鄰網格進行聚類，所以聚類簇的分布較廣.DB-SCAN是以給定的半徑及最小點參數進行聚類.圖4(c)顯示的是DPC算法的聚類結果，可知該聚類結果從左至右呈長條矩形分布且聚類簇點數多，簇與簇之間的間距小.產生這種結果的原因在于DPC算法是人工選取截斷距離參數，取不到最優參數；同理在做噪聲點刪除時，也涉及到人工選取參數進行處理，導致每一個聚類簇點數多.圖4(d)顯示的是DGCCD算法的聚類結果，由圖可知，該聚類結果呈網格狀分布，且連接緊密.產生這種結果的原因在于DGCCD算法通過迭代網格數至滿足某個條件最終確定網格總數.DGCCD算法對聚類簇的區分度不好，會將原本不屬于同一個聚類簇的多個聚類結果合并在一起，無法得到準確的結果.圖4(e)顯示的是FDPC算法的聚類結果，該聚類結果中存在一個特別大的聚類簇和若干個分散的小聚類簇.大聚類簇已經涵蓋了二環區域內所有GPS點，結果完全錯誤.產生這一錯誤的原因是該算法在算局部密度時，是根據某一點到其K近鄰點的距離計算所得，導致將多個相鄰近的聚類簇合并為一個超大聚類簇.

圖4 5種算法在真實數據集上的聚類對比結果Fig.4 Comparison of clustering results for five algorithms on GPS data sets

對于非監督數據，本文使用DBI指數來評估聚類結果，表4顯示了7號和13號下各數據集聚類結果的戴維森堡丁指數.從表4可以看出，在7號各時段下AGPCA獲得最小的DB指數，DPC算法、DGCCD算法的DB指數較高，原因在于在大數據集上人為選取參數較不準確，剔除噪聲點較困難導致其聚類結果間距太小，且包含點數眾多.在13號各時段下DGCCD算法的平均DB指數最高，原因在于處理13：00-15：00/15：00-17：00時段下的文件時，分別聚出了40、31個類，遠高于其他算法的聚類結果，且每個類間距離緊密.AGPCA算法在獲得數量更多的聚類簇的同時又能得到最小DB指數，具有很好的聚類效果.

4.2.3 運行時間對比結果

表4 周一和周日聚類結果的DBI指數Table 4 DBI indices of clustering results on monday and sunday

最后，本文對比五種不同算法在不同數據量下的執行時間，如圖5和圖6所示.9月7號在7：00-9：00、9：00-11：00、13：00-15：00和15：00-17：00四個時段的數據量分別為10561、17728、17219和16760.9月13號在對應時段的數據量分別為11077、15501、18152和18113.各時段下數據量均超過1w條以上，其中19：00-21：00時段下的數據量最大，接近2萬條.

圖5 周一各時段數據集運行時間對比結果Fig.5 ComparisonofRunningtimeonmonday圖6 周日各時段數據集運行時間對比結果Fig.6 ComparisonofRunningtimeonsunday

從圖5和圖6可以看出：AGPCA與DBSCAN的運行時間比較接近，但AGPCA的運行時間最短.DBSCAN算法耗時較短，原因在于其運行參數是預先給定的.一旦待處理數據集的分布和規模發生改變，DBSCAN算法的兩個運行參數Eps和Minpts要重新選取，這一過程非常耗費時間.DGCCD算法耗費時間長，原因在于選定網格個數時，需計算當前非空網格數是否滿足條件，若不滿足，則增加網格個數迭代計算，處理大數據集則運行時間長.DPC算法耗時最長的原因是該算法首先需要計算海量數據點之間的兩兩距離并形成距離矩陣，然后從中選取2%作為截斷距離，該過程的時間復雜度為O(n2).FDPC算法的運行時間稍低于DPC算法，其耗時原因是需要計算每個未分配點的K近鄰相似距離點以確定點的類標，并依次遍歷下去.AGPCA算法在劃分網格時利用相對熵將一些網格進行合并，從而減少了網格數；而且，在做網格聚類時利用KD樹以及鄰接網格思想分配網格，從而提高了查詢效率和運算速度.

5 結 論

本文提出了一種基于自適應網格劃分和決策圖的聚類算法.該算法首先對數據集進行自適應網格劃分，得到稠密和稀疏的網格，將無效網格進行刪減；在聚類過程中，使用Kd-tree進行索引查找，提高了查詢效率.該算法在處理大數據集時，可以很好地減少計算量以及降低運行時長.通過對DBSCAN算法、DPC算法、DGCCD算法、FDPC算法以及AGPCA算法在標準數據集以及昆明市出租車GPS軌跡數據進行實驗對比，從結果分析可知AGPCA算法能夠挖掘出準確的聚類結果，并且在處理大數據集時也具有較好的時間性能.相對熵閾值的選取在一定程度上影響著網格劃分結果，目前還是通過多次實驗獲得最好的結果；此外，在處理不平衡數據集時，簇心選取時會丟失小簇聚類.因此，這兩個問題將是下一步工作的研究重點.