基于代数观与信息观的粗糙集属性核

基于代数观与信息观的粗糙集属性核

1差别化矩阵的求核方法罗赫集（ss，厚量集）是一种新的计算不准确、不完整、不相容的知识的数学理论。在厚量集理论中，属性约简单是研究的重要内容之一，而属性约简单是从元素开始的。因此，要确定属性，将元素搜索作为搜索特征的关键步骤，是探索和研究属性要求的有效方法，具有重要的实用价值。现在有很多方法。其中，基于hu差异矩阵的计算方法是经典的计算方法之一，但在某些情况下无法获得正确的数据。叶东毅等人在基于hu差异矩阵定义的基础上提出了新的差异矩阵。杨明教授在叶片的基础上进一步改进了差异矩阵。然而，在他们的方法中，只考虑两个比较对象是否为非公共对象，而不研究它们的自由反应程度。因此，获得的那矩阵中的单个属性元素是代表达信息矩阵的核属性。王国扬教授从代数观念和信息观念两个方面探讨了要求核属性的问题，分析了代数观念和信息观念中属性核的一致性和差异，并对文献进行了有效补充和改进。然而，算法的效率必须提高。为此,我们提出一种新的改进的差别矩阵及其求核方法,该方法将粗糙集的代数观与信息观结合起来研究,能够较快地得出信息论观点下的属性核.2u3000属性系数定义2.1设P在U上导出的划分为X,X={X1,X2,…,Xn},则P在U的子集组成的σ代数上的概率分布为:(X∶Ρ)=[X1X2LXnΡ(X1)Ρ(X2)LΡ(Xn)],其中p(x)=|Xi||U|,i=1,2,⋯,n.有了知识的概率分布定义,根据信息论就可以定义知识的熵与条件熵的概念.定义2.2知识(属性集合)P的熵H(P)定义为Η(Ρ)=-n∑i=1p(Xi)log2p(Xi).定义2.3知识(属性集合)Q(U/IND(Q)={Y1,Y2,…,Ym}相对于知识(属性集合)P(U/IND(P)={X1,X2,…,Xn}的条件熵H(Q|P)定义为:Η(Q|Ρ)=-n∑i=1p(Xi)×m∑j=1p(Yi|Xi)log2p(Yi|Xi)其中Ρ(Yj|Xi)=|Xi∩Yj||Xi|‚i=1,⋯,n‚j=1,⋯,m.定义2.4U是一个论域,C是U的条件属性集,D是U的决策属性集,B⊆C.若H(D|B)=H(D|C),且a∈B有H(D|B-{a})≠H(D|B),则B是C相对于决策D的信息熵约简.定义2.5U是一个论域,C是U的条件属性集,D是U的决策属性集,RED(C)为C的所有D约简关系簇,C的属性核为Core(C)=∩RED(C).为了说明属性a在条件属性集C中相对于决策属性D的重要度,可以定义如下的度量:SIG(a,C,D)=H(D|C-{a})-H(D|C);其值越大说明在一定的条件属性集C的情形下,属性a对D决策越重要,反之则越不重要.定理2.1决策表S=(U,C∪D,V,F),其中C是条件属性,D是决策属性,则a∈C是核属性的充分必要条件是SIG(a,C,D)≠0.3改进的差别矩阵定义及求解为有效地求核,Hu等学者提出利用差别矩阵来确定核的方法,其差别矩阵M={mij}定义为:mij={a∈C,f(xi,a)≠f(xj,a),D(xi,a)≠D(xj,a)‚>‚其它(1)文献给出如下结论:当且仅当某个mij为单个属性时,该属性属于核Core(C).叶东毅对Hu的这个结论提出质疑,并举例说明了该结论的问题,并通过对差别矩阵的改进提出了一种计算核属性的方法,其提出的改进的差别矩阵定义为:定义3.1对xi∈U,记d(xi)=card{f(y,D):y∈[xi]C},即d(xi)表示U中所有与xi在关系IND(C)下是等价的元素相应的决策属性值构成的集合的基数.定义3.2对给定的决策系统S,定义差别矩阵MS={m′ij}为:m′ij={mij当min(d(xi),d(xj))=1)>其它(2)其中{mij}的定义同式(1).叶东毅的结论如下:当且仅当某个m′ij为单个属性时,该属性属于核Core(C).杨明认为叶东毅提供的算法的效率仍需改进.因此,杨明在引入求解某个属性为不可缺少属性的等价定理后,提出了改进的差别矩阵定义以及求解核的方法:定义3.3对给定的信息系统S,定义差别矩阵M1={nij}为:nij={a∈C:f(xi,a)≠f(xj,a),f(xi,D)≠f(xj,D),xi∈U1,xj∈U1‚a∈C:f(xi,a)≠f(xj,a),xi∈U1,xj∈U2‚>其它(3)其中U1=POSD(P),U2=U-U1.依据定义3.3,文献给出并证明了如下结论:当且仅当某个nij为单个属性时,该属性属于核Core(C).仔细分析差别矩阵(2)和(3),我们可以看出,(2)和(3)是等价的.U1中对象是一致的,U2中的对象不一致,当两个对象xi与xj有一个在U1中时,d(xi)或d(xj)值一定为1.所以,(3)中前面两种情况,实际上都满足(2)的min(d(xi),d(xj))=1.同样的,min(d(xi),d(xj))=1,实际上包含两种情况:d(xi)与d(xj)均为1,即xi与xj两个都在U1中;d(xi)与d(xj)只有一个为1,即xi与xj有一个在U1中,另一个在U2中.如果两个对象xi与xj都在U2中时,(2)与(3)都将以空集表示.这样,在核属性的选取中就可能存在遗漏,或者说对某些情况,(2)与(3)都不能找到核属性.为了说明这一点,我们看下面的例子:例3.1表1所示决策信息系统S是一个不一致性决策信息系统,条件属性集C={a1,a2,a3,a4},决策属性集D={d}.用(2)和(3)方法计算所有元素后得到的分辨矩阵依次如矩阵1和矩阵2如下所示:矩阵1叶定义的分辨矩阵:[x1x2x3x4x5x6x7x8x9x1>x2a2a3>x3>a1a2>x4a1a2a3>>x5>a1a2>>>x6a1a3>>>>x7>a1a2a3>>>>>x8>a1a2a3>>>>>>x9a1a3>>>>>>>>]‚矩阵2杨定义的分辨矩阵:[x1x2x3x4x5x6x7x8x1>a2a3a1a2a3a1a2a3a1a3a1a3a1a3a1a3a1a3x2a2a3>a1a2a1a2a1a2a1a2a1a2a3a1a2a3a1a2a3].所以,叶和杨的方法都没有得到单属性元素,没有找到核属性.文献中给出了利用条件熵求信息论观点下的属性核的方法,即根据条件熵计算出每个属性在信息论观点下的属性重要度SIG(a,C,D),得到SIG大于0的为核.但此方法必须对所有属性进行计算,在属性较多时运算量大.4删除条件属性的选择我们先将决策表的条件熵的定义扩展到决策表的局部条件熵.定义4.1如果决策表S=<U,R,V,f>,R=C∪D是属性集合,子集C和D分别称为条件属性集和决策属性集,U/IND(D)={Y1,Y2,…,Ym},U/IND(C)={X1,X2,…,Xr},对于∀Xp,Xq,1≤p,q≤r,定义决策表的局部条件熵ΗXp∪Xq(D|C)=-|Xp||Xp∪Xq|∑k=1m|Xp∩Yk||Xp|log|Xp∩Yk||Xp|-|Xq||Xp∪Xq|∑k=1m|Xq∩Yk||Xq|log|Xq∩Yk||Xq|(4)结合上面定义的决策表局部条件熵,我们定义如下的新差别矩阵:定义4.2如果决策表S=<U,C∪D,V,f>,论域U={x1,x2,…,xn},条件属性集C在论域上的划分为U/IND(C)={X1,X2,…,Xr},决策属性集D在论域上的划分U/IND(D)={Y1,Y2,…,Ym},差别矩阵DM=(rij)n×n定义为:rij={a∈C,当min{|dxi|,|dxj|}=1,a(xi)≠a(xj),D(xi)≠D(xj),a∈C,当min{|dxi|,|dxj|}＞1,a(xi)≠a(xj),D(xi)≠D(xj),Η[xi]c∪[xj]c(D|C-{a})＞Η[xi]c∪[xj]c(D|C),>‚其它‚其中,令[xi]c=Xp,[xj]c=Xq,则ΗXp∪Xq(D|C-{a})=-∑k=1m(Xp∪Xq)∩Yk|Xp∪Xq|log(Xp∪Xq)∩Yk|Xp∪Xq|(5)式中HXp∪Xq(D|C-{a})表示删除条件属性子集a后论域为Xp∪Xq的局部决策表的条件熵.该定义实际上是将代数观与信息观结合考虑,而在信息观下,以局部条件熵增大为限制条件,来判定删除不同的条件属性后是否影响整个决策表的条件熵.如果xi和xj均为不一致性的对象,这两个对象所属的条件等价类在约简过程中合并不会影响条件熵,也就是说这两个对象对应的条件属性在信息观下不需要区分.因此,在差别矩阵中对象xi和xj对应的属性组合a中各属性是可删除的,对应差别矩阵中置为空.在新的差别矩阵中加入局部条件熵增大的条件,使a中的区分属性与信息观下根据条件熵变化判断两个条件等价类需要区分的属性一致.因此有:定理4.1对于决策信息系统S=<U,R,V,f>,R=C∪D是属性集合,子集C和D分别称为条件属性集和决策属性集,如果记SDM(C)={a:a为单个属性},则有SDM(C)=Core(C).即当且仅当某个a为单个属性时,该属性属于信息论观下的属性核Core(C).为证明定理4.1,我们给出如下的引理:引理4.1若[xp]C-{a}=[xq]C-{a},p≠q,假设删除条件属性a后仅有xp,xq合并,此时在论域U上形成的新划分记为C′,则当HXp∪Xq(D|C-{a})≥HXp∪Xq(D|C)时,必有H(D|C-{a})≥H(D|C).证明已知HXp∪Xq(D|C-{a})≥HXp∪Xq(D|C),则有ΗXp∪Xq(D|C-{a})-ΗXp∪Xq(D|C)=-∑k=1m|(Xp∪Xq)∩Yk||Xp∪Xq|log|(Xp∪Xq)∩Yk||Xp∪Xq|+|Xp||Xp∪Xq|×∑k=1m|Xp∩Yk||Xp|log|Xp∩Yk||Xp|+|Xq||Xp∪Xq|×∑k=1m|Xq∩Yk||Xq|log|Xq∩Yk||Xq|＞0⇔-∑k=1m|(Xp∪Xq)∩Yk|log|(Xp∪Xq)∩Yk|+|Xp|×∑k=1m|Xp∩Yk||Xp|log|Xp∩Yk||Xp|+|Xq|∑k=1m|Xq∩Yk||Xq|log|Xq∩Yk||Xq|＞0⇔-∑k=1m|(Xp∪Xq)∩Yk||U|log|(Xp∪Xq)∩Yk||U|+|Xp||U|×∑k=1m|Xp∩Yk||Xp|log|Xp∩Yk||Xp|+|Xq||U|∑k=1m|Xq∩Yk||Xq|log|Xq∩Yk||Xq|＞0⇔Η(D|C′)-Η(D|C)＞0?.删除条件属性a后合并的等价类可能不仅仅是Xp,Xq,由于Xp,Xq选择的任意性,多个等价类的合并可以分解为两两等价类合并的过程.因此,删除条件属性a后若有多个等价类的合并,则等价关系R在论域上形成的新划分比划分C′的粒度大.条件熵随着条件等价类划分的变粗而单调递增,所以H(D|C-{a})≥H(D|C′).于是有H(D|C-{a})-H(D|C)≥H(D|C′)-H(D|C)>0.证毕.定理4.1的证明(i)证明SDM(C)⊆Core(C).a∈SDM(C),由定义4.2可知一定存在rij={a}.假设xi∈Xp,xj∈Xq,xi∈Ys,xj∈Yt,根据rij的定义有a(xi)≠a(xj)且D(xi)≠D(xj),因此p≠q且s≠t,即xi,xj分别包含于不同的条件等价类和不同的决策等价类.删除属性a后[Xp]C-{a}=[Xq]C-{a},下面分三种情况讨论.①当Xp,Xq为一致性条件等价类时,根据叶的证明知a∈Core(C).②当Xp,Xq分别为一致性条件等价类和不一致性条件等价类时,根据叶的证明知a∈Core(C).③当Xp,Xq均为不一致性条件等价类时,只有当两个不一致性条件等价类包含的对象分别在所有决策等价类中的分布概率相同时,其合并才不导致条件熵的增加.根据rij的定义有:H[xi]C∪[xj]C(D|C-{a})>H[xi]C∪[xj]C(D|C),由引理得H(D|C-{a})-H(D|C)>0,a∈Core(C).综上,SDM(C)⊆Core(C).(ii)证明SDM(C)⊇Core(C).∀a∈Core(C),一定有H(D|C-{a})>H(D|C).则至少存在两个条件等价类Xp,Xq在删除条件属性a后合并,即a唯一区分这两个条件等价类的条件属性,并且使H(D|C-{a})>H(D|C).同样分三种情况讨论:①当Xp,Xq为一致性条件等价类时,设Xp⊆Ys,Xq⊆Yt.则存在xi∈Xp,xj∈Xq,必然有d(xi)=d(xj)=1,且a(xi)≠a(xj)且D(xi)≠D(xj).因此a∈SDM(C).②当Xp,Xq一个为一致性条件等价类,一个为不一致性条件等价类时,不失一般性,我们假设Xp为一致性条件等价类,Xq为不一致性条件等价类.则存在xi∈Xp,xj∈Xq,必然有d(xi)=1,d(xj)>1,但min(d(xi),d(xj))=1且a(xi)≠a(xj)且D(xi)≠D(xj).因此a∈SDM(C).③当Xp,Xq均为不一致性条件等价类时,设xi∈Xp,xj∈Xq.删除a后Xp,Xq合并,说明a是唯一区分Xp,Xq的条件属性,也是唯一区分xi,xj的条件属性.并且Xp,Xq合并使得H(D|C′)>H(D|C),由引理的证明过程有H[xi]C∪[xj]C(D|C-{a})>H[xi]C∪[xj]C(D|C.可知a∈SDM(c).故SDM(c)⊇Core(C).证毕.下面我们用新定义的差别矩阵求例3.1的决策信息系统S属性核.条件等价类有X1={x1},X2={x2},X3={x3,x4},X4={x5,x6},X5={x7,x8,x9},决策等价类有Y1={x1,x3,x5,x7,x8},Y2={x2,x4,x6,x9}.例如,按照叶的差别矩阵d(x5)=2,d(x4)=2,min(d(x5),d(x4))>1,于是m54=>;d(x8)=2,d(x6)=2,min(d(x8),d(x6))>1,于是m86=>,ΗX3∪X4(D|C)=-24(-12log12+12log12)-24(12log+12log12)=log2‚ΗX3∪X4(D|C-m54)=-(24log24-24log24)=log2=ΗX3∪X4(D|C)‚所以m54=>.ΗX4∪X5(D|C)=-25(-12log12+12log12)-35(23log23+13log13)=0.18‚ΗX4∪X5(D|C-m86)=-35log35-25log25=0.29＞ΗX4∪X5(D|C)‚所以m86={a3}.矩阵3新的差别矩阵:[x1x2x3x4x5x6x7x8x9x1>x2a2a3>x3>a1a2>x4a1a2a3>>x5>a1a2>>>x6a1a3>>>>x7>a1a2a3>a2a3>a3>x8>a1a2a3>a2a3>a3>>x9a1a3>a2a3>a3>>>>].所以,按照上述方法得到的核属性为{a3},这与利用文献得到的核属性一致.根据定理4.1,我们给出求核属性的算法如下:输入一个决策系统S=<U,A,V,f>,其中U为论域,属性集A=C∪D,C为条件属性集,D为决策属性集.输出核属性集CORED(C).(i)求U/IND(C)={X1,X2,…,Xr},U/IND(D)={Y1,Y2,…,Ym};(ii)求d(xi)(i=1,…,n);(iii)令CORED(C)=>;(iv)令n=|U|,m为n×n数组;(v)令变量i从1到n取值;(vi)令变量j从1到n取值;(vii)如果D(xi)≠D(xj),则mij=xi,xj中取值不同的属性集;否则转(viii);①如果min(d(xi),d(xj))=1且|mij|=1,则CORED(C)=CORED(C)∪mij;②如果min(d(xi),d(xj))>1且|mij|=1,如果H[xi]C∪[xj]C(D|C-{mij})-H[xi]C∪