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