模糊數(shù)學(xué)2008-8等價(jià)關(guān)系與相似關(guān)系

1、吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,1,模糊數(shù)學(xué) 8,孫舒楊Email. sysun@jlu.edu.cn,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2,作業(yè)答案,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,3,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,4,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,5,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,6,習(xí)題3-3,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,7,習(xí)題3-6,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,8,習(xí)題3-7,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,9,習(xí)題3-

2、7答案,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,10,內(nèi)容回顧,模糊等價(jià)關(guān)系（矩陣）自反性 R (u,u)=1或I?R對(duì)稱性 R(u,v)=R(v,u);傳遞性 R2 ?R,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,11,模糊等價(jià)矩陣的性質(zhì),若R為模糊等價(jià)矩陣，則 R= R2 = R3 = … = Rn-1 = Rn 證明：自反性： R?R2 ?…? Rn-1 ?Rn傳遞性: R?R2?…?Rn-1?Rn,吉林大學(xué)計(jì)算機(jī)

3、科學(xué)與技術(shù)學(xué)院,12,模糊等價(jià)矩陣的定理1,定理1. R是模糊等價(jià)矩陣?對(duì)于任何λ∈[0,1]，Rλ是等價(jià)布爾矩陣。證明：對(duì)稱性、自反性顯然傳遞性的證明見3.6節(jié)定理1,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,13,定理1的意義,模糊等價(jià)矩陣?普通等價(jià)矩陣普通等價(jià)矩陣?普通等價(jià)關(guān)系普通等價(jià)關(guān)系可以分類當(dāng)λ在[0,1]上變動(dòng)時(shí)，得到不同的Rλ, 從而得到不同的分類,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,14,模糊等價(jià)矩陣分類——例,設(shè)U={

4、u1, u2, u3 ,u4, u5 }求當(dāng)λ ＝1，0.8，0.5，0.4時(shí)的聚類結(jié)果。,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,15,模糊等價(jià)矩陣的定理2,定理2. R ∈ μn×n是模糊等價(jià)矩陣，則對(duì)于任何λ,μ ∈[0,1]，且λ<μ，Rμ所決定的分類中的每個(gè)類都是Rλ所決定的分類中的某個(gè)類的子類。說明什么？λ越大，分類越細(xì),吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,16,動(dòng)態(tài)聚類圖,λ由1變到0的過程，是Rλ的分類由

5、細(xì)到粗的過程，從而形成了一個(gè)動(dòng)態(tài)的聚類圖。,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,17,3-8 模糊相似關(guān)系,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,18,模糊相似關(guān)系的定義,設(shè)R∈F(U×U)，若R具有自反性和對(duì)稱性，則稱R為U上的一個(gè)模糊相似關(guān)系例如：模糊關(guān)系“熟悉”、“朋友”、“同學(xué)”等模糊相似關(guān)系vs.模糊等價(jià)關(guān)系沒有了傳遞性的要求,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,19,為何研究模糊相似關(guān)系？,實(shí)際應(yīng)用中，通常只能得到自反和對(duì)稱矩陣

6、（相似矩陣），模糊等價(jià)矩陣較為少見Questions. 對(duì)具有相似關(guān)系的元素如何分類？相似矩陣可否改造為等價(jià)矩陣？,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,20,全新概念——傳遞閉包,設(shè)A, Â, B∈F(U×U)，若Â為包含A的傳遞關(guān)系即A?Â且Â2? Â對(duì)于任何包含A的傳遞關(guān)系B，都有Â?B則稱Â為A的傳遞閉包，記為t(A)= Â,吉林大學(xué)

7、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,21,傳遞閉包是什么？,R的傳遞閉包t(R)是包含R的最小的傳遞關(guān)系,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,22,傳遞閉包的定理1,定理1. 設(shè)模糊矩陣 A ∈ μn×n ，則其中，t(A)是傳遞閉包。,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,23,傳遞閉包定理1證明,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,24,傳遞閉包的定理2,定理2. 設(shè)模糊矩陣 A ∈ μn×n ，則其中，t(A)是傳遞閉包。,吉

8、林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,25,定理2的意義,定理2說明，當(dāng)R是n階方陣時(shí)，至多用n次并運(yùn)算，就可以得到R的傳遞閉包定理2極大地簡(jiǎn)化了傳遞閉包的計(jì)算,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,26,內(nèi)容回顧,模糊相似矩陣自反性對(duì)稱性傳遞閉包傳遞性模糊相似矩陣?傳遞閉包?模糊等價(jià)矩陣,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,27,改造有理！,定理. 相似矩陣R∈μn×n 的傳遞閉包是等價(jià)矩陣，且t(R)=Rn證明：只需證明自反性和對(duì)稱

9、性R自反? I ? R?R2 ? … ?Rn?t(R)=∪k=1n Rk= Rn是自反的對(duì)稱性。R= RT?(Rn)T= (RT)n = (Rn),吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,28,模糊相似矩陣?模糊等價(jià)矩陣,將相似矩陣改造成等價(jià)矩陣只需求相似矩陣的傳遞閉包,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,29,可否更簡(jiǎn)單？t(R)=Rn,定理. 設(shè)R∈μn×n 是模糊相似矩陣，則存在一個(gè)最小自然數(shù)k (k≤n)，使得傳遞閉包t(R)

10、=Rk，對(duì)于任何自然數(shù)b≥k，都有Rb=Rk，此時(shí)，t(R)是模糊等價(jià)矩陣。,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,30,平方法求傳遞閉包,從模糊相似矩陣R出發(fā)，依次求平方：當(dāng)?shù)谝淮纬霈F(xiàn)Rk ?Rk =Rk時(shí)， Rk就是所求的傳遞閉包t(R),吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,31,時(shí)間復(fù)雜度,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,32,課堂作業(yè),設(shè)請(qǐng)問至多幾次平方可以到達(dá)傳遞閉包？請(qǐng)給出傳遞閉包t(R),吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,3

11、3,3-9 聚類分析,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,34,聚類分析,所謂聚類分析，就是用數(shù)學(xué)方法對(duì)事物進(jìn)行分類應(yīng)用十分廣泛模糊數(shù)學(xué)產(chǎn)生之前，聚類分析是數(shù)理統(tǒng)計(jì)多元分析的一個(gè)分支現(xiàn)實(shí)分類問題具有模糊性，例如“環(huán)境污染分類”、“巖石分類”等用到模糊聚類分析,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,35,分類問題,設(shè)U ={u1, u2, …, un }為待分類的全體對(duì)象，其中每個(gè)待分類對(duì)象由一組數(shù)據(jù)表征如下：?jiǎn)栴}轉(zhuǎn)化為：如何建立對(duì)象ui

12、與uj之間的相似關(guān)系,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,36,何謂數(shù)據(jù)表征,例如，要對(duì)一些環(huán)境單元進(jìn)行分類，判斷它們的污染程度每個(gè)環(huán)境單元包括四個(gè)要素：空氣、水分、土壤、作物環(huán)境單元的污染狀況由污染物在四個(gè)要素中含量的超限度來描述《北京市東南郊環(huán)境污染治理》，獲北京市科技成果一等獎(jiǎng),吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,37,五個(gè)環(huán)境單元,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,38,步驟1：建立模糊相似關(guān)系,如何建立對(duì)象ui與uj之間的相似關(guān)系？

13、有許多方法，應(yīng)用時(shí)根據(jù)實(shí)際情況，選擇一種方法來求ui與uj的相似關(guān)系R(ui, uj)=rij在“環(huán)境污染”的例子中，如何給出模糊相似矩陣？,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,39,建立相似矩陣,建立模糊相似矩陣的注意事項(xiàng)：rij∈[0,1]自反對(duì)稱“環(huán)境”例中，采用“絕對(duì)值減數(shù)法”問：得到的相似矩陣的維數(shù)是多少？,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,40,模糊相似矩陣,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,41,步驟2：相似關(guān)系?等價(jià)關(guān)

14、系,步驟1得到的矩陣一般滿足自反性和對(duì)稱性將模糊相似矩陣改造成模糊等價(jià)矩陣平方法求傳遞閉包,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,42,至多計(jì)算多少次？,模糊相似矩陣5×5k=[log25]+1=2+1=3最壞情況下，R?R2?R4?R8，計(jì)算到R8,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,43,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,44,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,45,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,46,模糊等價(jià)矩陣,,吉林大學(xué)計(jì)

15、算機(jī)科學(xué)與技術(shù)學(xué)院,47,其他建立相似矩陣的方法,非常多！主要分為3類相似系數(shù)法距離法（絕對(duì)值減數(shù)法就是距離法之一）主觀法在后面的附錄中給出,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,48,聚類分析的步驟,建立初始矩陣?yán)媚硞€(gè)建立相似矩陣的方法，建立相似矩陣?yán)闷椒椒ǎ嗨凭仃?等價(jià)矩陣若相似矩陣的維數(shù)較大，需要多次自乘，工作量大,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,49,直接聚類法,無需求相似矩陣的傳遞閉包直接用相似矩陣進(jìn)行聚類有很多

16、種直接聚類法我們只講其中一種,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,50,直接聚類法,取λ=1(最大值)，對(duì)每個(gè)ui,確定其相似類取λ=0.8(次大值)，對(duì)每個(gè)ui,確定其相似類取λ=0.6(第三大值)，對(duì)每個(gè)ui,確定其相似類依此類推直到U歸并到一類終止得到聚類圖,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,51,問題,相似矩陣直接聚類vs.等價(jià)矩陣聚類看上去沒有區(qū)別有區(qū)別！對(duì)于一個(gè)固定的λ，等價(jià)矩陣聚類得到的等價(jià)類沒有公共元素！,吉林大學(xué)

17、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,52,回憶——等價(jià)矩陣聚類,設(shè)U={u1, u2, u3 ,u4, u5 }求當(dāng)λ ＝1，0.8，0.5，0.4時(shí)的聚類結(jié)果。,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,53,直接聚類法,對(duì)于一個(gè)固定的λ，等價(jià)矩陣聚類得到的等價(jià)類沒有公共元素！相似矩陣聚類得到的相似類則有公共元素，這是因?yàn)椴痪哂小皞鬟f性”直接聚類法——把有公共元素的相似類歸并為一類,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,54,用直接聚類法對(duì)“環(huán)境”例子

18、聚類,,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,55,課堂作業(yè),吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,56,著名聚類的例子,日本學(xué)者Tamura給出，在模糊數(shù)學(xué)中廣泛使用有三個(gè)家庭，共16人。每個(gè)家庭人數(shù)為4-7人。每人提供一張照片，共計(jì)16張由若干素不相識(shí)的中學(xué)生對(duì)照片兩兩進(jìn)行比較，按相貌相似程度進(jìn)行評(píng)分，分?jǐn)?shù)在[0,1]上。每對(duì)照片的相似程度由所有人對(duì)他們的評(píng)分的平均值確定。,吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,57,得到相似矩陣,,吉林大學(xué)計(jì)算機(jī)科