基于变精度粗糙集理论的知识约简方法

1、2004年1月系统工程理论与实践第1期文章编号:100026788(2004)0120076207基于变精度粗糙集理论的知识约简方法米据生1,2,吴伟志1,张文修1(1.西安交通大学理学院信息与系统科学研究所,陕西西安710049;2.河北师范大学数学与信息科学学院,河北石家庄050016)摘要:基于变精度粗糙集理论与包含度理论,引入了不协调目标信息系统的上、下分布约简的概念,并讨论了它们之间的关系.上(下)分布约简是保持每个决策类的上(下)近似不变的最小属性集,由约简系统产生的命题规则与由原系统产生的命题规则是相容的,即约简不会改变由对象所产生的规则的决策结果.通过对这两种知识约简的等价刻画

2、,得到了上、下分布知识约简的判定定理和可辨识属性矩阵,从而提供了不协调目标信息系统知识约简的新方法.关键词:变精度粗糙集;知识约简;信息系统;协调集中图分类号:TP18文献标识码:AKnowledgeReductsBasedonVariablePrecisionRoughSetTheoryMIJu2sheng1,2,WUWei2zhi1,ZHANGWen2xiu1(1.InstituteforInformationandSystemSciences,FacultyofScience,XianJiaotongUniversity,Xian710049,China;2.CollegeofMathe

3、mathisandInformationScience,HebeiNormalUniversity,Shijiazhuang050016,China)Abstract:Themainobjectiveofthepaperistointroducesomenewconceptsofknowledgereductionbasedonvariableprecisionroughsettheorysuchasupperdistributionreductionandlowerdistributionreduction.Thedecisionrulesderivedfromthedistribution

4、consistentsetarecompatiblewiththeonesderivedfromoriginalsystem.Theirequivalentdefinitionsarestudied.Therelationshipsamongalterna2tivereductsininconsistentinformationsystemsarediscussed.Thejudgementtheoremsanddiscernibili2tymatrixeswithrespecttoupperandlowerreductionsareobtained.Soonecancalculatesthe

5、reducts.Theseresultsaremeaningfulbothinthetheoryandinapplications.bythediscernibilityformulasKeywords:variableprecisionroughset;informationsystem;knowledgereduction;consistentset知识发现是人工智能的核心问题之一,它是从信息系统中识别正确、新颖、有潜在应用价值并最终可为人们所理解的模式的方法.粗糙集理论提供了知识发现的一种数学方法.由于这一理论的广泛应用,它越来越引起国际学术界的关注.知识约简是知识发现的重要课题,因而也

6、是粗糙集理论的核心问题之一.目前,信息系统的知识约简大多是在Pawlak粗糙集模型下进行的1-7.Pawlak粗糙集模型的一个局限性是它所处理的分类必须是完全正确的或肯定的,因而它的分类是精确的,亦即只考虑完全“包含”与“不包含”,而没有某种程度上的“包含”与“属于”.Pawlak粗糙集模型的另一个局限性是它所处理的对象是已知的,且从模型中得到的结论仅适用于这些对象.但在实际应用中,往往需要把从小规模对象集中得到的结论应用于大规模对象集上去.Pawlak粗糙集模型的这些局限性限制了它的应用.近年来,许多学者从多方面推广了这一模型.在这个模型中,给定一个阈值,当对象所在的等价类在某种Ziarko

7、于1993年提出了变精度粗糙集模型程度上包含于集合X中时,就认为这个对象属于X.这一推广在应用上是非常重要的,因为在实际问题收稿日期:2002211218资助项目:国家自然科学基金(10271039);973项目(2002CB312206)作者简介:张文修(1940-),男,教授,博士生导师,中国数学会常务理事.研究方向:应用概率论,人工智能的数学基础等;米据生(1966-),男,副教授,博士生.研究方向:人工智能的数学基础,粗糙集与随机集;吴伟志(1964-),男,副教授,博士生.研究方向:人工智能的数学基础,粗糙集与随机集© 1995-2005 Tsinghua Tongfang

8、 Optical Disc Co., Ltd. All rights reserved.第1期基于变精度粗糙集理论的知识约简方法77中绝对的包含有时是不必要的.基于变精度粗糙集理论,文8-11给出并研究了不协调信息系统的下近似约简.下近似约简保持有决策的对象总数不变,但所产生的决策规则与原信息系统产生的规则有可能冲突.因此,这种约简定义不太适合实际需要,并且也没有文献从理论上给出这种知识约简的具体操作方法.为此,在文12中,我们利用可辨识属性矩阵给出并研究了不协调目标信息系统的几种知识约简方法.本文提出变精度粗糙集模型上两种知识约简的新概念,即上、下分布约简.它们分别是保持每个决策类的上、下近

9、似不变的属性集,并且与全部属性集A产生相容的命题规则.同时给出了上分布约简与下分布约简的判定定理和相应的可辨识属性矩阵,从而得到了变精度粗糙集模型上知识约简的新方法.这为不协调目标信息系统的知识约简提供了理论依据与算法.1变精度粗糙集模型变精度粗糙集模型8是Pawlak粗糙集模型1的推广.先给出有关概念和术语.定义1.1设(U,AD,f)是目标信息系统,其中,U是有限对象集合,U=x1,xn;A是有限条件属性集,A=a1,ap;D是有限目标属性集,D=d1,dq,AD=󰂡.f是描述,f:U×(A.B)V,V=Vc,Vc是c的有限值域cAD对于任意BAD,记RB=(x,

10、y):f(x,c)=f(y,c),cB则RB是U上的等价关系,称为由B决定的不可区分关系.它产生的上的U分划记为:U󰃗RB=xB:xU其中xB=y:(x,y)RB是x关于B的等价类.XU,记(X)=xU:xBX=xB:xBXRB(X)=xU:xBX󰂡=xB:xBX󰂡则(X)与RB(X)分别称为x关于B的下近似和上近似.X的下近似是按着知识B肯定属于X的对象全体,而上近似是按着知识B可能属于X的对象全体.显然XRB(X),(X)(X),RB(X)RBa(X)这说明:增加属性会减少对象是否属于X的不确定程度.称(U,RA,RA)为Pawlak粗糙集模

11、型.对(0.5,1,记(X)=xU:D(X󰃗xB)=xB:D(X󰃗xB)=xB:D(X󰃗xB)>1-(X)与RB(X)为X关于B的下近似和上近似)(BA)为变精度粗糙则分别称.称(U,RA,RB集模型8.其中D为U的幂集P(U)=X:XU上的包含度.为方便起见,本文中取D(X󰃗Y)=,若󰃜Y󰃜0;D(X󰃗.则Y)=1,若󰃜Y󰃜=0.其中󰃜Y󰃜表示Y中的元素个数󰃜Y󰃜cD(Xϗ

12、255;Y)+D(X󰃗Y)=1󰃜Y󰃜(X)与RB(X)满足对偶性质:RB(X)=RB(X).(X)=(X)且RB(X)=RB(X).因此,变精度粗糙集模型是Pawlak粗糙集模型的推当=1时,RB(X)=xU:D(X󰃗xB)>1-广.为叙述简单,以下设D=d,Vd=1,2,r,Dj=xU,f(d,x)=j.则U󰃗RD=xD:xU=D1,Dr.容易证明8,与RB具有以下性质:(Di)(Dj)=󰂡,(ij);1)(Dj)RB(Dj)U,等号未必成立;2)j=1j=1(Di)RB(Dj)=ϗ

13、201;一般不成立3)RB.rr© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.78系统工程理论与实践(Dj)可产生如下形式的命题规则在变精度粗糙集模型中,由x(c,f(c,x)d=jcA2004年1月显然,基于变精度粗糙集理论,并不是每一个对象都有决策,只有当其所在等价类在某个决策类中的包含度不小于阈值时,它才能产生决策规则.定义1.2设(U,AD,f)是目标信息系统,若RARD,则称目标信息系统是协调的,否则称目标信息系统是不协调的.2变精度粗糙集模型上知识约简的概念基于变精度粗糙集

14、理论,文8-11给出了下近似约简的概念.下面再定义几种知识约简概念.定义2.1设(U,AD,f)是目标信息系统,BA.记B=(Dk)󰃜:kr󰃜󰃜U󰃜B=B(Dk)󰃜:kr󰃜RB󰃜U󰃜LB=(D1),(Dr);H(D1),RB(Dr)=(RB1)若B=A,则称B是下近似协调集.若B是下近似协调集,但B的任何真子集不是下近似协调集,则称B是下近似约简11.2)若.若B是上近似协调集,但B的任何真子集不是上近似B=A,则称B是上近似协调集协调集,则称B是上近似约简.3)若L

15、B=LA,则称B是下分布协调集.若B是下分布协调集,但B的任何真子集不是下分布协调集,则称B是下分布约简.4)若HB=HA,则称B是上分布协调集.若B是上分布协调集,但B的任何真子集不是上分布协调集,则称B是上分布约简.上(下)分布协调集是保持每个决策类的上(下)近似不变的属性集,它与A产生相容的命题规则,即在原系统和约简系统中,由同一对象所产生的命题规则的决策部分相同.而下近似协调集保持决策类的下近似中的对象总数不变,由它产生的命题规则与由A产生的命题规则可能冲突,但支持这些命题规则的对象个数不变.定理2.1设(U,AD,f)是目标信息系统,则下分布协调集必为下近似协调集,上分布协调集必为上

16、近似协调集.证明由定义立即可得.例2.1下近似协调集未必是下分布协调集.给出目标信息系统(表2.1).记D1=x1,x2,x4,D2=x3,D3=x5,x7D4=x6,x8,A=a1,a2,B=a1表2.1Ux1x2x3x4x5x6x7x8a1a2d111122220112022111213434则0.70.70.7(D1)=x1,x4,(D2)=󰂡,(D3)=x50.70.70.7(D4)=x8,(D1)=x1,x2,x3,x4,(D2)=󰂡(D3)=󰂡,(D4)=󰂡.0.70.7因此,B=a1是0.7下近似协调集,但不是0.7下分布协调集.同样,上近似协调集也未