Attribute Reduction Based on Relative Dominance Neighborhood Granularity in Interval-valued Decision Tables

本节先给出一些基本定义和相关性质，详细可见文献[16].

区间值决策表指由论域$U$、条件属性集$C$、决策属性集$d$, 以及属性值域$V$组成的四元组$I V D T=\{U$, $A T=C \cup d, V, f\}$, 其中论域$U$是非空有限对象的集合, 条件属性集$C$是有限个条件属性的集合, 决策属性集$d$是有限个决策属性的集合, 且$C \cap d=\varnothing$; 属性值域$V=U_{a \in A T} V_a, V_a$是任意属性$a \in C \cup d$的值域；信息函数$f: U \times C \longrightarrow V_a$满足对于$\forall x_i \in U$, 属性$a$上的值$f\left(x_i, a\right) \in V_a$是一个区间值, 决策属性值仍为单值.

设区间值决策表$I V D T=\{U, A T=C \cup d, V, f\}$，且属性子集$B \subseteq C$，阈值$\alpha \in[0, 1]$, 则关于$B$的相邻关系定义为

式中

这里

且

对于区间值决策表IVDT={U，AT=C∪d，V，f}，基于相邻关系基础的相邻类为

可知决策表IVDT所有的相邻类构成一个对应于每一个元素的|U|维粒化结构

进一步，区间值决策表IVDT={U，AT=C∪d，V，f}对任意一个条件属性子集$B \subseteq C $，0≤α₁≤α₂≤1有

1) $\forall x_i \in U, N C_C^{\alpha_1}\left(x_i\right) \subseteq N C_B^{\alpha_1}\left(x_i\right) $

2) $\forall x_i \in U, N C_B^{\alpha_1}\left(x_i\right) \subseteq N C_B^{\alpha_2}\left(x_i\right) $

由于相对优势邻域粒度可以很直观地体现条件邻域粒化对决策属性划分的分辨力，故可借助相邻关系导出粒化结构研究区间值决策表的属性约简方法.

虽然经典相对优势邻域粒度能够体现优势邻域的粗细程度，但却不适用于区间值决策表. 为此，本节给出了基于区间相对优势粒度的启发式约简算法.

首先，区间值决策表的区间相对优势邻域粒度定义如下.

定义1  设$I V D T=\{U, A T=C \cup d, V, f\}$为一个区间值决策表，对于任意一个条件属性子集$B \subseteq$ $C$及阈值$\alpha \in[0, 1]$, 则$B$相对于$d$的区间相对优势邻域粒度为

式中$D_h$为决策属性的决策类, 且$\sum\limits_{i=1}^{|U|}\left(\frac{\left|N C_B^\alpha\left(x_i\right)\right|}{|U|}\right)^2=A N(\alpha ; B)$, 及$\sum\limits_{i, h=1}^{|U|, m}\left(\frac{\left|N C_B^\alpha\left(x_i\right) \cap D_h\right|}{|U|}\right)^2=$ $A N(\alpha ; B \cup d)$.

性质1  设IVDT={U，AT=C∪d，V，f}为一个区间值决策表，对于任意一个条件属性子集B$\subseteq $C及阈值α∈[0, 1]，则有

证  由于

因此对于$\forall i \in[1, |U|] $，可以得出

于是，性质1成立.

引理1  设$f\left(g_1, g_2, \cdots, g_{m-1}, g_m\right)=\left(\sum\limits_{s=1}^m g_s\right)^2-\sum\limits_{s=1}^m g_s^2$, 其中$g_s(1 \leqslant s \leqslant m)$为函数自变量, 则有

1) $f\left(g_1, g_2, \cdots, g_{m-1}, g_m\right)=2\left(g_1 g_2+g_1 g_3+\cdots+g_{m-1} g_m\right)$;

2) 若$0 \leqslant g_1 \leqslant t_1, \cdots, 0 \leqslant g_m \leqslant t_m $, 则$f\left(g_1, g_2, \cdots, g_m\right) \leqslant f\left(t_1, t_2, \cdots, t_m\right)$.

证  1)很显然成立. 接下来证明2). 由于

当且仅当t₁=g₁，t₂=g₂，⋯，t_m=g_m时等号成立. 证毕.

性质2  设$I V D T=\{U, C \cup d, V, f\}$是一个区间值决策表, 对于任意两个条件属性子集$A, B \subseteq C$以及阈值$\alpha \in[0, 1]$, 则以下结论成立:

1) 若$A \subseteq B$, 则$R N(\alpha ; B ； d) \leqslant R N(\alpha ; A ； d)$;

2) 若$0 \leqslant \alpha_1 \leqslant \alpha_2 \leqslant 1$, 则$R N\left(\alpha_1 ; B ; d\right) \leqslant R N\left(\alpha_2 ; B ; d\right)$.

证  1) 令

可知关于B和A的区间相对优势邻域粒度可以化简为

又因$ A \subseteq B $, 可知$\forall x_i \in U$满足$N C_B^a\left(x_i\right) \subseteq N C_A^a\left(x_i\right)$, 于是

即0≤B_hⁱ≤A_hⁱ.

根据引理1可得

所以

2) 令

则关于α₁，α₂的区间相对优势邻域粒度可以简化为

又因为0≤α₁≤α₂≤1，则

所以

即0≤B_h^α₁≤B_h^α₂.

再由引理1可得

所以有

故

性质3  设$I V D T=\{U, C \cup d, V, f\}$为一个区间值决策表, 对于任意一个条件属性子集$B \subseteq C$及阈值$\alpha \in[0, 1]$, 有$R N(\alpha ; B ; d) \in[0, |U|-1]$.

特别地, 当粒化结构$N_B^\alpha$最细时, 即$\forall x_i \in U, N C_B^\alpha\left(x_i\right)=\left\{x_i\right\}$, 此时$R N(\alpha ; B ; d)=0$; 当粒化结构$N_B^\alpha$最粗时, 即$\forall x_i \in U, N C_B^a\left(x_i\right)=\{U\}$, 此时$R N(\alpha ; B ; d)=|U|-1$.

由性质2和性质3可以进一步有属性的必要性和独立性的定义. 下文中均设阈值$\alpha \in[0, 1]$.

定义2  设$I V D T=\{U, C \cup d, V, f\}$是一个区间值决策表, 对于$\forall a \in C$, 若$R N(\alpha ; C-a ; d)=$ $R N(\alpha ; C ; d)$, 则称$a$是$C$中的不必要属性，否则称$a$是必要属性.

定义3  设$I V D T=\{U, C \cup d, V, f\}$是一个区间值决策表, 由$C$中所有关于决策属性$d$的必要属性组成的集合, 称为属性集合$C$相对于决策属性$d$的核, 记为$Core_C^\alpha(d)$.

任意一个条件属性子集$B \subseteq C$, 若$B$中任意一个条件属性在$B$中相对于决策属性$d$都必要, 则称$B$是$C$的一个相对于决策属性$d$的属性约简, 且易证$Cor_C^\alpha(d)$恰好是全部属性约简的交集.

定义4  设$I V D T=\{U, C \cup d, V, f\}$是一个区间值决策表, $B \subseteq C$, 则$B$是$C$的一个相对于决策属性$d$的属性约简, 当且仅当

1) $R N(\alpha ; B ; d)=R N(\alpha ; C ; d)$

2) $\forall a \in B, R N(\alpha ; B ; d) \neq R N(\alpha ; B-\{a\} ; d)$

属性约简的核心主要来源于相对优势邻域粒度.

定义5  对于区间值决策表$I V D T=\{U, C \cup d, V, f\}$, 若$\forall a \in C$, 则条件属性$a$关于属性集$C$相对于决策属性$d$的属性内重要度为

另外, 对于$\forall B \in C$以及$\forall a \in C-B, a$关于$B$相对于决策属性$d$的区间属性外重要度为

由定义5可知，区间属性内外重要度变化越大说明该属性对于决策的影响越大. 因此区间属性内重要度与区间属性外重要度两者提供了快速实现约简的属性选择原理.

性质4  对于区间值决策表$I V D T=\{U, C \cup d, V, f\}$, 若$\forall a \in C$, 则条件属性$a$为$C$中对$d$必要的属性当且仅当$S i g^{\text {inner }}(\alpha ; a ; C ; d)>0$, 即

证  若$a$为$C$中对$d$必要的属性, 则$R N(\alpha ; C ; d) \neq R N(\alpha ; C-\{a\} ; d)$, 再根据区间相对优势邻域粒度的粒化单调性可知, $R N(\alpha ; C ; d) \leqslant R N(\alpha ; C-\{a\} ; d)$, 所以$Sig^{\mathrm{inner}}(\alpha ; a ; C ; d)>0$. 反之, 若$Sig^{\text {inner }}(\alpha ; a ; C ; d)>0$, 则$R N(\alpha ; C ; d) \leqslant R N(\alpha ; C-\{a\} ; d)$, 那么$R N(\alpha ; C ; d) \neq R N(\alpha$; $C-\{a\} ; d)$. 再根据定义2可知, $a$为$C$中对$d$必要的属性, 于是性质成立.

下面给出相对优势邻域粒度属性约简的启发式算法.

算法1  基于区间值相对优势邻域粒度的属性约简算法

输入  区间值决策表IVDT及阈值α

输出  决策表IVDT的一个属性约简S

step1  计算C相对于d的区间相对优势邻域粒度RN(α；C；d)；

step2  设$Core_C^\alpha(d)=\varnothing, \forall a \in C$, 计算$Sig^{\text {inner }}(\alpha ; a ; C ; d)$, 若$Sig^{\text {inner }}(\alpha ; a ; C ; d)>0$, $Core_C^\alpha(d)=Core_C^\alpha(d) \cup\{a\}$, 并令$S=Core_C^\alpha(d)$;

step3  判断$R N(\alpha ; S ; d)=R N(\alpha ; C ; d)$是否成立, 若成立则goto step5, 否则goto step4;

step4  进人step4, 则说明$\forall a \in\{C-S\}, R N(\alpha ; C ; d) \leqslant R N(\alpha ; S ; d)$, 计算$Sig^{\text {outer }}(\alpha ; a ; S$; $d)$, 将$\max \left(Sig^{\text {outer }}\left(\alpha ; a^* ; S ; d\right)\right)$对应属性$a^*$并到$S$中, 重复该步骤过程直到满足$N(\alpha ; S ; d)=$ $R N(\alpha ; C ; d)$, 转到step 5;

step5   输出S

算法1的时间复杂度分析如下：

step1   计算RN(α；C；d)的时间复杂度为

step2   对于$\forall a \in C$, 计算$Sig^{\text {inner }}(\alpha ; a ; C ; d)$的时间复杂度为

step3   计算$R N(\alpha ; S ； d)$的时间复杂度为

step4   将属性$a^*$添加到属性约简集合中, 对$\forall a \in\{C-S\}$, 计算$Si g^{\text {outer }}(\alpha ; a ; S ; d)$, 时间复杂度为

最复杂情况下，step4的复杂度为

从而此式的复杂度不超过

所以算法1的时间复杂度为

由算法1可知，条件属性子集基数越大，相对优势邻域粒度越小.

基于正域的属性约简是粗糙集理论中常用的方法之一，用于在决策信息系统中降低数据维度并提高决策效率. 该方法通过寻求能够唯一确定决策属性值的最小条件属性子集(即正域)，并删除冗余属性，构建简化后的数据集. 基于正域的属性约简方法在保持决策精度的同时减少了数据冗余，提高了决策过程的效率，为处理大规模、高维度的数据提供了有效的工具和技术.

接下来将证明在区间值决策表中，区间相对优势邻域粒度的属性约简与代数约简是等价的.

定义6  设有区间值决策表$I V D T=\{U, C \cup d, V, f\} $，若对于该决策表的$\forall N C_C^\alpha\left(x_i\right) \in N_C^\alpha, \exists D_h \in$ $\left(\frac{U}{d}\right)$，有$N C_C^\alpha\left(x_i\right) \subseteq D_h$，则称该决策表为协调区间值决策表，否则为不协调的.

性质5  区间值决策表$I V D T=\{U, C \cup d, V, f\}$是协调的, 当且仅当$R N(\alpha ; C ; d)=0$.

证   “$\Rightarrow$”由于$I V D T$是协调区间值决策表, 所以

有

又因为

故$ \forall i \in[1, |U|]$.

另外,

故可得

“$\Leftarrow$”若$R N(\alpha ; C ; d)=0$, 则由

可知

又由

可得

也即

于是有

因此有

于是$N C_C^\alpha\left(x_i\right) \subseteq D_h$.

故IVDT是协调区间值决策表.

性质6  设$I V D T=\{U, C \cup d, V, f\} $是一个协调区间值决策表, 若$B \subseteq C$, 则

式中pos_B^α(D)，pos_C^α(D)分别指决策类D关于条件属性集B，C的正域.

证  先证充分性. 因为IVDT是协调区间值决策表，可知pos_C^α(D)=U；由性质6可知RN(α；C；d)=0，因为RN(α；B；d)=RN(α；C；d)，所以RN(α；B；d)=0.

由

可得

又由

得到

因此

再证必要性. 因为IVDT是协调区间值决策表，所以pos_C^α(D)=U，由性质6知

由

可得

因此

即

所以

因此

区间决策表IVDT如表 1所示^[8]，其中U={x₁，x₂，x₃，x₄，x₅，x₆，x₇，x₈，x₉，x₁₀}代表 10个对象，C={a₁，a₂，a₃，a₄}为条件属性集，d为决策属性集. 文献[8]计算表明当阈值α=0.65时该区间值决策表的属性约简为S₁={a₁，a₂}和S₂={a₂，a₃}.

设阈值α=0.65，计算可知条件属性子集增链为

阈值增链为

对条件属性子集增链和阈值增链分别计算区间相对优势邻域粒度.

对条件属性子集增链有

对于阈值增链有

故区间相对优势粒度满足属性和阈值的双重粒化单调性，即性质3成立. 同时，计算结果都满足双界范围：[0，|U|-1]，即性质4成立.

当α=0.65时，由算法1可计算出该决策表的一个属性约简.

1) 计算相对优势邻域粒度RN(0.65；C；d)=0.34.

2) 设$Core_C^\alpha(d)=\emptyset $，计算区间属性内重要度

选择区间属性内重要度大于零的属性并入到核心Core_C^0.65(d)中，即Core_C^0.65(d)={a₂}，实现对S的更新.

3) 计算S关于d的区间相对优势邻域粒度RN(0.65；S；d)=0.84＞RN(0.65；C；d)=0.34.

4) a∈{C-S}计算区间属性外重要度

选择区间属性外重要度最大的条件属性a^*并入到S中，实现对核心S的更新. 又因为属性a₁与属性a₃的外重要度都为0.50. 为保证一般性，对属性a₁与属性a₃都进行验证，可得

5) 输出S₁={a₁，a₂}或S₂={a₂，a₃}.

即S₁={a₁，a₂}和S₂={a₂，a₃}为该区间值决策表的两个属性约简，这与文献[8]基于正域属性约简的结果相同.

本文给出了区间相对优势邻域粒度等概念，在此基础上构建出相应的启发式约简算法，并证明了在协调区间值决策表上，区间相对优势邻域粒度表示与代数表示是等价的. 同时，结合具体实例分析验证了区间相对优势邻域粒度及属性约简算法的合理性. 本文研究结果可应用于环境监测数据的属性约简，从而进一步选出对环境质量评估和污染防治具有关键影响的属性. 然而，由于现实生活中的决策信息系统可能存在不协调或不完备的情况，将来可进一步研究不协调或不完备区间决策信息系统下的属性约简. 同时，目前区间值决策表中基于相对优势邻域粒度的属性约简中阈值并未解释选取标准，这也是该领域未来需要研究的工作.