目不相容决策表求核方法

1、辽宁对外经贸学院第六届学术研讨会题 目：不相容决策表求核方法学 科：工学单 位：信息技术系作者姓名：陈凤娟二一年十一月不相容决策表求核方法陈凤娟（辽宁对外经贸学院信息技术系,辽宁省 大连市 116052）摘 要 在不相容决策表中计算核属性有很多方法，这些方法得到的结果并不完全一致。使用代数定义的方法求核可以忽略不相容决策表中不相容信息的影响，得到核属性，很多改进的差别矩阵都能得到与代数方法一致的核属性。论文通过分析不相容决策表，提出相容核与不相容核的概念。然后分析了三个不相容决策表中的相容核与不相容核，比较了几种现有的不相容决策表的求核方法，这些方法要么不能完全求出相容核与不相容核，要么不能把

2、得到的相容核与不相容核区分开来。针对这一问题，对HU差别矩阵进行改进，得到两个新的差别矩阵，这两个矩阵能分别计算出相容核与不相容核。关键词 不相容决策表; 相容核; 不相容核; 差别矩阵Methods for Calculating Core Attributes of Inconsistent Decision TableChen Fengjuan(Department of information technology, Liaoning University of International Business and Economics, Dalian 116052)Abstract T

3、here are many calculation methods for core attributes of inconsistent decision table. But the results of these methods are not exactly the same. The algebraic definition method ignores the impact of inconsistent information of inconsistent decision table. Many improved discernibility matrix can get

4、the same results with algebraic definition method. Two concepts core for consistent information and core for inconsistent information have been proposed in this paper. Then analyzes the core of three inconsistent decision tables and compare several existing methods. These existing methods either can

5、not find the core for inconsistent information, or cannot distinguish core for consistent information and core for inconsistent information. Two new matrices have been proposed to solve this problem. One of the two new matrices can calculate core for consistent information, the other one can calcula

6、te core for inconsistent information.Key words Inconsistent Decision Table; Core for Consistent Information; Core for Inconsistent Information; Discernibility Matrix 中图法分类号：TP18 1 引言属性约简（知识约简）的计算是粗糙集理论中的一个主要研究方向。属性核是决策表中最重要的特征集合，它包含在所有属性约简之中，可以作为属性约简的基础，因此很多属性约简算法是从属性核出发，在属性核之上通过一定的方法选取属性增加到核中，从而得到约

7、简集合1。HU XIAOHUA等学者在文献2中给出的利用改进差别矩阵求核的方法是一个很有效的方法，但是有学者已经证明该方法不适用于不相容决策表中求核34。目前，在不相容决策表的求核问题上，主要的方法有使用代数定义、HU差别矩阵、使用信息熵定义5和改进的HU差别矩阵346等方法，但这些方法并没有完全解决不相容决策表的求核问题。本文深入分析不相容决策表的性质，把不相容决策表中的核属性分为相容核与不相容核两部分，以文3和文5中使用的三个不相容决策表为例，分析这三个不相容决策表的相容核与不相容核，然后比较现有的求核方法，发现这些方法不能够得到正确的相容核与不相容核，通过改进HU差别矩阵得到两个新的差别

8、矩阵，利用这两个新的矩阵计算出不相容决策表的相容核与不相容核。2 基本概念代数观中的正域、属性必要性及核属性的相关概念如下1。定义1 设U为一个论域，P,Q为定义在U上的两个等价关系族，Q的P正域记作POSP(Q)，定义为定义2 设U为一个论域，P,Q为定义在U上的两个等价关系族，对于P中的关系r，若有 成立，则称为P中Q不必要的；否则称r为P中Q必要的。定义3 设U为一个论域，P,Q为定义在U上的两个等价关系族，P中所有Q必要的原始关系族，称为P的Q核，记为。核属性是所有必要属性的集合。从上面的定义可知，当去掉某个属性会导致正域发生变化时，则该属性是核属性。在不相容决策表中，论域中的元素可以

9、通过计算正域的方法，分成不包含冲突信息的相容元素和包含冲突信息的不相容元素两部分。使用代数定义求核的方法通过比较正域的变化得到核属性，由于不相容元素的划分块之间的合并对正域完全没有影响，因此，这种方法能忽略掉不相容决策表中的不相容元素之间的变化规律，把导致正域发生变化的属性称为核属性，本文称这种核属性为相容核属性。有两种情况会导致一个不相容决策表的正域发生变化一个相容元素的划分块和一个不相容元素的划分块发生合并；一个相容元素的划分块和另一个相容元素的划分块发生合并。（多于两个的划分块的合并都可以分解成上面两种情况）由于这两种情况会影响正域，因此定义不相容决策表的相容核如下。定义4 在不相容决策

10、表中，若去掉某一个条件属性，会使包含相容元素的划分块与其他划分块发生合并，导致正域发生变化，则该属性属于相容部分的核属性，简称相容核。从决策表的正域的变化中不能看到不相容信息是否发生了变化，由于负域与正域完全对应，所以也不能用负域来衡量不相容部分是否变化。由于正域发生变化的本质就是包含相容元素的划分块与别的划分块发生了合并，因此可以用不相容信息的划分块之间的合并作为衡量不相容部分是否发生变化的标准。也就是说去掉某个属性会导致不相容信息的划分块发生合并，那么这个属性对不相容部分就是必要的属性，是不相容部分的核属性，为了区别于相容部分的核，称这部分核属性为不相容核。这种属性的存在能保证不相容决策表

11、中不相容部分的划分块保持不变。根据这类属性与决策表的不相容部分信息的变化之间存在的内在联系，给出如下的不相容决策表的不相容核的定义。定义5 在不相容决策表中，若去掉某一个条件属性，会使包含不相容元素的划分块之间发生合并，则该属性属于不相容部分的核属性，简称不相容核。对于一个不相容决策表，完整的核属性包含两部分，即相容核与不相容核。相容核部分能考察相容部分的变化，而不相容核能考察不相容部分的变化。一个核属性只能是相容核与不相容核中的一种，不可能二者兼为。3 已有不相容决策表求核方法存在的问题在文3中，叶东毅教授分析了HU差别矩阵运用于不相容决策表中求核时产生的错误，并改进HU差别矩阵，得到与代数

12、定义相同的结果。叶的方法就是通过改进HU矩阵，把不相容决策表中的不相容信息对HU矩阵的影响去掉，只考虑影响相容部分信息的属性。类似的改进矩阵的方法还有很多，如杨明的改进矩阵等46，这些方法虽然得到不同形式的差别矩阵，但是它们的思想是完全一致的，都是把不相容决策表中影响计算结果的冲突信息忽略掉。这类改进HU矩阵的方法计算结果与代数定义方法完全相容，可以与代数定义方法归为一类。在文5中，王国胤教授使用条件信息熵的方法计算不相容决策表的核，由于条件信息熵是由不相容信息产生的，因此计算条件信息熵的方法能考察到不相容部分的变化，但是由于条件信息熵是由比率得到的，因此当某些不相容部分的划分块发生了合并，而

13、其比率不发生变化的情况，就会被条件信息熵方法忽略掉，导致该方法不能判断所有的不相容划分块发生合并的情况。下面针对文3和文5中用到的三个不相容决策表，分别分析这些决策表中相容部分划分块和不相容部分划分块的变化，从而说明现有的求核方法存在的问题。 表1 决策表1U C1 C2 C3 D x1 1 0 1 1 x2 1 0 1 0 x3 0 0 1 1 x4 0 0 1 0 x5 1 1 1 1 决策表1的划分如下：U/IND(C1,C2,C3)=x1,x2,x3,x4,x5，U/IND(D)=x1,x3,x5,x2,x4,正域POSC(D)=x5。去掉属性C1,有U/IND(C2,C3)=x1,x

14、2,x3,x4,x5；去掉属性C2,有U/IND(C1,C3)=x1,x2,x5,x3,x4；去掉属性C3有U/IND(C1,C2)=x1,x2,x3,x4,x5；从上面的计算可知：决策表1中相容部分为x5，相容部分的划分为x5，存在不相容信息的部分为x1,x2,x3,x4，不相容部分的划分为x1,x2,x3,x4；去掉属性C1，相容部分的划分没有发生变化，而不相容部分的划分发生了变化，即不相容部分的划分块x1,x2和x3,x4合并成了一个划分块x1,x2,x3,x4。去掉属性C1，导致不相容部分的划分块发生合并，由不相容核的定义，C1属于不相容核。去掉属性C2，使相容部分的划分块x5和不相容

15、部分的划分块x1,x2合并成了一个划分块x1,x2,x5，导致正域POSC(D)发生变化，根据相容核的定义，C2属于相容核。去掉属性C3，对相容部分的划分没有影响，对不相容部分的划分也没有影响，因此C3不属于任何核。由以上分析可得，决策表1的核属性集为C1, C2，其中，相容核为C2，不相容核为C1。代数方法求得的核为相容核C2；改进的差别矩阵（如文3、4）中求得的也是相容核C2；信息熵的方法求得的核也是相容核C2；HU矩阵的方法求得的核是C1, C2，是所有的核。 表2 决策表2U C1 C2 C3 D x1 1 0 1 0 x2 0 0 1 1 x3 0 0 1 0 x4 1 1 1 1

16、决策表2的划分如下：U/IND(C1,C2,C3)=x1,x2,x3,x4,U/IND(D)=x1,x3,x2,x4,正域POSC(D)= x1,x4。去掉属性C1,有U/IND(C2,C3)=x1,x2,x3,x4；去掉属性C2,有U/IND(C1,C3)=x1,x4,x2,x3；去掉属性C3有U/IND(C1,C2)=x1,x2,x3,x4；从上面的计算可知：决策表2中相容部分为x1,x4，相容部分的划分为x1,x4，存在不相容信息的部分为x2,x3，不相容部分的划分为x2,x3；去掉属性C1，使相容部分的划分块x1和不相容部分的划分块x2,x3合并成了一个划分块x1,x2,x3，导致正域

17、POSC(D)发生变化，根据相容核的定义，C1属于相容核。去掉属性C2，使相容部分的划分块x1和x4合并成了一个划分块x1,x4，导致正域POSC(D)发生变化，根据相容核的定义，C2属于相容核。去掉属性C3，相容部分的划分和不相容部分的划分都没有发生变化，因此C3不属于任何核。由以上分析可得，决策表2的核属性集为C1, C2，其中，相容核为C1, C2，不相容核为空。代数方法、改进的差别矩阵方法、信息熵的方法和HU矩阵的方法求得的核都是C1, C2。 表3 决策表3U C1 C2 C3 D x1 1 0 1 1 x2 1 0 1 0 x3 1 0 1 2x4 0 0 1 1 x5 0 0 1

18、 0 x6 1 1 1 1 决策表3的划分如下：U/IND(C1,C2,C3)=x1,x2,x3,x4,x5,x6,U/IND(D)=x1,x4,x6,x2,x5,x3,正域POSC(D)= x6。去掉属性C1,有U/IND(C2,C3)=x1,x2,x3,x4,x5,x6；去掉属性C2,有U/IND(C1,C3)=x1,x2,x3,x6,x4,x5；去掉属性C3有U/IND(C1,C2)=x1,x2,x3,x4,x5,x6；从上面的计算可知：决策表3中相容部分为x6，相容部分的划分为x6，存在不相容信息的部分为x1,x2,x3,x4,x5，不相容部分的划分为x1,x2,x3,x4,x5；去掉

19、属性C1，使不相容部分的划分块x1,x2,x3和x4,x5合并成了一个划分块x1,x2,x3,x4,x5，根据不相容核的定义，C1属于不相容核。去掉属性C2，使相容部分的划分块x6和不相容部分的划分块x1,x2,x3合并成了一个划分块x1,x2,x3,x6，导致正域POSC(D)发生变化，根据相容核的定义，C2属于相容核。去掉属性C3，相容部分的划分和不相容部分的划分都没有发生变化，因此C3不属于任何核。由以上分析可得，决策表3的核属性集为C1, C2，其中，相容核为C2，不相容核为C1。代数方法和改进的差别矩阵的方法求得的核是相容核C2，信息熵的方法和HU矩阵的方法求得的核是所有核C1, C

20、2。对于上面的表1、表2和表3，代数方法和改进的差别矩阵方法完全等价，它们只能求得不相容决策表的相容核；信息熵方法有时得到的是相容核，有时得到的是全部核属性；HU矩阵方法能计算出不相容决策表的全部核属性。HU矩阵方法虽然得到了全部的和属性集合，但是该矩阵把这两种核属性混合在一起，使人很难分辨出哪个是相容核，哪个是不相容核，这种现象使得许多学者一致认为HU矩阵不适用于不相容决策表。下面通过对HU差别矩阵进行修改，使HU矩阵中的相容核与不相容核分开，从而得到不相容决策表的所有的核属性集合。4 改进的差别矩阵HU差别矩阵定义如下：定义6 对于信息系统S=(U,A,V,f)，A=CD，CD= ，C和D

21、分别是条件属性和决策属性。S的可辨识矩阵M是一个n*n对称矩阵，a(x)是记录x在属性a上的值，表示可辨识矩阵中第i行，第j列的元素，因此可辨识矩阵的定义为：= 文献中给出如下结论：当且仅当某个mij为单个属性时,该属性属于核CORE(C)。根据前面给出的相容核与不相容核的计算过程及方法，修改HU矩阵为下面两个新的矩阵分别计算不相容决策表的相容核与不相容核。定义7 对于信息系统S=(U,A,V,f)，A=CD，CD=，C和D分别是条件属性和决策属性。S的可辨识矩阵为CD(i,j)和CD(i,j)分别定义如下：， 其他情况CD(i,j)= 其中U1=POSC(D)，当CD(i,j)为单个属性时，

22、该属性是相容部分的核属性，与代数观的核属性定义方法计算的核属性等价。， 其他情况CD(i,j)= 其中U2=U-POSC(D)，当CD(i,j)为单个属性时，该属性是不相容部分的核属性，删除该属性将导致不相容部分发生变化，即某些不相容块发生合并。它的存在保证了不相容部分的分类与原始决策表的不相容部分分类一致。下面使用改进的差别矩阵，计算以上三个不相容决策表的相容核与不相容核，由于矩阵的对称性，只计算这些矩阵的下三角矩阵。对决策表1使用新的差别矩阵分别计算相容核与不相容核。 由矩阵CD(i,j)的定义计算得到如下矩阵。 表4 决策表1的差别矩阵CD(i,j) x1 x2 x3 x4 x5 x1

23、x2 x3 x4 x5 C2 C1,C2 由于C2是矩阵CD(i,j)中的单个属性，因此，C2是相容核。由矩阵CD(i,j)的定义计算得到如下矩阵。 表5 决策表1的差别矩阵CD(i,j) x1 x2 x3 x4 x5 x1 x2 x3 C1 x4 C1 x5 由于C1是矩阵CD(i,j)中的单个属性，因此，C1是不相容核。对决策表2使用新的差别矩阵分别计算相容核与不相容核。 由矩阵CD(i,j)的定义计算得到如下矩阵。 表6 决策表2的差别矩阵CD(i,j) x1 x2 x3 x4 x1 x2 C1 x3 x4 C1 C1,C2 由于C1，C2都是矩阵CD(i,j)中的单个属性，因此，C1，

24、C2都是相容核。由矩阵CD(i,j)的定义计算得到如下矩阵。 表7 决策表2的差别矩阵CD(i,j) x1 x2 x3 x4 x1 x2 x3 x4 由于矩阵CD(i,j)中的没有单个属性，因此，该决策表的不相容核为。对决策表3使用新的差别矩阵分别计算相容核与不相容核。由矩阵CD(i,j)的定义计算得到如下矩阵。 表8 决策表3的差别矩阵CD(i,j) x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 x5 x6 C2 C2 C1,C2 由于C2是矩阵CD(i,j)中的单个属性，因此，C2是相容核。由矩阵CD(i,j)的定义计算得到如下矩阵。 表9 决策表3的差别矩阵CD(i,j) x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 C1 C1 x5 C1 C1 x6 由于C1是矩阵CD(i,j)中的单个属性，因此，C1是不