基于可辨识矩阵吸收律的属性约简方法

宋 婷，陈战伟

(1.太原科技大学计算机科学与技术学院，太原 030024;2.中国移动通信集团山西有限公司，太原 030009)

粗糙集理论[1-4]是一种刻划不完整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。一般情况下，知识库中的知识并不是同等重要的，存在冗余知识或属性，这不利于做出正确而简洁的决策。粗糙集理论的核心思想就是在保持分类能力不变的前提下，通过属性约简，将知识库中的冗余属性排除、删减，找出问题的决策属性。

针对基于可辨识矩阵的一般约简算法，本文讨论了可辨识函数析取范式繁琐的求取过程以及耗时长的缺点，尤其不适用于实际应用中对象和属性数目庞大的决策系统，针对上述问题，本文在对可辨识矩阵研究的基础上，通过吸收律及引入属性重要性度量来简化可辨识函数，使其计算过程简化，从而构造基于可辨识矩阵吸收律及属性重要性的属性约简算法，代替了可辨识函数由合取范式向析取范式传统的转化模式。

1 基于可辨识矩阵的一般约简算法

Skowron提出了可辨识矩阵，定义如下[5-10]:

给定一个信息系统S= ＜ U，A，V，f＞，A=C∪D，C，D分别为条件知识(属性)集和决策知识(属性)集，ai(xi)表示的是对象xi在知识(属性)ai上的取值，D(xj)表示的是对象 xj在决策知识(属性)D上的取值，则该信息系统的可辨识矩阵为:

可以看出上述可辨识矩阵为对称矩阵，根据对称矩阵的特性通常只计算其上三角元素或者是下三角元素。根据分析可以得到:1)若两个对象对应的决策属性D取值不同，则两个对象对应的矩阵元素值包含两者所有条件属性值不同的知识(属性)，用此类条件属性去区分决策属性是否相同，决定决策属性取值;2)如若两个对象对应的决策属性D相同，这时不考虑属性所对应的任意条件属性是否相同，矩阵元素值都赋值为Ø，这就表明属性对应的条件属性对决策属性的值没有影响;3)若两个对象对应的决策属性值不同，但所有条件属性取值相同时，矩阵元素值都赋值为Ø.

上述矩阵特点:某个属性组合项包含单一的元素，把这类单个属性称为核属性，两个对象由核属性唯一区分，将其最后保留到约简集中。

由上述可辨识矩阵可以计算可辨识函数:△=∧(∨cij).可辨识函数的极小析取范式中的所有合取式构成约简。

由此得出基于可辨识矩阵的原始算法如下:

输入:信息系统 S= ＜ U，A，V，f ＞;

输出:信息系统S的属性约简集RED.

Step1:根据信息系统表中的对象关系列出可辨识矩阵;

Step2:设定集合he=Ø，找出可辨识矩阵中的核属性，并入集合he，再将集合he并入约简集中，即RED=he;

Step3:列出可辨识矩阵中不包含核属性的元素，依次并入K中，将其中所有属性组合项进行合取计算;

Step4:将Step3中的合取范式计算成析取范式;

Step5:在Step4中选取元素数目最少的合取式，将式中属性放入RED中，从而得到最终约简结果。

2 基于可辨识矩阵吸收律的属性约简算法

2.1 算法思想

基于可辨识矩阵的一般约简方法分三步:一、根据决策表建立可辨识矩阵;二、找出可辨识矩阵中的核元素;三、根据可辨识矩阵导出可辨识函数，将其转化为析取范式的形式，约简结果为析取范式中的任意一项合取式组合。

分析上述步骤二，存在以下现象:(1)矩阵中两个位置上的属性组合项间存在包含与被包含关系;(2)矩阵中两个位置上的属性组合项完全相同。从可辨识函数析取范式的求解过程可以看出最终的结果是对可辨识矩阵中的非空元素进行合取计算，上述现象在析取范式的求解中无形增加了计算量，由此可以根据合取过程中的元素吸收规则，在求解可辨识函数前增加一个步骤来简化可辨识矩阵。分析上述步骤三，在实际应用中，通常遇到对象和属性数目庞大的决策表，为了简化析取范式的求解过程，可通过属性重要性的度量，以及判断删除属性组合项后的矩阵状态，进行属性约简。分为如下三个步骤:

创建可辨识矩阵:集合W:初值 =Ø，用来存放创建矩阵时临时生成的元素。将矩阵中的每一个元素与集合W中的元素依次进行比较，对于原始矩阵中新生成的元素a:若集合W中存在某元素w包含a，则根据吸收律用a替换W中的w元素，并且在矩阵中找出等同于w的元素值，将其置空;若集合W中存在某元素w被新元素a包含，则根据吸收律将矩阵中等同于元素a的元素值置空;若集合W中不存在任一元素与新元素a产生包含或被包含关系，则在集合W中添加元素a，同时保留矩阵中的元素a.

计算属性重要性:对于化简后的可辨识矩阵，首先找出其中的核元素，并入约简集;列出与核属性不存在包含关系的属性组合项，计算每个单个属性的重要性值，由大到小排列，属性a的重要性为a在矩阵各个组合项中所占的比例值求和。计算方法如下:

判断属性组合项对矩阵状态的影响度:从上一步的排序中选取第一个属性b，删除矩阵中包含属性b的元素，若得到矩阵为空，将属性b并入约简集，算法结束，求得约简结果;若删除组合项后，矩阵非空，则还需继续做重复计算。

2.2 算法描述

算法说明:集合W:存放可辨识矩阵构造过程中临时生成的元素，初始值为空;集合Z:按由大到小的顺序存放各个属性的重要性计算值。

输入:信息系统 S= ＜ U，A，V，f ＞;

输出:信息系统S的属性约简集RED.

Step1:构造信息系统S的可辨识矩阵:

(1)构造矩阵生成的第一个元素并入W;

(2)依次比较集合W中元素与矩阵构造过程中得到的每一个元素X之间的关系:若存在A∈W且A⊆X，则将矩阵中等同于元素X的元素值置空;若A∈W且A⊇X，则将新元素X替换集合W中的A元素，并且将可辨识矩阵中等同于元素A的元素值置空，等同于元素X的元素值保留不变;若对于集合W中的任意元素A，A与X不存在包含或被包含关系，则在集合W中添加元素X，同时保留矩阵中的元素X;

Step2:列出核属性(即属性组合项数目为一的元素)，依次并入到集合RED中，删除可辨识矩阵中等同于核属性的元素值;

Step3:给集合Z赋初值:Z=Ø，依次计算可辨识矩阵剩余属性组合项中单个属性的属性重要性，根据计算值由大到小的顺序并入集合Z中;

Step4:从集合Z中选取属性重要性值最大的属性，赋给max;

Step5:删除可辨识矩阵中包含属性max的属性组合项，若所得可辨识矩阵为空，则将max并入约简集中，即 max∪RED→RED，算法结束;否则，转Step3.

3 实例分析

给定决策表(表1)，用文中提到的两种方法进行计算，加以对比。首先用基于可辨识矩阵的一般方法进行约简:

表1 决策表Tab.1 Decision table

根据一般可辨识矩阵算法求得的约简结果为:RED={a，c}，(a，d)或(b，d)。为了便于求解，上述例子包含的属性数目较少，但仍可得到这样的结论:可辨识函数合取式的计算是一个繁琐复杂的过程，特别对于大型决策表，其可辨识函数由析取式向合取式的转化可能是一个很难完成的计算过程。

将上述例子采用基于可辨识矩阵吸收律的约简方法求解，步骤如下:

(1)构造可辨识矩阵:按照2.1节理论描述中的矩阵构造方法建立矩阵，根据吸收规则，简化可辨识矩阵:

(2)计算上述可辨识矩阵中每个元素的属性重要性:

f(a)=1/2+1/2=1;

f(b)=1/2;

f(c)=1/2;

f(d)=1/2+1/2=1.

(3)判断删除属性组合项对矩阵状态的影响程度:由(2)得出:排序后属性a和d是重要性最大的属性。首先选取元素a:列出矩阵中包含属性a的属性组合项ab和ad，删除ab和ad，矩阵非空，将属性a并入约简集;此时的可辨识矩阵包含属性c和d，很明显两个属性的重要性相同，分别删除包含c和d的属性组合项cd，得到矩阵 =Ø，计算结束，约简结果为a∧c或a∧d。同理，若首先选取属性重要性最大的元素d，则得到的约简结果为a∧d或b∧d。故最终的约简结果为 RED={a，c}，(a，d) 或(b，d) ，可以看到与一般可辨识矩阵约简算法的结果相同。

4 结束语

总结基于可辨识矩阵吸收律的约简算法对原始方法进行了两方面改进:(1)根据合取过程中的元素吸收规则，在求解可辨识函数前增加一个步骤来简化可辨识矩阵，从而减少了矩阵中的属性组合项数目，以方便可辨识函数的计算;(2)在简化可辨识矩阵后，通过属性重要性的度量，以及判断删除属性组合项后的矩阵状态，来计算约简结果，从而代替了可辨识函数析取范式向合取范式转化的繁琐过程。针对基于可辨识矩阵的一般约简算法，讨论了可辨识函数析取范式繁琐的求取过程以及耗时长的缺点，尤其不适用于实际应用中对象和属性数目庞大的决策系统，由此通过吸收律及引入属性重要性度量来简化可辨识函数，使其计算过程简化，从而构造基于可辨识矩阵吸收律及属性重要性的属性约简算法。

[1]张文修，梁吉业，李德玉，等.粗糙集理论与方法[M].北京:科学出版社，2001.

[2]PAWLAK Z.Rough sets[J].International Journal of Information and Computer Science，1982，11:341-356.

[3]PAWLAK Z.Rough sets and intelligent data analysis[J].Information Sciences，2002，147:1-12.

[4]范敏，刘文奇，朱兴东.基于粗集可辨识矩阵的属性约简算法[J].计算机工程与应用，2004，13:79-81.

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

[6]金贵林，崔炳谋.改进可辨识矩阵的启发式知识约简及规则算法[J].兰州交通大学学报，2005，24(4):92-95.

[7]王国胤.决策表核属性的计算方法[J].计算机学报，2003，26(5):611-615.

[8]叶东毅，陈昭炯.不相容决策表属性约简计算的一个可辨识矩阵方法[J].福州大学学报，2005(1):11-15.

[9]SKOWRON A，RAUSZER C.The Discernbility Matrics and Functions in Information System[C]//Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory，Dordrecht:kluwer Academic Publishers，1992:331-362.

[10]芦晓红，陈世权，吴今培.基于可辨识矩阵的启发式属性约简方法及其应用[J].计算机工程，2003，29(1):56-59.