（東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 上海 201620）

摘 要：

聚類分析是數(shù)據(jù)挖掘中一個重要研究內(nèi)容。傳統(tǒng)的聚類算法可劃分為硬聚類和模糊聚類兩大類，提出一種基于對象集上的相容關(guān)系的聚類算法，該算法通過極大相容簇來對數(shù)據(jù)對象集進(jìn)行分類，使得同一對象可以屬于不同的簇，而每個簇又有自己獨(dú)有的成員對象，從而得到既不同于硬聚類也不同于模糊聚類的聚類效果。實驗進(jìn)一步表明了該算法的聚類的合理性。

關(guān)鍵詞：聚類； 相容關(guān)系； 相容（子）集

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)04-1302-03

Clustering on compatible relation

WAN Ren-xia， WANG Li-xin， LIU Zhen-wen， SU Xiao-ke

(College of Information Science Technology， Donghua University， Shanghai 201620， China)

Abstract:

Cluster analysis had played a very important role in data mining. This paper proposed a new algorithm based on compatible relation. The new algorithm grouped objects by the maximum compatible clusters and permited one object belonging to several different clusters while every cluster had its exclusive members， which gained a different clustering result from the traditional cluster algorithms. The experiments get a consistent result.

Key words：cluster; compatible relation; compatible subset

0 引言

近年來，對數(shù)據(jù)集上的聚類算法已有了廣泛的研究。總體來說，傳統(tǒng)聚類算法可以劃分為硬聚類和模糊聚類兩大類[1]。硬聚類算法將數(shù)據(jù)集劃分為不相交的幾個數(shù)據(jù)子集，每個數(shù)據(jù)子集代表一個類簇，而模糊聚類更多的是關(guān)注于簇中心及各個數(shù)據(jù)與所有簇中心隸屬關(guān)系的變化，分析每個數(shù)據(jù)點(diǎn)隸屬于各個簇的程度。本文提出了一種基于數(shù)據(jù)點(diǎn)間關(guān)系度量的聚類算法，該算法依據(jù)數(shù)據(jù)點(diǎn)間關(guān)系程度進(jìn)行聚類，得到了不同于傳統(tǒng)算法的聚類結(jié)果?；谡鎸崝?shù)據(jù)集的實驗分析表明新算法具有比傳統(tǒng)算法更為合理的聚類效果。

1 相關(guān)工作

傳統(tǒng)的聚類是指將數(shù)據(jù)對象分組成為若干個類，使得在同類中的對象間具有較高的相異度，而不同類中的對象差別較大。相異度是根據(jù)描述對象的屬性值來計算的，而距離是其經(jīng)常采用的度量方式。在聚類分析中，許多基于內(nèi)存的聚類算法選擇如下兩種有代表性的數(shù)據(jù)結(jié)構(gòu):a)數(shù)據(jù)矩陣。它用P個屬性來表示n個對象，表現(xiàn)形式是[xij]n×p。其中xij表示對象i在屬性j上的取值。b)相異度矩陣。它用來存儲n個對象兩兩間的相異性，表現(xiàn)形式是[D(i，j)]n×n。其中D(i，j)是對象i與對象j間相異性的量化表示，其值越小，兩個對象就越接近，且D(i，j)≥0，D(i，i)=0，D(i，j)=D(j，i)。從數(shù)據(jù)對象間的關(guān)系角度上來說，相異度只是對數(shù)據(jù)對象之間的離散關(guān)系的一種分析，這只是數(shù)據(jù)對象間關(guān)系分析的一種，而實際上數(shù)據(jù)對象的關(guān)系可能會比較復(fù)雜，甚至有些關(guān)系是不可以用相異度來衡量的，如對操場上的學(xué)生按朋友關(guān)系分組。

文獻(xiàn)[2，3]研究了利用偏序關(guān)系和偏序集進(jìn)行分層聚類的問題，提出了PoClustering算法，該算法在基因分組的實驗中表現(xiàn)出更好的分類效果。

文獻(xiàn)[4]研究了利用相異度的正交變換對具有三角不等式特性的高維數(shù)據(jù)的聚類問題，并通過誤差評價邊界來降低聚類的計算復(fù)雜度和提升其可擴(kuò)展性。

文獻(xiàn)[5]利用壓縮相異度的方法來擴(kuò)展K-modes算法，并利用啟發(fā)式的方法來改進(jìn)相異度的簡單匹配。

文獻(xiàn)[6]研究了利用相異度平滑的技術(shù)來對二元變量聚類的方法。通過收縮評價的思想來過濾噪聲數(shù)據(jù)，從而達(dá)到平滑相異度矩陣的目的。

文獻(xiàn)[7]通過定義關(guān)系和多值對象屬性及類型多樣性的拓?fù)錅y度來構(gòu)建一類特殊的相異度模型，并基于此模型完成自動分類的目標(biāo)。

文獻(xiàn)[8]介紹了等價相異度矩陣的性質(zhì)，并給出了等價相異度矩陣的逐次平方求解方法和基于相異度矩陣的聚類算法。

上述研究主要還是基于對象間相異或相似關(guān)系，其聚類結(jié)果也往往都是些類球形的簇?？傮w來說，基于數(shù)據(jù)對象間非相異或相似關(guān)系的研究還較少見報道；從現(xiàn)有的聚類技術(shù)來看，各種聚類方法也都沒有很好地利用相異度的性質(zhì)。本文研究基于相容關(guān)系的聚類問題，并對相異度聚類的性質(zhì)和方法作了進(jìn)一步探討。

2 對象集上的相容關(guān)系

定義1 設(shè)D是對象集S上的關(guān)系度量，δ(≥0)是已給定的閾值，滿足：

a) D是自反的（即當(dāng)且僅當(dāng)x∈S，有D(x，x)≤δ）。

b) D是對稱的（即當(dāng)且僅當(dāng)x，y∈S，如果D(x，y)≤δ，則D(y，x)≤δ）。

本文稱D為S上的一個相容關(guān)系，S是關(guān)系D下一個相容集。

一對概念間的相似度是指它們共享信息的程度[2]，因而相異度可以理解為兩概念間最小的差異信息程度。由于相異測度中，對于對象i、j總有D(i， i)=0， D(i， j)=D(j， i)成立，相異性是對象間的一種特殊的相容關(guān)系。

定義2 設(shè)C是對象集S的一個子集，D是S上的一個關(guān)系，如果C是關(guān)系D下的一個相容集，則稱C是關(guān)系D下S的一個相容子集。

當(dāng)關(guān)系是相異度時，此時對象集可以看做是一些相容子集的合集。這是因為對象集總能由單個對象構(gòu)成的單點(diǎn)集的合集構(gòu)成，而單點(diǎn)集{v}總是相容的（因為D(v， v)=0）。

定義3 設(shè)在關(guān)系D下C是對象集S的一個相容子集，如果不存在另一個相容子集C′，使得C是C′的一個真子集，則C是S的一個極大相容子集。

定理1 設(shè)S是任意一個對象集，D是S上的一個關(guān)系，C是關(guān)系D下S的一個相容子集，則必存在一個極大相容子集CD，使得 CCD。

證明 S={a1，a2，…，an}，構(gòu)造相容子集系列C0C1C2…。其中C0=C且Ci+1=Ci∪{aj}。其中j滿足ajCi，而 aj與Ci中各對象都有相容關(guān)系的最小足標(biāo)。

由于對象集S所含對象的個數(shù) |S|=n，至多經(jīng)過 n-|C|步就使這個過程終止，而此序列的最后一個相容子集即為所要找的極大相容子集。 證畢。

定理2 設(shè)S是任意一個對象集，如果在S上定義一個關(guān)系D，則存在此關(guān)系下S的惟一一個極大相容子集的集合，使得所有這些相容子集的并集等于S。

證明 若在關(guān)系D下，對象集S上的每個相容子集都是單點(diǎn)集，則單點(diǎn)集即為S的極大相容子集；若存在相容子集，由定理1必存在包含此相容子集的極大相容子集。設(shè){S1，S2，…，Sm}是關(guān)系D下S所有的極大相容子集的集合。如果存在對象ai∈S但ai∪mk=1Sk，若ai構(gòu)成相容單點(diǎn)集{ai}，則{ai}即為S的一個極大相容子集，這與{S1，S2，…，Sm}是關(guān)系D下S所有的極大相容子集的集合矛盾；若存在包含ai的一個S的極大相容子集S′，則S′必屬于{S1，S2，…，Sm}，這又與ai∪mk=1Sk矛盾。所以關(guān)系D下S一定存在極大相容子集的集合，使得所有這些相容子集的并集等于S。

如果關(guān)系D下S存在另一極大相容子集的集合{S′1，S′2，…，S′l}且S=∪mk=1S′k，證明{S1，S2，…，Sm}={S′1，S′2，…，S′l}。

不妨設(shè)S′j(j∈{1，2，…，l})為不同于任意Si(i=1，2，…，m)的任意一極大相容子集， ΔS為S′j與{S1，S2，…，Sm}中的Si1，Si2，…，Sim0的交集，即ΔS=S′j∩Si1=S′j∩Si2=…=S′j∩Sim0。記S′j-ΔS={aj1，aj2，…，ajr}，不妨設(shè)aj1∈Si1，aj2∈Si2，由于aj1、aj2同屬于極大相容子集S′j，{aj1}∪{aj2}∪ΔS是一相容子集；由于Si1是包含 {aj1}∪ΔS的一極大相容子集，aj2∈Si1，同理可得aj3∈Si1，…，ajr∈Si1，即aj1，aj2，…，ajr∈Si1，所以ΔS∪{aj1，aj2，…，ajr}Si1，即S′jSi1，而S′j是S的一極大相容子集，S′j=Si1。這與“不妨設(shè)S′j(j∈{1，2，…，l})為不同于任意Si(i=1，2，…，m)的任意一極大相容子集”的假設(shè)矛盾，從而證明了極大相容子集的集合存在的惟一性。證畢。

3 基于相容關(guān)系的聚類

由上述定理2可知，對于任意一個給定的對象集和一關(guān)系度量，對象集的每個極大相容子集就是一個基于此關(guān)系的對象分組（即對象簇），由此可得到如下基于相容關(guān)系的聚類算法。

3.1 相容關(guān)系的聚類算法

算法：Comp-clustering

輸入：D——關(guān)系度量；S——對象集； δ——閾值

輸出：SC——相容簇

 SC=;Cnew=

while S≠ do

x∈S；Cnew←x

S=S-{x}；

S(x)={y|D(y，x)≤δ and D(x，y)≤δ，y∈S}；

while S(x)≠ do

 z∈S(x);Cnew←z;S(x)=S(x)-{z};

 S′=S-Cnew;

 while S′≠ do

 if(w∈S′， for all u∈Cnew such that

 D(w，u)≤δ and D(u，w)≤δ) then

Cnew←w；

 end if

 S′=S′-{w};

 end while ∥S′

 if !C∈SC， such that CnewC then

SC←Cnew;Cnew=;

 end if

 end while∥S(x)

 end while∥S

return SC

如表1所示，給定對象集{A， B， C， D， E， F， G}的相異度矩陣（其中∞表示兩對象間沒有相異度值），閾值δ取值為{1， 2， 3， 4， 5}的結(jié)果如表2 所示。



3.2 算法的圖表示

實際上，給定任一相容集S是可以用有向加權(quán)的圖G=〈V， E， W〉來表示，其中圖G中頂點(diǎn)集V的每個點(diǎn)對應(yīng)S中一個對象，E中每條邊e=〈x， y〉的權(quán)值w表示對象x與對象y之間的關(guān)系度量值D(x， y)與D(y， x)中較小的那一個。由此，從對象集S中求每個極大相容子集等價于從相應(yīng)的圖G找最大完全子圖。

圖1為表1對應(yīng)的無向加權(quán)圖，則聚類結(jié)果如圖2所示。圖2中，加粗的黑線表示公共邊，同線型的邊代表同一個類族。



4 實驗結(jié)果與分析

為了進(jìn)一步了解Comp-clustering算法的聚類效果，筆者采用一個包含20個數(shù)據(jù)點(diǎn)的數(shù)據(jù)集S 20（圖3）對新算法進(jìn)行了聚類效果的實驗測試。

4.1 實驗設(shè)置

本文實驗平臺配置如下：CPU為Intel Pentium 2.2 GHz，內(nèi)存為512 MB， 操作系統(tǒng)為Windows XP Professional Edition， 所用代碼均用7.0編程實現(xiàn)。

4.2 聚類效果分析

為了得到較好的聚類效果，首先考察該數(shù)據(jù)的相異度的頻度分布情況，如圖4所示。



從圖4中可以看出，相異度在0.2~0.6的數(shù)據(jù)量保持在70%左右，因此實驗時分別選取相異度值 δ為0.2、0.4、0.6，其聚類效果如圖5所示。

可以看出，本文的算法與傳統(tǒng)的硬聚類和模糊聚類有明顯的不同：Comp-clustering允許同一個對象屬于多個簇，這點(diǎn)不同于傳統(tǒng)的硬聚類算法；同時，各個簇又都必須有自己獨(dú)有的對象，這又明顯不同于模糊聚類及其變體[9]。

5 結(jié)束語

本文提出了一種基于數(shù)據(jù)對象間關(guān)系的聚類算法，并通過實驗演示了該算法的聚類效果，進(jìn)一步表明該算法具有不同于傳統(tǒng)算法的聚類效果。新算法對于對象間具有相容關(guān)系的對象集的聚類將表現(xiàn)出其可靠的合理性。該新算法在聚類前須指定劃分水平δ，不同的δ會得到不同的聚類效果。然而在聚類前指定劃分水平要比預(yù)先指定聚類簇數(shù)的傳統(tǒng)聚類算法難以操作得多，如何指定一個合適的劃分水平尚需要進(jìn)一步的研究；另外，分層聚類在不同粒度的數(shù)據(jù)分析方面有著重要的意義，如何構(gòu)建基于新算法的分層聚類也有待于深入討論。這些都是下一步需要開展的工作。



參考文獻(xiàn):

[1]JAIN A K， MURTY M N， FLYNN P J. Data clustering: a review[J]. ACM Computing Surveys， 1999，31(3): 264-323.

[2]LIU Jin-ze， ZHANG Qi， WANG Wei， et al. Clustering pairwise dissimilarity data into partially ordered sets[C]//Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press， 2006:637-642.

[3]LIU Jin-ze， ZHANG Qi， WANG Wei， et al. PoClustering: lossless clustering of dissimilarity data[C]//Proc of the 7th SIAM Internatio-nal Conference on Data Mining. 2007:55-81.

[4]SOCOLOVSKY E A. A dissimilarity measure for clustering high-and infinite dimensional data that satisfies the triangle inequality[R]. NASA LaRC Technical Library Digital Repository， 2002:1-12.

[5]NG M K， LI M J， HUANG J Z， et al. On the impact of dissimilarity measure in k-modes clustering algorithm[J]. IEEE Trans on Pattern analysis and Machine Intelligence， 2007，29(3):503-507.

[6]HITCHCOCK D B， CHEN Zhi-min. Smoothing dissimilarities to cluster binary data[J]. Computational Statistics and Data Analysis， 2008，52(10):4699-4711.

[7]VALTCHEV P， EUZENAT J. Dissimilarity Measure for collections of objects and values [C]//Proc of Lecture Notes in Computer Sciences. Berlin:Springer， 1997:259-272.

[8]趙明清， 蔣昌俊， 陶樹平. 基于等價相異度矩陣的聚類[J].計算機(jī)科學(xué)， 2004， 31(7):183-184.

[9]HORE P， HANLL L O， GOLDGOF D B. A fuzzy C means variant for clustering evolving data stream[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics. 2007:360-365.

[10]EPP S S. Discrete mathematics with applications[M]. 3rd ed. [S.l.]: Thomson Learning Asia Pte Ltd， 2004:571-610.

[11]ROSS K A， WRIGHT C R B. Discrete mathematics[M]. 5th ed. [S.l.]: Pearson Education， 2003:95-118.