第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201710011 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180408.1625.026.html 不协调区间值决策系统的最大分布约简 尹继亮2，张楠2，童向荣12，陈曼如2 (1.烟台大学数据科学与智能技术山东省高校重点实验室，山东烟台264005,2.烟台大学计算机与控制工程学院， 山东烟台264005) 摘要：分布式约简可以保证约简前后决策系统各规则的置信度保持不变，是属性约简的重要方法之一。最大分布 式约简保持了约简前后决策系统中可信程度最大的规则不变，提取置信度较大的规则在智能决策中具有广泛的应用 价值。本文在相容关系下的不协调区间值决策系统中引入最大置信度的概念，构造最大分布保持不变的可辨识矩 阵，并给出基于可辨识矩阵的最大分布约简算法。分析了不协调区间值决策系统的最大分布约简算法与其它约简算 法之间的关系。最后，利用UCI标准数据集进行了实验验证，实验结果表明了算法的有效性。 关键词：分布式约简：最大分布约简：置信度：相容关系：可辨识矩阵：不协调：区间值：决策系统 中图分类号：TP181文献标志码：A文章编号：1673-4785(2018)03-0469-10 中文引用格式：尹继亮，张楠，童向荣，等.不协调区间值决策系统的最大分布约简.智能系统学报，2018,133：469-478 英文引用格式：YIN Jiliang.,ZHANG Nan,TONG Xiangrong,.etal.Maximum distribution reduction in inconsistent interval--va- ued decision systems[J].CAAI transactions on intelligent systems,2018,13(3):469-478. Maximum distribution reduction in inconsistent interval-valued decision systems YIN Jiliang,ZHANG Nan2,TONG Xiangrong2,CHEN Manru'2 (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) Abstract:Distribution reduction is one of the important methods of attribute reduction as it can guarantee consistent confidence coefficients of all decision rules before and after reduction.Maximum distributed reduction keeps the un- changed rule with the highest confidence coefficient in the decision system,and extracting a rule with a high confidence coefficient has a wide application value.This paper introduces the concept of maximum confidence coefficient for in- consistent interval-valued decision systems based on compatibility relation and proposes a maximum distribution reduc- tion algorithm based on discernibility matrix,whereby a discernibility matrix is constructed to keep the unchanged max- imum distribution.The relationship between the maximum distribution reduction algorithm in inconsistent interval-val- ued decision systems and other reduction algorithms was analyzed.Experiments were performed using UCI standard data sets,and the proposed algorithm proved to be effective. Keywords:distributed reduction:maximum distributed reduction:confidence coefficient:compatibility relation;dis- cernibility matrix;inharmonious;interval-valued;decision system 属性约简”是粗糙集理论的核心研究内容 处理等领域取得了诸多研究成果。属性约简的目的 之一，在数据挖掘、机器学习、决策分析、智能信息 是删除冗余属性，只保留使决策表某种分类特征不 收稿日期：2017-10-16.网络出版日期：2018-04-08. 变的最小属性子集。差别矩阵方法是一种用于求取 基金项目：国家自然科学基金项目(61403329.61572418.61702439. 61572419,61502410):山东省自然科学基金项目 所有属性约简的有效方法，该方法由Skowron!侧 (ZR2016FM42):烟台大学研究生科技创新基金项目 于1982年提出，并将差别矩阵应用于正域约简中。诸 (YDZD1807). 通信作者：张楠.E-mail:zhangnant0851@l63.com. 多学者在此基础上做了大量的研究工作。Kysz水ie
DOI: 10.11992/tis.201710011 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180408.1625.026.html 不协调区间值决策系统的最大分布约简 尹继亮1,2，张楠1,2，童向荣1,2，陈曼如1,2 （1. 烟台大学 数据科学与智能技术山东省高校重点实验室，山东 烟台 264005; 2. 烟台大学 计算机与控制工程学院， 山东 烟台 264005） 摘 要：分布式约简可以保证约简前后决策系统各规则的置信度保持不变，是属性约简的重要方法之一。最大分布 式约简保持了约简前后决策系统中可信程度最大的规则不变，提取置信度较大的规则在智能决策中具有广泛的应用 价值。本文在相容关系下的不协调区间值决策系统中引入最大置信度的概念，构造最大分布保持不变的可辨识矩 阵，并给出基于可辨识矩阵的最大分布约简算法。分析了不协调区间值决策系统的最大分布约简算法与其它约简算 法之间的关系。最后，利用 UCI 标准数据集进行了实验验证，实验结果表明了算法的有效性。 关键词：分布式约简；最大分布约简；置信度；相容关系；可辨识矩阵；不协调；区间值；决策系统 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2018)03−0469−10 中文引用格式：尹继亮, 张楠, 童向荣, 等. 不协调区间值决策系统的最大分布约简[J]. 智能系统学报, 2018, 13(3): 469–478. 英文引用格式：YIN Jiliang, ZHANG Nan, TONG Xiangrong, et al. Maximum distribution reduction in inconsistent interval-valued decision systems[J]. CAAI transactions on intelligent systems, 2018, 13(3): 469–478. Maximum distribution reduction in inconsistent interval-valued decision systems YIN Jiliang1,2 ，ZHANG Nan1,2 ，TONG Xiangrong1,2 ，CHEN Manru1,2 (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) Abstract: Distribution reduction is one of the important methods of attribute reduction as it can guarantee consistent confidence coefficients of all decision rules before and after reduction. Maximum distributed reduction keeps the unchanged rule with the highest confidence coefficient in the decision system, and extracting a rule with a high confidence coefficient has a wide application value. This paper introduces the concept of maximum confidence coefficient for inconsistent interval-valued decision systems based on compatibility relation and proposes a maximum distribution reduction algorithm based on discernibility matrix, whereby a discernibility matrix is constructed to keep the unchanged maximum distribution. The relationship between the maximum distribution reduction algorithm in inconsistent interval-valued decision systems and other reduction algorithms was analyzed. Experiments were performed using UCI standard data sets, and the proposed algorithm proved to be effective. Keywords: distributed reduction; maximum distributed reduction; confidence coefficient; compatibility relation; discernibility matrix; inharmonious; interval-valued; decision system 属性约简[1-7]是粗糙集理论[1-3]的核心研究内容 之一，在数据挖掘、机器学习、决策分析、智能信息 处理等领域取得了诸多研究成果。属性约简的目的 是删除冗余属性，只保留使决策表某种分类特征不 变的最小属性子集。差别矩阵方法是一种用于求取 所有属性约简的有效方法，该方法由 Skowron[ 8 ] 于 1982 年提出，并将差别矩阵应用于正域约简中。诸 多学者在此基础上做了大量的研究工作。Kryszkie- 收稿日期：2017−10−16. 网络出版日期：2018−04−08. 基金项目：国家自然科学基金项目 (61403329，61572418，61702439， 61572419，61502410)；山东省自然科学基金项目 (ZR2016FM42)；烟台大学研究生科技创新基金项目 (YDZD1807). 通信作者：张楠. E-mail：zhangnan0851@163.com. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018
·470· 智能系统学报 第13卷 wicz于1999年在不完备信息系统下引入广义决策 属性ak上的区间属性值，即对任意的x:∈U,a∈AT, 保持约简的概念，并提出基于差别矩阵的广义决策 有fx,a)=a4(x)=[,]o 保持约简方法；2007年，邓大勇等1首先分析了不 如果属性集AT由条件属性集C和决策属性集 相容信息系统下几种约简目标之间的关系；2009 D组成，C={a1,a2,…agh,D={d,即CUD=AT;V= 年，Miao等进一步分析了3种约简目标之间的关 VeU Vp,.其中，Vc为条件属性值集合，V,为决策属性 系，提出不可分辨关系保持约简以及相应的差别矩 值集合；f:U×C→Vc为区间值映射，f:U×D→Vo 阵构造方法；Zhou等在2011年对现有的13种属 为单值映射，则称区间值信息系统为区间值决策系 性约简目标进行总结，并将所有约简目标分为 统DS=(U,CUD,V,f)e 4类，完善了现有约简目标之间的关系。 定义1设=[，]和=[，1为任意两个区 分布约简保持了信息系统约简前后每条规则置 间值，则区间值的交运算与并运算如下。 信度不变。2003年，张文修等1提出了分配约简、 1)区间值交运算为 分布约简以及最大分布约简的概念，并分别给出了 0,(<)v(t<) 基于差别矩阵的分配约简、分布约简以及最大分布 hn2={ [max(,),min(,t】,其他 约简方法；2007年，徐伟华等在优势关系下提出 2)区间值并运算为 了两种约简概念，即分布约简和最大分布约简，同 U2=[min(,,max(,t】 时建立了基于差别矩阵的分布和最大分布约简的具 目前，度量区间值相似度比较合理的主要方法 体方法。如某一段时间内的温度、湿度等区间值数 有Jaccard相似率、悲观相似率和乐观相似率，本文 据在现实环境中大量存在，它较好地表示了许多不 统一采用Jaccard相似率来度量两个区间值的相似度。 确定类型数据，区间值决策系统是经典Pawlak决策 定义2DS=(U,CUD,Vf)为区间值决策系统， 系统的推广，充分地考虑了数据的不确定性，在近 对任意的x,x∈U,∈C,区间值a(x)=[,的和 几年得到了广泛关注。2009年，张楠等1定义了- a(x)=[,1的Jaccard相似率定义为 极大相容类的概念，提出了区间值决策系统的广义 决策保持约简：2016年，张楠等16在不协调区间值 0岛 决策系统中提出确定性规则保持约简；2016年，张 Jaccard相似率为两个区间数的交集与并集长 楠等讨论了不协调区间值决策系统中的知识约简 度的比值，它适合度量长度相似的两个区间数。 并提出了分布约简的概念。 例1区间值决策系统DS=(U,CUD,V,f),如 基于上述研究，文献[13]和14]分别对等价关系 表1所示，其中，U={x,2,…,x6为对象的集合，C= 和优势关系下的最大分布约简进行了研究，但未有 {a1,a2,a3,a4}为条件属性的集合，D={d为决策属性。 区间值决策系统的最大分布约简讨论。置信度表示 表1不协调区间值决策系统 了信息系统中规则的可信程度，置信度越大，规则 Table 1 Inconsistent interval-valued decision systems 的可信程度越高：置信度越小规则的可信程度越 U da d 低，在实际应用中，人们往往关注置信度最大的规 x10.863.131「-0.20,2.231「-0.26,2.261「-0.19.2.2011 则。为此，本文提出了区间值决策系统的最大分布 x2-0.12,2.1310.79,3.201 [0.73,3.26 [0.73,3.26]2 约简概念，为区间值决策系统提供了一种求取所有 属性约简的新方法。 x3【-0.13,2.20][0.86,2.95] 【-0.26,2.26]【-0.24,2.12]2 【-0.14,2.01 [0.853.011 0.71,3.11] -0.24,2.11]2 1基本知识 5【-0.13,2.13] 0.79,2.941-0.262.231 -0.252.3011 1.1区间值决策系统的粗糙近似 x6「-0.13,2.131[0.82,3.101 [-0.24,2.19] [-0.24,2.11]1 基于相容关系的区间值粗糙集模型是经典 令1=[，]，1=，，分别计算n和n2的交 Pawlak粗糙集模型的推广，首先给出相关概念和 并： 性质。 给定区间值信息系统1s1S=(U,AT,Vf,其 1n2=[0.86,3.13]n[-0.12,2.13]=[0.86,2.13] 1U2=[0.86,3.13]U[-0.12,2.13]=[-0.12,3.13] 中，U是有限对象集合，U={x1,2,…,h:AT是有限 计算n,和n2的Jaccard相似率： 属性集合，AT={a,a2,…,am;V是全体属性的值 ,1n5.=0.391 域，即V=U_Va,Va是属性a∈AT的值域；f:UXAT→ 4,]U[,] EAT V是一个信息函数，它指定论域U中每一个对象x在 定义315] 对于区间值决策系统DS=(U,CU
wicz[9]于 1999 年在不完备信息系统下引入广义决策 保持约简的概念，并提出基于差别矩阵的广义决策 保持约简方法；2007 年，邓大勇等[10]首先分析了不 相容信息系统下几种约简目标之间的关系；2009 年，Miao 等 [11]进一步分析了 3 种约简目标之间的关 系，提出不可分辨关系保持约简以及相应的差别矩 阵构造方法；Zhou 等 [12]在 2011 年对现有的 13 种属 性约简目标进行总结，并将所有约简目标分为 4 类，完善了现有约简目标之间的关系。 α 分布约简保持了信息系统约简前后每条规则置 信度不变。2003 年，张文修等[13]提出了分配约简、 分布约简以及最大分布约简的概念，并分别给出了 基于差别矩阵的分配约简、分布约简以及最大分布 约简方法；2007 年，徐伟华等[14]在优势关系下提出 了两种约简概念，即分布约简和最大分布约简，同 时建立了基于差别矩阵的分布和最大分布约简的具 体方法。如某一段时间内的温度、湿度等区间值数 据在现实环境中大量存在，它较好地表示了许多不 确定类型数据，区间值决策系统是经典 Pawlak 决策 系统的推广，充分地考虑了数据的不确定性，在近 几年得到了广泛关注。2009 年，张楠等[15]定义了 - 极大相容类的概念，提出了区间值决策系统的广义 决策保持约简；2016 年，张楠等[16]在不协调区间值 决策系统中提出确定性规则保持约简；2016 年，张 楠等[17]讨论了不协调区间值决策系统中的知识约简 并提出了分布约简的概念。 基于上述研究，文献[13]和[14]分别对等价关系 和优势关系下的最大分布约简进行了研究，但未有 区间值决策系统的最大分布约简讨论。置信度表示 了信息系统中规则的可信程度，置信度越大，规则 的可信程度越高；置信度越小，规则的可信程度越 低，在实际应用中，人们往往关注置信度最大的规 则。为此，本文提出了区间值决策系统的最大分布 约简概念，为区间值决策系统提供了一种求取所有 属性约简的新方法。 1 基本知识 1.1 区间值决策系统的粗糙近似 基于相容关系的区间值粗糙集模型是经典 Pawlak 粗糙集模型的推广，首先给出相关概念和 性质。 IS = (U,AT,V, f) U U = {x1, x2,··· , x|U|} AT AT = {a1,a2,··· ,a|AT|} V V = ∪ ak∈AT Vak Vak ak ∈ AT f :U×AT → U xi 给定区间值信息系统[ 1 5 - 1 8 ] ，其 中， 是有限对象集合， ； 是有限 属性集合， ； 是全体属性的值 域，即 ， 是属性 的值域； V 是一个信息函数，它指定论域 中每一个对象 在 xi ∈ U ak ∈ AT f(xi ,ak) = ak(xi) =[l k i ,u k i ] 属性 ak 上的区间属性值，即对任意的 ， ， 有 。 AT D C = {a1,a2,···a|C|} D = {d} C ∪ D= AT VC ∪VD VC VD f : U ×C → VC f : U × D → VD DS = (U,C ∪ D,V, f) 如果属性集 由条件属性集 C 和决策属性集 组成， ， ，即 ；V = ，其中， 为条件属性值集合， 为决策属性 值集合； 为区间值映射， 为单值映射，则称区间值信息系统为区间值决策系 统 。 η1=[l k i ,u k i ] η2=[l k j ,u k j 定义 1 设 和 ] 为任意两个区 间值，则区间值的交运算与并运算如下。 1) 区间值交运算为 η1 ∩η2 = { 0, (u k i < l k j )∨(u k j < l k i ) [max(l k i ,l k j ),min(u k i ,u k j )], 其他 2) 区间值并运算为 η1 ∪η2 = [min(l k i ,l k j ),max(u k i ,u k j )] 目前，度量区间值相似度比较合理的主要方法 有 Jaccard 相似率、悲观相似率和乐观相似率，本文 统一采用 Jaccard 相似率来度量两个区间值的相似度。 DS = (U,C ∪ D,V, f) xi , xj ∈ U ak ∈ C ak(xi)= [l k i ,u k i ] ak(xj) = [l k j ,u k j ] α k i j 定义 2 为区间值决策系统， 对任意的 ， ，区间值 和 的 Jaccard 相似率[18] 定义为 α k i j= |[l k i ,u k i ]∩[l k j ,u k j ]| |[l k i ,u k i ]∪[l k j ,u k j ]| Jaccard 相似率为两个区间数的交集与并集长 度的比值，它适合度量长度相似的两个区间数。 DS = (U,C ∪ D,V, f) U = {x1, x2,··· , x6} {a1,a2,a3,a4} D ={d} 例 1 区间值决策系统 ，如 表 1 所示，其中， 为对象的集合，C = 为条件属性的集合， 为决策属性。 表 1 不协调区间值决策系统 Table 1 Inconsistent interval-valued decision systems U a1 a2 a3 a4 d x1 [0.86,3.13] [–0.20,2.23] [–0.26,2.26] [–0.19,2.20] 1 x2 [–0.12,2.13] [0.79,3.20] [0.73,3.26] [0.73,3.26] 2 x3 [–0.13,2.20] [0.86,2.95] [–0.26,2.26] [–0.24,2.12] 2 x4 [–0.14,2.01] [0.85,3.01] [0.71,3.11] [–0.24,2.11] 2 x5 [–0.13,2.13] [0.79,2.94] [–0.26,2.23] [–0.25,2.30] 1 x6 [–0.13,2.13] [0.82,3.10] [–0.24,2.19] [–0.24,2.11] 1 η1 = [l 1 1 ,u 1 1 ] η1 = [l 1 2 ,u 1 2 令 ， ] ，分别计算 η1和 η2的交、 并： η1 ∩η2 = [0.86,3.13]∩[−0.12,2.13] = [0.86,2.13] η1 ∪η2 = [0.86,3.13]∪[−0.12,2.13] = [−0.12,3.13] 计算 η1和 η2的 Jaccard 相似率： α 1 12 = |[l 1 1 ,u 1 1 ]∩[l 1 2 ,u 1 2 ]| |[l 1 1 ,u 1 1 ]∪[l 1 2 ,u 1 2 ]| = 0.391 定义 3 DS = (U,C∪ [ 1 5 ] 对于区间值决策系统 ·470· 智 能 系 统 学 报 第 13 卷
第3期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·471· D,Vf),a∈C,a∈[0,1，则关于条件属性a的a-相容 比例，近似分类精度越大，区间值信息系统中确定 关系定义为 性规则越多；反之，确定性规则越少。 Ta,={,,x）eU×U,a>al 定义6对于区间值决策系统DS=(U,CUD,Y 其中a哈，表示对象x,和对象x,关于属性a的a-Jac- ),AsC,决策属性D对U的划分为UID= card相似度，简称a-相似度。 (D,D2,…,DuI,决策属性D关于a-相容关系的 关于条件属性子集AsU的-相容关系定义为 上、下近似分别定义为 T={x,xx,x)∈U×U,a崎>a,a∈A】 apr(D)={xk,∈U,D,∈U/D,S(x)nD,≠O} 性质1s1对于区间值决策系统DS=(U,CU apr(D)={xk∈U,D,∈U/D,S(x)D,} D,Vf),AcC,a∈A,a∈[0,1，T是属性a的a-相容 决策属性D关于α-相容关系的正域定义为 关系，则关于集合A的相容关系为 POS(D)=apr(D) T=0 Tio 定义8161设区间值决策系统DS=(,CUD 性质218]设区间值决策系统DS=(U,CUD, V,f),AsC,决策属性D对U的划分为U/D={D, V,fD,AcC,则T具有： D2,·,Duo山，则在决策属性D下，关于条件属性集 1)自反性：任意x∈U,则(x,x)∈TA。 A的近似分类精度定为 2)对称性：任意x,x∈U,若(x,)∈TA,则 lapr(D列 (xnx)∈TA。 (D)= lapr(D) 3)非传递性：任意x,xx∈U,若满足(c,x)E 定义5和定义6是关于集合x的上、下近似和 T和(x,x)∈TA,则(x,x）∈T不一定成立。 近似分类精度，而定义7和定义8是关于决策属性 定义411设区间值决策系统DS=(U,CUD, D的上、下近似和近似分类精度。 VfD,AcC,a∈0,1，T是属性集A的a-相容关系， 定义g鬥对于区间值决策系统DS=(U,CUD,Vf), 则关于对象x,在属性集A下的α-相容类定义为 对任意x,x∈U,且i≠j,若x和x具有a-相容关系， SR(x)={x,x,∈U,(x,x)∈T} 对任意x∈U,区间值决策系统DS在阈值α下的 且满足d(x)=d(x),则称x∈U是关于属性集AsC的 相容类集合定义为 a-协调对象：否则称为α-不协调对象。 S(U)={S(x),S(2,…,Sgxn)} 若存在一个对象x∈U是关于ASC的-不协调 其中n是论域的个数。 对象，那么称DS为不协调区间值决策表，否则称为 经典粗糙集中对象间的二元关系为等价关系， 协调区间值决策表。 具有自反性、传递性、对称性，导出的等价类集合是 例2如表1所示的区间值决策系统，令α=0.6， 对论域的划分，而定义4中的相容类是对论域的 则相容关系T06为 覆盖。 100000 定义5给定区间值决策系统DS=(U,CUD,Vf), 010000 001011 S(x)是在相容关系下包含x的相容类，则对象集合 T0.6 000100 X关于a-相容关系的上、下近似四分别定义为 001011 001011 apr(X)={xx∈U,S()nX≠O) api(X)={x∈U,S(x)X) 根据相似率布尔矩阵，计算阈值α=0.6下的相 集合x关于α-相容关系的正域为 容类集合为 POS(X)=apr(X) S6(U={Se6(x),S6(2.…,S6(x6》 下近似是由肯定属于x的对象组成的集合，上 式中：Se6(x1)={x,S6(x2)={2,S6(3)=S6(x)= 近似是由可能属于X的对象组成的集合，根据上下 Se6(x6)={x3,x,6h,Se6(x4)={x}。 近似的概念，决策规则可以分为确定性规则和可能 U/D={,x5,x6,{x2,3,x》为决策属性D对 性规则。 U的划分，计算决策属性D关于相容关系T6的上、 定义69给定区间值决策系统DS=(U,CUD,Vf), 下近似： XsU,AcC,则条件属性集A的近似分类精度定义为 apr6(D)=U,apre6(D)=x. lapr(X) 计算条件属性集C的近似分类精度： (X)= lapr(X) (D)= lapre(D)3 近似分类精度表示确定性规则占可能性规则的 apr吧D1605
D,V, f)，ak ∈ C，α ∈ [0,1] ，则关于条件属性ak的α-相容 关系定义为 T α {ak } = {(xi , xj)|(xi , xj) ∈ U ×U,αk i j > α} α k i j ak α α 其中 表示对象 xi 和对象 xj 关于属性 的 -Jaccard 相似度，简称 -相似度。 关于条件属性子集 A ⊆ U 的α-相容关系定义为 T α A = {(xi , xj)|(xi , xj) ∈ U ×U,αk i j > α,ak ∈ A} DS = (U,C∪ D,V, f) A ⊆ C ak ∈ A α ∈ [0,1] T α {ak} ak α A 性质 1 [ 1 5 ] 对于区间值决策系统 ， ， ， ， 是属性 的 -相容 关系，则关于集合 的相容关系为 T α A = ∩ ak∈A T α {ak} DS = (U,C ∪ D, V, f) A ⊆ C T α A 性质 2 [ 1 8 ] 设区间值决策系统 ， ，则 具有： (xi , xj) ∈ T α 1 A ) 自反性：任意 xi∈U，则 。 (xi , xj) ∈ T α A (xj , xi) ∈ T α A 2) 对称性：任意 x i，x j∈U，若 ，则 。 xi , xj , xk ∈ U (xi , xk) ∈ T α A (xk , xj) ∈ T α A (xi , xj) ∈ T α A 3) 非传递性：任意 ，若满足 和 ，则 不一定成立。 DS = (U,C ∪ D, V, f) A ⊆ C α ∈ [0,1] T α A α 定义 4 [ 1 8 ] 设区间值决策系统 ， ， ， 是属性集 A 的 α-相容关系， 则关于对象 xi 在属性集 A 下的 -相容类定义为 S α A (xi) = {xj |xj ∈ U,(xi , xj) ∈ T α A } 对任意xi ∈ U ，区间值决策系统 DS 在阈值α下的 相容类集合定义为 S α A (U) = {S α A (x1),S α A (x2),··· ,S α A (xn)} 其中n是论域的个数。 经典粗糙集中对象间的二元关系为等价关系， 具有自反性、传递性、对称性，导出的等价类集合是 对论域的划分，而定义 4 中的相容类是对论域的 覆盖。 DS = (U,C ∪ D,V, f) S α A (xi) xi X α 定义 5 给定区间值决策系统 ， 是在相容关系下包含 的相容类，则对象集合 关于 -相容关系的上、下近似[19]分别定义为 aprα A (X) = {xi |xi ∈ U,S α A (xi)∩ X , Ø} aprα A (X) = {xi |xi ∈ U,S α A (xi) ⊆ X} 集合 X 关于α-相容关系的正域为 POSα A (X) = aprα A (X) X X 下近似是由肯定属于 的对象组成的集合，上 近似是由可能属于 的对象组成的集合，根据上下 近似的概念，决策规则可以分为确定性规则和可能 性规则。 DS=(U,C∪D,V, f) X⊆U A⊆C A 定义 6 [16] 给定区间值决策系统 ， ， ，则条件属性集 的近似分类精度定义为 µ α A (X) = |aprα A (X)| |aprα A (X)| 近似分类精度表示确定性规则占可能性规则的 比例，近似分类精度越大，区间值信息系统中确定 性规则越多；反之，确定性规则越少。 DS = (U,C∪D,V, A ⊆ C U {D1,D2,··· ,D|U/D|} α 定义 7 [16] 对于区间值决策系统 f ) ， ，决策属 性 D 对 的划分 为 U / D = ，决策属性 D 关于 -相容关系的 上、下近似分别定义为 aprα A (D) = {xi |xi ∈ U,Dj ∈ U/D,S α A (xi)∩ Dj , Ø} aprα A (D) = {xi |xi ∈ U,Dj ∈ U/D,S α A (xi) ⊆ Dj} 决策属性 D 关于α-相容关系的正域定义为 POSα A (D) = aprα A (D) DS = (U,C ∪ D, V, f) A ⊆ C U U/D = {D1, D2,··· ,D|U/D|} 定义 8 [ 1 6 ] 设区间值决策系统 ， ，决策属性 D 对 的划分为 ，则在决策属性 D 下，关于条件属性集 A 的近似分类精度定为 µ α A (D) = |aprα A (D)| |aprα A (D)| X D 定义 5 和定义 6 是关于集合 的上、下近似和 近似分类精度，而定义 7 和定义 8 是关于决策属性 的上、下近似和近似分类精度。 DS=(U,C∪D,V, f) xi , xj ∈ U i , j xj α d(xi) = d(xj) xi ∈ U A ⊆ C α α 定义 9 [13] 对于区间值决策系统 ， 对任意 ，且 ，若 xi 和 具有 -相容关系， 且满足 ，则称 是关于属性集 的 -协调对象；否则称为 -不协调对象。 xi ∈ U A ⊆ C α DS 若存在一个对象 是关于 的 -不协调 对象，那么称 为不协调区间值决策表，否则称为 协调区间值决策表。 α = 0.6 T 0.6 C 例 2 如表 1 所示的区间值决策系统，令 ， 则相容关系 为 T 0.6 C = 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 根据相似率布尔矩阵，计算阈值α = 0.6 下的相 容类集合为 S 0.6 C (U) = {S 0.6 C (x1),S 0.6 C (x2),··· ,S 0.6 C (x6)} S 0.6 C (x1) = {x1} S 0.6 C (x2) = {x2} S 0.6 C (x3) = S 0.6 C (x5) = S 0.6 C (x6) = {x3, x5, x6} S 0.6 C (x4) = {x4} 式中： ， ， ， 。 U/D = {{x1, x5, x6},{x2, x3, x4}} T 0.6 C 为决策属 性 D 对 U 的划分，计算决策属性 D 关于相容关系 的上、 下近似： apr0.6 C (D) = U apr0.6 C ， (D) = {x1, x2, x4} 计算条件属性集 C 的近似分类精度： µ 0.6 C (D) = |aprα C (D)| |aprα C (D)| = 3 6 = 0.5 第 3 期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·471·
·472· 智能系统学报 第13卷 1.2区间值决策系统的分布约简 根据例2可知相似布尔矩阵以及相容类集合。 文献[16提出不协调区间决策系统的分布约简。 计算每个对象对应的概率分布： 定义10设区间值决策系统DS=(U,CUD, e(x)=1,0,2(x2)=0,1, Vf月，A≤U,U/D={D,D2,…,Duo,则xeU对应 2(x3)={2/3,1/3,e6(x4)=(0,1, 的概率分布定义为 2(xs)=2/3,1/3},(x6)=(2/3,1/3}。 (c)=(D(D/S(x),D(D2/Sc),…, 计算分布保持约简可辨识矩阵： DD,/S(x),·,D(Du/Sc》 0 式中DD,/Sg》= DinS SM,js1U1D。 a1,a2,a3,a4 0 定义11设区间值决策系统DS=(U,CUD, DMg(6,6)= a1,a2 a3,a40 a1,a2,a3 0 as 0 Vf月，U={x,2,…,ml,则对任商≤i,j≤U: a1,a2 a3,a4 a3 0 a1,42 a3,a40 a30 0 DMp(i,j)= {alas∈CAa<a,(x)≠(x) 0,(x)=(x) 计算分布约简可辨识函数： 式中：DMi,)为基于a-相容类的分布约简可辨识 (C)(a,az,as,a)=as(az va) 矩阵DMg第i行j列的元素，DMg简称为分布可辨识 转化后的分布约简可辨识函数为 矩阵，其中i,j=1,2.…,U八，0表示空集。 h (C)(a,az,aa)=(a Aa3)v (aza3) 定义12设区间值决策系统DS=(U,CUD,Vf), 因此分布保持约简为{a1,a}和(a2,a3。 C={a1,a2,…,ag},DM%(i,)表示可辨识矩阵中第 2区间值决策系统的最大分布约简 i行j列的元素，基于α-相容类的分布可辨识函数定 义为与a1,a2,…,ag相对应的C个布尔变量a,a2,…, 本节在区间值决策系统中引入最大规则置信度 ag的布尔函数为 的概念，提出了不协调区间值决策系统的最大分布 f(C)(a,a,.,a)=A(VDMD(i,D):DMD(i,i)#O 约简算法。 此函数简称分布可辨识函数。这里的vDM位，)表 定义13设区间值决策系统DS=(U,CUD,Vf, 示满足aE DMp((,)的全体布尔变量ā的析取式。 A≤C,UID={D,D2,…,Duol,则x∈U对应的最大 利用分配率和吸收率将fg(C)转化为h(C) 概率分布定义为 (a1,a2,…,am)=(A)V…V(A0),0≤C,k=1,2,…,l,0 mA(x:)=D(Dj/S(x))=max D(Di/S(x)) 中每一个属性元素只出现一次。 定理1设区间值决策系统DS=(U,CUD,Vf, x∈U对应的最大分布为 yx)={DlD(D,/S(x)》=D(D/Sg(x)》 (C)是分布可辨识函数f(C)的形式转化，若A二C 是分布约简，当且仅当A是(C)的一个蕴含项。 若对任意的x,∈U,有y(x)=y(x),称A是 基于可辨识矩阵的分布约简算法(distribution DS中基于α-相容关系的最大分布协调集，简称最大 分布协调集。若A是最大分布协调集，且A的任意 reduction algorithm based on discernibility matrix, DRADM)描述如下。 真子集都不是最大分布协调集，那么称A是DS中 算法1 DRADM 基于α-相容关系的最大分布相对约简，简称最大分 输入区间值决策系统DS,阈值a。 布约简。 输出区间值决策系统的所有分布保持约简结果。 定义14设区间值决策系统DS=(U,CUD,V,f), I)计算区间值决策系统DS的在阈值α下的相容 ASC,x∈U,若属性子集A满足： 类集合S(U): 1)y(x）=y(x: 2)根据每个对象对应的相容类，计算每个对象 2)任意BcA,满足y(x)≠Y(x 相对于每一个决策类的概率分布(x): 那么称属性子集A为区间值决策系统基于相容关 3)根据每个对象的可信度不同构造分布约简 系的最大分布约简。DS的所有约简集合记为a- 可辨识矩阵DM: Reduct,.所有约简的交集称为DS的核，记为a-Core。 4)由可辨识矩阵DM计算分布约简可辨识函 定理2设区间值决策系统DS=(U,CUD,V,f), 数f8(C): ASC,则A是最大分布协调集当且仅当任意x,x∈U, 5)利用分配率和吸收率将(C)转化为(C), 当y(x)=yx,有S()S(x (C)中每一个蕴含项为一个分布保持的约简。 证明记J(S(x》=(S(x,S(x,)≤S(x》。 例3如表1所示的区间值决策系统，令α=0.6， “一”：设A是最大分布协调集，对任意x,x∈U
1.2 区间值决策系统的分布约简 文献[16]提出不协调区间决策系统的分布约简。 DS = (U,C ∪ D, V, f) A ⊆ U U/D = {D1,D2,··· ,D|U/D|} 定义 1 0 设区间值决策系统 ， ， ，则 xi∈U 对应 的概率分布定义为 µ α A (xi) = (D(D1/S α A (xi)),D(D2/S α A (xi)),··· , D(Dj/S α A (xi),··· ,D(D|U|/S α A (xi))) D(Dj/S α A (xi)) = |Dj ∩S α A (xi)| |S α A (xi)| 式中 ， j ⩽ |U/D|。 DS = (U,C ∪ D, V, f) U = {x1, x2,··· , x|U|} 1 ⩽ i, j ⩽ |U| 定义 1 1 设区间值决策系统 ， ，则对任意 ： DMα D (i, j) = { {ak |ak ∈ C ∧α k i j < α}, µα A (xi) , µ α A (xj) Ø, µα A (xi) = µ α A (xj) DMα D (i, j) α DMα D i j DMα D i, j = 1,2,··· ,|U| 式中： 为基于 -相容类的分布约简可辨识 矩阵 第 行 列的元素， 简称为分布可辨识 矩阵，其中 ，Ø表示空集。 DS = (U,C ∪ D,V, f) C = {a1,a2,··· ,a|C|} DMα D (i, j) α a1,a2,··· ,a|C| |C| a¯ 1,a¯ 2,··· , a¯|C| 定义 12 设区间值决策系统 ， ， 表示可辨识矩阵中第 i 行 j 列的元素，基于 -相容类的分布可辨识函数定 义为与 相对应的 个布尔变量 的布尔函数为 f α D (C)(¯a1,a¯ 2,··· ,a¯|C|) = ∧{∨DMα D (i, j) : DMα D (i, j) , Ø} ∨DMα D (i, j) a ∈ DMα D (i, j) a¯ 此函数简称分布可辨识函数。这里的 表 示满足 的全体布尔变量 的析取式。 f α D (C) h α D (C) (¯a1,a¯ 2,··· ,a¯m) = (∧θ1)∨ ··· ∨(∧θl), θk ⊆ C, k = 1,2,··· ,l θk 利用分配率和吸收率将 转化为 ， 中每一个属性元素只出现一次。 DS = (U,C ∪ D,V, f) h α D (C) f α D (C) A ⊆ C h α D (C) 定理 1 设区间值决策系统 ， 是分布可辨识函数 的形式转化，若 是分布约简，当且仅当 A 是 的一个蕴含项。 基于可辨识矩阵的分布约简算法 (distribution reduction algorithm based on discernibility matrix， DRADM) 描述如下。 算法 1 DRADM 输入 区间值决策系统 DS ，阈值 α。 输出 区间值决策系统的所有分布保持约简结果。 DS α S α C (U) 1) 计算区间值决策系统 的在阈值 下的相容 类集合 ； µ α C (xi) 2) 根据每个对象对应的相容类，计算每个对象 相对于每一个决策类的概率分布 ； DMα D 3) 根据每个对象的可信度不同构造分布约简 可辨识矩阵 ； DMα D f α D (C) 4) 由可辨识矩阵 计算分布约简可辨识函 数 ； f α D (C) h α D (C) h α D (C) 5) 利用分配率和吸收率将 转化为 ， 中每一个蕴含项为一个分布保持的约简。 例 3 如表 1 所示的区间值决策系统，令α = 0.6， 根据例 2 可知相似布尔矩阵以及相容类集合。 计算每个对象对应的概率分布： µ 0.6 C (x1) = {1,0} µ 0.6 C (x2) = {0,1} µ 0.6 C (x3) = {2/3,1/3} µ 0.6 C (x4) = {0,1} µ 0.6 C (x5) = {2/3,1/3} µ 0.6 C (x6) = {2/3,1/3} ， ， ， ， ， 。 计算分布保持约简可辨识矩阵： DM0.6 D (6,6) = Ø a1,a2,a3,a4 Ø a1 ,a2 a3 ,a4 Ø a1 ,a2 ,a3 Ø a3 Ø a1,a2 a3,a4 Ø a3 Ø a1,a2 a3,a4 Ø a3 Ø Ø 计算分布约简可辨识函数： f 0.6 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 ∧(a2 ∨a1) 转化后的分布约简可辨识函数为 h 0.6 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) 因此分布保持约简为 {a1,a3} 和 {a2,a3}。 2 区间值决策系统的最大分布约简 本节在区间值决策系统中引入最大规则置信度 的概念，提出了不协调区间值决策系统的最大分布 约简算法。 DS = (U,C ∪ D,V, f) A ⊆ C U/D = {D1,D2,··· ,D|U/D|} xi ∈ U 定义 13 设区间值决策系统 ， ， ，则 对应的最大 概率分布定义为 m α A (xi) = D(Dj0 /S α A (xi)) = max j⩽q D(Dj/S α A (xi)) xi ∈ U 对应的最大分布为 γ α A (xi) = {Dj |D(Dj/S α A (xi)) = D(Dj0 /S α A (xi)} γ α A (xi) = γ α C (xi) α α 若对任意的 x i∈U，有 ，称 A 是 DS 中基于 -相容关系的最大分布协调集，简称最大 分布协调集。若 A 是最大分布协调集，且 A 的任意 真子集都不是最大分布协调集，那么称 A 是 DS 中 基于 -相容关系的最大分布相对约简，简称最大分 布约简。 DS = (U,C ∪ D,V, f) A ⊆ C xi ∈ U 定义 14 设区间值决策系统 ， ， ，若属性子集 A 满足： γ α A (xi) = γ α C 1) (xi) ； B ⊂ A γ α B (xi) , γ α C 2) 任意 ，满足 (xi) ； α Reduct α Core 那么称属性子集 A 为区间值决策系统基于相容关 系的最大分布约简。DS 的所有约简集合记为 - ，所有约简的交集称为 DS 的核，记为 - 。 DS = (U,C ∪ D,V, f) A ⊆ C xi , xj ∈ U γ α C (xi) = γ α C (xj) S α A (xi) ,S α A (xj) 定理 2 设区间值决策系统 ， ，则 A 是最大分布协调集当且仅当任意 ， 当 ，有 。 J(S α A (xi)) = {S α C (xj)|S α C (xj) ⊆ S α A (xi)} ⇒ 证 明 记 。 “ ”：设 A 是最大分布协调集，对任意 xi，xj∈U， ·472· 智 能 系 统 学 报 第 13 卷
第3期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·473· 假设S(x=Sx),有(，x)ET,即Y(x)=Yx), AcC,则A是最大分布协调集当且仅当任意x,x∈U, 又因为yx)=y(x)和y(x)=y(x)成立，那么 当yx)≠y(c)时，有DM(i)nA≠O。 (x)=Y(x),这与y()≠y(x)矛盾，从而任意 证明“一”：设A是最大分布协调集，对于任意的 x,x∈U,当/()=y(x)时，有(x)≠S(x)。 x,x,∈U,假设存在DMOMA(i,)使DMa(，位jnA≠O, “=”:对任意，x∈U,当S(x)=S(x）,有 则存在S(x)和S(x),有y(x)≠Y(x),由定理1得 y(x)=y(x),对于任意的D∈y(,有D∈Y() S)≠S(x),从而存在ak∈A,满足a<a,因此存 由于S)=US(xS(x)eJ(S(x},于是对任意 在a4∈MPM(，低)，即DMM(,i)nA≠O。 的k≤q,有 “=”:假设存在x,x∈U,满足y(x)≠y(x,且 D(D/SA(xi))= DMa位，)nA≠O,则对任意a∈A,有DMPMa(低，j, ∑{D.nS(x:S(x)eJ((x)川 a崎>a,因此(：，x)∈T。假设x、x对应的a-相容类 IS(G川 分别为S(x)和S(x,则有S(x)=S(x)由定理 ∑D.S2 IS( Z11S(x训 IS(c川 S(x)∈J(S(x)》 1得A不是最大分布协调集。定理得证。 定义16设区间值决策系统DS=(U,CUD,V,fD, 9 IS( IS(x) S(x;)EJ(S(x)) C={a1,a2,…,aGl,DMx(位，)表示最大分布可辨识矩 DnS=DD1Sx》 阵中第行j列的元素，基于α-相容类的最大分布可 IS(x) 辨识函数为与a1,a2,…,an相对应C个布尔变量āg 故D。∈y(,从而yx)=y()o 的布尔函数：fg(C)Max(a,a2,…,ac)=A(VDMPMa(i,): 另一方面，任意的D∈yx),若D(),则 DM%ax(位，)≠O,为基于a-相容类的最大分布约简可 任意的S(x)∈JSx),由yx)=y(x）可得 辨识函数，简称最大分布可辨识函数。VDM(位，) m(x)>D(D./S(x》。取D∈y(x),则 表示满足aeDM%Max(i,)的全体布尔变量a的析取式。 DDL/S(x)》= 利用分配率和吸收率将f(C)ax转化为（ā， Σ9 1S(x川 :S(x)eJ(S(x》 a2,…,ag)=(A0)V…V(g),a≤C,k=(a1,a2,…,ag)= S() (A8)V…V(0),0≤C,k=1,2,…,l,0中每一个属性 ∑me)x S(x) SG) :S(x）∈J(S(x)> 元素只出现一次。 定理4设区间值决策系统DS=(U,CUD, ∑DD.1Sx》 S(x训 ISx) :S(x)∈J(S()》 Vf),h(C)au是可辨识函数(C)Mar的形式转化，若 IDnS(xl、IS(x训 A是最大分布约简，当且仅当A是h(C)人x的一个蕴 IS(x IS4(x) Sc(xj)EJ(S(x)) 含项。 D.nS(c训 D(Dj/S(x)) 证明“=”：假设0是h(C)ax的一个蕴含项，则 S(x訓 存在DM(位，)n0≠O,通过定理2得知0是其中一 与D。∈y(x)矛盾，因此D。∈y(x),于是有yx)S 个最大分布约简。 (x)。 “←”：根据定义16可得hg(C)Max(a1,a2,…,an)= 因此，证明了对任意x∈U,yx)=y(x),即集 (A0)V…V(0),0二C,k=1,2,…,1若在0中去掉一个元 合A是最大分布协调集。定理得证。 素形成0，则存在S(x)和S(x)满足y(x)≠y(x, 定义15设区间值决策系统DS=(U,CUD,V,f), 使得DMx(,)n0≠O,故g不是最大分布约简， U={,2,…,x山，则对任意i≥L,j≤W 从而0是其中一个最大分布约简。定理得证。 DMoMx(i,j)= {alak∈CAa崎<a以，yx)≠yx) 基于差别矩阵的分布约简算法(maximum dis- 0,y(x)=y(x) tribution reduction algorithm based on discernibility DMa(位，)为基于a-相容类的最大分布约简可 matrix,.MDRADM)描述如算法2。 辨识矩阵DMM第行j列的元素，DMa简称为最 算法2 MDRADM 大分布可辨识矩阵，其中i,j=1,2,…,U八，0表示空集。 输入区间值决策系统DS,阈值a。 基于-相容类的最大分布可辨识矩阵是一个 输出区间值决策系统的所有最大分布保持约 相对于主对角线对称的矩阵，在进行运算时只需考 简结果。 虑其上三角或下三角部分即可。 1)计算区间值决策系统DS在阈值α下的相容 定理3设区间值决策系统DS=(U,CUD,Vf), 类集合S:(U)
S α A (xi) = S α A (xj) (xi , xj) ∈ T α A γ α A (xi) = γ α A (xj) γ α A (xi) = γ α C (xi) γ α A (xj) = γ α C (xj) γ α C (xi) = γ α C (xj) γ α C (xi) , γ α C (xj) xi , xj ∈ U γ α C (xi) = γ α C (xj) S α A (xi) , S α A (xj) 假设 ，有 ，即 ， 又因为 和 成立，那么 ，这与 矛盾，从而任意 ，当 时，有 。 ⇐ xi , xj ∈ U S α A (xi) = S α A (xj) γ α C (xi) = γ α C (xj) Dj0 ∈ γ α C (xi) Dj0 ∈ γ α C (xj) S α A (xi) = ∪{S α C (xj)|S α C (xj) ∈J(S α A (xi))} k ⩽ q “ ” ：对任意 ， 当 ， 有 ，对于任意的 ，有 。 由于 ，于是对任意 的 ，有 D(Dk/S α A (xi))= ∑ {|Dk ∩S α C (xj)| : S α C (xj) ∈ J(S α A (xi))} |S α A (xi)| = ∑{ |Dk ∩S α C (xj)| |S α C (xj)| × |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} ⩽ ∑{ |Dj0 ∩S α C (xj)| |S α C (xi)| × |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} = |Dj0 ∩S α A (xi)| |S α A (xi)| =D(Dj0 /S α A (xi)) Dj0 ∈ γ α C (xi) γ α A (xi) = γ α C 故 ，从而 (xi)。 Dj0 ∈ γ α A (xi) Dj0 ,γ α C (xi) S α C (xj) ∈ J(S α A (xi)) γ α C (xi) = γ α C (xj) m α C (xj) > D(Dj0 /S α C (xj)) Dk0 ∈ γ α C (xj) 另一方面，任意的 ，若 ，则 任意的 ， 由 可 得 。取 ，则 D(Dk0 /S α A (xi))= ∑{ |Dk0 ∩S α C (xj)| |S α C (xj)| × |S α C (xj)| S α A (xi) : S α C (xj) ∈ J(S α A (xi))} = ∑{ m α C (xj)× |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} > ∑{ D(Dj0 /S α C (xj))× |S α AT(xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} = ∑{ |Dj0 ∩S α C (xj)| |S α C (xj)| × |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} = |Dj0 ∩S α A (xi)| |S α A (xi)| = D(Dj0 /S α A (xi)) Dj0 ∈ γ α A (xi) Dj0 ∈ γ α C (xi) γ α A (xi) ⊆ γ α C (xi) 与 矛盾，因此 ，于是有 。 xi ∈ U γ α A (xi) = γ α C 因此，证明了对任意 ， (xi) ，即集 合 A 是最大分布协调集。定理得证。 DS = (U,C ∪ D,V, f) U = {x1, x2,··· , x|U|} i ⩾ 1, j ⩽ |U| 定义 15 设区间值决策系统 ， ，则对任意 ： DMα DMax(i, j) = { {ak |ak ∈ C ∧α k i j < α}, γα A (xi) , γ α A (xj) Ø, γα A (xi) = γ α A (xj) DMα DMax(i, j) DMα DMax i j DMα DMax i, j = 1,2,··· ,|U| 为基于 α-相容类的最大分布约简可 辨识矩阵 第 行 列的元素， 简称为最 大分布可辨识矩阵，其中 ，Ø表示空集。 基于 α-相容类的最大分布可辨识矩阵是一个 相对于主对角线对称的矩阵，在进行运算时只需考 虑其上三角或下三角部分即可。 定理 3 设区间值决策系统 DS = (U,C ∪ D,V, f)， A ⊆ C xi , xj ∈ U γ α C (xi) , γ α C (xj) DMα DMax(i, j)∩ A , Ø ，则 A 是最大分布协调集当且仅当任意 ， 当 时，有 。 ⇒ A xi , xj ∈ DMα DMax(i, j) DMα DMax(i, j)∩A , Ø S α C (xi) S α C (xj) γ α C (xi) , γ α C (xj) S α A (xi) , S α A (xj) ak ∈ A α k i j < α ak ∈ DMα DMax(i, j) DMα DMax(i, j)∩ A , Ø 证明 “ ”：设 是最大分布协调集，对于任意的 U，假设存在 使 ， 则存在 和 ，有 ，由定理 1 得 ，从而存在 ，满足 ，因此存 在 ，即 。 ⇐ γ α C (xi) ,γ α C (xj) DMα DMax(i, j)∩ A , Ø ak <DMα DMax(i, j) α k i j > α (xi , xj) ∈ T α A xi、xj α S α A (xi) S α A (xj) S α A (xi) = S α A (xj) A “ ”：假设存在 xi，xj∈U，满足 ，且 ，则对任意ak∈A，有 ， ，因此 。假设 对应的 -相容类 分别为 和 ，则有 ，由定理 1 得 不是最大分布协调集。定理得证。 DS = (U,C ∪ D,V, f) C = { a1,a2,··· ,a|C| } DMα DMax(i, j) i j a1,a2,··· ,am |C| a¯|C| f α D (C)Max(¯a1,a¯ 2,··· ,a¯|C|) =∧{∨DMα DMax(i, j) : 定义 16 设区间值决策系统 ， ， 表示最大分布可辨识矩 阵中第 行 列的元素，基于 α-相容类的最大分布可 辨识函数为与 相对应 个布尔变量 的布尔函数： DMα DMax(i, j) , Ø} α ∨DMα DMax(i, j) a ∈ DMα DMax(i, j) a¯ ，为基于 -相容类的最大分布约简可 辨识函数，简称最大分布可辨识函数。 表示满足 的全体布尔变量 的析取式。 f α D (C)Max (¯a1, a¯ 2,··· ,a¯|C|) = (∧θ1)∨ ··· ∨(θl) θk ⊆ C, k = (¯a1,a¯ 2,··· ,a¯|C|) = (∧θ1)∨ ··· ∨(θl), θk ⊆ C, k = 1,2,··· ,l θk 利用分配率和吸收率将 转化为 ， ， 中每一个属性 元素只出现一次。 DS = (U,C ∪ D, V, f) h α D (C)Max f α D (C)Max A h α D (C)Max 定 理 4 设区间值决策系统 ， 是可辨识函数 的形式转化，若 是最大分布约简，当且仅当 A 是 的一个蕴 含项。 ⇒ θ h α D (C)Max DMα DMax(i, j)∩θ , Ø θ 证明 “ ”：假设 是 的一个蕴含项，则 存在 ，通过定理 2 得知 是其中一 个最大分布约简。 ⇐ h α D (C)Max(¯a1,a¯ 2,··· ,a¯m) = (∧θ1)∨ ··· ∨(θl), θk ⊆ C, k = 1,2,··· ,l S α C (xi) S α C (xj) γ α C (xi) , γ α C (xj) DMα DMax(i, j)∩θ ′ , Ø “ ”：根据定义 16 可得 ，若在θ中去掉一个元 素形成 θ′，则存在 和 满足 ， 使得 ，故 θ′ 不是最大分布约简， 从而 θ 是其中一个最大分布约简。定理得证。 基于差别矩阵的分布约简算法 (maximum distribution reduction algorithm based on discernibility matrix，MDRADM) 描述如算法 2。 算法 2 MDRADM 输入 区间值决策系统 DS，阈值α。 输出 区间值决策系统的所有最大分布保持约 简结果。 α S α C (U) 1) 计算区间值决策系统 DS 在阈值 下的相容 类集合 。 第 3 期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·473·