区间值决策系统下的最小属性约简

Minimum Attribute Reduction under Interval-Valued Decision System

摘要: 在给定的属性约简目标函数下，决策表中往往存在多个约简。最后的决策规则集直接依赖于所获得的约简。决策规则集的简洁性、可理解性、通用性和精确性因约简的不同而不同，因此期望得到一些最优结果，即长度最短的最小约简。这样可以尽可能多地去除冗余属性，有效地管理决策表的存储空间，并且决策规则集的性能将变得优异。不幸的是，寻找最小约简已被证明是一个NP-难问题(Wong和Ziarko 1985)。当给定决策表时，启发式算法并不总是能得到最小约简。因此本文在区间值决策系统下提出了基于差别矩阵的0-1规划最短约简算法。

Abstract: With a given attribute reduction objective function, there are often multiple reductions in the deci-sion table. The final decision rule set is directly dependent on the obtained reductions. The con-ciseness, comprehensibility, generality and accuracy of the decision rule set vary from one reduc-tion to another, so it is expected to obtain some optimal result, i.e., the smallest reduction with the shortest length. This will remove as many redundant attributes as possible, manage the storage space of the decision table efficiently, and the performance of the decision rule set will become superior. Unfortunately, finding the minimum reduction has been shown to be an NP-hard problem (Wong and Ziarko, 1985). Heuristic algorithms do not always yield the minimum reduction when given a decision table. Therefore, in this paper, we propose a difference matrix-based shortest reduction algorithm for 0-1 programming under interval-valued decision system.

1. 引言

波兰数学家Pawlak于1982年提出的粗糙集理论 [1] ，它是一种新型的处理模糊和不确定知识的数学工具，其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。属性约简 [2] [3] [4] [5] 是粗糙集理论中的核心内容之一，数据库中的属性并不是同等重要的，甚至其中某些知识是冗余的，通过属性约简，可以去除数据库中的冗余、无用的成分，揭示数据中隐含的规律。从粗糙集理论的角度来理解，在一个信息系统中，有些属性对于分类来说是多余的，去掉这些属性后，信息系统的分类能力不会改变，所以属性约简后仍然反映了一个信息系统的本质信息 [6] [7] [8] [9] [10] 。一般来讲，一个信息系统的属性约简不是唯一的，通常人们希望能够找到一个属性个数最小的属性约简，该属性约简称为最小属性约简。

对任一给定区间值决策系统，若属性约简算法能确保找到其最小属性约简，则该算法称为最小属性约简的完备算法。现有的最短约简工作大多是基于二进制差别矩阵 [11] [12] [13] 的方法，这种方法大多又只适用于经典的粗糙集系统模型。本文在经典的区间值决策系统数据背景下，提出了基于差别矩阵的0-1规划最短约简算法并与经典的基于差别矩阵的属性约简算法作比较。

2. 基本概念

2.1. 区间值决策系统

定义1 给定区间值系统IVDS是一个四元组： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，其中U是一个非空有限集合称为论域，AT表C表示条件属性的集合，D表示决策属性的集合， $V_a$ 表示的是属性a的值域，f是一个映射函数，其中 $f:U\times AT\to V$ ， $f\left(x,a\right)$ 表示对象 $x\in U$ 在属性 $a\in C$ 上的取值，简记为 $a\left(x\right)$ ， $f\left(x,d\right)$ 表示对象x在属性 $d\in D$ 上的取值，简记为 $d\left(x\right)$ 。

定义2 [14] 设 ${\xi }_i=\left[l_i^m,u_i^m\right]$ 和 ${\xi }_j=\left[l_j^m,u_j^m\right]$ 为任意两个区间值，分别表示的是对象 $x_i$ 和 $x_j$ 在属性 $a_m$ 下的属性值，则区间值的相关运算如下：

${\xi }_i\cap {\xi }_j=\{\begin{array}{l}\varnothing ,\left(u_i^m<l_j^m\right)\vee \left(u_j^m<l_i^m\right)\\ \left[\max \left(l_i^m,l_j^m\right),\min \left(u_i^m,u_j^m\right)\right],\text{otherwise}\end{array}$ (1)

${\xi }_i\cup {\xi }_j=\left[\min \left(l_i^m,l_j^m\right),\max \left(u_i^m,u_j^m\right)\right]$ (2)

其中 $1\le i,j\le \left|U\right|$ ， $1\le m\le \left|C\right|$ ， $\left|U\right|$ 表示对象的个数， $\left|C\right|$ 表示条件属性的个数。式(1)和式(2)分别表示两个区间数的交运算和并运算。

定义3 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，对于 $\forall x_i,x_j\in U,a_m\in C$ ，区间值 ${\xi }_i=\left[l_i^m,u_i^m\right]$ 和 ${\xi }_j=\left[l_j^m,u_j^m\right]$ 的杰卡德相似系数 [15] $Si{m}_{i,j}^m$ 为：

$Si{m}_{i,j}^m=\frac{\left|\left[l_i^m,u_i^m\right]\cap \left[l_j^m,u_j^m\right]\right|}{\left|\left[l_i^m,u_i^m\right]\cup \left[l_j^m,u_j^m\right]\right|}$ (3)

又称为杰卡德相似率用于度量区间数之间的相似性。

定义4 [16] 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ， $E\subseteq C$ ，阈值 $\alpha$ 的取值范围是 $0\le \alpha \le 1$ ，定义关于条件属性子集E下的 $\alpha$ -相容关系 ${\mathcal{l}}_C^{\alpha }$ 为：

${\mathcal{l}}_C^{\alpha }=\left\{\left(x_i,x_j\right)|\left(x_i,x_j\right)\in U\times U,Si{m}_{i,j}^m\ge \alpha ,a_m\in C\right\}$ (4)

定义5 [16] 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ， $E\subseteq C$ ， $0\le \alpha \le 1$ ， ${\mathcal{l}}_C^{\alpha }$ 是在条件属性子集E下的 $\alpha$ -相容关系，定义关于对象 $x_i$ 在属性 $E\subseteq C$ 下的相容类为：

$T{C}_E^{\alpha }\left(x_i\right)=\left\{x_j|x_j\in U:\left(x_i,x_j\right)\in {\mathcal{l}}_E^{\alpha }\right\}$ (5)

$\forall a_m\in E$ ， $a_m$ 的相容类为：

$T{C}_{\left\{a_m\right\}}^{\alpha }\left(x_i\right)=\left\{x_j|x_j\in U:\left(x_i,x_j\right)\in {\mathcal{l}}_{\left\{a_m\right\}}^{\alpha }\right\}$ (6)

在E下的 $\alpha$ -相容类集合为：

$T{C}_E^{\alpha }\left(U\right)=\left\{T{C}_E^{\alpha }\left(x_1\right),T{C}_E^{\alpha }\left(x_2\right),\cdots ,T{C}_E^{\alpha }\left(x_n\right)\right\}$ (7)

其中n的值为论域里对象的个数。

定义6 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，定义C， $X\subseteq U$ 关于 $\alpha$ -相容类 $T{C}_C^{\alpha }\left(x_i\right)$ 的上、下近似为：

${\overline{Apr}}_C^{\alpha }\left(X\right)=\left\{x_i:x_i\in U,T{C}_C^{\alpha }\left(x_i\right)\cap X\ne \varnothing \right\}$ (8)

${\underset{\_}{Apr}}_C^{\alpha }\left(X\right)=\left\{x_i:x_i\in U,T{C}_C^{\alpha }\left(x_i\right)\subseteq X\right\}$ (9)

决策属性D对论域的划分为 $U/D=\left\{D_1,D_2,\cdots ,D_{\left|U/D\right|}\right\}$ ，对于 $\forall x_i\in U$ ，决策属性D的上、下近似定义如下：

${\overline{Apr}}_C^{\alpha }\left(D\right)=\left\{x_i:x_i\in U,T{C}_C^{\alpha }\left(x_i\right)\cap D\ne \varnothing \right\}$ (10)

${\underset{\_}{Apr}}_C^{\alpha }\left(D\right)=\left\{x_i:x_i\in U,T{C}_C^{\alpha }\left(x_i\right)\subseteq D\right\}$ (11)

关于决策属性D对于属性集C的正域为：

$PO{S}_C^{\alpha }\left(D\right)={\displaystyle \underset{D_j\in U/D}{\cup }{\underset{\_}{Apr}}_C^{\alpha }\left(D_j\right)}$ (12)

其中 $\left|U/D\right|$ 表示 $U/D$ 集合中元素个数。

2.2. 差别矩阵

性质1 [17] 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ， $\alpha$ -相容类 $T{C}_C^{\alpha }\left(x_i\right)$ 的具有以下性质：

1) 满足对称性： $\forall x,y\in U$ ，如果 $\left(x,y\right)\in {\mathcal{l}}_C^{\alpha }$ ，则 $\left(y,x\right)\in {\mathcal{l}}_C^{\alpha }$ ；

2) 满足自反性：对于 $\forall x\in U$ ，有 $\left(x,x\right)\in {\mathcal{l}}_C^{\alpha }$ ；

3) 不传递性： $\forall x,y,z\in U$ ，如果 $\left(x,z\right)\in {\mathcal{l}}_C^{\alpha }$ 和 $\left(z,y\right)\in {\mathcal{l}}_C^{\alpha }$ ，成立，则 $\left(x,y\right)\in {\mathcal{l}}_C^{\alpha }$ 不一定成立。

定义7 [14] 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ， $E\subseteq C$ 是IVDS的一个正域保持约简当且仅当以下两条件成立：

1) 联合充分性： $PO{S}_E^{\alpha }\left(D\right)=PO{S}_C^{\alpha }\left(D\right)$ ；

2) 个体必要性： $\forall c\in E$ ，满足 $PO{S}_{E-\left\{c\right\}}^{\alpha }\left(D\right)\ne PO{S}_E^{\alpha }\left(D\right)$ 。

定义8 [1] 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ， $U=\left\{x_1,x_2,\cdots ,x_n\right\}$ 对于

$\forall x,y\in \left[1,n\right]$ ， $\alpha \in \left[0,1\right]$ ，正域保持约简对应的差别矩阵为 $M^{\alpha }={\left(m_{xy}^{\alpha }\right)}_{n\times n}$ ，其中 $m_{xy}^{\alpha }$ 表示为：

$m_{xy}^{\alpha }=\{\begin{array}{l}\left\{a_m\in C:Si{m}_{ij}^m\le \alpha \right\},\text{condition}1\\ \varnothing ,\text{otherwise}\end{array}$ (13)

其中 $\text{condition}\text{1}=x_x\vee x_y\in PO{S}_C^{\alpha }\left(D\right)\wedge d\left(x_x\right)\ne d\left(x_y\right)$ ， $n=\left|U\right|$ 。

定义9 [1] 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，正域约简对应的差别函数为：

$D{F}^{\alpha }=\wedge \left\{\vee m_{xy}^{\alpha }:m_{xy}^{\alpha }\ne \varnothing \right\}$ (14)

差别函数 $D{F}^{\alpha }$ 可以转化为极小析取范式 $D{H}^{\alpha }$ 。

基于上述定义，结合文献 [18] 所提出的快速约简方法和文献 [16] 给出区间值决策系统下基于差别矩阵的正域约简算法((Positive regions Reduction Algorithm based on Discernibility Matrix, PRADM))如表1所示。

Table 1. Positive regions reduction algorithm based on discernibility matrix (PRADM)

表1. 基于差别矩阵的正域约简算法

3. 0-1规划问题

定义9中的差别函数可以求出所有约简，但是在实际生活中，有时只需要找出一个约简即可，于是人们就去寻找最短约简，即能区分开所有对象的条件属性最少的约简集合。文献 [19] 提出了计算信息系统的最小属性约简可转化为求解0-1规划问题，本小节主要分析计算最短属性约简如何转换成求解0-1规划问题。

定义10 设 $X,Y$ 是差别矩阵中的两个元素，若 $X\subseteq Y$ ，即X中的属性都包含于Y中的属性，称Y为X的重复元素。

因此为了求得约简，通常会把重复元素和空集删去，下面引入极小差别集合的概念。

定义11 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，如果 $Ms=\left\{s_1,s_2,\cdots ,s_k\right\}$ 为区间值系统的极小差别集合，则Ms满足以下两个条件：

1) $\forall s_k\in Ms$ ， $\exists m_{ij}\ne \varnothing$ 使得 $s_k=m_{ij}$ ；

2) $\forall i,j\in \left\{1,2,\cdots ,n\right\}$ ， $k\in \left\{1,2,\cdots ,l\right\}$ ， $m_{ij}\ne \varnothing$ ，若 $m_{ij}\subseteq s_k$ ，则 $s_k=m_{ij}$ 。

由定义11可知，差别矩阵的非空极小项构成了极小差别集合，对差别矩阵进行约简时删除重复元素和空集就得到了极小差别集合，极小差别集合与差别矩阵起到相同的作用，可以代替差别矩阵。

定理1给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，假设R是一个约简，那么它的充要条件如下：

1) $R\cap s_i\ne \varnothing ,i\in \left[1,k\right]$ ；

2) $\forall a\in R$ ， $\exists j\in \left\{1,2,\cdots ,k\right\}$ ，使得 $s_j\cap \left(R-\left\{a\right\}\right)=\varnothing$ 。

根据定理1可以将R转化为如下优化问题：

$\begin{array}{l}\min \left|R\right|\\ \text{s}\text{.t}.R\cap s_i\ne \varnothing ,i\in \left[1,k\right],\\ \forall a\in R,\exists j\in \left\{1,2,\cdots ,k\right\},\\ s_k\cap \left(R-\left\{a\right\}\right)=\varnothing \end{array}$ (15)

经分析可进一步优化为：

$\begin{array}{l}\min \left|R\right|\\ \text{s}\text{.t}\text{.}R\cap s_i\ne \varnothing ,i\in \left[1,k\right]\end{array}$ (16)

下面证明优化问题(15)和(16)等价：

“(16) $\Rightarrow$ (15)”使用反证法。假设 $R^o$ 是(16)的最优解，现须得证明 $R^o$ 使得优化条件 $\forall a\in R^o$ ， $\exists j\in \left\{1,2,\cdots ,k\right\}$ ， $s_j\cap \left(R^o-\left\{a\right\}\right)=\varnothing$ 满足。假设该条件不满足，则 $\exists a\in R^o$ ， $\forall j\in \left\{1,2,\cdots ,k\right\}$ ， $s_j\cap \left(R^o-\left\{a\right\}\right)=\varnothing$ ，令 $R^{\prime }=R^o-\left\{a\right\}$ ，则有 $\forall i\in \left\{1,2,\cdots ,k\right\}$ ， $s_i\cap R^{\prime }\ne \varnothing$ ，即 $R^{\prime }$ 是(16)的可行解，且 $R^{\prime }\subseteq R^o$ 这就导致 $R^o$ 不是最优解与题意矛盾。所以 $R^o$ 满足优化条件 $\forall a\in R^o$ ， $\exists j\in \left\{1,2,\cdots ,k\right\}$ ， $s_j\cap \left(R^o-\left\{a\right\}\right)=\varnothing$ 。

“(15) $\Rightarrow$ (16)”假设 $R^o$ 是(15)的最优解，则 $R^o$ 是(16)的可行解。因为 $R^o$ 满足优化条件 $\forall a\in R^o$ ， $\exists j\in \left\{1,2,\cdots ,k\right\}$ ， $s_j\cap \left(R^o-\left\{a\right\}\right)=\varnothing$ ，所以 $R^o$ 去掉任意属性(16)的约束条件就不成立，这就说明 $R^o$ 确为(16)的最优解。

4. 基于0-1规划的特定类最小属性约简算法

定义12给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，属性集合 $C=\left\{a_1,a_2,\cdots ,a_m\right\}$ ，最小约简对应一个列向量 $e={\left(e_1,e_2,\cdots ,e_n\right)}^{\text{T}}$ ，该向量的表述如下所示：

$e_i=\{\begin{array}{l}0,a_i\notin RED\\ 1,a_i\in RED\end{array}$ (17)

易知 $\left|RED\right|={\displaystyle \underset{i=1}{\overset{n}{\sum }}{e}_i}$ 。

定义13 给定一个四元组区间值系统IVDS： $IVDS=\left(U,AT=C\cup D,V,f\right)$ ，属性集合 $C=\left\{a_1,a_2,\cdots ,a_m\right\}$ ，极小差别集合 $Ms=\left\{s_1,s_2,\cdots ,s_k\right\}$ ， $s_j$ 对应一个行向量 $p_i=\left(p_{i1},p_{i2},\cdots ,p_{im}\right)$ ，该向量表述如下：

$p_{ij}=\{\begin{array}{l}0,a_j\notin s_i\\ 1,a_j\in s_i\end{array}$ (18)

其中 $j\in \left[1,m\right]$ ，易知 $\left|RED\cap s_i\right|={\displaystyle \underset{j=1}{\overset{m}{\sum }}{p}_{ij}{e}_j}$ 。

由定义12和定义13可知优化问题(16)的优化条件 $R\cap s_i\ne \varnothing$ 可以转化为 ${\displaystyle \underset{j=1}{\overset{m}{\sum }}{p}_{ij}{e}_j}\ge 1$ ，因此优化问题

(16)可转化为如下0-1规划：

$\begin{array}{l}\min {\displaystyle \underset{i=1}{\overset{n}{\sum }}{e}_i}\\ \text{s}\text{.t}\text{.}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{p}_{ij}{e}_j}\ge 1,i\in \left[1,k\right].\\ e_j=0或1.\end{array}$ (19)

0-1规划(19)又可以进一步可以变形为矩阵形式。

定义14设 $z={\left(1,1,\cdots ,1\right)}^{\text{T}}$ ， $t={\left(1,1,\cdots ,1\right)}^{\text{T}}$ 是个m维的单位列向量，矩阵 $P=\left[\begin{array}{c}{p}_1\\ p_2\\ ⋮\\ p_l\end{array}\right]$ ，于是0-1规划(19)

的矩阵形式定义如下：

$\begin{array}{l}\min z^{\text{T}}e\\ \text{s}\text{.t}\text{.}pe\ge t\\ e_j=0或1.\end{array}$ (20)

本节针对全部决策类进行属性约简。本文提出了区间值决策系统下基于0-1规划的正域保持最小属性约简算法(Positive region preserving minimum attribute reduction algorithm based on 0-1 programming under interval-valued decision system (MPR-IVDS))如表2所示。

Table 2. Positive region preserving minimum attribute reduction algorithm based on 0-1 programming under interval-valued decision system (MPR-IVDS)

表2. 区间值决策系统下基于0-1规划的正域保持最小属性约简算法

5. 实验分析

本实验选取6个UCI数据集进行约简效率的对比，数据集的详细信息如表3所示。本节主要对经典区间值决策系统下基于差别矩阵的正域约简算法(PRADM)与本文提出的区间值决策系统下基于0-1规划的正域保持最小属性约简算法(MPR-IVDS)约简效率进行对比。本实验在英特尔(R)酷睿(TM)i5-7200UCPU @ 2.50 GHz 2.71 GHz处理器、8.00 GB内存和Windows 10操作系统。算法使用python语言编写，并在开发工具PyCharm上编译和运行。在验证算法有效性之前，使用Weka 3.8.6对数据集合进行离散化，对于缺失数据集，用相应属性下出现频率最高的值填充；对于名词性数据集用数字数据集进行替换；对于条件属性的数据类型采用文献 [20] 所提方法把单值数据转换为区间值数据，阈值 $\alpha =0.3$ 。

Table 3. Dataset Information

表3. 实验使用的数据集

约简效率

图1为经典区间值决策系统下基于差别矩阵的正域约简算法(PRADM)与本文提出的区间值决策系统下基于0-1规划的正域保持最小属性约简算法(MPR-IVDS)按照对象的均匀添加比例变化的时间效率对比柱状图。横坐标表示参与实验的数据比例，纵坐标是约简所消耗的时间单位是秒，蓝色是正域约简算法(PRADM)，橙色表示基于0-1规划的正域保持最小属性约简算法(MPR-IVDS)。从中可以看出随着参与对象比例增加，两个算法的时间消耗也逐渐增加，但是MPR-IVDS消耗时间几乎都要低于PRADM，因此本文提出的MPR-IVDS约简效率更高。

(a) Lymphography (b) Hepatitis

(c) Autism Screening Adult (d) Audit Data (e) Breast Cancer Wisconsin (f) Autistic Spectrum Disorder Screening Data for Children

Figure 1. Comparison of reduction efficiency

图1. 约简效率对比

6. 结论

在本文中，对于寻找最小约简结果的研究中，本文提出了区间值决策系统下基于0-1规划的正域保持最小属性约简算法(MPR-IVDS)，与传统的差别矩阵算法相比本文提出的算法避免了计算最小析取范式，缩短了算法计算时间，提高了算法效率。实验结果表明，本文在区间值决策系统下提出的算法在进行最小属性约简的查询时具有很好的效率。

基金项目

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