【文章內(nèi)容簡(jiǎn)介】 {u5, u7}, {u6, u8}. 2022/8/18 高級(jí)人工智能 史忠植 34 Lower amp。 Upper 近似 (4) R = {Headache, Temp.} U/R = { {u1}, {u2}, {u3}, {u4}, {u5, u7}, {u6, u8}} X1 = {u | Flu(u) = yes} = {u2,u3,u6,u7} X2 = {u | Flu(u) = no} = {u1,u4,u5,u8} RX1 = {u2, u3} = {u2, u3, u6, u7, u8, u5} RX2 = {u1, u4} = {u1, u4, u5, u8, u7, u6} X1RX2Ru1 u4 u3 X1 X2 u5 u7 u2 u6 u8 2022/8/18 高級(jí)人工智能 史忠植 35 例 1： 設(shè)有一知識(shí)庫(kù) K={U,{p,q,r}}﹐ 其中 U={x1,x2,x3,x4,x5,x6,x7,x8}﹐ 且 U/p={{x1,x4,x5},{x2,x8},{x3},{x6,x7}} U/q={{x1,x3,x5},{x6},{x2,x4 ,x7,x8}} U/r={{x1,x5},{x6},{x2,x7,x8},{x3,x4}} 則 [x1]p={x1 ,x4 ,x5}﹐[x 1]q= {x1 ,x3 ,x5} 。 若 P={p,q,r}﹐ 則 IND(P)= {{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}} 對(duì)于 U上的子集 X1={x1,x4,x7}﹐ 可得到 P* X1={x4}∪{x 7}={x4 ,x7} P* X1={x1 ,x5}∪{x 4}∪{x 7}={x1 ,x4 ,x5 ,x7} Lower amp。 Upper 近似 (5) 2022/8/18 高級(jí)人工智能 史忠植 36 近似度 Accuracy of Approximation where |X| denotes the cardinality of Obviously If X is crisp with respect to B. If X is rough with respect to B. |)(||)(|)(XBXBXB ??.??X.10 ?? B?,1)( ?XB?,1)( ?XB?2022/8/18 高級(jí)人工智能 史忠植 37 近似性質(zhì) Properties of Approximations YXYBXBYXBYBXBYXBUUBUB BBXBXXB?????????????)()()()()()()()(,)()()(???)()( YBXB ? )()( YBXB ?implies and 2022/8/18 高級(jí)人工智能 史忠植 38 近似性質(zhì) Properties of Approximations (2) )())(())(()())(())(()()()()()()()()()()(XBXBBXBBXBXBBXBBXBXBXBXBYBXBYXBYBXBYXB????????????????where X denotes U X. 2022/8/18 高級(jí)人工智能 史忠植 39 三、 知識(shí)的約簡(jiǎn) ? 一般約簡(jiǎn) 定義 6 設(shè) R是等價(jià)關(guān)系的一個(gè)族集，且設(shè) R?R。若IND(R)=IND(R–R)，則稱關(guān)系 R在族集 R之中是 可省 的(dispensable)﹐ 否則就是 不可省 的。若族集 R中的每個(gè)關(guān)系 R都是不可省的 ﹐ 則稱族集 R是 獨(dú)立的 (independent)﹐ 否則就是 依賴的 或 非獨(dú)立 的。 定義 7 若 Q?P是獨(dú)立的 ﹐ 并且 IND(Q)=IND(P)﹐ 則稱 Q是關(guān)系族集 P的一個(gè) 約簡(jiǎn) (reduct) 。在族集 P中所有不可省的關(guān)系的集合稱為 P的 核 (core) ﹐ 以 CORE(P)來(lái)表示。 顯然，族集 P有多個(gè)約簡(jiǎn)（約簡(jiǎn)的不唯一性）。 定理 1 族集 P的核等于 P的所有約簡(jiǎn)的交集。即 CORE(P)=∩ RED(P) 2022/8/18 高級(jí)人工智能 史忠植 40 例 2： 取 前面 的例 1﹐ 若 P={p,q,r}﹐ 則IND(P)={{x1 ,x5},{x2 ,x8},{x3},{x4},{x6},{x7}}﹐ IND(Pp})={{x1 ,x5},{x2 ,x7 ,x8},{x3},{x4},{x6}}?IND(P) 所以 p是不可省的 ﹐ 同理可得 q、 r是可省的。這樣 ﹐ 由{p,q,r}三個(gè)等價(jià)關(guān)系組成的集合和 {p,q}、 {p,r}定義了相同的不分明關(guān)系。 又 IND({p,q})?IND({p})﹐ IND({p﹐q}) ?IND({q})﹐ 則{p,q}和 {p, r}就是 P的 約簡(jiǎn) ﹐ 而且 {p}是 P的核 ﹐ 也就是說(shuō) p是絕對(duì)不能省的 三、 知識(shí)的約簡(jiǎn) 2022/8/18 高級(jí)人工智能 史忠植 41 相對(duì)約簡(jiǎn) 定義 8 設(shè) P和 Q是全域 U上的等價(jià)關(guān)系的族集，所謂族集 Q的P正區(qū)域 (Ppositive region of Q)，記作 POSP(Q)= ?Q/UX?P*(X) 族集 Q的 P正區(qū)域 是全域 U的所有那些使用分類 U/P所表達(dá)的知識(shí)，能夠正確地分類于 U/Q的等價(jià)類之中的對(duì)象的集合。 定義 9 設(shè) P和 Q是全域 U上的等價(jià)關(guān)系的族集 ， R?P。 若 POSIND(P)(IND(Q))=POSIND(P{R})(IND(Q)) 則稱關(guān)系 R在族集 P中是Q可省的 ﹐ 否則稱為 Q不可省的 ﹔ 如果在族集 P中的每個(gè)關(guān)系 R都是 Q不可省的 ﹐ 則稱 P關(guān)于 Q是 獨(dú)立的 ﹐ 否則就稱為是依賴的 。 2022/8/18 高級(jí)人工智能 史忠植 42 相對(duì)約簡(jiǎn) 定義 10 S?P稱為 P的 Q約簡(jiǎn) (Qreduct)﹐ 當(dāng)且僅當(dāng) S是 P的 Q獨(dú)立的子族集 ﹐ 且 POSS(Q)=POSP(Q)；族集 P中的所有 Q不可省的初等關(guān)系的集合 ﹐ 稱為族集 P的 Q核 (Qcore)﹐ 記作COREQ(P) 。 下面的定理是 定理 1的拓廣 。 定理 2 族集 P的 Q核等于族集 P的所有 Q約簡(jiǎn)的交集 。 即 COREQ(P)=?REDQ(P) 其中 REDQ(P)是族集 P的所有 Q約簡(jiǎn)的族集 。 2022/8/18 高級(jí)人工智能 史忠植 43 知識(shí)的依賴性 知識(shí)的依賴性可形式定義如下： 定義 11 設(shè) K=(U, R)是一個(gè)近似空間 ， P, Q?R。 1) 知識(shí) Q依賴于 知識(shí) P或知識(shí) P可推導(dǎo)出 知識(shí) Q，當(dāng)且僅當(dāng)IND(P)?IND(Q)﹐ 記作 P?Q； 2) 知識(shí) P和知識(shí) Q是 等價(jià)的 ﹐ 當(dāng)且僅當(dāng) P?Q且 Q?P﹐ 即IND(P)=IND(Q)﹐ 記作 P= Q，明顯地， P=Q當(dāng)且僅當(dāng)IND(P)=IND(Q)； 3) 知識(shí) P和知識(shí) Q是 獨(dú)立的 ，當(dāng)且僅當(dāng) P?Q且 Q?P均不成立，記作 P?Q。 2022/8/18 高級(jí)人工智能 史忠植 44 知識(shí)的依賴性 依賴性也可以是部分成立的 ﹐ 也就是從知識(shí) P能推導(dǎo)出知識(shí)Q的一部分知識(shí)，或者說(shuō)知識(shí) Q只有一部分依賴于知識(shí) P的。部分依賴性（部分可推導(dǎo)性）可以由知識(shí)的正區(qū)域來(lái)定義。現(xiàn)在我們形式地定義部分依賴性。 定義 12 設(shè) K=(U, R)是一個(gè)知識(shí)庫(kù) ﹐ P, Q?R﹐ 我們稱 知識(shí) Q以依賴度 k(0? k? 1)依賴于知識(shí) P﹐ 記作 P?kQ﹐ 當(dāng)且僅當(dāng) k=?P(Q)=card(POSP(Q))/card(U) () (1) 若 k=1﹐ 則稱知識(shí) Q完全依賴于 知識(shí) P， P?1Q也記成 P?Q； (2) 若 0?k?1﹐ 則稱知識(shí) Q部分依賴于 知識(shí) P； (3) 若 k=0﹐ 則稱知識(shí) Q完全獨(dú)立于 與知識(shí) P。 2022/8/18 高級(jí)人工智能 史忠植 45 四、 決策表的約簡(jiǎn) 決策表 決策表是一類特殊而重要的知識(shí)表達(dá)系統(tǒng) ， 它指當(dāng)滿足某些條件時(shí) ， 決策 （ 行為 ） 應(yīng)當(dāng)怎樣進(jìn)行 。 多數(shù)決策問(wèn)題都可以用決策表形式來(lái)表示 ， 這一工具在決策應(yīng)用中起著重要的作用 。 決策表可以定義如下： S=(U, A)為一信息系統(tǒng)，且 C, D?A是兩個(gè)屬性子集，分別稱為條件屬性和決策屬性，且 C?D=A， C?D=?，則該信息系統(tǒng)稱為 決策表，記作 T=(U, A, C, D)或簡(jiǎn)稱 CD決策表。關(guān)系 IND(C)和關(guān)系 IND(D)的等價(jià)類分別稱為條件類和決策類。 2022/8/18 高級(jí)人工智能 史忠植 46 身高 性別 視力 錄取 e1 高 男 差 否 e2 高 女 一般 是 e3 高 男 好 是 e4 矮 男 差 否 e5 矮 女 一般 是 e6 矮 男 好 是 表 1 一決策表 身高、性別、視力為條件屬性，錄取為決策屬性 四、 決策表的約簡(jiǎn) 2022/8/18 高級(jí)人工智能 史忠植 47 決策規(guī)則 決策表中的每一行對(duì)應(yīng)諸如 ??? 形式的決策規(guī)則，?和 ?分別稱為決策規(guī)則的前驅(qū)和后繼 。 當(dāng)決策表 S中決策規(guī)則 ???為真時(shí) ， 我們說(shuō)該決策規(guī)則是 S中一致的 ， 否則說(shuō)該決策規(guī)則是 S中不一致的 。 若決策規(guī)則是 S中一致的 ， 相同的前驅(qū)必導(dǎo)致相同的后繼；但同一種后繼不一定必需是同一前驅(qū)產(chǎn)生的 。 如表 1第一行對(duì)應(yīng)決策規(guī)則： 身高 (高 )?性別 (男 )?視力 (差 ) ? 錄取 (否 ) 2022/8/18 高級(jí)人工智能 史忠植 48 決策表的一致性 命題 1 當(dāng)且僅當(dāng) C?D， 決策表 T=(U, A, C, D)是一致的 。 由命題 1， 很容易通過(guò)計(jì)算條件屬性和決策屬性間的依賴程度來(lái)檢查一致性 。 當(dāng)依賴程度等于 1時(shí) ， 我們說(shuō)決策表是一致的 ， 否則不一致 。 2022/8/18 高級(jí)人工智能 史忠植 49 決策表的分解 命題 2 每個(gè)決策表 T=(U, A, C, D)都可以唯一分解為兩個(gè)決策表T1=(U1, A, C, D)和 T2=(U2, A, C, D)， 這樣使得表 T1中C?1D 和 T2 中 C?0D 。 這里 U1=POSC(D) ， U2=?BNC(