第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·