【正文】 0 U\A c d e u1 2 1 0 u2 1 2 1 u3 2 1 0 u4 2 2 2 U5 2 1 0 表 7 決策表約簡 2022/8/18 高級人工智能 史忠植 59 求最優(yōu)或次優(yōu)約簡 所有約簡的計算是 NPhard問題，因此運用啟發(fā)信息來簡化計算以找出最優(yōu)或次優(yōu)約簡是必要的。 2022/8/18 高級人工智能 史忠植 55 Skowron的約簡方法 對于每一個分明矩陣 M(S)對應(yīng)唯一的分明函數(shù)fM(S)﹙ Discernibility Function﹚ ，它的定義如下： 信息系統(tǒng) S的分明函數(shù) fM(S)是一個有 m元變量 a1,… , am(ai∈ A， i=1,… ,m)的布爾函數(shù) ， 它是 ∨ cij的合取 ，∨ cij是矩陣項 cij中的各元素的析取 ， 1≤ji≤n且 cij≠Φ。 知識表達系統(tǒng) S的 分明 矩陣 M(S)=[cij]n n， 其中矩陣項定義如下： cij={a∈ A： a(xi)≠a(xj)， i,j=1,2,… ,n} 因此 cij是個體 xi與 xj有區(qū)別的所有屬性的集合 2022/8/18 高級人工智能 史忠植 54 分明矩陣對應(yīng)的核與約簡 核就可以定義為分明矩陣中所有只有一個元素的矩陣項的集合，即 CORE(A)={a∈A ： cij=(a)，對一些 i,j} 相對于集合包含關(guān)系運算而言，若屬性集合 B?A是滿足下列條件 B∩cij≠?， 對于 M(S)中的任一非空項 cij≠? 的一個最小屬性子集，則稱屬性集合 B?A是 A的一個約簡。 一致決策表的約簡步驟如下： (1) 對決策表進行條件屬性的約簡 ， 即從決策表中消去某一列； (主要研究點 ) (2) 消去重復(fù)的行； (3) 消去每一決策規(guī)則中屬性的冗余值。 2022/8/18 高級人工智能 史忠植 50 表 2 不一致決策表 a、 b、 c為條件屬性， d、 e為決策屬性 5產(chǎn)生不一致 U a b c d e 1 2 3 4 5 6 7 8 1 0 2 2 0 0 1 1 1 2 2 0 0 1 1 1 1 0 2 2 1 0 2 0 1 2 2 0 1 1 2 1 1 1 2 0 1 1 0 1 決策表的分解 2022/8/18 高級人工智能 史忠植 51 表 3 完全一致的決策表 U a b c d e 3 4 6 7 2 0 0 1 1 1 1 0 2 2 2 2 0 1 1 2 1 1 1 2 表 4 完全不一致的決策表 U a b c d e 1 2 5 8 1 0 2 2 0 0 1 1 1 2 1 0 2 0 1 0 1 1 0 1 決策表的分解 2022/8/18 高級人工智能 史忠植 52 一致決策表的約簡 在我們制定決策時是否需要全部的條件屬性，能否進行決策表的約簡。 由命題 2可見 ， 假設(shè)我們已計算出條件屬性的依賴度 ， 若表的結(jié)果不一致 ， 即依賴度小于 1， 則由命題 2可以將表分解成兩個子表：其中一個表完全不一致 ， 依賴度為 0；另一個表則完全一致 ， 依賴度為 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 。 由命題 1， 很容易通過計算條件屬性和決策屬性間的依賴程度來檢查一致性 。 若決策規(guī)則是 S中一致的 ， 相同的前驅(qū)必導(dǎo)致相同的后繼；但同一種后繼不一定必需是同一前驅(qū)產(chǎn)生的 。 2022/8/18 高級人工智能 史忠植 46 身高 性別 視力 錄取 e1 高 男 差 否 e2 高 女 一般 是 e3 高 男 好 是 e4 矮 男 差 否 e5 矮 女 一般 是 e6 矮 男 好 是 表 1 一決策表 身高、性別、視力為條件屬性，錄取為決策屬性 四、 決策表的約簡 2022/8/18 高級人工智能 史忠植 47 決策規(guī)則 決策表中的每一行對應(yīng)諸如 ??? 形式的決策規(guī)則，?和 ?分別稱為決策規(guī)則的前驅(qū)和后繼 。 決策表可以定義如下： S=(U, A)為一信息系統(tǒng)，且 C, D?A是兩個屬性子集，分別稱為條件屬性和決策屬性，且 C?D=A， C?D=?，則該信息系統(tǒng)稱為 決策表，記作 T=(U, A, C, D)或簡稱 CD決策表。 2022/8/18 高級人工智能 史忠植 45 四、 決策表的約簡 決策表 決策表是一類特殊而重要的知識表達系統(tǒng) ， 它指當滿足某些條件時 ， 決策 （ 行為 ） 應(yīng)當怎樣進行 。現(xiàn)在我們形式地定義部分依賴性。 2022/8/18 高級人工智能 史忠植 44 知識的依賴性 依賴性也可以是部分成立的 ﹐ 也就是從知識 P能推導(dǎo)出知識Q的一部分知識，或者說知識 Q只有一部分依賴于知識 P的。 2022/8/18 高級人工智能 史忠植 43 知識的依賴性 知識的依賴性可形式定義如下： 定義 11 設(shè) K=(U, R)是一個近似空間 ， P, Q?R。 定理 2 族集 P的 Q核等于族集 P的所有 Q約簡的交集 。 2022/8/18 高級人工智能 史忠植 42 相對約簡 定義 10 S?P稱為 P的 Q約簡 (Qreduct)﹐ 當且僅當 S是 P的 Q獨立的子族集 ﹐ 且 POSS(Q)=POSP(Q)；族集 P中的所有 Q不可省的初等關(guān)系的集合 ﹐ 稱為族集 P的 Q核 (Qcore)﹐ 記作COREQ(P) 。 定義 9 設(shè) P和 Q是全域 U上的等價關(guān)系的族集 ， R?P。這樣 ﹐ 由{p,q,r}三個等價關(guān)系組成的集合和 {p,q}、 {p,r}定義了相同的不分明關(guān)系。 定理 1 族集 P的核等于 P的所有約簡的交集。在族集 P中所有不可省的關(guān)系的集合稱為 P的 核 (core) ﹐ 以 CORE(P)來表示。若族集 R中的每個關(guān)系 R都是不可省的 ﹐ 則稱族集 R是 獨立的 (independent)﹐ 否則就是 依賴的 或 非獨立 的。 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 近似性質(zhì) Properties of Approximations YXYBXBYXBYBXBYXBUUBUB BBXBXXB?????????????)()()()()()()()(,)()()(???)()( YBXB ? )()( YBXB ?implies and 2022/8/18 高級人工智能 史忠植 38 近似性質(zhì) Properties of Approximations (2) )())(())(()())(())(()()()()()()()()()()(XBXBBXBBXBXBBXBBXBXBXBXBYBXBYXBYBXBYXB????????????????where X denotes U X. 2022/8/18 高級人工智能 史忠植 39 三、 知識的約簡 ? 一般約簡 定義 6 設(shè) R是等價關(guān)系的一個族集，且設(shè) R?R。 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： 設(shè)有一知識庫 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} 。 )(xRX?2022/8/18 高級人工智能 史忠植 30 集近似實例 Set Approximation ? Let W = {x | Walk(x) = yes}. ? The decision class, Walk, is rough since the boundary region is not empt