第三章 差别矩阵

1、-作者xxxx-日期xxxx第三章 差别矩阵【精品文档】第三章 差别矩阵粗集中的不确定性，是在论域上引入了某种限制性知识，这种限制性知识是取离散值的可称作等价关系的属性构成的属性集。由于对形成一种客观性的划分等价集，当用知识对中非空子集中的元素进行分类时才产生了不确定性。虽然，Pawlak在上引入限制性知识，但属性集并非是新的空间，中对象可以获得种属性的值，因而成为维特征空间中的点。这一点不论是在Cantor集中、模糊集中还是在经典模式识别中，都被认为是已知事实。只是在粗集中限定的值域是有限离散集（连续值必须离散化），规定属性值不完全相同的个体，分属不同类，或说同一类中所有个体，对于每一种属性

2、的取值都是一样的。因为作了与的假定，才将论域客观地划分成若干等价类族。正因为对形成确定性分类才称为知识，才导至中非空子集中元素用分类时产生不确定性。从这个角度讲，粗集与Cantor集、模糊集一样都是在一个空间上研究分类问题。粗集的特殊性在于：是在知识下考虑中元素是否属于的非空子集（中属于的元素才认为确定属于，即可按知识准确分类）。§1 差别矩阵(The discernibility matrices)引例1 序 我们先考虑一个具体例子。例 1. 设信息系统=(,)由表1表示 1021000121202100022211210, , , , 是条件属性集。表中不出现相同行，说明每个个体

3、都不同。考虑下面表2：区分元素 个体个体注意到： 把与区分开的元素为, , ，, 并且每个元素都能区分开，故有一个就行，称为析取关系，记作： 能把与区分开的只有。那么，能同时把，与区分开的元素是与()同时满足，这种逻辑关系称为合取关系，记作：()。由此把与，同时区分开的属性应满足()() 第一列差别元素合取。把所有个体两两区分开的属性应满足：所有列的差别元素的“合取式” 。当表1（即信息系统）给定，则表2确定（称为差别矩阵）,全部的差别元素的合取式也确定: 称作差别函数。问题是：如何简化差别函数。要进行关于析取，合取关系的逻辑变换需保证变换是等价的。考虑上面例子：=()()()()()()()

4、()方法:从最简差别元素入手：在此为，含义是：要把,与同时区分开，要求。这样，包含与的差别元素将失去意义而被吸收掉。因为存在且必须被保留，使得()失去存在价值。因为选其中或或不能把与区分开，还必须加上。而的加入，使, , 成为冗余。于是经一次吸收得=()= ()()化为最简析取范式后，每个析取子式对应一个约简。2 差别函数简化的一般步骤对例1给出的差别函数，经一次吸收律便得到欲求的约简。但是，当属性个数、个体数很大时，对于包含个差别元素（且每个差别元素最多是个属性的析取式）的合取式的化简仍存在一个计算方法问题。下面给出一种简化差别函数的速算法。步骤1：不用按表格形式构造差别矩阵，而是直接从信息

5、表按下列规则提取保留差别元素；步骤2：从差别矩阵的第一列至第列对差别元素排序，序号为从至；步骤3：按顺序从节拍开始，保留第 个差别元素，当提取的第个差别元素和前面保留的差别元素之间存在包含关系时，则吸收所有包含集；否则，连同前面的保留差别元素均保留，且保留的差别元素之间为合取关系。步骤4：当节拍=时，算法停止。 此时，所有保留差别元素的合取范式构成差别函数。每个合取子式或是若干单一属性的析取式或是单一属性；并且这些合取子式作为属性子集不存在包含关系。即如果有一个合取子式为单个属性，则在其他所有合取子式中属性不出现；若有一个合取子式为()，那么，在所有其它合取子式中最多只能包含或而不会同时包含与

6、。经上述步骤，差别函数化为 =。其中为单个属性；是包含至少有两种属性的析取式，并且中的属性个数是的不减函数。 通常情况下，(+)<<。中属性个数远小于(为属性数)。步骤5：从开始施行合取关于析取关系的分配律。比如，若=.则化为=()() 分别对上述两个析取子式应用吸收律，在第一个子句中吸收掉包含的，在第二个析取子句中吸收掉包含的,得：=()()其中，, 步骤6：重复步骤5，直到将化为最简析取范式，则每个析取子式对应一个约简。§2 差别矩阵差别矩阵也称作可辨识矩阵或分明矩阵，是由斯科龙（Skowron）教授于1991年提出来的一种表示知识的方法，其优点是可以解释并便于计算数

7、据核和约简。斯科龙最初提出差别矩阵的概念，也是为了计算约简。1 信息系统的差别矩阵设是一个信息系统，其中，。称阶矩阵为信息系统的差别矩阵，其中 ， （1）称为差别元素，它是使第个个体与第个个体属性值不相等的那些属性构成的集合，或说是所有能区分开个体和的属性构成的集合。当时，显然，因为不存在把样本与自身区分开的属性。且是对称的，可只用其下三角部分表示，即 和。设，能把个体和区分开的差别元素是这个属性中的若干个。这若干个属性间的关系是“或”，用“”表示。中的每一个属性都能把与区分开。若能把与区分开的属性是，则称为析取范式，即每个差别元素都是由析取范试表达的属性集。显然，把与,都区分开的属性应是,

8、这些差别元素的“与”（同时成立），用“”表示，即这些差别元素的合取式：把所有个体都两两区分开就应该是所有差别元素的合取式。通过逻辑运算将所有差别元素的合取式化为析取试后，记作，称为信息系统的分明函数（差别函数），任意的差别矩阵都唯一地确定了一个差别函数。定理：设是一信息系统，是的差别矩阵，是信息系统的一个差别函数，则该函数的最小简化的析取范式对应信息系统的全体约简。该命题给出了计算信息系统全体约简的重要方法：只要将合取范式的差别函数展开成析取范式，便得到的全体约简。例1 设信息系统由表1表示表11021000121202100022211210其中，由于容易推出：，。因为且使划分等价类中只含一

9、个个体，并且从中任意去掉一种属性将导致划分能力改变在此不能将5个体都区分开，所以，是的一个约简。同理也是信息表的一个约简。现在我们换一个角度，用差别矩阵和差别函数来计算约简。步骤1 计算信息系统的差别矩阵；步骤2 计算与差别矩阵相关的差别函数；步骤3 计算差别函数的最小析取范式，它将给出的所有约简。解：步骤1 写出的差别矩阵：步骤2 的差别函数为差别矩阵中下三角表示的个列构成的合取范式。（把所有对象都区分开的属性集）= 第一列 第二列 第三列最后一列将简化利用逻辑运算中的吸收律= 步骤3 合取范式有结合律、交换律、合取对析取的分配律，但是，要求对每一列构成的合取范式先化简。即个大圆括号中的合取

10、式化简。= =上述是不能再化简的最小析取范式，每个合取式对应的一个约简：，上述算法，通常具有理论上的价值。表1101111211002310103410014511105611016表1是一张普通信息表，表1中每一行表示不同状态的决策即每个个体看作是行为的不同状态。有关属性是否都必要呢？现在考虑属性约简。一、解法1数据分析法移去属性，不出现相同的行，所以可约去；移去，则3与5不一致（即条件属性值一样，决策结果不同），所以是核属性；移去，则2与5不一致，所以是核属性；移去，则2与6不一致，所以是核属性。故、中只有是可移去的，知是核，且核集自身是约简，所以是唯一的最小约简。二、解法2划分等价类法属

11、性、对划分生成的等价类族为至： 由此得： 式表明属性集能够把个体一个一个区分开，故知识是充分的。考虑对的划分等价类，由得所以，与具有相同的分类能力。从中移去，由知不是约简；移去，由知不是约简；移去，不是约简。故有唯一约简。三、解法3差别矩阵法为清楚起见将从表1中提取的差别矩阵由表2表出。表2差别矩阵给定的差别矩阵为6阶，其下三角由5列构成，第（1）列中个差别元素的合取范式表示把个体分别与个体,（）区分开的属性满足的逻辑关系式。具体作法是按顺序提取第1列，第2列，第列中的判别元素并构成合取范式，对每列构成的合取式用吸收律进行等价变换；将简化后的个范式合取，进行第二轮化简。例如，从差别矩阵中提取第

12、一列的差别元素构成合取式为： 我们用逻辑运算中的吸收律对式进行等价变换。应特别强调的一点是：变换必须是等价的。通俗点讲就是：对第（在此）列差别元素构成的合取式应用吸收律时，对于能把个体与,区分开的不重复的所有属性集一个不少的都求出来，而不仅仅是最小（数目最少）属性集；否则，不能保证最终求出的是约简。例如，应用吸收律简化式时，显然属性能够把个体与，都区分开，是最小属性集；假若式简化后为；显然有：第2列差别元素合取范式可简化为： 第3列差别元素的合取范式可简化为： 第4列差别元素的合取范式可简化为： 第5列差别元素的合取范式可简化为： 将与、合取得 = 最终差别函数的化简结果为，即得到一个约简集。

13、由前面用数据分析计算结果知，本例有唯一约简；显然用差别矩阵求出的不是约简。问题就出在：对第一列差别元素构成的合取范式在应用吸收律时，变换不是等价的。正确的作法如下： 由于的存在使得和可以被吸收；由于的存在可使与被吸收，所以，= 将式与、合取得= 则差别函数的最小简化式为： = 即是唯一最小约简，结论与前同。最初的错误结论源于在第一列差别元素合取范式用吸收律简化时，漏了子句，使得变换不等价导致错误。所以，在对差别函数进行逻辑变换过程中，必须把个差别元素的合取式作为整体进行变换。这样因为实行吸收率的范围大而使简化运算来得容易，在实施分配律时，应选择实行顺序，方可使逻辑变换过程简洁。结论用差别矩阵计

14、算约简时，为了节省时空，可以省去写出差别矩阵的中间环节，直接从信息表中依次提取第一至第列中差别元素并分别构成合取式。并行地用吸收律简化这个合取式；在保证变换等价前提下将并行计算得到的个简化结果再合取。经二次吸收（辅之合取的交换律、结合律，合取对析取分配律）将差别函数化为最简析取范式，则析取范式的每个子句给出信息表的所有约简，并且是约简。但是，从第一列起：提取组由差别元素构成的析取式作合取式，单独对其用吸收律、分配律、结合律、交换律简化时，未必“简单”，比如，对式的简化，就比较困难，稍有不慎将导致错误。而将个由差别元素（析取式）一并提出，以它们为子句构成合取式，把该合取式作为整体进行化简，步骤为

15、：（1）观察合取子句中是否有单个差别元素，若有则相同的保留一个，保留的单个差别元素作合取。同时去掉包含该单个差别元素的所有析取子句；若无则进行第二步。（2）观察由两个差别元素的析取式构成的子句，相同的只保留一个，同时删除包含着由两个差别元素的析取式构成的保留子句的所有析取式。（3）观察由3个差别元素的析取式构成的子句，当所有个由析取式构成的合取式中的所有析取式都被观察过后第一轮简化完毕。这时的合取式中，每个合取式或是单个差别元素或是两个（不包含已有单个差别元素）差别元素的析取式或是由3个差别元素的析取式。第二轮化简是应用分配律将合取式化为析取式，每个析取式对应一个约简。§3 决策表属

16、性约简1 决策表设信息系统=中，属性集，其中为条件属性集，中含若干个条件属性；为决策属性集，其中含若干个决策属性，最常见的是中只含一种决策属性，这时。这时，信息系统称作决策系统，简称决策表，记成。应用中出现最多的是用决策表给出的信息系统。如表1，就是由决策表表达的一个知识表达系统。表1 决策表表达的知识表达系统110211212211321010421202512002表1中，论域，为条件属性集，为决策属性集，每个个体关于各属性的属性值在表中标出。表中每一行表示一条决策规则，比如第一条决策规则（即第一个个体关于各条件属性与决策属性取值的对应关系）：含意是：当个体关于,的取值分别为时，那么该个体

17、的决策属性值为这作为一条决策规则。称为决策规则的前件（条件部分）；称为决策规则的后件（结论部分）。定义：如果和某条决策规则前件相同的所有其它决策规则，其后件也都与该条决策规则的后件相同，则称该条决策规则是一致性规则，或协调规则；如果决策表中所有决策规则都是一致性决策规则，则称决策表为一致性决策表，否则称为不一致性决策表。决策表是一致的表明：条件等价类都包含于决策等价类中或说条件属性完全决定了个体分类，记作；若决策表不一致，则说明存在这样的条件等价类，其中的个体被划分到不同的决策等价类中，这是条件属性集不能完全决定个体的决策分类或说决策属性集只是对条件属性集部分依赖。2 决策表约简中的基本概念设

18、为决策表，其中为论域，为条件属性集，为决策属性集。条件属性集中所有等价关系的交记为，它把论域划分成的等价类族记为：决策属性集中所有等价关系的交记成，它把论域划分成的等价类族为：等价类是的子集，的正域为=即是由对划分等价类中完全包含在中的那些等价类的并集，所以，的正域中样本可以按条件属性精确分类。定义1 称为的正域。描述的是条件属性集对论域的划分生成的等价类中完全包含于决策属性集对论域划分生成的等价类中的那些等价类（中包含的元素）的并集。中的元素由于都包含于的等价类中，所以都能被准确分类，即都能通过条件属性集划入分类。定义2 在知识下，能确切地划入类的对象在论域中所占的百分比称为根据，的近似分类

19、质量，用表示。则定义3 称 为根据，的近似分类精度。分类精度描述的是使用知识对对象分类时，可能的决策中正确决策的百分比。定义4 设为决策表，为条件属性集，为决策属性集。，若，则称是上的可约去的；否则，是上不可约去的。定义5 若，如果上的每个等价关系都是上不可约去的，则称关于是独立的。定义6 等价关系是的约简，当且仅当是的独立子族并且 定义7 所有中不可约去的等价关系的集合，被称为的核，记成命题1 为决策表，是条件属性集中所有的约简构成的约简族，是的核，则=注意几个符号：的正域：的等价类，含于的等价类，由导入的约简：在条件下，对约简的核：在下的核例1 设为决策表，为条件属性集且，为决策属性集，已

20、知：，求的约简。解 第一步：求的划分等价类：第二步：求的正域，=第三步：为了计算的约简，先确定中的核属性，即从中哪个属性是不可约去的。 因为=，所以，是中不可约去的。 因为=，所以，是中可约去的。最后去掉，得，所以，是中不可约去的。于是，的核为，它是唯一的的约简。上述求的约简过程中，先求的核，具体作法是：从中删去一属性后观察是否改变的正域。知识的约简是知识的最小子集，它提供的个体到知识的基本类与整体知识提供的个体到知识的基本类相同；本例中的约简只有一个，这时，当分类个体为知识的基本类时，利用知识来描述有唯一一种方法；如果知识有多个约简，则利用知识分类个体为的基本类存在多种方法。关键语：按决策属

21、性分类是已知的，那么，这些分类有哪些能用条件属性去描述呢？而且是最少的条件属性。这就要求的约简。上面给出了求的约简的具体算法，但比较烦索。下面利用决策表表达知识的特殊形式，简化求核属性的作法，在表中去掉一种条件属性，看决策规则是否产生新的不一致。给定一个决策表，如，T如表1所示：表1 决策表AUabcde123451221101122202201101010212决策表1显然是一致性决策表，因为表中每一条决策规则都是一致的。我们主要讨论一致性决策表，但不一致的决策规则也是有用的。在后面的应用中会看到这一点。对于一个一致性决策表，我们的问题是：决策规则中的条件属性是否都是必要的，不必要的应消去。

22、再者，每一条决策规则中的条件属性值是否都是必要的，无关的应消去。前者称为属性约简，后者称为属性值约简。因此，对一致性决策表的简化分两步：1. 属性约简：它等价于从决策表中消去一些不必要的列；2. 属性值约简：对于表中的每一条决策规则，消去一些无关紧要的属性值。对决策表的属性约简，有下述定理:定理1 从决策表中，将条件属性C中属性逐个移去，每移去一个属性即刻检查其决策表，如果不出现新的不一致则该属性是可以被约去的；否则，该属性不能被约去，即该属性必是C的D核属性。称这种方法为属性约简的数据分析法。在决策表约简的基本概念中定义了D的C正域，C的D核，其中是C中的所有D约简族。下面来证明，如果从C中

23、移去一属性比如a，其决策表将出现新的不一致，则该属性必是C的D核属性，是不能被约简的。证明：不妨讨论一致性决策表。假如移去a属性决策表将出现新的不一致，这种新的不一致是因属性值引起的，即至少有两个个体（不妨设为）的a属性值不同其余的条件属性值均相同，但与的决策属性值不同。这样与因a属性被删除将被划分到的同一个等价类中。即原来不在一个等价类中的个体，因a属性删除被划分到同一个等价类中。另一方面，因为与的属性值不同，所以，将被划分到C的不同等价类中，如果与个体（或）的各条件属性值相同的仅有（和）（即一致性决策表T中相同的行只有一行，否则可以去掉其它相同行只保留（或）所在行，那么，C的包含（或）的等

24、价类中只有（或）一个元素。显然，只包含（或）的等价类被包含在中，可见。故属性是不能被约去的，即必是C关于D的核属性，证毕。这样，在决策表T中，当移去属性后，决策表出现新的不一致性，就可确定是C关于D的核属性。由此，可求出C的D核。可见，定理1给出了求相对核的方法，而不用先求C的D约简族，再通过求C的D核。现在按此算法求决策表中C的D核及C关于D的全部约简。对决策表1，表1 一致性决策表AUabcde123451221101122202201101010212解法一：由于表1中不存在条件属性值相同的行，显然，表1是一致性决策表。从表中移去条件属性a，则决策表不出现新的不一致，即两个个体的条件属性

25、值相同而决策属性值不同，故条件属性a是可以被约去的；从表中移去b，也不出现新的不一致性，所以b也是可以被约去的；从表中移去c，所得决策表是不一致的，因为第二、三条决策规则出现不一致，所以，条件属性是a,b,c关于D=d,e的核，而a,b都是可以约去的非核属性。但是，核属性自身不构成约简。因为：去掉后的规则1，3不协调；2，5不协调。而、均是约简。由此得两个约简： ， 解法二：下面通过的正域求相对核、相对约简。决策属性D、各条件属性对论域U的划分分别为：U/D=1,4,2,3,5U/a=1,4,5,2,3，U/b=1,2,3,4,5，U/c=1,3,4,2,5所以U/C=1,4,5,2,3，由此

26、得=1,3,2,4,5，所以a是可约去的，即a不是核属性。=1,4,5,2,3，所以b是可约去的，即b不是核属性。=1,4,5,2,3，所以，从C中去掉后改变了D的C正域，所以属性c不能约去，c是核属性。那么a,c与b,c能否构成D的约简呢？这是显然的。因为a,c是独立的，b,c也是独立的，即从中去掉任何一属性将改变D的C正域；a,c，b,c与C具有同样的对D的划分能力。这样，从两个角度计算了相对核与相对约简，故在求决策表的相对核与相对约简时，有两个途境：从D的C正域考虑；用移去某一属性列的数据分析方法考虑。比较相对约简的两条途境，易见，数据分析法（即解法一）相对来说操作简单，所以，对决策表T

27、的简化通常采用数据分析法。§4 决策表属性约简的差别矩阵方法前面针对信息表定义了其差别矩阵及与对应的差别函数。通过吸收律，合取范式的结合律、交换律，合取关于析取式的分配律将由差别元素的析取式表示的所有子句组成的合取式化成最简析取范式，则每个最简析取范式对应的一个约简。由此给出针对信息表的计算约简的一种算法。现在给出针对决策表的差别矩阵概念。设为决策系统，其中为论域，为条件属性集，为决策属性集，对于，任意，为个体在属性上的值，为的值域。决策表的差别矩阵定义为：其中是中第行第列上的元素，称做差别元素，其表达式为：=其中。上述定义表明：的第行第列上的差别元素是条件属性构成的集合或数值0。（1）当与的决策属性值不同时，那么使与有不同值的所有条件属性构成差别元素，