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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、算機科學與技術(shù)學院,47,其他建立相似矩陣的方法,非常多！主要分為3類相似系數(shù)法距離法（絕對值減數(shù)法就是距離法之一）主觀法在后面的附錄中給出,吉林大學計算機科學與技術(shù)學院,48,聚類分析的步驟,建立初始矩陣利用某個建立相似矩陣的方法，建立相似矩陣利用平方法，相似矩陣?等價矩陣若相似矩陣的維數(shù)較大，需要多次自乘，工作量大,吉林大學計算機科學與技術(shù)學院,49,直接聚類法,無需求相似矩陣的傳遞閉包直接用相似矩陣進行聚類有很多

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

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

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