一種基于相容關系的聚類算法
2009-01-01 00:00:00萬仁霞王立新劉振蘇曉珂
計算機應用研究 2009年4期
（東華大學 信息科學與技術學院， 上海 201620）
摘 要：
聚類分析是數據挖掘中一個重要研究內容。傳統的聚類算法可劃分為硬聚類和模糊聚類兩大類，提出一種基于對象集上的相容關系的聚類算法，該算法通過極大相容簇來對數據對象集進行分類，使得同一對象可以屬于不同的簇，而每個簇又有自己獨有的成員對象，從而得到既不同于硬聚類也不同于模糊聚類的聚類效果。實驗進一步表明了該算法的聚類的合理性。
關鍵詞：聚類； 相容關系； 相容（子）集
中圖分類號：TP391文獻標志碼：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 引言
近年來，對數據集上的聚類算法已有了廣泛的研究。總體來說，傳統聚類算法可以劃分為硬聚類和模糊聚類兩大類[1]。硬聚類算法將數據集劃分為不相交的幾個數據子集，每個數據子集代表一個類簇，而模糊聚類更多的是關注于簇中心及各個數據與所有簇中心隸屬關系的變化，分析每個數據點隸屬于各個簇的程度。本文提出了一種基于數據點間關系度量的聚類算法，該算法依據數據點間關系程度進行聚類，得到了不同于傳統算法的聚類結果。基于真實數據集的實驗分析表明新算法具有比傳統算法更為合理的聚類效果。
1 相關工作
傳統的聚類是指將數據對象分組成為若干個類，使得在同類中的對象間具有較高的相異度，而不同類中的對象差別較大。相異度是根據描述對象的屬性值來計算的，而距離是其經常采用的度量方式。在聚類分析中，許多基于內存的聚類算法選擇如下兩種有代表性的數據結構:a)數據矩陣。它用P個屬性來表示n個對象，表現形式是[xij]n×p。其中xij表示對象i在屬性j上的取值。b)相異度矩陣。它用來存儲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)。從數據對象間的關系角度上來說，相異度只是對數據對象之間的離散關系的一種分析，這只是數據對象間關系分析的一種，而實際上數據對象的關系可能會比較復雜，甚至有些關系是不可以用相異度來衡量的，如對操場上的學生按朋友關系分組。
文獻[2，3]研究了利用偏序關系和偏序集進行分層聚類的問題，提出了PoClustering算法，該算法在基因分組的實驗中表現出更好的分類效果。
文獻[4]研究了利用相異度的正交變換對具有三角不等式特性的高維數據的聚類問題，并通過誤差評價邊界來降低聚類的計算復雜度和提升其可擴展性。
文獻[5]利用壓縮相異度的方法來擴展K-modes算法，并利用啟發式的方法來改進相異度的簡單匹配。
文獻[6]研究了利用相異度平滑的技術來對二元變量聚類的方法。通過收縮評價的思想來過濾噪聲數據，從而達到平滑相異度矩陣的目的。
文獻[7]通過定義關系和多值對象屬性及類型多樣性的拓撲測度來構建一類特殊的相異度模型，并基于此模型完成自動分類的目標。
文獻[8]介紹了等價相異度矩陣的性質，并給出了等價相異度矩陣的逐次平方求解方法和基于相異度矩陣的聚類算法。
上述研究主要還是基于對象間相異或相似關系，其聚類結果也往往都是些類球形的簇。總體來說，基于數據對象間非相異或相似關系的研究還較少見報道；從現有的聚類技術來看，各種聚類方法也都沒有很好地利用相異度的性質。本文研究基于相容關系的聚類問題，并對相異度聚類的性質和方法作了進一步探討。
2 對象集上的相容關系
定義1 設D是對象集S上的關系度量，δ(≥0)是已給定的閾值，滿足：
a) D是自反的（即當且僅當x∈S，有D(x，x)≤δ）。
b) D是對稱的（即當且僅當x，y∈S，如果D(x，y)≤δ，則D(y，x)≤δ）。
本文稱D為S上的一個相容關系，S是關系D下一個相容集。
一對概念間的相似度是指它們共享信息的程度[2]，因而相異度可以理解為兩概念間最小的差異信息程度。由于相異測度中，對于對象i、j總有D(i， i)=0， D(i， j)=D(j， i)成立，相異性是對象間的一種特殊的相容關系。
定義2 設C是對象集S的一個子集，D是S上的一個關系，如果C是關系D下的一個相容集，則稱C是關系D下S的一個相容子集。
當關系是相異度時，此時對象集可以看做是一些相容子集的合集。這是因為對象集總能由單個對象構成的單點集的合集構成，而單點集{v}總是相容的（因為D(v， v)=0）。
定義3 設在關系D下C是對象集S的一個相容子集，如果不存在另一個相容子集C′，使得C是C′的一個真子集，則C是S的一個極大相容子集。
定理1 設S是任意一個對象集，D是S上的一個關系，C是關系D下S的一個相容子集，則必存在一個極大相容子集CD，使得 CCD。
證明 S={a1，a2，…，an}，構造相容子集系列C0C1C2…。其中C0=C且Ci+1=Ci∪{aj}。其中j滿足ajCi，而 aj與Ci中各對象都有相容關系的最小足標。
由于對象集S所含對象的個數 |S|=n，至多經過 n-|C|步就使這個過程終止，而此序列的最后一個相容子集即為所要找的極大相容子集。 證畢。
定理2 設S是任意一個對象集，如果在S上定義一個關系D，則存在此關系下S的惟一一個極大相容子集的集合，使得所有這些相容子集的并集等于S。
證明 若在關系D下，對象集S上的每個相容子集都是單點集，則單點集即為S的極大相容子集；若存在相容子集，由定理1必存在包含此相容子集的極大相容子集。設{S1，S2，…，Sm}是關系D下S所有的極大相容子集的集合。如果存在對象ai∈S但ai∪mk=1Sk，若ai構成相容單點集{ai}，則{ai}即為S的一個極大相容子集，這與{S1，S2，…，Sm}是關系D下S所有的極大相容子集的集合矛盾；若存在包含ai的一個S的極大相容子集S′，則S′必屬于{S1，S2，…，Sm}，這又與ai∪mk=1Sk矛盾。所以關系D下S一定存在極大相容子集的集合，使得所有這些相容子集的并集等于S。
如果關系D下S存在另一極大相容子集的集合{S′1，S′2，…，S′l}且S=∪mk=1S′k，證明{S1，S2，…，Sm}={S′1，S′2，…，S′l}。
不妨設S′j(j∈{1，2，…，l})為不同于任意Si(i=1，2，…，m)的任意一極大相容子集， ΔS為S′j與{S1，S2，…，Sm}中的Si1，Si2，…，Sim0的交集，即ΔS=S′j∩Si1=S′j∩Si2=…=S′j∩Sim0。記S′j-ΔS={aj1，aj2，…，ajr}，不妨設aj1∈Si1，aj2∈Si2，由于aj1、aj2同屬于極大相容子集S′j，{aj1}∪{aj2}∪ΔS是一相容子集；由于Si1是包含 {aj1}∪ΔS的一極大相容子集，aj2∈Si1，同理可得aj3∈Si1，…，ajr∈Si1，即aj1，aj2，…，ajr∈Si1，所以ΔS∪{aj1，aj2，…，ajr}Si1，即S′jSi1，而S′j是S的一極大相容子集，S′j=Si1。這與“不妨設S′j(j∈{1，2，…，l})為不同于任意Si(i=1，2，…，m)的任意一極大相容子集”的假設矛盾，從而證明了極大相容子集的集合存在的惟一性。證畢。
3 基于相容關系的聚類
由上述定理2可知，對于任意一個給定的對象集和一關系度量，對象集的每個極大相容子集就是一個基于此關系的對象分組（即對象簇），由此可得到如下基于相容關系的聚類算法。
3.1 相容關系的聚類算法
算法：Comp-clustering
輸入：D——關系度量；S——對象集； δ——閾值
輸出：SC——相容簇
SC=;Cnew=
while S≠ do
x∈S；Cnew←x
S=S-{x}；
S(x)={y|D(y，x)≤δ and D(x，y)≤δ，y∈S}；
while S(x)≠ do
z∈S(x);Cnew←z;S(x)=S(x)-{z};
S′=S-Cnew;
while S′≠ do
if(w∈S′， for all u∈Cnew such that
D(w，u)≤δ and D(u，w)≤δ) then
Cnew←w；
end if
S′=S′-{w};
end while ∥S′
if !C∈SC， such that CnewC then
SC←Cnew;Cnew=;
end if
end while∥S(x)
end while∥S
return SC
如表1所示，給定對象集{A， B， C， D， E， F， G}的相異度矩陣（其中∞表示兩對象間沒有相異度值），閾值δ取值為{1， 2， 3， 4， 5}的結果如表2 所示。
3.2 算法的圖表示
實際上，給定任一相容集S是可以用有向加權的圖G=〈V， E， W〉來表示，其中圖G中頂點集V的每個點對應S中一個對象，E中每條邊e=〈x， y〉的權值w表示對象x與對象y之間的關系度量值D(x， y)與D(y， x)中較小的那一個。由此，從對象集S中求每個極大相容子集等價于從相應的圖G找最大完全子圖。
圖1為表1對應的無向加權圖，則聚類結果如圖2所示。圖2中，加粗的黑線表示公共邊，同線型的邊代表同一個類族。
4 實驗結果與分析
為了進一步了解Comp-clustering算法的聚類效果，筆者采用一個包含20個數據點的數據集S 20（圖3）對新算法進行了聚類效果的實驗測試。
4.1 實驗設置
本文實驗平臺配置如下：CPU為Intel Pentium 2.2 GHz，內存為512 MB， 操作系統為Windows XP Professional Edition， 所用代碼均用7.0編程實現。
4.2 聚類效果分析
為了得到較好的聚類效果，首先考察該數據的相異度的頻度分布情況，如圖4所示。
從圖4中可以看出，相異度在0.2~0.6的數據量保持在70%左右，因此實驗時分別選取相異度值 δ為0.2、0.4、0.6，其聚類效果如圖5所示。
可以看出，本文的算法與傳統的硬聚類和模糊聚類有明顯的不同：Comp-clustering允許同一個對象屬于多個簇，這點不同于傳統的硬聚類算法；同時，各個簇又都必須有自己獨有的對象，這又明顯不同于模糊聚類及其變體[9]。
5 結束語
本文提出了一種基于數據對象間關系的聚類算法，并通過實驗演示了該算法的聚類效果，進一步表明該算法具有不同于傳統算法的聚類效果。新算法對于對象間具有相容關系的對象集的聚類將表現出其可靠的合理性。該新算法在聚類前須指定劃分水平δ，不同的δ會得到不同的聚類效果。然而在聚類前指定劃分水平要比預先指定聚類簇數的傳統聚類算法難以操作得多，如何指定一個合適的劃分水平尚需要進一步的研究；另外，分層聚類在不同粒度的數據分析方面有著重要的意義，如何構建基于新算法的分層聚類也有待于深入討論。這些都是下一步需要開展的工作。
參考文獻:
[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].計算機科學， 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.
