属性约简^[1-7]是粗糙集理论^[1-3]的核心研究内容之一，在数据挖掘、机器学习、决策分析、智能信息处理等领域取得了诸多研究成果。属性约简的目的是删除冗余属性，只保留使决策表某种分类特征不变的最小属性子集。差别矩阵方法是一种用于求取所有属性约简的有效方法，该方法由Skowron^[8]于1982年提出，并将差别矩阵应用于正域约简中。诸多学者在此基础上做了大量的研究工作。Kryszkiewicz^[9]于1999年在不完备信息系统下引入广义决策保持约简的概念，并提出基于差别矩阵的广义决策保持约简方法；2007年，邓大勇等^[10]首先分析了不相容信息系统下几种约简目标之间的关系；2009年，Miao等^[11]进一步分析了3种约简目标之间的关系，提出不可分辨关系保持约简以及相应的差别矩阵构造方法；Zhou等^[12]在2011年对现有的13种属性约简目标进行总结，并将所有约简目标分为4类，完善了现有约简目标之间的关系。

分布约简保持了信息系统约简前后每条规则置信度不变。2003年，张文修等^[13]提出了分配约简、分布约简以及最大分布约简的概念，并分别给出了基于差别矩阵的分配约简、分布约简以及最大分布约简方法；2007年，徐伟华等^[14]在优势关系下提出了两种约简概念，即分布约简和最大分布约简，同时建立了基于差别矩阵的分布和最大分布约简的具体方法。如某一段时间内的温度、湿度等区间值数据在现实环境中大量存在，它较好地表示了许多不确定类型数据，区间值决策系统是经典Pawlak决策系统的推广，充分地考虑了数据的不确定性，在近几年得到了广泛关注。2009年，张楠等^[15]定义了 $\alpha $ -极大相容类的概念，提出了区间值决策系统的广义决策保持约简；2016年，张楠等^[16]在不协调区间值决策系统中提出确定性规则保持约简；2016年，张楠等^[17]讨论了不协调区间值决策系统中的知识约简并提出了分布约简的概念。

基于上述研究，文献[13]和[14]分别对等价关系和优势关系下的最大分布约简进行了研究，但未有区间值决策系统的最大分布约简讨论。置信度表示了信息系统中规则的可信程度，置信度越大，规则的可信程度越高；置信度越小，规则的可信程度越低，在实际应用中，人们往往关注置信度最大的规则。为此，本文提出了区间值决策系统的最大分布约简概念，为区间值决策系统提供了一种求取所有属性约简的新方法。

1 基本知识 1.1 区间值决策系统的粗糙近似

基于相容关系的区间值粗糙集模型是经典Pawlak粗糙集模型的推广，首先给出相关概念和性质。

给定区间值信息系统^[15-18] ${\rm{IS}} = (U,{\rm{AT}},V,f)$ ，其中， $U$ 是有限对象集合， $U = \{ {x_1},{x_2}, \cdots, {x_{|U|}}\} $ ； ${\rm{AT}}$ 是有限属性集合， ${\rm{AT}} = \{ {a_1},{a_2}, \cdots, {a_{{\rm{|AT|}}}}\} $ ； $V$ 是全体属性的值域，即 $V \!=\! \mathop \cup \limits_{{a_k} \in {\rm{AT}}} {V_{{a_k}}}$ ， ${V_{{a_k}}}$ 是属性 ${a_k} \in {\rm{AT}}$ 的值域； $f\!:\!U \! \times \! {\rm{AT}} \to $ V是一个信息函数，它指定论域 $U$ 中每一个对象 ${x_i}$ 在属性a_k上的区间属性值，即对任意的 ${x_i} \in U$ ， ${a_k} \in {\rm{AT}}$ ，有 $f({x_i},{a_k}) = {a_k}({x_i}) = $ $[l_i^k,u_i^k]$ 。

如果属性集 ${\rm{AT}}$ 由条件属性集C和决策属性集 $D$ 组成， $C = \{ {a_1},{a_2}, \cdots {a_{|C|}}\} $ ， $D = \{ d\} $ ，即 $C \cup D$ $ = {\rm{AT}}$ ；V = ${V_C} \cup {V_D}$ ，其中， ${V_C}$ 为条件属性值集合， ${V_D}$ 为决策属性值集合； $f:U \times C \to {V_C}$ 为区间值映射， $f:U \times D \to {V_D}$ 为单值映射，则称区间值信息系统为区间值决策系统 ${\rm{DS}} = (U,C \cup D,V,f)$ 。

定义1　设 ${\eta _1}{\rm{ = }}[l_i^k,u_i^k]$ 和 ${\eta _2}{\rm{ = }}[l_j^k,u_j^k]$ 为任意两个区间值，则区间值的交运算与并运算如下。

1)区间值交运算为

${\eta _1} \cap {\eta _2} = \left\{ {\begin{array}{*{20}{l}}{0, \quad (u_i^k < l_j^k) \vee (u_j^k < l_i^k)\;\;}\\{[{\rm{max}}(l_i^k,l_j^k),{\rm{min}}(u_i^k,u_j^k)], \quad \text{其他}}\end{array}} \right.$

2)区间值并运算为

${\eta _1} \cup {\eta _2} = [{\rm{min}}(l_i^k,l_j^k),{\rm{max}}(u_i^k,u_j^k)]\;$

目前，度量区间值相似度比较合理的主要方法有Jaccard相似率、悲观相似率和乐观相似率，本文统一采用Jaccard相似率来度量两个区间值的相似度。

定义2　 ${\rm{DS}} = (U,C \cup D,V,f)$ 为区间值决策系统，对任意的 ${x_i},{x_j} \in U$ ， ${a_k} \in {\rm{C}}$ ，区间值 ${a_k}({x_i})$ $ = [l_i^k,u_i^k]$ 和 ${a_k}({x_j}) = [l_j^k,u_j^k]$ 的Jaccard相似率^[18] $\alpha _{ij}^k$ 定义为

$\alpha _{ij}^k{\rm{ = }}\frac{{{\rm{|}}[l_i^k,u_i^k] \cap [l_j^k,u_j^k]{\rm{|}}}}{{{\rm{|}}[l_i^k,u_i^k] \cup [l_j^k,u_j^k]{\rm{|}}}}$

Jaccard相似率为两个区间数的交集与并集长度的比值，它适合度量长度相似的两个区间数。

例1　区间值决策系统 ${\rm{DS}} = (U,C \cup D,V,f)$ ，如表1所示，其中， $U = \{ {x_1},{x_2}, \cdots ,{x_6}\} $ 为对象的集合，C = $ \{ {a_1},{a_2},{a_3},{a_4}\} $ 为条件属性的集合， $D = $ $\{ d\} $ 为决策属性。

令 ${\eta _1} = [l_1^1,u_1^1]$ ， ${\eta _1} = [l_2^1,u_2^1]$ ，分别计算 ${\eta _1}$ 和 ${\eta _2}$ 的交、并：

${\eta _1} \cap {\eta _2} = [0.86,3.13] \cap [{\rm{ - }}0.12,2.13] = {\rm{[0}}{\rm{.86,2}}{\rm{.13]}}$

${\eta _1} \cup {\eta _2} = [0.86,3.13] \cup [{\rm{ - }}0.12,2.13] = [{\rm{ - }}0.12,3.13{\rm{]}}$

计算 ${\eta _1}$ 和 ${\eta _2}$ 的Jaccard相似率：

$\alpha _{12}^1 = \frac{{|[l_1^1,u_1^1] \cap [l_2^1,u_2^1]|}}{{|[l_1^1,u_1^1] \cup [l_2^1,u_2^1]|}} = 0.391$

定义3^[15] 　对于区间值决策系统 ${\rm{DS}} = (U,C \cup $ $D,V,f)$ ， ${a_k} \in C$ ， $\alpha \in [0,1]$ ，则关于条件属性 ${a_k}$ 的 $\alpha $ -相容关系定义为

${T}_{\{ {a_k}\} }^\alpha = \{ ({x_i},{x_j})|({x_i},{x_j}) \in U \times U,\alpha _{ij}^k > \alpha \} $

其中 $\alpha _{ij}^k$ 表示对象x_i和对象x_j关于属性 ${a_k}$ 的 $\alpha $ -Jaccard相似度，简称 $\alpha $ -相似度。

关于条件属性子集 $A \subseteq U$ 的 $\alpha $ -相容关系定义为

${T}_A^\alpha = \{ ({x_i},{x_j})|({x_i},{x_j}) \in U \times U,\alpha _{ij}^k > \alpha ,{a_k} \in A\} $

性质1^[15] 　对于区间值决策系统 ${\rm{DS}} = (U,C \cup $ $D,V,f)$ ， $A \subseteq C$ ， ${a_k} \in A$ ， $\alpha \in [0,1]$ ， ${T}_{\{ {a_{k\} }}}^\alpha $ 是属性 ${a_k}$ 的 $\alpha $ -相容关系，则关于集合 $A$ 的相容关系为

${T}_A^\alpha = \mathop \cap \limits_{{a_k} \in A} {T}_{\{ {a_{k\} }}}^\alpha $

性质2^[18] 　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ，则 ${T}_A^\alpha $ 具有：

1)自反性：任意x_i∈U，则 $({x_i},{x_j}) \in {T}_A^\alpha $ 。

2)对称性：任意x_i，x_j∈U，若 $({x_i},{x_j}) \in {T}_A^\alpha $ ，则 $({x_j},{x_i}) \in {T}_A^\alpha $ 。

3)非传递性：任意 ${x_i},{x_j},{x_k} \in U$ ，若满足 $({x_i},{x_k}) \in $ $ {T}_A^\alpha $ 和 $({x_k},{x_j}) \in {T}_A^\alpha $ ，则 $({x_i},{x_j}) \in {T}_A^\alpha $ 不一定成立。

定义4^[18] 　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ， $\alpha \in [0,1]$ ， ${T}_A^\alpha $ 是属性集A的α-相容关系，则关于对象x_i在属性集A下的 $\alpha $ -相容类定义为

$S_A^\alpha ({x_i}) = \{ {x_j}|{x_j} \in U,({x_i},\,{x_j}) \in {T}_A^\alpha \} $

对任意 ${x_i} \in U$ ，区间值决策系统 ${\rm{DS}}$ 在阈值 $\alpha $ 下的相容类集合定义为

$S_A^\alpha (U) = \{ S_A^\alpha ({x_1}),S_A^\alpha ({x_2}), \cdots ,S_A^\alpha ({x_n})\} $

其中 $n$ 是论域的个数。

经典粗糙集中对象间的二元关系为等价关系，具有自反性、传递性、对称性，导出的等价类集合是对论域的划分，而定义4中的相容类是对论域的覆盖。

定义5　给定区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $S_A^\alpha ({x_i})$ 是在相容关系下包含 ${x_i}$ 的相容类，则对象集合 $X$ 关于 $\alpha $ -相容关系的上、下近似^[19]分别定义为

$\overline {{\rm{apr}}_A^\alpha } (X) = \{ {x_i}|{x_i} \in U,S_A^\alpha ({x_i}) \cap X \ne \text{Ø} \} $

$\underline {{\rm{apr}}_A^\alpha } (X) = \{ {x_i}|{x_i} \in U,S_A^\alpha ({x_i}) \subseteq X\} $

集合 $X$ 关于 $\alpha $ -相容关系的正域为

${\rm{POS}}_A^\alpha (X) = \underline {{\rm{apr}}_A^\alpha } (X)$

下近似是由肯定属于 $X$ 的对象组成的集合，上近似是由可能属于 $X$ 的对象组成的集合，根据上下近似的概念，决策规则可以分为确定性规则和可能性规则。

定义6^[16] 　给定区间值决策系统 ${\rm{DS}} \!=\! (U,C \cup $ $D,V,f)$ ， $X \! \subseteq \! U$ ， $A \! \subseteq \! C$ ，则条件属性集 $A$ 的近似分类精度定义为

$\mu _A^\alpha (X) = \frac{{|\underline {{\rm{apr}}_A^\alpha } (X)|}}{{|\overline {{\rm{apr}}_A^\alpha } (X)|}}$

近似分类精度表示确定性规则占可能性规则的比例，近似分类精度越大，区间值信息系统中确定性规则越多；反之，确定性规则越少。

定义7^[16] 　对于区间值决策系统 ${\rm{DS}} = (U,C \cup $ $D,V,$ f)， $A \subseteq C$ ，决策属性D对 $U$ 的划分为U/D = $ {\rm{\{ }}{D_1},{D_2}, \cdots ,{D_{|U/D|}}{\rm{\} }}$ ，决策属性D关于 $\alpha $ -相容关系的上、下近似分别定义为

$\overline {{\rm{apr}}_A^\alpha } (D) = \{ {x_i}|{x_i} \in U,{D_j} \in U/D,S_A^\alpha ({x_i}) \cap {D_j} \ne \text{Ø} \} $

$\underline {{\rm{apr}}_A^\alpha } (D) = \{ {x_i}|{x_i} \in U,{D_j} \in U/D,S_A^\alpha ({x_i}) \subseteq {D_j}\} $

决策属性D关于 $\alpha $ -相容关系的正域定义为

${\rm{POS}}_A^\alpha (D) = \overline {{\rm{apr}}_A^\alpha } (D)$

定义8^[16] 　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ，决策属性D对 $U$ 的划分为 $U/D = {\rm{\{ }}{D_1},$ ${D_2}, \cdots ,{D_{|U/D|}}{\rm{\} }}$ ，则在决策属性D下，关于条件属性集A的近似分类精度定为

$\mu _A^\alpha (D) = \frac{{|\underline {{\rm{apr}}_A^\alpha } (D)|}}{{|\overline {{\rm{apr}}_A^\alpha } (D)|}}$

定义5和定义6是关于集合 $X$ 的上、下近似和近似分类精度，而定义7和定义8是关于决策属性 $D$ 的上、下近似和近似分类精度。

定义9^[13] 　对于区间值决策系统 ${\rm{DS}} \!=\! (U,C \cup $ $D,V,f)$ ，对任意 ${x_i},{x_j} \in U$ ，且 $i \ne j$ ，若x_i和 ${x_j}$ 具有 $\alpha $ -相容关系，且满足 $d({x_i}) = d({x_j})$ ，则称 ${x_i} \in U$ 是关于属性集 $A \subseteq C$ 的 $\alpha $ -协调对象；否则称为 $\alpha $ -不协调对象。

若存在一个对象 ${x_i} \in U$ 是关于 $A \subseteq C$ 的 $\alpha $ -不协调对象，那么称 ${\rm{DS}}$ 为不协调区间值决策表，否则称为协调区间值决策表。

例2　如表1所示的区间值决策系统，令 $\alpha = 0.6$ ，则相容关系 ${{T}}_C^{0.6}$ 为

${{T}}_C^{0.6}{\rm{ = }}\left[ {\begin{array}{*{20}{c}} 1&0&0&0&0&0 \\ 0&1&0&0&0&0 \\ 0&0&1&0&1&1 \\ 0&0&0&1&0&0 \\ 0&0&1&0&1&1 \\ 0&0&1&0&1&1 \end{array}} \right]$

根据相似率布尔矩阵，计算阈值 $\alpha = 0.6$ 下的相容类集合为

$S_C^{0.6}(U) = \{ S_C^{0.6}({x_1}),S_C^{0.6}({x_2}), \cdots ,S_C^{0.6}({x_6})\} $

式中： $S_C^{0.6}({x_1}) = \{ {x_1}\} $ ， $S_C^{0.6}({x_2}) = \{ {x_2}\} $ ， $S_C^{0.6}({x_3}) = S_C^{0.6}({x_5}) = $ $ S_C^{0.6}({x_6}) = \{ {x_3},{x_5},{x_6}\} $ ， $S_C^{0.6}({x_4}) = \{ {x_4}\} $ 。

$U/D = \left\{ {\left\{ {{x_1},{x_5},{x_6}} \right\},\left\{ {{x_2},{x_3},{x_4}} \right\}} \right\}$ 为决策属性D对U的划分，计算决策属性D关于相容关系 ${{T}}_C^{0.6}$ 的上、下近似：

$\overline {{\rm{apr}}_C^{0.6}} (D) = U$ ， $\underline {{\rm{apr}}_C^{0.6}} (D) = \{ {x_1},{x_2},{x_4}\} $

计算条件属性集C的近似分类精度：

$\mu _C^{0.6}(D) = \frac{{|\underline {{\rm{apr}}_C^\alpha } (D)|}}{{|\overline {{\rm{apr}}_C^\alpha } (D)|}} = \frac{3}{6} = 0.5$

1.2 区间值决策系统的分布约简

文献[16]提出不协调区间决策系统的分布约简。

定义10　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq U$ ， $U/D = {\rm{\{ }}{D_1},{D_2}, \cdots ,{D_{|U/D|}}{\rm{\} }}$ ，则x_i∈U对应的概率分布定义为

$\begin{array}{c}\mu _A^\alpha ({x_i}) = (D({D_1}/S_A^\alpha ({x_i})),D({D_2}/S_A^\alpha ({x_i})), \cdots ,\\D({D_j}/S_A^\alpha ({x_i}), \cdots ,D({D_{|U|}}/S_A^\alpha ({x_i})))\end{array}$

式中 $D({D_j}/S_A^\alpha ({x_i})) = \displaystyle\frac{{|{D_j} \cap S_A^\alpha ({x_i})|}}{{|S_A^\alpha ({x_i})|}}$ ， $j \leqslant |U/D|$ 。

定义11　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $U = \{ {x_1},{x_2}, \cdots ,{x_{|U|}}\} $ ，则对任意 $1 \leqslant i,j \leqslant |U|$ ：

${\rm{DM}}_D^\alpha (i,j) = \left\{ {\begin{array}{*{20}{l}} {\{ {a_k}|{a_k} \in C \wedge \alpha _{ij}^k < \alpha \} ,\quad \mu _A^\alpha ({x_i}) \ne \mu _A^\alpha ({x_j})} \\ { \text{Ø} ,\quad \mu _A^\alpha ({x_i}) = \mu _A^\alpha ({x_j})} \end{array}} \right.$

式中： ${\rm{DM}}_D^\alpha (i,j)$ 为基于 $\alpha $ -相容类的分布约简可辨识矩阵 ${\bf{DM}}_D^\alpha $ 第 $i$ 行 $j$ 列的元素， ${\bf{DM}}_D^\alpha $ 简称为分布可辨识矩阵，其中 $i,j = 1,2, \cdots ,|U|$ ，Ø表示空集。

定义12　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $C = \{ {a_1},{a_2}, \cdots ,{a_{|C|}}\} $ ， ${\rm{DM}}_D^\alpha (i,j)$ 表示可辨识矩阵中第i行j列的元素，基于 $\alpha $ -相容类的分布可辨识函数定义为与 ${a_1},{a_2}, \cdots ,{a_{|C|}}$ 相对应的 $|C|$ 个布尔变量 ${\bar a_1},{\bar a_2}, \cdots ,$ ${\bar a_{|C|}}$ 的布尔函数为

$f_D^\alpha (C)({\bar a_1},{\bar a_2}, \cdots ,{\bar a_{|C|}}) = \wedge \{ \vee {\rm{DM}}_D^\alpha (i,j):{\rm{DM}}_D^\alpha (i,j) \ne \text{Ø} \} $

此函数简称分布可辨识函数。这里的 $ \vee {\rm{DM}}_D^\alpha (i,j)$ 表示满足 $a \in {\rm{DM}}_D^\alpha (i,j)$ 的全体布尔变量 $\bar a$ 的析取式。

利用分配率和吸收率将 $f_D^\alpha \left( C \right)$ 转化为 $h_D^\alpha (C)$ $({\bar a_1},{\bar a_2}, \cdots ,{\bar a_m}) = ( \wedge {\theta _1}) \vee \cdots \vee (\wedge {\theta _l}),{\theta _k} \subseteq C,k = 1,2, \cdots ,l$ ， ${\theta _k}$ 中每一个属性元素只出现一次。

定理1　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $h_D^\alpha (C)$ 是分布可辨识函数 $f_D^\alpha (C)$ 的形式转化，若 $A \subseteq C$ 是分布约简，当且仅当A是 $h_D^\alpha (C)$ 的一个蕴含项。

基于可辨识矩阵的分布约简算法(distribution reduction algorithm based on discernibility matrix，DRADM)描述如下。

算法1　DRADM

输入　区间值决策系统 ${\rm{DS}}$ ，阈值α。

输出　区间值决策系统的所有分布保持约简结果。

1)计算区间值决策系统 ${\rm{DS}}$ 的在阈值 $\alpha $ 下的相容类集合 $S_C^\alpha (U)$ ；

2)根据每个对象对应的相容类，计算每个对象相对于每一个决策类的概率分布 $\mu _C^\alpha ({x_i})$ ；

3)根据每个对象的可信度不同构造分布约简可辨识矩阵 ${\bf{DM}}_D^\alpha $ ；

4)由可辨识矩阵 ${\bf{DM}}_D^\alpha $ 计算分布约简可辨识函数 $f_D^\alpha \left( C \right)$ ；

5)利用分配率和吸收率将 $f_D^\alpha (C)$ 转化为 $h_D^\alpha (C)$ ， $h_D^\alpha (C)$ 中每一个蕴含项为一个分布保持的约简。

例3　如表1所示的区间值决策系统，令 $\alpha = 0.6$ ，根据例2可知相似布尔矩阵以及相容类集合。

计算每个对象对应的概率分布：

$\mu _C^{0.6}({x_1}) = \{ 1,0\} $ ， $\mu _C^{0.6}({x_2}) = \{ 0,1\} $ ，　　 $\mu _C^{0.6}({x_3}) = \{ 2/3,1/3\} $ ， $\mu _C^{0.6}({x_4}) = \{ 0,1\} $ ，　　 $\mu _C^{0.6}({x_5}) = \{ 2/3,1/3\} $ ， $\mu _C^{0.6}({x_6}) = \{ 2/3,1/3\} $ 。

计算分布保持约简可辨识矩阵：

${{\bf{DM}}}_D^{0.6}(6,6) = \left[ {\begin{array}{*{20}{c}} \text{Ø} &{}&{}&{}&{}&{} \\ {{a_1},{a_2},{a_3},{a_4}}&\text{Ø} &{}&{}&{}&{} \\ {{a_1},{a_2}}&{{a_3},{a_4}}&\text{Ø} &{}&{}&{} \\ {{a_1},{a_2},{a_3}}&\text{Ø} &{{a_3}}&\text{Ø} &{}&{} \\ {{a_1},{a_2}}&{{a_3},{a_4}}&\text{Ø} &{{a_3}}&\text{Ø} &{} \\ {{a_1},{a_2}}&{{a_3},{a_4}}&\text{Ø} &{{a_3}}&\text{Ø} &\text{Ø} \end{array}} \right]$

计算分布约简可辨识函数：

$f_D^{0.6}(C)({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_3} \wedge ({a_2} \vee {a_1})$

转化后的分布约简可辨识函数为

$h_D^{0.6}(C)({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = ({a_1} \wedge {a_3}) \vee ({a_2} \wedge {a_3})$

因此分布保持约简为 $\{ {a_1},{a_3}\} $ 和 $\{ {a_2},{a_3}\} $ 。

2 区间值决策系统的最大分布约简

本节在区间值决策系统中引入最大规则置信度的概念，提出了不协调区间值决策系统的最大分布约简算法。

定义13　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ， $U/D = {\rm{\{ }}{D_1},{D_2}, \cdots ,{D_{|U/D|}}{\rm{\} }}$ ，则 ${x_i} \in U$ 对应的最大概率分布定义为

$m_A^\alpha ({x_i}) = D({D_{{j_0}}}/S_A^\alpha ({x_i}))= \mathop {{\rm{max}}}\limits_{j \leqslant q} D({D_j}/S_A^\alpha ({x_i})) $

${x_i} \in U$ 对应的最大分布为

$\gamma _A^\alpha ({x_i}) = \{ {D_j}|D({D_j}/S_A^\alpha ({x_i})) = D({D_{{j_0}}}/S_A^\alpha ({x_i})\} $

若对任意的x_i∈U，有 $\gamma _A^\alpha ({x_i}) = \gamma _C^\alpha ({x_i})$ ，称A是DS中基于 $\alpha $ -相容关系的最大分布协调集，简称最大分布协调集。若A是最大分布协调集，且A的任意真子集都不是最大分布协调集，那么称A是DS中基于 $\alpha $ -相容关系的最大分布相对约简，简称最大分布约简。

定义14　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ， ${x_i} \in U$ ，若属性子集A满足：

1) $\gamma _A^\alpha ({x_i}) = \gamma _C^\alpha ({x_i})$ ；

2)任意 $B \subset A$ ，满足 $\gamma _B^\alpha ({x_i}) \ne \gamma _C^\alpha ({x_i})$ ；

那么称属性子集A为区间值决策系统基于相容关系的最大分布约简。DS的所有约简集合记为 $\alpha $ - ${\rm{Reduct}}$ ，所有约简的交集称为DS的核，记为 $\alpha $ - ${\rm{Core}}$ 。

定理2　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ，则A是最大分布协调集当且仅当任意 ${x_i},{x_j} \in U$ ，当 $\gamma _C^\alpha ({x_i}) = \gamma _C^\alpha ({x_j})$ ，有 $S_A^\alpha ({x_i}) \ne $ $S_A^\alpha ({x_j})$ 。

证明　记 $J(S_A^\alpha ({x_i})) = \{ S_C^\alpha ({x_j})|S_C^\alpha ({x_j}) \subseteq S_A^\alpha ({x_i})\} $ 。“ $\Rightarrow$ ”：设A是最大分布协调集，对任意x_i，x_j∈U，假设 $S_A^\alpha ({x_i}) = S_A^\alpha ({x_j})$ ，有 $({x_i},{x_j}) \in {T}_A^\alpha $ ，即 $\gamma _A^\alpha ({x_i}) = \gamma _A^\alpha ({x_j})$ ，又因为 $\gamma _A^\alpha ({x_i}) = \gamma _C^\alpha ({x_i})$ 和 $\gamma _A^\alpha ({x_j}) = \gamma _C^\alpha ({x_j})$ 成立，那么 $\gamma _C^\alpha ({x_i}) = \gamma _C^\alpha ({x_j})$ ，这与 $\gamma _C^\alpha ({x_i}) \ne \gamma _C^\alpha ({x_j})$ 矛盾，从而任意 ${x_i},{x_j} \in U$ ，当 $\gamma _C^\alpha ({x_i}) = \gamma _C^\alpha ({x_j})$ 时，有 $S_A^\alpha ({x_i}) \ne S_A^\alpha ({x_j})$ 。

“ $\Leftarrow$ ”：对任意 ${x_i},{x_j} \in U$ ，当 $S_A^\alpha ({x_i}) = S_A^\alpha ({x_j})$ ，有 $\gamma _C^\alpha ({x_i}) = \gamma _C^\alpha ({x_j})$ ，对于任意的 ${D_{{j_0}}} \in \gamma _C^\alpha ({x_i})$ ，有 ${D_{{j_0}}} \in \gamma _C^\alpha ({x_j})$ 。由于 $S_A^\alpha ({x_i}) = \cup \{ S_C^\alpha ({x_j})|S_C^\alpha ({x_j}) \in $ $J(S_A^\alpha ({x_i})){\rm{\} }}$ ，于是对任意的 $k \leqslant q$ ，有

$\begin{gathered} D({D_k}/S_A^\alpha ({x_i})){\rm{ = }} \hfill \\ \frac{{\sum {\{ |{D_k} \cap S_C^\alpha ({x_j})|:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))\} } }}{{|S_A^\alpha ({x_i})|}}{\rm{ = }} \hfill \\ \sum {\left\{ {\frac{{|{D_k} \cap S_C^\alpha ({x_j})|}}{{|S_C^\alpha ({x_j})|}}} \right.} \times \left. {\frac{{|S_C^\alpha ({x_j})|}}{{|S_A^\alpha ({x_i})|}}:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))} \right\} \leqslant \hfill \\ \sum {\left\{ {\frac{{|{D_{{j_0}}} \cap S_C^\alpha ({x_j})|}}{{|S_C^\alpha ({x_i})|}}} \right.} \times \left. {\frac{{|S_C^\alpha ({x_j})|}}{{|S_A^\alpha ({x_i})|}}:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))} \right\}{\rm{ = }} \hfill \\ \frac{{|{D_{{j_0}}} \cap S_A^\alpha ({x_i})|}}{{|S_A^\alpha ({x_i})|}}{\rm{ = }}D({D_{{j_0}}}/S_A^\alpha ({x_i})) \hfill \\ \end{gathered} $

故 ${D_{{j_0}}} \in \gamma _C^\alpha ({x_i})$ ，从而 $\gamma _A^\alpha ({x_i}) = \gamma _C^\alpha ({x_i})$ 。

另一方面，任意的 ${D_{{j_0}}} \in \gamma _A^\alpha ({x_i})$ ，若 ${D_{{j_0}}} \ne $ $\gamma _C^\alpha ({x_i})$ ，则任意的 $S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))$ ，由 $\gamma _C^\alpha ({x_i}) = \gamma _C^\alpha ({x_j})$ 可得 $m_C^\alpha ({x_j}) > D({D_{{j_0}}}/S_C^\alpha ({x_j}))$ 。取 $\,\,\,\, {D_{{k_0}}} \in \gamma _C^\alpha ({x_j})$ ，则

$\begin{gathered} D({D_{{k_0}}}/S_A^\alpha ({x_i})){\rm{ = }} \\ \sum {\left\{ {\frac{{|{D_{{k_0}}} \cap S_C^\alpha ({x_j})|}}{{|S_C^\alpha ({x_j})|}}} \right.} \times \left. {\frac{{|S_C^\alpha ({x_j})|}}{{S_A^\alpha ({x_i})}}:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))} \right\}{\rm{ = }} \\ \sum {\left\{ {m_C^\alpha ({x_j}) \times \frac{{|S_C^\alpha ({x_j})|}}{{|S_A^\alpha ({x_i})|}}:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))} \right\} > } \\ \sum {\left\{ {D({D_{{j_0}}}/S_C^\alpha ({x_j})) \times \frac{{|S_{\rm{AT}}^\alpha ({x_j})|}}{{|S_A^\alpha ({x_i})|}}:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i})) } \right\}} = \\ \sum {\left\{ {\frac{{|{D_{{j_0}}} \cap S_C^\alpha ({x_j})|}}{{|S_C^\alpha ({x_j})|}}} \right.} \times \left. {\frac{{|S_C^\alpha ({x_j})|}}{{|S_A^\alpha ({x_i})|}}:S_C^\alpha ({x_j}) \in J(S_A^\alpha ({x_i}))} \right\} = \\ \frac{{|{D_{{j_0}}} \cap S_A^\alpha ({x_i})|}}{{|S_A^\alpha ({x_i})|}} = D({D_{{j_0}}}/S_A^\alpha ({x_i})) \end{gathered} $

与 ${D_{{j_0}}} \in \gamma _A^\alpha ({x_i})$ 矛盾，因此 ${D_{{j_0}}} \in \gamma _C^\alpha ({x_i})$ ，于是有 $\gamma _A^\alpha ({x_i}) \subseteq $ $ \gamma _C^\alpha ({x_i})$ 。

因此，证明了对任意 ${x_i} \in U$ ， $\gamma _A^\alpha ({x_i}) = \gamma _C^\alpha ({x_i})$ ，即集合A是最大分布协调集。定理得证。

定义15　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $U = \{ {x_1},{x_2}, \cdots ,{x_{|U|}}\} $ ，则对任意 $i \geqslant1 ,j \leqslant |U|$ ：

${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) = \left\{ {\begin{array}{*{20}{l}}{\{ {a_k}|{a_k} \in C \wedge \alpha _{ij}^k < \alpha \} ,\quad\gamma _A^\alpha ({x_i}) \ne \gamma _A^\alpha ({x_j})}\\{\text{Ø} ,\quad \gamma _A^\alpha ({x_i}) = \gamma _A^\alpha ({x_j})}\end{array}} \right.$

${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ 为基于α-相容类的最大分布约简可辨识矩阵 ${\bf{DM}}_{D{\rm{Max}}}^\alpha$ 第 $i$ 行 $j$ 列的元素， ${\bf{DM}}_{D{\rm{Max}}}^\alpha$ 简称为最大分布可辨识矩阵，其中 $i,j = 1,2, \cdots ,|U|$ ，Ø表示空集。

基于α-相容类的最大分布可辨识矩阵是一个相对于主对角线对称的矩阵，在进行运算时只需考虑其上三角或下三角部分即可。

定理3　设区间值决策系统 $DS = (U,C \cup D,$ $V,f)$ ， $A \subseteq C$ ，则A是最大分布协调集当且仅当任意 ${x_i},{x_j} \in U$ ，当 $\gamma _C^\alpha ({x_i}) \ne \gamma _C^\alpha ({x_j})$ 时，有 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) \cap A \ne \text{Ø} $ 。

证明　“ $ \Rightarrow $ ”：设 $A$ 是最大分布协调集，对于任意的 ${x_i},{x_j} \in $ U，假设存在 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ 使 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ $ \cap A \ne \text{Ø} $ ，则存在 $S_C^\alpha ({x_i})$ 和 $S_C^\alpha ({x_j})$ ，有 $\gamma _C^\alpha ({x_i}) \ne \gamma _C^\alpha ({x_j})$ ，由定理1得 $S_A^\alpha ({x_i}) \ne S_A^\alpha ({x_j})$ ，从而存在 ${a_k} \in A$ ，满足 $\alpha _{ij}^k < \alpha $ ，因此存在 ${a_k} \in {\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ ，即 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) \cap A \ne \text{Ø} $ 。

“ $\Leftarrow$ ”：假设存在x_i，x_j∈U，满足 $\gamma _C^\alpha ({x_i}) \ne $ $\gamma _C^\alpha ({x_j})$ ，且 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) \cap A \ne \text{Ø} $ ，则对任意a_k∈A，有 ${a_k} \notin $ $ {\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ ， $\alpha _{ij}^k > \alpha $ ，因此 $({x_i},{x_j}) \in {T}_A^\alpha $ 。假设 ${x_i}\text{、}{x_j}$ 对应的 $\alpha $ -相容类分别为 $S_A^\alpha ({x_i})$ 和 $S_A^\alpha ({x_j})$ ，则有 $S_A^\alpha ({x_i}) = S_A^\alpha ({x_j})$ ，由定理1得 $A$ 不是最大分布协调集。定理得证。

定义16　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $C = \left\{ {{a_1},{a_2}, \cdots ,{a_{\left| C \right|}}} \right\}$ ， ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ 表示最大分布可辨识矩阵中第 $i$ 行 $j$ 列的元素，基于α-相容类的最大分布可辨识函数为与 ${a_1},{a_2}, \cdots ,{a_m}$ 相对应 $|C|$ 个布尔变量 ${\bar a_{|C|}}$ 的布尔函数： $f_D^\alpha {(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2}, \cdots ,{\bar a_{|C|}}) = $ $ \wedge \{ \vee {\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j):$

${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) \ne \text{Ø} \} $ ，为基于 $\alpha $ -相容类的最大分布约简可辨识函数，简称最大分布可辨识函数。 $ \vee {\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ 表示满足 $a \in {\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j)$ 的全体布尔变量 $\bar a$ 的析取式。

利用分配率和吸收率将 $f_D^\alpha {(C)_{{\rm{Max}}}}$ 转化为 $({\bar a_1},$ ${\bar a_2}, \cdots ,{\bar a_{|C|}}) = ( \wedge {\theta _1}) \vee \cdots \vee ({\theta _l})$ ， ${\theta _k} \subseteq C,k = ({\bar a_1},{\bar a_2}, \cdots ,{\bar a_{|C|}}) = $ $( \wedge {\theta _1}) \vee \cdots \vee ({\theta _l}),{\theta _k} \subseteq C,k =1,2, \cdots ,l$ ， ${\theta _k}$ 中每一个属性元素只出现一次。

定理4　设区间值决策系统 $DS = (U,C \cup D,$ $V,f)$ ， $h_D^\alpha {(C)_{\rm{Max}}}$ 是可辨识函数 $f_D^\alpha {(C)_{Max}}$ 的形式转化，若 $A$ 是最大分布约简，当且仅当A是 $h_D^\alpha {(C)_{\rm{Max}}}$ 的一个蕴含项。

证明　“ $ \Rightarrow $ ”：假设 $\theta $ 是 $h_D^\alpha {(C)_{\rm{Max}}}$ 的一个蕴含项，则存在 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) \cap \theta \ne \text{Ø} $ ，通过定理2得知 $\theta $ 是其中一个最大分布约简。

“ $\Leftarrow$ ”：根据定义16可得 $h_D^\alpha {(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2}, \cdots ,{\bar a_m}) =$ $ ( \wedge {\theta _1}) \vee \cdots \vee ({\theta _l}),{\theta _k} \subseteq C,k = 1,2, \cdots ,l$ ，若在θ中去掉一个元素形成θ′，则存在 $S_C^\alpha ({x_i})$ 和 $S_C^\alpha ({x_j})$ 满足 $\gamma _C^\alpha ({x_i}) \ne \gamma _C^\alpha ({x_j})$ ，使得 ${\rm{DM}}_{D{\rm{Max}}}^\alpha(i,j) \cap \theta ' \ne \text{Ø} $ ，故θ′ 不是最大分布约简，从而θ是其中一个最大分布约简。定理得证。

基于差别矩阵的分布约简算法(maximum distribution reduction algorithm based on discernibility matrix，MDRADM)描述如算法2。

算法2　MDRADM

输入　区间值决策系统DS，阈值 $\alpha $ 。

输出　区间值决策系统的所有最大分布保持约简结果。

1)计算区间值决策系统DS在阈值 $\alpha $ 下的相容类集合 $S_C^\alpha (U)$ 。

2)根据每个对象对应的相容类，计算每个对象相对于每一个决策类的概率分布 $\, \mu _C^\alpha ({x_i})$ 。

3)根据每个对象的概率分布，计算所对应的最大分布 $\gamma _C^\alpha ({x_i})$ 。

4)根据每个对象的可信度不同构造最大分布约简可辨识矩阵 ${\bf{DM}}_{D{\rm{Max}}}^\alpha$ 。

5)由可辨识矩阵 ${\bf{DM}}_{D{\rm{Max}}}^\alpha$ 计算最大分布约简可辨识函数 $f_D^\alpha {(C)_{{\rm{Max}}}}$ 。

6)利用分配率和吸收率将 $U$ 转化为 $h_D^\alpha {(C)_{{\rm{Max}}}}$ ， $h_D^\alpha {(C)_{{\rm{Max}}}}$ 中每一个蕴含项为一个最大分布保持的约简。

算法2是通过可辨识矩阵求得区间值决策表的所有最大分布保持约简，因此算法在最坏情况下的时间复杂度为 $O(|C{|^{|U{|^2}}})$ ， $|C|$ 为条件属性的个数， $|U|$ 为对象的个数。

例4　如表1所示的区间值决策系统，令 $\alpha = 0.6$ ，根据例2可知相似布尔矩阵以及相容类。

计算决策属性 $D$ 对 $U$ 划分：

$U/D = \{ {D_1},{D_2}\} = \Bigr\{ \{ {x_1},{x_5},{x_6}\} ,\{ {x_2},{x_3},{x_4}\} \Bigr\}$ 。

计算每个对象对应的概率分布：

$\mu _C^{0.6}({x_1}) = \{ 1,0\} $ ， $\mu _C^{0.6}({x_2}) = \{ 0,1\} $ ，

$\mu _C^{0.6}({x_3}) = \{ 2/3,1/3\} $ ， $\mu _C^{0.6}({x_4}) = \{ 0,1\} $ ，

$\mu _C^{0.6}({x_5}) = \{ 2/3,1/3\} $ ， $\mu _C^{0.6}({x_6}) = \{ 2/3,1/3\} $ 。

计算每个对象对应的最大分布：

$\gamma _C^{0.6}({x_1}) = \{ {D_1}\} $ ， $\gamma _C^{0.6}({x_2}) = \{ {D_2}\} $ ，

$\gamma _C^{0.6}({x_3}) = \{ {D_1}\} $ ， $\gamma _C^{0.6}({x_4}) = \{ {D_2}\} $ ，

$\gamma _C^{0.6}({x_5}) = \{ {D_1}\} $ ， $\gamma _C^{0.6}({x_6}) = \{ {D_1}\} $ 。

计算最大分布约简可辨识矩阵：

${\bf{DM}}_{D{\rm{Max}}}^{0.6}(6,6) = \left[ {\begin{array}{*{20}{c}} \text{Ø} &{}&{}&{}&{}&{}\\{{a_1},{a_2},{a_3},{a_4}}& \text{Ø} &{}&{}&{}&{}\\ \text{Ø} &{{a_3},{a_4}}& \text{Ø} &{}&{}&{}\\{{a_1},{a_2},{a_3}}& \text{Ø} &{{a_3}}& \text{Ø} &{}&{}\\ \text{Ø} &{{a_3},{a_4}}& \text{Ø} &{{a_3}}& \text{Ø} &{}\\ \text{Ø} &{{a_3},{a_4}}& \text{Ø} &{{a_3}}& \text{Ø} & \text{Ø} \end{array}} \right]$

计算最大分布约简可辨识函数：

$f_D^{0.6}{(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_3}$

因此，最大分布保持约简结果为{a₃}。

例5　如表1所示的区间值决策系统，令 $\alpha $ 分别为 $0.4,0.5,0.6,0.7$ ，则分布保持约简结果为

$h_D^{0.4}(C)({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_1} \vee {a_4}$

$h_D^{0.5}(C)({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = ({a_1} \wedge {a_3}) \vee ({a_2} \wedge {a_3})$

$h_D^{0.6}(C)({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = ({a_1} \wedge {a_3}) \vee ({a_2} \wedge {a_3})$

$h_D^{0.7}(C)({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = ({a_1} \wedge {a_3}) \vee ({a_2} \wedge {a_3})$

最大分布保持约简结果为

$h_D^{0.4}{(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_1} \vee {a_4}$

$h_D^{0.5}{(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_3}$

$h_D^{0.6}{(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_3}$

$h_D^{0.7}{(C)_{{\rm{Max}}}}({\bar a_1},{\bar a_2},{\bar a_3},{\bar a_4}) = {a_3}$

性质3　设区间值决策系统 ${\rm{DS}} = (U,C \cup D,$ $V,f)$ ， $H = {h_1} \vee {h_2} \vee \cdots \vee {h_m}$ 和 $K = {k_1} \vee {k_2} \vee \cdots \vee {k_n}$ 分别是分布约简和最大分布约简结果，则在阈值 $\alpha $ 下，对于 $K$ 中任意一个蕴含项 ${k_j}$ ， $H$ 中存在一个蕴含项 ${h_i}$ 满足 ${h_i} \supseteq {k_j}$ 。

3 实验验证与分析

本节对提出的最大分布约简算法进行实验验证，实验包括两部分：1)比较最大分布约简方法和其他约简方法的约简结果，验证了性质3的正确性；2)比较了最大分布保持、分布保持和正域保持3种约简算法的约简效率。采用UCI标准测试集进行实验。实验环境为PC机，操作系统为Windows 7旗舰版64 位；内存为6.0 GB DDR3，CPU为Intel i5-3470。

实验选取8组标准UCI数据集，对缺失数据通过将对应属性下占多数属性值进行替换，对名词性数据采用{0,1}替换，对连续型数据采用等频分割^[19]的方法，所有数据预处理均在WEKA3.6进行，数据集信息如表2所示， $|U|$ 表示对象数，|AT|表示条件属性数， $|D|$ 表示决策属性将对象分类个数。

由于表格有限，表3～10中数据集名称均为相应数据集名称的缩写。

由于采用的UCI数据集都是单值数据，因此需将单值数据转换为区间值数据，单值数据转换为区间值数据的方法在文献[19]中已经描述，先将该方法改进，引进阈值 $\lambda $ ，该值可调节振幅，即区间值的长度。

设区间值决策系统 $(U,C \cup D,V,f)$ ，对任意的 ${x_i} \in U$ ， ${a_t}({x_i})$ 为 ${x_i}$ 在属性t上的取值 $U/D = \{ {D_1},$ ${D_2}, \cdots ,{D_{|U/D|}}\} $ ， ${D_k} \in U/D$ ，则单值性数据转换为区间值数据的振幅为

$\sigma _t^k = \sqrt {\frac{1}{{|{D_k}| - 1}}\sum\limits_{{x_i} \in {D_k}} {{{({a_t}({x_j}) - \bar a_t^k)}^2}} } $

式中 $\bar a_t^k = \displaystyle\frac{{\displaystyle\sum\limits_{{x_j} \in {D_k}} {{a_t}({x_j})} }}{{|{D_k}|}}$ 。

区间值的左右区间分别为

$l_i^t = {a_t}({x_i}) - \lambda \bar a_t^k$

$u_i^t = {a_t}({x_i}) + \lambda \bar a_t^k$

式中 $\lambda $ 为调节区间值长度的值。

3.1 约简结果对比

在本节中，讨论了最大分布约简与其他约简方法之间的关系^[20]，选取正域保持约简算法(PRADM)^[17]和分布保持约简算法(DRADM)。 $\lambda $ 分别取 $2.4$ 和 $3.5$ ， $\alpha $ 分别取 $0.4\text{、}0.5\text{、}0.6\text{、}0.7$ ，共进行了8组实验，实验结果如表3~10所示，其中：集合1=集合7=集合17=集合19=集合22=集合28={{1}, {2}, {3}, {4}, {5}, {6}}；集合2=集合14=集合16=集合18=集合21=集合23={{1}, {2}, {3}, {4}, {5}}；集合3=集合20=集合24={{1}, {2}, {3}, {4}, {5}, {6}, {7}}；集合4=集合6={1, 3, 4, 5, 6, 7, 8, 9}；集合5=集合8=集合9=集合10=集合26=集合27={1, 2, 3, 4, 5, 6, 7, 8, 9}；集合11=集合12=集合13={{1, 3, 5},{2, 3, 5},{3, 4, 5},{1, 2, 3, 4, 6},{1, 5, 6},{2, 5, 6},{3, 5, 6}{4, 5, 6}}；集合15={{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}；集合25={1, 2, 3, 4, 5, 7, 8, 9}。

表3～6为 $\lambda $ 取 $2.4$ ， $\alpha $ 分别取0.4、0.5、0.6、0.7时，正域保持、分布保持和最大分布保持约简算法的约简结果。实验结果表明，MDRADM约简结果为DRADM约简结果的子集，即验证了性质3的正确性，而PRADM约简结果和MDRADM约简结果没有明显关系。这是因为，当正域为空时，正域约简结果为条件属性中任意一个属性，故PRADM的约简结果和MDRADM的约简结果不存在包含关系。当 $\lambda {\rm{ = 3}}{\rm{.5,}}\alpha {\rm{ = 0}}{\rm{.4}}$ 时，对于大部分数据集，DRADM的约简结果最短，Fertility数据集则在 $\lambda {\rm{ = }}$ 2.4， $\alpha {\rm{ = 0}}{\rm{.7}}$ 时最短，但Liverdisorders数据集在任何阈值下均没有冗余属性。

3.2 约简效率对比

本节选取Mammographic Mass数据集，对比两个算法随对象数量的增加耗时变化情况。图1～5为 $\lambda $ 取 $2.4$ ， $\alpha $ 分别取0.4、0.5、0.6、0.7、0.8时，3个算法的时间耗费情况；横坐标表示Mammographic Mass数据集的对象数量，纵坐标表示运行时间，单位为s。

图1～5中虚线表示PRADM随着对象数量增加运行时间变化曲线，空心圆点实线表示MDRADM随着对象数量增加运行时间变化曲线，交叉点实线表示DRADM随着对象数量增加运行时间变化曲线。实验结果表明，在对象数较少情况下，由于差别矩阵较简单，PRADM、DRADM和MDRADM运行时间几乎没有差别，但随着对象数量的增加，3种算法的运行时间差异越来越明显；由于MDRADM差别元素是DRADM差别元素的一个子集，PRADM的差别矩阵为非对称矩阵，故MDRADM的运行时间小于PRADM和DRADM运行时间。当 $\alpha $ 分别取0.5、0.6、0.7、0.8时，Mammographic Mass数据集随着对象的增加，3个算法的耗时差距增大，这是由于随着对象的增加差别矩阵愈加复杂，计算量越大造成的；当 $\alpha = 0.4$ 时，也呈现这样的趋势，但当对象数达到900时，利用吸收率和结合律运算的差别矩阵较简单，造成时间增长率减小。当 $\lambda $ 取 $3.5$ ， $\alpha $ 分别取0.4、0.5、0.6、0.7、0.8时，3个算法的时间耗费情况跟 $\lambda $ 取 $2.4$ 时的折线图大致相同，所以本文不作详细描述。

4 结束语

属性约简是粗糙集理论研究的热点问题之一，在实际应用中具有重要意义，主要作用有：1)提取更加泛化的规则；2)针对应用中的海量数据，能够压缩数据集规模。分布保持约简能够保持信息系统在约简前后置信度不变，而人们往往只关注置信度最大的规则，具有广泛的应用价值。

本文在相关研究成果的基础上，在不协调区间值决策系统中提出最大分布约简的概念，构造了基于可辨识矩阵的最大分布约简算法，该算法保持了在知识约简前后各个规则的最大置信度不变。实验选取8组UCI数据集将本文算法与已有的两种约简算法的约简结果和效率进行对比。实验结果表明，分布约简包含最大分布约简，并且最大分布约简算法比其他两种算法具有更高的效率。由于本文提出的算法是在可辨识矩阵基础上的，其时间和空间复杂度较高，不利于在实际应用中推广，故提出高效率的约简算法是未来研究方向之一。