基于層次思想的聚類算法

基于層次思想的聚類算法

集群是挖掘研究的重要手段。到目前為止，研究人員提出了幾種集群算法，并在商業(yè)智能、web挖掘等領域得到了廣泛的應用。然而，許多集群算法要求用戶指定聚類數(shù)。事實上，用戶通常有必要根據(jù)自己的經(jīng)驗和相關領域的背景知識來確定數(shù)據(jù)集的數(shù)量?，F(xiàn)在，這也是集類分析研究的一個根本性問題?，F(xiàn)有的研究[2,3,4,5,6,7,8,9,10,11,12,13]是通過以下過程(一種迭代的trial-and-error過程)來確定數(shù)據(jù)集最佳聚類數(shù)的,如圖1所示.在給定的數(shù)據(jù)集或通過隨機抽樣得到的數(shù)據(jù)子集上,使用不同的參數(shù)(通常是聚類數(shù)k)運行特定的聚類算法對數(shù)據(jù)集進行不同的劃分,計算每種劃分的統(tǒng)計指標值,最后比較分析各個指標值的大小或變化情況,符合預定條件的指標值所對應的算法參數(shù)k被認為是最佳的聚類數(shù)k*.各種類型的統(tǒng)計指標從不同角度出發(fā)衡量數(shù)據(jù)集劃分的聚類質(zhì)量.聚類有效性指標(clustervalidityindex簡稱CVI)是一類常見的指標,在為數(shù)眾多的CVI[6,7,8,9,10,11,12,13]中,基于數(shù)據(jù)集幾何結(jié)構(gòu)的指標函數(shù)具有代表意義,它們考慮了聚類的基本特征,即一個“好”的聚類結(jié)果應使得k個簇的簇內(nèi)數(shù)據(jù)點是“緊湊”的,而不同簇的點之間是盡可能“分離”的,指標量化聚類的簇內(nèi)緊湊度和簇間分離度并組合二者,代表性的指標包括Xie-Beni指標Vxie和S.Wang-H.Sun-Q.Jiang指標Vwsj等.對應于最大或最小指標值的k被認為是最佳聚類數(shù)k*.其他類型的統(tǒng)計指標包括Gapstatistic、信息熵和IGP(in-groupproportion)等,其中,IGP是一種新近提出的指標,它使用簇內(nèi)數(shù)據(jù)點的in-group比例來衡量聚類結(jié)果的質(zhì)量,取得了優(yōu)于現(xiàn)有其他指標的性能.然而,現(xiàn)有的工作[2,3,4,5,6,7,8,9,10,11,12,13]多集中在對統(tǒng)計指標的改進上,而忽略了對計算過程的研究.圖1所示的計算過程存在兩個問題:首先,由于需要多次地對整個數(shù)據(jù)集進行聚類,其效率顯然與所選用聚類算法本身的效率密切相關,且將隨著數(shù)據(jù)集的增大而顯著下降.盡管可以通過減少聚類次數(shù)來提高效率,然而估計準確的kmin和kmax也是不容易的;其次,指標被特定的聚類算法聯(lián)系在一起.例如,實際中許多CVI是與FCM(fuzzyC-mean)算法(或融合GA(geneticalgorithm)算法)結(jié)合在一起的,上述的其他指標出于計算的需要總要選擇以聚類數(shù)k為參數(shù)的算法,如k-means或?qū)哟涡途垲愃惴?這導致了指標性能依賴于聚類算法的問題.例如,FCM和k-means算法存在不能有效識別噪聲和只能發(fā)現(xiàn)凸形簇的局限性,使得這些指標自然地存在同樣的缺陷.本文提出的新方法COPS(clustersoptimizationonpreprocessingstage)采用與圖1完全不同的兩階段計算方案,首先通過掃描一遍數(shù)據(jù)集一次性地構(gòu)造出數(shù)據(jù)集所有合理的劃分組合,進而生成一條關于不同劃分的聚類質(zhì)量曲線;在第2階段抽取出對應曲線極小值點的劃分來估計數(shù)據(jù)集的最佳聚類數(shù)目,從而避免了對大型數(shù)據(jù)集的反復聚類,且不依賴于特定的聚類算法,能夠有效識別數(shù)據(jù)集中可能包含的噪聲和復雜形狀的簇.在實際數(shù)據(jù)和合成數(shù)據(jù)上的測試結(jié)果表明,COPS的性能優(yōu)于IGP,同時大幅度提高了計算效率.本文第1節(jié)給出COPS方法.第2節(jié)提出和分析COPS使用的聚類有效性新指標.第3節(jié)進行實驗驗證和分析.最后在第4節(jié)作出總結(jié).1數(shù)據(jù)集聚類方法給定d維數(shù)據(jù)集DB={X1,X2,…,Xn},X={x1,x2,…,xd}為一個數(shù)據(jù)點,n為數(shù)據(jù)點數(shù)目.一個硬劃分聚類算法將DB劃分為k(k>1)個子集的集合Ck={C1,C2,…,Ck},且?j≠l,1≤j,l≤k,Cj∩Cl=Φ,Cj稱為DB的簇.常用的trail-anderror方法為產(chǎn)生Ck(k=kmin,…,kmax)需要對數(shù)據(jù)集進行kmax-kmin+1次聚類,這影響了算法效率,尤其當數(shù)據(jù)量較大時;另一方面,不恰當?shù)膋min和kmax設置也會影響計算結(jié)果的準確性.因此,若能根據(jù)數(shù)據(jù)集的幾何結(jié)構(gòu)一次性地生成所有合理的劃分,同時評估它們的聚類質(zhì)量,就可以在很大程度上提高計算效率和結(jié)果的準確性.COPS借鑒層次聚類的思想來達到這個目的.其原理是,首先將每個數(shù)據(jù)點看作單獨的簇,然后在自底向上層次式的簇合并過程中生成所有合理的劃分,同時計算它們的聚類質(zhì)量,保存具有最優(yōu)聚類質(zhì)量的劃分為C*,最后根據(jù)C*的有關統(tǒng)計信息來估計聚類數(shù)k*.這里使用新的聚類有效指標性指標函數(shù)Q(C)來評估劃分C的聚類質(zhì)量,其最小值對應最優(yōu)的質(zhì)量.COPS計算過程的形式化表示如下:COPS的處理對象是可能包含噪聲和復雜形狀(非凸形)簇的數(shù)據(jù)集,這樣的數(shù)據(jù)在實際應用中是常見的,如空間數(shù)據(jù)和一些高維度的數(shù)據(jù).過程θ剔除噪聲的影響,識別C*中有意義的簇的數(shù)目.1.1tda型數(shù)據(jù)集下面,首先結(jié)合距離和維度投票(dimensionvoting)思想提出數(shù)據(jù)點間相似度的定義,以此為基礎給出確定DB最優(yōu)劃分C*的計算過程.定義1(點的相似維度).給定一個閾值tj≥0,1≤j≤d,若|xj-yj|≤tj,則稱點X和Y是關于tj第j維相似的.根據(jù)定義1,可以定義相似的數(shù)據(jù)點.定義2(相似點).給定一個閾值向量T={t1,t2,…,td},若點X和Y在所有數(shù)據(jù)維度上都是關于tj(j=1,2,…,d)相似的,則稱數(shù)據(jù)點X和Y是關于T相似的.彼此相似的數(shù)據(jù)點組成DB的簇.若T的各分量相等,則||T||相當于基于密度聚類算法中點的鄰域半徑.這里,我們允許T的各分量不相等,它反映了數(shù)據(jù)集各維度屬性值分布的差異.顯然,T的取值“大小”決定了簇結(jié)構(gòu).鑒于T是一個向量,定義3用于比較不同T之間的相對關系.定義3(T的比較).給定兩個閾值向量Ta={t1a,t2a,...,tda}和Tb={t1b,t2b,...,tdb},稱Ta>Tb若滿足:(2)至少存在一個j∈[1,d],使得tja>tjb.給定數(shù)據(jù)集DB,根據(jù)定義2和定義3,一個很小的T令大多數(shù)數(shù)據(jù)點不相似,極端情形是每個數(shù)據(jù)點(設DB中沒有相同的數(shù)據(jù)點)都構(gòu)成單獨的“簇”,此時,DB的劃分數(shù)目達到最大值,k=n;記這樣的T為T0.相反地,一個足夠大的T將使得所有數(shù)據(jù)點彼此相似而組成一個大簇,此時,k達到最小值,k=1;用Tm表示使得k=1的最小的T.至此,可以把確定數(shù)據(jù)集DB最優(yōu)劃分C*的問題轉(zhuǎn)換為求解最優(yōu)閾值向量T*(T0<T*<Tm)的問題,T*是使得Q在T從T0開始增大到Tm過程中取得最小值的閾值向量.由此可以給出COPS的計算過程,如圖2所示.計算從T=T0(每個分量值為0)開始,每個步驟T增大一個量Δ(Δ={Δ1,Δ2,…,Δd}),根據(jù)定義2,此時將有部分原本屬于不同子集的點變得相似,這些子集被合并,生成了新的劃分;對每個劃分計算其Q的值,直到T增長到所有點被劃分到同一個集合為止.這里子集的合并,也就是簇的合并,以類似singlelink的方式進行.圖3給出一個例子,說明圖2的計算過程如何自底向上地進行簇的合并.圖3給出了COPS在一個2維數(shù)據(jù)集上若干步驟的結(jié)果,該數(shù)據(jù)集包含2個簇和1個噪聲點,其中一個簇是非凸形的.如初始狀態(tài)圖3(a)所示,所有的數(shù)據(jù)點均構(gòu)成獨立的簇;隨T的增大數(shù)據(jù)點被逐漸合并,假設在某個步驟形成了圖3(b)所示的橢圓形區(qū)域所代表的若干個小簇;當T進一步增大使得兩個分屬于不同簇的點(如圖3(b)中分屬于簇A和B的兩個標志為‘x’的點)變得相似時,兩個原本為凸形的簇被合并.基于這樣的策略可以生成任意形狀的簇,如圖3(c)所示,最終合并成了一個banana型的非凸形簇.圖3中,3個階段的簇結(jié)構(gòu)組成聚類樹的3個層次(實際的聚類樹可能不止這3個層次,作為一個例子,這里只給出其中的3層).對于每個層次上的簇集合,分別計算它們的Q值,抽取出其中使得Q取值最小的層次,識別其中的噪聲點.考慮圖3(c)所示的簇集合,位于下方只包含一個數(shù)據(jù)點的“簇”被識別為噪聲,這樣就得到了該數(shù)據(jù)集的最佳聚類數(shù)目為2.以上簇的合并方法與singlelink的區(qū)別是,傳統(tǒng)的singlelink方式以全空間的歐氏距離為基礎,而COPS依據(jù)定義2來衡量簇間的相似度.Singlelink已被證明可以識別數(shù)據(jù)集中非凸形的簇結(jié)構(gòu),我們在此基礎上增加考慮了數(shù)據(jù)集各維度屬性值分布的差異因素,這種差異在具有較高維度的實際應用數(shù)據(jù)中是常見的.Δ的選取以及隨T的變化如何快速地生成新的劃分和計算Q值是影響算法性能的重要環(huán)節(jié),以下章節(jié)將分別闡述.1.2tj/yj-yj/tj/tj/tjCOPS的計算過程類似于凝聚型層次聚類算法中層次聚類樹的構(gòu)建過程.然而,一個典型的層次聚類算法具有O(n2)的計算復雜度.性能的瓶頸在于為每個數(shù)據(jù)點X查找與其相似點的集合Neighbors(X),這是rangequeries問題,通常這需要遍歷整個數(shù)據(jù)集,一些改進方法可參見文獻.基于定義2可以簡化查找相似點的過程.首先將數(shù)據(jù)點按照每個維度的屬性值大小進行排序(每個維度j有一個排序的序列Aj);根據(jù)定義1,通過順序掃描Aj可以得到所有與點X第j維相似的點Y,掃描范圍局限在符合|xj-yj|≤tj條件的有限區(qū)間內(nèi).當tj增加Δj時,只需在原有范圍的基礎上擴展掃描區(qū)間tj<|xj-yj|≤tj+Δj即可.基于此優(yōu)化方法的COPS偽代碼如圖4所示.其中MergePartitions的功能是在Ck+1的基礎上合并兩個相似點X和Y所在的子集生成新的劃分Ck;UpdateQ在Q(Ck+1)的基礎上根據(jù)X和Y所在子集的統(tǒng)計信息計算得到新的值Q(Ck).第2節(jié)將闡述基于CF的子集合并和Q(C)的計算方法.算法參數(shù)Δ的選取與T的一個隱含性質(zhì)有關.考察定義2,T可以看作是聚類數(shù)據(jù)集的分辨率(clusteringresolution),而分辨率可以被想象為一個看待數(shù)據(jù)點是否構(gòu)成簇的“望遠鏡”.由此可知,T的各分量間應成一定的比例關系,這個比例與數(shù)據(jù)點投影到各維度上時點的分布密度有關.同理,Δ的各分量間也應具有這個性質(zhì).定義4通過度量維度的稀疏度來量化這種比例關系.定義4(維度稀疏度).數(shù)據(jù)集DB在第j維的分布稀疏度為λj,其中,x′ij是數(shù)據(jù)點Xi第j維屬性的規(guī)范化值,μj表示第j維的中心,即λj實際上是數(shù)據(jù)集第j維規(guī)范化的標準偏差.在高維數(shù)據(jù)的投影聚類中,正是以標準偏差為基礎度量維度與簇之間的相關程度.λj值越大,表明第j維屬性值分布得越稀疏,與其相關的簇也可能就越多.COPS利用這些維度上屬性值的變化來揭示數(shù)據(jù)集潛在的簇結(jié)構(gòu),因此可用以下公式來確定算法的參數(shù)Δ:其中,ε(ε>0)是給定的一個具有很小的數(shù)值的算法參數(shù),用于控制計算Q序列的精度.顯然,ε越小,COPS在每個維度上的搜索步數(shù)(即每個維度被分割成的用于計算的區(qū)間數(shù))就越多,因而也就擴大了算法搜索數(shù)據(jù)集最優(yōu)劃分的搜索空間,其結(jié)果也就越有可能是最優(yōu)的結(jié)果.另一方面,ε越小,將使得算法的時間開銷越大,因而需要在這兩者之間取一個平衡點.經(jīng)過實驗環(huán)節(jié)的反復驗證,我們設定ε=0.01.1.3編碼長度的生成|C*|是候選的聚類數(shù)k*,但由于噪聲的影響,k*=|C*|并不完全成立.在COPS中,噪聲數(shù)據(jù)點也是C*的組成部份,其特點是這些子集所包含的數(shù)據(jù)點數(shù)目較少.設|C*|>2,過程θ采用基于MDL(minimaldescriptionlength)的剪枝方法識別出C*中“有意義”的子集.MDL的基本思想是,對輸入的數(shù)據(jù)進行編碼,進而選擇具有最短編碼長度的編碼方案.在COPS中,其輸入的數(shù)據(jù)是各個子集包含的數(shù)據(jù)點數(shù)目,簇的重要性由其包含數(shù)據(jù)點的數(shù)目來決定.令C*={C1*,C2*,...,Ck*},|iC*|為iC*包含的數(shù)據(jù)點數(shù)目.首先按照|iC*|從大到小排序生成一個新的序列C1C2,…,Ck;然后將這個序列以Cp(1<p<k)為界分為兩個部分:SL(p)={C1,C2,…,Cp}和SR(p)={Cp+1,Cp+2,…,Ck},求得數(shù)據(jù)的編碼長度CL(p).CL(p)的定義為其中,.上式的第1項和第3項分別表示以p為界的兩個序列的平均編碼長度;其余兩項衡量|Cj|與平均數(shù)據(jù)點數(shù)之間的差異.實際計算中若出現(xiàn)或而使得log函數(shù)沒有定義,則直接忽略該子集,即設定此時的差異為0bit.最短的編碼長度CL(p)對應的分割位置p被看作數(shù)據(jù)序列的最優(yōu)分割點,根據(jù)MDL(minimaldescriptionlength)剪枝方法的思想,此時SL(p)所包含的數(shù)據(jù)點可以認為代表了對DB的覆蓋.在COPS中,SR(p)所包含的數(shù)據(jù)點就識別為噪聲.至此,我們得到了數(shù)據(jù)集的最佳聚類數(shù),k*=p.1.4快速排序算法最壞情況下,COPS的空間復雜度為O(n2),實際中采用以下策略降低算法的空間使用量:對任意兩個不相似的數(shù)據(jù)點Xi和Xj,若Xi和Xj至少在一個維度上是相似的,則通過一個hash函數(shù)映射到一個線性表中的單元HASH(i,j),HASH(i,j)記錄Xi和Xj的維度相似情況.算法開始時,該表的所有單元為空(未被使用),隨著T的增大一些點對變得相似時,其映射在線性表中的單元亦被釋放,從而有效降低了算法的實際空間占有量.采用快速排序(quicksort)方法對數(shù)據(jù)點進行排序的時間復雜度為O(dnlogn).生成Q序列部分算法的時間復雜度為,其中,為外層循環(huán)的執(zhí)行次數(shù),是一個與n無關的量,在數(shù)值上,.這是因為隨著T的增大,越來越多的點變得相似,k在內(nèi)層循環(huán)中將迅速減少,其數(shù)值只與數(shù)據(jù)點的分布和ε的取值有關;是數(shù)據(jù)點在Δ鄰域內(nèi)的平均相似點數(shù)目,在數(shù)值上,它也只與數(shù)據(jù)點分布和ε有關.計算初始值Q(Cn)的復雜度為O(dn)(參見第2.3節(jié)分析),MDL剪枝方法的復雜度為O(k2).綜上,COPS的時間復雜度為O(dnlogn).2qc計算中心數(shù)據(jù)集幾何結(jié)構(gòu).其聚類分析方法.其cCOPS用有效性指標Q(C)評估DB被劃分為C時的聚類質(zhì)量.本節(jié)提出的指標Q(C)主要考慮數(shù)據(jù)集的幾何結(jié)構(gòu),即通過衡量簇內(nèi)數(shù)據(jù)點分布的緊湊度以及簇間的分離度,并保持二者之間的平衡.Q(C)不依賴于具體的聚類算法.2.1scat和sep設||X-Y||表示點X和Y之間的歐氏距離,給定DB的一個劃分Ck={C1,C2,…,Ck},Scat(Ck)衡量Ck的簇內(nèi)緊湊度,Sep(Ck)對應Ck的簇間分離度.具體地,以上兩式的定義原理如下:Scat是簇內(nèi)任意兩個數(shù)據(jù)點之間距離的平方和;Sep的原理是將每個簇看作是一個大“數(shù)據(jù)點”,大“數(shù)據(jù)點”間的“距離”通過簇間點對的平均距離來衡量.這樣,Scat和Sep保持了度量上的一致性.另一方面,Scat和Sep基于“點對”的平均距離定義,可用于度量非凸形簇結(jié)構(gòu)的聚類質(zhì)量.傳統(tǒng)的基于幾何結(jié)構(gòu)的聚類有效性指標(如Vxie)通?；诖刭|(zhì)心(centroids)使用簇的平均半徑和質(zhì)心之間的距離來定義Scat和Sep,這樣的指標往往只對球(超球)形的簇結(jié)構(gòu)有效.代入歐氏距離公式再做簡單的變換,Scat(Ck)和Sep(Ck)可分別表示為其中,.直觀上,Scat的值越小,表明簇越緊湊;Sep的值越大,表明簇間的分離性越好.在下式中使用線性組合平衡二者,β(β>0)為組合參數(shù),用于平衡Scat和Sep取值范圍上的差異:這里將數(shù)據(jù)集的劃分C看作一個變量,其定義域為{C1,C2,…,Cn}.根據(jù)定理1可以推定β=1.定理1.給定數(shù)據(jù)集DB,Scat(C)和Sep(C)具有相同的值域范圍.證明:在初始狀態(tài)k=n,Cn={{X1},{X2},…,{Xn}},由公式(1)可知Scat(Cn)=0;根據(jù)公式(2)有設在某個步驟Cu和Cv(u,v∈[1,k],u≠v,k>1)合并:因此,Scat(C)是單調(diào)遞增函數(shù),而Sep(C)為單調(diào)遞減函數(shù).當k=1時,C1={{X1,X2,…,Xn}},容易求得Sep(C1)=0和Scat(C1)=M.□根據(jù)定理1,COPS使用的聚類有效性指標函數(shù)Q(C)取以下形式:2.2qc極小值的計算最優(yōu)的聚類質(zhì)量對應于簇內(nèi)緊湊度和簇間分離度的平衡點,在數(shù)值上反映為指標函數(shù)Q(C)取得最小值.定理2表明,對于大多數(shù)(一種特例除外,見定理條件)數(shù)據(jù)集Q(C)存在(0,1)區(qū)間的最小值.定理2.給定數(shù)據(jù)集DB={X1,X2,…,Xn},若n>2且至少存在一個i∈[2,n-1]使得‖Xi-1-Xi‖≠‖Xi-Xi+1‖,則Q(C)存在小于1的極小值.證明:考慮在COPS的初始狀態(tài)k=n,Cn={{X1},{X2},…,{Xn}}.令tj=minl=1,2,…,n-1{xlj-x(l+1)j},j=1,2,…,d,若滿足定理條件,根據(jù)定義1,?u,v∈[1,n],u≠v,使得Xu和Xv是相似的,且(Xi-1,Xi)和(Xi,Xi+1)中至少有1對是不相似的,后者確保對所有相似點做合并處理后k>1.考慮點Xu和Xv合并后Q的變化,根據(jù)公式(3)~公式(6)有定理1已經(jīng)證明Q(C1)=Q(Cn)=1,這意味著若滿足定理條件,則Q(C)存在小于1的極小值.□定理2給出了Q(C)無法取得(0,1)區(qū)間極小值的一種特殊結(jié)構(gòu)的數(shù)據(jù)集,其直觀情形是所有數(shù)據(jù)點均勻地分布在空間等分網(wǎng)格的節(jié)點上.對這樣的數(shù)據(jù)集,COPS將輸出k*=n.這是合理的,因為此時,合理的k*取值為1或n,而聚類算法通常要求k*>1.2.3聚類分析方法根據(jù)公式(3)~公式(6)可以進行Q(Ck)的增量計算(UpdateQ過程)為了得到Q(Ck),只需在Q(Ck+1)的基礎上使用公式(4)和公式(5)計算其增量即可.為此,在算法中為每個Ci(i=1,2,…,k)保存一個結(jié)構(gòu):這正是BIRCH算法提出的聚類特征(clusteringfeature).基于此合并數(shù)據(jù)集劃分的操作(MergePartitions過程)可以轉(zhuǎn)化成為相應的|Ci|,SSij和LSij數(shù)值之間簡單的加法運算.在計算初始值M時,需獲得每個數(shù)據(jù)點的CF結(jié)構(gòu),再按照公式(3)計算,其時間復雜度為O(dn).一條典型的Q(C)曲線例子如圖5所示.圖中,在最小值之后Q值出現(xiàn)大幅跳變,這意味著若合并最優(yōu)劃分的一些子集將使得聚類質(zhì)量急劇下降.利用這個特點,此時加大T的增量Δ可以進一步提高COPS的性能.具體地,當數(shù)據(jù)集較大時(比如n>1000),計算過程中若Q大于已出現(xiàn)的最小值我們設定ε=ε×2.3算法的穩(wěn)定性實驗驗證包括算法有效性和算法效率兩方面.在眾多的聚類有效性指標[6,7,8,9,10,11,12,13]里,選用基于幾何結(jié)構(gòu)的Vxie和Vwsj這兩種有代表意義的指標作為對比對象,其中,Vxie是首個采用“緊湊度”和“分離度”概念的經(jīng)典指標;Vwsj改進了線性組合方法的穩(wěn)定性,可以有效地處理包含有重疊的簇和噪聲的數(shù)據(jù)集.兩種指標都基于FCM算法,實驗設定FCM算法的模糊因子w=2.在其他類型方法中,選用Gapstatistic和IGP作比較.Gapstatistic的特點是通過檢測聚類質(zhì)量的“突變(dramaticchange)”確定最佳的k值;IGP是新近提出的一個指標,使用ingroup比例衡量聚類的質(zhì)量,其性能已被驗證優(yōu)于現(xiàn)有的其他統(tǒng)計指標.根據(jù)文獻的建議,使用k-means作為它們的基本算法,取參數(shù)R=5;IGP使用的Cutoff閾值設置為0.90.使用Greedy技術(shù)選擇FCM/k-means的初始簇中心點以提高算法的收斂速度.實驗在CPU2.6GHz,RAM512MB的計算機上進行,操作系統(tǒng)為MicrosoftWindows2000.3.1基于fcm或k-meas算法的復雜形狀簇實驗分別采用了真實數(shù)據(jù)和人工合成數(shù)據(jù).以下報告6個有代表性的數(shù)據(jù)集上的實驗結(jié)果,數(shù)據(jù)集的參數(shù)匯總見表1.為比較起見,選取的前2個數(shù)據(jù)集DS1和DS2是常被類似研究引用的真實數(shù)據(jù)X30和IRIS數(shù)據(jù)為測試各種方法處理大型數(shù)據(jù)集的性能,根據(jù)文獻提供的方法(在原方法基礎上改進為隨機簇中心)合成了含4000個數(shù)據(jù)點的3維數(shù)據(jù)集DS5.DS5同時還包含少量的噪聲,這些噪聲模糊了簇的邊界,其中兩個簇存在明顯的重疊.第6個數(shù)據(jù)集DS6包含有8000個數(shù)據(jù)點,是命名為“t5.8k”的公用數(shù)據(jù)集,其特點是包含有大量的噪聲和復雜形狀的簇(其6個簇呈‘GEOAGE’字母形狀).更為重要的是,我們通過實驗發(fā)現(xiàn),在適當?shù)膮?shù)配置下,即指定了正確的聚類數(shù),FCM和k-means算法可以很好地區(qū)分出這6個簇.以此驗證基于FCM或k-means算法的其他4種方法以及COPS識別復雜形狀簇的性能.3.2復雜數(shù)據(jù)集的聚類結(jié)果COPS在6個數(shù)據(jù)集上都得到了正確的聚類數(shù),實驗結(jié)果如圖6所示.對DS1和DS2,COPS檢測出在聚類數(shù)從最優(yōu)數(shù)目3變?yōu)?時聚類質(zhì)量大幅度下降.DS2包含有兩個重疊的簇,圖6(b)表明,COPS能夠有效區(qū)分重疊的簇.受噪聲影響,DS5中有兩個邊界模糊的簇,圖6(e)顯示,對應于聚類數(shù)6和5的聚類質(zhì)量只存在很小的差異,盡管如此,COPS還是完成了準確的區(qū)分,得到最優(yōu)聚類數(shù)6,這說明COPS可以有效地識別噪聲并區(qū)分簇間的密度差異.對DS3~DS6這4個較為復雜的數(shù)據(jù),COPS沒有檢測到連續(xù)變化的k值,例如在圖6(f)中,k從18跳變到最優(yōu)數(shù)6.這是因為COPS采用了與其他方法不同的做法,它不是通過設定一個k的區(qū)間反復運行聚類算法來計算和比較不同的聚類結(jié)果,而是在層次式的簇合并過程中計算不同劃分的質(zhì)量,合并過程中產(chǎn)生的簇的數(shù)目取決于數(shù)據(jù)集本身的結(jié)構(gòu),這正是COPS在識別復雜形狀簇方面的優(yōu)勢.不同方法的實驗結(jié)果對比見表2.實驗中為Vxie和Vwsj設置的k值范圍是,對Gap和IGP設置為文獻建議設定,根據(jù)本文測試數(shù)據(jù)集的大小則會得到很大的kmax值,因而作了以上統(tǒng)一的設置.由于FCM/k-means算法的聚類結(jié)果容易受初始簇中心的影響,根據(jù)Greedy技術(shù)的原理,其第1個初始簇中心是隨機選擇的,使得它們在復雜數(shù)據(jù)集上產(chǎn)生不確定的結(jié)果;Gapstatistic使用的隨機空分布數(shù)據(jù)(不含簇結(jié)構(gòu))和IGP使用的隨機數(shù)據(jù)抽樣是另一個因素.表2列出了它們在多次實驗中最接近真實聚類數(shù)的結(jié)果.作為對比COPS使用的Q(C)指標獨立于具體的聚類算法,它在由數(shù)據(jù)集幾何結(jié)構(gòu)所確定的層次聚類樹上搜索最優(yōu)的劃分,由此得到的結(jié)果具有確定性的特點.從表2可以看出,對于3個簇明顯分離的簡單數(shù)據(jù)集DS1,所有方法都得到了正確的最優(yōu)聚類數(shù)3.對于DS2只有COPS,Vwsj和IGP得到正確的結(jié)果,這在一定程度上驗證了Vwsj和IGP能夠正確處理重疊簇的能力.然而在DS6上,只有COPS得到正確的結(jié)果.需要指出的是,FCM/k-means算法在設置k=6時可以對DS6的6個簇進行較好的區(qū)分,但4種對比方法均未能正確地計算,說明這些方法在識別非凸形簇方面存在缺陷.Gapstatistic需要隨機生成的空分布數(shù)據(jù)作為對比以檢測聚類質(zhì)量存在跳變的k值,在多次嘗試后我們沒有得到更好的結(jié)果.實際上,除DS1外,Gapstatistic都返回錯誤的簇數(shù)目,這是由于Gapstatistic只適合于處理簇間明顯分離的數(shù)據(jù)集.表2顯示IGP具有較好的性能,但在DS3和DS6上得到錯誤