决策逻辑的二部图语义模型及其粗糙性

　　智能信息处理是当前信息科学理论和应用研究中的一个热点领域.由于计算机科学与技术的发展,特别是计算机网络的发展,每日每时为人们提供了大量的信息.信息量的不断增长,对信息分析的要求也越来越高,人们希望自动地从数据中获取其潜在的知识.特别是近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 是一个四元组<U,A,V,f>,其中 U 称为论域有穷集合,A 是有穷的属性集合,V=∪Va有穷的属性值集合,f:U×A→V=∪Va是一个函数.

　　定义 4[2]决策逻辑 DL 的一个模型是一个结构 M=<S,m>,m:P→2U.

　　有了定义 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,m(>其中信息系统 S 是一个四元组<U,A,V,f>的 f 如下给定:f(x,a)=v 当且仅当,在基本语义二部图 Ga∈G 中, x 与 av有边相连),则这两个模型等价,也即是对于任给的决策逻辑 DL 的公式 α 和 x∈U 有G,x╞α ,当且仅当,M,x╞α .

　　证明:首先易证信息系统 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.