序决策系统下近似约简的启发式算法

Heuristic Algorithm to Attribute Reduction for Lower Approximation Preservation in Ordered Decision Systems

摘要: 随着网络的进步，社会中产生了大量的高维数据，但很多统计方法难以直接应用到高维数据上。如何获得去噪简化且保存关键信息的低维度数据是一项急需解决的问题。粗糙集理论提供了一种数据降维的方法，被称为属性约简。属性约简的目标是保证原数据集的一种分类特征不变，获得其最小的属性子集。目前，基于不同的分类特征，已提出了许多不同的属性约简算法，如下近似保持、分布保持等。在序决策系统中，传统的下近似约简算法是基于差别矩阵的，计算复杂度高。为了解决这一问题，本文使用依赖度，设计了一个后向贪婪的启发式算法来计算下近似约简。实验使用6组UCI数据集。实验结果表明本文设计的算法可以得到正确的下近似约简，并在时间效率上优于传统的差别矩阵算法。

Abstract: With the development of network, a large number of high-dimensional data are generated in the society, but many statistical methods are difficult to be directly applied to high-dimensional data. How to obtain the denoising simplified data with low dimensions and key information is an urgent problem. Rough set theory provides a method for reducing data dimensions, called attribute reduction. The purpose of attribute reduction is to obtain a minimal subset of attributes without changing a classification property of the original data. Until now, different attribute reduction methods are proposed for different classification properties, such as lower approximation preservation and distribution preservation. In an ordered decision system, the traditional attribute reduction algorithm is based on discernibility matrices, and the computation complexity is high. To solve this problem, we design a backward greedy heuristic algorithm to compute a reduct for lower approximation preservation. The experiments are conducted in six UCI data sets. The experimental results show that the algorithm gets a correct reduct and is better than the traditional discernibility matrix algorithm in time efficiency.

1. 引言

粗糙集理论 [1] 是Pawlak提出的处理模糊数据分类的有效方法，已被使用在数据挖掘 [2] [3]、数据分析 [4] 和机器学习 [5] 等领域。属性约简 [6] [7] [8] 是粗糙集理论中的一种数据降维方法。属性约简可以保证原数据集的一种分类特征不变，然后获得最小的特征子集。Pawlak粗糙集使用等价关系来划分样本，但在现实生活中，样本往往需要使用序关系来进行描述，例如学生的成绩、产品的市场占有率等。序决策系统是经典决策系统的一种拓展。在序决策系统中，属性的值域是有序的，在样本间能建立偏序(优势)关系。为了从序决策系统中提取有效信息，Greco等 [9] 提出了优势粗糙集方法(Dominance-based rough set approach, DRSA)。

如今，对于DRSA的研究已经较为深入。对于序决策系统中不同的分类特征，专家学者们设计了许多不同的属性约简算法。Yuan等 [10] 提出了上近似保持约简和广义决策保持约简的算法，并证明了两种算法结果的等价性。Xu等 [11] 提出了下近似保持约简算法。Qian等 [12] [13] 将DRSA应用于集值数据和区间值数据，提出了优势关系保持的约简算法。

以上提及的算法是基于差别矩阵 [14]、利用布尔运算法则来进行计算的。尽管这种方法能够得到所有的约简结果，但计算的时间复杂度高。为了提升属性约简的效率，专家学者们在序决策系统中研究设计了启发式算法 [15] [16] [17]。启发式算法能够根据不同的分类特征得到一个约简结果，计算效率高。本文基于后向贪婪策略，在序决策系统中提出了下近似约简的启发式算法。实验表明，本文所提的算法能计算出一个正确的下近似约简，且在时间效率上优于Xu等 [11] 提出的差别矩阵算法。

2. 基本概念

给定一个序决策系统 $S=\left(O,A=M\cup N\right)$，O是样本集合，也被称为论域。A是属性集合，其中M是条件属性集合，N是决策属性集合。对于 $\forall a\in A$， $\forall x\in O$， $a\left(x\right)$ 表示样本x在某个属性a下的取值。表1为一个序信息系统，论域 $O=\left\{x_1,x_2,x_3,x_4\right\}$，条件属性集 $M=\left\{a,b,c\right\}$，决策属性集 $N=\left\{d\right\}$。

Table 1. An ordered decision system

表1. 序决策系统

定义1 [9] 给定一个序信息系统 $S=\left(O,A=M\cup N\right)$，对于 $B\subseteq A$，记

$R_B^{\ge }=\left\{\left(x,y\right)\in O\times O|\forall a\in B,a\left(x\right)\ge a\left(y\right)\right\}.$

则 $R_B^{\ge }$ 为属性集B下的优势关系。 $\left(x,y\right)\in R_B^{\ge }$ 表示x在属性集B下优于y，且 $R_B^{\ge }={\cap }_{a\in B}{R}_a^{\ge }$。

优势关系是一个自反、传递、反对称的偏序关系，由优势关系可以导出论域上的一个覆盖。对于 $B\subseteq M$， ${\left[x\right]}_B^{\ge }=\left\{y\in O|\left(y,x\right)\in R_B^{\ge }\right\}$ 和 ${\left[x\right]}_B^{\le }=\left\{y\in O|\left(x,y\right)\in R_B^{\ge }\right\}$ 为样本x关于属性集B的条件优势类和条件劣势类。对于决策属性集N， ${\left[x\right]}_N^{\ge }=\left\{y\in O|\left(y,x\right)\in R_N^{\ge }\right\}$，称 ${\left[x\right]}_N^{\ge }$ 为样本x关于优势关系 $R_N^{\ge }$ 的决策优势类，关于 $R_N^{\ge }$ 的决策优势类的全体记为 $O/R_N^{\ge }=\left\{N_1,N_2,\cdots ,N_t\right\}=\left\{{\left[x\right]}_N^{\ge }|x\in O\right\}$。

定义2 [9] 给定一个序决策系统 $S=\left(O,A=M\cup N\right)$，对于 $B\subseteq M$， $N_i\in O/R_N^{\ge }$，记

$\underset{\_}{R_B^{\ge }}\left(N_i\right)=\left\{x\in O|{\left[x\right]}_B^{\ge }\subseteq N_i\right\};$

$\overline{R_B^{\ge }}\left(N_i\right)=\left\{x\in O|{\left[x\right]}_B^{\le }\cap N_i\ne \varnothing \right\},$

$\underset{\_}{R_B^{\ge }}\left(N_i\right)$ 和 $\overline{R_B^{\ge }}\left(N_i\right)$ 分别为 $N_i$ 关于属性集B的下近似和上近似。

3. 下近似保持约简以及差别矩阵算法

在下近似集合中，每一个样本对应着数据集中的一条确定性规则，保证约简前后下近似不变，即保证了确定性规则不变。Xu等 [11] 在序决策系统S中定义了下近似约简。

定义3 [11] 给定一个序决策系统 $S=\left(O,A=M\cup N\right)$，对于 $B\subseteq M$， $O/R_N^{\ge }=\left\{N_1,N_2,\cdots ,N_t\right\}$，B是序决策系统S的一个下近似约简需满足以下两点：

1) $\forall N_i\in O/R_N^{\ge },\underset{\_}{R_B^{\ge }}\left(N_i\right)=\underset{\_}{R_M^{\ge }}\left(N_i\right)$，

2) $\forall P\subset B,\exists N_i\in O/R_N^{\ge },\underset{\_}{R_P^{\ge }}\left(N_i\right)\ne \underset{\_}{R_B^{\ge }}\left(N_i\right)$。

条件1)保证了约简前后S的下近似保持不变，条件2)则保证获得的约简B是能够满足1)的最小属性子集。为了计算下近似约简，Xu等 [11] 设计了一个差别矩阵算法，如表2所示。

Table 2. A discernibility matrix algorithm for lower approximation preservation (DMALA) [11]

表2. 基于下近似保持的差别矩阵算法 [11]

4. 基于依赖度的启发式算法

上一节介绍的差别矩阵算法是基于范式转换来计算约简的。研究已表明，范式的转换是一个NP-Hard问题，因此Xu等 [11] 设计的差别矩阵算法计算复杂度高，难以应用在多样本的高维数据集上。为了提升计算效率，本节基于依赖度，提出了一个下近似约简的启发式算法。

定义4 [18] 给定一个序决策系统 $S=\left(O,A=M\cup N\right)$，对于 $B\subseteq M$， $O/R_N^{\ge }=\left\{N_1,N_2,\cdots ,N_t\right\}$，记

${\gamma }_B^{\ge }=\frac{1}{\left|O\right|}{\displaystyle \underset{i=1}{\overset{t}{\sum }}\left|\underset{\_}{R_B^{\ge }}\left(N_i\right)\right|},$

则 ${\gamma }_B^{\ge }$ 为属性集B关于决策属性N的依赖度，其中 $\left|\cdot \right|$ 表示集合中元素的个数。

基于依赖度，给出下近似约简的等价定义如下。

定义5 [18] 给定一个序决策系统 $S=\left(O,A=M\cup N\right)$，对于 $B\subseteq M$，B是序决策系统S的一个下近似约简需满足以下两点：

1) ${\gamma }_B^{\ge }={\gamma }_M^{\ge }$，

2) $\forall P\subset B,{\gamma }_P^{\ge }\ne {\gamma }_B^{\ge }$。

基于定义5，本文将依赖度作为搜索条件，设计了一个后向贪婪的算法，在每次迭代过程中逐步搜索删除冗余属性。算法具体步骤如表3所示。

Table 3. A backward greedy algorithm for lower approximation preservation (BGALA)

表3. 基于下近似保持的后向贪婪算法

令m表示样本个数，n表示条件属性数目。算法BGALA第1步和第2步是为了计算原始属性集的依赖度，时间复杂度为 $O\left(m^2{n}^2\right)$。第4步是一个迭代的过程，在每次迭代中删除一个对依赖度无影响(冗余)的属性，其时间复杂度为 $O\left(m^3{n}^2\right)$。当所有冗余属性被删除，输出约简结果B。算法的整体时间复杂度是 $O\left(m^3{n}^2\right)$。

5. 实验分析

本节通过实验对比Xu等 [11] 的算法DMALA和本文所提算法BGALA。实验对比主要有两个方面。首先对比两种算法(DMALA, BGALA)的约简结果，验证BGALA可以获得和DMALA相同的约简。然后对DMALA和BGALA的运行效率进行对比。本节实验所用的硬件配置为：Windows 10 64位操作系统，Inter(R) Core(TM) i5-8400处理器，16G运行内存。实验使用的编程语言为Python3.6.5，编译器为Pycharm Community Edition 2018.3.6。实验使用的6组UCI数据集如表4所示。

Table 4. Data sets description

表4. 数据集描述

5.1. 约简结果对比

表5为DMALA和BGALA两种算法的约简结果对比。属性按照从左到右的顺序使用从1开始的正整数来命名。从表中可以看出，DMALA可以得到多个下近似约简，BGALA只能得到一个下近似约简。而且，在DMALA计算出的所有下近似约简中，有一个约简和BGALA计算出的约简是相同的。这个实验结果说明BGALA的计算结果是DMALA的计算结果之一，是一个正确的下近似约简。

Table 5. The comparison of the reduction results

表5. 约简结果对比

5.2. 时间效率对比

图1~6展示了DMALA、BGALA在6组数据集上的效率对比。其中横轴代表属性的个数，纵轴代表运行时间。从图中可以看出，随着属性数的增加，BGALA的运行时间曲线较为平稳，而DMALA的运行时间曲线则波动较大。属性数目较少时，BGALA的运行时间略长于DMALA的运行时间，但当属性数目较大时，BGALA的运行时间要远远短于DMALA的运行时间。这个实验结果表明，在处理高维数据时，BGALA的时间性能要优于DMALA。

6. 总结

在序决策系统中，下近似约简的差别矩阵算法时间复杂高，不利于应用在高维数据当中。本文通过引入依赖度的概念，设计了一个后向贪婪的启发式算法来获得下近似约简。实验证明本文所提的算法能计算出一个正确的约简，并在时间性能上优于传统的差别矩阵算法。下一步将继续研究其它约简目标的启发式算法。

Figure 1. Absenteeism at work

图1. Absenteeism at work

Figure 2. Chronic kidney disease

图2. Chronic kidney disease

Figure 3. Dermatology

图3. Dermatology

Figure 4. Flags

图4. Flags

Figure 5. Lymphography

图5. Lymphography

Figure 6. Stalog (vehicle)

图6. Stalog (vehicle)

基金项目

烟台大学研究生科技创新基金(YDYB2023)资助。