【文章內(nèi)容簡(jiǎn)介】 等價(jià)關(guān)系 ： R是 U上的一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng) ? 對(duì)于任意 x?U，均有 x R x（ 自反性 ） ? 對(duì)于任意 x, y?U， x R y?y R x （ 對(duì)稱性 ） ? 對(duì)于任意 x, y, z?U， x R y ∧ y R z→x R z （ 傳遞性 ） ? 等價(jià)類 ：若 R是 U上的一個(gè)等價(jià)關(guān)系，對(duì)于任意 x?U，稱集合 [x]={y| y R x, y ?U}為 U關(guān)于 R的一個(gè)等價(jià)類，記為 [x]R。設(shè) X1, X2, …, X n是 U關(guān)于 R的所有等價(jià)類，則有： ? Xi∩Xj=φ（ i≠j， i, j=1,2,…,n ） ? X1∪ X2∪ … ∪ Xn=U ? 劃分 ： 所有等價(jià)類的集合稱為 U關(guān)于 R的商集，它構(gòu)成了 U的一個(gè)劃分，記為 U/R。 ? 概念 ：具有相同特征值的一群對(duì)象稱為一個(gè)概念（一個(gè)等價(jià)類就是一個(gè)概念） 粗糙集：預(yù)備知識(shí) ? pi T1 pj iff 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à)類 ） ? 顯然 X1∩X2=φ。 X1∪ X2=U ? 商集 U/T1={X1, X2} U T1 T2 T3 E p1 N Y Normal Y p2 Y N Normal Y p3 Y Y High Y p4 N Y Low N p5 Y N Normal N p6 N Y High Y 粗糙集：預(yù)備知識(shí) ? 集合成員 ：明確的隸屬關(guān)系 ? 模糊成員 ：概念模糊 (如青年 )導(dǎo)致成員模糊 ? 粗糙成員 ：概念清晰 (如感冒 )，成員模糊 (是否感冒不清楚 )，具有概率特征 (隸屬函數(shù) )，但不是概率問題，只是由于根據(jù)可用知識(shí)無法得到準(zhǔn)確結(jié)論。 粗糙集：預(yù)備知識(shí) ? 粗糙集理論由 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): 341356 ? Pawlak Z., Rough set— Theoretical Aspects of Reasoning about Data, Dordrecht, Boston, London: Kluwer Academic Publishers,1991 粗糙集：理論的提出 ? 知識(shí)是主體對(duì)論域中的客體進(jìn)行分類的能力，分類能力越強(qiáng)，主體所具備知識(shí)的可靠度越高 ? 分類能力受主體分辨能力的影響，因此分類具有近似性 (粗糙集 ) ? 影響分類能力的因素 (在信息系統(tǒng)中常描述為屬性 )很多，不同的因素重要程度不同，其中某些因素起決定性作用 (屬性重要性：屬性約簡(jiǎn) ) ? 具有相同屬性的實(shí)體，屬性取值的不同對(duì)分類能力也產(chǎn)生影響 (值重要性：值約簡(jiǎn) ) ? 屬性之間存在某種依賴關(guān)系 (決策規(guī)則 ) 粗糙集：基本思想 ? 信息系統(tǒng) I可以定義為四元組 U, A, V, f，其中有限非空集合 U是論域， A為關(guān)于 U的屬性集， ， Va表示屬性 a的值域，映射 f: U A→ V表示對(duì) ?x?U， a?A，有： f(x, a)?V。 ? 決策表 ：若屬性集合 A可進(jìn) 一步分為兩個(gè)屬性子集的并： 條件屬性集 C和決策屬性集 D， A=C∪ D， C∩D=?，則信息 系統(tǒng)也被稱為決策表。 aAa VV ?? ?U T1 T2 T3 E p1 N Y Normal Y p2 Y N Normal Y p3 Y Y High Y p4 N Y Low N p5 Y N Normal N p6 N Y High Y 粗糙集：信息系統(tǒng)與知識(shí) ? A的任何一個(gè)子集 B確定一個(gè) U上的二元關(guān)系 IND(B)：對(duì)于任意 a?B， xIND(B)y?a(x)=a(y)； x, y?U； 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)或 [x]B，同一等價(jià)類中的元素是不可分辨的，稱 IND(B)等價(jià)類為 初等集（范疇） ，它是知識(shí)庫的基本結(jié)構(gòu)單元即 概念 。 ? 設(shè) R是由屬性集 A的子集誘導(dǎo)的論域 U上的等價(jià)關(guān)系族，則稱R為 U上的一個(gè) 知識(shí)庫 ，記為 K=(U, R)。 粗糙集：信息系統(tǒng)與知識(shí) ? 對(duì)于 U的任意子集 X，若 X恰能由知識(shí) R的若干個(gè)初等集的并構(gòu)成，則稱 X為 R精確集，否則為 R粗糙集 。 ? 每個(gè)粗糙集 X都可用兩個(gè)與之相關(guān)的精確集近似表示即 X的 上近似 和 下近似 ，他們是粗糙集理論的兩個(gè)最基本運(yùn)算。 粗糙集：粗糙集與近似 ? 下近似 ? 由所有包含于 X的初等集合的并構(gòu)成， X的下近似中的元素一定屬于 X。 ? 上近似 ? 由與 X的交為非空的初等集合的并構(gòu)成，而上近似中的元素可能屬于 X。 ? 上近似與下近似的差為 邊界域 ，粗糙集的邊界域?yàn)榉强?，否則為精確集。邊界域中的元素根據(jù)可用知識(shí)沒有確定的分類，即它既不能劃分到 X也不能劃分到 X的補(bǔ)集。 ? 正域與負(fù)域 XRXPO S R ?)(XRUXNeg R ??)(粗糙集：粗糙集與近似 論域 U 粗糙集 X 粗糙集粗糙集：經(jīng)典粗糙集模型 ? R1={T1}： U/R1={{p2, p3, p5}， {p1, p4, p6}}； ? R2={T2,T1}： U/R2={{p1, p4, p6}, {p2, p5}, {p3}}； ? R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 ? F={E}： U/F={{p1, p2, p3, p6}, {p4, p5}} ? X1={p1, p2, p3, p6}是 R粗糙集， X1的 R下近似是 {p1, p3, p6}， R上近似是 {p1, p2, p3, p5, p6}，邊界域?yàn)?{p2, p5}； ? X2={p4, p5}也是 R粗糙集， X2的 R下近似是 {p4}，X2的 R上近似是 {p2, p4, p5}，而邊界域是 {p2, p5}。 粗糙集：經(jīng)典粗糙集模型 U T1 T2 T3 E p1 N Y Normal Y p2 Y N Normal Y p3 Y Y High Y p4 N Y Low N p5 Y N Normal N p6 N Y High Y ? 精度 ： X的 R精度反映了我們對(duì)于了解集合 X的知識(shí)的完全程度。αR(X)=1為 精確集， 0≤αR(X)1為粗糙集。 ? 粗糙度 ： X的 R粗糙度反映了我們對(duì)于了解集合 X的知識(shí)的不完全程度。 (精度與概率或隸屬度的區(qū)別 ) 粗糙集：數(shù)字特征 ? 知識(shí) R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 ? 分類 F={E}： U/F={{p1, p2, p3, p6}, {p4, p5}} ? X1={p1, p2, p3, p6}是 R粗糙集， X1的 R下近似是 {p1, p3, p6}，R上近似是 {p1, p2, p3, p5, p6}， R精度為 ； R粗糙度為 ； ? X2={p4, p5}也是 R粗糙集， X2的 R下近似是 {p4}， X2的 R上近似是 {p2, p4, p5}， R精度為 ； R粗糙度為 。 粗糙集：數(shù)字特征 ? 設(shè) F={X1， X2， … ， Xn}是論域 U上的一個(gè)劃分，那么根據(jù)知識(shí) R， F的分類精度如何？ ? 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看成決策屬性集，近似質(zhì)量反映了兩者之間的依賴關(guān)系。 粗糙集：數(shù)字特征 ? 知識(shí) R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 ? 分類 F={E}： U/F={{p1, p2, p3, p6}, {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的近似精度為 ； ? F的近似質(zhì)量為 。 粗糙集：數(shù)字特征 ? 為了尋找“ IF…… THEN”形式的推理規(guī)則，在粗糙集理論體系中所采用的方法是從一個(gè)給定的知識(shí)，推導(dǎo)另一個(gè)知識(shí)。如果知識(shí) D的所有初等范疇都能用知識(shí) C的某些初等范疇來定義，則稱知識(shí) D可由知識(shí) C推得，也稱 D完全依賴于 C，記為 C?D。 ? 設(shè)信息系統(tǒng) I=U, A, V, f， A=C∪ D， B?C，則 D的 B正域定義為： ? D的 B正域表示：利用知識(shí) B，能正確地劃分到 U/D各等價(jià)類中的所有對(duì)象的集合 XBDPOSDUXB /)(?? ?粗糙集：知識(shí)依賴 ? 設(shè)信息系統(tǒng) I=U, C∪ D, V, f， ① D完全依賴于 C當(dāng)且僅當(dāng) ② D等價(jià)于 C當(dāng)且僅當(dāng) (C?D) ?(D?C)； ③ D獨(dú)立于 C當(dāng)且僅當(dāng) ?(C?D) ??(D?C)。 ? 如果知識(shí) D的部分初等范疇能用知識(shí) C的某些初等范疇來定義，稱知識(shí) D部分依賴于知識(shí) C。 ? 設(shè)信息系統(tǒng) I=U, C∪ D, V, f，有： 則稱 D是 k(0?k?1)度依賴于 C，記為 C?kD。 DUCU /~/ ? )( ))(()( UCard DPOSCardDk CC ?? ?粗糙集：知識(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, p4, p6}, 所以 F對(duì) R3的依賴度是 2/3。 條件屬性子集 {T1} {T2} {T3} {T1,T2} {T1,T3} {T2,T3} {T1,T2,T3} 依賴度 k 0 0 1/2 1/6 2/3 2/3 2/3 粗糙集：知識(shí)依賴 ? 為什么要約簡(jiǎn)知識(shí)？ ? 判別：根據(jù)條件屬性取值確定對(duì)象所屬的類。 ? 實(shí)際：確定對(duì)象所屬的類只需其中幾個(gè)屬性甚至一個(gè)屬性，而不需要知道對(duì)象所有的屬性，這與人類對(duì)實(shí)體的識(shí)別是一致的。 ? 表明：不同屬性在分類時(shí)所起的作用是不同的。 ? 什么是知識(shí)約簡(jiǎn)？ ? 將知識(shí)庫中某些不必要的等價(jià)關(guān)系（知識(shí)）移去的過程。 ? 設(shè)信息系統(tǒng) I=U,C∪ D,V,f， B?C，若 ?C(D)=?B(D)且 B是 D獨(dú)立的，則 B為 C的 D約簡(jiǎn)，記為 REDD(C)。 ? C的 D約簡(jiǎn)是不含任何冗余知識(shí)且與 C具有相同分類能力的子集（用知識(shí) C將對(duì)象劃分到知識(shí) D的初等范疇中的能力）。 粗糙集：知識(shí)約簡(jiǎn) ? 在確定某個(gè)決策目標(biāo)時(shí)，不同屬性的重要性是不同的，在一般分析中常用事先假設(shè)的權(quán)重來描述。 粗糙集理論并不使用事先假設(shè)的信息 ，而是根據(jù)各屬性的分類能力不同，確定該屬性的重要性。處理方法是將該屬性從信息表中移去，分析其對(duì)分類能力的影響，影響越大，屬性越重要。 ? 設(shè)信息系統(tǒng) I=U,C