李曄鋒　樂嘉錦　王　梅

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

?

HCLOPE：一種處理分類數(shù)據(jù)的優(yōu)化層次聚類算法

李曄鋒樂嘉錦王梅

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

摘要隨著分類數(shù)據(jù)規(guī)模的快速增長，關于分類數(shù)據(jù)聚類方法的研究日趨重要。在現(xiàn)有的算法中，CLOPE在運行速度、內(nèi)存開銷和聚類結(jié)果方面要優(yōu)于同類算法，但是它的聚類質(zhì)量并沒有達到最優(yōu)，而且受到輸入數(shù)據(jù)順序的影響，顯現(xiàn)出不穩(wěn)定性?；诖嗽?，提出一種處理分類數(shù)據(jù)的層次聚類算法HCLOPE，采用自底向上的凝聚法生成穩(wěn)定的聚類結(jié)果。此外，還定義了聚簇間全局最大的收益差值作為聚類的合并準則，并引入無向圖的結(jié)構(gòu)優(yōu)化聚類合并迭代過程。在蘑菇數(shù)據(jù)集上運行的實驗結(jié)果顯示HCLOPE的聚類質(zhì)量更優(yōu)。

關鍵詞HCLOPE分類數(shù)據(jù)層次聚類穩(wěn)定性無向圖

0引言

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

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

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

1CLOPE算法

1.1相關定義

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

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

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

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

(5)

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

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

1.2缺陷與不足

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

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

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

2優(yōu)化的層次聚類算法HCLOPE

本節(jié)提出了優(yōu)化的層次聚類算法HCLOPE，旨在消除事務的輸入順序?qū)垲惤Y(jié)果產(chǎn)生的影響。首先，為了支持聚簇合并操作，提出相關定義對現(xiàn)有的CLOPE算法進行了擴展；其次，為了支持多個聚簇能夠同時進行合并，引入了無向圖結(jié)構(gòu)，使位于同一連通子圖內(nèi)的所有聚簇能夠批量合并。

2.1擴展CLOPE算法

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

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

(6)

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

(7)

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

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

(8)

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

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

(9)

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

(10)

2.2優(yōu)化層次聚類過程

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

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

圖1　聚簇的合并過程

仍然以輸入數(shù)據(jù){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實驗分析

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

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

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

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

圖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的穩(wěn)定性比較

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

圖4　CLOPE與HCLOPE的聚類質(zhì)量比較

4結(jié)語

本文提出了一種處理分類數(shù)據(jù)的優(yōu)化層次聚類算法HCLOPE。它不但擴展了CLOPE算法以支持聚簇合并操作，而且引入了無向圖的結(jié)構(gòu)以實現(xiàn)多個聚簇的同時合并。實驗結(jié)果顯示，HCLOPE能夠產(chǎn)生穩(wěn)定的聚類結(jié)果，并且聚類的收益值顯著高于CLOPE，從而獲得更好的聚類質(zhì)量。但是HCLOPE算法的運行速度不如CLOPE。未來的工作將與并行技術結(jié)合，如使用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算法及其參數(shù)優(yōu)選[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。李曄鋒，博士生，主研領域：分布式數(shù)據(jù)庫和數(shù)據(jù)挖掘。樂嘉錦，教授。王梅，副教授。

中圖分類號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