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

李曄鋒　樂嘉錦　王　梅

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　上海 201620)

?

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

李曄鋒樂嘉錦王梅

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院上海 201620)

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

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

0引言

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

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

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

1CLOPE算法

1.1相關(guān)定義

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

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

定義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中事務(wù)的數(shù)目，表示為|c|。

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

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

(5)

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

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

1.2缺陷與不足

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

假設(shè)數(shù)據(jù)庫D中有如下事務(wù)：{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。但是，如果把事務(wù)的輸入順序改成{ab, bc, bcd, acd, ac, abd}，CLOPE把所有的事務(wù)放到一個(gè)聚簇中作為聚類結(jié)果，則收益值的分子部分為15×6÷42=5.625。

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

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

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

2.1擴(kuò)展CLOPE算法

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

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

(6)

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

(7)

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

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

(8)

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

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

(9)

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

(10)

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

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

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

圖1　聚簇的合并過程

仍然以輸入數(shù)據(jù){ab, bc, ac, abd, bcd, acd}為例，圖1顯示了聚簇的合并過程。首先，每個(gè)事務(wù)單獨(dú)作為一個(gè)聚簇加入到G的頂點(diǎn)集V中，然后分別計(jì)算各頂點(diǎn)之間的差值，并把差值等于GM的頂點(diǎn)連接成邊加入到E中；接著把G中所有的連通子圖各自合并成一個(gè)頂點(diǎn)，生成新的無向圖G′。反復(fù)迭代直到無向圖中不包含邊時(shí)算法終止。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實(shí)驗(yàn)分析

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

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

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

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

圖2　CLOPE和HCLOPE花費(fèi)的時(shí)間比較

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)和聚簇?cái)?shù)目(cluster no.)的值。聚類的純度計(jì)算方法為取每個(gè)聚簇中可食用蘑菇和有毒蘑菇的最大值相加，所得的值越大聚類質(zhì)量越好。圖4 的實(shí)驗(yàn)結(jié)果顯示，當(dāng)r≥2.8時(shí)，CLOPE和HCLOPE的純度均到達(dá)事務(wù)的總數(shù)8124，并且聚簇的數(shù)目穩(wěn)定保持為23。在其他情況下，HCLOPE要略微優(yōu)于CLOPE。

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

4結(jié)語

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

參考文獻(xiàn)

[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。李曄鋒，博士生，主研領(lǐng)域：分布式數(shù)據(jù)庫和數(shù)據(jù)挖掘。樂嘉錦，教授。王梅，副教授。

中圖分類號TP301.6

文獻(xiàn)標(biāo)識碼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