区间值序信息系统中差别信息树的属性约简*

杨 蕾，张晓燕，徐伟华

1.重庆理工大学 理学院，重庆 400054

2.西南大学 数学与统计学院，重庆 400715

1 引言

波兰数学家Pawlak[1]在1982年提出了粗糙集理论用以解决不精确、不完备数据问题，它的一个主要课题是属性约简[2-8]。属性约简即去掉知识库中冗余的属性之后其数据的分类能力保持不变，从而达到数据表降维的目的，减少了冗余数据，简化了规则。不少学者已经在不同的粗糙集背景下根据不同的属性约简思想提出了不同的属性约简方法[9]。自从Skowron等人[10]提出通过差别矩阵来求取属性约简的思想之后，差别矩阵因为其自身的直观简明性被广大学者关注和研究。蒋瑜、王燮等人[11]提出了基于差别矩阵的Rough集属性约简算法，他们主要分析了不同的差别矩阵对求取属性约简效率的影响，然后定义一种新的差别矩阵来减少矩阵中非空差别信息的个数从而达到提高效率的目的。蒋瑜、王鹏等人[12]提出了基于差别矩阵的属性约简的完备算法，它们结合的属性重要度以及迭代的思想来求取决策表的最小约简；王兵和陈善本[13]也给出了一种基于差别矩阵的属性约简完备算法，该算法的特别之处在于迭代过程中对各类属性的处理。但是在通过差别矩阵来求取属性约简的这些算法当中，要想获得约简就必须使用差别矩阵中所有的非空元素。Skowron等[10]提出在求决策表的属性约简时将决策表所对照的差别矩阵中的所有非空元素进行合取即可，但在使用合取运算的时候相同（重复）元素和父集元素对属性约简时没有任何作用，但这些重复元素和父集元素却占用了大量的存储空间，同时也增加了求取约简的时间。为了消除差别矩阵中重复元素的出现，文献[14]提出了一种新的差别矩阵存储方法（C-Tree）实现了差别矩阵的压缩储存，但是该方法还存在一定的弊端，当父集元素和子集元素同时出现的时候它保留了父集元素，从而使该树中还存在一定数量的冗余元素；为了消除差别矩阵中冗余的父集元素，蒋瑜[15]给出了一种基于差别信息树的属性约简算法,该算法不仅能消除差别矩阵中的重复元素，在大多数情况下亦能消除父集元素的影响，实现对差别矩阵的压缩储存。但是蒋瑜所提出的差别信息树是通过等价关系下的差别矩阵获得的，而基于等价关系的差别矩阵是对称的，因此在求约简时只用差别矩阵中的上三角元素或者下三角元素即可。现在在区间值序信息系统的背景下考虑属性约简，其差别矩阵便失去了对称性，因此基于差别信息树的属性约简并不一定适用于区间值序信息系统下的属性约简。

本文在区间值序信息系统的背景下，结合了蒋瑜提出的差别信息树的优点，提出了基于可分辨矩阵的差别信息树，并在此基础上给出区间值序信息系统的基于差别信息树的完备的属性约简方法。最后在第4章给出了实证分析，验证了该方法的可行性以及有效性。

2 预备知识

本章主要讲述了有关区间值序信息系统下求取属性约简的理论基础以及差别信息树等相关知识。

定义1[16]称三元组I=(U,A,F)为信息系统，其中：U是有限的对象集；A是有限的条件属性集；F是U与A的关系集；Va为a的有限值域。若∀f∈F,a∈A和xi∈U都有f(xi,a)=[aL(xi),aU(xi)]。

那么称I=(U,A,F)为区间值信息系统，其中aL(xi)和aU(xi)都是实数且满足aL(xi)≤aU(xi)；f(xi,a)为对象xi在属性a下的属性值且f(xi,a)是一个区间数。当aL(xi)=aU(xi)时，属性值f(xi,a)为一个实数，因此区间值信息系统是单值信息系统的推广。

定义2[16]设I=(U,A,F)是一个区间值信息系统，对∀a∈A，可以对区间值信息系统中的属性值进行比较，定义：

定义4[16]设I≥=(U,A,F)为区间值序信息系统，辨矩阵。特别地，对 ∀xi,xj∈U，有Dis≥A(xi,xi)=∅ 并且得到：

定义6[16]设I≥=(U,A,F)为区间值序信息系统，M≥A=∧{∨{a|a∈Dis≥A(xi,xj)}}所对应的极小析取范式为：记Bk={as|s=1,2,…,qk}，则 {Bk|k=1,2,…,p}是区间值信息系统I≥的所有约简的集合。

定义7[15]差别信息树是一棵有序树，其中序体现在：它的条件属性的排列顺序是按照原信息系统中条件属性的顺序从左到右进行排列，顺序不能颠倒或者改变。差别信息树有如下几个特征：

（1）差别信息树中的每个节点最多存在|A|个子节点，其中|A|代表信息表中条件属性的个数。

（2）差别信息树中的每一个节点涵盖了4个方面的信息，分别为：前缀指针、后继指针、节点名、同名指针。其中：前缀指针指向该节点的父亲节点，后继指针指向该节点的孩子节点，节点名记录了该节点所对应的条件属性名称，同名指针则指向差别信息树中与该节点具有相同条件属性名的其他路径当中的节点。

（3）差别信息树的子树也是一棵有序树，其中条件属性的排列顺序同样不能颠倒或者改变。

3 区间值序信息系统中基于差别信息树的属性约简方法

本章将通过差别信息树的概念，给出区间值序信息系统中基于可分辨矩阵的差别信息树的算法，并通过相关定理来证明由该差别信息树得到区间值序信息系统属性约简的合理性。

首先，根据差别信息树的定义和蒋瑜提出的差别信息树的设计与实现过程给出区间值序信息系统中基于可分辨矩阵的差别信息树的构建过程：

算法1区间值序信息系统中基于可分辨矩阵的差别信息树的构建方法

输入：区间值序信息系统I≥=(U,A,F)。

输出：区间值序信息系统中基于可分辨矩阵的差别信息树。

1.创建区间值序信息系统中基于可分辨矩阵的差别信息树的根节点TN，并令TN为null；

2.根据Dis≥A(xi,xj)={a∈A|(xi,xj)∉R≥a}求出任意(xi,xj)所对应的可分辨属性集Dis≥A(xi,xj)，从而得到可分辨矩阵Dis≥A=(Dis≥A(xi,xj))|U|×|U|。设B⊂A满足B=Dis≥A(xi,xj)(∀xi,xj)且B中元素的顺序按区间值信息系统中条件属性的顺序进行排列。

创建一新的节点N′使其成为TN的子节点，将N′的属性名初始化为a，并通过该节点的同名指针连接到具有与该节点有相同属性名的节点上，从而构成了一个同名属性节点链；

从算法1可以看出：在区间值序信息系统下构建基于可分辨矩阵的差别信息树时运用了不扩展路径策略以及删除子树策略，即所构建的差别信息树具有如下几个特征：

（1）将相同的分配可辨识属性集映射到同一条路径当中；

（2）将具有相同前缀的可分辨属性集映射到最小的可分辨属性集所对应的路径当中；

（3）可分辨矩阵中的属性集存在共享前缀。

因此，在区间值序信息系统下构建的基于可分辨矩阵的差别信息树实现了对分配可辨识矩阵的压缩储存，从而减少了构建基于可分辨矩阵的差别信息树的时空复杂度。

区间值序信息系统下基于可分辨矩阵的差别信息树的相关定理如下：

定理1区间值序信息系统中基于可分辨矩阵的差别信息树中包含了获得区间值序信息系统的属性约简所需要的所有属性。

证明设区间值序信息系统中基于可分辨矩阵的差别信息树中所有路径的可分辨属性集存放在集合DS中，可分辨矩阵中所有元素存放在集合Dis≥A中。由算法1所对应的基于可分辨矩阵的差别信息树的构建过程有：DS⊆Dis≥A，对于∀(xi,xj)有Dis≥A(xi,xj)∈Dis≥A,∃Dis≥AT(xi′,xj′)∈DS,s.t.Dis≥AT(xi′,xj′)⊆Dis≥AT(xi,xj),由运算公理可知：Dis≥AT(xi,xj)与Dis≥AT(xi′,xj′)作合取运算得到的结果还是Dis≥AT(xi′,xj′)。从而，区间值序信息系统中基于可分辨矩阵的差别信息树中包含了获得区间值序信息系统的属性约简所需要的所有属性。

定理2区间值序信息系统中基于可分辨矩阵的差别信息树中所有仅含一个节点的路径所对应的单元素可分辨属性集的并组成了该区间值序信息系统中条件属性集的核core(A)。

证明通过在区间值序信息系统下构建基于可分辨矩阵的差别信息树的过程可知：假设该差别信息树中存在一个节点名为a的节点，而且该树中存在仅包含节点名为a的节点的路径，则存在可分辨属性集{a}与该路径对应。在可分辨矩阵中，若a∈A并且{a}为可分辨矩阵中的单元素集，则称a为A中的必要属性。A中所有必要属性的集合构成了A的核，即core(A)。

接下来，将分析算法1的时空复杂度。

对一个区间值序信息系统I≥=(U,A,F)来说，若存在|U|个对象、|A|个条件属性，则在可分辨矩阵中最多可以得到|U|2个非空的条件属性的子集（即差别信息），假设可分辨矩阵中实际的非空条件属性的子集数为M（一般情况下，M＜＜|U|2）。由基于可分辨矩阵的差别信息树的构建过程可以看出，一棵差别信息树最多可以有M条不同的路径并且每一条路径中最多可以有|A|个节点，因此，一棵差别信息树中最多可以有M×|A|个节点，又由于在基于可分辨矩阵的差别信息树中存在许多的路径都存在共享前缀导致差别信息树中的实际节点数远小于M×|A|。因此在最坏的情况下基于分配可辨识矩阵的差别信息树的空间复杂度为O(|A|×|U|2)。

和文献[11]提出的差别矩阵存储方法（C-Tree）相比，在基于可分辨矩阵的差别信息树的构建中，当父集元素和子集元素同时出现的时候，它保留了子集元素，消除差别矩阵中冗余的父集元素，更进一步对差别矩阵进行了存储压缩。在空间复杂度的比较上，基于可分辨矩阵的差别信息树的空间复杂度小于C-Tree的空间复杂度。

为了验证算法1所提出的区间值序信息系统中基于可分辨矩阵的差别信息树的合理性以及有效性，给出了区间值序信息系统中基于该差别信息树的属性约简方法。

算法2区间值序信息系统中基于可分辨矩阵差别信息树的属性约简方法

输入：区间值序信息系统中基于可分辨矩阵的差别信息树。

输出：由差别信息树得到的属性约简。

1.创建空集R；

2.将基于可分辨矩阵差别信息树中只含单个节点的路径，将这些节点对应属性名放在一个集合R′中；

3.若R′≠∅，对所有a∈R′，在基于可分辨矩阵差别信息树中删掉所有含节点{a}的路径；

4.令R←R′；

5.从基于可分辨矩阵差别信息树中选择其根节点的最右孩子节点并假设该子节点所对应的属性名为b，此时令R←R⋃{b}，然后在得到的差别信息树中去掉所有含节点b的路径；

6.若基于可分辨矩阵的差别信息树中仅含有根节点，输出R，算法结束。

下面给出算法2的完备性证明：

对区间值序信息系统的可分辨矩阵来说，若R⊆A是一个完备约简，同样的R需要满足两个条件：（1）∀Dis≥A(xi,xj)≠∅，有Dis≥A(xi,xj)⋂R≠∅；（2）∀r∈R,∃Dis≥A(xi,xj)，满足Dis≥A(xi,xj)⋂(R-{r})=∅。

由定理1知道：区间值序信息系统中基于可分辨矩阵的差别信息树中包含了获得区间值序信息系统的属性约简所需要的所有属性。因此对基于可分辨矩阵的差别信息树来说，若R⊆A是一个完备约简，R需要满足两个条件如下：

（1）∀B∈DS，B⋂R≠∅（其中DS为包含了基于可分辨矩阵差别信息树的所有路径所代表的可分辨属性集的集合）；

（2）∀r∈R，∃B∈DS，满足B⋂(R-{r})=∅。

若算法2完备只需证明算法2输出的R满足条件（1）、（2）均可。

由算法2知，条件（1）显然成立，下证条件（2）满足。

由定理2可知：区间值序信息系统中基于可分辨矩阵的差别信息树中所有仅含一个节点的路径所对应的单元素可分辨属性集的并组成了该区间值序信息系统中条件属性集的核core(A)。

将算法2第二步得到的core(A)看作R的一部分并在基于可分辨矩阵差别信息树中删掉所有含有core(A)中元素的路径。

令R′=R-core(A)。若r是R′中最右边的一个元素，则在当前的差别信息树中，根节点最右边的孩子节点的节点名一定是r，并且以该节点为根的子树中一定不包含R′-{r}中任何属性所对应的节点，则对r∈R,∃B∈DS满足B⋂(R-{r})=∅。可证R′中所有元素都满足该条件。因此，算法2得到的约简是完备约简。

4 实证分析

给定一个区间值序信息系统I≥=(U,A,F)（表1），其中有限对象集U={x1,x2,…,x10}，有限属性集为A={a,b,c,d,e}。

Table1 Interval valued sequence information systems表1 区间值序信息系统

先求取每个对象对的可分辨属性集，从而获得区间值序信息系统的可分辨矩阵。从而，表1所对应的可分辨矩阵如表2所示。

Table2 Discernibility matrix of interval valued ordinal information systems in Table 1表2 表1对应的区间值序信息系统的可分辨矩阵

注2可分辨矩阵中每一对对象对的可分辨属性集均应该为集合的形式，此处为了简便写成了如表2的形式。

根据极小析取范式可以求得表1所对应的区间值序信息系统的约简如下：

根据算法1给出表1所对应的区间值序信息系统中基于可分辨矩阵的差别信息树的具体构建过程如下：

（1）首先创建根节点；然后求取各个对象对的可分辨属性集，将可分辨属性集中的属性顺序按区间值序信息系统中条件属性从左至右的顺序排列；最后得到可分辨矩阵如表2所示。

（2）构建可分辨矩阵中第一个可分辨属性集A={a,b,c,d,e}所对应的路径＜a,b,c,d,e＞，将此路径插入到要构建的基于可分辨矩阵的差别信息树当中。

（3）为第二个可辨识属性集{a,b,c,e}创建其对应的路径＜a,b,c,e＞，其与路径＜a,b,c,d,e＞具有相同的前缀＜a,b,c＞。

（4）对于第三个可分辨属性集A，因为基于可分辨矩阵的差别信息树中已经存在A所对应的路径＜a,b,c,d,e＞，所以不构建新的路径。同理，将所有相同的可分辨属性集映射到同一个子集中。

（5）构建可分辨属性集{a,c}对应的路径＜a,c＞，它与路径＜a,b,c,d,e＞和＜a,b,c,e＞具有相同的前缀＜a＞。

依此类推，最后得到区间值序信息系统(表1)中基于可分辨矩阵的差别信息树如图1所示。

Fig.1 Difference information based on discernibility matrix(Table 2)图1 基于可分辨矩阵（表2）的差别信息

根据如图1所示的区间值序信息系统的基于可分辨矩阵的差别信息树以及算法2给出求取表1所对应的区间值序信息系统约简的过程：

（1）创建空集R。

（2）从区间值序信息系统的基于可分辨矩阵的差别信息树中选择仅含单个节点的路径＜d＞，将属性d存放在集合R中，然后删去树中有d的所有路径。

（3）此时选择差别信息树的根节点的最右子节点{b}令R=R⋃{b}，然后删去信息树中含有节点名为b的全部路径。

（4）此时差别信息树只余下一条路径＜a,c＞，此时选择差别信息树的根节点的子节点{a}，令R=R⋃{a}，最后输出R={d,b,a}，算法结束。于是{d,b,a}就是通过基于可分辨矩阵差别信息树求得的一个约简。

5 结束语

本文提出了区间值序信息系统的一种新的约简方法：首先构建区间值序信息系统的基于可分辨矩阵的差别信息树，然后通过该差别信息树求取该信息系统的属性约简。通过该差别信息树，实现了对可分辨矩阵的压缩储存，从而缩短了求取区间值序信息系统属性约简的空间复杂度。但从差别信息树的构建过程可知，往该差别信息树中插入的可分辨属性集当中的属性顺序是按信息表中属性的原始顺序，没有考虑属性重要度对信息树构建的影响。因此接下来的工作可以考虑结合属性重要度去实现对差别信息树的构建，看是否能对可分辨识矩阵进一步压缩储存。