粗糙集理论^[1-5]是于1982年由波兰科学家Pawlak提出的一种用于分析和处理不确定或不精确数据的数学工具。目前，粗糙集理论正被广泛应用于人工智能、机器学习、模式识别、数据挖掘等领域，并取得了丰硕的研究成果。属性约简^[6-12]是粗糙集理论的核心研究内容之一。属性约简的本质是在保持原决策系统某种分辨能力不变的前提下，删除冗余属性，获取最小属性子集。

在决策系统中，若某个条件属性值存在缺失，则称该决策系统为不完备决策系统。目前，国内外相关学者针对不完备决策系统做了大量的研究工作。2002年，Liang等^[13]提出了基于粗糙熵的不完备决策系统约简算法。2010年，周献中等^[14]介绍了在不完备决策系统下基于相容关系和相似关系的粗糙集模型及其拓展模型，通过引入相容矩阵和相似矩阵，系统研究了相应的粗计算、属性约简以及决策规则提取的矩阵算法。2010年Qian等^[15]提出了基于极大相容块的不协调不完备决策系统下的上下近似约简概念并给出构造相应差别矩阵方法。2014年，Shu等^[16]提出了不完备决策系统下基于候选属性重要度的快速求属性约简方法。2015年，Qian等^[17]提出了基于紧凑差别矩阵的动态不完备决策系统下的特征选择方法。2018年，Xie等^[18]提出了不完备决策系统下不协调度的概念，证明了基于不协调度与基于正域的属性约简等价。

在不完备决策系统中，具有相同条件属性的对象可能决策出多个不同的决策值，每个对象所有可能决策出的决策值称为该对象的广义决策值，广义决策约简旨在保持约简前后每个对象的广义决策值不变。1993年，Skowron^[19]提出了广义决策的概念。1998年，Kryszkiewicz^[20]讨论了不完备决策系统下的广义决策约简问题，给出相关决策规则的提取方法，并提出了基于差别矩阵^[21]的广义决策约简方法。上述研究考虑决策属性的所有决策类，而在实际应用中，决策者往往只关注部分决策类。为此相关学者针对局部约简即特定类约简做了大量研究。尹继亮等^[22]讨论了区间值系统下的局部属性约简。Qian等^[23]为解决经典粗糙集无法处理具有有限标记的大数据集的问题，引入了局部粗糙集的概念。Liu等^[24]提出了第 $l$ 决策类下近似约简概念并提出相应差别矩阵构造方法。

综合上述研究，文献[20]研究讨论了不完备决策系统所有决策类的广义决策约简，文献[22]只在区间值系统下对局部约简进行了研究，文献[24]在完备系统下对单特定类的正域约简进行了研究。然而，基于多特定类的不完备决策系统下广义决策约简未见报道。为此，本文提出基于多特定类的不完备决策系统广义决策约简的理论框架，定义了单特定类的不完备决策系统广义决策约简的相关概念，提出并证明相关定理，构造相应差别矩阵和区分函数，并将单特定类推广到多特定类，提出基于差别矩阵的多特定类不完备决策系统广义决策约简算法并通过实验验证了算法的有效性。

1 基本概念

为方便进一步研究基于多特定类的不完备决策系统广义决策约简，本节将给出不完备决策系统及广义决策约简的相关基本概念。

1.1 不完备决策系统及其上下近似

定义1^[16] 　四元组 ${\rm{DS}} = (U,{\rm{AT}} = C \cup D,V,f)$ 为一个决策系统，其中 $U$ 表示所有对象的非空有限集合，称之为论域； $C$ 表示条件属性的非空有限集合； $D$ 表示决策属性的非空有限集合， $C \cap D = \text{Ø} $ ； $V = \mathop \cup \limits_{a \in {\rm{AT}}} {V_a}$ ， ${V_a}$ 表示属性 $a \in {\rm{AT}}$ 的值域； $f:U \times {\rm{AT}} \to V$ 是一个信息函数，它使得任意对象的任意一个属性都有一个信息值， $f(x,a)$ 表示对象 $x \in U$ 在属性 $a \in {\rm{AT}}$ 上的取值。

定义2^[16] 　四元组 ${\rm{DS}} = (U,{\rm{AT}} = C \cup D,V,f)$ 为一个决策系统，对任意非空属性集 $B \subseteq {\rm{AT}}$ 导出论域 $U$ 上的不可区分关系 ${\rm{IND}}(B)$ 定义为

$\begin{array}{l} {\rm{IND}}(B) = \{ (x,y) \in U \times U|\forall b \in B,\;f(x,b) = f(y,b)\} \end{array} $

(1)

不可区分关系是一个满足自反性、对称性和传递性的等价关系。由不可区分关系 ${\rm{IND}}(B)$ 导出对论域 $U$ 的划分为 ${U / {{\rm{IND}}(B)}} = \{ {[x]_B}|x \in U\} $ ，简记为 ${U / B}$ ，其中 ${[x]_B}$ 表示包含 $x$ 的等价类。

定义3^[16] 　四元组 ${\rm{DS}} = (U,{\rm{AT}} = C \cup D ,V,f)$ 为一个决策系统，若存在条件属性 $c \in C$ 使得 ${V_c}$ 含有缺失值，则称该决策系统为不完备决策系统，用 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup D ,V,f)$ 表示， ${V_c}$ 中的缺失值使用 *表示。

在不完备决策系统 ${\rm{IDS}}$ 中，决策属性 $d \in D$ 的值域 ${V_d}$ 不含有缺失值。若决策属性集 $D$ 中决策属性数目为1，则称 ${\rm{IDS}} $ 为不完备单决策系统；若 $D$ 中决策属性数目大于1，则称 ${\rm{IDS}} $ 为不完备多决策系统。为表述方便，本文只考虑不完备单决策系统的情况，即 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 的情况。

定义4^[20] 　四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统，对任意条件属性集 $A \subseteq C$ ，定义其相容关系为

$ \begin{array}{l} {\rm{SIM}}\left( A \right) = \{ \left( {x,y} \right) \in U \times U|\forall a \in A,f\left( {x,a} \right) = f\left( {y,a} \right) \vee \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f\left( {x,a} \right) = * \vee f\left( {y,a} \right) = *\} \end{array} $

(2)

其中 $f\left( {x,a} \right)$ 表示对象 $x \in U$ 在属性 $a \in A$ 上的取值。

相容关系 ${\rm{SIM}}\left( A \right)$ 具有以下性质：

性质1^[20] 　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统，对 $\forall A \subseteq C$ ，有：

$ {\rm{SIM}}\left( A \right){\rm{ = }}\mathop \cap\limits_{a \in A} {{\rm{SIM}}\left( {\{ a\} } \right)} $

(3)

性质2　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统，对 $\forall A \subseteq C$ ， ${\rm{SIM}}\left( A \right)$ 满足：

1) 自反性，对 $\forall x \in U$ ，有 $\left( {x,y} \right) \in {\rm{SIM}}\left( A \right)$ ；

2) 对称性，对 $\forall x,{{y}} \in U$ ，若 $\left( {x,y} \right) \in {\rm{SIM}}\left( A \right)$ ，则 $\left( {y,x} \right) \in {\rm{SIM}}\left( A \right)$ ；

3) 非传递性，对 $\forall x,y,z \in U$ ，若 $\left( {x,y} \right) \in {\rm{SIM}}\left( A \right)$ 且 $\left( {y,z} \right) \in {\rm{SIM}}\left( A \right)$ ， $\left( {x,z} \right) \in {\rm{SIM}}\left( A \right)$ 不一定成立。

设 ${S_A}\left( x \right) = \{ y \in U|\left( {x,y} \right) \in {\rm{SIM}}\left( A \right)\} $ ，其中条件属性集 $A \subseteq C$ ， ${S_A}\left( x \right)$ 表示通过条件属性集 $A$ 与 $x$ 可能不可区分的对象的最大集合。设 ${D_A}\left( x \right) =$ $ \{ y \in U|\left( {x,y} \right) \notin {\rm{SIM}}\left( A \right)\} $ ，其中条件属性集 $A \subseteq C$ ， ${D_A}\left( x \right)$ 表示通过条件属性集 $A$ 与 $x$ 可能可区分的对象的最大集合。对 $\forall x \in U$ ，有 ${S_A}\left( x \right) \cap {D_A}\left( x \right) = \text{Ø} $ 且 ${S_A}\left( x \right) \cup {D_A}\left( x \right) = U$ 。

在 ${\rm{IDS}} $ 中，对 $\forall A \subseteq C$ ，有 $U/{\rm{SIM}}\left( A \right)$ 表示分类且 $U/{\rm{SIM}}\left( A \right) = \{ {S_A}\left( x \right)|x \in U\} $ 。 $U/{\rm{SIM}}\left( A \right)$ 中的每一个元素 ${S_A}\left( x \right)\left( {x \in U} \right)$ 被称为相容类，且满足 $\cup U/ $ ${\rm{SIM}}{\left( A \right)} {\rm{ = }}U$ 。

根据相容类，可得到对象集 $X \subseteq U$ 有关于条件属性集 $A \subseteq C$ 的下近似集和上近似集。

定义5^[20] 　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统，对 $\forall X \subseteq U$ ， $\forall A \subseteq C$ ， $X$ 关于条件属性集 $A$ 的下近似集和上近似集分别定义为

$ {\underline A} X = \{ x \in U|{S_A}\left( x \right) \subseteq X\} = \{ x \in X|{S_A}\left( x \right) \subseteq X\} $

(4)

$ {\overline A} X = \{ x \in U|{S_A}\left( x \right) \cap X \ne \text{Ø} \} = \cup {\{ {S_A}\left( x \right)|x \in X\} } $

(5)

例1　 不完备决策系统 ${\rm{IDS}} $ 如表1所示，论域 $U{\rm{ = \{ }}{x_1}{\rm{,}}{x_2}{\rm{,}}{x_3}{\rm{,}}{x_4}{\rm{,}}{x_5}{\rm{,}}{x_6}{\rm{\} }}$ ， $C{\rm{ = \{ }}{a_1},{a_2},{a_3},{a_4}{\rm{\} }}$ 为条件属性集，决策属性集为 $\{ d\}$ 。

由定义4得 ${\rm{IDS}} $ 在条件属性集 $C$ 上相容类集合 $U\!/\!{\rm{SIM}}\left( C \right){\rm{ \!=\!\!\! \{ }}{S_C}\!\left( {{x_1}} \right){\rm{,}}{S_C}\!\left( {{x_2}} \right){\rm{,}}{S_C}\!\left( {{x_3}} \right){\rm{,}}{S_C}\!\left( {{x_4}} \right){\rm{,}}{S_C}\!\left( {{x_5}} \right){\rm{,}}{S_C}\!\left( {{x_6}} \right)\!\!{\rm{\} }}\;\;\;\;\;\;\;\;\;$ ，其中 ${S_C}\left( {{x_1}} \right){\rm{ = \{ }}{x_1},{x_3}{\rm{\} }}$ ， ${S_C}\left( {{x_2}} \right){\rm{ = \{ }}{x_2},{x_5}{\rm{\} }}$ ， ${S_C}\left( {{x_3}} \right){\rm{ = \{ }}{x_1},{x_3}{\rm{\} }}$ ， ${S_C}\left( {{x_4}} \right){\rm{ = \{ }}{x_4}{\rm{\} }}$ ， ${S_C}\left( {{x_5}} \right){\rm{ = \{ }}{x_2},{x_5},{x_6}{\rm{\} }}$ ， ${S_C}\left( {{x_6}} \right){\rm{ = \{ }}{x_5},{x_6}{\rm{\} }}$ 。决策属性 $d$ 对论域 $U$ 的划分为 $U/\{ d\} {\rm{ = \{ }}{D_1},{D_2},{D_3}{\rm{\} }}$ ，其中 ${D_1} = {\rm{\{ }}{x_1},{x_2}{\rm{\} }}$ ， ${D_2} = {\rm{\{ }}{x_3},{x_4}{\rm{\} }}$ ， ${D_3} = {\rm{\{ }}{x_5},{x_6}{\rm{\} }}$ 。由 ${\rm{IDS}} $ 中条件属性集 $C$ 的相容类集合 $U/{\rm{SIM}}\left( C \right)$ 及决策属性 $d$ 对论域 $U$ 的划分 $U/\{ d\} $ 可得决策类 ${D_i} \in$ $ U/\{ d\} \left( {i = 1,2,3} \right)$ 在 $C$ 上的下近似集 $CD_i$ 和上近似集 ${\overline C} {D_i}$ 分别为：

$\underline C {D_1}{\rm{ = }}\text{Ø} ,\;\;\overline C {D_1} = {\rm{\{ }}{x_1},{x_2},{x_3},{x_5}{\rm{\} }}$ ；

$\underline C {D_2}{\rm{ = \{ }}{x_4}{\rm{\} }},\;\;\overline C {D_2} = {\rm{\{ }}{x_1},{x_3},{x_4}{\rm{\} }}$ ；

$\underline C {D_3}{\rm{ = \{ }}{x_6}{\rm{\} }},\;\;\overline C {D_3} = {\rm{\{ }}{x_2},{x_5},{x_6}{\rm{\} }}$ 。

1.2 不完备决策系统广义决策约简

定义6^[20] 　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统，对 $\forall x \in U$ ，关于条件属性集 $A \subseteq C$ 的广义决策值定义为

${\partial _A}(x) = \{ f(y,d)|y \in {S_A}(x)\} $

(6)

在 ${\rm{IDS}}$ 中， ${\partial _A}(x)$ 表示对象 $x$ 关于条件属性集 $A$ 的所有可能决策值的集合。

属性约简旨在保证决策系统的某种分类能力不变的情况下，删除冗余属性，获得最小属性子集。给出不完备决策系统的广义决策约简定义如下。

定义7^[20] 　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统，若条件属性集 $A \subseteq C$ 为属性集 $C$ 的一个广义决策约简，当且仅当满足以下两个条件：

1)对 $\forall x \in U$ ，有 ${\partial _A}(x) = {\partial _C}(x)$ ；

2)对 $\forall A' \subset A$ ， $\exists x' \in U$ ，有 ${\partial _{A'}}(x') \ne {\partial _A}(x')$ 。

条件 1)保证了条件属性联合的充分性，即约简前后决策系统广义决策值的一致性；条件 2)保证了条件属性个体的必要性，即缺少任意一个必要属性，则无法保持决策系统的广义决策值不变。

由广义决策约简定义可以构造相应的差别矩阵及区分函数，定义如下。

定义8^[20] 　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， $U = \{ {x_1},{x_2}, \cdots ,{x_n}\} $ ， $\forall x,y \in U$ ， ${\rm{IDS}}$ 广义决策约简的差别矩阵为 $n \times n$ 的矩阵，记为 ${{{M}}_{{\rm{GEN}}}} = {({M_{{\rm{GEN}}}}(x,y))_{n \times n}}$ ，其中矩阵元素 ${M_{{\rm{GEN}}}}(x,y)$ 为

${M_{{\rm{GEN}}}}(x,y) = \left\{ {\begin{array}{*{20}{l}} \begin{array}{l} \!\!\!\! \{ a \in C|f(x,a) \ne f(y,a) \wedge \\ \quad f(x,a) \ne * \wedge f(y,a) \ne * \} \\ \end{array}, &{y \in {\Pi _{{\rm{GEN}}}}} \\ \text{Ø}, & \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! {\text{其他}} \end{array}} \right.$

(7)

其中 $ {\Pi _{{\rm{GEN}}}} = \{ z \in U|f(z,d) \notin {\partial _C}(x)\} $ 。

定义9^[20] 　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${{{M}}_{{\rm{GEN}}}}$ 为 ${\rm{IDS}}$ 广义决策约简的差别矩阵，若 ${M_{{\rm{GEN}}}}(x,y) = \{ {a_1},{a_2}, \cdots ,{a_k}\} \ne \text{Ø} $ ，其中 $k$ 表示 ${M_{{\rm{GEN}}}}(x,y)$ 中属性的数量，用 $ \vee {M_{{\rm{GEN}}}}(x,y)$ 表示布尔函数 ${a_1} \vee {a_2} \vee \cdots \vee {a_k}$ ，对 $\forall {M_{{\rm{GEN}}}}(x,y) \ne \text{Ø} $ ， ${\rm{IDS}}$ 广义决策约简的区分函数为

${\rm{DF}}({{{M}}_{{\rm{GEN}}}}) = \wedge ( \vee {M_{{\rm{GEN}}}}(x,y))$

(8)

例2　 不完备决策系统 ${\rm{IDS}}$ 如表1所示，论域 $U = \{ {x_1},{x_2},{x_3},{x_4},{x_5},{x_6}\} $ ， $C = \{ {a_1},{a_2},{a_3},{a_4}\} $ 为条件属性集，决策属性集为 $\{ d\} $ 。

由定义6得 ${\rm{IDS}}$ 在条件属性集 $C$ 上广义决策值 ${\partial _C}(U) = \{ {\partial _C}({x_1}),{\partial _C}({x_2}),{\partial _C}({x_3}),{\partial _C}({x_4}),{\partial _C}({x_5}),{\partial _C}({x_6})\} $ ，其中 ${\partial _C}({x_1}) = \{ 1,2\} $ ， ${\partial _C}({x_2}) = \{ 1,3\} $ ， ${\partial _C}({x_3}) = \{ 1,2\} $ ， ${\partial _C} $ $({x_4}) = \{ 2\} $ ， ${\partial _C}({x_5}) = \{ 1,3\} $ ， ${\partial _C}({x_6}) = \{ 3\} $ 。 ${\rm{IDS}}$ 中所有决策类的广义决策约简差别矩阵为

$ \begin{gathered} \;\;\;\;\;{{ M}_{{\rm{GEN}}}} = \\ \left[ {\begin{array}{*{20}{c}} \text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!{\{ {a_3}\} }&\!\!\!\!\!{\{ {a_3}\} } \\ \text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!{\{ {a_3}\} }&\!\!\!\!\!{\{ {a_1},{a_3},{a_4}\} }&\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} \\ \text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!{\{ {a_3}\} }&\!\!\!\!\!{\{ {a_1},{a_3}\} } \\ {\{ {a_4}\} }&\!\!\!\!\!{\{ {a_1},{a_3},{a_4}\} }&\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!{\{ {a_2},{a_3},{a_4}\} }&\!\!\!\!\!{\{ {a_2},{a_3}\} } \\ \text{Ø} &\!\!\!\!\!\text{Ø} &\!\!\!\!\!{\{ {a_3}\} }&\!\!\!\!\!{\{ {a_2},{a_3},{a_4}\} }&\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} \\ {\{ {a_3}\} }&\!\!\!\!\!{\{ {a_1}\} }&\!\!\!\!\!{\{ {a_1},{a_3}\} }&\!\!\!\!\!{\{ {a_2},{a_3}\} }&\!\!\!\!\!\text{Ø} &\!\!\!\!\!\text{Ø} \end{array}} \right] \end{gathered} $

根据 ${\rm{IDS}}$ 所有决策类的广义决策约简的差别矩阵 ${ M_{{\rm{GEN}}}}$ 可得对应的区分函数为

$\begin{gathered} {\rm{DF}}({{ M}_{{\rm{GEN}}}}) = ({a_3}) \wedge ({a_1} \vee {a_3} \vee {a_4}) \wedge ({a_1} \vee {a_3}) \wedge ({a_4}) \\ \wedge ({a_2} \vee {a_3} \vee {a_4}) \wedge ({a_2} \vee {a_3}) \wedge ({a_1}) =\\ {a_1} \wedge {a_3} \wedge {a_4} \\ \end{gathered} $

因此, ${\rm{IDS}}$ 的所有决策类的广义决策约简为 $\{ {a_1},{a_3},{a_4}\} $ 。

2 多特定类广义决策约简

在实际应用中，相较经典广义决策约简中关注全部决策类，决策者往往只关注决策属性中的一种或者几种决策类。因此，对于某些特定决策类的约简可能更有意义。本节将讨论不完备决策系统下多特定类的广义决策约简。

2.1 基于差别矩阵的单特定类的广义决策约简

定义10　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对 $\forall {D_i} \in {U / {\{ d\} }},i = 1,2, \cdots ,|{U / {\{ d\} }}|$ ， $\forall A \subseteq C$ ， $\forall x \in \{ z \in U|{D_i} \cap {S_C}(z) \ne \text{Ø} \} $ ，若满足 ${\partial _A}(x) = {\partial _C}(x)$ ，则称条件属性集 $A$ 为单特定类 ${D_i}$ 的广义决策协调集。

定义11　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{\left| {{U / {\{ d\} }}} \right|}}\} $ 为决策类集合，对 $\forall {D_i} \in {U / {\{ d\} }}$ ， $i{\rm{ = }}1,2, \cdots ,\left| {{U / {\{ d\} }}} \right|$ ，若 $\forall A \subseteq C$ 为单特定类 ${D_i}$ 的广义决策约简当且仅当满足以下两个条件：

1) $\forall x \in \{ z \in U|{D_i} \cap {S_C}(z) \ne \text{Ø}\} $ ， ${\partial _A}(x) = {\partial _C}(x)$ ；

2) $\forall A' \subset A$ ， $\exists x' \in \{ z \in U|{D_i} \cap {S_C}(z) \ne \text{Ø} \} $ ，使得 ${\partial _{A'}} $ $(x') \ne {\partial _C}(x')$ 。

定理1　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对 $\forall {D_i} \in {U / {\{ d\} }}$ ， $i = 1,2, \cdots ,|{U / {\{ d\} }}|$ ，条件属性集 $A \subseteq C$ 为单特定类 ${D_i}$ 的广义决策协调集当且仅当 ${D_i} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，有 $(x,y) \notin $ $ {\rm{SIM}}(A)$ 。

证明：

充分性：因条件属性集 $A$ 是 ${\rm{IDS}}$ 单特定类 ${D_i}$ 的广义决策协调集，对 $\forall x \in \{ z \in U|{D_i} \cap {S_C}(z) \ne \text{Ø} \} $ ，有 ${\partial _A}(x) = {\partial _C}(x)$ 。当 ${D_i} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _{\rm{C}}}(x)$ ，即 $f(y,d) \notin {\partial _A}(x)$ ，即 $(x,y) \notin {\rm{SIM}}(A)$ 。

必要性：当 ${D_i} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，有 $(x,y) \notin {\rm{SIM}}(A)$ ，所以有 $f(y,d) \notin {\partial _A}(x)$ 成立。当满足 ${D_i} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，必有 $f(y,d) \notin $ $ {\partial _A}(x)$ ，即 ${\partial _C}(x) \supseteq {\partial _A}(x)$ ，又因为 $A \subseteq C$ ， ${\partial _A}(x) \supseteq {\partial _C}(x)$ ，所以当 $\forall x \in \{ z \in U|{D_i} \cap {S_C}(z) \ne \text{Ø} \} $ 时，有 ${\partial _A}(x) = {\partial _C}(x)$ 。因此条件属性集 $A \subseteq C$ 为单特定类 ${D_i} \in {U / {\{ d\} }}$ 的广义决策协调集。证毕。

定义12　 四组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合， $U = \{ {x_1},{x_2}, \cdots ,{x_n}\} $ ， $\forall x,y \in U$ , ${\rm{IDS}}$ 单特定类 ${D_i} \in {U / {\{ d\} }}$ 广义决策约简的差别矩阵为 $n \times n$ 的矩阵，记为 ${{ M}_i} = {({M_i}(x,y))_{n \times n}}$ ，其中矩阵元素 ${{ M}_i}(x,$ $y) $ 为

${M_i}(x,y) =\\ \left\{ {\begin{array}{*{20}{l}}\begin{array}{l} \!\!\!\{ a \in C|f(x,a) \ne f(y,a) \wedge \\ \quad f(x,a) \ne * \wedge f(y,a) \ne * \} \end{array},&{(x,y) \in {\Pi _i}} \\ \text{Ø}, &\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!{\text{其他}} \end{array}} \right.$

(9)

其中， ${\Pi _i} = \{ (x,y)|x,y \in U,{D_i} \cap {S_C}(x) \ne \text{Ø} \wedge f(y,d) \notin $ $ {\partial _C}(x)\} $ ， $i = 1,2, \cdots ,|{U / {\{ d\} }}|$ 。

定理2　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，论域 $U = \{ {x_1},{x_2}, \cdots ,{x_n}\} $ ，对 $\forall {D_i} \in {U / {\{ d\} }}$ ， $i = 1,2, \cdots ,|{U / {\{ d\} }}|$ ，条件属性集 $A \subseteq C$ 是单特定类 ${D_i}$ 的广义决策协调集当且仅当 $\forall (x,y) \in {\Pi _i}$ 时，有 $A \cap {M_i}(x,y) \ne \text{Ø} $ 。

证明：

充分性：设条件属性集 $A$ 是单特定类 ${D_i}$ 的广义决策协调集，对于 $\forall (x,y) \in {\Pi _i}$ ，若 ${D_i} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ ，则有 $(x,y) \notin {\rm{SIM}}(A)$ ，所以一定存在 $a \in A$ 使得 $(x,y) \notin {\rm{SIM}}(\{ a\} )$ ，故 $a \in {M_i}(x,y)$ ，所以 $A \cap {M_i}(x,y) \ne \text{Ø} $ 。

必要性：设 $\exists (x,y) \in {\Pi _i}$ ，使得 $A \cap {M_i}(x,y) = \text{Ø} $ ，则有 $(x,y) \in {\rm{SIM}}(A)$ 成立，又因为对 $\forall x \in U$ ，当 ${D_i} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，必有 $(x,y) \notin {\rm{SIM}}(A)$ ，这与 $(x,y) \in {\rm{SIM}}(A)$ 矛盾。证毕。

定义13　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对 $\forall {D_i} \in {U / {\{ d\} }}$ ， $i = 1,2, \cdots ,|{U / {\{ d\} }}|$ ， ${{ M}_i}$ 为 ${\rm{IDS}}$ 单特定类 ${D_i}$ 的广义决策约简的差别矩阵，若 ${M_i}(x,y) = \{ {a_1},{a_2}, \cdots ,{a_k}\} \ne \text{Ø} $ ，其中 $k$ 表示 ${M_i}(x,y)$ 中属性的数量，用 $ \vee {M_i}(x,y)$ 表示布尔函数 ${a_1} \vee {a_2} \vee \cdots \vee {a_k}$ ，对 $\forall {M_i}(x,y) \ne \text{Ø} $ ， ${\rm{IDS}}$ 单特定类 ${D_i}$ 的广义决策约简的区分函数为

${\rm{DF}}({{ M}_i}) = \wedge ( \vee {M_i}(x,y))$

(10)

定理3　 四元组 ${\rm{IDS}} = (U,AT = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对 $\forall {D_i} \in {U / {\{ d\} }}$ ， $i = 1,2, \cdots ,|{U / {\{ d\} }}|$ ， ${\rm{IDS}}$ 单特定类 ${D_i}$ 的广义决策约简区分函数 ${\rm{DF}}({{ M}_i}) = $ $ \wedge ( \vee {{M}_i}(x,y))$ 的极小析取范式为 ${\rm{DF}}'({{{M}}_i}) = \mathop \vee \limits_{k = 1}^t (\mathop \wedge \limits_{s = 1}^{{q_k}} {a_s})$ ， $t$ 表示 ${\rm{DF}}'({{{M}}_i})$ 中的析取项数目， ${q_k}$ 表示 ${\rm{DF}}'({{{M}}_i})$ 中第 $k$ 个析取项中属性数目。记 ${A_k} = \{ {a_s}|s = 1,2, \cdots ,{q_k}\} $ ，则 $\{ {A_k}|k = 1,2, \cdots ,t\} $ 是单特定类 ${D_i} \in {U / {\{ d\} }}$ 的所有广义决策约简形成的集合。

证明：

对 $\forall k \leqslant t$ ， $\forall (x,y) \in {\Pi _i}$ ，由极小析取范式定义可知 ${A_k} \cap {M_i}(x,y) \ne \text{Ø} $ ，由定理2可知 ${A_k}$ 是广义决策协调集。

$DF'({{{M}}_i}) = \mathop \vee \limits_{k = 1}^t ({A_k})$ ，若在 ${A_k}$ 中删除一个元素形成 ${A'_k}$ ，则 $\exists (x,y) \in {\Pi _i}$ 使得 ${A'_k} \cap {M_i}(x,y) = \text{Ø} $ ，故 ${A'_k}$ 不是广义决策约简，因此 ${A_k}$ 是广义决策约简。因为区分函数中包含所有 ${M_i}(x,y)$ ，故不存在其余广义决策约简。证毕。

2.2 基于差别矩阵的多特定类的广义决策约简

根据以上讨论，将单特定类的不完备决策系统广义决策约简扩展得到多特定类的不完备决策系统广义决策约简。给出多特定类的广义决策约简相关定义如下。

定义14　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，则多特定类 ${D_{{\rm{mcs}}}}$ 定义为

$ {D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }},{D_{{\rm{mcs}}}} \ne \text{Ø} $

(11)

由多特定类的定义可知，多特定类 ${D_{{\rm{mcs}}}}$ 至少含有一个单特定类至多含有 $|{U / {\{ d\} }}|$ 个互不相同的单特定类。

定义15　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对 $\forall {D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ ， $\forall A \subseteq C$ ， $\forall x \in \{ z \in $ $ U| \cup {D_{{\rm{mcs}}}} \cap {S_C}(z) \ne \text{Ø} \} $ ，若 ${\partial _A}(x) = {\partial _C}(x)$ ，则称条件属性集 $A$ 为多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策协调集。

定义16　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对 $\forall {D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ ，条件属性集 $A \subseteq C$ 为多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策约简当且仅当满足以下两个条件：

1) 对 $\forall x \in \{ z \in U| \cup {D_{{\rm{mcs}}}} \cap {S_C}(z) \ne \text{Ø} \} $ ，都有 $ {\partial _A}(x) =$ $ {\partial _C}(x)$ ；

2) $\forall A' \subset A$ ， $\exists x' \in \{ z \in U| \cup {D_{{\rm{mcs}}}} \cap {S_C}(z) \ne \text{Ø} \} $ ，使得 ${\partial _{A'}}(x') \ne {\partial _C}(x')$ 。

由定义16可知，当 $|{D_{{\rm{mcs}}}}| = 1$ 时， ${\rm{IDS}}$ 多特定类的广义决策约简将退化为单特定类的广义决策约简；当 $|{D_{{\rm{mcs}}}}| = |{U / {\{ d\} }}|$ 时， ${\rm{IDS}}$ 多特定类的广义决策约简将退化为全决策类的广义决策约简。

定理4　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，条件属性集 $A \subseteq C$ 为多特定类 ${D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ 的广义决策协调集当且仅当 $ \cup {D_{{\rm{mcs}}}}\cap $ $ {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，有 $(x,y) \notin {\rm{SIM}}(A)$ 。

证明：

充分性：因属性集 $A$ 是 ${\rm{IDS}}$ 多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策协调集，对 $\forall x \in \{ z \in U| \cup {D_{{\rm{mcs}}}} \cap {S_C}(z) \ne \text{Ø} \} $ 有 ${\partial _A}(x) = {\partial _C}(x)$ 。 $ \cup {D_{{\rm{mcs}}}} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _{\rm{C}}}(x)$ 时，必有 $f(y,d) \notin {\partial _A}(x)$ 成立，所以 $(x,y) \notin {\rm{SIM}}(A)$ 。

必要性：当 $ \cup {D_{{\rm{{\rm{mcs}}}}}} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，有 $(x,y) \notin {\rm{SIM}}(A)$ ，所以 $f(y,d) \notin {\partial _A}(x)$ 成立。因为当 $ \cup {D_{{\rm{{\rm{mcs}}}}}} \cap {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，必有 $f(y,d) \notin {\partial _A}(x)$ 成立，即 ${\partial _C}(x) \supseteq {\partial _A}(x)$ 。又因为当 $A \subseteq C$ 时，必有 ${\partial _A}(x) \supseteq {\partial _C}(x)$ 成立，所以对 $\forall x \in \{ z \in U| \cup$ $ {D_{{\rm{{\rm{mcs}}}}}} \cap {S_C}(z) \ne \text{Ø} \} $ ，有 ${\partial _A}(x) = {\partial _C}(x)$ 。因此条件属性集 $A \subseteq C$ 为多特定类 ${D_{{\rm{{\rm{mcs}}}}}} \subseteq {U / {\{ d\} }}$ 的广义决策协调集。证毕。

定义17　 四元组 ${\rm{{\rm{IDS}}}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合， $U = \{ {x_1},{x_2}, \cdots ,{x_n}\} $ ， $\forall x,y \in U$ , ${\rm{{\rm{IDS}}}}$ 多特定类 ${D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ 广义决策约简的差别矩阵为 $n \times n$ 的矩阵，记为 ${{{M}}_{{\rm{mcs}}}} = {({M_{{\rm{mcs}}}}(x,y))_{n \times n}}$ ，其中矩阵元素 ${M_{{\rm{mcs}}}}(x,y)$ 为

${M_{{\rm{mcs}}}}(x,y) = \left\{ {\begin{array}{*{20}{l}}\begin{array}{l} \!\!\! \{ a \in C|f(x,a) \ne f(y,a) \wedge \\ \quad f(x,a) \ne * \wedge f(y,a) \ne * \} \end{array},&{(x,y) \in {\Pi _{{\rm{mcs}}}}} \\ \text{Ø}, &\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!\!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\! \!\!\!\!{\text{其他}} \end{array}} \right.$

(12)

其中， $ {\Pi _{{\rm{mcs}}}} = \{ (x,y)|x,y \in U, \cup {D_{{\rm{mcs}}}} \cap{S_C}(x) \ne \text{Ø} \wedge $ $f(y,d) \notin $ $ {\partial _C}(x)\}$ 。

定理5　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，对多特定类 ${D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ ，条件属性集 $A \subseteq C$ 是多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策协调集当且仅当 $\forall (x,y) \in {\Pi _{{\rm{mcs}}}}$ 时，有 $A \cap {M_{{\rm{mcs}}}}(x,y) \ne \text{Ø} $ 。

证明：

充分性：设条件属性集 $A$ 是多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策协调集，对 $\forall (x,y) \in {\Pi _{{\rm{mcs}}}}$ ，当 $\cup {D_{{\rm{mcs}}}} \cap $ $ {S_C}(x) \ne \text{Ø} $ 且 $f(y,d) \notin {\partial _C}(x)$ 时，则有 $(x,y) \notin {\rm{SIM}}(A)$ ，所以一定存在 $a \in A$ 使得 $(x,y) \notin {\rm{SIM}}(\{ a\} )$ ，故 $a \in {M_{{\rm{mcs}}}}(x,y)$ ，所以 $A \cap {M_{{\rm{mcs}}}}(x,y) \ne \text{Ø}$ 。

必要性：设 $\exists (x,y) \in {\Pi _{{\rm{mcs}}}}$ ，使 $A \cap {M_{{\rm{mcs}}}}(x,y) = \text{Ø} $ 成立，则有 $(x,y) \in {\rm{SIM}}(A)$ ，又因对 $\forall x \in U$ ，当 $f(y,d) \notin $ $ {\partial _C}(x)$ 且 $ \cup {D_{{\rm{mcs}}}} \cap {S_C}(x) \ne \text{Ø} $ 时，必有 $(x,y) \notin {\rm{SIM}}(A)$ ，这与 $(x,y) \in {\rm{SIM}}(A)$ 矛盾。证毕。

定义18　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ 为多特定类， ${ M_{{\rm{mcs}}}}$ 为 ${\rm{IDS}}$ 多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策约简的差别矩阵，若 ${M_{{\rm{mcs}}}}(x,y) = \{ {a_1},{a_2}, \cdots ,{a_k}\} \ne \text{Ø} $ ，其中 $k$ 表示 ${M_{{\rm{mcs}}}}(x,y)$ 中属性的数量，用 $ \vee {M_{{\rm{mcs}}}}(x,y)$ 表示布尔函数 ${a_1} \vee {a_2} \vee \cdots \vee {a_k}$ ，对 $\forall {M_{{\rm{mcs}}}}(x,y) \ne \text{Ø} $ ， ${\rm{IDS}}$ 多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策约简的区分函数为

${\rm DF}({{ M}_{{\rm{mcs}}}}) = \wedge ( \vee {M_{{\rm{mcs}}}}(x,y))$

(13)

定理6　 四元组 ${\rm{IDS}} = (U,{\rm{AT}} = C \cup \{ d\} ,V,f)$ 为一个不完备决策系统， ${U / {\{ d\} }} = \{ {D_1},{D_2}, \cdots ,{D_{|{U / {\{ d\} }}|}}\} $ 为决策类集合，多特定类 ${D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ 的广义决策约简区分函数 ${\rm{DF}}({{ M}_{{\rm{mcs}}}}) = \wedge ( \vee {M_{{\rm{mcs}}}}(x,y))$ 的极小析取范式为 ${\rm{DF}}'({{ M}_{{\rm{mcs}}}}) = \mathop \vee \limits_{k = 1}^t (\mathop \wedge \limits_{s = 1}^{{q_k}} {a_s})$ ， $t$ 表示 ${\rm{DF}}'({{ M}_{{\rm{mcs}}}})$ 中的析取项数目， ${q_k}$ 表示 ${\rm{DF}}'({{ M}_{{\rm{mcs}}}})$ 中第 $k$ 个析取项中属性数目。设 ${A_k} = \{ {a_s}|s = 1,2, \cdots ,{q_k}\} $ ， $\{ {A_k}|k = 1,2, \cdots ,t\} $ 是多特定类 ${D_{{\rm{mcs}}}} \subseteq {U / {\{ d\} }}$ 的所有广义决策约简形成的集合。

证明：

对 $\forall k \leqslant t$ ， $\forall (x,y) \in {\Pi _{{\rm{mcs}}}}$ ，由极小析取范式定义可知 ${A_k} \cap {M_{{\rm{mcs}}}}(x,y) \ne \text{Ø} $ ，由定理5可知 ${A_k}$ 是 ${\rm{IDS}}$ 多特定类的广义决策协调集。

${\rm{DF}}'({{ M}_{{\rm{mcs}}}}) = \mathop \vee \limits_{k = 1}^t ({A_k})$ ，若在 ${A_k}$ 中删除一个元素得 ${A'_k}$ ， $\exists (x,y) \in {\Pi _{{\rm{mcs}}}}$ 使 ${A'_k} \cap {M_{{\rm{mcs}}}}(x,y) = \text{Ø} $ ，故 ${A'_k}$ 不是广义决策约简，因此 ${A_k}$ 是广义决策约简。因为区分函数中包含所有 ${M_{{\rm{mcs}}}}(x,y)$ ，故不存在其余广义决策约简。证毕。

根据不完备决策系统单特定类以及多特定类广义决策约简的相关定义，可依据相应的差别矩阵以及区分函数进行广义决策约简的求解，现给出实例如下。

例3　不完备决策系统 ${\rm{IDS}}$ 如表1所示，论域 $U = \{ {x_1},{x_2},{x_3},{x_4},{x_5},{x_6}\} $ ， $C = \{ {a_1},{a_2},{a_3},{a_4}\} $ 为条件属性集，决策属性集为 $\{ d\} $ 。

由例1易得， $IDS$ 在属性集 $C$ 上的相容类集合 ${U / {{\rm{SIM}}(C)}} = \{ \{ {x_1},{x_3}\} ,\{ {x_2},{x_5}\} ,\{ {x_1},{x_3}\} ,\{ {x_4}\} ,\{ {x_2},{x_5},{x_6}\}$ ， $\{ {x_5},{x_6}\} \} $ 。决策属性 $d$ 对论域 $U$ 划分决策类为 ${U / {\{ d\} }} = \{ \{ {x_1},{x_2}\} ,\{ {x_3},{x_4}\} ,\{ {x_5},{x_6}\} \} $ 。广义决策值为 $ {\partial _C}(U) =$ $ \{ {\partial _C}({x_1}),{\partial _C}({x_2}),{\partial _C}({x_3}),{\partial _C}({x_4}),{\partial _C}({x_5}),{\partial _C}({x_6})\} $ ，其中 $ {\partial _C}({x_1}) =$ $ \{ 1,2\} $ ， ${\partial _C}({x_2}) = \{ 1,3\} $ ， ${\partial _C}({x_3}) = \{ 1,2\} $ ， ${\partial _C}({x_4}) = \{ 2\} $ ， ${\partial _C}({x_5}) = $ $ \{ 1,3\} $ ， ${\partial _C}({x_6}) = \{ 3\} $ 。

对于单特定类 ${D_1} = \{ {x_1},{x_2}\} $ ，依据定义12构造 ${\rm{IDS}}$ 单特定类 ${D_1}$ 的差别矩阵为

${{ M}_1} = \left[ {\begin{array}{*{20}{c}} \text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} &{\{ {a_3}\} }&{\{ {a_3}\} } \\ \text{Ø} &\text{Ø} &{\{ {a_3}\} }&{\{ {a_1},{a_3},{a_4}\} }&\text{Ø} &\text{Ø} \\ \text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} &{\{ {a_3}\} }&{\{ {a_1},{a_3}\} } \\ \text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} \\ \text{Ø} &\text{Ø} &{\{ {a_3}\} }&{\{ {a_2},{a_3},{a_4}\} }&\text{Ø} &\text{Ø} \\ \text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} &\text{Ø} \end{array}} \right]$

根据 ${\rm{IDS}}$ 单特定类 ${D_1}$ 的广义决策约简的差别矩阵 ${{ M}_1}$ 可得对应的区分函数为

$\begin{gathered} {\rm DF}({{ M}_1}) = ({a_3}) \wedge ({a_1} \vee {a_3} \vee {a_4}) \wedge ({a_1} \vee {a_3}) \wedge\\ ({a_2} \vee {a_3} \vee {a_4}) = {a_3} \end{gathered} $

因此 ${\rm{IDS}}$ 的单特定类 ${D_1}$ 的广义决策约简为 $\{ {a_3}\} $ 。

对多特定类 ${D_{{\rm{mcs}}}} = \{ {D_1},{D_2}\} = \{ \{ {x_1},{x_2}\} ,\{ {x_3},{x_4}\} \} $ ，依据定义17构造 ${\rm{IDS}}$ 多特定类 ${D_{{\rm{mcs}}}}$ 的差别矩阵为

$ \begin{gathered} \;\;\;\;{{ M}_{{\rm{mcs}}}} = \\ \left[ {\begin{array}{*{20}{c}} \text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!{\{ {a_3}\} }&\!\!\!{\{ {a_3}\} } \\ \text{Ø} &\!\!\!\text{Ø} &\!\!\!{\{ {a_3}\} }&\!\!\!{\{ {a_1},{a_3},{a_4}\} }&\!\!\!\text{Ø} &\!\!\!\text{Ø} \\ \text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!{\{ {a_3}\} }&\!\!\!{\{ {a_1},{a_3}\} } \\ {\{ {a_4}\} }&\!\!\!{\{ {a_1},{a_3},{a_4}\} }&\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!{\{ {a_2},{a_3},{a_4}\} }&\!\!\!{\{ {a_2},{a_3}\} } \\ \text{Ø} &\!\!\!\text{Ø} &\!\!\!{\{ {a_3}\} }&\!\!\!{\{ {a_2},{a_3},{a_4}\} }&\!\!\!\text{Ø} &\!\!\!\text{Ø} \\ \text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} &\!\!\!\text{Ø} \end{array}} \right] \end{gathered} $

根据 ${\rm{IDS}}$ 多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策约简的差别矩阵 ${{ M}_{{\rm{mcs}}}}$ 可得对应的区分函数为

$\begin{gathered} { \rm DF}({{ M}_{{\rm{mcs}}}}) = ({a_3}) \wedge ({a_1} \vee {a_3} \vee {a_4}) \wedge ({a_1} \vee {a_3}) \wedge ({a_4}) \wedge \\ ({a_2} \vee {a_3} \vee {a_4}) \wedge ({a_2} \vee {a_3}) = {a_3} \wedge {a_4} \\ \end{gathered} $

因此 ${\rm{IDS}}$ 的多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策约简为 $\{ {a_3},{a_4}\} $ 。

因单特定类广义决策约简为多特定类广义约简的特例，所以仅给出多特定类的不完备决策系统广义决策约简算法如下。

算法1　 基于差别矩阵的多特定类不完备决策系统广义决策约简(multi-class-specific generalized decision preservation reduction based on discernibility matrix in incomplete decision systems, MGDRDM)

输入　一个不完备决策系统 $ {\rm{IDS}} = (U,{\rm{AT}} =$ $ C \cup \{ d\} ,V,f)$ ，多特定类 ${D_{{\rm{mcs}}}}$ 。

输出　多特定类 ${D_{{\rm{mcs}}}}$ 的不完备决策系统广义决策约简。

1)　 依据条件属性集 $C$ 计算论域 $U$ 中每个对象的相容类 ${S_C}({x_i})({x_i} \in U)$ ，根据决策属性 $d$ 计算决策类集合 ${U / {\{ d\} }}$ ；

2)　 依据相容类 ${S_C}({x_i})$ 计算每个对象的广义决策值 ${\partial _C}({x_i})$ ；

3)　 依据决策系统中每个对象的广义决策值 ${\partial _C}({x_i})$ 和多特定类 ${D_{{\rm{mcs}}}}$ 构造相应差别矩阵 ${{ M}_{{\rm{mcs}}}}$ ；

4)　 依据差别矩阵 ${{ M}_{{\rm{mcs}}}}$ 构造相应多特定类的广义决策约简区分函数 $DF({{ M}_{{\rm{mcs}}}})$ ；

5)　 利用吸收律和分配律将多特定类区分函数 ${\rm{DF}}({{ M}_{{\rm{mcs}}}})$ 转变为极小析取范式 ${\rm{DF}}'({{ M}_{{\rm{mcs}}}})$ ；

6)　 依据极小析取范式 ${\rm{DF}}'({{ M}_{{\rm{mcs}}}})$ 输出多特定类 ${D_{{\rm{mcs}}}}$ 的广义决策约简，算法结束。

算法1中，步骤1) 的时间复杂度为 $O(|C||U{|^2})$ ，步骤2) 的时间复杂度为 $O(|U{|^2})$ ，步骤3) 、步骤4) 的时间复杂度为 $O(|C||U{|^2})$ ，步骤5) 的过程是一个NP-hard问题，该步骤的时间复杂度为 $O(|C{|^{|U{|^2}}})$ ，因此算法1的整体时间复杂度为 $O(|C{|^{|U{|^2}}})$ 。

3 实验结果与分析

针对本文提出的多特定类不完备决策系统广义决策约简算法进行实验验证与分析。本节实验选择与经典不完备决策系统广义决策约简针对约简结果、占用空间以及约简效率进行比较。

本节采用6组标准UCI数据集进行实验，数据集从 http://archive.ics.uci.edu/ml/datasets.php处下载。数据集使用WEKA3.6进行等频率离散化预处理，因某些原始数据中存在缺失数据数量极少，无法直接作为实验使用，所以针对缺失数据使用相应属性下出现频率最高属性值作为替换，针对名词性数据使用整数作为替换。数据集详细信息如表2所示。表2中，ID表示数据集编号，“数据集”表示数据集名称， $|U|$ 表示数据集中对象数目， $|C|$ 表示数据集中条件属性数目， $|U/\{ d\} |$ 表示数据集中决策类数目。本节实验环境：操作系统Windows7-64 bit；CPU Intel Core i5-6500(3.2 GHz)；内存4 GB；运行环境Python 3.6；开发工具PyCharm。

因本节采用UCI标准数据集，预处理之后数据集所表示的决策系统为完备决策系统，所以需要将其转为不完备决策系统。采用文献[16]中的方法对完备决策系统进行处理，具体处理方式为：除决策属性之外，每个条件属性对应列选取10%的属性值进行缺失处理，缺失值使用*表示。

3.1 约简结果对比

两种约简算法所得平均约简长度对比如表3所示。表3中，“全决策类”表示经典全决策类约简算法所得约简结果，“单特定类”表示MGDRDM算法选定一个特定类时所得约简结果，“多特定类”表示MGDRDM算法选定多个特定类时所得约简结果，“决策值”表示对应算法选取的一个或多个特定类所表现决策值，“平均约简长度”表示对应算法所得约简的平均约简长度。

由表3可知，相比全部决策类，当选定特定类数量较少时，平均约简长度往往会比全决策类所得平均约简长度要短。若多特定类选择为所有决策类，则算法将退化为全决策类约简，平均约简长度不会缩短。

3.2 占用空间对比

本节通过比较两种算法生成的差别矩阵中非空属性集占比进而比较两种算法占用空间大小。两种算法生成差别矩阵中非空属性集占比如表4所示，其中“占比(%)”表示对应不同算法构造差别矩阵中非空属性集所占比例。

由表4可知，当选定一个或者几个特定类，特定类数量相对全部决策类数量较少时，MGDRDM算法所构造差别矩阵中非空属性集占比要小于经典算法构造差别矩阵中的非空属性集占比。因此，在保证约简目标不变的前提下，MGDRDM算法所构造差别矩阵占用空间要小于经典算法构造差别矩阵占用空间。除此之外，利用差别矩阵中非空属性集构造区分函数以及求取极小析取范式时，MGDRDM算法也将占用更小空间。当选定特定类为全部决策类时，MGDRDM算法将退化为全决策类约简，占用空间不会减小。

3.3 约简效率对比

本节将6组数据集，依据随属性数目递增的时间消耗进行经典不完备决策系统广义决策约简与MGDRDM算法之间约简效率对比。约简效率如图1所示，其中“全决策类”表示经典全类不完备决策系统广义决策约简算法随属性数目增加的约简耗时变化曲线，“单特定类”和“多特定类”则表示MGDRDM算法分别选定一个和多个特定类随属性数目增加的约简耗时变化曲线，“决策值”表示选定特定类所表现的决策值。

由图1可知，选取特定类数量相对全部决策类数量较少时，约简效率相较对比算法会有明显的提升，这是由于多特定类广义决策约简的差别矩阵中非空属性集的数目小于全决策类广义决策约简的差别矩阵中非空属性集的数目，所以MGDRDM算法在构造差别矩阵时耗时会有所减少。另外，因多特定类广义决策约简的差别矩阵中非空属性集数目偏少，所以构造区分函数以及求取极小析取范式耗时相对较少，因此约简效率更高。除此之外，随着属性数目的增加，算法之间耗时差距越发明显，这是由于随着属性数目的增加，差别矩阵也愈加复杂，使得构造区分函数以及计算极小析取范式时计算量增大，而且MGDRDM算法构造差别矩阵中非空属性集数目较少，所以耗时增长缓慢，两个算法之间耗时差距越明显。当多特定类选择为所有决策类时，算法退化为全类约简，此时约简效率并无明显提升。

某些情况下，添加属性求解约简反而会使耗时减少，这可能是因为在添加属性之后构造差别矩阵的过程中产生了较添加属性之前更短的非空属性集，这使得构造区分函数以及求取极小析取范式的过程耗时减少，所以在某些情况添加属性反而求解更快。

4 结束语

属性约简作为数据分析预处理的重要手段之一，能够提取更加泛化的规则，压缩数据规模，使得数据分析更加准确、高效，具有重要意义。

本文提出了基于多特定类的不完备决策系统广义决策约简基本理论框架，定义了多特定类的不完备决策系统广义决策约简基本定义，并构造相应差别矩阵以及区分函数，提出基于差别矩阵的约简算法并通过6组UCI数据集验证了算法的有效性。本文提出约简算法是基于差别矩阵求取所有约简，为提升算法效率，差别矩阵优化是将来研究的重要问题。