第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201905059 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190719.1623.006html 不完备决策系统下的多特定类广义决策约简 唐玉凯2，张楠2，童向荣2，张小峰3 (1.烟台大学数据科学与智能技术山东省高校重点实验室，山东烟台264005,2.烟台大学计算机与控制工程 学院，山东烟台264005：3.鲁东大学信息与电气工程学院，山东烟台264025) 摘要：属性约简是粗糙集理论研究中最重要的领域之一。经典的不完备决策系统广义决策约简关注决策系 统中的所有决策类，而在实际应用中，决策者往往只关注一个或者几个特定决策类。针对以上问题，提出基于 多特定类的不完备决策系统广义决策约简理论框架。首先，定义了单特定类的不完备决策系统广义决策约简 的相关概念，提出并证明相关定理，构造相应差别矩阵和区分函数。其次，将单特定类的广义决策约简推广到 多特定类，提出基于差别矩阵的多特定类的不完备决策系统广义决策约简算法。最后，采用6组UCI数据集进 行实验。实验结果表明，相对全部决策类数量，当选定特定类数量较少时，平均约简长度有不同程度的缩短， 占用空间有所减小，约简效率有不同程度的提升。 关键词：粗糙集；属性约简；不完备；决策系统：相容关系：多特定类；广义决策约简；差别矩阵 中图分类号：TP181文献标志码：A文章编号：1673-4785(2019)06-1199-10 中文引用格式：唐玉凯，张楠，童向荣，等.不完备决策系统下的多特定类广义决策约简J.智能系统学报，2019,14(6)： 1199-1208. 英文引用格式：TANG Yukai,,ZHANG Nan,TONG Xiangrong,ctal.The multi-clas-specific generalized decision preservation re- duction in incomplete decision systems[J].CAAI transactions on intelligent systems,2019,14(6):1199-1208. The multi-class-specific generalized decision preservation reduction in incomplete decision systems TANG Yukai2,ZHANG Nan2,TONG Xiangrong,ZHANG Xiaofeng (1.Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes,Yantai University,Yantai 264005,China;2.School of Computer and Control Engineering,Yantai University,Yantai 264005,China;3.School of Information and Electrical Engineering,Ludong University,Yantai 264025,China) Abstract:Attribute reduction has an important place in rough set theory.The method of classical generalized decision preservation reduction in incomplete decision systems is to find the reducts of all decision classes.In practical applica- tions,however,the decision makers may focus on one or several decision classes.To fill this gap,the theoretical frame- work of multi-class-specific generalized decision preservation reduction in incomplete decision systems is proposed. First,the single-class-specific generalized decision preservation reduction in incomplete decision systems is defined.Re- lated theorems are proposed and proven,and the corresponding discernibility matrix and function are constructed.Then, the single-class-specific generalized decision preservation reduction is extended to the multi-class-specific generalized decision preservation reduction in incomplete decision systems.The algorithm of the multi-class-specific generalized decision preservation reduction based on discernibility matrix in incomplete decision systems (MGDRDM)is proposed. Finally,six datasets from UCI were used for experiments.The experimental results show that when the number of selec- ted specific classes is less than all the decision classes,the average length of reducts will be shortened to varying de- grees,the space used will be reduced,and the time efficiency will be roughly improved. Keywords:rough sets;attribute reduction;incomplete;decision systems;tolerance relation;multi-class-specific;gener- alized decision preservation reduction,discernibility matrix 收稿日期：2019-05-28.网络出版日期：2019-07-19. 基金项目：国家自然科学基金项目(61572418.61572419.61873117. 粗糙集理论11是于1982年由波兰科学家 61403329):山东省自然科学基金项目(ZR2018BA004, ZR2016FM42). Pawlak提出的一种用于分析和处理不确定或不精 通信作者：张楠.E-mail:changnan0851@163.com. 确数据的数学工具。目前，粗糙集理论正被广泛
DOI: 10.11992/tis.201905059 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190719.1623.006.html 不完备决策系统下的多特定类广义决策约简 唐玉凯1,2，张楠1,2，童向荣1,2，张小峰3 （1. 烟台大学 数据科学与智能技术山东省高校重点实验室，山东 烟台 264005; 2. 烟台大学 计算机与控制工程 学院，山东 烟台 264005; 3. 鲁东大学 信息与电气工程学院，山东 烟台 264025） 摘 要：属性约简是粗糙集理论研究中最重要的领域之一。经典的不完备决策系统广义决策约简关注决策系 统中的所有决策类，而在实际应用中，决策者往往只关注一个或者几个特定决策类。针对以上问题，提出基于 多特定类的不完备决策系统广义决策约简理论框架。首先，定义了单特定类的不完备决策系统广义决策约简 的相关概念，提出并证明相关定理，构造相应差别矩阵和区分函数。其次，将单特定类的广义决策约简推广到 多特定类，提出基于差别矩阵的多特定类的不完备决策系统广义决策约简算法。最后，采用 6 组 UCI 数据集进 行实验。实验结果表明，相对全部决策类数量，当选定特定类数量较少时，平均约简长度有不同程度的缩短， 占用空间有所减小，约简效率有不同程度的提升。 关键词：粗糙集；属性约简；不完备；决策系统；相容关系；多特定类；广义决策约简；差别矩阵 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2019)06−1199−10 中文引用格式：唐玉凯, 张楠, 童向荣, 等. 不完备决策系统下的多特定类广义决策约简 [J]. 智能系统学报, 2019, 14(6): 1199–1208. 英文引用格式：TANG Yukai, ZHANG Nan, TONG Xiangrong, et al. The multi-class-specific generalized decision preservation reduction in incomplete decision systems[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1199–1208. The multi-class-specific generalized decision preservation reduction in incomplete decision systems TANG Yukai1,2 ，ZHANG Nan1,2 ，TONG Xiangrong1,2 ，ZHANG Xiaofeng3 (1. Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes, Yantai University, Yantai 264005, China; 2. School of Computer and Control Engineering, Yantai University, Yantai 264005, China; 3. School of Information and Electrical Engineering, Ludong University, Yantai 264025, China) Abstract: Attribute reduction has an important place in rough set theory. The method of classical generalized decision preservation reduction in incomplete decision systems is to find the reducts of all decision classes. In practical applications, however, the decision makers may focus on one or several decision classes. To fill this gap, the theoretical framework of multi-class-specific generalized decision preservation reduction in incomplete decision systems is proposed. First, the single-class-specific generalized decision preservation reduction in incomplete decision systems is defined. Related theorems are proposed and proven, and the corresponding discernibility matrix and function are constructed. Then, the single-class-specific generalized decision preservation reduction is extended to the multi-class-specific generalized decision preservation reduction in incomplete decision systems. The algorithm of the multi-class-specific generalized decision preservation reduction based on discernibility matrix in incomplete decision systems (MGDRDM) is proposed. Finally, six datasets from UCI were used for experiments. The experimental results show that when the number of selected specific classes is less than all the decision classes, the average length of reducts will be shortened to varying degrees, the space used will be reduced, and the time efficiency will be roughly improved. Keywords: rough sets; attribute reduction; incomplete; decision systems; tolerance relation; multi-class-specific; generalized decision preservation reduction; discernibility matrix 粗糙集理论[1-5] 是于 1982 年由波兰科学家 Pawlak 提出的一种用于分析和处理不确定或不精 确数据的数学工具。目前，粗糙集理论正被广泛 收稿日期：2019−05−28. 网络出版日期：2019−07−19. 基金项目：国家自然科学基金项目 (61572418，61572419，61873117， 61403329)；山东省自然科学基金项目 (ZR2018BA004， ZR2016FM42). 通信作者：张楠. E-mail：zhangnan0851@163.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019
·1200· 智能系统学报 第14卷 应用于人工智能、机器学习、模式识别、数据挖掘 框架，定义了单特定类的不完备决策系统广义决 等领域，并取得了丰硕的研究成果。属性约简 策约简的相关概念，提出并证明相关定理，构造 是粗糙集理论的核心研究内容之一。属性约简的 相应差别矩阵和区分函数，并将单特定类推广到 本质是在保持原决策系统某种分辨能力不变的前 多特定类，提出基于差别矩阵的多特定类不完备 提下，删除冗余属性，获取最小属性子集。 决策系统广义决策约简算法并通过实验验证了算 在决策系统中，若某个条件属性值存在缺失， 法的有效性。 则称该决策系统为不完备决策系统。目前，国内 外相关学者针对不完备决策系统做了大量的研究 1基本概念 工作。2002年，Liang等提出了基于粗糙熵的 为方便进一步研究基于多特定类的不完备决 不完备决策系统约简算法。2010年，周献中等 策系统广义决策约简，本节将给出不完备决策系 介绍了在不完备决策系统下基于相容关系和相似 统及广义决策约简的相关基本概念。 关系的粗糙集模型及其拓展模型，通过引入相容 1.1不完备决策系统及其上下近似 矩阵和相似矩阵，系统研究了相应的粗计算、属 定义1四元组DS=(U,AT=CUD,Vf)为 性约简以及决策规则提取的矩阵算法。2010年 Qian等1提出了基于极大相容块的不协调不完 一个决策系统，其中U表示所有对象的非空有限 备决策系统下的上下近似约简概念并给出构造相 集合，称之为论域：C表示条件属性的非空有限集 应差别矩阵方法。2014年，Shu等u提出了不完 合；D表示决策属性的非空有限集合，CnD=O; 备决策系统下基于候选属性重要度的快速求属性 V=UVa,Va表示属性a∈AT的值域；f:U×AT→V aEAT 约简方法。2015年，Qian等m提出了基于紧凑差 是一个信息函数，它使得任意对象的任意一个属 别矩阵的动态不完备决策系统下的特征选择方 性都有一个信息值，fx,a)表示对象x∈U在属性 法。2018年，Xe等提出了不完备决策系统下 a∈AT上的取值。 不协调度的概念，证明了基于不协调度与基于正 定义2四元组DS=(U,AT=CUD,Vf月为 域的属性约简等价。 一个决策系统，对任意非空属性集B二AT导出论 在不完备决策系统中，具有相同条件属性的 域U上的不可区分关系ND(B)定义为 对象可能决策出多个不同的决策值，每个对象所 IND(B)={(x,y∈U×UIYb∈B,fx,b)=fG,b}(I) 有可能决策出的决策值称为该对象的广义决策 不可区分关系是一个满足自反性、对称性和 值，广义决策约简旨在保持约简前后每个对象的 传递性的等价关系。由不可区分关系ND(B)导 广义决策值不变。1993年，Skowron1提出了广 出对论域U的划分为UND(B)={[xslx∈U,简 义决策的概念。1998年，Kryszkiewicz2o1讨论了 记为UIB,其中[xs表示包含x的等价类。 不完备决策系统下的广义决策约简问题，给出相 定义31四元组DS=(U,AT=CUD,Vf)为 关决策规则的提取方法，并提出了基于差别矩阵四 一个决策系统，若存在条件属性c∈C使得V。含 的广义决策约简方法。上述研究考虑决策属性的 有缺失值，则称该决策系统为不完备决策系统， 所有决策类，而在实际应用中，决策者往往只关 用DS=(U,AT=CUD,V,f)表示，V中的缺失值使 注部分决策类。为此相关学者针对局部约简即特 用*表示。 定类约简做了大量研究。尹继亮等2讨论了区 在不完备决策系统DS中，决策属性d∈D的 间值系统下的局部属性约简。Qian等21为解决 值域V不含有缺失值。若决策属性集D中决策 经典粗糙集无法处理具有有限标记的大数据集的 属性数目为1，则称DS为不完备单决策系统；若 问题，引入了局部粗糙集的概念。Liu等2！提出 D中决策属性数目大于1，则称DS为不完备多 了第1决策类下近似约简概念并提出相应差别矩 决策系统。为表述方便，本文只考虑不完备单决 阵构造方法。 策系统的情况，即DS=(U,AT=CU{d,V,f)的 综合上述研究，文献[20]研究讨论了不完备 情况。 决策系统所有决策类的广义决策约简，文献[22] 定义42o1四元组DS=(U,AT=CU{d,Vf) 只在区间值系统下对局部约简进行了研究，文 为一个不完备决策系统，对任意条件属性集 献[24]在完备系统下对单特定类的正域约简进行 A二C,定义其相容关系为 了研究。然而，基于多特定类的不完备决策系统 SM(A)={(x,y)∈U×UIHa∈A,f(x,a)=f(y,a)V 下广义决策约简未见报道。为此，本文提出基于 f(x,a)=*v f(y,a)=* 多特定类的不完备决策系统广义决策约简的理论 (2)
应用于人工智能、机器学习、模式识别、数据挖掘 等领域，并取得了丰硕的研究成果。属性约简[6-12] 是粗糙集理论的核心研究内容之一。属性约简的 本质是在保持原决策系统某种分辨能力不变的前 提下，删除冗余属性，获取最小属性子集。 在决策系统中，若某个条件属性值存在缺失， 则称该决策系统为不完备决策系统。目前，国内 外相关学者针对不完备决策系统做了大量的研究 工作。2002 年，Liang 等 [13] 提出了基于粗糙熵的 不完备决策系统约简算法。2010 年，周献中等[14] 介绍了在不完备决策系统下基于相容关系和相似 关系的粗糙集模型及其拓展模型，通过引入相容 矩阵和相似矩阵，系统研究了相应的粗计算、属 性约简以及决策规则提取的矩阵算法。2010 年 Qian 等 [15] 提出了基于极大相容块的不协调不完 备决策系统下的上下近似约简概念并给出构造相 应差别矩阵方法。2014 年，Shu 等 [16]提出了不完 备决策系统下基于候选属性重要度的快速求属性 约简方法。2015 年，Qian 等 [17] 提出了基于紧凑差 别矩阵的动态不完备决策系统下的特征选择方 法。2018 年，Xie 等 [18] 提出了不完备决策系统下 不协调度的概念，证明了基于不协调度与基于正 域的属性约简等价。 l 在不完备决策系统中，具有相同条件属性的 对象可能决策出多个不同的决策值，每个对象所 有可能决策出的决策值称为该对象的广义决策 值，广义决策约简旨在保持约简前后每个对象的 广义决策值不变。1993 年，Skowron[19] 提出了广 义决策的概念。1998 年，Kryszkiewicz[20] 讨论了 不完备决策系统下的广义决策约简问题，给出相 关决策规则的提取方法，并提出了基于差别矩阵[21] 的广义决策约简方法。上述研究考虑决策属性的 所有决策类，而在实际应用中，决策者往往只关 注部分决策类。为此相关学者针对局部约简即特 定类约简做了大量研究。尹继亮等[22] 讨论了区 间值系统下的局部属性约简。Qian 等 [23] 为解决 经典粗糙集无法处理具有有限标记的大数据集的 问题，引入了局部粗糙集的概念。Liu 等 [24] 提出 了第 决策类下近似约简概念并提出相应差别矩 阵构造方法。 综合上述研究，文献 [20] 研究讨论了不完备 决策系统所有决策类的广义决策约简，文献 [22] 只在区间值系统下对局部约简进行了研究，文 献 [24] 在完备系统下对单特定类的正域约简进行 了研究。然而，基于多特定类的不完备决策系统 下广义决策约简未见报道。为此，本文提出基于 多特定类的不完备决策系统广义决策约简的理论 框架，定义了单特定类的不完备决策系统广义决 策约简的相关概念，提出并证明相关定理，构造 相应差别矩阵和区分函数，并将单特定类推广到 多特定类，提出基于差别矩阵的多特定类不完备 决策系统广义决策约简算法并通过实验验证了算 法的有效性。 1 基本概念 为方便进一步研究基于多特定类的不完备决 策系统广义决策约简，本节将给出不完备决策系 统及广义决策约简的相关基本概念。 1.1 不完备决策系统及其上下近似 DS = (U,AT = C ∪ D,V, f) U C D C ∩ D = Ø V = ∪ a∈AT Va Va a ∈ AT f : U ×AT → V f(x,a) x ∈ U a ∈ AT 定义 1 [16] 四元组 为 一个决策系统，其中 表示所有对象的非空有限 集合，称之为论域； 表示条件属性的非空有限集 合； 表示决策属性的非空有限集合， ； ， 表示属性 的值域； 是一个信息函数，它使得任意对象的任意一个属 性都有一个信息值， 表示对象 在属性 上的取值。 DS = (U,AT = C ∪ D,V, f) B ⊆ AT U IND(B) 定义 2 [16] 四元组 为 一个决策系统，对任意非空属性集 导出论 域 上的不可区分关系 定义为 IND(B) = {(x, y) ∈ U ×U|∀b ∈ B, f(x,b) = f(y,b)} (1) IND(B) U U/IND(B) = {[x]B|x ∈ U} U/B [x]B x 不可区分关系是一个满足自反性、对称性和 传递性的等价关系。由不可区分关系 导 出对论域 的划分为 ，简 记为 ，其中 表示包含 的等价类。 DS = (U,AT = C ∪ D,V, f) c ∈ C Vc IDS = (U,AT = C ∪ D,V, f) Vc 定义 3 [16] 四元组 为 一个决策系统，若存在条件属性 使得 含 有缺失值，则称该决策系统为不完备决策系统， 用 表示， 中的缺失值使 用 *表示。 IDS d ∈ D Vd D IDS D IDS IDS = (U,AT = C ∪ {d},V, f) 在不完备决策系统 中，决策属性 的 值域 不含有缺失值。若决策属性集 中决策 属性数目为 1，则称 为不完备单决策系统；若 中决策属性数目大于 1，则称 为不完备多 决策系统。为表述方便，本文只考虑不完备单决 策系统的情况，即 的 情况。 IDS = (U,AT = C ∪ {d},V, f) A ⊆ C 定义 4 [ 2 0 ] 四元组 为一个不完备决策系统，对任意条件属性集 ，定义其相容关系为 SIM(A) = {(x, y) ∈ U ×U|∀a ∈ A, f (x,a) = f (y,a)∨ f (x,a) = ∗∨ f (y,a) = ∗} (2) ·1200· 智 能 系 统 学 报 第 14 卷
第6期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1201· 其中f(x,a)表示对象x∈U在属性a∈A上的 Sc(x4)={x4},Sc(xs)={2,,x6},Sc(6)={xs,x6}。决 取值。 策属性d对论域U的划分为U/Id={D,D2,D, 相容关系SM(A)具有以下性质： 其中D1={,xl,D2={x,x,D3={x,x6}。由DS 性质120] 四元组DS=(U,AT=CU{d,V,f) 中条件属性集C的相容类集合U/SM(C)及决策 为一个不完备决策系统，对YA≤C,有： 属性d对论域U的划分U/Id可得决策类D,∈ SIM(A)=SIM(a)) (3) U/八di=1,2,3)在C上的下近似集CD和上近似 性质2四元组DS=(U,AT=CU{d,Vf)为 集CD,分别为： 一个不完备决策系统，对YASC,SM(A)满足： CD1=0,CD1=(x1,X2,x.xs]; 1)自反性，对Yx∈U,有(x,y)∈SM(A); CD2={xh,CD2={,x3,x4: 2)对称性，对Vx,y∈U,若(x,y)∈SM(A),则 CD3={x6h,CD3={2,,x6l0 O,x)∈SM(A): 1.2不完备决策系统广义决策约简 3)非传递性，对Yx,y,z∈U,若(x,y)∈SIM(A) 定义62o四元组DS=(U,AT=CU{d,Vf月 且O,z)∈SM(A),(,z)∈SM(A)不一定成立。 为一个不完备决策系统，对x∈U,关于条件属性 设SA(x)=y∈UI(x,y)∈SM(A)},其中条件属 集AsC的广义决策值定义为 性集A二C,SA(x)表示通过条件属性集A与x可 aa(x)={fy,dby∈Sa(x)】 (6) 能不可区分的对象的最大集合。设Da(x)= 在DS中，aa(x)表示对象x关于条件属性集 y∈U(x,y)SM(A)》,其中条件属性集AcC, A的所有可能决策值的集合。 DA()表示通过条件属性集A与x可能可区分的 属性约简旨在保证决策系统的某种分类能力 对象的最大集合。对Yx∈U,有Sa()nDa(x)=O 不变的情况下，删除冗余属性，获得最小属性子 且SA(x)UDa(x)=U。 集。给出不完备决策系统的广义决策约简定义如下。 在DS中，对YASC,有U/SIM(A)表示分类 定义7201四元组DS=(U,AT=CU{d,VfD 且U/SIM(A)={Sa(x)x∈U)。U/SIM(A)中的每一 为一个不完备决策系统，若条件属性集A二C为 个元素SA(x)(x∈U)被称为相容类，且满足UU/ 属性集C的一个广义决策约简，当且仅当满足以 SMA)=U。 下两个条件： 根据相容类，可得到对象集X≤U有关于条 1)对x∈U,有aa(x)=ac(x 件属性集A二C的下近似集和上近似集。 2)对YAcA,3x∈U,有aar(x)≠aa(x)。 定义5o1四元组DS=(U,AT=CU{d,VfD 条件1)保证了条件属性联合的充分性，即约 为一个不完备决策系统，对YXSU,YASC,X关 简前后决策系统广义决策值的一致性：条件2)保 于条件属性集A的下近似集和上近似集分别定义为 证了条件属性个体的必要性，即缺少任意一个 AX={x∈USA(x)∈X)={x∈XSA(x)SX)(4) 必要属性，则无法保持决策系统的广义决策值 AX={x∈U1Sa(x)nX≠O)=USA(x)r∈X)(5) 不变。 例1不完备决策系统DS如表1所示，论 由广义决策约简定义可以构造相应的差别矩 域U={1,x23x4,x56l,C={a1,a2,a3,a4}为条件属性 阵及区分函数，定义如下。 集，决策属性集为{d。 定义82o1四元组DS=(U,AT=CU{d,Vf) 表1不完备决策系统 为一个不完备决策系统，U={,2,…,xn,x,y∈U, Table 1 An incomplete decision system DS广义决策约简的差别矩阵为n×n的矩阵，记 U a a d 为MGEN=(MGEN(x,y)nn,其中矩阵元素MGEN(x,y)为 2 {a∈CLfx,a)≠fy,a)A 1 率 1 2 1 MGEN(x,y)）= fx,a≠*Af0,a)≠利'yeeN X3 0,其他 女 2 2 2 2 (7) Xs 其中ΠN={z∈Uf(2,d年ac(xl。 2 3 定义92o,四元组DS=(U,AT=CUd,Vf) 由定义4得DS在条件属性集C上相容类集合 为一个不完备决策系统，Mcv为DS广义决策约 U/SIM(C)=Sc(xi),Sc(x2),Sc(x3),Sc(xa).Sc(xs).Sc(x6), 简的差别矩阵，若MGsv(x,y)={a1,a2,…,a}≠0，其 其中Sc()={,,Sc(x)={2,,Sc()={x,, 中k表示MGx(x,y)中属性的数量，用VMGEN(x,y)
其中 f (x,a) 表示对象 x ∈ U 在属性 a ∈ A 上的 取值。 相容关系 SIM(A) 具有以下性质： IDS = (U,AT = C ∪ {d},V, f) ∀A ⊆ C 性质 1 [20] 四元组 为一个不完备决策系统，对 ，有： SIM(A)= ∩ a∈A SIM({a}) (3) IDS = (U,AT = C ∪ {d},V, f) ∀A ⊆ C SIM(A) 性质 2 四元组 为 一个不完备决策系统，对 ， 满足： 1) 自反性，对 ∀x ∈ U ，有 (x, y) ∈ SIM(A) ； ∀x, y ∈ U (x, y) ∈ SIM(A) (y, x) ∈ SIM(A) 2) 对称性，对 ，若 ，则 ； ∀x, y,z ∈ U (x, y) ∈ SIM(A) (y,z) ∈ SIM(A) (x,z) ∈ SIM(A) 3) 非传递性，对 ，若 且 ， 不一定成立。 S A (x) = {y ∈ U|(x, y) ∈ SIM(A)} A ⊆ C S A (x) A x DA (x) = {y ∈ U|(x, y) < SIM(A)} A ⊆ C DA (x) A x ∀x ∈ U S A (x)∩ DA (x) = Ø S A (x)∪ DA (x) = U 设 ，其中条件属 性集 ， 表示通过条件属性集 与 可 能不可区分的对象的最大集合。设 ，其中条件属性集 ， 表示通过条件属性集 与 可能可区分的 对象的最大集合。对 ，有 且 。 IDS ∀A ⊆ C U/SIM(A) U/SIM(A) = {S A (x)|x ∈ U} U/SIM(A) S A (x)(x ∈ U) ∪U/ SIM(A)=U 在 中，对 ，有 表示分类 且 。 中的每一 个元素 被称为相容类，且满足 。 X ⊆ U A ⊆ C 根据相容类，可得到对象集 有关于条 件属性集 的下近似集和上近似集。 IDS = (U,AT = C ∪ {d},V, f) ∀X ⊆ U ∀A ⊆ C X A 定义 5 [20] 四元组 为一个不完备决策系统，对 ， ， 关 于条件属性集 的下近似集和上近似集分别定义为 AX = {x ∈ U|S A (x) ⊆ X} = {x ∈ X|S A (x) ⊆ X} (4) AX = {x ∈ U|S A (x)∩ X , Ø} = ∪{S A (x)|x ∈ X} (5) IDS U= {x1,x2,x3,x4,x5,x6} C= {a1,a2,a3,a4} {d} 例 1 不完备决策系统 如表 1 所示，论 域 ， 为条件属性 集，决策属性集为 。 表 1 不完备决策系统 Table 1 An incomplete decision system U a1 a2 a3 a4 d x1 * * 2 2 1 x2 1 * 1 2 1 x3 1 1 2 * 2 x4 2 2 2 1 2 x5 * 1 1 2 3 x6 2 1 1 * 3 IDS C U/SIM(C)={S C(x1),S C(x2),S C(x3),S C(x4),S C(x5),S C(x6)} S C (x1)= {x1, x3} S C (x2)= {x2, x5} S C (x3)= {x1, x3} 由定义 4 得 在条件属性集 上相容类集合 ， 其中 ， ， ， S C (x4)= {x4} S C (x5)= {x2, x5, x6} S C (x6)= {x5, x6} d U U/{d}= {D1,D2,D3} D1 = {x1, x2} D2 = {x3, x4} D3 = {x5, x6} IDS C U/SIM(C) d U U/{d} Di ∈ U/{d}(i = 1,2,3) C CDi CDi ， ， 。 决 策属性 对论域 的划分为 ， 其中 ， ， 。由 中条件属性集 的相容类集合 及决策 属性 对论域 的划分 可得决策类 在 上的下近似集 和上近似 集 分别为： CD1=Ø, CD1 = {x1, x2, x3, x5} ； CD2= {x4}, CD2 = {x1, x3, x4} ； CD3= {x6}, CD3 = {x2, x5, x6}。 1.2 不完备决策系统广义决策约简 IDS = (U,AT = C ∪ {d},V, f) ∀x ∈ U A ⊆ C 定义 6 [20] 四元组 为一个不完备决策系统，对 ，关于条件属性 集 的广义决策值定义为 ∂A(x) = {f(y,d)|y ∈ S A(x)} (6) IDS ∂A(x) x A 在 中， 表示对象 关于条件属性集 的所有可能决策值的集合。 属性约简旨在保证决策系统的某种分类能力 不变的情况下，删除冗余属性，获得最小属性子 集。给出不完备决策系统的广义决策约简定义如下。 IDS = (U,AT = C ∪ {d},V, f) A ⊆ C C 定义 7 [20] 四元组 为一个不完备决策系统，若条件属性集 为 属性集 的一个广义决策约简，当且仅当满足以 下两个条件： 1) 对 ∀x ∈ U ，有 ∂A(x) = ∂C(x) ； ∀A ′ ⊂ A ∃x ′ ∈ U ∂A′ (x ′ ) , ∂A(x ′ 2) 对 ， ，有 )。 条件 1) 保证了条件属性联合的充分性，即约 简前后决策系统广义决策值的一致性；条件 2) 保 证了条件属性个体的必要性，即缺少任意一个 必要属性，则无法保持决策系统的广义决策值 不变。 由广义决策约简定义可以构造相应的差别矩 阵及区分函数，定义如下。 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) 定义 8 [20] 四元组 为一个不完备决策系统， ， ， 广义决策约简的差别矩阵为 的矩阵，记 为 ，其中矩阵元素 为 MGEN(x, y) = {a ∈ C| f(x,a) , f(y,a)∧ f(x,a) , ∗∧ f(y,a) , ∗} , y ∈ ΠGEN Ø, 其他 (7) 其中 ΠGEN = {z ∈ U| f(z,d) < ∂C(x)}。 IDS = (U,AT = C ∪ {d},V, f) MGEN IDS MGEN(x, y) = {a1,a2,··· ,ak} , Ø k MGEN(x, y) ∨MGEN(x, y) 定义 9 [20] 四元组 为一个不完备决策系统， 为 广义决策约 简的差别矩阵，若 ，其 中 表示 中属性的数量，用 第 6 期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1201·
·1202· 智能系统学报 第14卷 表示布尔函数aVa2VVa,对YMN(x,y)≠O, 定理1四元组DS=(U,AT=CU{d,Vf)为 DS广义决策约简的区分函数为 个不完备决策系统，U/Id={D1,D2,…,Dw}为 DF(MGEN)=A(VMGEN(x.y)) (8) 决策类集合，对YD,eU/八d,i=1,2,…,lU/d吼，条件 例2不完备决策系统DS如表1所示，论 属性集A二C为单特定类D:的广义决策协调集当 域U={x1,2,x3,x4,x,x6,C={a1,a2a3,a4}为条件属 且仅当D,nSc()≠O且fy,d0Eac()时，有(x,y) 性集，决策属性集为{d。 SIM(A) 由定义6得DS在条件属性集C上广义决策 证明： ac(U)=(0c(x1),dc(x2),0c(x3).0c(xa).0c(xs).0c(x6)1, 充分性：因条件属性集A是DS单特定类D: 其中ac(x)={1,2},ac(x2)={1,3},ac(x)={1,2},ac 的广义决策协调集，对Yx∈{z∈U1D:nSc(a)≠O, (x4)={2,ac(xs)={1,3引，0c(x6)={3}。DS中所有决 有aa(x)=ac(x)。当D,nSc(x)≠0且fy,d)生ac(x), 策类的广义决策约简差别矩阵为 即fOy,dEaa(x,即(x,y)ESMA)。 MGEN 必要性：当D,nSc(x)≠0且fy,d生c(x)时， 0 0 0 0 {a3} {a3} 有(x,y)SM(A),所以有fy,d)aa(x)成立。当满 0 0 {a3}{a1,a3,aa} 0 0 足DnSc(x)≠0且f6y,d)生ac(x)时，必有fy,d) 0 0 0 0 {a3} {a1,a3} aa(x),即ac(x)2aa(x),又因为A二C,aa(x)2ac(x), {a4}{a1,a3,a4} 0 0 {a2,a3,aa}{a2,a3} 0 0 las az,as,a 0 0 所以当Yx∈{z∈U1D,nSc(a)≠O)时，有aa(x)=ac(x)。 {a3} {a1} {a1,a3}{a2,a3} 0 0 因此条件属性集A≤C为单特定类D,∈U/八d的广 根据DS所有决策类的广义决策约简的差别 义决策协调集。证毕。 矩阵MGv可得对应的区分函数为 定义12四组DS=(U,AT=CU{d,V,f)为一 DF(MGEN)=(a3)A(a V a3 Vaa)(a v a3)A (a) 个不完备决策系统，UId={D,D2,…,Duun}为决 A(a va3 vaa)A(ava3)A(a)= 策类集合，U={x1,,…,xl,xy∈U,DS单特定 a1∧a3Aa4 因此，DS的所有决策类的广义决策约简为 类D,∈U/八d广义决策约简的差别矩阵为n×n的 {a1,a3,a4}o 矩阵，记为M,=(M,(c,y)m,其中矩阵元素M,(x y)为 2多特定类广义决策约简 {a∈CLfx,a)≠fy,a)A 在实际应用中，相较经典广义决策约简中关 Mi(x,y)= f0≠幸人f0,@)≠制’低)eⅡ 注全部决策类，决策者往往只关注决策属性中的 0,其他 (9) 一种或者几种决策类。因此，对于某些特定决策 其中，Π={(x,ylx,y∈U,DnSc(x)≠0AfOy,dc(x)h, 类的约简可能更有意义。本节将讨论不完备决策 i=1,2,…,U/{d 系统下多特定类的广义决策约简。 定理2四元组DS=(U,AT=CU{d,Vf)为 2.1基于差别矩阵的单特定类的广义决策约简 一个不完备决策系统，UId={D,D2,…,Duu}为 定义10四元组DS=(U,AT=CU{d,V,f)为 决策类集合，论域U={x1,x2,…,xn,对YD∈U/{d, 一个不完备决策系统，U/Id={D,D2,…,Du}为 i=1,2,…,lU八dH,条件属性集AsC是单特定类D 决策类集合，对D∈U/川d,i=1,2,…,lU/八d, 的广义决策协调集当且仅当(x,y)∈Ⅱ时，有 HA≤C,Hx∈z∈UID:nSc()≠O1,若满足aa(x)=ac(x AnM(x,y)≠0。 则称条件属性集A为单特定类D:的广义决策协 证明： 调集。 充分性：设条件属性集A是单特定类D:的广 定义11四元组DS=(U,AT=CU{d,V,f)为 义决策协调集，对于(x,y)∈，若DnSc(x)≠O 一个不完备决策系统，U/{d={D,D2,…,Duwn}为 且fy,d)年ac(x),则有(x,y)年SM(A),所以一定存 决策类集合，对VD,∈U/八d,i=1,2,…,U/川dl,若 在a∈A使得(x,y)SM({a),故a∈M(x,y),所以 YASC为单特定类D,的广义决策约简当且仅当 AnM(x,y)≠O。 满足以下两个条件： 必要性：设(x,y)∈Π，使得AnM(x)=O,则 1)Yx∈{z∈UlD,nSc(a)≠O1,aa(x)=ac(x: 有(x,y)∈SMA)成立，又因为对Yx∈U,当 2)YA'cA,3r∈{z∈UID,nSc(a)≠O1,使得aA D,nSc(x)≠0且fy,d)±ac(x)时，必有(x,y)ESM(A), (x)≠8c(x)。 这与(x,y∈SM(A)矛盾。证毕
a1 ∨a2 ∨··· ∨ak ∀MGEN(x, y) , Ø IDS 表示布尔函数 ，对 ， 广义决策约简的区分函数为 DF(MGEN) = ∧(∨MGEN(x, y)) (8) IDS U = {x1, x2, x3, x4, x5, x6} C = {a1,a2,a3,a4} {d} 例 2 不完备决策系统 如表 1 所示，论 域 ， 为条件属 性集，决策属性集为 。 IDS 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} IDS 由定义 6 得 在条件属性集 上广义决策 值 ， 其 中 ， ， ， ， ， 。 中所有决 策类的广义决策约简差别矩阵为 MGEN = Ø Ø Ø Ø {a3} {a3} Ø Ø {a3} {a1 ,a3 ,a4} Ø Ø Ø Ø Ø Ø {a3} {a1 ,a3} {a4} {a1,a3,a4} Ø Ø {a2,a3,a4} {a2,a3} Ø Ø {a3} {a2,a3,a4} Ø Ø {a3} {a1} {a1,a3} {a2,a3} Ø Ø IDS MGEN 根据 所有决策类的广义决策约简的差别 矩阵 可得对应的区分函数为 DF(MGEN) = (a3)∧(a1 ∨a3 ∨a4)∧(a1 ∨a3)∧(a4) ∧(a2 ∨a3 ∨a4)∧(a2 ∨a3)∧(a1) = a1 ∧a3 ∧a4 IDS {a1,a3,a4} 因此, 的所有决策类的广义决策约简为 。 2 多特定类广义决策约简 在实际应用中，相较经典广义决策约简中关 注全部决策类，决策者往往只关注决策属性中的 一种或者几种决策类。因此，对于某些特定决策 类的约简可能更有意义。本节将讨论不完备决策 系统下多特定类的广义决策约简。 2.1 基于差别矩阵的单特定类的广义决策约简 IDS = (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 ∩S C(z) , Ø} ∂A(x) = ∂C(x) A Di 定义 10 四元组 为 一个不完备决策系统， 为 决策类集合，对 ， ， ，若满足 ， 则称条件属性集 为单特定类 的广义决策协 调集。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} ∀Di ∈ U/{d} i=1,2,··· ,|U/{d}| ∀A ⊆ C Di 定义 11 四元组 为 一个不完备决策系统， 为 决策类集合，对 ， ， 若 为单特定类 的广义决策约简当且仅当 满足以下两个条件： 1) ∀x ∈ {z ∈ U|Di ∩S C(z) , Ø}，∂A(x) = ∂C(x) ； ∀A ′ ⊂ A ∃x ′ ∈ {z ∈ U|Di ∩S C(z) , Ø} ∂A′ (x ′ ) , ∂C(x ′ ) 2 ) ， ，使得 。 IDS = (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 ∩S C(x) , Ø f(y,d) < ∂C(x) (x, y) < SIM(A) 定理 1 四元组 为 一个不完备决策系统， 为 决策类集合，对 ， ，条件 属性集 为单特定类 的广义决策协调集当 且仅当 且 时，有 。 证明： A IDS Di ∀x ∈ {z ∈ U|Di ∩S C(z) , Ø} ∂A(x) = ∂C(x) Di ∩S C(x) , Ø f(y,d) < ∂C(x) f(y,d) < ∂A(x) (x, y) < SIM(A) 充分性：因条件属性集 是 单特定类 的广义决策协调集，对 ， 有 。当 且 ， 即 ，即 。 Di ∩S C(x) , Ø f(y,d) < ∂C(x) (x, y) < SIM(A) f(y,d) < ∂A(x) Di ∩S C(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 ∩S C(z) , Ø} ∂A(x) = ∂C(x) A ⊆ C Di ∈ U/{d} 必要性：当 且 时， 有 ，所以有 成立。当满 足 且 时，必有 ，即 ，又因为 ， ， 所以当 时，有 。 因此条件属性集 为单特定类 的广 义决策协调集。证毕。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} U = {x1, x2,··· , xn} ∀x, y ∈ U IDS Di ∈ U/{d} n×n Mi = (Mi(x, y))n×n Mi(x, y) 定义 12 四组 为一 个不完备决策系统， 为决 策类集合， ， , 单特定 类 广义决策约简的差别矩阵为 的 矩阵，记为 ，其中矩阵元素 为 Mi(x, y) = {a ∈ C| f(x,a) , f(y,a)∧ f(x,a) , ∗∧ f(y,a) , ∗} , (x, y) ∈ Πi Ø, 其他 (9) Πi = {(x, y)|x, y ∈ U,Di ∩S C(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 ⊆ C Di ∀(x, y) ∈ Πi A∩ Mi(x, y) , Ø 定理 2 四元组 为 一个不完备决策系统， 为 决策类集合，论域 ，对 ， ，条件属性集 是单特定类 的广义决策协调集当且仅当 时，有 。 证明： A Di ∀(x, y) ∈ Πi Di ∩S C(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 ∩S C(x) , Ø f(y,d) < ∂C(x) (x, y) < SIM(A) (x, y) ∈ SIM(A) 必要性：设 ，使得 ，则 有 成立，又因为对 ， 当 且 时，必有 ， 这与 矛盾。证毕。 ·1202· 智 能 系 统 学 报 第 14 卷
第6期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1203· 定义13四元组DS=(U,AT=CU{d,Vf)为 决策类集合，对YDmc三U/{d,条件属性集AsC 一个不完备决策系统，UId={D,D2,…,Dui}为 为多特定类D的广义决策约简当且仅当满足以 决策类集合，对yD∈U/八d,i=1,2,…,U/d,M 下两个条件： 为DS单特定类D,的广义决策约简的差别矩阵， 1)对Yx∈{z∈U川JDmesnSc(z)≠O1,都有aa(x)= 若M,(x,y)）={a1,a2,…,a}≠0，其中k表示M,(x,y)中 oc(x): 属性的数量，用VM,(x,y)表示布尔函数a1Va2VVa, 2)A'CA,r∈{z∈UlUD esnSc(z)≠O1,使得 对YM,(x,y)≠O,DS单特定类D的广义决策约简 aa(x)≠ac(x)o 的区分函数为 由定义16可知，当Dmsl=1时，DS多特定类 DF(M )=A(VM(x,y)) (10) 的广义决策约简将退化为单特定类的广义决策约 定理3四元组DS=(U,AT=CU{d,V,f)为 简；当Dmes=IU/Id时，IDS多特定类的广义决策 一个不完备决策系统，U/Id={D,D2,…,Dwn}为 约简将退化为全决策类的广义决策约简。 决策类集合，对D,eU/八d,i=1,2,…,U/d,DS 定理4四元组DS=(U,AT=CU{d,V,f月)为 单特定类D,的广义决策约简区分函数DF(M)= 一个不完备决策系统，U/{d={D,D2,…,Duw}为 ANMx,》的极小析取范式为DF'(M)=(六a),t 决策类集合，条件属性集A二C为多特定类 表示DF'(M,)中的析取项数目，9k表示DF'(M)中 Daes CU/Id山的广义决策协调集当且仅当UDmsn 第k个析取项中属性数目。记A={as=1,2,…,q, Sc(x)≠O且f0y,d)年ac(x)时，有(x,y)ESM(A)。 则{Ak=1,2,…,是单特定类D,∈U/{d的所有 证明： 广义决策约简形成的集合。 充分性：因属性集A是DS多特定类Dcs的 证明： 广义决策协调集，对x∈{z∈UU DmesnSc(a)≠O列 对Yk≤t,Y(x,y)∈Ⅱ，由极小析取范式定义可 有aa(x)=ac(x)。UD esnSc(x)≠0且f,d)Eac(x) 知AnM(x,y)≠O,由定理2可知A是广义决策 时，必有fy,daa(x)成立，所以(x,y)SMA)。 协调集。 必要性：当UDmesnsc()≠0且fy,d)生ae(x) DF(M)=V(A),若在A中删除一个元素形 时，有(x,y)SM(A),所以f0,d)生aa(x)成立。因 成A,则3(x,y)e·使得A:nM,(x,y)=O,故A:不 为当UDesnsc(x)≠0且fO,d)生ac(x)时，必有 是广义决策约简，因此A是广义决策约简。因为 fy,daa(x)成立，即ae(x)2aA(x)。又因为当 区分函数中包含所有M,(x,y),故不存在其余广义 A二C时，必有aa(x)2ac(x)成立，所以对Hx∈{z∈ULU 决策约简。证毕。 DesnSc(②≠O1,有aa(x)=ac(r)。因此条件属性集 2.2基于差别矩阵的多特定类的广义决策约简 AsC为多特定类DsU/Id的广义决策协调 根据以上讨论，将单特定类的不完备决策系 集。证毕。 统广义决策约简扩展得到多特定类的不完备决策 定义17四元组DS=(U,AT=CU{d,Vf月为 系统广义决策约简。给出多特定类的广义决策约 一个不完备决策系统，U/d={D,D2,…,Dua}为 简相关定义如下。 决策类集合，U={,2,…,xn},xy∈U,DS多特 定义14四元组DS=(U,AT=CU{d,Vf)为 定类DaesU/八d广义决策约简的差别矩阵为 一个不完备决策系统，U/{d={D,D2,…,Du}为 nXn的矩阵，记为Mmes=(Mme(x,y)n,其中矩阵 决策类集合，则多特定类D定义为 元素Mms(x,y)为 Dies CU/dl,Dmcs≠O (11) {a∈Cfx,a)+fy,a)n 由多特定类的定义可知，多特定类D至少 Mmes(x.y)= fa≠*f0,@)≠制’)eⅡm 含有一个单特定类至多含有IU/Id个互不相同的 0, 其他 单特定类。 (12) 定义15四元组DS=(U,AT=CU{d,V,f)为 其中，Πs={(x,y)x,y∈U,UDmesnSc(x)≠Of0y,d) 一个不完备决策系统，U/{d={D,D2,…,Duni}为 ac(x)}。 决策类集合，对YDmesCU/Id,YAsC,Yx∈{z∈ 定理5四元组DS=(U,AT=CU{d,Vf)为 UlU Dmesnsc(a)≠O,若aa(x)=ac(x),则称条件属 一个不完备决策系统，UId={D,D2,…,Dua}为 性集A为多特定类Ds的广义决策协调集。 决策类集合，对多特定类DsU/Id,条件属性 定义16四元组DS=(U,AT=CU{d,Vf)为 集AsC是多特定类D的广义决策协调集当且 个不完备决策系统，U/Id={D,D2,…,Dwam}为 仅当(x,y)∈Πmes时，有AnMmes(x,y≠O
IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} ∀Di ∈ U/{d} i = 1,2,··· ,|U/{d}| Mi IDS Di Mi(x, y) = {a1,a2,··· ,ak} , Ø k Mi(x, y) ∨Mi(x, y) a1 ∨a2 ∨··· ∨ak ∀Mi(x, y) , Ø IDS Di 定义 13 四元组 为 一个不完备决策系统， 为 决策类集合，对 ， ， 为 单特定类 的广义决策约简的差别矩阵， 若 ，其中 表示 中 属性的数量，用 表示布尔函数 ， 对 ， 单特定类 的广义决策约简 的区分函数为 DF(Mi) = ∧(∨Mi(x, y)) (10) IDS = (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)) DF′ (Mi) = t ∨ k=1 ( qk ∧ s=1 as) t DF′ (Mi) qk DF′ (Mi) k Ak = {as |s = 1,2,··· ,qk} {Ak |k = 1,2,··· ,t} Di ∈ U/{d} 定理 3 四元组 为 一个不完备决策系统， 为 决策类集合，对 ， ， 单特定类 的广义决策约简区分函数 的极小析取范式为 ， 表示 中的析取项数目， 表示 中 第 个析取项中属性数目。记 ， 则 是单特定类 的所有 广义决策约简形成的集合。 证明： ∀k ⩽ t ∀(x, y) ∈ Πi Ak ∩ Mi(x, y) , Ø Ak 对 ， ，由极小析取范式定义可 知 ，由定理 2 可知 是广义决策 协调集。 DF ′ (Mi) = t ∨ k=1 (Ak) Ak A ′ k ∃(x, y) ∈ Πi A ′ k ∩ Mi(x, y) = Ø A ′ k Ak Mi(x, y) ，若在 中删除一个元素形 成 ，则 使得 ，故 不 是广义决策约简，因此 是广义决策约简。因为 区分函数中包含所有 ，故不存在其余广义 决策约简。证毕。 2.2 基于差别矩阵的多特定类的广义决策约简 根据以上讨论，将单特定类的不完备决策系 统广义决策约简扩展得到多特定类的不完备决策 系统广义决策约简。给出多特定类的广义决策约 简相关定义如下。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} Dmcs 定义 14 四元组 为 一个不完备决策系统， 为 决策类集合，则多特定类 定义为 Dmcs ⊆ U/{d},Dmcs , Ø (11) Dmcs |U/{d}| 由多特定类的定义可知，多特定类 至少 含有一个单特定类至多含有 个互不相同的 单特定类。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} ∀Dmcs ⊆ U/{d} ∀A ⊆ C ∀x ∈ {z ∈ U|∪ Dmcs ∩S C(z) , Ø} ∂A(x) = ∂C(x) A Dmcs 定义 15 四元组 为 一个不完备决策系统， 为 决策类集合，对 ， ， ，若 ，则称条件属 性集 为多特定类 的广义决策协调集。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} 定义 16 四元组 为 一个不完备决策系统， 为 ∀Dmcs ⊆ U/{d} A ⊆ C Dmcs 决策类集合，对 ，条件属性集 为多特定类 的广义决策约简当且仅当满足以 下两个条件： ∀x ∈ {z ∈ U| ∪ Dmcs ∩S C(z) , Ø} ∂A(x) = ∂C(x) 1) 对 ，都有 ； ∀A ′ ⊂ A ∃x ′ ∈ {z ∈ U| ∪ Dmcs ∩S C(z) , Ø} ∂A′ (x ′ ) , ∂C(x ′ ) 2) ， ，使得 。 |Dmcs| = 1 IDS |Dmcs| = |U/{d}| IDS 由定义 16 可知，当 时， 多特定类 的广义决策约简将退化为单特定类的广义决策约 简；当 时， 多特定类的广义决策 约简将退化为全决策类的广义决策约简。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} A ⊆ C Dmcs ⊆ U/{d} ∪Dmcs∩ S C(x) , Ø f(y,d) < ∂C(x) (x, y) < SIM(A) 定理 4 四元组 为 一个不完备决策系统， 为 决策类集合，条件属性集 为多特定类 的广义决策协调集当且仅当 且 时，有 。 证明： A IDS Dmcs ∀x ∈ {z ∈ U| ∪ Dmcs ∩S C(z) , Ø} ∂A(x) = ∂C(x) ∪Dmcs ∩S C(x) , Ø f(y,d) < ∂C(x) f(y,d) < ∂A(x) (x, y) < SIM(A) 充分性：因属性集 是 多特定类 的 广义决策协调集，对 有 。 且 时，必有 成立，所以 。 ∪Dmcs ∩S C(x) , Ø f(y,d) < ∂C(x) (x, y) < SIM(A) f(y,d) < ∂A(x) ∪Dmcs ∩S C(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 ∩S C(z) , Ø} ∂A(x) = ∂C(x) A ⊆ C Dmcs ⊆ U/{d} 必要性：当 且 时，有 ，所以 成立。因 为 当 且 时，必有 成立，即 。又因为当 时，必有 成立，所以对 ，有 。因此条件属性集 为多特定类 的广义决策协调 集。证毕。 IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} U = {x1, x2,··· , xn} ∀x, y ∈ U IDS Dmcs ⊆ U/{d} n×n Mmcs = (Mmcs(x, y))n×n Mmcs(x, y) 定义 17 四元组 为 一个不完备决策系统， 为 决策类集合， ， , 多特 定 类 广义决策约简的差别矩阵为 的矩阵，记为 ，其中矩阵 元素 为 Mmcs(x, y) = {a ∈ C| f(x,a) , f(y,a)∧ f(x,a) , ∗∧ f(y,a) , ∗} , (x, y) ∈ Πmcs Ø, 其他 (12) Πmcs = {(x, y)|x, y ∈ U,∪Dmcs ∩S C(x) , Ø∧f(y,d) < ∂C(x)} 其中， 。 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) , Ø 定理 5 四元组 为 一个不完备决策系统， 为 决策类集合，对多特定类 ，条件属性 集 是多特定类 的广义决策协调集当且 仅当 时，有 。 第 6 期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1203·
·1204· 智能系统学报 第14卷 证明： U/{d={,x,{3,x4,{x,x6h。广义决策值为8c(U)= 充分性：设条件属性集A是多特定类D的 oc(x).oc(x2).0c(x3).oc(x).oc(xs),oc(x6)c(x)= 广义决策协调集，对Y(x,y)eⅡmes,当UDmsn {1,2,8c(x)={1,3h,c(x3)={1,2,ac(x)={2,ac(x)= Sc(x)≠0且f0y,d)年ac(x)时，则有(x,y)SM(A), {1,3,0c(x6)={3。 所以一定存在a∈A使得(x,y)SM(Ia),故 对于单特定类D1={,,x2},依据定义12构造 a∈Mnme(xy),所以A0 M(化，y)≠O。 DS单特定类D,的差别矩阵为 必要性：设3(x,y)eΠcs,使AnMe(c,y)=0成 000 0 {a3} {a3} 立，则有(x,y)eSM(A),又因对YxeU,当f0,d) 0 0{al {a1,a3,aa 0 0 ac(d)且UDmesnSc(x)≠O时，必有(xy)年SM(A), 0 0 0 0 {a3} (a,ah 这与(x,y)∈SM(4)矛盾。证毕。 0 0 0 0 0 0 0 0 0 定义18四元组DS=(U,AT=CU{d,Vf)为 0{a3}{a2,a3,a4} 00 ① 0 0 0 一个不完备决策系统，DecUld)为多特定类， 根据DS单特定类D的广义决策约简的差 Mmes为DS多特定类De的广义决策约简的差别 别矩阵M可得对应的区分函数为 矩阵，若Mme(x,y)={a1,2,…,a}≠0，其中k表示 DF(M)=(a3)A(a Vas va)A(a Va3) Mc(x,y)中属性的数量，用VMme(x,y)表示布尔函 (a Va3 vaa)=a3 数a1Va2VVak,对YMme(x,y)≠O,DS多特定类 因此DS的单特定类D的广义决策约简为{a}。 Dmc的广义决策约简的区分函数为 对多特定类Dm={D1,D2}={x1,x2l,{x3,xh,依 DF(Mm)=A(VM(x.y)) (13) 据定义17构造DS多特定类Dme的差别矩阵为 定理6四元组DS=(U,AT=CU{d,V,f)为 一个不完备决策系统，Ud={D,D2,…,Duam}为 Mmes= 0 0 0 0 {a3} as] 决策类集合，多特定类DmSU/Id的广义决策约 0 0 {a3}{a1,a3,a4} 0 0 简区分函数DF(Mnc)=A(VMme(x,y》的极小析取 0 0 0 {a3} (a,a3) 范式为DF'(Mnes)=y(人a,),t表示DF'(Me)中的 {a4}{a1.a3,a4}0 0 {a2,a3,a4}{a2,a3} k=1=1 0 {a3}{a2,a3,a4l 0 0 析取项数目，qk表示DF'(Mme)中第k个析取项中 0 0 0 0 0 0 属性数目。设Ak={als=1,2,…,q,{4k=1,2,…, 根据DS多特定类Dme的广义决策约简的差 是多特定类DssU/八d的所有广义决策约简形 别矩阵Mcs可得对应的区分函数为 成的集合。 DF(Mmes)=(a3)A(a1 va3vas)A(a1 va3)A(aa)A 证明： (az V as Va)A(a2 Vas)=as Aa 对Yk≤t,Y(x,y)∈Ls,由极小析取范式定义 因此DS的多特定类Dm的广义决策约简为 可知Akn Mmes(x,y)≠O,由定理5可知Ak是DS多 {a3,a4}e 特定类的广义决策协调集。 因单特定类广义决策约简为多特定类广义约 DF'(Mmcs)=V(4),若在A中删除一个元素得 简的特例，所以仅给出多特定类的不完备决策系 A4,3x,y)eⅡcs使A4nMmc(x,y)=O,故A:不是广 统广义决策约简算法如下。 义决策约简，因此A:是广义决策约简。因为区分 算法1基于差别矩阵的多特定类不完备决 函数中包含所有Mc(x,y),故不存在其余广义决 策系统广义决策约简(multi--class--specific general- 策约简。证毕。 ized decision preservation reduction based on discern- 根据不完备决策系统单特定类以及多特定类 ibility matrix in incomplete decision systems,MG- 广义决策约简的相关定义，可依据相应的差别矩 DRDM) 阵以及区分函数进行广义决策约简的求解，现给 输入一个不完备决策系统DS=(U,AT= 出实例如下。 CU{d.Vf),多特定类Dme。 例3不完备决策系统DS如表1所示，论域 输出多特定类Dm的不完备决策系统广义 U={m,2,x3,x4,5,x6},C={a1,a2,a3,a4}为条件属性 决策约简。 集，决策属性集为{d。 1)依据条件属性集C计算论域U中每个 由例1易得，IDS在属性集C上的相容类集 对象的相容类Sc(x(x∈U),根据决策属性d计算 合U/SM(C)={x1,3,{x2,x5,1,x,{x4,{x2,x5,x6}, 决策类集合U/d: {x5,x}。决策属性d对论域U划分决策类为 2)依据相容类Sc(x)计算每个对象的广义
证明： A Dmcs ∀(x, y) ∈ Πmcs ∪Dmcs∩ S C(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 ∩S C(x) , Ø (x, y) < SIM(A) (x, y) ∈ SIM(A) 必要性：设 ，使 成 立，则有 ，又因对 ，当 且 时，必有 ， 这与 矛盾。证毕。 IDS = (U,AT = C ∪ {d},V, f) Dmcs ⊆ U/{d} Mmcs IDS Dmcs Mmcs(x, y) = {a1,a2,··· ,ak} , Ø k Mmcs(x, y) ∨Mmcs(x, y) a1 ∨a2 ∨··· ∨ak ∀Mmcs(x, y) , Ø IDS Dmcs 定义 18 四元组 为 一个不完备决策系统， 为多特定类， 为 多特定类 的广义决策约简的差别 矩阵，若 ，其中 表示 中属性的数量，用 表示布尔函 数 ，对 ， 多特定类 的广义决策约简的区分函数为 DF(Mmcs) = ∧(∨Mmcs(x, y)) (13) IDS = (U,AT = C ∪ {d},V, f) U/{d} = {D1,D2,··· ,D|U/{d}|} Dmcs ⊆ U/{d} DF(Mmcs) = ∧(∨Mmcs(x, y)) DF′ (Mmcs) = t ∨ k=1 ( qk ∧ s=1 as) t DF′ (Mmcs) qk DF′ (Mmcs) k Ak = {as |s = 1,2,··· ,qk} {Ak |k = 1,2,··· ,t} Dmcs ⊆ U/{d} 定理 6 四元组 为 一个不完备决策系统， 为 决策类集合，多特定类 的广义决策约 简区分函数 的极小析取 范式为 ， 表示 中的 析取项数目， 表示 中第 个析取项中 属性数目。设 ， 是多特定类 的所有广义决策约简形 成的集合。 证明： ∀k ⩽ t ∀(x, y) ∈ Πmcs Ak ∩ Mmcs(x, y) , Ø Ak IDS 对 ， ，由极小析取范式定义 可知 ，由定理 5 可知 是 多 特定类的广义决策协调集。 DF′ (Mmcs) = t ∨ k=1 (Ak) Ak A ′ k ∃(x, y) ∈ Πmcs A ′ k ∩ Mmcs(x, y) = Ø A ′ k Ak Mmcs(x, y) ，若在 中删除一个元素得 ， 使 ，故 不是广 义决策约简，因此 是广义决策约简。因为区分 函数中包含所有 ，故不存在其余广义决 策约简。证毕。 根据不完备决策系统单特定类以及多特定类 广义决策约简的相关定义，可依据相应的差别矩 阵以及区分函数进行广义决策约简的求解，现给 出实例如下。 IDS U = {x1, x2, x3, x4, x5, x6} C = {a1,a2,a3,a4} {d} 例 3 不完备决策系统 如表 1 所示，论域 ， 为条件属性 集，决策属性集为 。 IDS C U/SIM(C) = {{x1, x3},{x2, x5},{x1, x3},{x4},{x2, x5, x6} {x5, x6}} d U 由例 1 易得， 在属性集 上的相容类集 合 ， 。决策属性 对论域 划分决策类为 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) = {1,3} ∂C(x6) = {3} 。广义决策值为 ，其中 ， ， ， ， ， 。 D1 = {x1, x2} IDS D1 对于单特定类 ，依据定义 12 构造 单特定类 的差别矩阵为 M1 = Ø Ø Ø Ø {a3} {a3} Ø Ø {a3} {a1,a3,a4} Ø Ø Ø Ø Ø Ø {a3} {a1 ,a3} Ø Ø Ø Ø Ø Ø Ø Ø {a3} {a2,a3,a4} Ø Ø Ø Ø Ø Ø Ø Ø IDS D1 M1 根据 单特定类 的广义决策约简的差 别矩阵 可得对应的区分函数为 DF(M1) = (a3)∧(a1 ∨a3 ∨a4)∧(a1 ∨a3)∧ (a2 ∨a3 ∨a4) = a3 因此 IDS 的单特定类 D1的广义决策约简为 {a3}。 Dmcs = {D1,D2} = {{x1, x2},{x3, x4}} IDS Dmcs 对多特定类 ，依 据定义 17 构造 多特定类 的差别矩阵为 Mmcs = Ø Ø Ø Ø {a3} {a3} Ø Ø {a3} {a1 ,a3 ,a4} Ø Ø Ø Ø Ø Ø {a3} {a1 ,a3} {a4} {a1,a3,a4} Ø Ø {a2,a3,a4} {a2,a3} Ø Ø {a3} {a2,a3,a4} Ø Ø Ø Ø Ø Ø Ø Ø IDS Dmcs Mmcs 根据 多特定类 的广义决策约简的差 别矩阵 可得对应的区分函数为 DF(Mmcs) = (a3)∧(a1 ∨a3 ∨a4)∧(a1 ∨a3)∧(a4)∧ (a2 ∨a3 ∨a4)∧(a2 ∨a3) = a3 ∧a4 IDS 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 的不完备决策系统广义 决策约简。 C U S C(xi)(xi ∈ U) d U/{d} 1) 依据条件属性集 计算论域 中每个 对象的相容类 ，根据决策属性 计算 决策类集合 ； 2) 依据相容类 S C(xi) 计算每个对象的广义 ·1204· 智 能 系 统 学 报 第 14 卷
第6期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1205· 决策值ac(x: 要将其转为不完备决策系统。采用文献[16]中的 3)依据决策系统中每个对象的广义决策值 方法对完备决策系统进行处理，具体处理方式 ac(x)和多特定类Dme构造相应差别矩阵Mmes; 为：除决策属性之外，每个条件属性对应列选取 4)依据差别矩阵Mms构造相应多特定类 10%的属性值进行缺失处理，缺失值使用*表示。 的广义决策约简区分函数DF(Mms); 3.1约简结果对比 5)利用吸收律和分配律将多特定类区分函 两种约简算法所得平均约简长度对比如表3 数DF(Mmcs)转变为极小析取范式DF'(Mme): 所示。表3中，“全决策类”表示经典全决策类约 6)依据极小析取范式DF'(M)输出多特 简算法所得约简结果，“单特定类”表示MG- 定类D的广义决策约简，算法结束。 DRDM算法选定一个特定类时所得约简结果， 算法1中，步骤1)的时间复杂度为OCIU), “多特定类”表示MGDRDM算法选定多个特定类 步骤2)的时间复杂度为OU),步骤3)、步骤4) 时所得约简结果，“决策值”表示对应算法选取的 的时间复杂度为OCU),步骤5)的过程是一个 一个或多个特定类所表现决策值，“平均约简长 NP-hard问题，该步骤的时间复杂度为OICr),因 此算法1的整体时间复杂度为OCF)。 度”表示对应算法所得约简的平均约简长度。 由表3可知，相比全部决策类，当选定特定类 3实验结果与分析 数量较少时，平均约简长度往往会比全决策类所 得平均约简长度要短。若多特定类选择为所有决 针对本文提出的多特定类不完备决策系统广 策类，则算法将退化为全决策类约简，平均约简 义决策约简算法进行实验验证与分析。本节实验 长度不会缩短。 选择与经典不完备决策系统广义决策约简针对约 简结果、占用空间以及约简效率进行比较。 表3平均约简长度 本节采用6组标准UCI数据集进行实验，数 Table 3 Average reduct length 据集从htp://archive.ics.uci.cdu/ml/datasets.php处下 全决策类 单特定类 多特定类 载。数据集使用WEKA3.6进行等频率离散化预 D数据集 平均约决策平均约决策平均约 处理，因某些原始数据中存在缺失数据数量极 简长度 值 简长度 值 简长度 少，无法直接作为实验使用，所以针对缺失数据 1 Z00 10.3 2 7.6 2,4 8.0 使用相应属性下出现频率最高属性值作为替换， 2 Audiology 24.1 16.7 1.4,611 20.0 针对名词性数据使用整数作为替换。数据集详细 3 Glass 10.0 6 7.0 5,6 8.0 信息如表2所示。表2中，ID表示数据集编号， “数据集”表示数据集名称，U表示数据集中对象 House 13.0 0 10.0 0,2 12.0 数目，1C1表示数据集中条件属性数目，U/Id表 Connec- 5 9.0 0 7.5 0,2 8.0 示数据集中决策类数目。本节实验环境：操作系 tionist Windows7-64 bit;CPU Intel Core i5-6500(3.2 6 Yeast 8.0 7.0 58 7.0 GHz):内存4GB;运行环境Python3.6:开发工具 3.2占用空间对比 PyCharm 本节通过比较两种算法生成的差别矩阵中非 表2数据集 空属性集占比进而比较两种算法占用空间大小。 Table 2 Data Sets 两种算法生成差别矩阵中非空属性集占比如表4 ID 数据集 UI ICI 1U/dl 所示，其中“占比(%)”表示对应不同算法构造差 1 Zoo 101 16 7 别矩阵中非空属性集所占比例。 2 Audiology 200 69 24 由表4可知，当选定一个或者几个特定类，特 3 Glass 214 10 6 定类数量相对全部决策类数量较少时，MG- DRDM算法所构造差别矩阵中非空属性集占比 4 House 506 3 4 J 要小于经典算法构造差别矩阵中的非空属性集占 Connectionist 528 10 11 比。因此，在保证约简目标不变的前提下，MG 6 Yeast 1484 8 10 DRDM算法所构造差别矩阵占用空间要小于经 因本节采用UCI标准数据集，预处理之后数 典算法构造差别矩阵占用空间。除此之外，利用 据集所表示的决策系统为完备决策系统，所以需 差别矩阵中非空属性集构造区分函数以及求取极
决策值 ∂C(xi) ； ∂C(xi) Dmcs Mmcs 3) 依据决策系统中每个对象的广义决策值 和多特定类 构造相应差别矩阵 ； Mmcs DF(Mmcs) 4) 依据差别矩阵 构造相应多特定类 的广义决策约简区分函数 ； DF(Mmcs) DF′ (Mmcs) 5) 利用吸收律和分配律将多特定类区分函 数 转变为极小析取范式 ； DF′ (Mmcs) Dmcs 6) 依据极小析取范式 输出多特 定类 的广义决策约简，算法结束。 O(|C||U| 2 ) O(|U| 2 ) O(|C||U| 2 ) O(|C| |U| 2 ) O(|C| |U| 2 ) 算法 1 中，步骤 1) 的时间复杂度为 ， 步骤 2) 的时间复杂度为 ，步骤 3) 、步骤 4) 的时间复杂度为 ，步骤 5) 的过程是一个 NP-hard 问题，该步骤的时间复杂度为 ，因 此算法 1 的整体时间复杂度为 。 3 实验结果与分析 针对本文提出的多特定类不完备决策系统广 义决策约简算法进行实验验证与分析。本节实验 选择与经典不完备决策系统广义决策约简针对约 简结果、占用空间以及约简效率进行比较。 |U| |C| |U/{d}| 本节采用 6 组标准 UCI 数据集进行实验，数 据集从 http://archive.ics.uci.edu/ml/datasets.php 处下 载。数据集使用 WEKA3.6 进行等频率离散化预 处理，因某些原始数据中存在缺失数据数量极 少，无法直接作为实验使用，所以针对缺失数据 使用相应属性下出现频率最高属性值作为替换， 针对名词性数据使用整数作为替换。数据集详细 信息如表 2 所示。表 2 中，ID 表示数据集编号， “数据集”表示数据集名称， 表示数据集中对象 数目， 表示数据集中条件属性数目， 表 示数据集中决策类数目。本节实验环境：操作系 统 Windows7-64 bit；CPU Intel Core i5-6500(3.2 GHz)；内存 4 GB；运行环境 Python 3.6；开发工具 PyCharm。 表 2 数据集 Table 2 Data Sets ID 数据集 |U| |C| |U/{d}| 1 Zoo 101 16 7 2 Audiology 200 69 24 3 Glass 214 10 6 4 House 506 13 4 5 Connectionist 528 10 11 6 Yeast 1 484 8 10 因本节采用 UCI 标准数据集，预处理之后数 据集所表示的决策系统为完备决策系统，所以需 要将其转为不完备决策系统。采用文献 [16] 中的 方法对完备决策系统进行处理，具体处理方式 为：除决策属性之外，每个条件属性对应列选取 10% 的属性值进行缺失处理，缺失值使用*表示。 3.1 约简结果对比 两种约简算法所得平均约简长度对比如表 3 所示。表 3 中，“全决策类”表示经典全决策类约 简算法所得约简结果， “ 单特定类 ” 表 示 MGDRDM 算法选定一个特定类时所得约简结果， “多特定类”表示 MGDRDM 算法选定多个特定类 时所得约简结果，“决策值”表示对应算法选取的 一个或多个特定类所表现决策值，“平均约简长 度”表示对应算法所得约简的平均约简长度。 由表 3 可知，相比全部决策类，当选定特定类 数量较少时，平均约简长度往往会比全决策类所 得平均约简长度要短。若多特定类选择为所有决 策类，则算法将退化为全决策类约简，平均约简 长度不会缩短。 表 3 平均约简长度 Table 3 Average reduct length ID 数据集 全决策类 单特定类 多特定类 平均约 简长度 决策 值 平均约 简长度 决策 值 平均约 简长度 1 Zoo 10.3 2 7.6 2,4 8.0 2 Audiology 24.1 4 16.7 1,4,6,11 20.0 3 Glass 10.0 6 7.0 5,6 8.0 4 House 13.0 0 10.0 0,2 12.0 5 Connectionist 9.0 0 7.5 0,2 8.0 6 Yeast 8.0 5 7.0 5,8 7.0 3.2 占用空间对比 本节通过比较两种算法生成的差别矩阵中非 空属性集占比进而比较两种算法占用空间大小。 两种算法生成差别矩阵中非空属性集占比如表 4 所示，其中“占比 (%)”表示对应不同算法构造差 别矩阵中非空属性集所占比例。 由表 4 可知，当选定一个或者几个特定类，特 定类数量相对全部决策类数量较少时， MGDRDM 算法所构造差别矩阵中非空属性集占比 要小于经典算法构造差别矩阵中的非空属性集占 比。因此，在保证约简目标不变的前提下，MGDRDM 算法所构造差别矩阵占用空间要小于经 典算法构造差别矩阵占用空间。除此之外，利用 差别矩阵中非空属性集构造区分函数以及求取极 第 6 期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1205·
·1206· 智能系统学报 第14卷 小析取范式时，MGDRDM算法也将占用更小空 某些情况下，添加属性求解约简反而会使耗 间。当选定特定类为全部决策类时，MGDRDM 时减少，这可能是因为在添加属性之后构造差别 算法将退化为全决策类约简，占用空间不会减小。 矩阵的过程中产生了较添加属性之前更短的非空 表4差别矩阵非空属性集占比 属性集，这使得构造区分函数以及求取极小析取 Table 4 The proportion of non-empty attribute sets in the 范式的过程耗时减少，所以在某些情况添加属性 discernibility matrix 反而求解更快。 全决策类 单特定类 多特定类 ID 数据集 0.8 0 单特定类（决策值2） 占比%决策值占比%决策值占比% 0.7 多特定类（决策值2,4） 0.6 △一全决策类 Zoo 75.7 2 11.2 2.4 20.1 Audiology 85.0 4 9.6 1,4,6,11 22.9 量8 Glass 71.3 6 5.8 5.6 10.2 0.2 House 22.2 0 3.1 0,2 6.7 0.1 5 Connectionist 90.8 0 8.3 0.2 16.6 6 810 121416 属性数量 6 Yeast 53.5 5 4.3 58 7.1 (a)Zoo 20 单特定类（决策值：4） 3.3约简效率对比 18 0 多特定类（决策值：1,4,6,11） 本节将6组数据集，依据随属性数目递增的 16 。一全决策类 14 时间消耗进行经典不完备决策系统广义决策约简 10 与MGDRDM算法之间约简效率对比。约简效率 12 8 如图1所示，其中“全决策类”表示经典全类不完 6 备决策系统广义决策约简算法随属性数目增加的 3 约简耗时变化曲线，“单特定类”和“多特定类”则 10 20304050 60 表示MGDRDM算法分别选定一个和多个特定类 属性数量 随属性数目增加的约简耗时变化曲线，“决策值” (b)Audiology 表示选定特定类所表现的决策值。 0.9 0 单特定类（决策值：5 0.8 多特定类（决策值：5,6） 由图1可知，选取特定类数量相对全部决策 0.7 。一全决策类 类数量较少时，约简效率相较对比算法会有明显 的提升，这是由于多特定类广义决策约简的差别 0.5 0.4 矩阵中非空属性集的数目小于全决策类广义决策 0.3 约简的差别矩阵中非空属性集的数目，所以MG 0.2 0.1 DRDM算法在构造差别矩阵时耗时会有所减 少。另外，因多特定类广义决策约简的差别矩阵 0 345678910 属性数量 中非空属性集数目偏少，所以构造区分函数以及 (c)Glass 求取极小析取范式耗时相对较少，因此约简效率 5.0 0 单特定类（决策值0） 4.5 。-多特定类（决策值0,2） 更高。除此之外，随着属性数目的增加，算法之 4.0 4一全决策类 间耗时差距越发明显，这是由于随着属性数目的 3.5 3.0 增加，差别矩阵也愈加复杂，使得构造区分函数 2.5 以及计算极小析取范式时计算量增大，而且MG DRDM算法构造差别矩阵中非空属性集数目较 1.0 少，所以耗时增长缓慢，两个算法之间耗时差距 0.5 越明显。当多特定类选择为所有决策类时，算法 4. 1012 属性数量 退化为全类约简，此时约简效率并无明显提升。 (d)House
小析取范式时，MGDRDM 算法也将占用更小空 间。当选定特定类为全部决策类时，MGDRDM 算法将退化为全决策类约简，占用空间不会减小。 表 4 差别矩阵非空属性集占比 Table 4 The proportion of non-empty attribute sets in the discernibility matrix ID 数据集 全决策类 单特定类 多特定类 占比/% 决策值 占比/% 决策值 占比/% 1 Zoo 75.7 2 11.2 2,4 20.1 2 Audiology 85.0 4 9.6 1,4,6,11 22.9 3 Glass 71.3 6 5.8 5,6 10.2 4 House 22.2 0 3.1 0,2 6.7 5 Connectionist 90.8 0 8.3 0,2 16.6 6 Yeast 53.5 5 4.3 5,8 7.1 3.3 约简效率对比 本节将 6 组数据集，依据随属性数目递增的 时间消耗进行经典不完备决策系统广义决策约简 与 MGDRDM 算法之间约简效率对比。约简效率 如图 1 所示，其中“全决策类”表示经典全类不完 备决策系统广义决策约简算法随属性数目增加的 约简耗时变化曲线，“单特定类”和“多特定类”则 表示 MGDRDM 算法分别选定一个和多个特定类 随属性数目增加的约简耗时变化曲线，“决策值” 表示选定特定类所表现的决策值。 由图 1 可知，选取特定类数量相对全部决策 类数量较少时，约简效率相较对比算法会有明显 的提升，这是由于多特定类广义决策约简的差别 矩阵中非空属性集的数目小于全决策类广义决策 约简的差别矩阵中非空属性集的数目，所以 MGDRDM 算法在构造差别矩阵时耗时会有所减 少。另外，因多特定类广义决策约简的差别矩阵 中非空属性集数目偏少，所以构造区分函数以及 求取极小析取范式耗时相对较少，因此约简效率 更高。除此之外，随着属性数目的增加，算法之 间耗时差距越发明显，这是由于随着属性数目的 增加，差别矩阵也愈加复杂，使得构造区分函数 以及计算极小析取范式时计算量增大，而且 MGDRDM 算法构造差别矩阵中非空属性集数目较 少，所以耗时增长缓慢，两个算法之间耗时差距 越明显。当多特定类选择为所有决策类时，算法 退化为全类约简，此时约简效率并无明显提升。 某些情况下，添加属性求解约简反而会使耗 时减少，这可能是因为在添加属性之后构造差别 矩阵的过程中产生了较添加属性之前更短的非空 属性集，这使得构造区分函数以及求取极小析取 范式的过程耗时减少，所以在某些情况添加属性 反而求解更快。 2 4 6 8 10 12 14 16 属性数量 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 约简耗时/s 单特定类 (决策值:2) 多特定类 (决策值:2,4) 全决策类 10 20 30 40 50 60 属性数量 0 2 4 6 8 10 12 14 16 18 20 约简耗时/s 单特定类 (决策值:4) 多特定类 (决策值:1,4,6,11) 全决策类 (a) Zoo 1 2 3 4 5 6 7 8 9 10 属性数量 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 约简耗时/s 单特定类(决策值:5) 多特定类(决策值:5,6) 全决策类 (c) Glass (b) Audiology 单特定类 (决策值:0) 多特定类 (决策值:0,2) 全决策类 2 4 6 8 10 12 属性数量 0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 约简耗时/s (d) House ·1206· 智 能 系 统 学 报 第 14 卷
第6期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1207· 单特定类（决策值：0） 计算机学报，2009,32(7)：1229-1246 。一多特定类（决策值：0,2） 5 。一全决策类 WANG Guoyin,YAO Yiyu,YU Hong.A survey on rough set theory and applications[J].Chinese journal of com- puters,.2009,32(7):1229-1246 [5]于洪，王国胤，姚一豫.决策粗糙集理论研究现状与展望 [U.计算机学报，2015,38(8)：1628-1639. YU Hong,WANG Guoyin,YAO Yiyu.Current research and future perspectives on decision-theoretic rough sets[J] 2345678910 Chinese journal of computers,2015,38(8):1628-1639. 属性数量 (e)Connectionist [6]张文修，米据生，吴伟志.不协调目标信息系统的知识约 简[J.计算机学报，2003,26(1)少12-18. 20 单特定类（决策值：5） 。一多特定类（决策值：5,8） ZHANG Wenxiu,MI Jusheng,WU Weizhi.Knowledge 18 16 。一全决策类 reductions in inconsistent information systems[J].Chinese 14 journal of computers,2003,26(1):12-18. 12 10 [7]MIAO D Q,ZHAO Y,YAO YY,et al.Relative reducts in 8 consistent and inconsistent decision tables of the Pawlak 6 rough set model[J].Information sciences,2009,179(24): 4140-4150. 2 345 6 78 [8]HU Qinghua,ZHANG Lingjun,ZHOU Yucan,et al. 属性数量 Large-scale multimodality attribute reduction with multi- (f)Yeast kernel fuzzy rough sets[J].IEEE transactions on fuzzy sys- 图1约简效率 tems,2018,26(1226-238 Fig.1 Reduction efficiency [9]QIAN Yuhua,LIANG Jiye,PEDRYCZ W,et al.Positive approximation:an accelerator for attribute reduction in 4结束语 rough set theory[J].Artificial intelligence,2010,174 (9/10):597-618. 属性约简作为数据分析预处理的重要手段之 [10]WU Weizhi,QIAN Yuhua,LI Tongjun,et al.On rule ac- 一，能够提取更加泛化的规则，压缩数据规模，使 quisition in incomplete multi-scale decision tables[J].In- 得数据分析更加准确、高效，具有重要意义。 formation sciences,2017.378:282-302. 本文提出了基于多特定类的不完备决策系统 广义决策约简基本理论框架，定义了多特定类的 [11]YAO Yiyu,ZHANG Xianyong.Class-specific attribute reducts in rough set theory[J].Information sciences,2017, 不完备决策系统广义决策约简基本定义，并构造 418/419:601-618. 相应差别矩阵以及区分函数，提出基于差别矩阵 [12]LI Jingzheng,YANG Xibei,SONG Xiaoning,et al. 的约简算法并通过6组UCI数据集验证了算法的 Neighborhood attribute reduction:a multi-criterion ap- 有效性。本文提出约简算法是基于差别矩阵求取 proach[J].International journal of machine learning and 所有约简，为提升算法效率，差别矩阵优化是将 cybernetics.2019,10(4):731-742, 来研究的重要问题。 [13]LIANG Jiye,XU Zongben.The algorithm on knowledge 参考文献： reduction in incomplete information systems[J].Interna- tional journal of uncertainty,fuzziness and knowledge- [1]PAWLAK Z.Rough sets[J].International journal of com- based systems,2002,10(1):95-103. puter and information sciences,1982,11(5):341-356. [2]PAWLAK Z.Rough sets:theoretical aspects of reasoning [14)]周献中，黄兵，李华雄，等.不完备信息系统知识获取的 粗糙集理论与方法M.南京：南京大学出版社，2010. about data[M].Dordrecht:Kluwer Academic Publishers, 1991 [15]QIAN Yuhua,LIANG Jiye,LI Deyu,et al.Approxima- [3]ZHANG Qinghua,ZHANG Pei,WANG Guoyin.Re- tion reduction in inconsistent incomplete decision search on approximation set of rough set based on fuzzy tables[J].Knowledge-based systems,2010.23(5): similarity[J].Journal of intelligent and fuzzy systems, 427-433 2017,32(3):2549-2562. [16]SHU Wenhao,QIAN Wenbin.A fast approach to attrib- [4]王国胤，姚一豫，于洪.粗糙集理论与应用研究综述U。 ute reduction from perspective of attribute measures inin-
4 结束语 属性约简作为数据分析预处理的重要手段之 一，能够提取更加泛化的规则，压缩数据规模，使 得数据分析更加准确、高效，具有重要意义。 本文提出了基于多特定类的不完备决策系统 广义决策约简基本理论框架，定义了多特定类的 不完备决策系统广义决策约简基本定义，并构造 相应差别矩阵以及区分函数，提出基于差别矩阵 的约简算法并通过 6 组 UCI 数据集验证了算法的 有效性。本文提出约简算法是基于差别矩阵求取 所有约简，为提升算法效率，差别矩阵优化是将 来研究的重要问题。 参考文献： PAWLAK Z. Rough sets[J]. International journal of computer and information sciences, 1982, 11(5): 341–356. [1] PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Dordrecht: Kluwer Academic Publishers, 1991. [2] ZHANG Qinghua, ZHANG Pei, WANG Guoyin. Research on approximation set of rough set based on fuzzy similarity[J]. Journal of intelligent and fuzzy systems, 2017, 32(3): 2549–2562. [3] [4] 王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述 [J]. 计算机学报, 2009, 32(7): 1229–1246. WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and applications[J]. Chinese journal of computers, 2009, 32(7): 1229–1246. 于洪, 王国胤, 姚一豫. 决策粗糙集理论研究现状与展望 [J]. 计算机学报, 2015, 38(8): 1628–1639. YU Hong, WANG Guoyin, YAO Yiyu. Current research and future perspectives on decision-theoretic rough sets[J]. Chinese journal of computers, 2015, 38(8): 1628–1639. [5] 张文修, 米据生, 吴伟志. 不协调目标信息系统的知识约 简 [J]. 计算机学报, 2003, 26(1): 12–18. ZHANG Wenxiu, MI Jusheng, WU Weizhi. Knowledge reductions in inconsistent information systems[J]. Chinese journal of computers, 2003, 26(1): 12–18. [6] MIAO D Q, ZHAO Y, YAO Y Y, et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model[J]. Information sciences, 2009, 179(24): 4140–4150. [7] HU Qinghua, ZHANG Lingjun, ZHOU Yucan, et al. Large-scale multimodality attribute reduction with multikernel fuzzy rough sets[J]. IEEE transactions on fuzzy systems, 2018, 26(1): 226–238. [8] QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial intelligence, 2010, 174 (9/10): 597–618. [9] WU Weizhi, QIAN Yuhua, LI Tongjun, et al. On rule acquisition in incomplete multi-scale decision tables[J]. Information sciences, 2017, 378: 282–302. [10] YAO Yiyu, ZHANG Xianyong. Class-specific attribute reducts in rough set theory[J]. Information sciences, 2017, 418/419: 601–618. [11] LI Jingzheng, YANG Xibei, SONG Xiaoning, et al. Neighborhood attribute reduction: a multi-criterion approach[J]. International journal of machine learning and cybernetics, 2019, 10(4): 731–742. [12] LIANG Jiye, XU Zongben. The algorithm on knowledge reduction in incomplete information systems[J]. International journal of uncertainty, fuzziness and knowledgebased systems, 2002, 10(1): 95–103. [13] 周献中, 黄兵, 李华雄, 等. 不完备信息系统知识获取的 粗糙集理论与方法 [M]. 南京: 南京大学出版社, 2010. [14] QIAN Yuhua, LIANG Jiye, LI Deyu, et al. Approximation reduction in inconsistent incomplete decision tables[J]. Knowledge-based systems, 2010, 23(5): 427–433. [15] SHU Wenhao, QIAN Wenbin. A fast approach to attribute reduction from perspective of attribute measures in in- [16] 单特定类 (决策值:0) 多特定类 (决策值:0,2) 全决策类 单特定类 (决策值:5) 多特定类 (决策值:5,8) 全决策类 1 2 3 4 5 6 7 8 9 10 属性数量 0 1 2 3 4 5 6 约简耗时/s (e) Connectionist 1 2 3 4 5 6 7 8 属性数量 0 2 4 6 8 10 12 14 16 18 20 约简耗时/s (f) Yeast 图 1 约简效率 Fig. 1 Reduction efficiency 第 6 期 唐玉凯，等：不完备决策系统下的多特定类广义决策约简 ·1207·
·1208· 智能系统学报 第14卷 complete decision systems[J].Knowledge-based systems, [23]QIAN Yuhua,LIANG Xinyan,WANG Qi,et al.Local 2014.72:60-71. rough set:a solution to rough data analysis in big data[]. [17]QIAN Wenbin,SHU Wenhao,XIE Yonghong,et al.Fea- International journal of approximate reasoning,2018,97: ture selection using compact discernibility matrix-based 38-63. approach in dynamic incomplete decision system[J]. [24]LIU Guilong,HUA Zheng,ZOU Jiyang.Local attribute Journal of information science and engineering,2015, reductions for decision tables[J].Information sciences, 31(2):509-527. 2018.422:204-217. [18]XIE Xiaojun,QIN Xiaolin.A novel incremental attribute 作者简介： reduction approach for dynamic incomplete decision sys- 唐玉凯，男，1996年生，硕士研究 tems[J].International journal of approximate reasoning, 生，主要研究方向为粗糙集、数据挖掘 2018.93:443-462 与机器学习。 [19]SKOWRON A.Boolean reasoning for decision rules gen- eration[C]//Proceedings of the 7th International Symposi- um on Methodologies for Intelligent Systems.Trondheim. Norway,.1993:295-305. [20]KRYSZKIEWICZ M.Rough set approach to incomplete 张楠.男，1979年生，讲师，主要 information systems[J].Information sciences,1998, 研究方向为粗糙集、认知信息学与人 112(1/2/3/4):39-49 工智能。 [21]SKOWRON A,RAUSZER C.The discernibility matrices and functions in information systems[M]//SLOWINSKI R.Intelligent Decision Support:Handbook of Applica- tions and Advances of the Rough Sets Theory.Dordrecht, Netherlands:Springer,1992:331-362. 童向荣，男，1975年生，教授，主 要研究方向为多Agent系统、分布式 [22]尹继亮，张楠，赵立威，等.区间值决策系统的局部属性 人工智能与数据挖掘技术。主持国家 约简计算机科学，2018,45(7)：178-185 自然科学基金面上项目2项，发表学 YIN Jiliang,ZHANG Nan,ZHAO Liwei,et al.Local at- 术论文50余篇。 tribute reduction in interval-valued decision systems[J]. Computer science,2018,45(7):178-185
complete decision systems[J]. Knowledge-based systems, 2014, 72: 60–71. QIAN Wenbin, SHU Wenhao, XIE Yonghong, et al. Feature selection using compact discernibility matrix-based approach in dynamic incomplete decision system[J]. Journal of information science and engineering, 2015, 31(2): 509–527. [17] XIE Xiaojun, QIN Xiaolin. A novel incremental attribute reduction approach for dynamic incomplete decision systems[J]. International journal of approximate reasoning, 2018, 93: 443–462. [18] SKOWRON A. Boolean reasoning for decision rules generation[C]//Proceedings of the 7th International Symposium on Methodologies for Intelligent Systems. Trondheim, Norway, 1993: 295–305. [19] KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1/2/3/4): 39–49. [20] SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[M]//SŁOWIŃSKI R. Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht, Netherlands: Springer, 1992: 331–362. [21] 尹继亮, 张楠, 赵立威, 等. 区间值决策系统的局部属性 约简 [J]. 计算机科学, 2018, 45(7): 178–185. YIN Jiliang, ZHANG Nan, ZHAO Liwei, et al. Local attribute reduction in interval-valued decision systems[J]. Computer science, 2018, 45(7): 178–185. [22] QIAN Yuhua, LIANG Xinyan, WANG Qi, et al. Local rough set: a solution to rough data analysis in big data[J]. International journal of approximate reasoning, 2018, 97: 38–63. [23] LIU Guilong, HUA Zheng, ZOU Jiyang. Local attribute reductions for decision tables[J]. Information sciences, 2018, 422: 204–217. [24] 作者简介： 唐玉凯，男，1996 年生，硕士研究 生，主要研究方向为粗糙集、数据挖掘 与机器学习。 张楠，男，1979 年生，讲师，主要 研究方向为粗糙集、认知信息学与人 工智能。 童向荣，男，1975 年生，教授，主 要研究方向为多 Agent 系统、分布式 人工智能与数据挖掘技术。主持国家 自然科学基金面上项目 2 项，发表学 术论文 50 余篇。 ·1208· 智 能 系 统 学 报 第 14 卷