HCLOPE：一種處理分類數據的優化層次聚類算法

李曄鋒　樂嘉錦　王　梅

(東華大學計算機科學與技術學院　上海 201620)

?

HCLOPE：一種處理分類數據的優化層次聚類算法

李曄鋒樂嘉錦王梅

(東華大學計算機科學與技術學院上海 201620)

摘要隨著分類數據規模的快速增長，關于分類數據聚類方法的研究日趨重要。在現有的算法中，CLOPE在運行速度、內存開銷和聚類結果方面要優于同類算法，但是它的聚類質量并沒有達到最優，而且受到輸入數據順序的影響，顯現出不穩定性。基于此原因，提出一種處理分類數據的層次聚類算法HCLOPE，采用自底向上的凝聚法生成穩定的聚類結果。此外，還定義了聚簇間全局最大的收益差值作為聚類的合并準則，并引入無向圖的結構優化聚類合并迭代過程。在蘑菇數據集上運行的實驗結果顯示HCLOPE的聚類質量更優。

關鍵詞HCLOPE分類數據層次聚類穩定性無向圖

0引言

聚類是一種重要的數據挖掘技術，它把數據組織成聚簇，使得各聚簇內部的相似度最大，同時聚簇間的相似度最小。大多數聚類算法處理數值型數據，以兩點之間的距離作為生成聚簇的基準。但是，在現實生活中包含大量的含有分類屬性的事務，對這些數據進行聚類的過程比數值型數據更復雜。隨著分類數據規模的快速增長，關于分類數據聚類方法的研究顯得日趨重要。

在所有關于分類數據聚類算法的研究成果中[1-6]， CLOPE的聚類速度相對最快，聚類效果相對最好，它為聚簇的直方圖定義了一種高寬比的計算方法來衡量聚簇內部各事務的相似度[6]。此外，CLOPE算法還定義了一個排斥因子r作為輸入參數來控制聚簇的緊湊性，因此最終輸出的聚簇數目由該參數和輸入數據的分布特征共同決定，不需要用戶事先指定(例如k-means算法)。科研工作者還對CLOPE進行了各種改進，例如Ong等人提出了SCLOPE[7]和σ-CLOPE算法[8]對分類類型的數據流進行聚類；Li等人提出了一種模糊CLOPE算法[9]用于實現參數的自動優選。但是，這些研究均忽視了CLOPE算法本身具有的缺陷：聚類的結果受到輸入數據集中事務的順序影響，具有嚴重的不穩定性，即給定同一個數據集和相同的排斥因子，讀取事務的先后順序不同將可能產生不同的聚類結果。

通過深入分析CLOPE算法的聚類過程，可以發現它在聚簇調整過程中每次只移動一個事務，因此無法找到一組事務的最佳組合來構成“最優的”聚簇集合，并獲得穩定有效的聚類結果。為了解決這個問題，本文提出了一種用于處理分類數據的層次聚類算法HCLOPE。該算法在初始階段構建一個無向圖，數據集中的每個事務被當作單獨的聚簇存入到無向圖的頂點集中，然后全局最大收益差值的聚簇(頂點)兩兩相連，各連通子圖中的頂點一次性合并，在生成新的無向圖后第一次迭代完成。經過多次迭代，直到沒有新的邊生成時算法終止。該算法能夠獲得一個穩定的聚類結果，同時它產生的收益值更優。在蘑菇數據集上運行的實驗結果顯示，HCLOPE算法在排斥因子位于文獻[6]所述的最佳范圍(2.8≤r≤4.0)時，產生的收益值比CLOPE算法平均提高了34.2%。

1CLOPE算法

1.1相關定義

假設D={t1,t2,…,tn}表示包含n個事務的數據庫，I={i1,i2,…，im}表示D中的所有分類屬性，據此有如下定義：

定義1事務(Transaction)D中的一個事務t可以表示為二元組，其中key是事務的標題，A={ia,ib,…}?I是事務中分類屬性的集合。

定義3直方圖(Histogram)若occ(i,c)表示分類屬性i在聚簇c中的出現次數，則c的直方圖可以表示為：

(1)

a) 大小，即聚簇c中分類屬性的總數，表示如下：

(2)

b) 寬度，即聚簇c中分類屬性不同值的總數，表示如下：

W(c)=|{occ(i,c)>0|i∈I}|

(3)

c) 高度，即大小和寬度的比值，表示如下：

H(c)=S(c)/W(c)

(4)

d) 聚簇c中事務的數目，表示為|c|。

定義4聚類(Clustering)聚類C表示聚簇的集合，即C={c1,c2,…，cp}。

定義5聚類的收益值(Profit of Clustering)假設聚類C中包含p個聚簇，則C的收益值表示如下：

(5)

根據上述定義，CLOPE算法的目標可以概括為：給定數據庫D和排斥因子r，找出一組聚簇集合，使得它生成的聚類具有最大的收益值。

此外，式(5)的分母部分是聚類C中事務的總數，在計算過程中是一個常數，因此實際上影響收益值大小的是其中的分子部分。

1.2缺陷與不足

為了實現上節的目標，CLOPE算法在每一次迭代過程中會依次遍歷每個事務，并判斷它是否可以從當前聚簇中移動到另一個更合適的聚簇。即對于聚類C中的p個聚簇，如果把事務t移動到聚簇ck后形成聚簇ck′，k∈p，使得S(ck′)×|ck′|/W(ck′) -S(ck)×|ck|/W(ck)的值為最大，則ck為算法中的最佳聚簇。事實上，CLOPE算法并沒有生成最優聚類而使其收益值最大。本文通過如下的例子闡述該問題。

假設數據庫D中有如下事務：{ab, bc, ac, abd, bcd, acd}，并且固定r=2，使用CLOPE算法產生的聚類結果為{{ab, abd}, {bc, bcd}, {ac,acd}}，根據式(5)可得該聚類收益值的分子部分為(5×2÷32)×3≈3.33。但是，如果把事務的輸入順序改成{ab, bc, bcd, acd, ac, abd}，CLOPE把所有的事務放到一個聚簇中作為聚類結果，則收益值的分子部分為15×6÷42=5.625。

顯然，事務的輸入順序不同，CLOPE算法產生的聚類結果就會不同，其原因在于CLOPE算法每次只移動一條事務。對于第一種順序產生的聚類結果，如果把聚簇{ab, abd}與{bc, bcd}或{ac, acd}進行合并，就能使收益值增大成10×4÷42+5×2÷32≈3.61。因此，如果算法能夠支持聚簇的合并操作，不但能夠消除事務的輸入順序對聚類結果產生的影響，而且能獲得更大的收益值。

2優化的層次聚類算法HCLOPE

本節提出了優化的層次聚類算法HCLOPE，旨在消除事務的輸入順序對聚類結果產生的影響。首先，為了支持聚簇合并操作，提出相關定義對現有的CLOPE算法進行了擴展；其次，為了支持多個聚簇能夠同時進行合并，引入了無向圖結構，使位于同一連通子圖內的所有聚簇能夠批量合并。

2.1擴展CLOPE算法

由于CLOPE算法每次只能移動一條事務，本節對其中聚簇和收益值的定義進行了擴展，使它們能夠支持更多的操作。

定義7聚簇的收益值(Profit of Cluster)聚簇c的收益值表示如下：

(6)

因此聚類的收益值為聚簇收益值之和除以事務的總數，即：

(7)

定義8差值(Delta)假設有兩個聚簇ca和cb，它們合并后的結果為ca/b，則ca和cb合并產生的差值為合并前后收益值之差，記為Delta(ca,cb)，簡化表示為Da,b，即：

Da,b=Profit(ca/b)-(Profit(ca)+Profit(cb))

(8)

顯然兩個聚簇的差值具有對稱性，即Da,b=Db,a。另外，定義Da,a= 0表示相同的聚簇不能進行合并。為了保證最終聚類結果的收益值最大，每次聚簇合并操作必須產生最大的差值。假設當前聚類中共有p個聚簇，則聚簇ca的最大差值定義如下：

M(ca)=max({Da,k|k∈[1,…,p]})

(9)

GM=max{M(ck)|k∈[1,…,p]}

(10)

2.2優化層次聚類過程

在上一節中，本文定義了聚簇的合并準則，即只要聚簇之間的差值等于GM便可執行合并操作。但是，傳統的自底向上層次聚類算法每次只能合并兩個聚簇，并不支持一次性合并多個聚簇[10]。為此，本節引入了一種無向圖的結構來表征聚簇的合并狀態。

定義9聚簇圖(Cluster Graph)聚簇圖可以表示成無向圖G=(V,E)，其中V表示頂點集合，每個頂點代表一個聚簇；E表示邊的集合，差值等于GM的兩個頂點(聚簇)構成邊。

圖1　聚簇的合并過程

仍然以輸入數據{ab, bc, ac, abd, bcd, acd}為例，圖1顯示了聚簇的合并過程。首先，每個事務單獨作為一個聚簇加入到G的頂點集V中，然后分別計算各頂點之間的差值，并把差值等于GM的頂點連接成邊加入到E中；接著把G中所有的連通子圖各自合并成一個頂點，生成新的無向圖G′。反復迭代直到無向圖中不包含邊時算法終止。HCLOPE的偽代碼如下所示：

/*第一階段：初始化*/

1:while not end of the database file

2:read the next transaction t;

3:ci←t;V←ci;M(ci)=0;

/*第二階段：迭代*/

4:do

5:moved=false; GM=0;

6:for i=0 to V.size

7:for j=i+1 to V.size

8:if(Di,j<=0) continue;

9:if(Di,j>M(ci))

11:else if(Di,j==M(ci))

13:if(Di,j>M(cj))

15:else if(Di,j==M(ci))

17:if(Di,j>GM)

18:clear(E);E.add(i,j);GM=Di,j;

19:else if(Di,j==GM)

20:E.add(i,j);

21:if (E.size>0)

22:合并G中的所有連通子圖;

23:merged=true;

24:clear(E); clear(M);

25:while(merged)

3實驗分析

本節設計了四組實驗，從不同角度分別比較HCLOPE的各項指標，包括運行時間、生成的聚類收益值、算法穩定性和生成聚類的質量。實驗數據為加州大學機器學習庫中的蘑菇數據集(http://www.ics.uci.edu/～mlearn/MLRepository.html)，它包含8124個事務，4208個可食用蘑菇和有毒蘑菇，其中每個事務有22個分類屬性，并且分類屬性的總數為116。

首先比較r取不同值時CLOPE和HCLOPE的運行時間，實驗結果如圖2所示。顯然CLOPE算法要遠遠優于HCLOPE，其原因是CLOPE在初始化階段產生的聚簇數目非常少，即N<

其次比較r取不同值時CLOPE和HCLOPE產生的聚類收益值，實驗結果如表1所示。根據式(5)的計算結果，收益值隨著r值的增大逐漸減小，但是毫無疑問HCLOPE的收益值要優于CLOPE，由此證明HCLOPE能夠產生更好的聚類結果。

接著把數據集中的事務打散，固定r=2.0并隨機產生5組不同的輸入順序。圖3的實驗結果顯示，對于同一數據集，CLOPE算法產生的收益值受輸入順序影響，而HCLOPE能夠保持穩定的聚類結果。

圖2　CLOPE和HCLOPE花費的時間比較

rCLOPEHCLOPErCLOPEHCLOPE1.0745.64731791.99662.62.26972.52421.2343.3131731.03812.80.96361.24291.4149.1631300.64433.00.47840.61411.668.7164123.71433.20.23750.30341.841.950150.95823.40.10650.14992.020.614021.70693.60.05290.07412.29.438610.42273.80.02620.03662.45.10015.12794.00.01410.0181

圖3　CLOPE與HCLOPE的穩定性比較

最后比較CLOPE和HCLOPE產生的聚類中純度(purity)和聚簇數目(cluster no.)的值。聚類的純度計算方法為取每個聚簇中可食用蘑菇和有毒蘑菇的最大值相加，所得的值越大聚類質量越好。圖4 的實驗結果顯示，當r≥2.8時，CLOPE和HCLOPE的純度均到達事務的總數8124，并且聚簇的數目穩定保持為23。在其他情況下，HCLOPE要略微優于CLOPE。

圖4　CLOPE與HCLOPE的聚類質量比較

4結語

本文提出了一種處理分類數據的優化層次聚類算法HCLOPE。它不但擴展了CLOPE算法以支持聚簇合并操作，而且引入了無向圖的結構以實現多個聚簇的同時合并。實驗結果顯示，HCLOPE能夠產生穩定的聚類結果，并且聚類的收益值顯著高于CLOPE，從而獲得更好的聚類質量。但是HCLOPE算法的運行速度不如CLOPE。未來的工作將與并行技術結合，如使用Hadoop框架或者多核技術，以期提高算法的運行速度。

參考文獻

[1] He Z Y, Xu X F, Deng S C. A cluster ensemble method for clustering categorical data [J]. Information Fusion, 2005,6(2):143-151.

[2] Gibson D, Kleiberg J, Raghavan P. Clustering categorical data: an approach based on dynamic systems[C]//Proc. of VLDB’98, 1998:311-323.

[3] Guha S, Rastogi R, Shim K. ROCK: a robust clustering algorithm for categorical attributes[C]//Proc. of ICDE’99, 1999:512-521.

[4] Wang K, Xu C, Liu B. Clustering transactions using large items[C]//Proc. of CIKM’99, 1999:483-490.

[5] He Z, Xu X, Deng S. Squeezer: an efficient algorithm for clustering categorical data[J].Journal of Computer Science and Technology, 2002,17(5):611-624.

[6] Yang Y, Guan S, You J. CLOPE: a fast and effective clustering algorithm for transactional data[C]//Proc. of KDD’02, 2002:682-687.

[7] Ong K L, Li W Y, Ng W K. SCLOPE: An algorithm for clustering data streams of categorical attributes[M].LCNS 3181: Knowledge-Based Intelligent Information and Engineering Systems, Berlin, Heidelberg: Springer, 2004:209-218.

[8] Yap P H, Ong K L. σ-SCLOPE: clustering categorical streams using attribute selection[M].LCNS 3682: Knowledge-Based Intelligent Information and Engineering Systems, Berlin Heidelberg: Springer, 2005:929-935.

[9] 李潔，高新波，焦李成. 模糊CLOPE算法及其參數優選[J]. 控制與決策, 2004(19):1250-1254.

[10] Hastie T, Tibshirani R, Friedman J. The elements of statistical learning: Data mining, inference, and prediction[M].2nd ed. Springer Verlag, 2009.

收稿日期：2015-03-15。李曄鋒，博士生，主研領域：分布式數據庫和數據挖掘。樂嘉錦，教授。王梅，副教授。

中圖分類號TP301.6

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.014

HCLOPE: AN OPTIMISED HIERARCHICAL CLUSTERING ALGORITHM FOR CATEGORICAL DATA PROCESSING

Li YefengLe JiajinWang Mei

(SchoolofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620,China)

AbstractWith the rapid growth of categorical data volume, the research on clustering methods for categorical data becomes increasingly important. Among current categorical clustering algorithms, CLOPE has better performance than similar algorithms on processing rate, memory consumption and clustering result. However, its clustering quality has not reached the optimal yet, and is affected by the sequence of input data that leads to instability. For this reason, we propose a hierarchical clustering algorithm for categorical data processing HCLOPE, it generates stable clustering result with a bottom-to-up merging process. Moreover, we also define the global maximum delta value of profit between clusters as the merging criteria of clustering, and introduce an undirected graph structure to optimise the merging iteration process of clustering. Results of experiment conducted on mushroom benchmark dataset demonstrate that the clustering quality of HCLOPE is much higher.

KeywordsHCLOPECategorical dataHierarchical clusteringStabilityUndirected graph