基于核与改进的条件区分能力的反向删除属性约简算法

冯卫兵　张　梅

(西安科技大学理学院　陕西 西安 710054)



基于核与改进的条件区分能力的反向删除属性约简算法

冯卫兵张梅

(西安科技大学理学院陕西 西安 710054)

摘要粗糙集理论的布尔矩阵表示形式具有直观、易于理解的优点，它的引入为研究粗糙集的理论提供了一个新的思路。在对布尔矩阵性质研究的基础上，针对已有的基于布尔矩阵算法没有考虑到核属性在浓缩布尔矩阵时的重要性的不足，将属性重要性与改进的条件区分能力相结合，提出基于核与改进的条件区分能力的属性约简算法，借助反向删除确保约简集的完备性。实例表明改进后的算法在条件区分能力上更加准确，并且使约简结果更具有较强的完备性。

关键词布尔矩阵条件区分能力属性约简完备算法

0引言

1982年,波兰科学家Pawlak提出Rough理论[1],它是一种关于数据分析和推理的理论。自粗糙集理论提出以来,属性约简一直是粗糙集研究领域的热点内容之一。国内外学者已经提出了许多算法,典型的有：基于属性重要度的属性约简、基于正区域的属性约简[14]、基于信息熵的属性约简、基于差别矩阵的属性约简算法等[4,5,13,17]。然而,已有的约简算法在约简结果精度、效率低和算法完备性等方面还有待进一步改进。

相对于用代数形式表示粗糙集理论的概念与运算,布尔矩阵表示有一定的优势：第一，直观性强；第二，使用布尔矩阵的表示更易于理解粗糙集理论的概念与运算的本质。因此，布尔矩阵的引入为研究粗糙集的理论提供了一个新的思路。从上个世纪90年代以来，国内外学者对布尔矩阵表示的属性约简问题做了大量的研究，取得了许多成果[6-11,14]。文献[7]中运用布尔矩阵的方法来表示粗糙集的概念与运算；并在此基础上证明了属性约简在布尔矩阵和代数这两种不同的表示下是等价的；文献[6]在此基础上提出了以属性的条件区分能力为基础，构造了一种求属性约简的启发式算法。文献[3]利用布尔代数通过改进Skowron可辨识矩阵中存在的问题，从而对布尔矩阵进行浓缩。文献[11]提出一种根据决策表提供的信息来生成布尔可辨矩阵的方法；文献[12]通过将布尔矩阵的初等行变换把系数矩阵化为最简矩阵提高约简效率。

已有的算法均是以d(a,R)作为属性约简的启发式信息，在条件区分能力选择上比较精确，但是没有考虑到核属性对于简化决策表，删除布尔矩阵冗余信息的重要性。本文针对已有算法没有考虑到核属性在浓缩布尔矩阵时的重要性的不足进行了改进，将属性重要性与改进的条件区分能力相结合，提出了基于核与改进后条件区分能力的启发式属性约简算法，借助反向删除确保约简集的完备性。实例表明改进后的算法在条件区分能力上更加准确，并且使约简结果更具有较强的完备性。

1基于布尔矩阵的概念和定理

1.1布尔矩阵的构造

定义1[6,7]设S=(U,A,V,f)是一个信息系统。论域U在属性集A=C∪D={C1,C2,…,Cn}∪{d}下的划分为X={X1,X2,…,Xm}，针对所有的集对X={Xk,Xp}(1≤k≤p≤m)，给定唯一一个编号i与之对应：

其中，如上述对应方法，(Xk,Xp)对应的是第i个集对，属性Cj对应的标号为j。

定义2[7,15]设信息系统S=(U,A,V,f)，属性集R⊂A，布尔矩阵CA中同时删除R中的属性对应的列中值1对应的行和这些列，将剩下的元素重新构造得到的矩阵记为CAR。设d(a,R)表示属性CAR在条件a下的区分能力, 其值为矩阵CAR中属性a所对应列的所有元素的和,其中∀a∈AR。

1.2布尔矩阵的基本性质

布尔矩阵CA中，列和越大的属性的区分能力越强并且区分的集对数目也就越多；布尔矩阵行元素和越小，该行中元素值为1对应的属性在区分对象时就越重要。

命题1[15]设决策表某次约简集为R，CR为R中的全部属性对应的布尔矩阵，若去掉属性a所在的列后其对应的布尔矩阵增加新的零行，则a为必要属性并且需要保留；否则，a为冗余属性直接删除。

证明设CR为约简属性R所重新构造的一个布尔矩阵，对于R中任意属性a，设去掉属性a的列后的布尔矩阵为CR-{a}。若删除属性a所在的列元素而并不增加新的零行(元素全为0的行)，表明CR和CR-{a}的非零行数相同，即a在R中为冗余属性需要删除。相反的情况可得，a为必要属性需要保留，定理得证。

上述定理以及推论的提出主要是为了保证下文属性约简集不会存在冗余属性，从而得到一个属性约简的最简集，保证每一个算法结果的完备性。命题1是通过对属性集R反向删除过程，逐步实现最优约简的目的。

2属性约简算法的改进

2.1基于条件区分能力的属性约简算法

在布尔矩阵属性约简性质的基础上，提出了基于条件区分能力的属性约简算法，其基本思想为：首先，对CAR中的每列求和，记为d(a,R)；其次，对d(a,R)进行大小比较，找出最大的d(a,R)和其对应的属性a，接着将属性a所对应的列中值为1的行逐一删除；并且去掉a所在的列。获得新矩阵CAR′，判断CAR′=∅是否成立，若成立则算法结束，否则继续迭代。具体步骤如下：

算法1[16]基于条件区分能力的属性约简算法

输入：S=(U,A,V,f)；

输出：约简集R；

Step1由S构造相应的布尔矩阵CA；

Step2初始化R=∅，CAR=CA；

Step3

1) 计算CAR中列元素和d(a,R)，选出d(a,R)的最大值对应的属性a加入属性集R中，如果有多个属性同时满足条件，则任取出一个加入R中，令R=R∪{a}；

2) 在CAR中，同时删除属性a所在列中值1对应的行元素和a所在的列元素，更新a；

Step4判断CAR=∅是否成立，若成立，输出R；否则，转Step3。

该算法将条件区分能力d(a,R)作为寻找最小属性约简的启发式信息，算法简单，易于实现。但是在选取最大d(a,R)时具有任意性，会导致其最终约简结果不准确。接下来对算法1进行改进。

2.2基于改进的条件区分能力的属性约简算法

在布尔矩阵的定义中，cij=1是指第i行中出现的1所对应的属性cj能区分开集对XpXq。设行和为：

S越小，说明越少的属性就能区分开XpXq；相反，需要更多属性才能区分开集对XpXq。特别地，如果XpXq对应的行只有cij=1，则说明只有cj才能区分开这两个对象。基于此分析，针对算法1在选取最大d(a,R)时具有任意性缺点，提出了基于改进的条件区分能力属性约简算法，其改进思想为：当同时有多个列和最大时，应该在列和最大的这几个属性选取使行和S(pi)最小而且出现频率最高的属性。

算法2[16]具体步骤：

输入：S=(U,A,V,f)，A=C∪D，C∩D=φ，C和D分别为条件属性集和决策属性集；

输出：约简集R；

Step1由S构造矩阵CA；

Step2初始化R=φ，CAR=CA；

Step3对CAR每一列求和，找出d(a,R)中的最大值，此时，当同时有多个列和最大时，在列和最大的这几个属性选取使行和S(pi)最小而且出现频率最高的属性加入到约简集中，即R=R∪{a}；

Step4同时删除属性a所在列中值1对应的所有行元素和属性a所在的列元素，更新矩阵为CAR。

Step5判断CAR≠∅是否成立，若成立，转Step3；否则，直接输出约简集R=R-{a}。

算法通过行和与列和的同时限制d(a,R)，选出其中的必要属性，从而在条件区分能力选择上该算法表现更加精确。但是，不足之处是没有考虑到核属性在浓缩布尔矩阵时的重要性。接下来对算法2进行改进。

3基于核与改进的条件区分能力的反向删除属性约简算法

命题2[6,7,16]若布尔矩阵中某一行和为1，则1所在的列对应的属性称为核属性；若不存在这样的行，则核属性为空。

布尔矩阵可以同时反映出各个属性对论域的重要性和其中每个属性对各个集对的分辨情况。在一个确定的布尔矩阵中，元素cij为1(0)意味着第j个属性可区分开(不可区分开)第i个集对(Xk,Xl)；布尔矩阵行元素中1的数目决定着能把同一集对区分开来的属性的数目，1的数目越少说明1所对应的属性越重要。列中1的数目决定着此属性可区分的集对数，1的数目越多则此属性区分的能力就越强；

上述算法1和算法2都是以d(a,R)作为属性约简的启发式信息，但是，都并没有考虑到核属性对于简化决策表，删除布尔矩阵冗余信息的重要性。接下来，针对算法1、2都没对核属性进行考虑的不足之处进行改进，提出了一个新的启发式属性约简算法，并对算法的运行结果利用反向删除确保约简集的完备性。其实现思想为：首先，删除布尔矩阵CA有相同对象的行和不相容的行，相同对象的行仅保留一个；接着，寻找核属性加入到约简集R中；然后，更新布尔矩阵CAR，进而以改进的条件区分能力为启发式信息，进行属性约简；若布尔矩阵的某一行全为1，直接对其进行删除，消除冗余信息，对布尔矩阵进行浓缩。最后利用命题1思想，通过对属性集R反向删除过程，逐步实现最优约简的目的。

算法3基于核与改进的条件区分能力的反向删除属性约简算法

输入：决策系统S=(U,A,V,f)；

输出：最优约简集R；

Step1由决策系统S属性值构造矩阵CA；

Step2令R=∅，则CAR=CA；

Step3先求核属性，即选取行和为1的元素a。令R=R∪{a}，更新对应的CAR；

Step4判断CAR=∅是否成立，若成立，则转Step9；

Step5对CAR每一列求和，找出区分能力d(a,R)中的最大值，此时，当同时有多个列和最大时，在列和最大的这几个属性选取使行和S(pi)最小而且出现频率最高的属性加入到约简集中，即R=R∪{a}；

Step6同时删除a所在列中值为1对应的所有行和a所在的列，更新得矩阵CAR；

Step7若CAR≠∅，转Step5；反之,转Step8；

Step8对于初步得到的约简集R，以其全部属性构造布尔矩阵，若去掉其中某个属性所在的列后其对应的布尔矩阵增加新的零行，则该属性为必要属性，并且保留该属性；否则，该属性为冗余属性,将其删除；

Step9输出约简集R。

相对于算法1和算法2，改进后的算法通过行和和列和的同时限制找出必要属性，从而在条件区分能力选择上更加精确。改进后的算法在算法1和算法2的基础上考虑了核属性对约简的重要性，在约简的开始先进行核属性的判断，并对约简结果重新构造布尔矩阵，算法中Step8再利用反向删除法进行冗余性检查，从而确保了改进后的算法更加准确、有效和完备。

4实例分析

某决策表如表1所示，其中条件属性C={a,b,c,d,e}，决策属性D={g}。

表1　决策表

先对表1进行数据预处理，具体为冗余性检查，如果存在属性完全相同的对象，对其进行删除，只保留其中一个，接着matlab程序对冗余性删除后的决策表进行计算，得到如下的布尔矩阵：

(1) 按算法1进行约简

先计算CA各列的和分别为d(a,R)=8、d(b,R)=6、d(c,R)=8、d(d,R)=4、d(e,R)=4。接下来按照算法1的步骤选择一个列和最大的属性加入到核属性R中，则约简R有两种结果分别为R={a}或者R={c}，然后更新CAR；

若选择R={a}，重复以上操作，直至CAR=∅，则可得到约简结果R={a,c,e}，R={a,d,e}，R={a,b,e}；若选择R={c}，重复以上操作，直至CAR=∅，则可得到约简集R={c,b,e}，R={a,c,e}。因此由于第一步的选择不同将会导致多种结果。

(2) 按照算法2进行约简

先计算CA各列的和，即d(a,R)=8、d(b,R)=6、d(c,R)=8、d(d,R)=4、d(e,R)=4。可知a和c的列和最大，但行和最小且出现次数最多的属性为a。此时，更新矩阵CAR；

重复以上操作，直至CAR=∅，则可得到约简结果R={a,c,e}，R={a,b,e}，R={a,d,e}。

(3) 按照改进后的算法(算法3)进行属性约简

首先通过选取行和为1的元素求出核属性e，令R={e}，并更新CAR得到如下：

进而运用算法3中的步骤4、5进行计算，计算得各列的和分别为d(a,R)=5、d(b,R)=4、d(c,R)=5、d(d,R)=3，可知属性a和c的列和最大，但行和最小且出现次数最多为属性a，此时，得到新矩阵CAR；

重复以上操作，直至CAR=∅，则可得到约简结果R={a,b,e}，R={a,c,e}，R={a,d,e}。

再根据约简结果分别重新构造新的布尔矩阵，分别去掉各自属性后均出现零行，因此，最后得到约简集为R={a,c,e}，R={a,b,e}，R={a,d,e}。

接下来，将改进后的算法(算法3)与已有算法1、算法2进行对比分析，如表2和表3所示。

表2　三种算法约简结果

表3　算法对比分析

经过对三种算法的计算结果对比分析可以看出，① 算法1的约简结果并不是期望结果，算法2和算法3明显优于算法1；② 算法2和算法3的主要区别在于是否考虑每个属性对整个论域的重要性，通过核属性的计算可以初步删除冗余信息，从而减少论域的数据量，浓缩信息系统的规模。因此在做约简前，考虑核属性显得非常关键。另一方面也说明改进后的算法更适合一般信息系统的属性约简。③ 在实际问题中，对象个数N相对来说比较大，属性个数M一般较小，因此尽管改进后的模型在时间复杂度上略有增加，但改进后的算法准确性明显提高，因此这种改进是值得的。

上面实例中算法2和算法3约简结果是相同的，然而并不是所有的实例算法2和算法3约简结果是相同的。接下来再通过一个实例对三种算法进行比较，该信息系统经过matlab计算得到其布尔矩阵为：

分别利用上述三种算法求解如表4所示。

表4　三种算法约简结果

由约简结果可知，算法1的约简结果存在多个并且其中两个约简结果存在冗余的属性。算法2得到的约简集也存在冗余属性，其冗余性检验可以利用命题1证明。接下来对算法3的约简结果{a,d}进行分析。首先，利用命题1进行冗余性检验，重新构造一个新的布尔矩阵CR如下所示：

可以看出删除任何一个属性{a}或者{d}都会出现零行，所以这两个属性都是必要属性必须同时保留；其次，任何一个属性约简的算法都期望利用最少的属性个数来代替原属性集合对信息系统进行分类。基于上述分析可得出算法3得到的约简结果{a,d}是本实例期望得到的最优属性约简集。

两个实例均表明，改进后的算法在条件区分能力上更加准确，并且使约简结果更具有较强的完备性。

5结语

属性约简是粗糙集研究核心之一。本文通过将核与条件区分能力相结合，在对布尔矩阵进行浓缩的基础上，构造了以核和改进的条件区分能力为启发式信息的属性约简算法。另外，为了能找到一个更优或者最优的属性约简，在算法中增加了反向删除过程。实例表明改进后的算法在条件区分能力上更加准确，并且使约简结果更具有较强的完备性。本文的不足之处是当决策表的规模很大时，其复杂度将会明显增加，所以下一步，将借助布尔矩阵的性质，比如通过子串、偏序关系等概念对布尔矩阵进行初等行变换、压缩等[13]，对文中算法继续进行改进。

参考文献

[1] Pawlak.Rough Set[J].International Journal of Information and Computer Science,1982,11(5):341-365.

[2] 运士伟,刘庆伟,舒云星.决策表中粗糙集的布尔矩阵表示[J].计算机工程与应用,2007,43(10):177-224.

[3] 殷志伟,张健沛.基于浓缩布尔矩阵的属性约简算法[J].哈尔滨工程大学学报,2009,30(3):307-311.

[4] 李秀红,史开全.一种基于知识粒度的属性约简算法[J].计算机应用,2006,33(11):169-170.

[5] 吴强,周文,刘宗田,等.基于粗糙集理论的概念格属性约简及算法[J].计算机科学,2006,33(6):179-181.

[6] 李龙星,运士伟,杨炳儒.粗糙集及概念与运算的布尔矩阵表示[J].计算机工程,2005,31(14):16-17.

[7] 李龙星,运士伟,杨炳儒.基于布尔矩阵表示的粗糙集属性约简启发式算法[J].计算机工程,2007,33(10):205-206.

[8] Wong S K,Ziarko W.On optimal decision rules in decision tables[J].Bulletin of polish Academy of Sciences,1985,33(11-12):693-696.

[9] Ziako W.Introduction to the Special Issue on Rough Sets and Knowledge Discovery[J].International Journal of Computational Intelligence,1995,11(2):223-226.

[10] 苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684.

[11] 周海岩.采用布尔矩阵不完备信息系统的属性约简[J].计算机工程与应用,2010,46(1):119-121.

[12] 王道林.基于布尔矩阵的初等行变换的知识约简算法[J].计算机应用,2007,27(9):2267-2269.

[13] 高学军,丁军.基于简化差别矩阵的属性约简算法[J].系统工程理论与实践,2006,20(6):101-107.

[14] 刘文军,谷云东,冯艳宾,等.基于可辨别矩阵和逻辑运算的属性约简算法[J].模式识别与人工智能,2004,17(1):119-123.

[15] 高婷,刘文奇.一种基于布尔矩阵的新的属性约简完备算法[J].计算机工程与科学,2009,31(8):60-62.

[16] 童新安,运士伟,张永胜.基于布尔矩阵表示的粗糙集属性约简算法[J].洛阳理工学院学报:自然科学版,2009,19(1):69-71.

[17] 陈媛,杨栋.基于信息熵的属性约简算法及应用[J].重庆理工大学学报:自然科学版,2013,27(1):42-46.

CONVERSE DELETE ATTRIBUTE REDUCTION ALGORITHM BASED ON CORE AND IMPROVED CONDITION DISTINGUISHING ABILITY

Feng WeibingZhang Mei

(CollegeofSciences,Xi’anUniversityofScienceandTechnology,Xi’an710054,Shaanxi,China)

AbstractThe Boolean matrix representation of rough set theory is intuitive and easy to understand, the introduction of it provides a new train of thought for the research of rough set theory. This paper, based on studying some properties of Boolean matrix, and in view of the deficiency of existing Boolean matrix-based algorithm that it does not consider the importance of core attributes in enrichment of Boolean matrix, combines the attribute importance with the improved conditions distinguish ability, and proposes an attribute reduction algorithm which is based on core and improved condition distinguishing ability, thus ensures the completeness of the reduction set with the help of converse deletion. Examples show that the improved algorithm is more accurate in conditions distinguishing ability, and makes the reduction results have stronger completeness.

KeywordsBoolean matrixCondition distinguishing abilityAttribute reductionComplete algorithm

收稿日期：2015-07-13。国家自然科学基金项目(11402194)。冯卫兵，副教授，主研领域：数据知识管理，软件工程与理论。张梅，硕士生。

中图分类号TP301.6

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.063