基于布尔矩阵的决策表属性约简算法

袁红丽，陈志佳

（陆军工程大学石家庄校区装备模拟训练中心，石家庄050003）

0 引言

粗糙集（Rough Sets）是由Pawlak 提出的。该理论作为一个数学工具，可以用来处理不精确的、不一致的、不完整的信息和知识，目前其在机器学习、云计算等领域被广泛应用。在实际应用中，属性约简是粗糙集理论研究的一个重要方向。

利用布尔矩阵的表示方法解决属性约简问题，为研究粗糙集理论提出了一个新思路。文献[2]给出了布尔矩阵如何表示粗糙集理论中概念与运算，证明了布尔矩阵表示的属性约简与代数形式表示的属性约简是等价的；文献[3]在文献[2]基础上提出了条件区分能力的概念，构造了一个属性约简启发式算法；文献[4]在研究文献[3]的基础上构造了基于核与条件区分能力、加权条件区分能力两种属性约简算法，但是文献[2-4]均未考虑有决策属性的情况。文献[5]给出了决策表信息系统中的粗糙集理论的布尔矩阵表示，证明了相对约简在布尔矩阵表示形式下与代数表示下是等价的；文献[6]针对传统的Skowron 属性约简算法的不足之处，提出一种新的基于浓缩布尔矩阵的属性约简算法，文中并未提及决策属性的分类重要性；文献[10]提出了基于核与改进的条件区分能力的反向删除属性约简算法，但是也未提及决策属性的分类重要性。

本文针对现有算法中未提及决策属性的分类重要性情况进行了改进，增加了决策属性的布尔矩阵，修改了计算相对核、相对约简的方法，提出了一种基于布尔矩阵的属性约简算法。

1 基于布尔矩阵的决策表属性约简算法

1.1 算法思想

本算法为了解决文献[3]、文献[4]未考虑决策属性以及基于核与改进的条件区分能力的反向删除属性约简算法中没有考虑到决策属性重要性的基础上，在以下几个方面做了改进：

（1）增加了决策属性D 的布尔向量β

决策表信息系统的知识约简就是指，在保持原始决策表中，条件属性和决策属性之间的依赖关系不发生变化的前提下，删除冗余属性和属性值[11]，因此当决策表信息系统的条件属性部分转化为布尔矩阵的同时，决策属性也需要转化为布尔矩阵。增加决策属性的布尔向量，b 的计算方法同布尔矩阵的计算方法，某行的值的和若大于等于1，表示(Xk,Xp)属于同一个pos（d），即：CA中对应的该行中属性值为1 的属性的分类能力，对于区分不同的决策属性起到了至关重要的作用，也就是说该属性的不同，导致了决策属性的不同，若为0，则说明该属性的相同与否都对决策属性不起作用。

（2）改进了相对核的计算

在本算法计算核的过程是：首先判断布尔矩阵Mc中有无sum（Mc（i，j））=1 的行，如果有，则判断向量β中对应行的元素的和是否大于等于1，如果是，则布尔矩阵Mc 中元素1 所在列对应的某个属性即为相对核的一个属性，循环判断布尔矩阵Mc 中的所有行，所有这样的属性构成了决策表信息系统的相对核；若没有这样的行，则相对核为空。

在本算法中，除了考虑布尔矩阵MC中每行属性值为1 的个数外，还要考虑向量中该行的值，解决了只考虑布尔矩阵MC中每行属性值为1 的个数无法求决策表中相对核的问题。

（3）改进了相对约简的计算

在本算法中，找到核及部分约简，更新布尔矩阵Mc 时，首先删除属性R 对应的列中1 对应的行，其次删除向量b 中对应的这些行，然后删除属性R 所在的列，同时删除向量b 中值为0 的行和布尔矩阵Mc 中对应的这些行。循环判断该决策表信息系统中的所有条件属性，删除这些冗余信息，对布尔矩阵快速浓缩，考虑了条件属性与决策属性的依赖关系的重要性，保证了相对约简的正确性。

1.2 算法

输入：决策表信息系统K=(U,C ∪D,V,f)，其中U是论域，C 为条件属性集，D 为决策属性集

输出：决策表信息系统K 的布尔矩阵matrix、及核属性Core、属性约简Red。

Begin

计算pos（C），pos（D），posC（D）

求出C 的布尔矩阵matrix

求出D 的布尔矩阵B

计算matrix 矩阵中每行的和

针对和为1 的行，逐行判断

If（B 中对应的行是不是1）

如果是，则把matrix 矩阵的该行l 中值为1 所对应的属性加入到Core 中

再将整个matrix 矩阵中，l 中值为1 的行全部置为0；

End

for jj=1：m将matrix 中所有l 列的值为1 的行删掉，将l 列也删掉，更新matrix

End

Red（core，yy，BB，matr）;

End

Red（core，yy，BB，matr）

{

While（matrix 矩阵中如果不是全0）

{

求出matrix 矩阵中各列的和；

找出和值最大的列号n1;

For i=1：m

将整个matrix 矩阵中，n1 列的值为1 所在的行置0；

If（B 中该行的值不为0 且matrix 矩阵中该行的值也不全是0）/*更新matrix 矩阵时，除了要考虑非0 行以外，还要考虑B 矩阵中该行元素的值，若为0 表示该行的属性对决策表属性没有起作用，若为1 表示该分类对决策属性起作用。*/

将matrix 该行保留；

end

end

}

}

最后将布尔矩阵matrix，及核属性Core、属性约简Red 的结果输出。

2 仿真实验

基于布尔矩阵表示的粗集属性约简启发式算法，只是以条件区分能力为启发信息，并没有考虑到核信息的作用，经证明其缺乏完备性[4]，在文献[4]中，作者针对这种情况进行了改进，提出了两个改进算法：基于核与条件区分能力的属性约简算法和基于加权条件区分能力的属性约简算法，为叙述方便，下文分别称这两种算法为算法1、算法2。

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

表1 决策表

（1）算法1、算法2 进行约简

使用算法1 进行计算，得到核为：Core={ }a,b,c,d ，更新布尔矩阵matrix 后，matrix 为空，因此得到的约简为Red={a,b,c,d}；使用算法2 进行计算，matrix 矩阵中，各个属性的权值和，分别为：27.75，25.25，18.5833，19.4167，选取权值最高的属性a，加入到Red 中，Red={a}，更新matrix，计算权值和，分别为：9.5，8，8.5，选取权值最高的属性b，加入到Red 中，Red={a,b}，更新matrix，计算权值和，分别为：3，4，选取权值最高的属性d，加入到Red 中，Red={a,b,d}，更新matrix，计算权值和，分别为：2，选取权值最高的属性c，加入到Red中 ，Red={a,b,d,c} ，最 终 得 到 属 性 约 简为Red={a,b,c,d}。

（2）使用本文算法进行约简

首先，计算布尔矩阵MC中每行的和，找到和为1的行，如果向量β 中对应该行的值为1，则将MC该行中1 对应的属性加入到核中，最后得到核为：Core ={a ,d} ，更新布尔矩阵MC，删除该属性对应的列中1 所在的行包括向量β，以及该列；然后计算布尔矩阵MC中每列的和，选取列和最大的属性加入到约简中，更新布尔矩阵MC，直至MC为空。最后得到最优约简为Red={a,b,d}。该算法只能得到最优约简，不能得到全部约简。

（3）使用基于Skowron 差别矩阵的决策表属性约简算法进行约简。

首先计算pos（C）={{1}，{2}，{3}，{4}{5}{6}{7}，{8}，{9}，{10}，{11}，{12}，{13}，{14}}，pos（D）={{1，2，6，8，14}，{3，4，5，7，9，10，11，12，13}}，posc（D）={{1}，{2}，{3}，{4}{5}{6}{7}，{8}，{9}，{10}，{11}，{12}，{13}，{14}}，然后计算差别矩阵，搜索差别矩阵，从中找出单属性元素，并将其赋值给相对核，得到相对核为：Core={a ,d} ，相对约简为：Red={a ,b,d}，{a,c,d}。

由此可以看出，算法1 和算法2 未考虑决策属性，所以结果并未体现出条件属性与决策属性的依赖关系。本文算法虽然得不到全部约简，但是能得到最优约简。归纳如表2。

表2 四种算法约简结果

3 实验结果

基于以上的研究，该文选用UCI 机器学习数据库中的4 个数据库和表1 在PC（Intel Core i5-5200U CPU@2.2Hz，内存8.00G，64 位）上进行试验，分别采用算法1、算法2 和该文提出的约简算法进行属性约简，所有算法均在MATLAB 2014b 的基础上实现。实验结果如表3。

表3 约简算法的比较

由表3 可见，本文提出的基于布尔矩阵的属性约简算法在4 个数据集上的属性约简效果要优于其他算法。

4 结语

本文将条件属性C 与决策属性D 的依赖关系与条件区分能力相结合，在构建条件属性布尔矩阵matrix和决策属性布尔矩阵β 的基础上，构造了基于布尔矩阵的决策表属性约简算法。实例表明，该算法具备很好的完备性，能够得到决策表的最优约简。本文研究的是决策属性只有一个的情况下，多个决策属性的研究是下一步的研究方向。