智能信息處理是當前信息科學理論和應用研究中的一個熱點領域.由于計算機科學與技術的發展,特別是計算機網絡的發展,每日每時為人們提供了大量的信息.信息量的不斷增長,對信息分析的要求也越來越高,人們希望自動地從數據中獲取其潛在的知識.特別是近20年, 知識發現\\(規則提取、數據挖掘、機器學習\\)受到人工智能學界的廣泛重視,知識發現的各種不同方法應運而生.粗糙集\\(RoughSet,也稱Rough集、粗集\\)理論是Pawlak教授于1982年提出的一種能夠定量分析處理不精確、不一致、不完整信息與知識的數學工具[2][13].粗糙集理論最初的原型來源于比較簡單的信息模型,它的基本思想是通過關系數據庫分類歸納形成概念和規則,通過等價關系的分類以及分類對于目標的近似實現知識的發現.
知識表達是智能信息系統的關鍵,知識的獲取就是要從大量的原始數據信息中分析發現有用的規律信息,即是將知識從一種原來的表達形式轉換成一種新的目標表達形式.計算機與網絡信息技術的飛速發展,使得各領域的數據和信息急劇增加,為了尋求數據庫中的決策性的信息,粗糙集理論從數據庫中提煉出知識庫,由決策表給出知識庫的決策推理就是決策邏輯.文獻[11]、[12]對粗糙集理論的公理化進行研究.上個世紀 90 年代出現了很多的描述粗糙集的方式,Iwinski[4]用布爾代數的子代數來描述粗糙集,將粗糙集定義為一對可定義集;Yao[5]用論域 U 的子集空間來描述粗糙集,將粗糙集定義為一個閉區間集合.從代數學意義上講, Iwinski 粗糙集代數和區間代數是等價的,Iwinski 粗糙集代數系統可以看作為一個上下界是可定義集的區間代數系統.同時,Pawlak,Skowron,Wong 和Yao[6][7]等也提出用論域 U 的元素 x 來描述粗糙集,文獻[7]還提出了決策粗糙集理論,得到了集合的上下近似定義,研究了它的粗糙性.Kryszkiewicz、Banerjee 等分別從不同角度研究了不完全的信息系統的決策表[8]、[9]、[10],本文是基于完全信息系統的決策表而進行研究的.
在知識庫的表示和更新領域中決策表及決策邏輯起到了很大作用.本文對決策表給出的決策系統,進行圖論表示,從而給出決策邏輯在圖論上的語義模型.最后還研究了決策邏輯在圖論的語義模型上基本的粗糙性.
1 決策邏輯的基本語法和語義
本文所牽涉圖論的術語采用 Bondy 的文[1]給出的描述,文中的決策邏輯語言采用 Pawlak 在文[2]、[3]中給出的方式定義.為了閱讀方便,我們引入 Pawlak 給出的決策邏輯語言.
定義 1[2]決策邏輯 DL 語言的字母表包括以下三個部分:
\\(1\\)有窮的屬性集合 A,其元素稱為屬性;
\\(2\\)有窮的屬性值集合 V=∪Va,每個屬性 a 的屬性值集合 Va都是有窮集合;
\\(3\\)邏輯聯結符號 \\(非\\),∧\\(并且\\),∨\\(或者\\),→\\(蘊涵\\),\\(等價\\).
定義 2[2]決策邏輯 DL 語言合式公式包括以下三個部分:
\\(1\\)原子公式\\(a,v\\)或簡記為 av,其中 a∈A,av∈Va;
\\(2\\)如果 α ,β 是合式公式,那么 α ,α ∧β ,α ∨β ,α →β ,α β 是合式公式;
\\(3\\)僅有以上兩條形成合式公式.所有公式的集合記為 D
定義 3[2]一個信息系統 S 是一個四元組
定義 4[2]決策邏輯 DL 的一個模型是一個結構 M=
有了定義 4,我們可以定義決策邏輯 DL 合式公式 α 關于模型 M 在 x∈U 可滿足性,記為 M,x╞α .定義 5[2]
決策邏輯 DL 的可滿足性定義如下
\\(1\\)M,x╞\\(a,v\\)當且僅當 f\\(a,x\\)=v;
\\(2\\)M,x╞ α ,當且僅當, 非 M,x╞ α ;
\\(3\\)M,x╞α ∧β ,當且僅當, M,x╞ α ,并且 M,x╞ β ;
\\(4\\)M,x╞α ∨β ,當且僅當, M,x╞ α ,或者 M,x╞ β ;
\\(5\\)M,x╞α →β ,當且僅當,M,x╞ α ,或者 M,x╞ β ;
\\(6\\)M,x╞α β ,當且僅當,M,x╞α →β ,并且 M,x╞β →α .
顯然\\(5\\),\\(6\\)是由其他若干定義來給出,下面的討論中,我們省掉這兩條.
2 決策邏輯的二部圖語義模型
為了下面的描述,我們將決策邏輯 DL 語言的關于屬性 a 的原子公式集合記為 Pa={\\(a,v\\):v∈Va},決策邏輯 DL 語言合式公式的集合記為 D.
定義 6 決策邏輯 DL 系統關于屬性 a 的二部圖 Ga=\\(U ,Pa,Ea\\),如果任意論域個體 x∈U 僅僅存在唯一 av∈Pa使得 x 與 av有邊相連,即\\(x,av\\)∈Ea.
定義 7 決策邏輯 DL 系統的基本語義圖 GB是所有的屬性 a 的二部圖 Ga全體.對于任意的 x∈U,記關于基本語義圖 GB的屬性 a 的相同屬性值的論域子集[x]G a={y:頂點 x,y在二部圖 Ga中與同一個頂點\\(a,v\\)有邊相連}
為了給出決策邏輯 DL 系統的圖論模型,下面給出語義圖上的操作定義,它對于理解下文來說是很重要的.
定義 8 二部圖 G=\\(X,Y,E\\)上的一元操作,也稱為翻轉操作,將二部圖中 X 與 Y 所有沒連邊的頂點間連上邊,并且去掉原有的邊,同時將 Y 的每個頂點 y 改為 y,記這個二部圖為 G=\\(X, Y,E\\),稱為二部圖 G=\\(X,Y,E\\)的翻轉二部圖.
定義 9 若兩個二部圖 G1=\\(X,Y1,E1\\)與二部圖 G2=\\(X,Y2,E2\\)的第一部分頂點相同,則如下定義一個二元操作,也稱為并操作,先建立這個二部圖 G=\\(X,Y1∧Y2,E\\)的另一個頂點集合 Y1∧Y2={y1∧y2: y1∈Y1,y2∈Y2}再給出二部圖的邊集合 E ={\\(x,y1∧y2\\): \\(x,y1\\)∈E1并且\\(x,y2\\)∈E2}.稱這個二部圖 G=\\(X,Y1∧Y2,E\\),為二部圖 G1與二部圖 G2的并二部圖.
定義 10 若兩個二部圖 G1=\\(X,Y1,E1\\)與二部圖 G2=\\(X,Y2,E2\\)的第一部分頂點相同,則如下定義一個二元操作,也稱為或操作,先建立這個二部圖 G=\\(X,Y1∨Y2,E\\)的另一個頂點集合 Y1∨Y2={y1∨y2: y1∈Y1,y2∈Y2}再給出二部圖的邊集合 E ={\\(x,y1∨y2\\): \\(x,y1\\)∈E1或者\\(x,y2\\)∈E2}.稱這個二部圖 G=\\(X,Y1∨Y2,E\\),為二部圖 G1與二部圖 G2的或二部圖.
對于一個給點的決策邏輯 DL 系統的基本語義圖 GB,因為這些二部圖的第一部分頂點集合都相同,于是我們可以在決策邏輯 DL 系統的基本語義圖 GB上施行上面的操作.
下面我們來構造圖論的語義模型.
定義 11 決策邏輯 DL 系統的關于論域 U 的二部語義圖 G 是由僅有以下規則形成:
\\(1\\)基本語義圖 GB是決策邏輯 DL 系統的二部語義圖;
\\(2\\)若二部圖 G=\\(U,Y,E\\)是決策邏輯 DL 系統的二部語義圖,則施行翻轉操作后的二部圖是決策邏輯 DL 系統的二部語義圖;
\\(3\\)若二部圖 G1=\\(U,Y1,E1\\)與二部圖 G2=\\(U,Y2,E2\\)是決策邏輯 DL 系統的二部語義圖,則施行并操作后的二部圖 G=\\(U,Y1∧Y2,E\\)是決策邏輯 DL 系統的二部語義圖;
\\(4\\)若二部圖 G1=\\(U,Y1,E1\\)與二部圖 G2=\\(U,Y2,E2\\)是決策邏輯 DL 系統的二部語義圖,則施行或操作后的二部圖 G=\\(U,Y1∨Y2,E\\)是決策邏輯 DL 系統的二部語義圖;
定義 12 決策邏輯 DL 的公式 α 關于決策邏輯 DL 系統的二部語義圖模型 G={G:G 是關于論域 U的二部語義圖},在 x∈U 可滿足性定義如下:G,x╞α 當且僅當存在某個二部語義圖 G ∈G 使得在這個二部圖中 G 中, x 與 α 有邊相連.
容易得到下面的關于決策邏輯 DL 系統的二部語義圖模型 G 的性質.
性質 1 任給的決策邏輯 DL 的合式公式 α 必在且只在決策邏輯 DL 系統的二部語義圖模型 G 的某個二部圖 G 作為頂點出現一次.
性質 2 在決策邏輯 DL 系統的每一個基本二部圖 GB的頂點 x∈U 有且僅有一個頂點與之相連.
定理 1 決策邏輯 DL 系統的二部語義圖模型 G 與決策邏輯 DL 的一個模型是一個結構 M=
證明:首先易證信息系統 S 的 f 是個映射.下面通過歸納于公式 α 的結構,來證明這兩個模型的等價性.由性質 1 知 α 必是某個二部圖的頂點.基礎:當 α 為原子公式\\(a,v\\)時候,由 G,x╞α的定義有,在基本語義二部圖 Ga∈G 中, x 與 α 僅有一邊相連,于是在 M 中有對應 f\\(x,a\\)=v,于是由模型的定義知 M,x╞\\(a,v\\).另一方面,由 M,x╞\\(a,v\\)即有 f\\(x,a\\)=v,于是在關于屬性 a 的二部圖 Ga中,給出 x 與 α 有一邊相連,于是由模型 G 的可滿足性定義有 G,x╞α .
歸納部分:
當 α 是 β ∧γ 的形式時候,假若 G,x╞α ,由可滿足性的定義有, 存在二部圖 G∈G 使得,x與 α 有邊相連.由 G 的構造定義有,存在二部圖 G1∈G 與二部圖 G2∈G 使得 G 由它們利用并構造而得到的,并且在二部圖 G1中 x 與 β 有邊相連,在二部圖 G2中 x 與 γ 有邊相連,于是 G,x╞β ,并且G,x╞γ ,由歸納假設就有 M,x╞β 并且,M,x╞γ ,于是由合式公式 α 關于模型 M 在 x∈U 可滿足性的定義有 M,x╞β ∧γ 即 M,x╞α .反之假設 M,x╞α , 由合式公式 α 關于模型 M 在 x∈U可滿足性的定義有 M,x╞β ∧γ 即有 M,x╞β 并且,M,x╞γ ,由歸納假設就有 G,x╞β ,并且 G,x╞γ 于是由 G 的定義有,存在二部圖 G1∈G 與二部圖 G2∈G 使得在二部圖 G1中 x 與 β 有邊相連,在二部圖 G2中 x 與 γ 有邊相連,兩個二部圖使得, x 與 β 在其中一個二部圖中有邊相連,x 與 γ 在另一個二部圖中有邊相連,于是由 G 的構造定義有,存在一個并構造的二部圖 G∈G 使得 x 與 α 有邊相連,于是由模型 G 的可滿足性定義有 G,x╞α .
當 α 是 β ∨γ 的形式時候,假若 G,x╞α ,由可滿足性的定義有, 存在二部圖 G∈G 使得,x與 α 有邊相連.由 G 的構造定義有,存在二部圖 G1∈G 與二部圖 G2∈G 使得 G 由它們利用或構造而得到的,在二部圖 G1中 x 與 β 有邊相連,或者在二部圖 G2中 x 與 γ 有邊相連,于是 G,x╞β ,或者G,x╞γ ,由歸納假設就有 M,x╞β 或者,M,x╞γ ,于是由合式公式 α 關于模型 M 在 x∈U 可滿足性的定義有 M,x╞β 或者,M,x╞γ ,即有 M,x╞β ∨γ .反之假設 M,x╞α , 由合式公式 α關于模型 M 在 x∈U 可滿足性的定義有 M,x╞β 或者,M,x╞γ ,由歸納假設就有 G,x╞β \\(即是由可滿足性的定義有,存在二部圖 G1∈G 使得在二部圖 G1中 x 與 β 有邊相連\\),或者 G,x╞γ \\(即是由可滿足性的定義有,存在二部圖 G2∈G 中 x 與 γ 有邊相連\\),于是由 G 的構造定義有,存在一個或構造的二部圖 G∈G 使得 x 與 β ∨γ 有邊相連,即 x 與 α 有邊相連,于是由模型 G 的可滿足性定義有 G,x╞α .
當 α 是 β 的形式時候,假若 G,x╞α ,由可滿足性的定義有, 存在二部圖 G∈G 使得,x 與α 有邊相連.由 G 的構造定義有,存在二部圖 G'∈G 使得,在這個二部圖 x 與 β 無邊相連\\(即,非G,x╞β \\),二部圖 G 由它翻轉構造而得到.于是,非 G,x╞β ,由歸納假設就有非 M,x╞β ,于是由合式公式 α 關于模型 M 在 x∈U 可滿足性的定義有 M,x╞ β 即 M,x╞α .反之假設 M,x╞α ,由合式公式 α 關于模型 M 在 x∈U 可滿足性的定義有 M,x╞ β 即有非 M,x╞β ,由歸納假設就有非 G,x╞β ,由可滿足性定義有,存在二部圖 G∈G 使得,x 與 α 無邊相連.我們對 G 使用翻轉構造得到二部圖 G'∈G,在這個二部圖 x 與 β 有邊相連由 G 的構造定義有,存在二部圖 G'∈G 使得, x與 β 在這個二部圖中有邊相連,于是由模型 G 的可滿足性定義有 G,x╞ β ,即,G,x╞α .綜上所述,這個結論得以證明.
3 決策邏輯的粗糙性
定義 13 決策邏輯 DL 的公式 α 關于決策邏輯 DL 系統的二部語義圖模型 G 在 W U 可滿足性定義如下:G,W╞α ,當且僅當,對于任意的 x∈W 有 G,x╞α .
定義 14 決策邏輯 DL 的公式 α 關于決策邏輯 DL 系統的二部語義圖模型 G 在 x∈W 對于屬性 a∈A,必然為真,記為 G,x╞ □aα ,如果 G,[x]Ga╞α .決策邏輯 DL 的公式 α 關于決策邏輯 DL系統的二部語義圖模型G在x∈W對于屬性a∈A,可能為真,記為G,x╞aα ,如果存在y∈[x]G a使得 G,y╞α .
由性質 2 知,一個二部圖 Ga實際上確定了對論域集合的一種劃分,因而上述定義是合理的.
定理 2 決策邏輯 DL的公式 α 關于決策邏輯 DL系統的二部語義圖模型G 在x∈U 對于屬性 a∈A,\\(1\\) G,x╞ □aα 當且僅當 G,x╞aα ;\\(2\\)G,x╞aα 當且僅當 G,x╞ □aα .
證明:\\(1\\)任意給定決策邏輯 DL 的公式 α ,決策邏輯 DL 系統的二部語義圖模型 G 中任給的 x∈U,對于給定的屬性 a∈A, G,x╞ □aα ,當且僅當,G,[x]G a╞α .當且僅當,對于任意的 y∈[x]G a在二部圖 Ga∈G 中 y 與 α 有邊相連\\(y 與 α 無邊相連\\).Ga,y╞ α 不成立,于是 Ga,x╞aα 不成立,即 G,x╞aα .
另一方面 G,x╞aα 當且僅當,存在存在二部圖 G∈G 使得,x 與aα 有邊相連.當且僅當,存在二部圖 G'∈G 使得,在這個二部圖 x 與aα 無邊相連,二部圖 G 由它翻轉構造而得到.由定理 1 有,當且僅當,G,x╞aα 不成立,按照可能真的定義,當且僅當,\\(存在 y∈[x]G a使得 G,y╞ α .\\)不成立,當且僅當,任意的 y∈[x]G a,G,y╞ α 不成立.當且僅當,任意的 y∈[x]G a在二部圖 Ga∈G 中 y 與 α 無邊相連.這與上面的當且僅當相同,所以該結論得證.
\\(2\\) 任意給定決策邏輯 DL 的公式 α ,決策邏輯 DL 系統的二部語義圖模型 G 中任給的 x∈U,對于給定的屬性 a∈A, G,x╞aα ,當且僅當,G,[x]G a╞α .當且僅當,對于存在 y∈[x]G a在二部圖 Ga∈G 中 y 與 α 有邊相連\\(y 與 α 無邊相連\\).由二部圖得構造知,對于任意的 y∈[x]G a,Ga,y╞ α 不成立,于是 Ga,x╞□aα 不成立,即 G,x╞ □aα .
另一方面 G,x╞ □aα 當且僅當,存在存在二部圖 G∈G 使得,x 與aα 有邊相連.當且僅當,存在二部圖 G'∈G 使得,在這個二部圖 x 與□aα 無邊相連,二部圖 G 由它翻轉構造而得到.由定理 1 有,當且僅當,G,x╞ □aα 不成立,按照可能真的定義,當且僅當,\\(任意 y∈[x]G a使得 G,y╞ α .\\)不成立,當且僅當,存在 y∈[x]G a,G,y╞ α 不成立.當且僅當,任意的 y∈[x]G a在二部圖 Ga∈G 中 y 與 α 無邊相連.這與上面的當且僅當相同,所以該結論得證.
在我們的這個模型中,還可以研究其他的關于粗糙性的結論.因為我們的模型和 Pawlak 給出的決策邏輯的模型等價,故可以得到很多類似于 Pawlak 書中給出的結論.這里就不一一贅敘.
參考文獻
[1]Bondy J.A, Murty U.R.Graph theory with applications[M].London: Macmillan, 1976.
[2]Pawlak Z.Rough Sets. Theoretical Aspects of Reasoning about Data[M].Kluwer Academic Publishers,Dordrecht, 1991.
[3] Pawlak Z .Rough sets[J]. Journal of Computer and Information Sciences, 1982,\\(11\\): 341-356.
[4]IwinskiT.B.Algebraic approach to rough sets[J]. Bulletin of the Polish Academy of Sciences Mathematics,1987, \\(35\\):673 -683.
[5]YaoY.Y.Two views of the theory of rough sets in finite universes[J].International Journal of ManagementApproximation Reasoning, 1996,15,\\( 4\\):291-317.
[6]Pawlak Z., Skowron A. Rough membership functions[M].Zadeh LA, Kacprzyk J eds. Fuzzy Logic for theof Uncertainty. New York: John Wiley & Sons, 1994:251-271.
[7]YaoY.Y, Wong S K M .A decision theoretic framework for approximating concepts[J]. InternationalJournal of M an -Machine Studies, 1992, 37: 793 -809.
[8]Banerjee M., Khan M. A. Propositional logics from rough set theory[M].Transactions on rough sets VI.Springer Berlin Heidelberg, 2007: 1-25.
[9]Kryszkiewicz M. Rough set approach to incomplete information systems[J].Information sciences,1998,112,\\(1\\): 39-49.
[10]Kryszkiewicz M.Rules in incomplete information systems[J].Information Sciences,1999:113,\\(3\\):271-292.
[11] Wu W.Z., M i J. S., Zhang W X. Generalized fuzzy rough sets[J].Information Sciences, 2003, \\(151\\):263-282.
[ 12] Liu G.L.,Zhu W.The algebraic structures of generalized rough set theory[J].Information Sciences, 2008,178,\\( 21\\) :4105- 4113.
[13]王國胤,姚一豫,于 洪.粗 集理論與應用研究綜述[J].計算機學報 2009, 32,\\(7\\):1229-1246.
