第七章模糊聚類的有效性

第七章模糊聚類的有效性第七章模糊聚類的有效性#空間維數(shù)卩=4.00.560.910.940.960.98卩=32.00.920.940.970.980.98空間維數(shù)卩=4.00.560.910.940.960.98卩=32.00.920.940.970.980.98表7.4.3和7.4.4的數(shù)據(jù)表明，在半數(shù)框架制約下統(tǒng)計(jì)量T對多峰模式集可以建立較高的B功效檢驗(yàn)，也就是說可以較好的區(qū)分單峰和多峰模式。另外，對于固定點(diǎn)數(shù)n的集合，聚類趨勢檢驗(yàn)的效隨著d和卩的增加而變大，隨著◎的增加而變小，這是因?yàn)楫?dāng)n固定，空間維數(shù)越高，類間相對距離就越大，聚類趨勢變顯著，而卩的增加意味著類內(nèi)點(diǎn)數(shù)增加，聚類的個(gè)數(shù)減少，換句話說，類間趨向于良好分開?！蚴穷悆?nèi)分散程度的標(biāo)志，◎變大說明類與類間越來越可能交叉重迭，以致于聚類現(xiàn)象完全消失，因而效的變小就是自然的。因?yàn)榫垲惙治鐾ǔＪ窃诟呔S空間中進(jìn)行的，所以，效隨空間維數(shù)增加而變大的性質(zhì)對于聚類趨勢的檢驗(yàn)有利。因?yàn)榫垲愙厔輽z驗(yàn)的任務(wù)在于把那些不具有聚類結(jié)構(gòu)的數(shù)據(jù)集除去，所以效隨◎增加而變小的性質(zhì)亦是我們所需要的。表7.4.4在d=5條件下對多峰模式的功效檢驗(yàn)0.00.0250.050.0750.100.00.0250.050.0750.100.1250.15卩=4.01.00.980?960.950.910.740.45卩=32.01.00.980.960.950.92卩=32.0綜上所述，半數(shù)框架制約下的T-平方統(tǒng)計(jì)量檢驗(yàn)對于空間均勻分布的模式可以建立可信的檢驗(yàn)基礎(chǔ)，而對于單一Gauss模式的極低功效檢驗(yàn)，使得關(guān)于隨機(jī)模式的概念在聚類趨勢檢驗(yàn)的意義上可以溶均勻分布模式和Gauss模式于一體，從而拓寬了零假設(shè)的范圍。同時(shí)，該方法對多峰模式極高的功效檢驗(yàn)又使其完全可以用于聚類趨勢的檢驗(yàn)中。半數(shù)框架的應(yīng)用，使關(guān)于模式可聚性檢驗(yàn)，既避開了抽樣始點(diǎn)設(shè)置對抽樣窗口的要求，也消除了由于窗口設(shè)置而造成的邊界對近鄰距離分布規(guī)律的影響，因而是一個(gè)很有前途的方法。§4.4基于MonteCarlo和統(tǒng)計(jì)檢驗(yàn)的模糊聚類新方法三、基于MonteCarlo和統(tǒng)計(jì)檢驗(yàn)的模糊聚類新方法聚類分析是無監(jiān)督的類分技術(shù)，事先沒有任何有關(guān)數(shù)據(jù)集的先驗(yàn)知識，包括它的分布和類別數(shù)，因此應(yīng)該是一種機(jī)器自動(dòng)學(xué)習(xí)方法。通過對數(shù)據(jù)分布特性的分析，自動(dòng)給出模式集是否具有類分性，如果可分，自動(dòng)確定如何分類以及分為幾類合適等問題。把多峰分布模式的數(shù)據(jù)集全部分解成單峰分布的模式類，最后根據(jù)類間的相近信息進(jìn)行模式類的合并，獲得數(shù)據(jù)集的多分辨表示，為用戶提供多層次的信息，以幫助決策。由前一節(jié)的分析可知結(jié)合半數(shù)框架的T-平方抽樣的統(tǒng)計(jì)量T,可有效的進(jìn)行單峰模式的B假設(shè)檢驗(yàn)。因此，本節(jié)中我們將用該統(tǒng)計(jì)檢驗(yàn)方法進(jìn)行聚類趨勢和聚類有效性的判定，即分別對模式集X和聚類分析得到的各個(gè)模式子集S(i二1,2,…c)進(jìn)行單峰檢驗(yàn)，以此來指導(dǎo)聚i類分析，構(gòu)造一種可同時(shí)進(jìn)行聚類趨勢檢驗(yàn)、聚類分析和聚類有效性判定的模式綜合分析自動(dòng)機(jī)，如圖7.4.8所示，以補(bǔ)償現(xiàn)有聚類算法的功能單一所導(dǎo)致的無效操作。以下，分別介紹各模塊的工作原理及相關(guān)的算法。合理分類輸出合理分類輸出圖7.4.8結(jié)合聚類趨勢、聚類分析和有效性判定的模式分析自動(dòng)機(jī)1.基于k-近鄰T-平方統(tǒng)計(jì)量T的單峰檢驗(yàn)k對于一個(gè)給定的無標(biāo)定模式集，如圖7.4.8給出的模式分析自動(dòng)機(jī)首先進(jìn)行單峰分布的統(tǒng)計(jì)檢驗(yàn)，以確定該模式集是否具有類分性，即聚類趨勢檢驗(yàn)。這里借用前面介紹的半數(shù)框架下的T-平方統(tǒng)計(jì)檢驗(yàn)方法，統(tǒng)計(jì)量T的假設(shè)檢驗(yàn)基于抽樣點(diǎn)與模式間的最近鄰(NN)信息，B不過，NN模式的選取存在隨機(jī)性太強(qiáng)而統(tǒng)計(jì)性較差的問題。為了抽取魯棒性較好的檢驗(yàn)統(tǒng)計(jì)量，我們把NN模式間的距離替換為k-NN模式間的距離，把尋找最近鄰模式轉(zhuǎn)化為尋找k個(gè)近鄰模式集，大大降低了模式出現(xiàn)的隨機(jī)性，從而使所得到的統(tǒng)計(jì)量更穩(wěn)定。這樣以來，統(tǒng)計(jì)量T就被推廣為k-NN的統(tǒng)計(jì)量T，Bk1券Ud(i)T=——Zk(7104)TOC\o"1-5"\h\zkMUd(i)+0.5Vd(i)'?丿i=1kk其中U(i)為抽樣始點(diǎn)O到它的k-NN模式P的距離，而V(i)則為模式P與其k-NN模式Pk1k12間的距離。顯然，統(tǒng)計(jì)量T為統(tǒng)計(jì)量T在k=1時(shí)的特例。仍借助前一節(jié)介紹的半數(shù)框架建Bk立抽樣窗口，還利用MonteCarlo的方法進(jìn)行*-顯著性檢驗(yàn)，這兩個(gè)算法在此不在贅述。在對給定的無標(biāo)定模式集進(jìn)行*-顯著性檢驗(yàn)后，獲得檢驗(yàn)大小Size,然后按如下規(guī)則作出判決：如果Size與*相比擬，則模式集為單峰模式，否則，模式集有聚類趨勢。2．聚類有效性判定方法在獲知模式集X具有可分性后，首先令c=2，用現(xiàn)有的聚類算法(如FCM算法)獲得X的c-劃分。這里要求算法要收斂到最優(yōu)解，否則將影響后續(xù)工作。而FCM類型的的聚類算法對初始化敏感，容易陷入局部極值點(diǎn)而得不到最優(yōu)的分類結(jié)果。為此，我們可以利用第

三章中給出的基于形態(tài)學(xué)和圖象描述技術(shù)的初始化方法來保證全局收斂，或者借助進(jìn)化計(jì)算的方法進(jìn)行全局優(yōu)化。具體哪種方法可根據(jù)實(shí)際需要合理選取。得到模式集X在給定聚類數(shù)c條件下的最佳模式劃分后，對c個(gè)子集S,S,,S分別12c做單峰分布的Q-顯著性檢驗(yàn)，只要還有一個(gè)子集不滿足顯著性檢驗(yàn)，則說明仍存在可分性，???令c=c+1重新聚類劃分，直到所有c個(gè)子集均不具有類可分性后，則說明數(shù)據(jù)集X分布的峰態(tài)已經(jīng)分解完全，每個(gè)聚類均為單峰分布模式了，則轉(zhuǎn)入聚類后處理。3．聚類分析的后處理后處理主要是考慮到聚類的無監(jiān)督性，為了滿足不同的應(yīng)用場合，為后續(xù)決策提供更多的信息，利用最小生成樹技術(shù)進(jìn)行聚類合并，然后給出一個(gè)不同水平上類分的譜系圖，也就是說給出特征空間中模式矢量集的多分辨表示。當(dāng)然最細(xì)微層次上的聚類即為上面得到的數(shù)據(jù)集X完全分解的結(jié)果，最粗略的層次上的聚類為整個(gè)模式集X聚合為一類。數(shù)據(jù)集的類分譜系圖的建立要按如下步驟進(jìn)行：(1)(2)在聚類分析中獲得的c個(gè)聚類中心P=｛p,p,,p｝上構(gòu)造最小生成樹，其邊的(1)(2)12c權(quán)值即為節(jié)點(diǎn)間的歐氏距離w=lip-pI；ijij分析最小生成樹的權(quán)值｛w..｝，逐步在不同水平丫上刪除滿足條件的邊集ijwewe'wijw＜丫丿，合并每條邊連接的兩個(gè)類；ij(3)構(gòu)造新的最小生成樹，重復(fù)步驟(2)的操作，直至合并成一個(gè)類，最后輸出類分譜系(3)圖。整個(gè)模式分析自動(dòng)機(jī)就包括上述三大模塊，即數(shù)據(jù)集的單峰模式檢驗(yàn)、數(shù)據(jù)子集單峰模式檢驗(yàn)指導(dǎo)的聚類分析和聚類后處理，可同時(shí)考察給定模式集的聚類趨勢、聚類分析的有效性，并由此指導(dǎo)聚類算法把數(shù)據(jù)集完全分解為單峰分布的子集，最后通過后處理獲得數(shù)據(jù)集的類分譜系圖。整個(gè)流程如圖4-4.1所示的框圖，輸入一組模式集，先判斷其聚類趨勢，如果可分便輸出數(shù)據(jù)集類分的譜系圖，實(shí)現(xiàn)簡單，過程自動(dòng)，避免了人為的干預(yù)，使聚類分析真正成為一種機(jī)器自動(dòng)學(xué)習(xí)算法。§4.5實(shí)驗(yàn)結(jié)果與分析四、實(shí)驗(yàn)結(jié)果分析大量的實(shí)驗(yàn)結(jié)果表明本章提出的模式分析自動(dòng)機(jī)能夠合理有效地分析所給的空間數(shù)據(jù)集，并為后續(xù)工作提供不同層次的類分信息，使人們更清楚地認(rèn)識待分析模式間的親疏關(guān)系、分布形態(tài)和內(nèi)在結(jié)構(gòu)，整個(gè)過程自動(dòng)執(zhí)行，無須人為干預(yù)，為生產(chǎn)自動(dòng)化提供了條件。本節(jié)中，我們將選擇三個(gè)不同類型的實(shí)驗(yàn)結(jié)果來說明該方法的有效性。

00.200.20.40.60.8100.20.40.60.81(a)空間均勻分布的測試樣本集(b)半數(shù)框架制約下的T-平方抽樣圖7.4.9用本章方法對空間均勻分布模式集的統(tǒng)計(jì)檢驗(yàn)實(shí)驗(yàn)實(shí)驗(yàn)一：為了說明半數(shù)框架制約下T-平方統(tǒng)計(jì)量能夠?qū)臻g均勻分布的模式集建立可信的檢驗(yàn)，我們用空間Poisson過程產(chǎn)生如圖7.4.9(a)所示的均勻分布的樣本集，用半數(shù)框架算法設(shè)置如圖7.4.9(b沖所示的抽樣窗口(在圖中用大圓表示)，在抽樣域內(nèi)設(shè)置M=10個(gè)抽樣始點(diǎn)O(在圖中用“?”表示)并按T-平方抽樣原理得到最近鄰模式匚,P2(圖中分別用疊加在“X”上的“O”和“△”表示)，然后按公式計(jì)算統(tǒng)計(jì)量T，對以上的MonteCarlo試驗(yàn)重復(fù)100B次獲得如圖7.4.10的統(tǒng)計(jì)數(shù)據(jù)。(a)MonteCarlo試驗(yàn)得到的統(tǒng)計(jì)量的值(b)試驗(yàn)中統(tǒng)計(jì)量取值的統(tǒng)計(jì)直方圖圖7.4.10100次MonteCarlo試驗(yàn)所得到的T-平方統(tǒng)計(jì)量的統(tǒng)計(jì)數(shù)據(jù)圖7.4.10(a)所示為100次MonteCarlo試驗(yàn)中所得到的T-平方統(tǒng)計(jì)量的值，如果取顯著性水平0.05，則從標(biāo)準(zhǔn)正態(tài)分布函數(shù)可得臨界值T二1.64484，從圖中可很明顯地看出大a于T的試驗(yàn)只有4次，因此檢驗(yàn)大小為Size二0.04獲得了合理的第一類錯(cuò)誤概率的估計(jì)。圖a(b)顯示了100試驗(yàn)中T-平方統(tǒng)計(jì)量的統(tǒng)計(jì)直方圖，其中虛線為標(biāo)準(zhǔn)正態(tài)分布曲線，可見在空間Poisson過程的條件下，T-平方統(tǒng)計(jì)量良好的遵循正態(tài)分布。實(shí)驗(yàn)結(jié)果與前面的理論分析獲得了較好的一致性，也證實(shí)了方法的有效性。

(a)c=2時(shí)IRIS(a)c=2時(shí)IRIS數(shù)據(jù)的分類情況(b)c=3時(shí)IRIS數(shù)據(jù)的分類情況圖7.4.11用實(shí)測數(shù)據(jù)的測試實(shí)驗(yàn)(圖中顯示的IRIS數(shù)據(jù)的1,2,4維特征)實(shí)驗(yàn)二：為了驗(yàn)證本章提出的單峰統(tǒng)計(jì)檢驗(yàn)方法的有效性，我們選擇了著名的IRIS實(shí)測數(shù)據(jù)作為測試樣本，關(guān)于IRIS數(shù)據(jù)的情況在第二章中有詳細(xì)說明，它包括三類共150個(gè)四維模式，每類50個(gè)樣本，其樣本分布情況如圖7.4.11所示。用本章提出的模式分析自動(dòng)機(jī)對類別數(shù)為c=1,2,3的條件下，分別進(jìn)行Q=0.05,0.01的顯著性檢驗(yàn)，得到表7.4.5的結(jié)果。表7.4.5IRIS實(shí)測數(shù)據(jù)集的a-顯著性檢驗(yàn)的檢驗(yàn)大小類別數(shù)c類別數(shù)c12a二0.050.78(0.03,0.57)a二0.010.59(0.02,0.44)3(0.03,0.05,0.07)(0.02,0.02,0.03)從表中可以看出，IRIS數(shù)據(jù)集具有明顯的聚類趨勢，于是令c=2用FCM算法進(jìn)行數(shù)據(jù)劃分，去模糊后得到圖7.4.11(a)所示的分類結(jié)果，對得到的兩類子集分別進(jìn)行單峰檢驗(yàn)后得知,有一個(gè)子集已經(jīng)為單峰模式了，但另一個(gè)子集仍具有聚類趨勢，然后令c=3再用FCM算法劃分，劃分的結(jié)果顯示在圖7.4.11(b)中，對每個(gè)子集的檢驗(yàn)結(jié)果表明，三個(gè)子集均無聚類趨勢,因此算法結(jié)束，最終得到合理的分類數(shù)(c=3)和分類結(jié)果。實(shí)驗(yàn)三：為了證實(shí)本章提出的模式分析自動(dòng)機(jī)全面分析模式、提供多層次輔助決策信息的能力，我們用模擬數(shù)據(jù)設(shè)計(jì)了實(shí)驗(yàn)三。.X(a)二維空間中人造測試樣本集(b)峰態(tài)分解完全后所得到分類結(jié)果0

.X(a)二維空間中人造測試樣本集(b)峰態(tài)分解完全后所得到分類結(jié)果0圖7.4.12用人造測試樣本集對模式分析自動(dòng)機(jī)的測試實(shí)驗(yàn)圖7.4.12(a)所示為一組仿真數(shù)據(jù)集，包含二維平面上的300個(gè)模式，模式分析自動(dòng)機(jī)對這組數(shù)據(jù)的分析表明：該數(shù)據(jù)集具有聚類趨勢，因?yàn)槠鋯畏錫-顯著性檢驗(yàn)的大小遠(yuǎn)大于d(實(shí)驗(yàn)中取a=0.05)。于是，算法從c=2開始進(jìn)行聚類分析，并對所得到的每個(gè)聚類分別進(jìn)行單峰檢驗(yàn)，不滿足檢驗(yàn)則令c=c+1重新聚類，直到c=6時(shí)，所得到的子集才全部通過a-顯著性檢驗(yàn)，分類結(jié)果如圖7.4.12(b)所示，此時(shí)各個(gè)聚類皆為單峰分布的子集。表7.4.6在不同參數(shù)c,k條件下各子集統(tǒng)計(jì)檢驗(yàn)中最大的第一類錯(cuò)誤聚類數(shù)c1234561999747948992100655910099531008181991009410010010010010005100961001001002表7.4.6給出了不同分類數(shù)c和不同k值條件下,各個(gè)聚類進(jìn)行T統(tǒng)計(jì)檢驗(yàn)中得到的第一類錯(cuò)誤的最大值，即為最大檢驗(yàn)大小maxc《ize(S)},其中M=10，k取1到5。不同ki=1i值的T統(tǒng)計(jì)檢驗(yàn)結(jié)果均表明：直到c取6時(shí)各類才均滿足a-顯著性檢驗(yàn)，而對應(yīng)于不同k值k的檢驗(yàn)大小又反映出在k=1時(shí)，即統(tǒng)計(jì)量T的檢驗(yàn)大小不很穩(wěn)定，k=4時(shí)則較為理想。因B此，選擇適當(dāng)?shù)膋值，則更有利于模式分析的效果。得到樣本集的c-劃分后，模式分析自動(dòng)機(jī)進(jìn)行聚類的后處理，在不同水平上合并聚類,以輸出樣本類分的譜系圖。首先，以所得到的六個(gè)聚類中心為節(jié)點(diǎn)，構(gòu)造圖7.4.13(a)所示的最小生成樹，其中邊權(quán)值為節(jié)點(diǎn)間的距離，節(jié)點(diǎn)上的數(shù)值1-6表示聚類的序號，