何 英，何 丹

HE Ying1，HE Dan2

（1.南昌航空大学 现代教育技术中心，南昌 330063；2.南昌航空大学 信息中心，南昌 330063）

0 引言

Rough集理论自80年代初由波兰学者Z.Pawlak提出以来，是一种迅速发展的既有理论又有应用的研究领域[1]。粗糙集理论[2,3]是Pawlak 等人提出的一种处理不精确、不完全信息的新型数学工具。由于二进制的可实现性，很多学者将其引入属性约简算法中，文献[5,6]用二进制可辨矩阵设计了基于正域的属性约简算法，但都没有解决当二进制可辨矩阵列的属性频率出现次数相同的情况下选取加入到约简中的顺序问题。本文在文献[5-7]的基础上，提出了以属性频率和属性关于U/D正域之和为启发式信息的二进制可辨识矩阵列的属性约简算法，解决了当二进制可辨识矩阵列的属性频率相同的情况下的属性选取问题。

1 属性约简基本概念

定义1 一个信息系统S，表示为S=（U,A,V,f），其中U={X1,X2,…,Xn}是论域；A是属性集合；V=∪va，a∈A，va表示属性的值域；f=U×A→V是一个信息函数，对x∈U，a∈A，有f（x,a）∈va。若A可分为条件属性集C和决策属性集D，即A =C∪D，C∩D=φ，则该信息系统称为决策表。

定义2 设R是一个等价关系族，r∈R，如果IND（R）=IND（R-{r}），则称r在R中是可被约去的知识；如果P=R-{r}是独立的，则P是R中的一个约简。

定义3 在信息系统S中,若P,Q∈A，则Q的P正域POSP（Q）定义为：

其中P_X为X的P下近似。Q的P正域是U中所有根据分类U/P的信息可以准确地划分到关系Q的等价类中去的对象集合。

2 二进制可辨矩阵[8]

定义4 设决策表为T=（U,C,D,V,f），其中U={u1,u2,…,un}，C={c1,c2,…,cm}，D={d}则决策表T相应的二进制可辨矩阵MT构造为：矩阵的每一列对应一个条件属性，共有m列，每一行对应一对论域中的对象（up,uq），有n（n-1）/2行。设矩阵中一元素m（（p,q）,i）所在行对应的应对象对（up,uq），所在列对应条件属ci，则

这样得到的一个矩阵，称之为相应于决策表T=（U,C,D,V,f）的二进制可辨矩阵。

命题1 若二进制可辨矩阵中某一行只有一个元素为1其余元素均为0，则元素1所在列对应某个属性，所有这样的属性构成信息系统的核或决策表的相对核。若没有这样的行，则核或相对核为空。

3 属性重要性的度量方法

对于决策表T=（U,C,D,V,f）：用P（ci）（ci∈C,1≤i≤|C|）表示ci在二进制可辨识矩阵中的属性频率；用MAX（P（c））表示二进制可辨识矩阵中属性c出现的最大频率；用NMAX表示二进制可辨识矩阵中属性出现的频率等于最大频率的属性总数，NMAX=|{ci|P（ci）=MAX（P（c））,1≤i≤|C|}|；条件属性ci∈C（1≤i≤|C|）的重要性可以用ci的属性频率P（ci）和U/{ci}关于U/D正域POSU/{ci}（U/D）来度量，用Gci表示，则Gci可通过公式1给出，如下所示。

4 属性重要性的启发式属性约简算法

在二进制可辨矩阵中，对于那些只有一个元素为1其余元素均为0的行，元素1所在列的属性一定属于核，而对于那些有多个元素为1的行，在这些元素为1所在的列中，那些所含1的个数最多的列对应的属性虽未必是核属性，但具有很强的分辨能力，因此这样的属性在形成约简，尤其是最小约简的过程中具有重要地位。

算法 二进制可辨矩阵属性重要性的启发式属性约简。

输入：决策表T=（U,C,D,V,f）

输出：决策表T属性约简

1）根据给定的决策表T=（U,C,D,V,f）产生二进制可辨矩阵M，将M中全为1和0的行删除，得到新的Mnew。置矩阵MA←Mnew，用Reduction表示属性约简，初始值为Reduction=φ。

2）对每一行，若该行只有一个元素为1，则将该元素所对应的属性为核属性，并将该属性加入到Reduction，即Reduction←Reduction∪{ci}，其中ci∈C,1≤i≤|C|。

3）从MA中删除各行只有一个元素为1的行及该行元素1所对应的列值为1的行，将得到的新矩阵MAnew再赋给MA。如果MA=φ，则转到7），否则到4）。

4）将MA的各列纵向相加，并将结果存入相应col[ci]中，其中ci∈C,1≤i≤|C|。

5）用一维数组G[|C|]表示属性的重要性，初始值为G[ci]=0，其中ci∈C,1≤i≤|C|。根据公式1计算属性重要性；在MA中将属性重要性最大的属性ci列及ci列上值为1的元素所对应的行去掉；将得到的新矩阵再赋给MA，并将Reduction←Reduction∪{ci}。

6）将MA中行全为1和0的行删除，将得到的新矩阵再赋给MA。如果MA≠φ，则转到4）。

4）输出一个约简Reduction。

5 实例分析

表1中C={a,b,c,d}为条件属性，D={e}为决策属性，A=C∪D，对表1建立二进制可辨矩阵如表2所示。

表1 决策表T=（U,C,D,V,f）

表2 决策表T的二进制可辨矩阵

将表2中去掉（1,7）、（2,4）及（5,6）三行，并将属性c中为1的行去掉，得表3。

表3 化简后的二进制可辨矩阵

表3中a,b,d各列的属性频率都为6，根据公式（1）计算属性的重要性，计算过程如下：

U/{e}={Y1,Y2,Y3} ,Y1=（1,3,6,7）,Y2=（2,5）,Y3=（4）；U/{a}={X1a,X2a},X1a=（1,3,7）,X2a=（2,4,5,6）

U/{b}={X1b，X2b},X1b=（1,5,6,7）,X2b=（2,3,4）；U/{d}={X1d,X2d},X1d=（1,2,4,5,7）,X2d=（3,6）

由以上公式可得：G[a]=1+3/4=1.75,G[b]=1+0= 1,G[d]=1+2/4=1.5。可知a的属性的重要性最大，即Reduction={a,c}。将表3中a列及a列值为1的行去掉，再将行都为1的行删除，得到的表为空，因此Reduction={a,c}为最后这个决策表的约简集。

6 复杂度分析

设决策表中有m个条件属性，n个对象，在最坏情况下，构造二进制可辨矩阵需要比较mn（n-1）/2次，复杂度为O（mn2）；根据文献[9]的计算正域的方法，计算正域的最大的时间复杂度为O（（|C | + 1）| U |log | U |）= O（mnlogn），而计算MAX（P（ci））的最大的时间复杂度为O（n2）,所以算法第7步的时间复杂度为MAX（O（（mnlogn）,O（n2））。因此本算法的时间复杂度为O（mn2）。

通过上述分析，可见本算法在文献[5-7]的基础上，并解决了当二进制可辨识矩阵列的属性频率相同的情况下的属性选取问题。当决策表的复杂程度较高时，它使得求解的复杂程度大大降低，是一种获得属性约简的简单而有效的方法。

[1]刘清.Rough集及Rough推理[M].第一版.北京：科学出版社,2001.

[2]Pawlak Z.Rough sets and intelligent data analysis[J].Information Sciences：2002,147：1-12.

[3]Pawlak Z,Skowron A.Rough sets：Some extensions[J].Infor mation Sciences：2007,177：41-73.

[4]支天云,苗夺谦.二进制可辨别矩阵的变换及高效属性约简算法的构造[J].计算机科学：2002,29（2）：140-142.

[5]钱文彬,徐章艳,黄丽宇等.基于信息熵的二进制差别矩阵属性约简算法[J].计算机工程与应用：2010,46（6）：120-123.

[6]任小康等.基于可辫识矩阵的属性频率约简算法[J].兰州大学学报：2003,43（1）：138-140.

[7]Felix R,Ushio T.Rough Sets-based Machine Learning Using a Binary Discernibility Matrix.IPMM99 published：1999：299-305.

[8]刘少辉,盛秋戬,吴斌,等.Rough集高效算法研究[J].计算机学报：2003,26（5）：524-529.