不完备决策系统下的多特定类广义决策约简

唐玉凯，张楠，童向荣，张小峰

（1.烟台大学 数据科学与智能技术山东省高校重点实验室，山东 烟台 264005; 2.烟台大学 计算机与控制工程学院，山东 烟台 264005; 3.鲁东大学 信息与电气工程学院，山东 烟台 264025）

粗糙集理论[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]四元组 D S=(U,AT=C∪D,V,f) 为一个决策系统，其中U表示所有对象的非空有限集合，称之为论域；C表示条件属性的非空有限集合；D表示决策属性的非空有限集合，C∩D=Ø；表示属性a∈AT 的值域；f:U×AT →V是一个信息函数，它使得任意对象的任意一个属性都有一个信息值，f(x,a) 表示对象x∈U在属性a∈AT 上的取值。

定义2[16]四元组 D S=(U,AT=C∪D,V,f) 为一个决策系统，对任意非空属性集B⊆AT 导出论域U上的不可区分关系 I ND(B) 定义为

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

定义3[16]四元组 D S=(U,AT=C∪D,V,f) 为一个决策系统，若存在条件属性c∈C使得Vc含有缺失值，则称该决策系统为不完备决策系统，用 I DS=(U,AT=C∪D,V,f) 表示，Vc中的缺失值使用 *表示。

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

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

其中f(x,a) 表示对象x∈U在属性a∈A上的取值。

相容关系 S IM(A) 具有以下性质：

性质1[20]四元组IDS=(U,AT=C∪{d},V,f)为一个不完备决策系统，对 ∀A⊆C，有：

性质2四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，对 ∀A⊆C，S IM(A) 满足：

1) 自反性，对 ∀x∈U，有 (x,y)∈SIM(A)；

2) 对称性，对 ∀x,y∈U，若 (x,y)∈SIM(A)，则(y,x)∈SIM(A)；

3) 非传递性，对 ∀x,y,z∈U，若(x,y)∈SIM(A)且 (y,z)∈SIM(A)，(x,z)∈SIM(A) 不一定成立。

设SA(x)={y∈U|(x,y)∈SIM(A)}，其中条件属性集A⊆C，SA(x) 表示通过条件属性集A与x可能不可区分的对象的最大集合。设DA(x)={y∈U|(x,y)∉SIM(A)} ， 其 中 条 件 属 性 集A⊆C，DA(x) 表示通过条件属性集A与x可能可区分的对象的最大集合。对 ∀x∈U，有SA(x)∩DA(x)=Ø且SA(x)∪DA(x)=U。

在 I DS 中，对 ∀A⊆C，有U/SIM(A) 表示分类且U/SIM(A)={SA(x)|x∈U} 。U/SIM(A) 中的每 一个元素SA(x)(x∈U) 被称为相容类，且满足 ∪U/SIM(A)=U。

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

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

例1不完备决策系统 IDS 如表1 所示，论域U={x1,x2,x3,x4,x5,x6}，C={a1,a2,a3,a4} 为条件属性集 ，决策属性集为 {d}。

表1 不完备决策系统Table 1 An incomplete decision system

由定义4 得 I DS 在条件属性集C上相容类集合

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

定义6[20]四元组IDS=(U,AT=C∪{d},V,f)为一个不完备决策系统，对 ∀x∈U，关于条件属性集A⊆C的广义决策值定义为

在 I DS 中， ∂A(x) 表示对象x关于条件属性集A的所有可能决策值的集合。

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

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

1)对 ∀x∈U，有 ∂A(x)=∂C(x)；

2)对 ∀A′⊂A， ∃x′∈U，有 ∂A′(x′)≠ ∂A(x′)。

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

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

定义8[20]四元组IDS=(U,AT=C∪{d},V,f)为一个不完备决策系统，U={x1,x2,···,xn}， ∀x,y∈U，IDS 广义决策约简的差别矩阵为n×n的矩阵，记为MGEN=(MGEN(x,y))n×n， 其中矩阵元素MGEN(x,y) 为

定义9[20]四元组IDS=(U,AT=C∪{d},V,f)为一个不完备决策系统，MGEN为 I DS 广义决策约简的差别矩阵，若MGEN(x,y)={a1,a2,···,ak}≠ Ø，其中k表示MGEN(x,y) 中属性的数量，用 ∨MGEN(x,y)表示布尔函数a1∨a2∨···∨ak，对 ∀MGEN(x,y)≠ Ø，IDS 广义决策约简的区分函数为

例2不完备决策系统 IDS 如表1 所示，论域U={x1,x2,x3,x4,x5,x6}，C={a1,a2,a3,a4} 为条件属性集，决策属性集为 {d}。

由定义6 得 I DS 在条件属性集C上广义决策值 ∂C(U)={∂C(x1),∂C(x2),∂C(x3),∂C(x4),∂C(x5),∂C(x6)}，其 中 ∂C(x1)={1,2}， ∂C(x2)={1,3}， ∂C(x3)={1,2} ，∂C(x4)={2}，∂C(x5)={1,3}，∂C(x6)={3} 。 I DS 中所有决策类的广义决策约简差别矩阵为

根据 I DS 所有决策类的广义决策约简的差别矩阵MGEN可得对应的区分函数为

因此, IDS 的所有决策类的广义决策约简为{a1,a3,a4}。

2 多特定类广义决策约简

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

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

定义10四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决 策 类 集 合 ， 对 ∀Di∈U/{d},i=1,2,···,|U/{d}|，∀A⊆C，∀x∈{z∈U|Di∩SC(z)≠ Ø}， 若满足 ∂A(x)=∂C(x)，则称条件属性集A为单特定类Di的广义决策协调集。

定义11四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决 策类 集 合 ， 对 ∀Di∈U/{d}，i=1,2,···,|U/{d}|， 若∀A⊆C为单特定类Di的广义决策约简当且仅当满足以下两个条件：

2) ∀A′⊂A， ∃x′∈{z∈U|Di∩SC(z)≠ Ø} ， 使 得 ∂A′(x′)≠ ∂C(x′)。

定理1四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，对 ∀Di∈U/{d}，i=1,2,···,|U/{d}|，条件属性集A⊆C为单特定类Di的广义决策协调集当且仅当Di∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时，有(x,y)∉SIM(A)。

证明：

充分性：因条件属性集A是 I DS 单特定类Di的广义决策协调集，对 ∀x∈{z∈U|Di∩SC(z)≠ Ø}，有 ∂A(x)=∂C(x) 。当Di∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x)，即f(y,d)∉ ∂A(x)， 即 (x,y)∉SIM(A)。

必要性：当Di∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时，有 (x,y)∉SIM(A)， 所以有f(y,d)∉ ∂A(x) 成立。当满足Di∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时，必有f(y,d)∉∂A(x) ， 即 ∂C(x)⊇ ∂A(x) ， 又 因 为A⊆C， ∂A(x)⊇ ∂C(x)，所以当 ∀x∈{z∈U|Di∩SC(z)≠ Ø} 时，有 ∂A(x)=∂C(x)。因此条件属性集A⊆C为单特定类Di∈U/{d} 的广义决策协调集。证毕。

定义12四组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，U={x1,x2,···,xn}， ∀x,y∈U,I DS 单特定类Di∈U/{d} 广义决策约简的差别矩阵为n×n的矩阵，记为Mi=(Mi(x,y))n×n，其中矩阵元素Mi(x,y) 为

Πi={(x,y)|x,y∈U,Di∩SC(x)≠ Ø∧f(y,d)∉∂C(x)}

i=1,2,···,|U/{d}|

其中， ，。IDS=(U,AT=C∪{d},V,f)U/{d}={D1,D2,···,D|U/{d}|}U={x1,x2,···,xn} ∀Di∈U/{d}i=1,2,···,|U/{d}|A⊆CDi∀(x,y)∈Πi A∩Mi(x,y)≠Ø

定理2四元组 为一个不完备决策系统， 为决策类集合，论域 ，对 ，

，条件属性集 是单特定类的广义决策协调集当且仅当 时，有。

证明：

充分性：设条件属性集A是单特定类Di的广义决策协调集，对于 ∀(x,y)∈ Πi，若Di∩SC(x)≠ Ø且f(y,d)∉ ∂C(x) ，则有 (x,y)∉SIM(A)，所以一定存在a∈A使 得 (x,y)∉SIM({a}) ， 故a∈Mi(x,y)， 所 以A∩Mi(x,y)≠Ø。

必要性：设 ∃ (x,y)∈ Πi， 使得A∩Mi(x,y)=Ø，则有 (x,y)∈SIM(A) 成 立 ， 又 因 为 对 ∀x∈U， 当Di∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时，必有 (x,y)∉SIM(A)，这与 (x,y)∈SIM(A) 矛盾。证毕。

定义13四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，对 ∀Di∈U/{d}，i=1,2,···,|U/{d}|，Mi为 I DS 单特定类Di的广义决策约简的差 别 矩阵，若Mi(x,y)={a1,a2,···,ak}≠ Ø， 其中k表示Mi(x,y) 中属性的数量，用 ∨Mi(x,y) 表 示布尔函数a1∨a2∨ · · · ∨ak，对 ∀Mi(x,y)≠ Ø， IDS 单特定类Di的广义决策约简的区分函数为

定理3四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，对 ∀Di∈U/{d}，i=1,2,···,|U/{d}|，IDS单特定类Di的广义决策约简区分函数DF(Mi)=∧(∨Mi(x,y)) 的极小析取范式为表示 D F′(Mi) 中的析取项数目，qk表示 D F′(Mi) 中第k个析取项中属性数目。记Ak={as|s=1,2,···,qk}，则 {Ak|k=1,2,···,t} 是单特定类Di∈U/{d} 的所有广义决策约简形成的集合。

证明：

对 ∀k≤t， ∀ (x,y)∈ Πi，由极小析取范式定义可知Ak∩Mi(x,y)≠ Ø ，由定理2 可知Ak是广义决策协调集。若在Ak中删除一个元素形成则故不是广义决策约简，因此Ak是广义决策约简。因为区分函数中包含所有Mi(x,y)，故不存在其余广义决策约简。证毕。

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

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

定义14四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统为决策类集合，则多特定类Dmcs定义为

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

定义15四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决 策 类 集 合 ， 对 ∀Dmcs⊆U/{d} ， ∀A⊆C，∀x∈{z∈U|∪Dmcs∩SC(z)≠ Ø} ，若 ∂A(x)=∂C(x)，则称条件属性集A为多特定类Dmcs的广义决策协调集。

定义16四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，对 ∀Dmcs⊆U/{d} ，条件属性集A⊆C为多特定类Dmcs的广义决策约简当且仅当满足以下两个条件：

1) 对 ∀x∈{z∈U|∪Dmcs∩SC(z)≠ Ø}， 都有 ∂A(x)=∂C(x)；

2) ∀A′⊂A， ∃x′∈{z∈U|∪Dmcs∩SC(z)≠ Ø}，使得

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

定理4四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，条件属性集A⊆C为多特定类Dmcs⊆U/{d} 的广义决策协调集当且仅当 ∪Dmcs∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时，有 (x,y)∉SIM(A)。

证明：

充分性：因属性集A是 I DS 多特定类Dmcs的广义决策协调集，对 ∀x∈{z∈U|∪Dmcs∩SC(z)≠Ø}有 ∂A(x)=∂C(x) 。 ∪Dmcs∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x)时，必有f(y,d)∉ ∂A(x) 成立，所以 (x,y)∉SIM(A)。

必要性：当 ∪Dmcs∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x)时，有 (x,y)∉SIM(A) ，所以f(y,d)∉ ∂A(x) 成立。因为 当 ∪Dmcs∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时 ， 必 有f(y,d)∉∂A(x) 成立 ， 即 ∂C(x)⊇∂A(x)。 又 因 为当A⊆C时，必有 ∂A(x)⊇ ∂C(x) 成立，所以对 ∀x∈{z∈U|∪Dmcs∩SC(z)≠ Ø} ，有 ∂A(x)=∂C(x)。因此条件属性集A⊆C为多特定类Dmcs⊆U/{d} 的广义决策协调集。证毕。

定义17四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，U={x1,x2,···,xn} ， ∀x,y∈U,I D S 多特定类Dmcs⊆U/{d} 广义决策约简的差别矩阵为n×n的矩阵，记为Mmcs=(Mmcs(x,y))n×n，其中矩阵元素Mmcs(x,y) 为

其中，Πmcs={(x,y)|x,y∈U,∪Dmcs∩SC(x)≠Ø∧f(y,d)∉∂C(x)}。

定理5四元组 IDS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，对多特定类Dmcs⊆U/{d}，条件属性集A⊆C是多特定类Dmcs的广义决策协调集当且仅当 ∀ (x,y)∈ Πmcs时，有A∩Mmcs(x,y)≠ Ø。

证明：

充分性：设条件属性集A是多特定类Dmcs的广 义 决 策 协 调 集 ， 对 ∀(x,y)∈Πmcs， 当 ∪Dmcs∩SC(x)≠ Ø 且f(y,d)∉ ∂C(x) 时，则有 (x,y)∉SIM(A)，所 以 一定存 在a∈A使 得 (x,y)∉SIM({a})， 故a∈Mmcs(x,y) ，所以A∩Mmcs(x,y)≠ Ø 。

必要性：设 ∃ (x,y)∈ Πmcs， 使A∩Mmcs(x,y)=Ø 成立，则有 (x,y)∈SIM(A) ， 又因对 ∀x∈U，当f(y,d)∉∂C(x) 且 ∪Dmcs∩SC(x)≠ Ø 时 ， 必 有 (x,y)∉SIM(A)，这与 (x,y)∈SIM(A) 矛盾。证毕。

定义18四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，Dmcs⊆U/{d} 为多特定类，Mmcs为 I DS 多特定类Dmcs的广义决策约简的差别矩阵，若Mmcs(x,y)={a1,a2,···,ak}≠ Ø ，其中k表示Mmcs(x,y) 中属性的数量，用 ∨Mmcs(x,y) 表示布尔函数a1∨a2∨ ···∨ak，对 ∀Mmcs(x,y)≠ Ø， I DS 多特定类Dmcs的广义决策约简的区分函数为

定理6四元组 I DS=(U,AT=C∪{d},V,f) 为一个不完备决策系统，U/{d}={D1,D2,···,D|U/{d}|} 为决策类集合，多特定类Dmcs⊆U/{d} 的广义决策约简区分函数 DF(Mmcs)=∧(∨Mmcs(x,y)) 的极小析取范式为 DF′(Mmcs)=k∨=t

1(s∧q=k1as)，t表示 D F′(Mmcs) 中 的析取项数目，qk表示 D F′(Mmcs) 中第k个析取项中属性数目。设Ak={as|s=1,2,···,qk}，{Ak|k=1,2,···,t}是多特定类Dmcs⊆U/{d} 的所有广义决策约简形成的集合。

证明：

对 ∀k≤t， ∀ (x,y)∈ Πmcs，由极小析取范式定义可知Ak∩Mmcs(x,y)≠ Ø， 由定理5 可知Ak是 I DS 多特定类的广义决策协调集。若在Ak中删除一个元素得使，故不是广义决策约简，因此Ak是广义决策约简。因为区分函数中包含所有Mmcs(x,y)，故不存在其余广义决策约简。证毕。

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

例3不完备决策系统 I DS 如表1 所示，论域为条件属性集，决策属性集为 {d}。

由例1 易得，IDS在属性集C上的相容类集合U/SIM(C)={{x1,x3},{x2,x5},{x1,x3},{x4},{x2,x5,x6}，{x5,x6}} 。决策属性d对论域U划分决策类为U/{d}={{x1,x2},{x3,x4},{x5,x6}}。 广义决策值为 ∂C(U)={∂C(x1),∂C(x2),∂C(x3),∂C(x4),∂C(x5),∂C(x6)}， 其中 ∂C(x1)={1,2}，∂C(x2)={1,3}，∂C(x3)={1,2}，∂C(x4)={2}，∂C(x5)=

对于单特定类D1={x1,x2}，依据定义12 构造IDS 单特定 类D1的差 别矩阵为

根 据 IDS 单 特 定 类D1的 广 义 决 策 约 简 的 差别矩阵M1可得对应的区分函数为

因此 I DS 的单特定类D1的广义决策约简为 {a3}。

对多特定类Dmcs={D1,D2}={{x1,x2},{x3,x4}}，依据定义17 构造 I DS 多特定类Dmcs的差别矩阵为

根据 I DS 多特定类Dmcs的广义决策约简的差别矩阵Mmcs可得对应的区分函数为

因此 I DS 的多特定类Dmcs的广义决策约简为{a3,a4}。

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

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

输入一个不完备决策系统IDS=(U,AT=C∪{d},V,f) ，多特定类Dmcs。

输出多特定类Dmcs的不完备决策系统广义决策约简。

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

2) 依据相容类SC(xi) 计算每个对象的广义决策值 ∂C(xi)；

3) 依据决策系统中每个对象的广义决策值∂C(xi) 和多特定类Dmcs构造相应差别矩阵Mmcs；

4) 依据差别矩阵Mmcs构造相应多特定类的广义决策约简区分函数DF(Mmcs)；

5) 利用吸收律和分配律将多特定类区分函数 D F(Mmcs) 转变为极小析取范式 D F′(Mmcs)；

6) 依据极小析取范式 D F′(Mmcs) 输出多特定类Dmcs的广义决策约简，算法结束。

算法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；开发工具Py Charm。

表2 数据集Table 2 Data Sets

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

3.1 约简结果对比

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

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

表3 平均约简长度Table 3 Average reduct length

3.2 占用空间对比

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

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

表4 差别矩阵非空属性集占比Table 4 The proportion of non-empty attribute sets in the discernibility matrix

3.3 约简效率对比

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

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

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

图1 约简效率Fig.1 Reduction efficiency

4 结束语

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

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