基于一般二元关系的知识粗糙熵与粗集粗糙熵

2004年1月系统工程理论与实践第1期　文章编号:100026788(2004)0120093204基于一般二元关系的知识粗糙熵与粗集粗糙熵黄　兵,周献中,史迎春(南京理工大学自动化系1004教研室,江苏南京210094)摘要:　针对一般二元关系(自反的),通过引入知识粗糙熵来刻画知识的粗糙性和粗集粗糙性,为以一般二元关系为基础的信息系统中知识的获取提供了理论依据.关键词:　等价关系;二元关系;粗糙熵中图分类号:　T P18 文献标识码:　A En tropy of Know ledge and Rough Set Based onGeneral B inary R elati onHU AN G B ing,ZHOU X ian2zhong,SH I Y ing2chun(D epartm en t of A u tom ati on,N an jing U n iversity of Science and T echno logy,N angjing210094,Ch ina)Abstract:　In th is paper,the roughness of know ledge and rough set is deno ted by their rough en tropyw ith respect to general b inary relati on,w h ich p rovides theo ry basis fo r know ledge acqu isiti on in info r2m ati on system s based on general b inary relati on.Key words:　equ ivalence relati on;b inary relati on;rough en tropy1　引言近年来,由Paw lak提出的用于处理不精确、不完全数据的粗集理论由于在诸多领域的成功运用而引起了各国学者的极大关注.粗集理论认为知识即为分类能力,分类能力越强知识愈丰富.经典粗集理论以等价关系(自反性、对称性、传递性)为基础,通过等价关系对论域进行划分,而知识即表现为等价关系对论域划分的结果,划分越细,知识越精确,则粒度越小,从而又将知识与粒度紧密联系在一起.为描述知识不确定性,粗集理论通过引入上、下近似运算来逼近论域U中的任一概念.即通过已知的信息来描述待识的概念.更进一步,在保持任一概念上、下近似不变(分类能力不变)的条件下通过求取核与约简挖掘出信息系统中潜在的、简洁的知识,从而为知识获取提供了一套全新的方法.粗集理论这种通过等价关系和集合包含关系定义知识粗糙性,其本质含义不易被理解,并且求取知识的所有约简和最小约简均为N P完全问题.苗夺谦[1-3]等人讨论了知识粗糙性与信息熵之间的关系,证明了熵与互信息对于由知识粗糙性定义的偏序“较细”均是单调下降的,并证明了在无决策信息系统中,知识约简在信息和代数两种不同表示下是等价的,从而从信息论角度刻画了粗集理论的本质;并据此提出了基于互信息的知识相对约简的启发式算法M I BA R K;指出该算法的复杂度是多项式的,通过实例说明在多数情况下该算法能得到决策表的最小约简.王国胤[4,5]等人通过比较粗集理论的代数观点和信息论观点,得到在一致性决策表中两种观点下的知识约简是等价的;而在不一致决策表中,信息论观点下的约简包括代数观点下的约简;并进一步得到了知识约简算法,该算法在大多数情形下也能找到最小约简.以上研究仍然基于经典粗集等价关系这样一个基础之上.在现实中,等价关系的要求过于严格,有时也是不必要的.这就极大地限制了经典粗集理论的应用.于是人们将等价关系放宽为相容关系[6](自反性、收稿日期:2003201202作者简介:黄兵(1972-),男,四川绵阳人,讲师,博士研究生,主要研究方向为粗集理论及其应用对称性)、相似关系[7](自反性、传递性),甚至为一般二元关系(一般要求满足自反性),并以此为基础重新定义概念的上下近似运算,从而极大地丰富了粗集理论的内涵,为粗集理论的应用拓宽了道路.梁吉业[8,9]等人在相容关系下通过引入信息熵建立了知识粗糙熵及粗集粗糙熵的概念,为不完备信息系统(基于相容关系)中知识获取提供了理论依据.本文主要讨论在一般二元关系下知识的粗糙熵及粗集的粗糙熵.借鉴熵的思想定义一种新的知识粗糙熵;证明该熵是等价关系下粗糙熵的推广;得到随分辨能力的增强,知识粗糙熵和粗集粗糙熵均是单调下降的结论.为一般二元关系下认识粗集理论的本质,从信息角度给出合理解释,为进一步在一般二元关系下知识的获取提供理论依据.2　等价关系下知识的信息熵与粗糙熵定义2.1　U 为论域,等价关系P 对U 的划分为P ={X 1,X 2,…,X k },则P 的信息熵定义为:E (P )=-6ki =1 X i U log 2 X i UX i 、 U 分别表示X i 、U 的基数.信息熵度量了信源提供的平均信息量的大小.由定义可得:E (P )取最大值log 2 U α]X i ={x i }1Φi Φk = U ;E (P )取最小值0α]X 1=U ,即U 中所有元在P 下均是不可分辨的.由E (P )=6ki =1 X i U log 2 U -6k i =1 X i Ulog 2 X i =log 2 U -6k i =1 X i U log 2 X i ,定义P 的粗糙熵如下:E R (P )=6ki =1 X i Ulog 2 X i 显然E (P )+E R (P )=log 2 U .E R (P )描述了P 的不精确(粗糙)程度.3　基于一般二元关系的知识粗糙熵与粗集粗糙熵3.1　基于一般二元关系的知识粗糙熵基于等价关系的知识信息熵及粗糙熵利用等价关系对论域的划分进行定义,如果将等价关系放宽为相容关系或相似关系后,相容类或相似类不再构成对论域的划分而变成覆盖,即各相容类或相似类之间可能存在交叠.在一般二元关系下同样也存在这样的问题.因此,如果仍然利用分块大小来衡量知识的信息量大小或知识的粗糙性就不再恰当.在等价关系下,如果我们将每一个对象单独看待,将它所在的等价类看作它的邻域,那么一个对象在所有邻域中出现的次数即为它所在等价类元素的个数.它出现的次数越高,那么它所在的等价类的对象就越多,该等价类所构成的块就越大,即粒度就越大,分辨能力就越弱;反之亦然.基于这种考虑,我们可以利用论域中任一对象在一般二元关系构成的所有对象的邻域中出现的次数来定义知识的粗糙熵.定义3.1.1　对信息系统S =(U ,A ),U ={x 1,x 2,…,x U },P ΑA ,n P 表示在P 下的邻域算子.n P (x i )表示在知识P 下x i 的一般二元关系邻域,且x i ∈n P (x i ),i =1,2,…, U , x i P = {n P (x j ) x i ∈n P (x j ),1Φj Φ U } ,即x i 在所有元x j (1Φj Φ U )的邻域中出现的次数,则知识P 的粗糙熵定义为:E R (n P )=1 U 6 U i =1log 2 x i P 性质3.1.1　若n P 是在P 下的等价关系,则E R (n P )=E R (P ).证明　由于n P 是在P 下的等价关系,则x i 所在的等价类即为n P (x i ),共有 x i P 个元属于n P (x i ),设共有k 个不同的等价类{X 1,X 2,…,X k },则E R (n P )=1 U 6 U i =1log 2 x i P =1 U 6k j =1 X j log 2 X j =E R (P )49系统工程理论与实践2004年1月 性质3.1.1告诉我们,等价关系下知识粗糙熵是一般二元关系下知识粗糙熵的特殊情形.性质3.1.2　E R (n P )取最大值log 2 U α]n P (x i )=U ,1Φi Φ U ;E R (n P )取最小值0α]n P (x i )={x i },1Φi Φ U .由性质3.1.2:如果关系n P 在知识P 下不能区分论域U 中任意两个对象,那么知识P 的粗糙性最大;如果关系n P 在知识P 下能够区分论域U 中任意对象,那么知识P 达到最精确程度.这与直观是完全一致的.性质3.1.3　对信息系统S =(U ,A ),U ={x 1,x 2,…,x U }.P ,Q ΑA .若存在一个一一映射h :U →U ,使 h (x i ) Q = x i P ,1Φi Φ U ,则E R (n P )=E R (n Q ).我们称性质3.1.3为知识粗糙熵的不变性.性质3.1.4　对信息系统S =(U ,A ),U ={x 1,x 2,…,x U },P ,Q ΑA ,若邻域算子是对称的,且存在一个一一映射h :{n P (x i ) 1Φi Φ U }→{n Q (x j ) 1Φj Φ U },使得: h (n p (x i )) = n P (x i ) ,1Φi Φ U ,则:E R (n P )=E R (n Q ) 证明　只需证明:对任意x i ∈U ,ϖx j ∈U ,使 x i P = x j Q .由对称性知 x i P = n P (x i ) ,并且 h (n P (x i )) = n P (x i ) ,1Φi Φ U ,故存在x j ∈U ,使h (n P (x i ))=n Q (x j ),满足: x j Q = n Q (x j ) = h (n P (x i )) = n P (x i ) = x i P .由h 的一一性知:6 Ui =1log 2 x i P =6 U j =1log 2 x j Q ,即E R (n P )=E R (n Q ).由性质3.1.4知:在相容关系下,知识分块的大小相同,则知识的粗糙熵相等,即在相容关系下,新定义的知识粗糙熵从粒度角度刻画了知识的粗糙程度.性质3.1.5　对信息系统S =(U ,A ),U ={x 1,x 2,…,x U }P ,Q ΑA ,n P (x i )Αn Q (x i ),1Φi Φ U ,则:E R (n P )ΦE R (n Q )即知识粗糙熵随分辨能力的增强而单调减少.证明　由知识粗糙熵定义直接得.推论　设信息系统S =(U ,A ),P ,Q ΑA ,n P (x i )Αn Q (x i ),1Φi Φ U ,若存在一个x i 0∈U 使n P (x i 0)<n Q (x i 0),则E R (n P )<E R (n Q ).3.2　粗糙集的粗糙熵粗糙集的粗糙性可以用粗糙度来度量.定义3.2.1[11]　设信息系统S =(U ,A ),P ΑA ,X ΑU 在知识P 下的粗糙度定义如下:ΘP (X )=1- P (X 3) P (X 3)其中P (X 3),P (X 3)分别表示X 在一般二元关系下关于知识P 的下、上近似集.例1　设信息系统S =(U ,A ),P ,Q ΑA ,n P (U )={{x 1,x 2},{x 2,x 3,x 4},{x 3,x 4},{x 3,x 4}},n Q (U )={{x 1},{x 2,x 3},{x 3},{x 4}},X ={x 1,x 2},则P (X 3)={x i n P (x i )ΑX }={x 1}=Q (X 3)={x in Q (x i )ΑX },P (X 3)={x i n P (x i )∩X ≠<}={x 1,x 2}=Q (X 3)={x i n Q (x i )∩X ≠<}.故:ΘP (X )=ΘP (X )=1 2.例1中知识P 比Q 不确定性更大.但对X 却有相同的粗糙度.因此有必要寻求一种更精确的粗集不确定性度量.为此,我们引入粗糙集的粗糙熵定义.定义3.2.1　设信息系统S =(U ,A ),P ΑA ,X ΑU 在知识P 下的粗糙熵定义如下:E P (X )=ΘP (X )E R (n P ) 由上述定义,粗集的粗糙熵不仅与粗集本身的粗糙度有关,还与论域的知识的不确定性(知识的粗糙熵)有关.例2　对例1分别计算X 在知识P 、Q 下的粗糙熵:59第1期基于一般二元关系的知识粗糙熵与粗集粗糙熵E p(X)=ΘP(X)E R(n P)=(1+2l og23) 8,E Q(X)=ΘQ(X)E R(n Q)=1 8,E P(X)>E Q(X)可见,粗糙集的粗糙熵比粗糙度更精确地度量了粗集的粗糙性.性质3.2.1　设信息系统S=(U,A),P,QΑA,n P(x i)Αn Q(x i),1ΦiΦ U ,XΑU,则:E P(X)ΦE Q(X) 证明　只需证明:P(X3)ΒQ(X3),P(X3)ΑQ(X3).Πx∈Q(X3),则n Q(x)ΑX,由n P(x)Αn Q(x)知:x∈P(X3),故P(X3)ΒQ(X3);Πx∈P(X3),则n P(x)∩X≠<,由n P(x)Αn Q(x)知:n Q(x)∩X≠<,即x∈Q(X3)故P(X3)ΑQ(X3).故: P(X3) P(X3) ΕQ(X3) Q(X3) ,1- P(X3)P(X3) Φ1-Q(X3)Q(X3) ,即ΘP(X)ΦΘQ(X).又由性质3.1.5有E R(n P)ΦE R(n Q),所以:ΘP(X)E R(n P)ΦΘQ(X)E R(n Q).即E P(X)ΦE Q(X).由性质3.2.1知,粗集的粗糙熵随一般二元关系分辨能力的增强而单调下降.推论　设信息系统S=(U,A),P,QΑA,n P(x i)Αn Q(x i),1ΦiΦ U ,若存在一个x i0∈U,使n P(x i)<n Q(x i),XΑU是Q的粗糙集,则:E P(X)<E Q(X).4　结论本文在一般二元关系下通过引入信息熵,给出了在一般二元关系下知识粗糙熵定义及重要性质.证明了知识的粗糙熵随着知识确定程度的增强而单调下降的结论,从而给出了知识粗糙性在一般二元关系下的信息解释.结合知识的粗糙熵与粗集的粗糙度给出了粗集粗糙熵定义,并证明了粗集的粗糙熵也是随着知识确定程度的增强而单调下降的结论.并说明粗糙集的粗糙熵是比粗糙度更精确的度量.这些结论为在一般二元关系下知识的获取奠定了一定的理论基础.参考文献:[1]　苗夺谦,王珏.粗糙集理论中知识粗糙性与信息熵关系的讨论[J].模式识别与人工智能,1998,11(3):34-40.[2]　苗夺谦,王珏.粗糙集理论中概念与运算的信息表示[J].软件学报,1999,10(2):113-116.[3]　苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684.[4]　W ang G Y.A lgeb ra view and info rm ati on view of rough sets theo ry[A].D ata M in ing and Know ledge D iscovery:T heo ry,Too ls,and T echno logy ,P roceedings of SP IE[C],2001,4384:200-207.[5]　Hong Yu,Guoyin W ang,D achun Yang,Zhongfu W u.Know ledge reducti on algo rithm s based on rough set and con2diti onal info rm ati on en tropy[A].D ata M in ing and Know ledge D iscovery:T heo ry,Too ls,and T echno logy ,P ro2 ceedings of SP IE[C],2002,4730:422-431.[6]　K ryszk iew iczM.Rough set app roach to incomp lete info rm ati on system s[J].Info rm ati on Sciences,1998,112:39-49.[7]　Slow in sk i R,V snderpoo ten D.A generalized defin iti on of rough app rox i m ati on s based on si m ilarity[J].IEEE T ran son D ata and Know ledge Engineering,2000,12(2):331-336.[8]　L iang J i2ye,Q u rm ati on m easu res of roughness of know ledge and rough set fo r incomp lete system s[J].Jou rnal of System s Science and System s Engineering,2001,10(4):418-424.[9]　L iang J i2ye,Xu Zong2ben.T he algo rithm on know ledge reducti on in incomp lete info rm ati on system s[J].In terna2ti onal Jou rnal of U ncertain ty,Fuzziness and Know ledge2based System s,2002,10(10):95-103.[10]　V o D un tsch,Gun ther Gediga.U ncertain ty m easu res of rough set p redicti on[J].A rtificial In telligence,1998,106(1):109-137.[11]　张文修,吴伟志,梁吉业,李德玉.粗糙集理论与方法[M].北京:科学出版社,2001.69系统工程理论与实践2004年1月。