基于改进差别信息树的广义决策属性约简

Generalized Decision Attribute Reduction Based on Improved Discernibility Information Tree

摘要: 属性约简作为一种有效的数据降维方法，对于处理高维数据具有重要意义，通过删除冗余属性保留重要属性，获得与原系统具有相同表达能力和分类能力的属性子集。差别矩阵是得到属性约简的一种重要方法，但其中含有大量无用的信息，本文受改进差别信息树的启发，将改进差别信息树与决策多层次系统相结合，在该方法下研究不同决策层级间改进差别信息树之间的关系，提出一种基于改进差别信息树的广义决策属性约简算法。所提方法不仅可以实现对差别矩阵中非空元素的压缩存储，还有效缩短了时间消耗。为了验证算法的有效性，选取8组UCI数据集分别从算法的约简结果和约简效率两方面进行对比，实验结果验证了算法的可行性和有效性。

Abstract: Attribute reduction, as an effective data dimensionality reduction method, is of great significance for dealing with high-dimensional data, which obtains a subset of attributes with the same expressive and categorization ability as the original system by removing redundant attributes and retain-ing important attributes. Discernibility matrix is an important method to get attribute reduction, but it contains a lot of useless information, this paper is inspired by the improved discernibility information tree, combines the improved discernibility information tree with the multi-hierarchical decision systems, studies the relationship between the improved discernibility information tree among different decision levels under this method, and proposes a generalized decision attribute reduction algorithm based on the improved discernibility information tree. The proposed method can not only realize the compressed storage of non-empty elements in the discernibility matrix, but also effectively reduce the time consumption. In order to verify the effectiveness of the algorithm, eight groups of UCI datasets are selected to compare the algorithm in terms of reduction results and reduction efficiency, and the experimental results verify the feasibility and effectiveness of the algorithm.

1. 引言

粗糙集理论 [1] 是知识获取的重要工具，其主要思想是利用知识库中已有的知识逼近不精确、不确定的知识。属性约简 [2] [3] [4] [5] 是粗糙集理论中的重要研究内容之一。属性约简是从条件属性集中删除冗余属性且保留重要属性，以获得与原系统具有相同分类能力的属性子集。

目前，启发式方法和 [6] [7] [8] 差别矩阵方法 [9] [10] [11] 被认为是求取属性约简行之有效的方法。其中，启发式方法通过计算核属性和各条件属性的属性重要度来求取属性约简，时间效率高，但每次只能求取决策表的一个约简。而差别矩阵方法能求取决策表的全部约简，但其计算复杂度高，耗费大量空间去存储无用的差别项，进而导致时间效率低下。2015年，蒋瑜 [12] 将两种方法结合起来，提出一种基于差别矩阵的启发式方法，即差别信息树，用于消除差别矩阵中无用差别项，实现差别矩阵的压缩存储。随后，许多学者对其工作进行了拓展研究。2019年，Yang等 [13] 在区间值序信息系统的背景下提出了基于差别矩阵的差别信息树；2019年，Jiang [14] 针对差别信息树不能有效去除核属性的父集差别信息和其他差别项父集差别信息的缺点，使用了两种策略来改进差别信息树，提出了一种改进差别信息树的属性约简算法；2020年，徐怡等 [15] 结合改进差别信息树的概念提出了基于优化差别矩阵和属性加权重要度的改进差别信息树属性约简算法。

基于上述讨论，现有工作大多是基于单层决策属性下进行研究，未有在决策多层次系统下的研究并且未有分析决策层次间差别信息树的关系，本文在决策多层次系统下，给出了由粗粒度决策到细粒度决策下构造的改进差别信息树的优化方法，提出了基于改进差别信息树的广义决策属性约简优化算法。最后，通过实验结果证明了算法的可行性和有效性。

2. 基本概念

2.1. 决策多层次系统下的广义决策约简

定义1. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统， $U=\left\{s_1,s_2,\cdots ,s_m\right\}$ 是有限个非空对象的集合，称为论域， $C=\left\{a_1,a_2,\cdots ,a_n\right\}$ 是条件属性的集合， $D=\left\{d\right\}$ 是决策属性的集合，其中d具有l个层次，即 $d=\left\{d^1,d^2,\cdots ,d^l\right\}$ ， $V_d^l$ 表示的是决策属性d在第l层次上的值。

定义2. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统， $\forall x,y\in [1,m]$ ， $d^l$ 表示的是决策属性d在第l层次上的值，对于 $\forall s\in U$ ，关于条件属性集 $A\subseteq C$ 的广义决策值定义为：

${\mu }_A^l\left(s_x\right)=\left\{d^l\left(s_y\right)|s_y\in {\left[s_x\right]}_A\right\}$ (1)

定义3. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统， $\forall x,y\in [1,m]$ ，若条件属性集 $A\subseteq C$ 为属性集C的一个广义决策约简，当且仅当满足以下两个条件：

1) 对 $\forall s_x\in U$ ，有 ${\mu }_A^l\left(s_x\right)={\mu }_C^l\left(s_x\right)$ ；

2) 对 $\forall A^{\prime }\subset A$ ，有 ${\mu }_{A^{\prime }}^l\left(s_y\right)\ne {\mu }_C^l\left(s_y\right)$ 。

条件：1) 保证了约简前后原系统的广义决策值不变；条件2) 保证了获得的约简是满足条件1)的最小属性子集，且获得的约简中没有冗余属性。

定义4. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统， $\forall x,y\in [1,m]$ ，决策多层次系统下第l层决策属性对应的差别矩阵为 $D{M}_{Gen}^l={\left(D{M}_{Gen}^l\left(s_x,s_y\right)\right)}_{m\times m}$ ，其中 $D{M}_{Gen}^l\left(s_x,s_y\right)$ 被定义为：

$D{M}_{Gen}^l\left(s_x,s_y\right)=\{\begin{array}{l}\left\{a\in C:a\left(s_x\right)\ne a\left(s_y\right)\right\}\text{,}{\mu }_C^l\left(s_x\right)={\mu }_C^l\left(s_y\right)\hfill \\ \varnothing ,\text{otherwise}\hfill \end{array}$ (2)

2.2. 差别信息树

定义5. [12] 差别信息树是一颗有序树，每个节点至多只有 $\left|C\right|$ 棵子树，差别信息树的子树也是有序树，其次序不能任意颠倒。具体定义如下：

1) 差别信息树中每个节点由4个部分组成：节点名、父亲指针、孩子指针和同名指针。父亲指针指向该节点的父亲节点，孩子指针指向该节点的孩子节点，同名指针指向差别信息树中其他路径中的该节点同名的节点。

2) 属性指针头表由2个部分组成：节点名和同名指针。节点名表示的是该表项对应的条件属性，同名指针表示的是指向差别信息树中与该表项为相同节点名的最左边节点。

核剪枝策略 [14] ：决策表的核是差别矩阵中只包含一个元素的差别项的并集。在对非空差别项进行压缩存储时，以决策表的核作为启发信息可以在构建改进差别信息树时避免核属性的父集差别项参与，从而有效消除树中含核属性的路径。

核剪枝策略虽然保证了能消除核属性的父集非空差别项，但不能保证其他非空差别项的父集差别信息是否能被消除。因此，将使用属性重要度策略来解决这个问题。

属性重要度策略 [14] ：基于差别矩阵的属性重要度定义为属性在差别矩阵中出现的次数，表示属性在决策表中的重要性。在构建改进差别信息树时，将属性重要度作为启发式信息，有助于使重要属性靠近根节点，提高改进差别信息树的压缩程度，有效减少非空差别项的父集元素。

定义6. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统， $D{M}_{Gen}^l$ 表示的是在第l层决策属性对应的差别矩阵， $\forall x,y\in [1,m]$ ， $\forall a\in C$ ，则α的重要度定义为：

$SI{G}^l\left(a\right)=\frac{Nu{m}_a^l}{\left|D{M}_{Gen}^l\left(e_x,e_y\right)\right|}$ (3)

其中， $\left|D{M}_{Gen}^l\left(e_x,e_y\right)\right|$ 表示的是全部非空差别项的基数， $Nu{m}_a^l$ 表示的是属性α在第l层决策属性对应的

差别矩阵非空差别项中出现的频率。

根据上述定义和策略，以及文献 [14] 提出的改进差别信息树的方法，给出了基于改进差别信息树的多层次广义决策约简，如表1所示。

Table 1. Multi-hierarchical Generalized Decision Reduction Based on Discernibility Information Tree (LHGTD)

表1. 基于改进差别信息树的多层次广义决策约简

3. 基于改进差别信息树的广义决策属性约简优化方法

定义7. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统， $U=\left\{s_1,s_2,\cdots ,s_m\right\}$ 是论域集合， $C=\left\{a_1,a_2,\cdots ,a_n\right\}$ 是条件属性的集合， $\forall x,y\in [1,m]$ ，给定对象 $s_z$ 在粗层次决策属性下的决策类 $D_{s_z}^{cu}$ 和差别矩阵 $D{M}_{Gen}^{D_{s_z}^{cu}}$ ，决策类为 $U/D_{s_z}^{cu}=\left\{D_1^{cu},D_2^{cu},\cdots ,D_{\left|U/D_{s_z}^{cu}\right|}^{cu}\right\}$ ，对象 $s_z$ 在细层次决策属性下的决策类为 $D_{s_z}^{xi}$ ， $U/D_{s_z}^{xi}=\left\{D_1^{xi},D_2^{xi},\cdots ,D_{\left|U/D_{s_z}^{xi}\right|}^{xi}\right\}$ 且 $D_{s_z}^{xi}\subseteq D_{s_z}^{cu}$ 。令 $v=\left|U/D_{s_z}^{cu}\right|$ ， $t=\left|U/D_{s_z}^{xi}\right|$ ，则对任意的 $D_t^{xi}\in U/D_{s_z}^{xi}$ ，存在 $D_v^{cu}\in U/D_{s_z}^{cu}$ ，满足 $D_t^{xi}\subseteq D_v^{cu}$ 。细层次决策属性下的差别矩阵 $D{M}_{Gen}^{D_{s_z}^{xi}}={\left(D{M}_{Gen}^{D_{s_z}^{xi}}\left(s_x,s_y\right)\right)}_{m\times m}$ 可由以下方式得到：

$D{M}_{Gen}^{D_{s_z}^{xi}}={\left(D{M}_{Gen}^{D_{s_z}^{xi}}\left(s_x,s_y\right)\right)}_{m\times m}$ (4)

其中：

$\text{condition}1={\mu }_C^{D_{s_z}^{xi}}\left(s_x\right)\ne {\mu }_C^{D_{s_z}^{cu}}\left(s_y\right)\wedge D{M}_{Gen}^{D_{s_z}^{cu}}\left(s_x,s_y\right)\ne \varnothing$ ， $\text{condition}2={\mu }_C^{D_{s_z}^{xi}}\left(s_x\right)\ne {\mu }_C^{D_{s_z}^{cu}}\left(s_y\right)\wedge D{M}_{Gen}^{D_{s_z}^{cu}}\left(s_x,s_y\right)\ne \varnothing$ 。

定义8. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统，将细层次决策属性下的差别矩阵 $D{M}_{Gen}^{D_{s_z}^{cu}}$ 新增加的项定义为：

$NewD{M}_{Gen}^{D_{s_z}^{xi}}\left(s_x,s_y\right)=\left\{a\in C|a\left(s_x\right)\ne a\left(s_y\right)\right\}$ (5)

基于上述定义及分析，在表1的基础上结合了本节的优化方法，设计了基于改进差别信息树的广义决策属性约简加速算法(An Acceleration Algorithm for Multi-hierarchical Generalized Decision Reduction Based on Improved Discernibility Information Tree, OMGDIT)，称为算法1。

算法1. 算法1是修改了表1中的部分步骤，具体实现过程为：已知粗层次决策属性下的差别矩阵 $D{M}_{Gen}^{D_{s_z}^{cu}}$ 和改进差别信息树 $DCTre{e}^{cu}$ ，根据公式(4)求得细层次决策属性下的差别矩阵 $D{M}_{Gen}^{D_{s_z}^{cu}}$ ，替换步骤2，然后根据公式(5)计算差别矩阵新增项 $NewD{M}_{Gen}^{D_{s_z}^{xi}}\left(s_x,s_y\right)$ 替换步骤4.4，且步骤1中不需初始化改进差别信息树，而是在 $DCTre{e}^{cu}$ 基础上继续构造。除此之外，算法1其他计算步骤与表1相同。

定理1. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统，LEDS下基于差别矩阵的广义决策构造的改进差别信息树DCTree中包含了求取广义决策约简的所有差别项。

证明：设集合DTS包含了基于差别矩阵的广义决策构造的改进差别信息树所有路径的差别属性集，集合 $D{M}_{Gen}^l$ 是广义决策差别矩阵。由改进差别信息树的构造过程可知： $DTS\subseteq D{M}_{Gen}^l$ ，对于任意一个 $D{M}_{Gen}^l\left(s_x,s_y\right)\in D{M}_{Gen}^l$ ，存在 $D{M}_{Gen}^l\left({s^{\prime }}_x,{s^{\prime }}_y\right)\in DTS$ ，使得 $D{M}_{Gen}^l\left({s^{\prime }}_x,{s^{\prime }}_y\right)\subseteq D{M}_{Gen}^l\left(s_x,s_y\right)$ ，两者进行合取运算之后的结果还是 $D{M}_{Gen}^l\left({s^{\prime }}_x,{s^{\prime }}_y\right)$ 。由此可得，基于差别矩阵的广义决策构造的改进差别信息树DCTree中包含了求取广义决策约简的所有差别项。

定理2. 四元组 $\text{LEDS}=\left(U,AT=C\cup D,V,f\right)$ 是一个决策多层次系统，若W是基于差别矩阵的广义决策构造的改进差别信息树中根节点下的所有子节点所表示的属性集合，则对于任意的 $s\in U$ ，有 ${\mu }_W^l\left(s\right)={\mu }_C^l\left(s\right)$ 成立。

证明：由定理1，并设集合DTS为包含了基于差别矩阵的广义决策构造的改进差别信息树所有路径的差别属性集，对于 $\forall D{M}_{Gen}^l\left(s_x,s_y\right)\in DTS$ ，有 $D{M}_{Gen}^l\left(s_x,s_y\right)\cap W\ne \varnothing$ ，根据差别矩阵的定义4可知 ${\mu }_C^l\left(s_x\right)={\mu }_C^l\left(s_y\right)$ ，可得对于任意的 $s_x\in U$ ，有 ${\mu }_W^l\left(s\right)={\mu }_C^l\left(s\right)$ 成立。

4. 实验分析

本节将在约简结果和约简效率两个方面对所提出算法进行验证。本节进行的所有的实验都是在一台带有AMD Ryzen 5 3500X 6-Core Processor3.60 GHz、16 GB内存和操作系统是Windows 10 Professional的台式机上进行的。算法在Pycharm2023.1.3上运行，运行环境为Python3.9，实验图使用Python绘制。

实验选取了8组UCI数据集(https://archive.ics.uci.edu/datasets)来验证本文提出算法的性能，数据集详细信息如表2所示。为了得到实验所使用的数据集，需要对8组数据进行预处理，预处理过程分为以下几个步骤：首先将条件属性离散化；其次将名词性数据替换为整数表示；最后将单层决策使用DBSCAN聚类方法转为三层决策。

Table 2. UCI Datasets

表2. UCI数据集

4.1. 约简结果的正确性验证

本节将对所提算法在8组UCI数据集上的约简结果及约简长度进行对比，如表3所示。表中左侧的“序号”是数据集标号，对应表2中的数据集；表中“LHGTD-d²”和“LHGTD-d³”分别是算法LHGTD

Table 3. Reduction results

表3. 约简结果

在决策属性d²在第2层次上和决策属性d³在第3层次上获得的约简结果；表中“OMGDIT-d²”和“OMGDIT-d³”分别是算法OMGDIT在决策属性d²在第2层次上和决策属性d³在第3层次上获得的约简结果，约简结果中0表示第一个属性，1表示第二个属性，以此类推。

从表3的结果中可以看出，算法LHGTD所求得的广义决策约简结果以及长度与相对应层次的决策属性的算法OMGDIT所求得的广义决策约简结果和长度是相同的。并且在一般情况下，当决策层级变细时，两个算法所求得的约简结果的长度会保持不变或变长。

4.2. 约简效率

为了验证本章所提出算法的有效性，8组UCI数据集以对象增加的方式进行对比实验，实验结果如图1所示。对象递增时，数据集被平均分成十份，实验时逐次增加一份作为测试数据集，即第1份作为第一次测试数据集，第1份和第2份作为第二次测试数据集，以此类推，第十次测试使用全部的数据集。图1展示了LHGTD和OMGDIT算法的约简效率对比。

(a) Zoo (b) Ecoil (c) Dermatology (d) Connectionist (e) Vowel (f) Obesity (g) Stalog (h) Abalone

Figure 1. Comparison of reduction efficiency

图1. 约简效率对比

由图1(a)~(h)可知，随着对象规模的增加，LHGTD算法求取属性约简消耗的时间增加越来越快，所提OMGDIT算法求取属性约简的时间较为平缓，并且大多数情况OMGDIT算法的时间消耗小于LHGTD算法的时间消耗。实验说明OMGDIT算法的计算效率优于LHGTD算法的计算效率，OMGDIT算法通过构建差别矩阵和改进差别矩阵的优化方法能够更高效的求取广义决策约简，从而提高了算法整体的效率。

5. 结论

本文构建了以决策多层次系统为数据背景的差别矩阵以及改进差别信息树，给出了决策多层次系统下差别矩阵和改进差别信息树的定义，提出了基于改进差别信息树的广义决策属性约简优化算法，实验部分选用8组UCI数据集分别比较了约简结果和约简效率，实验证明了所提算法的高效性和有效性。

基金项目

本文受烟台市科技计划项目(编号：2022XDRH016)的资助。