第三章模糊關(guān)系與聚類

13.F關(guān)系與聚類分析

3.1F關(guān)系的定義和性質(zhì)

3.2F矩陣

3.3F關(guān)系的自反性與對(duì)稱性

3.4λ截集

3.5F關(guān)系合成

23.F關(guān)系與聚類分析

3.6F關(guān)系的傳遞性

3.7F等價(jià)關(guān)系及聚類圖

3.8F相似關(guān)系

3.9F聚類分析

3三、

模糊關(guān)系合成運(yùn)算性質(zhì)：(1)合成運(yùn)算滿足結(jié)合律

(Q?R)?S=

Q?(R?S)，

特別地

Rm

?Rn=Rm+n。(2)合成運(yùn)算關(guān)于并“?”滿足分配律

(Q?

R)?S=(Q?S)?(R?S),(1)S?(Q?

R)=(S?Q)?(S?R)。

(2)4證明只證(1)。設(shè)Q，RF

(UV),SF(VW),故有(Q?

R)?S=(Q?S)?(R?S)。

5第二式證明相似。應(yīng)注意的是，1)

合成運(yùn)算不滿足交換律，即Q?RR?Q。如設(shè)則因此，Q?RR?Q。62)合成運(yùn)算對(duì)交“”不滿足分配律，即有下列二式：(Q

R)?S(Q?S)

(R?S),S?(Q

R)(S?Q)(S?R)。

(Q

R)?S

(Q?S)

(R?S),S?(Q

R)

(S?Q)(S?R)。

例如：則

7因此(Q

R)?S(Q?S)

(R?S)。

同樣可以舉出反例來(lái)說(shuō)明第二個(gè)式子。?R=R?=,(UV)?R=R?(UV)=R

。

(4)

若QR，則

Q?SR?S

，P?Q

P?R,Qn

Rn8定義9:設(shè)RF

(UV

)，定義R-1F

(VU

)的隸屬函數(shù)為R-1(v，u)=R(u，v)

((v，u)V

U),稱V

到U

的模糊關(guān)系RT

為R的轉(zhuǎn)置關(guān)系。命題4:轉(zhuǎn)置關(guān)系有下述性質(zhì)：設(shè)R，R1，R2

F

(UV)，{Rt|tT}F

(UV),SF

(VW

),則(1)

若R1

R2

R1T

R2T

。(2)(RT)T=R。9推論(1)設(shè)R

F

(UU

)，則

(Rn

)T=(RT)n。(2)設(shè)R，QF

(UU)且RQ,則RnQn(n為正整數(shù))。103.6

F等價(jià)關(guān)系定義10:設(shè)R

F

(U

U

)(1)

稱R是自反的

uU，R(u,u)=1。(2)

稱R是對(duì)稱的

u,vX

，R(u,v)=R(v,u)。(3)若R是U

上的自反、對(duì)稱關(guān)系，則稱R是U

上的模糊相似關(guān)系，簡(jiǎn)稱相似關(guān)系。11命題5

設(shè)R

F

(UU)，則(1)

R是自反的

IR。(2)R是自反的

RnRn+1(n1)

且Rn也是自反的。證明(1)

顯然。12(2)

用歸納法證明包含式RnRn+1。(u,v)UU,有故R

R2。設(shè)Rn-1

Rn，由（7）式可得Rn-1

?R

Rn?R,即RnRn+1。因

IR

Rn(n1)，由(1)知Rn是自反的。13命題6

設(shè)R，R1，R2

F

(UU

)，則有(1)R是對(duì)稱的R=RT。(2)

若R1、R2都是對(duì)稱的，則R1

?R2對(duì)稱

R1

?R2=

R2

?R1(即

R1、R2是可以交換的）。(3)R是對(duì)稱的Rn是對(duì)稱的(n1)。證明(1)由對(duì)稱關(guān)系的定義可得。14(2)先證()：若R1

?R2

是對(duì)稱的，因R1、R2也對(duì)稱，故R1

?R2=(R1

?R2)-1=R2-1

?R1-1=R2

?R1。再證()：若R1

?R2=

R2

?R1，則

(R1

?R2)-1=R2-1

?R1-1=R2

?R1=R1

?R2由(1)知，R1

?R2是對(duì)稱的。

(3)若R對(duì)稱，則有(Rn

)-1=(R-1)n

=Rn。由(1)知，Rn是對(duì)稱的。15推論

(1)若R是U上的相似關(guān)系，則Rn也是U上的相似關(guān)系。

(2)設(shè)RF

(UU)是任一模糊關(guān)系，則R

?RT是U上的對(duì)稱關(guān)系。證明因(R

?RT)T=(RT

)T?RT=R

?RT，由命題

(1)知，R

?RT是對(duì)稱的。16定義11

設(shè)R

F

(U

U

)，

R為傳遞的

[0，1]，u，v，wU，

R(u,v)，R(v,w)，則R(u,w)。命題7

設(shè)R，R1，R2

F

(U

U

)，則(1)R是傳遞的

R2R。(2)若

R是傳遞的

Rn是傳遞的(n1)。(3)R1、R2

是傳遞的

R1

R2

是傳遞的。17證明(1)

先證()：設(shè)u，vU，tU，令t=R(u,t)R(t,v)，則R(u，t)t，R(t，v)t

。由于R是傳遞的,故R(u,v)t(tU)，于是18由u，v

的任意性知

R2R再證()：若R2R且R(u，v)，R(v，w)

于是由定義11知

R是傳遞的。19(2)

若R是傳遞的，則由(1)有R2R，進(jìn)一步由(7)右邊一式得(R2)n

Rn又由

(Rn)2=(R2)n

，聯(lián)合上面兩式，得

(Rn)2=(R2)n

Rn，最后由(1)知Rn是傳遞的。20(3)我們可以用兩

式證明(Q?

R)?S(Q?S)

(R?S),S?(Q?

R)

(S?Q)(S?R)。應(yīng)用上面兩式，得(R1

R2)2=(R1

R2)?(R1

R2)(R1?(R1

R2))

(

R2?(R1

R2))

(R1?

R1)

(R1?

R2)

(R2?

R1)(R2?

R2)21R12

R22。因?yàn)?，R1、R2是傳遞的，即R12

R1、R22

R2，則有

(R1

R2)2R1

R2

，所以，R1

?R2是傳遞的。22

模糊傳遞閉包和等價(jià)閉包

通常的模糊關(guān)系，不一定具有傳遞性，因而不是模糊等價(jià)關(guān)系。對(duì)這種模糊關(guān)系直接進(jìn)行分類顯然是不合理的。為此，我們希望尋求一種方法，能將不是等價(jià)的模糊關(guān)系進(jìn)行改造，以便分類使用。23

定義13

設(shè)RF

(UU

)，稱t(R)

為R

的傳遞閉包，如果t(R)

滿足:(1)傳遞性：(t(R))2

t(R)；(2)包容性：Rt(R)；(3)最小性：若R′是U

上的模糊傳遞關(guān)系，且

RR′t(R)

R′，即R的傳遞閉包是包含R的最小的傳遞關(guān)系。24定理2:設(shè)RF

(UU

)，則證明：(1)首先證明是傳遞的，即要證明25由傳遞性定義知，是傳遞的。26(2)顯然有(3)

若有R’

使RR’且R’是傳遞的，則由RR’

有

R2(R’)2R’,

R3=R?R2R?R’(R’)2R’,

……一般有RnR’,從而27即含于任一包含R的傳遞關(guān)系中。綜上所述，是包含R的最小傳遞關(guān)系，因而是R的傳遞閉包，即28

在論域?yàn)橛邢藜那闆r下，傳遞閉包的計(jì)算變得很簡(jiǎn)捷。命題8

設(shè)|U|=n，RF

(U

U

)

，則證明略。29推論設(shè)|U

|=n，RF

(UU

)

，且R是自反關(guān)系，則存在正整數(shù)m(n)

，使t(R)=Rm，且

l>m有Rl=t(R)。證明因?yàn)閨U|=n，所以又因?yàn)镽是自反的，由命題(2)知R

R2

R3……,

30因而在做上述合成運(yùn)算時(shí)，若做到

m(n)

次時(shí)，出現(xiàn)了Rm+1

=Rm，則有Rm+2

=Rm，進(jìn)而，t(R)=Rm。這時(shí)，若我們?nèi)≌麛?shù)

l>m，則有31即有Rl=t(R)。上述推論說(shuō)明，在計(jì)算有限論域上自反的模糊關(guān)系R的傳遞閉包時(shí)，可以從R開(kāi)始，反復(fù)自乘，依次計(jì)算出R，R2，R4，…，

，…，當(dāng)?shù)谝淮纬霈F(xiàn)Rk?Rk=Rk時(shí)，就有t(R)=Rk。32命題9

模糊關(guān)系的傳遞閉包t(R)

有以下性質(zhì)：(1)

若IR，則It(R)

。(2)

(

t(R))T=t(R

T)。(3)若R

T=R，則(

t(R))T=t(R)

。證明

(1)由定理2可得。

(2)由定理2、命題4(3)及推論(1)，有

33(3)由(2)即得。上述命題中的(1)說(shuō)明自反關(guān)系的傳遞閉包還是自反的，(3)表明對(duì)稱關(guān)系的傳遞閉包還是對(duì)稱的。34定義14:

設(shè)RF

(U

U)，稱e(R)

為R的等價(jià)閉包，若e(R)

滿足下述條件：(1)等價(jià)性：e(R)

是X上的模糊等價(jià)關(guān)系。(2)包容性：Re(R)。(3)最小性：若R’

是X上的模糊等價(jià)關(guān)系，且

RR’e(R)R’

。顯然，R的等價(jià)閉包是包含R的最小的等價(jià)關(guān)系。35例8

給定有限論域上的模糊關(guān)系R如下：則由于模糊矩陣R2的元素不超過(guò)R對(duì)應(yīng)位置上的元素36因而模糊關(guān)系R2R，故R是傳遞的。命題:

設(shè)R是U

上的一個(gè)自反的和傳遞的模糊關(guān)系，則有R=R2。證明因?yàn)镽是自反的，則有，RR2。又因?yàn)镽是傳遞的，則

有，R2R，故有R=R2。37定義12

設(shè)RF

(U

U

)，若R滿足下列三個(gè)條件，則稱R是U上的一個(gè)模糊等價(jià)關(guān)系：(1)

自反性：uU，R(u，u)=1。(2)

對(duì)稱性：u，vU，R(u，v)=R(v，u)。(3)

傳遞性：

R2R，即u，wU

U，有38

若U={u1,u2,…,un}為有限論域時(shí)，U上的模糊等價(jià)關(guān)系R是一個(gè)矩陣（稱為模糊等價(jià)矩陣），它滿足下述三個(gè)條件：(1)

自反性：rii=1,i=1,2,…,n。(2)

對(duì)稱性：rij=rji，i，j=1,2,…,n。(3)傳遞性：

R

?RR，即

39

條件(1)說(shuō)明模糊矩陣的對(duì)角線元素都是1；條件(2)意味著模糊等價(jià)矩陣是對(duì)稱矩陣。40定理3:

設(shè)R

F

(UU

)，則R是模糊等價(jià)關(guān)系[0，1]，R是經(jīng)典等價(jià)關(guān)系，這里R={(u,v)U

U

|R(u,v)}為R的截關(guān)系。且對(duì)于，[0，1]，>，有等價(jià)類

R[u]R[u](uU

)。證明略。41

本定理說(shuō)明，若R是U

上的模糊等價(jià)關(guān)系，則其截關(guān)系是經(jīng)典等價(jià)關(guān)系，它們都可將U

作一個(gè)劃分，當(dāng)從1下降到0時(shí)，就得到一個(gè)劃分族，而且由于>時(shí)，

R[u]R[u]，即R給出的分類結(jié)果中的每類，是R給出的分類結(jié)果的子類，所以R給出的分類結(jié)果比R給出的分類結(jié)果更細(xì)。隨著的下降，

R給出的分類越來(lái)越粗，這樣就得到一個(gè)動(dòng)態(tài)的聚類圖，我們可以根據(jù)實(shí)際情況的需要，選擇某個(gè)水平上的分類結(jié)果。這是模糊聚類分析的一大優(yōu)越性42例:

設(shè)U={x1，x2，x3，x4，x5}，R是U上的一個(gè)模糊關(guān)系，其對(duì)應(yīng)的模糊矩陣為在上面的矩陣中，對(duì)角線元素為1，即rii=1，所以R是自反的。又因R與其轉(zhuǎn)置矩陣相同，故3.7F動(dòng)態(tài)聚類圖43rij=rji，R

=R-1，即R是對(duì)稱的。由于即R?R=R2R，R是傳遞的，故R是模糊等價(jià)關(guān)系。44

依次取截關(guān)系R，R是經(jīng)典等價(jià)關(guān)系，它誘導(dǎo)出U

上的一個(gè)劃分U/R，將U

分成一些等價(jià)類。當(dāng)=1時(shí)，R1誘導(dǎo)的分類為五類：{x1},{x2},{x3},{x4},{x5}。45當(dāng)=0.8時(shí)，R0.8誘導(dǎo)的分類為四類：{x1，x3},{x2},{x4},{x5}。46當(dāng)=0.6時(shí)，R0.6誘導(dǎo)的分類為三類：{x1,x3},{x2},{x4,x5}。47當(dāng)=0.5時(shí)，R0.5誘導(dǎo)的分類為兩類：{x1,

x3,

x4,x5},{x2}。48最后，當(dāng)=0.4時(shí)，R0.4將X分成一類：{x1,

x2,

x3,

x4,x5}。49

隨由大到小，分類由細(xì)到粗，形成一個(gè)動(dòng)態(tài)的分類圖，如圖

所示：

x1x3x4x5x2=1

0.80.60.50.4

圖

動(dòng)態(tài)聚類圖50

教材

P75

用歸并相似類法給出了同樣的分類。求模糊相似關(guān)系的等價(jià)類有以下三種方法：等價(jià)閉包法(e(R))——間接法歸并相似類法最大樹(shù)法直接法513.9

模糊聚類分析模糊聚類分析在實(shí)際問(wèn)題中有廣泛的應(yīng)用，這是由于實(shí)際問(wèn)題中，一組事物是否屬于某一類常帶有模糊性，也就是問(wèn)題的界限不是十分清晰的。我們不能明確地回答“是”或“否”，而是只能作出“在某種程度上“是”或“否””的回答，這就是模糊聚類分析。本節(jié)主要討論基于模糊等價(jià)關(guān)系的動(dòng)態(tài)聚類的實(shí)際應(yīng)用。521.特征抽取假設(shè)待分類對(duì)象的集合為U={U1,U2,…,Un}，集合中的每個(gè)元素具有m個(gè)特征，設(shè)第i個(gè)對(duì)象Ui

的第j(j=1,2,…,m)個(gè)特征為xij，則Ui就可以用這m個(gè)特征的取值來(lái)描述，記Ui=(xi1,xi2,…,xim)

(i=1，2，…，n)53

為了計(jì)算簡(jiǎn)便，并使特征僅具有相對(duì)的意義，我們要首先對(duì)特征的觀測(cè)值進(jìn)行預(yù)先處理，使各特征值的取值在單位區(qū)間[0,1]中。設(shè)

Ui的觀測(cè)值為Xi0，Ui0=(xi10，xi20，…，xim0)(i=1,2,…,n)所以用下列各公式對(duì)Ui0進(jìn)行“規(guī)格化”的預(yù)處理。54(1)

xij=cxij0(i=1,…,n；

j=1,…,m)c是一個(gè)常數(shù)，選擇

c

使任何

xij在[0,1]中。(2)

xij=cxij0/max(xij0)(i=1,…,n;j=1,…,m)即選擇所有的特征中的最大值作分母。(3)

當(dāng)特征值中出現(xiàn)負(fù)值時(shí)，則用下式壓縮到[0,1]：55當(dāng)特征值不是負(fù)值時(shí)，當(dāng)然也可以用上式來(lái)“規(guī)格化”式中

是全部特征值的均值，分子是特征值與均值的距離。用此式“規(guī)格化”時(shí)應(yīng)注意：只要與均值的距離相等，特征值的大小的方向性就被“湮滅”。

562.建立U上的模糊關(guān)系（模糊相似矩陣）設(shè)待分類對(duì)象的全體是U={U1,U2,…,Un}，我們首先要鑒別U中的元素Ui與Uj的接近程度（相似程度）。用[0,1]中的數(shù)rij來(lái)表示Ui與Uj的相似程度，稱為相似系數(shù)。相似系數(shù)組成一個(gè)矩陣(rij)nn稱為相似系數(shù)矩陣，它是U上的模糊相似關(guān)系。我們對(duì)此關(guān)系矩陣求其等價(jià)閉包或等價(jià)類，就能對(duì)

U中的元素進(jìn)行聚類。57

為了確定相似系數(shù)，必須使相似系數(shù)符合自反、對(duì)稱的要求，可根據(jù)實(shí)際情況選用下列方法之一。1）數(shù)量積法其中582）夾角余弦法3）相關(guān)系數(shù)法其中594）指數(shù)相似系數(shù)法其中sk與

m為常數(shù)。5）絕對(duì)值指數(shù)法606）絕對(duì)值倒數(shù)法其中M

為適當(dāng)選擇的常數(shù)，M

的選擇使rij[0,1]。617)非參數(shù)法令是xik

與xjk的均值），nij+={x’i1x’j1,x’i2x’j2,…,x’im

x’jm}中正數(shù)個(gè)數(shù)，nij－={x’i1x’j1,x’i2x’j2,…,x’im

x’jm}中負(fù)數(shù)個(gè)數(shù)，628）貼近度法貼近度表示兩個(gè)模糊向量之間接近的程度，它符合自反、對(duì)稱的要求，所以可以用來(lái)表示相似系數(shù)。我們將

U中的元素Ui，Uj

看成是各自特征的模糊向量，便可以用貼近度來(lái)表示相似系數(shù)rij，rij=(Ui,Uj)63(1)當(dāng)取內(nèi)外積貼近度時(shí)或64(2)最大最小法，當(dāng)取上式時(shí)(3)算術(shù)平均最小法，當(dāng)取前式時(shí)65(4)幾何平均最小法，當(dāng)取前式時(shí)(5)絕對(duì)值減數(shù)法，當(dāng)取距離貼近度時(shí)rij=1－c(dp

(Xi，Xj))式中c，為常數(shù)，p為各種距離的代碼系數(shù)。66

當(dāng)

p=1時(shí)，dp

就是海明距離，此時(shí)求相似系數(shù)的方法稱絕對(duì)值減數(shù)法，其相似系數(shù)為

當(dāng)p=2時(shí)，dp

就是歐氏距離，此時(shí)有679）經(jīng)驗(yàn)法請(qǐng)有經(jīng)驗(yàn)的人來(lái)分別對(duì)Ui與

Uj的相似性打分，設(shè)有s個(gè)人參加評(píng)分，若第k個(gè)人(1ks)認(rèn)為Ui與

Uj相似的程度為aij(k)

（在[0，1]中），他對(duì)自己評(píng)分的自信度也打分，若自信度分值是bij(k)

，則可以用下式來(lái)計(jì)算相似系數(shù):68

在以上確定相似系數(shù)的諸多方法中，究竟選用哪一種合適，需要根據(jù)問(wèn)題的具體性質(zhì)來(lái)決定。693、例舉

環(huán)境單元分類每個(gè)環(huán)境單元可以包括空氣、水分、土壤、作物等四個(gè)要素。環(huán)境單元的污染狀況由污染物在四要素中含量的超限度來(lái)描寫。假設(shè)有五個(gè)單元x1,x2,x3,x4,x5，它們的污染數(shù)據(jù)如表3.13所示。70

取論域

U={x1,x2,x3,x4,x5}，按上式“規(guī)格化”，取

c=0.1，再按前式求相似系數(shù)（取

c=1)，

要素?cái)?shù)據(jù)單元空氣水分土壤作物x1x2x3x4

x552512535543423525311表13污染數(shù)據(jù)71得到模糊相似矩陣72

聚類方法可以有三種方法來(lái)對(duì)模糊相似矩陣聚類。1）傳遞閉包法（平方法）求出模糊相似矩陣的傳遞閉包t(R)，它就是R的等價(jià)閉包

e(R)=t(R)，然后求其

截關(guān)系

e(R)。它是經(jīng)典等價(jià)關(guān)系，讓

從1降至0，當(dāng)變化時(shí)，它們給出一個(gè)動(dòng)態(tài)的分類結(jié)果。求R

的傳遞閉包

t(R)時(shí)，可以用平方法，即求R2,R4,…,Rk，若有Rk

Rk=Rk，則t(R)=Rk。73經(jīng)計(jì)算可知74當(dāng)=1時(shí)，分成五類：{x1},

{x2}

,{x3},{x4},{x5}當(dāng)=0.8時(shí)，分成四類：{x1,x3},

{x2}

,{x4},{x5}當(dāng)=0.6時(shí)，分成三類：{x1,x3},

{x2}

,{x4,x5}當(dāng)=0.5時(shí)，分成二類：{x1,x3,x4,x5},

{x2}當(dāng)=0.4時(shí)，分成一類：{x1,x2,x3,x4,x5}75其動(dòng)態(tài)分類如下圖

所示：=1x1x3

x4

x5

x20.80.60.50.4圖

動(dòng)態(tài)聚類圖762）直接聚類法根據(jù)模糊相似矩陣

來(lái)直接由相似類求等價(jià)類。當(dāng)=1時(shí)，該矩陣只有對(duì)角線上的元素為1，所以不許歸并相似類，所得到的e(R)1

的等價(jià)類為{x1}，{x2}，{x3}，{x4}，{x5}。當(dāng)=0.8時(shí)，先求經(jīng)典矩陣R0.8，有此求得它的相似類是77R0.8[x1]={x1,x3}，R0.8[x2]={x2}

，R0.8[x4]={x4}，R0.8[x5]={x5}。在歸并時(shí)，找不到與{x1,x3}相交的其它等價(jià)類，于是e(R)0.8的等價(jià)類為：

{x1,x3},

{x2}

,{x4},{x5}。同樣=0.6時(shí)，相似類為R0.6[x1]={x1,x3},R0.6[x2]={x2},R0.6[x4]={x4,x5}，也無(wú)法再進(jìn)一步歸并，于是e(R)0.6的等價(jià)類為：

{x1,x3},

{x2}

,{x4,x5}。78

當(dāng)=0.5時(shí)，相似類為R0.5[x1]={x1,x3,x4}，R0.5[x2]={x2},R0.5[x4]={x1,x4,x5}，因此可以把相似類R0.5[x1]與

R0.5[x4]歸并，得

P1(x1)=R0.5[x1]R0.5[x4]={x1,x3,x4,x5}，最終得到的e(R)0.5的等價(jià)類為{x1,x3,x4,x5},

{x2}。當(dāng)=0.4時(shí)，得到R0.4[x2]={x2，x5}，于是可以和P1(x1)歸并，即P2(x1)={x1,x2,x3,x4,x5}，這就是e(R)0.4的等價(jià)類。

793）最大樹(shù)法（Kruskal）

在模糊相似矩陣

中，從=1開(kāi)始逐步做連通圖，直到=0時(shí)為止，每作一條邊，就在邊上寫出

rij

之值（連通強(qiáng)度）。注意不要做回路。從原則上來(lái)說(shuō)，可以選擇任一元素（頂點(diǎn)）作為起始點(diǎn)，但一般總是選有相似類的元素開(kāi)始。例如在本例中當(dāng)=0.8時(shí)，就有相似類{x1,x3}，于是就把

x1選為起始頂點(diǎn)，先作出強(qiáng)度為800.8的邊，然后再作強(qiáng)度為0.6的邊及強(qiáng)度為0.5和0.4的邊，這樣就得到最大樹(shù)，如下圖所示。

圖

3最大樹(shù)x1x4x5

x2x30.80.50.60.481

在不同

水平上的分類，就是在最大樹(shù)中砍去那些強(qiáng)度小于的邊，再分類。例如=0.8時(shí)，砍掉最大樹(shù)右邊的各枝，就得到分類：{x1,x3},

{x2}

,{x4},{x5}；而在=0.6時(shí)，只砍掉強(qiáng)度為0.5和0.4的邊，于是得到的分類就是：{x1,x3},