二进制辨识矩阵的属性约简及不必要属性的求解

时间：2024-12-28

黄丽萍

(闽南师范大学计算机学院，福建漳州 363000；数据科学与智能应用福建省高等学校重点实验室，福建漳州 363000；福建省粒计算及其应用重点实验室，福建漳州 363000)

0 引言

粗糙集理论自提出后就被广泛地应用，进行了多方面的研究．其中属性约简是粗糙集理论研究的主要内容．在对约简的研究中，利用二进制求约简是一个重要分支．二进制辨识矩阵是对skowron辨识矩阵[1]的改进，采用二进制表示形式，使计算更加简单直观．因此，采用二进制辨识矩阵进行属性约简具有一定的意义.

Hu等人在1995年提出了基于skowron矩阵的核属性求解算法[2]．Felix等人[3]在1999年提出了只由0和1构成的二进制可辨识矩阵．文献[4]利用Felix提出的二进制可辨识矩阵计算核属性并得出相应的属性约简方法．文献[4，5]指出Felix没有考虑决策表的不一致性，给出了二进制分辨矩阵的新定义和求解核属性的方法，并验证了该方法的正确性．王锡怀等[6]利用二进制差别矩阵构造了适用于一致和不一致决策表的广义信息表，提出了一种启发式算法，该算法可以计算各个属性的重要性，但没有对不兼容的情况进行考虑．文献[7，8]分别从上近似和下近似对二进制可辨矩阵进行定义，利用这两个矩阵可以得到属性核和约简结果．文献给出了一种广义二进制辨识矩阵用于处理不完备信息系统的约简．二进制辨识矩阵从最初的分别只对辨识矩阵的行或列[10]方向考虑并度量属性重要度，到现在同时从行和列两个角度对属性重要度进行判断[11，12]．

为了更加方便、直观地得到属性约简，本文对二进制辨识矩阵的求解算法进行改进，首先运用文献[12]的方法得到简化的二进制辨识矩阵；然后在文献[11，12]的基础上给出一种新的二进制辨识矩阵约简算法，算法同时从二进制辨识矩阵行和列的角度对属性的重要度进行度量，在获取约简属性的同时对二进制辨识矩阵已经能被区分的对象进行删减，从而有效地提高算法效率，并得到最小属性约简.文献[13，14]利用布尔矩阵求取了决策信息系统属性核、绝对不必要属性和相对必要属性.本文从二进制辨识矩阵的角度在求取约简的同时，求出当约简集中含有某一属性后，对决策表的对象没有进一步的区分能力的相对不必要属性和绝对不必要属性，并通过实例和实验来说明算法是正确的和有效的．

1 理论基础

定义2[14]给定S=〈U，C∪D，V，f〉和P⊆C∪D，P在U上的不可辨识关系定义为：

IND(P)={(x，y)|(x，y)∈U×U∧(∀b∈P，b(x)=b(y))}．

定义3[12]设决策表S=〈U，C∪D，V，f〉，其中U={u1，u2，…，un}，C={c1，c2，…，cn}，D={d}，则决策表S的二进制分别矩阵BM=(BM(i，j，ck))l，其中l≤n(n-1)/2×m．

其中BM((i，j)，ck)表示若两个样本的决策属性的值不同，决策表的第i和第j个对象是否能够通过第k个条件属性区分出，若能区分则BM(i，j，ck)=1，否则BM(i，j，ck)=0．

2 约简算法

本节主要给出一种基于二进制矩阵的属性约简和不必要属性的求解算法方法．先把决策信息系统转换为二进制辨识矩阵; 然后通过行和列中1的个数对属性重要性进行判定; 最后根据所得的属性重要性进行约简属性的选择，得到决策信息系统的属性约简．通过判断是否存在某列的取值全0来获取绝对不必要属性或相对不必要属性．

定理1[12]S=〈U，C∪D，V，f〉为一致的决策表，BMn×m为S的二进制辨识矩阵，若存在唯一的属性k∈{1，2，…，m}，使得BM(i，j，ck)=1，而对于∀a∈{1，2，…，k-1，k+1，…，m}，均有BM(i，j，ca)=0，则k所在的列为S的核属性．

对于属性k∈{1，2，…，m}，使得BM(i，j，ck)=1，而对于∀a∈{1，2，…，k-1，k+1，…，m}，均有BM(i，j，ca)=0，则删除k列中属性值为1的行，表示这些对象已经可以通过属性k区分开来，不需要进一步地区分．

定理2S=〈U，C∪D，V，f〉为一致的决策表，BMn×m为S的二进制辨识矩阵，若ck所在的列，对于∀i∈{1，2，…，n}和∀j∈{1，2，…，m}均有BM(i，j，ck)=0，则ck为不必要属性．

若ck所在的列，对于∀i∈{1，2，…，n}和∀j∈{1，2，…，m}均有BM(i，j，ck)=0，表示该ck不能进一步辨识任何对象，ck为相对不必要属性．相对于前面获取的约简属性而言ck为不必要属性，若获取的约简属性为核，则ck为绝对不必要属性.

针对文献[11，12]中算法的不足，给出改进的BIRD算法：

输入：决策信息系统S=〈U，C∪D，V，f〉；

输出：C相对于D的一个约简Red和不必要属性集Noneed;

步骤1：构造简化二进制辨识矩阵BM.

步骤2：初始化属性约简Red=∅.

步骤3：计算BM中每一行元素的和，若存在和为1的行，则选择这些行中1对应的属性k，加入到约简集中，Red={k}．若不存在和为1的值，则选择Rmin对应属性中max(C(c))的列k为约简集Red={k}．

步骤4：删除k中属性列值为1的行获得删减后的二进制矩阵BM′，计算BM′的每一列的和，若存在和为0 的列w，则Noneed={w}．

步骤5：重复步骤3和4直到BM′中所有的属性列的和为0或步骤4中无可删除行．

3 实例分析

给定决策信息表S=〈U，C∪D，V，f〉如表1[14]所示，其中论域U={x1，x2，x3，x4}，条件属性C={a1，a2，a3，a4}，决策属性D={d}．

表1 决策信息表

S的二进制辨识矩阵如表2所示.计算各行的和为3，3，2，3，1根据定理1，可得该决策信息表的核为core={a3}．删除属性列a3为1的行，即这些对象在a3的取值为1，表示这些对象能由a3区分，可以删除这些对象.从而得到约简后的表，如表3所示.

表2 二进制辨识矩阵

从表3可以看出a4的取值为0，它不能进一步区分余下的对象.a4为不必要属性，因为其对于核属性是不必要的，所以为绝对不必要属性.在其余的对象中a1或a2都可以区分它们，所以该决策表的约简为Red1={a3，a1}和Red2={a3，a2}同文献[15]．

表3 删除a3取值为1的行后的矩阵

给定决策信息表S=〈U，C∪D，V，f〉如表4[13]所示，其中论域U={x1，x2，x3，x4，x5，x6}，条件属性C={a1，a2，a3，a4，a5，a6}，决策属性D={d}．

表4 决策信息表

S的二进制辨识矩阵如表5所示.

表5 二进制辨识矩阵

该决策表无核属性，计算各行的和为2，4，4，2，3，5，6，5选取Rmin=2的行，分别为第1和第4行．选择Rmin的值为最小的行，表示这些对象用了最少的必要属性来区分，这些属性是必要属性.第1行中值为1的属性列中1的和分别为f(a2)=6，f(a6)=6；第4行中值为1的属性列中1的和分别为f(a2)=4，f(a6)=5．选取属性max(C(c))=a2为约简的属性，选择1中最少的行后接下来选择列中1最多的个数表示其能区分的对象越多，属性越重要．从而选择约简属性Red={a2}．

删除a2中属性值为1的行得到如表6所示.

同理可得：表6中各行的和为4，2选取Rmin=2的行，第2行．计算该行中属性列为1的和为f(a3)=2，f(a4)=1，选取属性max(C(c))=a3为约简的属性．Red={a2，a3}．因a3列中没有属性值为0的行，所以算法结束．Red={a2，a3}．本文算法的约简个数同文献[13]，为最小约简.

表6 删除a6取值为1的行后的矩阵

4 实验仿真测试及结果分析

为了进一步验证BIRD算法，本文从UCI(University of California Irvine)中选取了5个数据集，各数据集的描述如表7所示.

表7 数据集信息

本文算法BRID、文献[13]算法1，2和文献[14]的算法3约简结果如表8所示.

表8 约简结果

其中约简长度是用使用 RSES2粗糙集软件计算出来的结果5～7表示约简结果的属性个数范围为5～7，33表示有33个约简集．从表8可以看出，BIRD在属性约简(表8中的Red)个数上取得了较好的结果，可得最小约简，而文献[12]中给出的方法在Zoo，Spectf，Spect和lymn上没有得到最小约简，是由于算法1，2只从列的角度来度量属性的重要度.

用Zoo数据集合来说明本文的BRID算法对不必要属性(表8中的Noneed)求解的正确性．求得的约简过程如下：求得核属性为6，13后，去掉核属性中为1的行后，属性列为0 的属性列为2，5，15，即2，5，15为绝对不必要属性；REST的约简结果集是从下标0开始的从图1可以看出属性2，5，15，即a1，a4，a14不在Zoo的约简集中，为绝对不必要属性，与本文的算法一致．继续添加约简属性为3，该属性没有相对不必要属性，可以从表10可以看出a2可以和其他属性构成属性约简，添加属性8后，该属性的相对不必要属性为7，从图2可以看出所有的约简集合包含a7的属性就没有a6，也与本文的算法一致．

使用REST软件对Zoo约简得到相应的结果如下图1，2所示：

综上所述，本文算法在不需要求取全体约简集的情况下可以获得最小约简集、绝对不必要属性或相对不必要属性.