信息量的不完备信息系统属性约简方法

2007年5月　第30卷　第3期四川师范大学学报(自然科学版)Journal of Sichuan Nor mal University (Natural Science )May,2007Vol .30,No .3 收稿日期:2005-10-10基金项目:国家自然科学基金(60074014)资助项目作者简介:洪晓蕾(19812),女,硕士生;指导老师:莫智文(19632),男,教授集值不完备信息系统上的一种知识约简的方法洪晓蕾,　王　燕,　莫智文,　殷　璐(四川师范大学数学与软件科学学院,四川成都610066) 摘要:讨论了集值不完备系统上的两种基本关系:相容关系和拟序关系,论证得到了基于辨识矩阵的集值不完备系统知识约简的方法.在此基础上,讨论了知识约简的算法,并通过实例得到了证实.关键词:知识约简;相容;拟序;辨识矩阵中图分类号:O159 文献标识码:A 文章编号:100128395(2007)03202662040　引言粗糙集理论是上世纪80年代初由波兰学者Z .Pa wlak [1]提出的一种处理含糊和不精确性问题的数学工具.传统的粗糙集理论由于其定义的等价关系的严格性,已经不能满足实际工作的需要.在现实世界中由于种种原因,面临的信息系统往往是不完备的,如果能将传统粗糙集理论中的相关概念在不完备的信息系统中加以扩展,就可以直接进行处理,这样就能有效地分析和处理不精确、不一致、不完整等各种不完备信息,并从中发现隐含的知识,揭示潜在的规律.从数据本身获取情况来看,人们得到的数据本质上都是“近似值”.既然是近似值,从实际可用性角度考虑,就难于局限于取“单个值”,常常需要多次取值.由于客观条件限制和随机因素干扰,同一对象多次取值一般来说只是“相似”而不一定“相同”.在实际应用中,这些相似值往往一时难以确定取舍.由此就可能出现对象在某个确定属性上取得“多值”即“集值”的情形.基于粗糙集理论的应用技术发展迅速,应用范围也在不断扩大和深化,不完备信息系统就是其中重要课题之一[2].在不完备信息系统下,可以用属性集合间的相交关系和包含关系来定义论域U 上的相应关系,从而讨论其知识的发现和约简.本文主要讨论了多个属性集值的不完备信息系统下的一种新的知识约简.从这两类二元关系出发,定义了基于这两种关系的粗糙近似集合,得到了一些相关性质,随后利用辨识矩阵,论证得到了一类知识约简的方法,并给出参考算法,且通过实例来阐述说明所得到的主要结论.1　集值不完备信息系统及其相关性质和定理定义1　称(U,A T,F )为集值不完备信息系统,其中论域U 为非空有限集,属性集A T 也为非空有限集,F ={f l }为对象属性值映射,其中f l :U →P 0(V l ),V l 是属性a l 的值域,P 0(V l )表示V l 的非空子集的全体,其中P 0(V l )是由两部分组成V 0和{3},V 0为精确属性值域,3表示空值,空值代表不确定或无法确定但确实存在的值,假设3取值为相应属性值域中一切值.定义2[3]　对于二元关系R A ={(x,y )∈U ×U:f l (x )∩f l (y )≠ ,Πa l ∈A },记[x ]R A ={y ∈U:(x,y )∈R A }={y ∈U:f l (x )∩f l (y )≠ ,Πa l ∈A }.显然,在不完备信息系统中,令A ΑA T,由A 决定的容错关系[4]:S I M (A )={(x,y )∈U ×U:Πa l ∈A,f l (x )=f l (y )∨f l (x )=3∨f l (y )=3}也满足定义2中的二元关系.定义3[5]　对于A ΑA T,定义二元关系P A ={(x,y )∈U ×U:f l (x )Αf l (y ),Πa l ∈A },记[x ]P A ={y ∈U:(x,y )∈P A },[x ]-1P A ={y ∈U,(y,x )∈P A }.那么,二元关系R A 和P A 有如下性质:(1)R A 是自反的,对称的,不一定是传递的,故为相容关系;P A 是自反的和传递的,不一定是对称的和反对称的,故为拟序关系.它们在一般情况下都不是等价关系.(2)当A 1ΑA 2ΑA T 时,R A T ΑR A 2ΑR A 1,P A TΑP A 2ΑP A 1.(3)当A 1ΑA 2ΑA T 时,[x ]R A T Α[x ]R A 2Α[x ]R A 1,[x ]P A T Α[x ]P A 2Α[x ]P A 1,[x ]-1P A T Α[x ]-1P A2Α[x ]-1P A 1.(4)G 1={[x ]R A :x ∈U },G 2={[x ]P A :x ∈U },G 3={[x ]-1P A:x ∈U }都是U 的覆盖.定义4　设(U,A T,F )是集值不完备信息系统,ΠA ΑA T,ΠX ΑU,记:R A (X )={x ∈U |[x ]R A ΑX },R A (X )={x ∈U |[x ]R A ∩X ≠ }.R A (X )和R A (X )分别称为X 在相容关系R 下关于属性A 的下近似和上近似.定义5[5]　设(U,A T,F )是集值不完备信息系统,ΠA ΑA T,ΠX ΑU,记:P A (X )={x |x ∈U,[x ]P A ΑX },P A (X )=∪{[x ]-1P A|x ∈X }.P A (X )和P A (X )分别称为X 在拟序关系P 下关于属性A 的下近似和上近似.定理1　设(U,A T,F )是集值不完备信息系统,ΠA ΑA T,ΠX,Y ΑU,有:(1)R A (X )=～R A (～X ),R A (X )=～R A (～X );(2)R A (U )=U,R A ( )= ;(3)R A (X ∩Y )=R A (X )∩R A (Y ),R A (X ∪Y )=R A (X )∪R A (Y );(4)X ΑY,则有:R A (X )ΑR A (Y ),R A (X )ΑR A (Y );(5)R A (X )∪R A (Y )ΑR A (X ∪Y ),R A (X ∩Y )ΑR A (X )∩R A (Y );(6)R A (X )ΑX ΑR A (X );(7)R A (X )ΒR A (R A (X )),R A (X )ΑR A (R A (X )).证明　直接由定义可得.以上7条定理,对于二元关系P A 也同样成立,限于篇幅,这里就不一一列举了.在传统的粗糙集中近似算子的定义有两种主要形式,并且两种定义等价.(i )R (X )={x ∈U |[x ]ΑX },R (X )={x ∈U |[x ]∩X ≠ };(ii )R (X )=∪{[x ]∈U |[x ]ΑX },R (X )=∪{[x ]∈U |[x ]∩X ≠ }.但在相容关系下,两者不等价,试举例说明.例　图1是一集值不完备信息系统.U a 1a 2a 3a 4x 1{0,1}{1}{1}{0,1}x 2{0}3{1}{0}x 33{2}3{0,1}x 4{1}3{0,1}{0,1}x 53{1,2}{0,1}{0,1}x 6{0}{3}{1}3图1　集值不完备信息系统F i g .1　A set 2va lued i n com plete i n for ma ti on syste mU ={x 1,x 2,x 3,x 4,x 5,x 6},A T ={a 1,a 2,a 3,a 4},取A ={a 1,a 2},则:[x 1]R A ={x 1,x 2,x 4,x 5},[x 2]R A ={x 1,x 2,x 3,x 5,x 6},[x 3]R A ={x 2,x 3,x 4,x 5},[x 4]R A ={x 1,x 3,x 4,x 5},[x 5]R A ={x 1,x 2,x 3,x 4,x 5},[x 6]R A ={x 2,x 6}.取X ={x 1,x 3,x 4,x 5,x 6},则R A (X )={x 4},∪{[x ]R A |[x ]R A ΑX }={x 1,x 3,x 4,x 5}.明显看出R A (X )=∪{[x ]∈U |[x ]ΑX }不成立,同时R A (X )≠R A (R A (X )).取X ={x 1,x 3,x 4,x 5},则R A (X )={x 1,x 2,x 3,x 4,x 5},∪{[x ]R A |[x ]R A ∩X ≠ }={x 1,x 3,x 4,x 5}.明显看出R A (X )=∪{[x ]∈U |[x ]∩X ≠}不成立,同时R A (X )≠R A (R A (X )).取B ={a 1,a 2,a 4},则:[x 1]P B ={x 1,x 5},[x 2]P B ={x 2},[x 3]P B ={x 3,x 5},[x 4]P B ={x 4},[x 5]P B ={x 5},[x 6]P B ={x 6}.2　集值不完备信息系统的知识约简定义6　设(U,A T,F )是集值不完备信息系统,A ΑA T:(1)R A =R A T ,　(2)ΠB ΑA,R B ≠R A T ;(1′)P A =P A T ,　(2′)ΠB ΑA,P B ≠P A T .分别称A 是信息系统中在相容关系R 和拟序关系P 下的约简.当所有的约简的非空交非空时,则称此非空集为信息系统在相应关系下的核.由于关系R 和P 都满足:当A 1ΑA 2ΑA T 时,R A T ΑR A 2ΑR A 1,P A T ΑP A 2ΑP A 1成立,所以定义6′为定义6的等价表述.定义6′　设(U,A T,F )是集值不完备信息系统,ΠA ΑA T:762　第3期洪晓蕾等:集值不完备信息系统上的一种知识约简的方法 (1)RA=R A T,　(2)Πa∈A,R A-{a}≠R A;(1′)P A=P A T,　(2′)Πa∈A,P A-{a}≠P A.定理2[6]　对于任何信息系统(U,A T,F)约简总是存在的.由上例可知:RA =R A T,且R{a1}≠RA,R{a2}≠R A,故{a1,a2}是该信息系统在R下的一个约简;P B=P A T,且P{a1,a2}≠PB,P{a1,a4}≠PB,P{a2,a4}≠PB,故{a1,a2,a4}是该信息系统在P下的一个约简.定义7　设(U,A T,F)是集值不完备信息系统,在相容关系R下,记D(xi,x j)={a l∈A T, f l(x i)∩f l(x j)= },显然D(x i,x j)=D(x j,x i);在拟序关系P下,记D(xi,x j)={a l∈A T,f l(x i)⁄f l(x j)},它们称为集值不完备信息系统在相应关系下的辨识矩阵.记D={D(x i,x j):D(x i,x j)≠ }.定理3　设(U,A T,F)是集值不完备信息系统,ΠAΑA T,在相容关系R下(1)和(3)等价,在拟序关系P下(2)和(3)等价:(1)RA=R A T;(2)PA=P A T;(3)ΠD∈D0,A∩D≠ (其中D为相应二元关系下的辨识矩阵).证明　(1)](3):ΠD∈D,D(x i,x j)={a l∈A T,f l(x i)∩f l(x j)= }≠ ,则xj[x i]AT,由于R A=R AT,有[x i]AT=[x i]A,则xj[x i]A,即:ϖa l∈A,满足f l(x i)∩f l(x j)= ,所以A∩D≠ .(3)](1):ΠD∈D0,A∩D≠ ,任取a l∈A∩D,有:al ∈A T,且fl(xi)∩f l(x j)= ,即:xj[x i]A T,又a l∈A,同时f l(x i)∩f l(x j)= 成立,即xj[x i]A,则[x i]A TΒ[x i]A,又因为AΑA T,则[x i]A TΑ[x i]A,所以[x i]A=[x i]A T,故R A=R A T.(2)](3):ΠD∈D0,D={a l∈A T,f l(x i)⁄f l(x j)}≠ ,所以(x i,x j)PA T,由(2)P A T=P A,又有(xi ,x j)PA,即:ϖa l∈A,满足f l(x i)⁄f l(x j),故有A∩D≠ .(3)](2):ΠD∈D0,A∩D≠ ,任取a l∈A∩D,有al ∈A T,且fl(xi)⁄f l(x j),即(x i,x j)PA T.又al ∈A,同时fl(xi)⁄f l(x j)成立,即:(x i,x j)P A,所以P AΑP A T.又因为AΑA T,则P AΒP A T,故P A=P A T.证毕我们可以得到判断约简的另一类方法.定理4　设(U,A T,F)是集值不完备信息系统,ΠAΑA T,A在相容关系R下和拟序关系P下的约简,当且仅当它们满足以下条件:(1)ΠD∈D0,A∩D≠ ,(2)Πa l∈A存在D∈D0,使(A-{a l})∩D = .其中D为相应二元关系下的辨识矩阵.证明　由定理3和约简的定义直接可得.3　知识约简算法及相关实例此方法在解决实际问题上具有可操作性,从上面理论可以看出它有两个关键步骤:一是求出它的辨识矩阵,二是利用定理4的两条法则,从辨识矩阵中挖掘出相应的约简.以下为算法:输入:一个集值不完备信息系统(U,A T,F)各项数据.输出:该信息系统的一个知识约简A.(1)计算D(x i,x j),作出D0,并求出∪D0.(2)取A为D0的单元素集的并.(3)判断如下两个条件:〈1〉ΠD∈D0,A∩D≠ ;〈2〉Πa l∈A,ϖD∈D0,有(A\{a l})∩D= .(4)满足则输出A.(5)不满足,则A=A∪{a lj},遍取a lj∈(∪D0)\A,j=1,2,...,k,k为(∪D0)\A中的个数.(6)判断如下两个条件:〈1〉ΠD∈D0,A∩D≠ ;〈2〉Πa l∈A,ϖD∈D0,有(A\{a l})∩D= .(7)满足则输出A.(8)不满足,则A=A\{a lj}∪{a li},a li∈(∪D0)\A,i=1,2,...,k,且a li≠al j,转(3).此算法收敛,因为约简总是存在的[4].图2和图3分别给出了由前例产生的相容关系和拟序关系下的辨识矩阵.U x1x2x3x4x5x6x1{a2}{a2}x2{a1}x3{a2}{a2}x4{a1}{a1}x5{a2}x6{a2}{a2}{a1}{a2}图2　相容关系下的辨识矩阵F i g.2　D iscern i b ility ma tr i x ba sed on tolerance rel a ti onD0={{a1},{a2}},对于A={a1,a2}.显然A∩D≠ ,且{a1}∩{a2}= ,所以A是该系统在相容关系下的一个约简,即{a1,a2}.862 四川师范大学学报(自然科学版) 30卷 U x 1x 2x 3x 4x 5x 6x 1{a 1,a 4}{a 2}{a 1}{a 1,a 2}x 2{a 2}{a 2}{a 1}{a 2}{a 2}x 3{a 2,a 3}{a 1,a 3,a 4}{a 1}{a 1,a 2,a 3}x 4{a 2,a 3}{a 1,a 3,a 4}{a 2}{a 2}{a 1,a 2,a 3}x 5{a 2,a 3}{a 1,a 3,a 4}{a 2}{a 1}{a 1,a 2,a 3}x 6{a 2}{a 4}{a 2}{a 1}{a 2}图3　拟序关系下的辨识矩阵F i g .3　D iscern i b ility ma tr i x ba sed on preorder rel a ti onD 0={{a 1},{a 2},{a 4},{a 1,a 2},{a 2,a 3},{a 1,a 3,a 4},{a 1,a 2,a 3}},对于B ={a 1,a 2,a 4},显然B ∩D ≠ ,且{a 1,a 2}∩{a 4}= ,{a 1,a 4}∩{a 2}= ,{a 2,a 4}∩{a 1}= ,所以B 是该系统在拟序关系下的一个约简,即{a 1,a 2,a 4}.以上两项结果均与由约简定义分析的结果一致.4　结语知识库中存在的冗余的知识,不仅会造成资源的浪费,而且会干扰人们做出正确的判断,因此,知识约简一直是粗糙集理论的核心内容之一.本文从集值不完备信息系统中两类二元关系出发,依照这些关系给出了相应的近似集合,然后利用辨识矩阵给出了集值不完备信息系统的知识约简的方法.由于是将传统粗糙集模型中的等价关系推广到了相容关系和拟序关系,因而在实际工作中具有更广泛的应用价值.参考文献[1]Pa wlak Z .Rough set[J ].I nt J Computer and I nf or mati on Sci,1982(11):3412356.[2]Sl owinski R,Vander pooten D.A generalized definiti on of r ough app r oxi m ati ons based on si m ilarity [J ].I EEE Transacti on onKnowledge and Data Engineering,2000,12(2):3312336.[3]王虹,张文修,李鸿儒.集值信息系统的知识发现与约简[J ].计算机工程与应用,2005(6):37238.[4]M arzena K .Rough set app r oach t o incomp lete inf or mati on syste m [J ].J I nf or Sci,1998,112:39249.[5]吴陈,杨习贝,傅凡,等.基于属性集值不完备信息系统的Rough 集方法[J ].计算机工程与应用,2005(3):1782180.[6]张文修,梁怡,吴伟志.信息系统与知识发现[M ].北京:科学出版社,2003.A Method of Knowledge Reducti on in Set 2valued Incomp lete I nfor mati on SystemHONG Xiao 2lei,　WANG Yan,　MO Zhi 2wen,　YI N Lu(College of M athe m atics and Soft w are Science,S ichuan N or m al U niversity,Chengdu 610066,S ichuan )Abstract:I n this paper t w o kinds of relati ons on set 2valued incomp lete infor mati on syste m are discussed:t olerance relati on and p reorder relati on .The methods of knowledge reducti on based on discernibility matrices are obtained .An algorith m of knowledge reduc 2ti on is described .Key words:Knowledge reducti on;Tolerance;Preorder;D iscernibility matrix 2000M SC:03E72(编辑　余　毅)962　第3期洪晓蕾等:集值不完备信息系统上的一种知识约简的方法。

属性约简方法概述属性约简又称维规约或特征选择，从数学的角度考虑，就是有p 维数据 x =(x 1,x 2……x p )，通过某种方法，得到新的数据 x’=(x’1,x’2…… x’k ) , k ≤p , 新的数据在某种评判标准下，最大限度地保留原始数据的特征。

属性约简主要是为了解决高维数据计算的复杂性和准确性问题。

目标是消除冗余和不相关属性对计算过程和最终结果造成的影响。

对数据进行属性约简的意义，主要从以下几个方面考虑：a) 从机器学习的角度来看，通过属性约简去除噪音属性是非常有意义的； b) 对一些学习算法来说，训练或分类时间随着数据维数的增加而增加，经过属性约简可以降低计算复杂度，减少计算时间；c) 假如不进行属性约简，噪音或不相关属性和期望属性对分类的作用一样，就会对最终结果产生负面影响；d) 当用较多的特征来描述数据时，数据均值表现得更加相似，难以区分。

为了描述属性约简方法，这里假设数据集合为D ，D ={x 1,x 2….x n }, x i 表示D 中第i 个实例，1≤i≤n ，n 为总的实例个数。

每个实例包含p 个属性{|x i |=p }。

从机器学习的角度来看，属性约简方法可以分为监督的和非监督的两类。

下面是几种常用的方法。

(1) PCA 主成分分析主成分概念是Karl parson 于1901年最先引进。

1933年，Hotelling 把它推广到随机变量。

主成分分析把高维空间的问题转换到低维空间来处理，有效的降低了计算的复杂度。

通过主成分的提取，降低了部分冗余属性的影响，提高了计算的精度。

主成分分析的基本思想为：借助一个正交变换，将分量相关的原随机变量转换成分量不相关的新变量。

从代数角度，即将原变量的协方差阵转换成对角阵；从几何角度，将原变量系统变换成新的正交系统，使之指向样本点散布最开的正交方向，进而对多维变量系统进行降维处理[43]。

定义4-1[44]：设12(,,...,)'p X X X X =为p 维随机向量，它的第i 主成分分量可表示'i i Y u X =，i =1,2,…, p 。

不完备贝叶斯决策信息系统的属性约简韩楠;舒畅;莫智文【摘要】在不完备贝叶斯决策信息系统中,改进全局增益函数,结合二进制分辨矩阵编码方法提出一种新的不完备贝叶斯决策信息系统启发式属性约简算法,并将其应用于系统的故障状况诊断研究中,该方法提高了约简的效率.%In incomplete Bayesian decision information system,this paper improves the global gain function,and combines with the coding method of binary discernibility matrix.A new heuristic attribute reduction algorithm is proposed.The method is applied to the study of the system of the fault condition's diagnosis,and improves the efficiency of reduction.【期刊名称】《四川师范大学学报（自然科学版）》【年(卷),期】2016(039)006【总页数】4页(P825-828)【关键词】不完备贝叶斯决策信息系统;二进制分辨矩阵;全局增益函数;属性约简【作者】韩楠;舒畅;莫智文【作者单位】四川师范大学数学与软件科学学院, 四川成都 610066;四川师范大学数学与软件科学学院, 四川成都 610066;四川师范大学数学与软件科学学院, 四川成都 610066【正文语种】中文【中图分类】TP301.6经典粗糙集是处理不确定和不精确问题的有效工具[1].由于经典粗糙集以等价关系为基础,只适用于完备信息系统.对于不完备信息系统[2-3],则不再适用.目前对不完备信息系统的处理方式有2种:1)将不完备信息系统通过某种方法转化为完备信息系统;2)将经典粗糙集进行拓展.目前常见的扩展模型有变精度、容差、限制容差、优势、模糊等粗糙集模型.经典粗糙集只考虑属性值之间的可区分关系,未考虑到偏好关系,因此并不能很好地在决策过程中表达原有的偏好信息.文献[4-5]研究了优势关系下决策信息系统,文献[6]提出了可变精度粗糙集模型,在经典粗糙集的基础上引进阈值β,允许一定程度上错误分类的存在,但在实际运用中变精度粗糙集也有其局限性.文献[7]结合贝叶斯推理提出贝叶斯粗糙集模型,贝叶斯粗糙集是一种修正的变精度粗糙集模型,将变精度粗糙集中精度参数用先验概率来替代,从而避免了变精度粗糙集中参数对约简过程带来的影响,同时贝叶斯理论与统计决策相结合形成的贝叶斯决策理论,在医疗和管理中起到了重要作用,因此本文对不完备贝叶斯决策信息系统进行属性约简,在限制容差关系分类模型的基础上,利用贝叶斯粗糙集模型,通过引入全局增益函数和二进制分辨矩阵,给出了不完备贝叶斯决策信息系统的启发式属性约简算法.1.1 不完备贝叶斯决策信息系统定义 1.1[8] 称一个四元组(U,A,V,f)为信息系统,其中U为有限非空对象集;A为有限非空属性集;V为属性值值域;f为对象属性值映射,即U={x1,x2,...,xn},A={a1,a2,...,ap},V=∪a∈AVa,Va为属性a的值域,f:U×A→V,且f(x,a)∈Va.如果至少有一个属性b∈A使得Vb含有空值,用“*”表示空值,则称S是不完备信息系统,否则称为完备信息系统.A=C∪D,C∩D=∅,C称为条件属性集,D称为决策属性集.V=∪Va,a∈A,Va是属性a的值域;f表示U×A→V的信息函数,为每个对象的每个属性赋予一个信息值,即∀a∈A,x∈U,f(x,a)∈Va,称这样具有条件属性和决策属性的信息系统为决策信息系统.定义 1.2[9] 在信息系统S=(U,A,V,f)中,U为非空有限论域,A为有限非空属性集,E 为U上的等价关系,对于目标集X⊆U有:贝叶斯正域为|[x]E)>P(X)};贝叶斯负域为|[x]E)<P(X)};贝叶斯边界域为|[x]E)=P(X)},其中,P(X)=|X|/|U|,P(X|[x]E)=|X∩[x]E|/|[x]E|.贝叶斯粗糙集是一种修正过的变精度粗糙集模型[10-11],用事件的先验概率代替变精度粗糙集参数,从而避免了变精度粗糙集中参数带来的影响.贝叶斯正域定义为U/A中所有元素集的集合出现的条件下X发生的概率大于先验概率,即贝叶斯正域中的任何事件都会增加事件X确定发生的程度.贝叶斯负域定义为U/A中所有元素集的集合出现的条件下X发生的概率小于先验概率,即贝叶斯正域中的任何事件都会减少事件X确定发生的程度.贝叶斯边界域定义为U/A中所有元素集的集合出现的条件下X发生的概率等于先验概率,即贝叶斯正域中的任何事件不会影响事件X 确定发生的程度.为了描述分类的特征,文献[9]中贝叶斯决策信息系统引入了置信增益函数.定义 1.3[9] 在信息系统S中,对于E⊆C,U/D=[x]d={X1,X2...,Xp},则称...,p}-1为E相对于决策属性D的全局相对增益函数,全局增益函数可以用来度量贝叶斯决策信息系统的属性重要度.1.2 限制容差关系模型定义 1.4[12] 设S=(U,C∪D,V,f)是一个不完备决策信息系统,对于具有空值的属性子集,记空值为“*”,B⊆U,定义U上的容差关系T(B)记为a(y)∨((a(x)=*∨a(y)=*)→f(x,b)=f(y,b))}.则可记TB(x)={y∈U:(x,y)∈T(B)}为x的限制容差类.定义 1.5[12] 设S=(U,C∪D,V,f)是一个不完备决策信息系统,对于X⊆U,B⊆C,在容差关系T(B)下,X的下上近似集分别定义为⊆X},∅}.由表1可知:U/D=[x]d={X1,X2}={(x1,x2,x5,x6),(x3,x4,x7,x8)}.按定义1.4将U中对象在属性集C下进行分类可得TC(x3)={x3,x7}, TC(x4)={x1,x2,x4,x5},TC(x5)={x1,x4,x5,x7}, TC(x6)={x6},TC(x7)={x3,x5,x7}, TC(x8)={x8}.经典的属性约简算法中分辨矩阵以条件属性集合作为矩阵元素,其空间复杂度高,处理效率低,所以将其优化为二进制的分辨矩阵[13-14].本文通过限制容差关系模型对不完备决策信息系统进行分类,利用二进制分辨矩阵对所有对象进行编码组合,找出论域中各对象组合的行所在的属性值为1的属性集,从而提高了查找约简集合的效率.根据二进制分辨矩阵找出的各行可能的约简属性集,利用新定义的全局增益函数来度量属性重要度,给出不完备贝叶斯决策信息系统的启发式属性约简算法.定义 2.1 在不完备决策信息系统S=(U,C∪D,V,f)中,定义其二进制分辨矩阵为在很多预测模型[15](如股票市场、医疗领域、系统故障等)中,其最终目的都是为了提高决策的确定性程度.而传统的Slezak贝叶斯粗糙集模型中提出的全局增益函数则反映了相对于先验概率确定性增加或者减小的程度,但未能反映通过决策得到所需要的论域中的对象集合,本文改进了传统全局增益函数,改进的全局增益函数可以通过决策属性得到所需对象集合.定义 2.2 设S=(U,C∪D,V,f)是一个不完备决策信息系统,对于∀B⊆C,U/D=[x]d={X1,X2,...,Xn},定义则RC(X)=∪iRC(Xi),称RC(X)为C相对于D 的全局相对增益函数.定义 2.3 设在不完备信息系统S中,对于∀X⊆U,B⊆C,若B是信息系统S的约简集,则必须满足下列条件:1) RC(X)=RB(X);2) 不存在A⊆B,使得RC(X)=RA(X).2.1 算法输入:不完备决策信息系统S=(U,C∪D,V,f),输出:不完备贝叶斯粗糙集的R 约简.1) 根据限制容差关系,计算U中全部对象的容差类中使用到的子域;2) 根据不完备决策表S构造二进制分辨矩阵M;3) 删除二进制分辨矩阵M中全为零的行;4) 将i记为二进制分辨矩阵第i行,令i=i+1,初始化i=0,若第i行属性值为1的条件属性集合B满足RC(X)=RB(X),则得出约简集B,否则继续下一行i=i+1,直到第i 行属性值为1的条件属性集合B满足RC(X)=RB(X),结束算法.2.2 算法实例分析表1为某系统的故障信息,其中U={x1,x2,x3,x4,x5,x6,x7,x8}表示被控制的对象,系统的故障状况由3个传感器进行信息反馈,表示为A={a1,a2,a3},传感器会反馈3种信号,即值域为Vc={1,2,3},控制系统的故障d有2种状态,即{1,2},已知的历史决策表如下所示,但因种种原因有部分信息缺失,缺失信息用*代替.根据决策,确定3个传感器反馈信号的重要程度.步骤 1 根据定义1.2和1.4得到在条件属性集下论域U中全部对象的限制容差类并计算目标事件Xi发生下,出现在限制容差类中对象的条件概率.P([x3]C|X1)=0, P([x4]C|X1)=3/4,P([x5]C|X1)=2/4, P([x6]C|X1)=1/4,P([x7]C|X1)=1/4, P([x8]C|X1)=0,P([x1]C|X2)=1/4, P([x2]C|X2)=1/4,P([x3]C|X2)=2/4, P([x4]C|X2)=1/4,P([x5]C|X2)=2/4, P([x6]C|X2)=0,P([x7]C|X2)=2/4, P([x8]C|X2)=1/4.步骤 2 由不完备决策表1,构造二进制分辨矩阵M,如表2所示,M为12×3阶矩阵.表2中最后一列为各行对象组合中属性值为1的集合.步骤 3 计算属性集C相对于D的全局相对增益函数RC(X),同时依据表2中二进制分辨矩阵得出的属性值为1的集合计算相应属性集合对应的全局相对增益函数. {x1,x2,x4,x5},RC(X2)={[x]c|max P([x]c|X2)}={x1,x3,x4,x5,x7},则RC(X)=∪iRC(Xi)={x1,x2,x3,x4,x5,x7}.由二进制表2可得,论域中对象组合属性值为1的集合为(a1,a3),(a1),(a1,a2),(a3),(a2).分别计算其限制容差类及全局相对增益函数,结果如下:Ta1,a2(x2)={x1,x2,x4,x5},Ta1,a2(x3)={x3,x5,x7},Ta1,a2(x4)={x1,x2,x4,x5},Ta1,a2(x5)={x1,x2,x3,x4,x5,x7},Ta1,a2(x6)={x6},Ta1,a2(x7)={x3,x5,x7},Ta1,a2(x8)={x8};P([x1]a1,a2|X1)=3/4,P([x2]a1,a2|X1)=3/4,P([x3]a1,a2|X1)=1/4,P([x4]a1,a2|X1)=3/4,P([x5]a1,a2|X1)=3/4,P([x6]a1,a2|X1)=1/4,P([x7]a1,a2|X1)=1/4,P([x8]a1,a2|X1)=0,P([x1]a1,a2|X2)=1/4,P([x2]a1,a2|X2)=1/4,P([x3]a1,a2|X2)=2/4,P([x4]a1,a2|X2)=1/4,P([x5]a1,a2|X2)=3/4,P([x6]a1,a2|X2)=0,P([x7]a1,a2|X2)=2/4,P([x8]a1,a2|X2)=1/4;Ra1,a2(X1)={[x]a1,a2|max P([x]a1,a2|X1)}= {x1,x2,x3,x4,x5,x7},Ra1,a2(X2)={[x]a1,a2|max P([x]a1,a2|X2)}= {x1,x2,x3,x4,x5,x7},则{x1,x2,x3,x4,x5,x7}.经计算可得RC(X)=Ra1,a2(X).由定义2.3可知{a1,a2}为属性集C的约简集.所以相对于3个传感器反馈的信号,{a1,a2}应重点考虑.本文在不完备决策信息系统的基础上,利用限制容差关系和贝叶斯粗糙集决策理论相结合,引入二进制区分矩阵和改进的全局增益函数,对不完备贝叶斯决策粗糙集进行属性约简,给出新的思路和方法,从而提高了不完备决策信息系统的约简效率.【相关文献】[1] 张文修,吴伟志,梁吉业. 粗糙集理论与方法[M]. 北京:科学出版社,2001.[2] 杨柳娇,莫智文. 几类不完备信息系统的属性约简[D]. 成都:四川师范大学,2014.[3] 王国胤. Rough集理论在不完备信息系统中的扩充[J]. 计算机研究与发展,2002,39(10):1238-1243.[4] 张辉. 优势关系下区间值决策信息系统一致性度量[J]. 计算机工程与设计,2013,34(12):4336-4339.[5] 王斌,邵明文,王金鹤. 基于改进的优势关系下的不完备区间值信息系统评估模型[J]. 计算机科学,2014,41(2):253-258.[6] 华伟,祁云嵩,王芳. 不完备目标信息系统中的可变精度粗糙集模型[J]. 江苏科技大学学报,2009,23(6):531-534.[7] DOMINIK S, WOJCIECH Z. The investigation of the Bayesian rough set model[J]. Inter J Approximate Reasoning,2005(40):81-91.[8] WANG X. Incomplete decision-theoretic rough set model based on improved complete tolerance relation[C]//Computer Engineering and Networking. NewYork:Springer International Publishing, 2014:273-280.[9] 蔡娜,张雪峰. 基于贝叶斯粗糙集模型的属性约简[J]. 计算机工程,2007,33(24):45-48.[10] 陈可,张小强,徐选华. 基于改进贝叶斯粗糙集和证据理论的决策信息融合方法[J]. 计算机应用研究,2014,31(9):2625-2628.[11] 韩敏,张俊杰,彭飞,等. 一种基于多决策类的贝叶斯粗糙集模型[J]. 控制与决策,2009,24(11):1615-1619.[12] 郭嗣琮,徐丽,郑爱红. 限制容差关系的不完备可变粗糙集[J]. 辽宁工程技术大学学报,2015,33(7):988-991.[13] 赵军,陈宸. 一种基于二进制分辨矩阵的属性约简新算法[J]. 重庆邮电大学学报,2012,24(4):490-494.[14] 陈宸,赵军. 一种新的基于二进制分辨矩阵的属性约简方法[J]. 计算机应用与软件,2013,30(9):123-127.[15] 张本文. 基于贝叶斯粗糙集的大数据频繁项挖掘技术[J]. 科技通报,2015,31(6):210-213. 2010 MSC：03F03。

不完备信息系统属性约简算法研究作者：***来源：《计算机时代》2020年第07期摘要：基于经典粗糙集，从不完备信息系统和相容类的相关概念出发，给出了不完备信息系统中相容类的算法和属性约简算法。

此算法将继续被研究以期降低其时间复杂度。

关键词：不完备信息系统;粗糙集;属性约简;相容类中图分类号：TP18 文献标识码：A 文章编号：1006-8228（2020）07-83-030引言自学者Pawlak于1982年提出粗糙集以来，粗糙集理论在机器学习、规则提取、决策支持等领域得到了广泛应用。

经典的粗糙集理论以完备的信息系统为研究对象，在处理数据时基于严格的等价关系来进行划分。

然而，在实际生产、生活和科学实践中，由于数据获取、数据保存技术等方面的限制，很多信息系统都会存在属性的缺省值，即遇到的绝大多数信息系统都是不完备的。

在文献（7）中作者为了能利用粗糙集来处理不完备的信息系统，提出以相容关系来分类，但遇到数据量比较大时，人为计算相容类耗时耗力，求属性约简更是耗时。

所以设计计算机算法来处理是十分关键的。

本文的安排如下：第一部分简要阐述不完备信息系统、完备信息系统及其约简集的相关概念;第二部分设计了计算不完备信息系统中相容类的算法;第三部分设计了计算不完备信息系统中属性约简集的算法;最后，给出了全文总结。

4结束语本文在相关定义和相容类的分类方法下，设計了处理不完备信息系统中分类和属性约简的计算机算法，极大地简化了计算量，在一定程度上能够有效地节省计算时间和研究者的精力。

本文只是在相容类情况下进行分类和属性约简算法的一个初步探索。

基于本文的结果，还可以深入研究分类和属性约简的算法，以进一步降低算法的时间复杂度。

粗糙集的研究对象是一个数据集，数据集一般被保存为数据表格形式，即数据库或信息系统。

信息系统的形式是由研究对象和属性值关系构成的二维数据表，类似于基础数学中的关系数据库。

信息系统实现了粗糙集模型的知识表示。

定义 2.1.1[46] 设(,,,)S U A V f =为一个数据库，即信息系统，也称为知识表示系统。

其中12{,}U U x x x = 为一个非空的有限对象集，12{,,}A A a a a = 是属性的有限非空集合，a V V =⋃，a A ∈，a V 为属性a 的值域；定义信息函数:U V c a f A ⨯→ .例如表2.1.1是一个信息系统，其中12345{,,,,}U x x x x x =，1234{,,,}A a a a a =，123a a a V V V ==={0,1}，4a V ={0,1,2}.表2.1.1 信息系统定义2.1.2[46] 对于a A ∀∈，x U ∀∈，(,)a f x a V ∈，对于P A ∀∅≠⊆，定义：{(,):(,)(,),}I x y U U f x q f y q q P =∈⨯=∀∈，I U 称为上的不可分辨关系。

(1)若(,)x y I ∈，则称：x y 和是不可分辨的。

(2)不可分辨关系是等价关系，具有：自反性：xIx ； 对称性：xIy yIx ⇒；传递性：,xIy yIz xIz ⇒ ．(3) I 是U 上的一个等价关系，[]{,}I x y y U xIy =∈，12{[]}{,}I k U I x x U X X X =∈= ，12,k X X X 称为U 关于I 的一个划分。

(4)P I ∅≠⊆,1,2I I I ∈, 112{,}k U I X X X = ,212{,}l U I Y Y Y = ,12{,1,2,1,2}i j U I I X Y i k j l ⋂=⋂== ,()I Pind P I P ∈== ，则称：()ind P U 是上的一个等价关系，称为P 上的不可区分关系。

不完备模糊多目标信息系统中的知识约简与获取研究的开题报告一、选题背景和意义多目标信息系统是指在解决某些问题时涉及到多个目标或指标，而这些目标或指标往往之间相互矛盾，难以综合考虑。

随着信息技术的发展，多目标信息系统逐渐广泛应用于决策支持、战略规划、风险评估、智能控制等领域中。

但是，由于多目标信息系统中存在不确定性、模糊性等问题，因此传统的数据挖掘、机器学习等技术难以很好地应对这些问题。

知识约简是一种重要的数据预处理技术，可以有效地减少数据维度和冗余，提高数据处理效率和精度。

在不完备模糊多目标信息系统中，如何进行知识约简以及如何获取有效的约简知识，是当前研究的热点和难点。

二、研究内容和方法本研究主要围绕不完备模糊多目标信息系统中的知识约简与获取展开，具体研究内容和方法如下：1、针对不完备模糊多目标信息系统中存在的知识不确定性和不一致性问题，提出一种改进的知识约简方法，该方法基于定性推理，利用不确定性逻辑和模糊逻辑进行知识表示和推理，同时考虑到多目标和不完备性的约束条件。

2、针对当前知识约简方法的效率问题，提出一种基于增量学习和深度学习的约简优化方法，该方法利用神经网络和深度学习技术进行特征提取和重构，以提高约简效率和精度。

3、构建一个不完备模糊多目标信息系统的实验平台，利用真实数据集进行验证和实验分析，评估所提出方法的性能、可行性和可靠性，并与其他常用方法进行对比。

三、预期结果和贡献本研究预期可以取得以下结果和贡献：1、提出一种改进的知识约简方法，该方法能够有效地解决不完备模糊多目标信息系统中的知识不确定性和不一致性问题，为实际应用提供一种新的约简技术。

2、提出一种基于增量学习和深度学习的约简优化方法，该方法利用神经网络和深度学习技术进行特征提取和重构，提高约简效率和精度，为知识约简方法的优化提供一种新的思路。

3、构建一个实验平台，验证和评估所提出方法的性能、可行性和可靠性，并与其他常用方法进行对比，为相关领域的实际应用提供一些参考和指导。

第31卷第2期辽宁工程技术大学学报（自然科学版）2012年4月V ol.31No.2Journal of Liaoning Technical University（Natural Science）Apr.2011文章编号：1008-0562(2012)02-0284-05不完备信息系统的增量式约简算法金玲玲1，王喜凤2，朱紫焱3（1.海南师范大学数学与统计学院，海南海口571158;2.安徽工业大学计算机学院，安徽马鞍山243002;3.郑州大学科研处，河南郑州450001）摘要：针对经典粗糙集模型在处理不完备、动态数据方面的不足，通过分析容差关系模型，引入先验概率在知识估计中的方法，给出了一种基于区分矩阵的增量式属性约简算法.以属性重要度为启发信息，对区分矩阵的构造过程进行改进，仅需简单的矩阵运算就可以得到约简结果.最后通过示例分析处理增量式数据的算法复杂度有效，算法正确可行.关键词：粗糙集；不完备系统；增量式约简；区分矩阵；属性重要度；先验概率；容差关系；算法复杂度中图分类号：TP18文献标志码：AIncremental reduction algorithm based on imcomplete information systemJ IN Lingling1，WANG Xifeng2，ZH U Ziyan3(1.School of mathematics and sta tistics,H ainan Nor mal University,Haikou571158,China;2.School of Computer Science,Anhui University of Technology,Ma’an shan243002,China;3.Resear ch Depar tment,Zhenzhou Univer sity,Zhenzhou450001,China)Abstra ct：Aiming at the disadvantage of classical rough set model in dealing with imcomplete and dynamic data,a prior probability method in estimating knowledge is introduced through analyzing tolerance relation,and a incremental attribute reduction algorithm based on discernibility matrix is ing attribute significance as heuristic message,the process of constructing discernibility matrix is improved,reduction result can be got only by simple matrix computing.Finally,algorithm’s complexity in dealing with incremental data is effective through example analysis,and the algorithm is valid and feasible.Key wor ds：rough set;imcomplete system;incremental reduction;discernibility matrix；attribute significance; prior probability method;tolerance relation;algorithm’s complexity0引言自1982年，Pawlak提出粗糙集理论，已在知识发现、机器学习、决策分析、模糊控制和智能信息处理等领域得到了成功的应用[1-2].粗糙集理论是一种处理不精确、不确定和不完整数据的数学理论，在无任何先验信息的情况下，利用集合的上下近似集以及不可分辨关系来讨论知识的等价划分问题.经典粗糙集中，信息处理和知识获取主要针对完备的数据，而科学研究、生产实践活动中，由于数据测量或数据获取等条件的限制，所获取的对象数据往往不全或缺失遗漏，即数据的不完备性，这种不完备的数据集不能满足等价关系，因此研究不完备数据中提取有效的、潜在的信息成为重要的课题.目前采用粗糙集处理不完备信息系统的方法主要有两类：一是用删除、数据填补的方式将不完备信息系统转化为完备信息系统，但不同程度上会改变原系统的信息成分，存在一定的局限性.二是在不改变信息系统的前提下，对粗糙集模型作拓展研究[3]，这种方法成为目前研究的主流.Kryszkiewicz[4]和Stefanowski[5]先后给出了基于相容关系和相似关系的扩充方法，王国胤[6]等提出了限制容差关系的粗糙集模型.文献[7]和文献[8]在限制容差关系的基础上引入容差度参数对限制条件进行修正，提出了改进的容差关系模型.属性约简是粗糙集理论的核心内容之一，然而现有的属性约简算法主要研究完备系统的约简问题，提出的算法也主要针对静态数据.相比之下，不完备系统的约简研究还比较薄弱，适应于动态数据变化的约简算法更为少见.文献[9]虽然提出了一种收稿日期：2011-03-28基金项目：海南省自然科学基金资助项目(610221)；海南师范大学青年教师科研启动基金资助项目(QN0918)作者简介：金玲玲(1976-)，女，湖南常德人，硕士，讲师，主要从事精糙集与挖掘面的研究.本文编校：曾繁慧285第2期金玲玲，等：不完备信息系统的增量式约简算法无目标信息系统的增量式约简算法，但没有对不完备系统和决策系统展开研究.针对以上问题，本文在文献[7，9]的研究基础上，结合修正的相容关系提出了一种基于区分矩阵的增量式约简的算法，算法避免对原有数据进行重复计算的基础上，结合增量数据进行知识发现，并运用到不完备信息系统的数据处理中，通过数据测试说明该算法是正确可行的.1不完备系统的粗集扩展理论定义1决策系统S 是一个四元组，即S ＝{U ，,V,f}，其中U 为论域，表示所研究对象组成的非空有限集合，C 和D 分别表示条件属性和决策属性集(C ∪D=φ)，D C U ()a V V a C D ∈U ＝U ，V a 是属性a 的值域，f 是论域与属性的映射函数，f(x,a)表示对象x 关于属性a 的取值[10].若决策系统中存在x ∈U,a ∈C 的取值不确定，记作，则称为不完备决策系统，简记为IS={U ，C ∪D}.*=a)f (x,针对不完备的决策表，研究者对经典粗糙集理论进行了扩展.定义2对于给定的不完备信息系统IS ＝{U ，C ∪D }，条件属性B C ，其容差关系定义[4]为：,x y U ∈，，()B T x ,y a B ∈()()f x ,a =f y,a ∨()()f x,a =*f y,a =*∨.容差关系满足自反性和对称性，但不满足传递性.根据U 上的相容关系，对任意对象x ∈U ，存在集合：,表示与x 相容的对象的集合，即容差类.定义在容差关系下的上近似：(){|(,)(,)}B B T x y U x y T x y =∈∈(){|}B B T X x x U T X X =∈∧≠I （）,下近似：(){|}B B T X x x U T X X =∈∧（）.显然，容差关系将*与任意明确的属性值视为相等，容易将仅有少数相同信息或完全没有明确信息的对象划分到一个容差类中，如对象（1，*，*，*，*）和(*，2，*，*，*)认为是不可分辨的.容差关系过于宽松，相似关系[5]过于严格，王国胤提出了介于两者的限制容差关系L T ，定义[6]为：定义3给定的不完备信息系统IS 中，,x y U ∈，条件属性BC ，,(,)B LT x y a B ∈((,)(,)*(()())(((,B B f x a f y a P x P y f x ==∨≠∧I )*(,)*)((,)(,))a f y a f x a f y a ≠∧≠→=,式中，(){(,)*}B P x b B f x b =∈｜≠，限制容差关系也具有自反性和对称性，不满足传递性.对任意对象x ∈U ，存在集合：LT B (x)={y ∈U ∣(x,y )∈LT BB B(x,y)}，表示x 对象的限制容差类.从限制容差模型的定义可以看出，若仅有少量属性取值相同，其它属性不确定时，如对象(1,1,2,3,0)和(*,1,*,*,*)认为是不可分辨的，这种情况下条件(()())B B P x P y ≠I 则显得太宽松.为了弥补这种模型的缺陷，文献[7,12]提出一种可动态调整的容差关系，通过设定容差度∈[0,1]的值对容差关系进行修正，能够灵活控制系统中获取信息粒度的大小，得到了一个较满意的结果.定义4给定不完备系统IS={U,C ∪D,V ,f }，任x,，yU i B C ∈，则x ,y 在属性B Bi 上的概率(,)i P x y =21/||,((,)*(,)*)(,)*(,)=*)||,()*()=*1,()*()*()=()0,()*()*()(),i i i i i i i i i i i i i i i iV f B x f B y f B x f B y V f B,x f B,y f B,x f B,y f B,x f B,y f B,x f B,y f B,x f B,y =∧≠∨≠∧=∧≠∧≠∧≠∧≠∧≠（1）式中，|V i |是B i 属性上的值域基数.x ，y 在所有条件属性上取值相同的联合概率，即容差度(,)(,).B i B CR x y P x y ∈=∏定义5对于(x)B x U y T ∈∈，，动态阈值min (max (min (()))min (max (()))=R c x,y ,Rc x ,y 则变精度动态容差关系VDT 定义如下：(,)(,)(,)(,)B B B V DT x y x y T x y R x y ∈∧≥,那么对于任意对象x ∈U ，DT B (x)={y ∈U ∣(x,y)∈V DT BB B(x,y )}，表示x 对象的动态容差类.可见，当=1时，模型可退化为经典的等价关系；=0时，模型退化为经典的容差关系.2新的区分矩阵和增量式约简算法2.1基本定义为了更好地说明算法，先给出修正的区分矩阵286辽宁工程技术大学学报（自然科学版）第31卷及相关定义：定义6[13]给定信息系统IS={U ，C ∪D ，V ，f}，xU ，i B C ，表示某属性的值域，某属性中各个取值的频率，那么的取值会更倾向于出现频率较大的值，即：12{,,,}i i i im V V V V =L 12{(),(),,()ii i i P P V P V P V =}L m 表示>∧∧*=)(i B x f ,12111()()(*|())i i i i i P V P V P V V P V >==222(*|()).i i i P V V P V ==（2）定义7(绝对的区分矩阵)不完备决策系统IS={U,}，其中|U|=n ，，定义D C U U x x ji ,()ij n n s C ×=M ，其中|()(),()()(),()0,()(()()().i j ji i j ij n n j i ji i j a a x a x x VDT x d x d x C x VDT x x V DT x d x d x ×≠≠=∈∨=Ms (3)式中，i ，j ＝1,2,…,n ；a (x)，d(x)分别表示对象x 在a 条件属性和决策属性上的取值.定义8（相对区分矩阵）依据定义6,IS 系统中C={a 1,a 2,…,a m }，U={x 1,x 2,…,x n }，定义条件属性a i 的区分矩阵M a i(n ×n)，其矩阵元素如下：1,()()()(),()0,()()()().i i i j i j ai ij n n i i i j i j a x a x d x d x C a x a x d x d x ×≠∧≠===∨=M （4）式中，M ai 矩阵：元素值体现了属性a i 对各对象的区分能力，其中：元素值为1，表示a i 属性能区分决策值不同的第i 和第j 个对象；反之，则表示a i 属性不能区分第i 和第j 个对象.它是一个0-1矩阵.显然由M ai 所决定的分类与论域U 按照属性a i 的分类是等价的[9].Ms 矩阵：元素值表示能区分决策值不同的第i和第j 个对象的所有属性的集合.容易看出，对于任何条件属性B C ∈，上述矩阵间存在联系：;B a i a i B∈=U M M 1Ba i s=∑M M U .定义9在不完备信息系统IS={U ，C ，V ，f}中，条件属性a ∈C 是不重要的，当且仅当M D B =BM B-{a }.M a 是属性a 的区分矩阵，属性a 对系统区分能力的影响程度SIG(a)可按下式计算：SIG(a)=∣M B -M BB ∪{a }∣，其中∣M B B U ∣表示矩阵中非零元素的个.定义10在不完备信息系统IS={U ，C ，V ，f}中，对于属性集D C B，存在M B =M BC ，且a B ∈，M B ≠M B-{a }，则称B 是C 相对于D 的属性约简.2.2算法描述算法1属性约简算法.输入：不完备决策信息系统IS={U ，，V ，f},输出：最大约简属性集.D C U )(=C RED R 步骤1根据定义6，计算C 中各属性值域和各取值的概率，并根据概率分布估计出未知值*.步骤2对于a i C ∈计算相对区分矩阵，记M ai ；步骤3初始化(0)R n R n ×==，M ；步骤4对于任一a i C ∈-R ，根据定义9计算SIG (a i )，并令，;}{=a'R R U ()max ()i SIG a'SIG a =步骤5计算'RU M M a a a .若()那么'R R ≠U M M M 'RR =U M M M ，转步骤4；否则转步骤6.步骤6输出属性约简集R.算法2增量式属性约简算法.输入：根据算法1的计算结果M ai ，M R ，新增属性X 及值.输出：属性约简集）（＝X C RED R U .步骤1由算法1的步骤1，估计X 属性中未知值；步骤2计算X 的相对区分矩阵M X 和1Rai =∑M M ；步骤3若(M R ≠M R ∪M X )，那么R=R ∪{X }，令M R =M R ∪M X ，M=M+M X ，转步骤4；否则转步骤6.步骤4对于任意a i ∈R-X.令'ai ij ()n -n r ×=M M M =；//对矩阵M ’进行重新构造for i=1to nfor j=1to nif(r ij >0)则置r ij =1else 置r ij =0endfor步骤5若('R ==MM )，那么令-{}i R R a ＝，-a i＝M M M 转步骤4；否则转步骤6；步骤6输出新的约简R.287第2期金玲玲，等：不完备信息系统的增量式约简算法2.3算法分析属性约简的核心思想是通过约简某些属性后不改变整个决策系统的决策能力.所研究的增量式算法的基本思想是判断新增属性是否改变系统的决策能力，若没有改变，则属性约简仍是原来的属性约简.若发生改变，则该属性是必要的，然后从新构成的属性集中删除不必要的属性.和其它的增量式约简算法相比，如文献[14]，其优势体现在区分矩阵的并或差运算都能很好的利用原有的计算结果，避免了对已有数据的重复计算.文献[14]中给出的基于相容矩阵的不完备信息系统的属性约简算法，其最坏时间复杂度为O(|C|3|U|2).然而根据本文算法1可知，step1的时间复杂度为O(|C||U|)，step2的时间复杂度为O(|C||U|2)，step4计算属性重要度的时间复杂度为O(|C-R||U|2)，Step4~Step5循环计算相对区分矩阵的并运算，其时间复杂度为.即O(|C|||-12||0(|-|||)C R O C R U =∑2|U|2).算法2与算法1基本相同，因此本文算法总的最坏时间复杂度为O(|C|2|U|2)，比文献[14]效率有所提高.3实例分析表1是一个车辆评价的不完备信息表[12]，其中论域U ＝{1,2,3,4,5,6}，条件属性集C ＝{P,M,S,V }，分别代表车价、里程、车身尺寸和车速.决策属性为D ＝{d}.现利用表1中的数据对本文算法进行分析.表1不完备决策Tab.1imcomplete decision决策车号pM S V d 1High High Full Low Good 2Low *Full Low Good 3**Compact High Poor 4High *Full High Good 5**Full High Excel 6LowHighFull*Good(1)计算各属性取值的概率：各属性值域分别为：V P ＝{High ，Low}，V M ＝{High}，V S ={Full ，compact}，V V ＝{Low ，High}，得P P ＝{1/2，1/2}，P M ={1}，P S ={5/6，1/6}，P V ＝{2/5，3/5}，则未知属性值*在各属性中倾向的取值分别是：High 或Low ，High ，Full ，High.(2)令M R ＝(0)n ×n ，计算各属性的区分矩阵，可得M P =(0)n ×n ，M M ＝(0)n ×n ，000110001000100001000S =M ,.000110000011000000000V=M 计算出动态容差类和绝对区分矩阵M ，以便对区分矩阵进行验证.①根据定义2求容差类：T C (1)={1}，T C (2)={2，6}，T C (3)={3}，T C (4)={4，5}，T C (5)={4，5，6}，T C (6)={2，5，6}；②根据容差度计算公式：R C (1)=(1，1)，R C (2)=(1/4，1/4)，R C (3)=(1/16，1/16)，R C (4)=(1/8，1/8)，R C (5)=(1/8，1/8)，R C (6)=(1/8，1/4)，得到α=1/16.因此，根据定义5可以确定本例动态容差类与容差类结果相同.③然后根据定义7求得绝对区分矩阵M00220.001011100001000P M S =+＝M M M V ++M M (3)计算属性意义：SIG(P)=0，SIG(M )=0，SIG(S)=5，SIG(V)＝4；(4)计算∪M S ，R ＝R {∪S}；(5)由于M R ≠M S ，转入Step4，Step5后计算得到00110.001011100001000R =M 算法1结束，输出属性约简R ＝{S ，V }，其约简辽宁工程技术大学学报（自然科学版）第31卷288→4结论结果与文献[12]一致.(6)下面分两种情况讨论，新增属性X （其相对区分矩阵记为M X ）后的约简过程：①第一种情形：000110.000010100001000X =M 不完备信息是智能信息处理领域研究的难点和热点.考虑属性数动态增加的情况下属性约简的更新问题，本文引入先验概率后，结合动态容差关系的分析，提出了一种基于的区分矩阵的增量式约简算法.该算法可以充分利用到数据更新前的结果，仅通过简单的矩阵运算就能快速地获得约简结果，避免了大量的重复计算，其时间复杂度为O(|C|2|U|2).通过实例分析，表明该增量式属性约简算法是正确有效的.针对数据的动态更新，给出保持属性集不变增加实例的约简算法将是下一步的工作.因为M R =M R ∪M X ，所以属性X 是不必要的.根据算法2，其属性约简仍为R ＝{S ，V}.参考文献：②第二种情形：010100.010001000000000X =M [1]Pawlak Z,Grzymala B J,Slowinski R.Rough set s[J].Communications of theACM,1995,8(1):89-95.[2]王国胤.Rough 集理论与知识获取[M].西安：西交交通大学出版社,2001.5.[3]王彪,段禅伦,吴昊,等.粗糙集与模糊集的研究及应用[M].北京：电子工业出社,2008,3.[4]Kryszkiewicz M.Rough s et approach to incompl ete informationsys t ems[J].Information Science,1998,112(1):39-49.根据算法2的Step3，可得M R ≠M R ∪M X ，因此X 是必要的，R ＝R {∪X}；计算M R=M R ∪M x ，M ＝M+M X ，得到[5]Stefanowski J,Tsoukias A.Incomplete information tables and roughclass i fication[J].ComputationalIntelligence,2001,17(4):545-566.010110,011011100001000R =M 010330.012022200002000=M [6]王国胤.不完备信息系统的粗糙集扩展[J].计算机研究与发展,2002,39(8):1238-1243.[7]纪霞,李龙澍.基于变精度动态容差关系的扩充粗糙集模型[J].系统仿真学报,2009,21(8):5731-5734.[8]官礼和.基于粗糙集理论的不完备信息处理方法研究[J].重庆邮电大学学报：自然科学版,2009,21(4):461-466.[9]刘高峰,牟廉明.基于区分矩阵的增量式属性约简[J].计算机工程与设计,2009,30(18):4293-4295.然后考虑去除多余的属性，若R=R-{V}，可知010220012011200002000VM M =→01011001101110000100[10]苗守谦,李国道.粗糙集理论、算法与应用[M].北京：清华大学出版社,2008.4.[11]李龙澍,纪霞,汤伟.基于动态容差关系的不完备信息表约简研究[J].计算机工程与设计,2009,30(5):1173-1175.重新构造.[12]韩智东,王志良,高静,等.基于相容矩阵的改进属性约简算法[J].计算机工程,2010,36(20):25-31.[13]朱颢东,周姝,钟勇.不完备信息系统的粗集扩展模型[J].湖南科技大学学报：自然科学版,2009,24(3):73-76.处理结果与M R 相同，因此V 是多余的属性.用同样的方法，可以考虑S 属性是否可以去除.经计算增量属性约简结果为R ＝{S ，X}.[14]Huang B,He X,Zhou X Z.Rough computational methods based ontolerance matrix[J].Acta Automatica Sinica,2004,30(2):363-370.。