第04講-智能決策理論與方法-1(2)解析.ppt

1、2020/7/19,粗糙集理論(Rough Set Theory),1,粗糙集理論(Rough Set Theory: RST),電子商務(wù)研究所,2020/7/19,粗糙集理論(Rough Set Theory),2,預(yù)備知識(shí)相關(guān)名詞解釋,論域：研究對(duì)象的全體成員構(gòu)成的集合，一般用字母U表示；若XU，則稱X是U的子集 隸屬度：描述一個(gè)對(duì)象x與某個(gè)子集X之間的隸屬程度，一般用符號(hào)表示， 若xX, 則=1; 若 ,則=0; 其他： 01;(常用某個(gè)函數(shù)加以描述，稱為隸屬度函數(shù)),高斯函數(shù),2020/7/19,粗糙集理論(Rough Set Theory),3,預(yù)備知識(shí)相關(guān)名詞解釋,等價(jià)關(guān)系：R是U

2、上的一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng) 對(duì)于任意xU，均有x R x（自反性） 對(duì)于任意x, yU，x R yy R x（對(duì)稱性） 對(duì)于任意x, y, zU，x R y y R zx R z（傳遞性） 等價(jià)類：若R是U上的一個(gè)等價(jià)關(guān)系，對(duì)于任意xU，稱集合x(chóng)=y| y R x, y U為U關(guān)于R的一個(gè)等價(jià)類，記為xR。設(shè)X1, X2, , Xn是U關(guān)于R的所有等價(jià)類，則有： XiXj=（ij，i, j=1,2,n） X1X2Xn=U 劃分：所有等價(jià)類的集合稱為U關(guān)于R的商集，它構(gòu)成了U的一個(gè)劃分，記為U/R。 概念：具有相同特征值的一群對(duì)象稱為一個(gè)概念（一個(gè)等價(jià)類就是一個(gè)概念）,2020/7/19,粗糙集

3、理論(Rough Set Theory),4,預(yù)備知識(shí)相關(guān)名詞解釋,pi T1 pj iif v(pi, T1)=v(pj, T1)，則T1是U上的一個(gè)等價(jià)關(guān)系（類似地可以定義T2, T3, E） X1=p1=p4=p6=p1, p4, p6為U關(guān)于T1的一個(gè)等價(jià)類 X2=p2=p3=p5=p2, p3, p5為U關(guān)于T1的另一個(gè)等價(jià)類（T1有多少種取值就有多少個(gè)等價(jià)類） 顯然 X1X2=; X1X2=U 商集U/T1=X1, X2,2020/7/19,粗糙集理論(Rough Set Theory),5,預(yù)備知識(shí)成員,集合成員：明確的隸屬關(guān)系 模糊成員：概念模糊(如青年)導(dǎo)致成員模糊 粗糙成員

4、：概念清晰(如感冒)，成員模糊(是否感冒不清楚)，具有概率特征(隸屬函數(shù))，但不是概率問(wèn)題，只是由于根據(jù)可用知識(shí)無(wú)法得到準(zhǔn)確結(jié)論。,2020/7/19,粗糙集理論(Rough Set Theory),6,粗糙集理論的經(jīng)典模型RST的提出,粗糙集理論由Pawlak提出1982,1991。粗糙集理論反映了人們以不完全信息或知識(shí)去處理一些不可分辨現(xiàn)象的能力，或依據(jù)觀察、度量到某些不精確的結(jié)果而進(jìn)行分類數(shù)據(jù)的能力。 Pawlak Z., Rough sets. International Journal of Computer and Information Sciences, 1982(11): 3

5、41-356 Pawlak Z., Rough setTheoretical Aspects of Reasoning about Data, Dordrecht, Boston, London: Kluwer Academic Publishers,1991,2020/7/19,粗糙集理論(Rough Set Theory),7,粗糙集理論的經(jīng)典模型基本思想,知識(shí)是主體對(duì)論域中的客體進(jìn)行分類的能力，分類能力越強(qiáng)，主體所具備知識(shí)的可靠度越高 分類能力受主體分辨能力的影響，因此分類具有近似性 (粗糙集) 影響分類能力的因素(在信息系統(tǒng)中常描述為屬性)很多，不同的因素重要程度不同，其中某些因素起決

6、定性作用 (屬性重要性：屬性約簡(jiǎn)) 具有相同屬性的實(shí)體，屬性取值的不同對(duì)分類能力也產(chǎn)生影響 (值重要性：值約簡(jiǎn)) 屬性之間存在某種依賴關(guān)系(決策規(guī)則),2020/7/19,粗糙集理論(Rough Set Theory),8,粗糙集理論的經(jīng)典模型信息系統(tǒng)與知識(shí),信息系統(tǒng)I可以定義為四元組，其中有限非空集合U是論域，A為關(guān)于U的屬性集， ，Va表示屬性a的值域，映射f: UAV表示對(duì)xU，aA，有： f(x, a)V。 決策表：若屬性集合A可進(jìn) 一步分為兩個(gè)屬性子集的并： 條件屬性集C和決策屬性集D， A=CD，CD=，則信息 系統(tǒng)也被稱為決策表。,2020/7/19,粗糙集理論(Rough Se

7、t Theory),9,粗糙集理論的經(jīng)典模型信息系統(tǒng)與知識(shí),A的任何一個(gè)子集B確定一個(gè)U上的二元關(guān)系IND(B)：對(duì)于任意aB，xIND(B)ya(x)=a(y)；x, yU；a(x)表示對(duì)象x的a屬性值。則稱IND(B)為不可分辨關(guān)系(?)。 IND(B)是等價(jià)關(guān)系，IND(B)的所有等價(jià)類的集合記為U/B（稱為知識(shí)B），含有元素x的等價(jià)類記為B(x)或xB，同一等價(jià)類中的元素是不可分辨的，稱IND(B)等價(jià)類為初等集（范疇），它是知識(shí)庫(kù)的基本結(jié)構(gòu)單元即概念。 設(shè)R是由屬性集A的子集誘導(dǎo)的論域U上的等價(jià)關(guān)系族，則稱R為U上的一個(gè)知識(shí)庫(kù)，記為K=(U, R)。,2020/7/19,粗糙集理論(

8、Rough Set Theory),10,粗糙集理論的經(jīng)典模型粗糙集與近似,對(duì)于U的任意子集X，若X恰能由知識(shí)R的若干個(gè)初等集的并構(gòu)成，則稱X為R-精確集，否則為R-粗糙集。 每個(gè)粗糙集X都可用兩個(gè)與之相關(guān)的精確集近似表示即X的上近似和下近似，他們是粗糙集理論的兩個(gè)最基本運(yùn)算。,2020/7/19,粗糙集理論(Rough Set Theory),11,粗糙集理論的經(jīng)典模型粗糙集與近似,下近似 由所有包含于X的初等集合的并構(gòu)成， X的下近似中的元素一定屬于X。 上近似 由與X的交為非空的初等集合的并構(gòu)成，而上近似中的元素可能屬于X。 上近似與下近似的差為邊界域，粗糙集的邊界域?yàn)榉强?，否則為精確集

9、。邊界域中的元素根據(jù)可用知識(shí)沒(méi)有確定的分類，即它既不能劃分到X中也不能劃分到X的補(bǔ)集中。 正域與負(fù)域,2020/7/19,粗糙集理論(Rough Set Theory),12,粗糙集理論的經(jīng)典模型經(jīng)典粗糙集模型,2020/7/19,粗糙集理論(Rough Set Theory),13,粗糙集理論的經(jīng)典模型經(jīng)典粗糙集模型,R1=T1：U/R1=p2, p3, p5，p1, p4, p6； R2=T2,T1：U/R2=p1, p4, p6, p2, p5, p3； R3=T1, T2, T3：U/R3=(p1, p3, p6, p2, p5,p4; F=E：U/F=p1, p2, p3, p6,

10、p4, p5 X1=p1, p2, p3, p6是R3粗糙集，X1的R3下近似是p1, p3, p6，R3上近似是p1, p2, p3, p5, p6，邊界域?yàn)閜2, p5； X2=p4, p5也是R3粗糙集，X2的R3下近似是p4，X2的R3上近似是p2, p4, p5，而邊界域是p2, p5。,2020/7/19,粗糙集理論(Rough Set Theory),14,粗糙集理論的經(jīng)典模型拓?fù)浣Y(jié)構(gòu),R粗糙可定義 能準(zhǔn)確確定某部分對(duì)象一定屬于X，某部分對(duì)象一定不屬于X，某部分對(duì)象可能屬于X。 R內(nèi)不可定義 能準(zhǔn)確某部分對(duì)象一定不屬于X，某部分對(duì)象可能屬于X，而不能確定任何對(duì)象屬于X。 R外不可

11、定義 能準(zhǔn)確確定某部分對(duì)象一定屬于X，某部分對(duì)象可能屬于X ，不能確定任何對(duì)象不屬于X R完全不可定義,2020/7/19,粗糙集理論(Rough Set Theory),15,粗糙集理論的經(jīng)典模型粗糙集數(shù)字特征,精度： X的R精度反映了我們對(duì)于了解集合X的知識(shí)的完全程度。R(X)=1為精確集， 0R(X)1為粗糙集。 粗糙度：X的R粗糙度反映了我們對(duì)于了解集合X的知識(shí)的不完全程度。(精度與概率或隸屬度的區(qū)別) 隸屬度：是根據(jù)可用知識(shí)R，對(duì)象x隸屬于概念X的條件概率。,2020/7/19,粗糙集理論(Rough Set Theory),16,粗糙集理論的經(jīng)典模型粗糙集數(shù)字特征,設(shè)F=X1，X2

12、，Xn是論域U上的一個(gè)劃分，那么根據(jù)知識(shí)R，F(xiàn)的分類精度如何？ F的近似精度：分類的近似精度給出了根據(jù)現(xiàn)有知識(shí)對(duì)對(duì)象進(jìn)行分類時(shí)可能正確的決策的百分?jǐn)?shù)。 F的近似質(zhì)量：近似質(zhì)量給出了能正確分類的百分?jǐn)?shù)。這是一個(gè)非常重要的特征數(shù)字，它反映了兩種分類F和R之間的關(guān)系。如果將R看作決策表中的條件屬性集，F(xiàn)看成決策屬性集，近似質(zhì)量反映了兩者之間的依賴關(guān)系。,2020/7/19,粗糙集理論(Rough Set Theory),17,粗糙集理論的經(jīng)典模型粗糙集數(shù)字特征,知識(shí)R=T1, T2, T3：U/R=(p1, p3, p6, p2, p5,p4; 分類F=E：U/F=p1, p2, p3, p6, p

13、4, p5 X1=p1, p2, p3, p6是R粗糙集，X1的R下近似是p1, p3, p6，R上近似是p1, p2, p3, p5, p6，R精度為0.6；R粗糙度為0.4； X2=p4, p5也是R粗糙集，X2的R下近似是p4，X2的R上近似是p2, p4, p5， R精度為0.333；R粗糙度為0.667； p2隸屬于X1的隸屬度為0.25。,2020/7/19,粗糙集理論(Rough Set Theory),18,粗糙集理論的經(jīng)典模型粗糙集數(shù)字特征,知識(shí)R=T1, T2, T3：U/R=(p1, p3, p6, p2, p5,p4; 分類F=E：U/F=p1, p2, p3, p6,

14、 p4, p5 X1=p1, p2, p3, p6是R粗糙集，X1的R下近似是p1, p3, p6，R上近似是p1, p2, p3, p5, p6 ； X2=p4, p5也是R粗糙集，X2的R下近似是p4，X2的R上近似是p2, p4, p5； F的近似精度為0.5； F的近似質(zhì)量為0.667。,2020/7/19,粗糙集理論(Rough Set Theory),19,粗糙集理論的經(jīng)典模型知識(shí)依賴,為了尋找“IFTHEN”形式的推理規(guī)則，在粗糙集理論體系中所采用的方法是從一個(gè)給定的知識(shí)，推導(dǎo)另一個(gè)知識(shí)。如果知識(shí)D的所有初等范疇都能用知識(shí)C的某些初等范疇來(lái)定義，則稱知識(shí)D可由知識(shí)C推得，也稱D完

15、全依賴于C，記為CD。 設(shè)信息系統(tǒng)I=，A=CD，BC，則D的B正域定義為： D的B正域表示利用知識(shí)B，能正確地劃分到U/D各等價(jià)類中的所有對(duì)象的集合,2020/7/19,粗糙集理論(Rough Set Theory),20,粗糙集理論的經(jīng)典模型知識(shí)依賴,設(shè)信息系統(tǒng)I=， D完全依賴于C當(dāng)且僅當(dāng) D等價(jià)于C當(dāng)且僅當(dāng)(CD) (DC)； D獨(dú)立于C當(dāng)且僅當(dāng)(CD) (DC)。 如果知識(shí)D的部分初等范疇能用知識(shí)C的某些初等范疇來(lái)定義，稱知識(shí)D部分依賴于知識(shí)C。 設(shè)信息系統(tǒng)I=，有： 則稱D是k(0k1)度依賴于C，記為CkD。,2020/7/19,粗糙集理論(Rough Set Theory),2

16、1,粗糙集理論的經(jīng)典模型知識(shí)依賴,R1=T1：U/R1=p2, p3, p5，p1, p4, p6； R2=T2,T1：U/R2=p1, p4, p6, p2, p5, p3； R3=T1, T2, T3：U/R3=(p1, p3, p6, p2, p5,p4; F=E：U/F=p1, p2, p3, p6, p4, p5 X1=p1, p2, p3, p6是R3粗糙集，X1的R3下近似是p1, p3, p6，R3上近似是p1, p2, p3, p5, p6 ； X2=p4, p5也是R3粗糙集，X2的R3下近似是p4，X2的R3上近似是p2, p4, p5 。 F的R3正域是p1, p3,

17、p4, p6, 所以F對(duì)R3的依賴度是2/3。,2020/7/19,粗糙集理論(Rough Set Theory),22,粗糙集理論的經(jīng)典模型知識(shí)約簡(jiǎn),為什么要約簡(jiǎn)知識(shí)？ 判別：根據(jù)條件屬性取值確定對(duì)象所屬的類。 實(shí)際：確定對(duì)象所屬的類只需其中幾個(gè)屬性甚至一個(gè)屬性，而不需要知道對(duì)象所有的屬性，這與人類對(duì)實(shí)體的識(shí)別是一致的。 表明：不同屬性在分類時(shí)所起的作用是不同的。 什么是知識(shí)約簡(jiǎn)？ 將知識(shí)庫(kù)中某些不必要的等價(jià)關(guān)系（知識(shí)）移去的過(guò)程。 設(shè)信息系統(tǒng)I=，BC，若C(D)=B(D)且B是D獨(dú)立的，則B為C的D約簡(jiǎn)，記為REDD(C)。 C的D約簡(jiǎn)是不含任何冗余知識(shí)且與C具有相同分類能力的子集（用知

18、識(shí)C將對(duì)象劃分到知識(shí)D的初等范疇中的能力）。,2020/7/19,粗糙集理論(Rough Set Theory),23,粗糙集理論的經(jīng)典模型屬性重要性與屬性核,在確定某個(gè)決策目標(biāo)時(shí)，不同屬性的重要性是不同的，在一般分析中常用事先假設(shè)的權(quán)重來(lái)描述。粗糙集理論并不使用事先假設(shè)的信息，而是根據(jù)各屬性的分類能力不同，確定該屬性的重要性。處理方法是將該屬性從信息表中移去，分析其對(duì)分類能力的影響，影響越大，屬性越重要。 設(shè)信息系統(tǒng)I=，對(duì)于C的非空子集B，其重要度為 若B的重要度為，則表示B可以從C中移去，也即B是冗余的。重要度可理解為移去B時(shí)所產(chǎn)生的分類誤差。 設(shè)信息系統(tǒng)I=，C中所有D不可省略的元素構(gòu)

19、成的集合稱為C的D核，記作CoreD(C)。,2020/7/19,粗糙集理論(Rough Set Theory),24,粗糙集理論的經(jīng)典模型分辨矩陣,分辨矩陣 為了簡(jiǎn)化核、約簡(jiǎn)及其它概念的計(jì)算，Skowron在1991年提出了分辨矩陣的概念。 設(shè) ，BA的分辨矩陣M(B)定義為： B核是M(B)中全部含有單個(gè)元素的條目的并即：,2020/7/19,粗糙集理論(Rough Set Theory),25,粗糙集理論的經(jīng)典模型分辨矩陣,若存在一個(gè)B的最小子集 ，使得對(duì)于M(B)中的任意非空條目 有 ，則 是B的約簡(jiǎn)。 相對(duì)約簡(jiǎn)和相對(duì)核：設(shè)C、D是A的兩個(gè)非空子集，C為條件屬性，D為決策屬性，則C的分

20、辨矩陣定義為：,2020/7/19,粗糙集理論(Rough Set Theory),26,粗糙集理論的經(jīng)典模型分辨矩陣,的意義：表示兩個(gè)對(duì)象有且只有一個(gè)存在于POSC(D)中，或者若二者均存在于POSC(D)中，但二者對(duì)屬性集D不等價(jià)。如果D誘導(dǎo)的劃分可由知識(shí)C定義即所有對(duì)象均屬于POSC(D)，則 可簡(jiǎn)化為 C的D核：是MD(C)中所有含單個(gè)元素的條目的并 C的D約簡(jiǎn)：若存在一個(gè)C的最小子集 ，使得對(duì)于MD(C)中的任意非空條目 有 ， 則 是C的D約簡(jiǎn)。 按定義，C的D分辨矩陣為主對(duì)角線為空集的對(duì)稱陣：,2020/7/19,粗糙集理論(Rough Set Theory),27,粗糙集理論的

21、經(jīng)典模型分辨矩陣,2020/7/19,粗糙集理論(Rough Set Theory),28,粗糙集理論的經(jīng)典模型知識(shí)約簡(jiǎn)算法,基于屬性依賴度的屬性約簡(jiǎn)：設(shè)決策表T=，C,D分別為條件屬性和決策屬性，B是C的任一非空子集，對(duì)于粗糙集的VP-MD模型，D對(duì)B的依賴度為： 則在B中增加某個(gè)屬性pC-B所引起的k的變化大小為： p(D|B)= Bp(D)-B(D) p(D|B)越大，說(shuō)明在已知屬性B的條件下，p對(duì)決策D越重要?；趯傩砸蕾嚩鹊膶傩约s簡(jiǎn)算法就是將p(D|B)作為尋找最小屬性約簡(jiǎn)的啟發(fā)式信息。,2020/7/19,粗糙集理論(Rough Set Theory),29,粗糙集理論的經(jīng)典模型知

22、識(shí)約簡(jiǎn)算法,基于屬性互信息的屬性約簡(jiǎn)：苗奪謙等人將條件屬性與決策屬性的依賴度轉(zhuǎn)變成互信息，在決策表中增加某個(gè)屬性所引起互信息變化的大小作為屬性重要性的度量。 設(shè)決策表T=，C,D分別為條件屬性和決策屬性，B是C的任一非空子集，在B中增加某個(gè)屬性pC-B所引起的互信息增量為： I(p;D|B)=I(Bp;D)I(B;D)=H(D|B)H(D|Bp) 該增量越大，說(shuō)明在已知屬性B的條件下，p對(duì)決策D越重要?；诨バ畔⒌膶傩约s簡(jiǎn)算法就是將I(p;D|B)作為尋找最小屬性約簡(jiǎn)時(shí)的啟發(fā)式信息,2020/7/19,粗糙集理論(Rough Set Theory),30,粗糙集理論的經(jīng)典模型知識(shí)約簡(jiǎn)算法,基于

23、分辨矩陣的約簡(jiǎn)算法： 分辨函數(shù)：=(T1T2)(T3) (T1 T2) (T2 T3) (T1 T2 T3) (T1 T2 T3) (T1 T3) (T2 T3) (T1 T2 T3) (T3) (T1 T2 T3) =(T1T2) (T3) =(T1 T3 )(T2T3),2020/7/19,粗糙集理論(Rough Set Theory),31,粗糙集理論的經(jīng)典模型值約簡(jiǎn),為什么要約簡(jiǎn)屬性值？ 在判斷某個(gè)對(duì)象屬于某類時(shí)，某個(gè)屬性的取值不同，對(duì)分類產(chǎn)生的影響也不相同。例如，判斷人的體形(瘦、中、胖)時(shí)，體重是重要屬性。但若體重屬性值為60Kg時(shí)，此人的體形要結(jié)合其身高、性別才能確定，但若體重屬

24、性值為150Kg時(shí)，我們幾乎肯定他是個(gè)胖子，這時(shí)身高、性別已不重要，也就是說(shuō)身高、性別的屬性值是冗余的。 什么是值約簡(jiǎn)？ 值約簡(jiǎn)就是移去對(duì)分類沒(méi)有實(shí)際價(jià)值的冗余的屬性值。,2020/7/19,粗糙集理論(Rough Set Theory),32,粗糙集理論的經(jīng)典模型約簡(jiǎn)示例,IF (T1, No) AND (T3, Normal) THEN (E, Yes) IF (T1, Yes) AND (T3, Normal) THEN (E, Yes) IF (T3, High) THEN (E, Yes) IF (T3, Low) THEN (E, No) IF (T1, Yes) AND (T3,

25、 Normal) THEN (E, No) IF (T3, High) THEN (E, Yes),2020/7/19,粗糙集理論(Rough Set Theory),33,粗糙集理論的經(jīng)典模型約簡(jiǎn)示例,IF (T2, Yes) AND (T3, Normal) THEN (E, Yes) IF (T2, No) AND (T3, Normal) THEN (E, Yes) IF (T3, High) THEN (E, Yes) IF (T3, Low) THEN (E, No) IF (T2, No) AND (T3, Normal) THEN (E, No) IF (T3, High) THEN (E, Yes),2020/7/19,粗糙集理論(Rough Set Theory),34,擴(kuò)展粗糙集模型-擴(kuò)展的背景,為什么要研究RST的拓展模型？ 經(jīng)典粗糙集理論假設(shè)信息系統(tǒng)僅包含精確(準(zhǔn)確、可靠)數(shù)據(jù)，任何對(duì)象的任何屬性都有一個(gè)唯一的精確