模糊聚類分析課件

第七講

模糊聚類分析1第七講

模糊聚類分析17.1聚類分析的基本概念“聚類”就是按照一定的要求和規(guī)律對(duì)事物進(jìn)行區(qū)分和分類的過程,在這一過程中沒有任何關(guān)于分類的先驗(yàn)知識(shí),僅靠事物間的相似性作為類屬劃分的準(zhǔn)則,屬于無監(jiān)督分類的范疇。“聚類分析”是指用數(shù)學(xué)的方法研究和處理給定對(duì)象的分類。27.1聚類分析的基本概念“聚類”就是按照一定的要求和聚類分析是多元統(tǒng)計(jì)分析的一種,它把一個(gè)沒有類別標(biāo)記的樣本集按某種準(zhǔn)則劃分成若干個(gè)子集(類),使相似的樣本盡可能歸為一類,而不相似的樣本盡量劃分到不同的類中。傳統(tǒng)的聚類分析是一種硬劃分,它把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某類中,具有非此即彼的性質(zhì),因此這種類別劃分的界限是分明的。而實(shí)際上大多數(shù)對(duì)象并沒有嚴(yán)格的屬性,它們?cè)谛詰B(tài)和類屬方面存在著中介性,具有亦此亦彼的性質(zhì),因此適合進(jìn)行軟劃分。3聚類分析是多元統(tǒng)計(jì)分析的一種,它把一個(gè)沒有類別標(biāo)記的樣本集模糊集理論的提出為軟劃分提供了有力的分析工具,用模糊數(shù)學(xué)的方法來處理聚類問題,被稱之為模糊聚類分析。由于模糊聚類得到了樣本屬于各個(gè)類別的不確定性程度,表達(dá)了樣本類屬的中介性,更能客觀地反映現(xiàn)實(shí)世界,從而成為聚類分析研究的主流。模糊聚類已經(jīng)在諸多領(lǐng)域獲得了廣泛的應(yīng)用,如模式識(shí)別、圖像處理、信道均衡、矢量量化編碼、神經(jīng)網(wǎng)絡(luò)的訓(xùn)練、參數(shù)估計(jì)、醫(yī)學(xué)診斷、天氣預(yù)報(bào)、食品分類、水質(zhì)分析等。4模糊集理論的提出為軟劃分提供了有力的分析工具,用模糊數(shù)學(xué)的常用的模糊聚類分析方法大致可分為兩大類：其一是基于模糊關(guān)系(矩陣)的聚類分析方法,而作為其中核心步驟的模糊分類,有下述的主要方法：模糊傳遞閉包法、直接聚類法、最大樹法和編網(wǎng)法;其二是基于目標(biāo)函數(shù)的聚類分析方法,稱為模糊C均值(FCM)聚類算法(或稱為模糊ISODATA聚類分析法)。第一類方法,作為準(zhǔn)備先講解模糊關(guān)系傳遞閉包的基本概念。5常用的模糊聚類分析方法大致可分為兩大類：其一是基于模糊關(guān)系(7.2模糊關(guān)系的傳遞閉包設(shè)RF(XX).則R是模糊等價(jià)關(guān)系當(dāng)且僅當(dāng)對(duì)任意[0,1],R是等價(jià)關(guān)系。論域X上的經(jīng)典等價(jià)關(guān)系可以導(dǎo)出X的一個(gè)分類。論域X上的一個(gè)模糊等價(jià)關(guān)系R對(duì)應(yīng)一族經(jīng)典等價(jià)關(guān)系{R:[0,1]}.這說明模糊等價(jià)關(guān)系給出X的一個(gè)分類的系列。這樣,在實(shí)際應(yīng)用問題中可以選擇“某個(gè)水平”上的分類結(jié)果,這就是模糊聚類分析的理論基礎(chǔ)。實(shí)際問題中建立的模糊關(guān)系常常不是等價(jià)關(guān)系而是相似關(guān)系,這就需要將模糊相似關(guān)系改造為模糊等價(jià)關(guān)系,傳遞閉包正是這樣一種工具。67.2模糊關(guān)系的傳遞閉包設(shè)RF(XX).則R是定義設(shè)RF(XX).若R1F(XX)是傳遞的且滿足：1)RR1,2)若S是X上的模糊傳遞關(guān)系且RS,必有R1S.

則稱R1為R的傳遞閉包,記為t(R).

模糊關(guān)系R的傳遞閉包是包含R的最小傳遞關(guān)系。定理設(shè)RF(XX).則t(R)=∪n=1Rn.7定義設(shè)RF(XX).若R1F(XX)是傳遞的且滿(∪n=1Rn)(∪m=1Rm)=∪n=1[Rn(∪m=1Rm)]=∪n=1[∪m=1(Rn

Rm)]=∪k=2(∪n+m=k

Rn+m)=∪k=2Rk∪k=1Rk.這說明∪n=1Rn是傳遞的。又,顯然R∪n=1Rn.即∪n=1Rn是包含R的模糊傳遞關(guān)系。若有X上的模糊傳遞關(guān)系S滿足RS,下證∪n=1Rn

S(即證明∪n=1Rn

“最小”)

由RS得R2S2S,R3=R

R2R

SS2S,

…證明：8(∪n=1Rn)(∪m=1Rm)證明：8

一般地,RnS,nN.于是∪n=1Rn

S.綜上所述,∪n=1Rn是包含R的最小傳遞關(guān)系,因而是R的傳遞閉包,即t(R)=∪n=1Rn.在論域有限的情況下,傳遞閉包的計(jì)算更簡(jiǎn)捷:定理設(shè)|X|=n,RF(XX).則t(R)=∪k=1nRk.計(jì)算有限論域上自反模糊關(guān)系R的傳遞閉包的方法：從R出發(fā),反復(fù)自乘,依次計(jì)算出R2,R4,

…,當(dāng)?shù)谝淮纬霈F(xiàn)Rk

Rk=Rk時(shí)得t(R)=Rk.9一般地,RnS,nN.于是∪n=1Rn定理

設(shè)RF(XX).則R的傳遞閉包t(R)具有以下性質(zhì):(1)若IR,則It(R);(2)(t(R))1=t(R1);(3)若R=R1,則(t(R))1=t(R).上述結(jié)論表明：自反關(guān)系的傳遞閉包是自反的,對(duì)稱關(guān)系的傳遞閉包是對(duì)稱的。于是,模糊相似關(guān)系的傳遞閉包是模糊等價(jià)關(guān)系。例設(shè)|X|=5,R是X上的模糊關(guān)系,R可表示為如下的5×5模糊矩陣。求R的傳遞閉包。10定理設(shè)RF(XX).則R的傳遞閉包t(R)具有以下性解容易看出R是自反的對(duì)稱模糊關(guān)系(即模糊相似關(guān)系)。依次計(jì)算R2,R4,R8知:R8=R4R4=R4(參見下頁(yè)計(jì)算結(jié)果),所以R的傳遞閉包t(R)=R4.11解容易看出R是自反的對(duì)稱模糊關(guān)系(即模糊相似關(guān)系)。依12127.3基于模糊關(guān)系的聚類分析基于模糊關(guān)系的聚類分析的一般步驟:(1)數(shù)據(jù)規(guī)格化;(2)構(gòu)造模糊相似矩陣;(3)模糊分類。上述第三步又有不同的算法,以下先介紹利用模糊傳遞閉包進(jìn)行模糊分類的方法。設(shè)被分類對(duì)象的集合為X={x1,x2,,xn},每一個(gè)對(duì)象xi有m個(gè)特性指標(biāo)

(反映對(duì)象特征的主要指標(biāo)),即xi可由如下m維特性指標(biāo)向量來表示:xi=(xi1,xi1,,xim),i=1,2,,n其中xij表示第i個(gè)對(duì)象的第j個(gè)特性指標(biāo)。則n個(gè)對(duì)象的所有特性指標(biāo)構(gòu)成一個(gè)矩陣,記作X*=(xij)n×m,

稱X*為X的特性指標(biāo)矩陣。137.3基于模糊關(guān)系的聚類分析基于模糊關(guān)系的聚類分析的一般步步驟一：數(shù)據(jù)規(guī)格化由于m個(gè)特性指標(biāo)的量綱和數(shù)量級(jí)不一定相同,故在運(yùn)算過程中可能突出某數(shù)量級(jí)特別大的特性指標(biāo)對(duì)分類的作用,而降低甚至排除了某些數(shù)量級(jí)很小的特性指標(biāo)的作用。數(shù)據(jù)規(guī)格化使每一個(gè)指標(biāo)值統(tǒng)一于某種共同的數(shù)值特性范圍。14步驟一：數(shù)據(jù)規(guī)格化14數(shù)據(jù)規(guī)格化的方法有：(1)標(biāo)準(zhǔn)化方法:對(duì)特性指標(biāo)矩陣X*的第j列,計(jì)算均值和方差,然后作變換15數(shù)據(jù)規(guī)格化的方法有：15(2)均值規(guī)格化方法:對(duì)特性指標(biāo)矩陣X*的第j列,計(jì)算標(biāo)準(zhǔn)差j,然后作變換xij=xij/j,i=1,2,,n,j=1,2,,m.(3)中心規(guī)格化方法:對(duì)特性指標(biāo)矩陣X*的第j列,計(jì)算平均值xj,然后作變換xij=xijxj,i=1,2,,n,j=1,2,,m.(4)最大值規(guī)格化方法:對(duì)特性指標(biāo)矩陣X*的第j列,計(jì)算最大值Mj=max{x1j,x2j,,xnj},j=1,2,,m.然后作變換xij=xij/Mj,i=1,2,,n,j=1,2,,m.16(2)均值規(guī)格化方法:對(duì)特性指標(biāo)矩陣X*的第j列,計(jì)算步驟二：構(gòu)造模糊相似矩陣聚類是按某種標(biāo)準(zhǔn)來鑒別X中元素間的接近程度,把彼此接近的對(duì)象歸為一類。為此,用[0,1]中的數(shù)rij表示X中的元素xi與xj的接近或相似程度。經(jīng)典聚類分析中的相似系數(shù)以及模糊集之間的貼近度,都可作為相似程度(相似系數(shù))。設(shè)數(shù)據(jù)xij(i=1,2,,n,j=1,2,,m)均已規(guī)格化,xi=(xi1,xi2,,xim)與xj=(xj1,xj2,,xjm)之間的相似程度記為rij[0,1],于是得到對(duì)象之間的模糊相似矩陣R=(rij)n×n.17步驟二：構(gòu)造模糊相似矩陣17對(duì)于相似程度(相似系數(shù))的確定,有多種方法,常用的有：(1)數(shù)量積法其中M>0為適當(dāng)選擇的參數(shù)且滿足Mmax{xixj|ij}.這里,xixj為xi與xj的數(shù)量積.18對(duì)于相似程度(相似系數(shù))的確定,有多種方法,常用的有：其(2)夾角余弦法(3)相關(guān)系數(shù)法19(2)夾角余弦法(3)相關(guān)系數(shù)法19(4)貼近度法當(dāng)對(duì)象xi的特性指標(biāo)向量xi=(xi1,xi2,,xim)為模糊向量,即xik[0,1]

(i=1,2,,n;k=1,2,,m)時(shí),xi與xj的相似程度rij可看作模糊子集xi與xj的貼近度。在應(yīng)用中,常見的確定方法有：最大最小法、算術(shù)平均最小法、幾何平均最小法。20(4)貼近度法20(5)距離法利用對(duì)象xi與xj的距離也可以確定它們的相似程度rij,這是因?yàn)閐(xi,xj)越大,rij就越小。一般地,取rij

=1c(d(xi,xj)),其中c和是兩個(gè)適當(dāng)選取的正數(shù),使rij[0,1].在實(shí)際應(yīng)用中,常采用如下的距離來確定rij.21(5)距離法21(6)絕對(duì)值倒數(shù)法如右所示,其中c是適當(dāng)選取的正數(shù),使rij[0,1].22(6)絕對(duì)值倒數(shù)法22(7)主觀評(píng)定法在一些實(shí)際問題中,被分類對(duì)象的特性指標(biāo)是定性指標(biāo),即特性指標(biāo)難以用定量數(shù)值來表達(dá)。這時(shí),可請(qǐng)專家和有實(shí)際經(jīng)驗(yàn)的人員用評(píng)分的辦法來主觀評(píng)定被分類對(duì)象間的相似程度。步驟三：模糊分類由于由上述各種方法構(gòu)造出的對(duì)象與對(duì)象之間的模糊關(guān)系矩陣R=(rij)n×n,一般說來只是一個(gè)模糊相似矩陣,而不一定具有傳遞性。因此,要從R出發(fā)構(gòu)造一個(gè)新的模糊等價(jià)矩陣,然后以此模糊等價(jià)矩陣作為基礎(chǔ),進(jìn)行動(dòng)態(tài)聚類。23(7)主觀評(píng)定法23如上所述,模糊相似矩陣R的傳遞閉包t(R)就是一個(gè)模糊等價(jià)矩陣。以t(R)為基礎(chǔ)而進(jìn)行分類的聚類方法稱為模糊傳遞閉包法。具體步驟如下:(1)利用平方自合成方法求出模糊相似矩陣R的傳遞閉包t(R);(2)適當(dāng)選取置信水平值[0,1],求出t(R)的截矩陣t(R),它是X上的一個(gè)等價(jià)的Boole矩陣。然后按t(R)進(jìn)行分類,所得到的分類就是在水平上的等價(jià)分類。24如上所述,模糊相似矩陣R的傳遞閉包t(R)就是一個(gè)模糊等價(jià)對(duì)于xi,xjX,若rij()=1,則在水平上將對(duì)象xi和對(duì)象xj

歸為同一類。(3)畫動(dòng)態(tài)聚類圖:為了能直觀地看到被分類對(duì)象之間的相關(guān)程度,通常將t(R)中所有互不相同的元素按從大到小的順序編排:1=1>2>得到按t(R)進(jìn)行的一系列分類。將這一系列分類畫在同一個(gè)圖上,即得動(dòng)態(tài)聚類圖。例考慮某個(gè)環(huán)保部門對(duì)該地區(qū)5個(gè)環(huán)境區(qū)域X={x1,x2,x3,x4,x5}按污染情況進(jìn)行分類。設(shè)每個(gè)區(qū)域包含空氣、水分、土壤、作物4個(gè)要素。25對(duì)于xi,xjX,若rij()=1,則在水平上

環(huán)境區(qū)域的污染情況由污染物在4個(gè)要素中的含量超標(biāo)程度來衡量。設(shè)這5個(gè)環(huán)境區(qū)域的污染數(shù)據(jù)為x1=(80,10,6,2),x2=(50,1,6,4),x3=(90,6,4,6),x4=(40,5,7,3),x5=(10,1,2,4).試用模糊傳遞閉包法對(duì)X進(jìn)行分類。解由題設(shè)知特性指標(biāo)矩陣為:(1)數(shù)據(jù)規(guī)格化:采用最大值規(guī)格化,作變換xij=xij/Mj,i=1,2,,5,j=1,2,,4.可將X*規(guī)格化為:26環(huán)境區(qū)域的污染情況由污染物在4個(gè)要素中的含量超標(biāo)程度來(2)構(gòu)造模糊相似矩陣:采用最大最小法來構(gòu)造模糊相似矩陣R=(rij)55,這里27(2)構(gòu)造模糊相似矩