第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,满足aa,因此(：，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 α (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·
·474· 智能系统学报 第13卷 2)根据每个对象对应的相容类，计算每个对象 性质3设区间值决策系统DS=(U,CUD,V,f), 相对于每一个决策类的概率分布(x)。 H=h1Vh2V.Vhm和K=k1 VkV...Vkn分别是分布 3)根据每个对象的概率分布，计算所对应的最 约简和最大分布约简结果，则在阈值α下，对于K中 大分布y(x)。 任意一个蕴含项k,H中存在一个蕴含项h,满足 4)根据每个对象的可信度不同构造最大分布 h2kjo 约简可辨识矩阵DMax。 S)由可辨识矩阵DMa计算最大分布约简可 3实验验证与分析 辨识函数f(C)ax。 本节对提出的最大分布约简算法进行实验验 6)利用分配率和吸收率将U转化为h(C)x, 证，实验包括两部分：1)比较最大分布约简方法和 hg(C)中每一个蕴含项为一个最大分布保持的约简。 算法2是通过可辨识矩阵求得区间值决策表的 其他约简方法的约简结果，验证了性质3的正确 所有最大分布保持约简，因此算法在最坏情况下的 性：2)比较了最大分布保持、分布保持和正域保持 时间复杂度为OC),C为条件属性的个数，IU为 3种约简算法的约简效率。采用UCI标准测试集进 对象的个数。 行实验。实验环境为PC机，操作系统为Windows 例4如表1所示的区间值决策系统，令 7旗舰版64位；内存为6.0 GB DDR3,CPU为Intel α=0.6，根据例2可知相似布尔矩阵以及相容类。 i5-3470。 计算决策属性D对U划分： 实验选取8组标准UCI数据集，对缺失数据通 U/D (D1.D2)=(x1.xs,x61.(x2,xx 过将对应属性下占多数属性值进行替换，对名词性 计算每个对象对应的概率分布： 数据采用{0,1}替换，对连续型数据采用等频分割 g6(x1)={1,0,26(2)={0,1, 的方法，所有数据预处理均在WEKA3.6进行，数据 e6()={2/3,1/31,e6(x)=(0,1, 集信息如表2所示，IUI表示对象数，AT表示条件属 e(xs)={(2/3,1/3,e(x6)=2/3,1/31。 性数，D表示决策属性将对象分类个数。 计算每个对象对应的最大分布： 表2UCI数据集信息 y2(x)={Dh,Y2()={D2l, Table 2 UCI data sets information Y2(3)={D,y2(xa)=(D2l, 数据集 10 JATI D ye5(xs)=(Dil,ye(x6)=(Do 计算最大分布约简可辨识矩阵： BLOGGER 100 4 ⊙ Fertility 100 a1,a2,a3,a4 0 0 a3,a4 0 Teaching Assistant DMPM(6.6)= 151 a1,a2,a3 0 as 0 Evaluation 0 a3,a40a30 ⊙ a3,a40 00 QualitativeBankruptcy 250 计算最大分布约简可辨识函数： User Knowledge 258 f86(C)Max(a1,2,,a4)=a3 Modeling 因此，最大分布保持约简结果为{a} Liverdisorders 345 例5如表1所示的区间值决策系统，令α分别 Auto MPG 398 为0.4,0.5,0.6,0.7，则分布保持约简结果为 h9(C)(a1,a2,a3,a4)=a1Va4 Mammographic Mass 961 h9(C)(a1,a2,a3,a4)=(a1Aa3)V(a2Aa3) 由于表格有限，表3~10中数据集名称均为相 h8(C)(a1,a2,a3,a4)=(a1Aa3)V(a2Aa3) h(C)(a,az,asa)=(aAas)v(aAas) 应数据集名称的缩写。 最大分布保持约简结果为 由于采用的UCI数据集都是单值数据，因此需 hp(C)Max(an,an,a.)=ava 将单值数据转换为区间值数据，单值数据转换为区 h (C)Ma(an,a,a.)=as 间值数据的方法在文献[19]中已经描述，先将该方 h0(C)Mx(a1,a2,a3,a4)= 法改进，引进阈值入，该值可调节振幅，即区间值的 h97(C)Mx(a1,a2,a3,a4)=a3 长度
µ α C (xi) 2) 根据每个对象对应的相容类，计算每个对象 相对于每一个决策类的概率分布 。 γ α C (xi) 3) 根据每个对象的概率分布，计算所对应的最 大分布 。 DMα DMax 4) 根据每个对象的可信度不同构造最大分布 约简可辨识矩阵 。 DMα DMax f α D (C)Max 5) 由可辨识矩阵 计算最大分布约简可 辨识函数 。 U h α D (C)Max h α D (C)Max 6) 利用分配率和吸收率将 转化为 ， 中每一个蕴含项为一个最大分布保持的约简。 O(|C| |U| 2 ) |C| |U| 算法 2 是通过可辨识矩阵求得区间值决策表的 所有最大分布保持约简，因此算法在最坏情况下的 时间复杂度为 ， 为条件属性的个数， 为 对象的个数。 α = 0.6 例 4 如表 1 所示的区间值决策系统，令 ，根据例 2 可知相似布尔矩阵以及相容类。 计算决策属性 D 对 U 划分： U/D = {D1 ,D2} = { {x1 , x5 , x6},{x2 , x3 , x4} } 。 计算每个对象对应的概率分布： µ 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}。 计算每个对象对应的最大分布： γ 0.6 C (x1) = {D1} γ 0.6 C ， (x2) = {D2}， γ 0.6 C (x3) = {D1} γ 0.6 C ， (x4) = {D2}， γ 0.6 C (x5) = {D1} γ 0.6 C ， (x6) = {D1}。 计算最大分布约简可辨识矩阵： DM0.6 DMax(6,6) = Ø a1,a2,a3,a4 Ø Ø a3 ,a4 Ø a1 ,a2 ,a3 Ø a3 Ø Ø a3,a4 Ø a3 Ø Ø a3,a4 Ø a3 Ø Ø 计算最大分布约简可辨识函数： f 0.6 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 因此，最大分布保持约简结果为{a3}。 α 0.4,0.5,0.6,0.7 例 5 如表 1 所示的区间值决策系统，令 分别 为 ，则分布保持约简结果为 h 0.4 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = a1 ∨a4 h 0.5 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) h 0.6 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) h 0.7 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) 最大分布保持约简结果为 h 0.4 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a1 ∨a4 h 0.5 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 h 0.6 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 h 0.7 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 DS = (U,C ∪ D,V, f) H = h1 ∨h2 ∨ ··· ∨hm K = k1 ∨k2 ∨ ··· ∨kn α K kj H hi hi ⊇ kj 性质 3 设区间值决策系统 ， 和 分别是分布 约简和最大分布约简结果，则在阈值 下，对于 中 任意一个蕴含项 ， 中存在一个蕴含项 满足 。 3 实验验证与分析 本节对提出的最大分布约简算法进行实验验 证，实验包括两部分：1) 比较最大分布约简方法和 其他约简方法的约简结果，验证了性质 3 的正确 性；2) 比较了最大分布保持、分布保持和正域保持 3 种约简算法的约简效率。采用 UCI 标准测试集进 行实验。实验环境为 PC 机，操作系统为 Windows 7 旗舰版 64 位；内存为 6.0 GB DDR3，CPU 为 Intel i5-3470。 |U| |D| 实验选取 8 组标准 UCI 数据集，对缺失数据通 过将对应属性下占多数属性值进行替换，对名词性 数据采用{0,1}替换，对连续型数据采用等频分割[19] 的方法，所有数据预处理均在 WEKA3.6 进行，数据 集信息如表 2 所示， 表示对象数，|AT|表示条件属 性数， 表示决策属性将对象分类个数。 表 2 UCI 数据集信息 Table 2 UCI data sets information 数据集 |U| |AT| |D| BLOGGER 100 4 2 Fertility 100 9 2 Teaching Assistant Evaluation 151 4 3 QualitativeBankruptcy 250 6 2 User Knowledge Modeling 258 4 4 Liverdisorders 345 6 2 Auto MPG 398 6 3 Mammographic Mass 961 4 2 由于表格有限，表 3～10 中数据集名称均为相 应数据集名称的缩写。 λ 由于采用的 UCI 数据集都是单值数据，因此需 将单值数据转换为区间值数据，单值数据转换为区 间值数据的方法在文献[19]中已经描述，先将该方 法改进，引进阈值 ，该值可调节振幅，即区间值的 长度。 ·474· 智 能 系 统 学 报 第 13 卷
第3期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·475· 表3约简结果对比(=2.4，a=0.4) 表6约简结果对比(d=2.4,a=0.7) Table 3 Comparison of reduction results(A=2.4,q=0.4) Table 6 Comparison of reduction results (A=2.4.q=0.7) 数据集PRADM DRADM MDRADM 数据集 PRADM DRADM MDRADM BLO 1,2,4,5} {1,2,3,4,5} {1,2,3,4,5} BLO {1.2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} FER{1,3,7,8,9}{1,2,3,6,7,8,9} {1,3,7,9} FER {3} {3 {3} TAE {4,5} {1,2,3,4,5} {1,2,3,4,5} TA {1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} QB 集合1 {1,2,3,4,5,6} {1,2,6} QB 集合11 集合12 集合13 UKM 集合2 {1,2.4,5} 1,2,4,5 UKM {1.2.3.4,5} {1,23,4,5} {1,2,3,4,5} LD {5,6} {1,2,3,4,5,6} {1,2,34,5,6} LD {1,2,3,4,5,6}{1,2,3,4,5,6}{1,2,3,4,5,6} AM 集合3 {1,2,3,4,5n6,7}{1,2,3,4,5,6,7} AM{12,3,45,6,7}{1,2,3,4,5,6,7}{1,2,3,4,5,67} MM {1} {1,2,3,4,5} {1,2,3,4,5} MM {12.3.4.5} {1,2,3,4,5} {1,2,3,4,5} 表4约简结果对比(d=2.4,a=0.5) 表7约简结果对比(=3.5，a=0.4) Table 4 Comparison of reduction results(A=2.4.q=0.5) Table 7 Comparison of reduction results (A=3.5.q=0.4) 数据集 PRADM DRADM MDRADM 数据集 PRADM DRADM MDRADM BLO {1,2,4,5} {1,2,3,4.5} {1,2,34.5} BLO 集合14 {1,3,4} 4) FER 集合4 集合5 集合6 FER 集合15 {2,6,7,9} {2,6,7,9} TAE{1,2,3,45} {1,2,3,4,5} {1,2,3,4,5} TAE 集合16 {2,3,5} {2,3,5} QB 集合7 {1,2,3,4,5,6} {1,2,6} OB 集合17 {2,6} {2,6} UKM1,2,3.4.5} {1,2,3,4,5} {1,2,4,5} UKM 集合18 {5 5} LD {1,2,3,5,6}{1,2,3,4,5,6} {1,2,3,4,5,6} LD 集合19 {1,2,3,4,5,6} 6} AM {1,3,7} {1,3,4,5,6,7}{1,3,4,5,6,7} AM 集合20 {1,2,3.4,5} {1,2,3,4,5} MM {12,3.4,5} {1,2,3,4,5} {1,2,3,4,5} MM 1} {1,2,4,5} {1,2,4,5} 表5约简结果对比(=2.4，=0.6) 表8约简结果对比(d=3.5,a=0.5) Table 5 Comparison of reduction results(=2.4.q=0.6) Table 8 Comparison of reduction results (A=3.5.q=0.5) 数据集 PRADM DRADM MDRADM 数据集 PRADM DRADM MDRADM BLO {1.2.3,4.5} {12.3.4.5 {1.2.3,4,5} BLO 集合21 {1,3.4,5} {1.3.4,5} FER 集合8 集合9 集合10 FER {1,7,8,9}{1,2,3,6,7,8,9} {1,3,6,8,9} TAE {1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} TAE {4,5} {1,2,3,4,5} {1,2,34,5} QB {1,5.6 {1.2.3.4.5.6}{1.2,3.4.5,6} QB 集合22 {2,6} {2,6} UKM{1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} UKM 集合23 {2,5} {2,5} LD {1,2,3,4,5,6}{1,2,3,4,5,6}{1,2,3,4,5,6} LD {6} {1,2,3,4,5,6} {1,2,3,4,5,6} AM{1,2,3,4,5,6,7}{1,2,3,4,5,6,7}1,2,3,4,5,6,7} AM 集合24 {12,3,4,5,6.7}{1,2,3,4,5,6.7 MM {1,2,3,4,5} {1,2,3,4,5} {12,3,4,5} MM 1} {1,2,3,4,5} {1,2,3,4,5} 设区间值决策系统(U,CUD,V,fD,对任意的x∈U, 区间值的左右区间分别为 a,()为x在属性1上的取值U/D={D1,D2,…,DU, 5=a,(x)-d成 DeU/D,则单值性数据转换为区间值数据的振幅为 G=a,(x)+ 式中为调节区间值长度的值。 时Voa()- D. 3.1约简结果对比 ∑a(x) 在本节中，讨论了最大分布约简与其他约简方 式中花= 法之间的关系P四，选取正域保持约简算法(PRADM)啊 和分布保持约简算法(DRADM)。A分别取2.4和
表 3 约简结果对比 ( λ= 2.4,α= 0.4 ) Table 3 Comparison of reduction results ( λ= 2.4,α= 0.4 ) 数据集 PRADM DRADM MDRADM BLO {1, 2, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} FER {1, 3, 7, 8, 9} {1, 2, 3, 6, 7, 8, 9} {1, 3, 7, 9} TAE {4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB 集合 1 {1, 2, 3, 4, 5, 6} {1, 2, 6} UKM 集合 2 {1, 2, 4, 5} {1, 2, 4, 5} LD {5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM 集合 3 {1, 2, 3, 4, 5, 6, 7} {1, 2, 3, 4, 5, 6, 7} MM {1} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} 表 4 约简结果对比 ( λ= 2.4,α= 0.5 ) Table 4 Comparison of reduction results( λ= 2.4,α= 0.5 ) 数据集 PRADM DRADM MDRADM BLO {1, 2, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} FER 集合 4 集合 5 集合 6 TAE {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB 集合 7 {1, 2, 3, 4, 5, 6} {1, 2, 6} UKM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 4, 5} LD {1, 2, 3, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM {1, 3, 7} {1, 3, 4, 5, 6, 7} {1, 3, 4, 5, 6, 7} MM {12, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} 表 5 约简结果对比 ( λ= 2.4,α= 0.6 ) Table 5 Comparison of reduction results ( λ= 2.4,α= 0.6 ) 数据集 PRADM DRADM MDRADM BLO {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} FER 集合 8 集合 9 集合 10 TAE {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB {1, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} UKM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} LD {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM {1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7} MM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} (U,C ∪ D,V, f) xi ∈ U at(xi) xi U/D = {D1,D2,··· ,D|U/D|} Dk ∈ U/D 设区间值决策系统 ，对任意的 ， 为 在属性 t 上的取值 ， ，则单值性数据转换为区间值数据的振幅为 σ k t = √ 1 |Dk | −1 ∑ xi∈Dk (at(xj)−a¯ k t ) 2 a¯ k t = ∑ xj∈Dk at(xj) |Dk | 式中 。 表 6 约简结果对比 ( λ= 2.4,α= 0.7 ) Table 6 Comparison of reduction results ( λ= 2.4,α= 0.7 ) 数据集 PRADM DRADM MDRADM BLO {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} FER {3} {3} {3} TA {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB 集合 11 集合 12 集合 13 UKM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} LD {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM {1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7} MM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} 表 7 约简结果对比 ( λ= 3.5,α= 0.4 ) Table 7 Comparison of reduction results ( λ= 3.5,α= 0.4 ) 数据集 PRADM DRADM MDRADM BLO 集合 14 {1, 3, 4} {4} FER 集合 15 {2, 6, 7, 9} {2, 6, 7, 9} TAE 集合 16 {2, 3, 5} {2, 3, 5} QB 集合 17 {2, 6} {2, 6} UKM 集合 18 {5} {5} LD 集合 19 {1, 2, 3, 4, 5, 6} {6} AM 集合 20 {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} MM {1} {1, 2, 4, 5} {1, 2, 4, 5} 表 8 约简结果对比 ( λ= 3.5,α= 0.5 ) Table 8 Comparison of reduction results ( λ= 3.5,α= 0.5 ) 数据集 PRADM DRADM MDRADM BLO 集合 21 {1, 3, 4, 5} {1, 3, 4, 5} FER {1, 7, 8, 9} {1, 2, 3, 6, 7, 8, 9} {1, 3, 6, 8, 9} TAE {4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB 集合 22 {2, 6} {2, 6} UKM 集合 23 {2, 5} {2, 5} LD {6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM 集合 24 {1, 2, 3, 4, 5, 6, 7} {1, 2, 3, 4, 5, 6, 7} MM {1} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} 区间值的左右区间分别为 l t i = at(xi)−λa¯ k t u t i = at(xi)+λa¯ k t 式中 λ 为调节区间值长度的值。 3.1 约简结果对比 λ 2.4 在本节中，讨论了最大分布约简与其他约简方 法之间的关系[20] ，选取正域保持约简算法 (PRADM)[17] 和分布保持约简算法 (DRADM)。 分别取 和 第 3 期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·475·
·476· 智能系统学报 第13卷 3.5,a分别取0.4、0.5、0.6、0.7，共进行了8组实验， 2.4,a=0.7时最短，但Liverdisorders数据集在任何 实验结果如表3~10所示，其中：集合1=集合7=集 阈值下均没有冗余属性。 合17=集合19=集合22=集合28={1}，{2}，{3}， 3.2约简效率对比 {4},{5},{6}};集合2=集合14=集合16=集合 本节选取Mammographic Mass数据集，对比两 18=集合21=集合23={1，{2}，{3，{4)，{5}：集 个算法随对象数量的增加耗时变化情况。图1~ 合3=集合20=集合24={1}，{2，{3}，{4}，{5}，{6；， 5为入取2.4，a分别取0.4、0.5、0.6、0.7、0.8时，3个 {7};集合4=集合6={1,3,4,5,6,7,8,9}：集合 算法的时间耗费情况；横坐标表示Mammographic 5=集合8=集合9=集合10=集合26=集合27={1,2， Mass数据集的对象数量，纵坐标表示运行时间，单 3,4,5,6,7,8,9};集合11=集合12=集合13={1,3， 位为s 5},{2,3,5},{3,4,5},{1,2,3,4,6},{1,5,6},{2,5, PRADN 6),{3,5,6}{4,5,6}}:集合15={1}，{2}，{3}，{4}， 50 R (5,{6},{7,{8},{9}:集合25={1,2,3,4,5,7,8,9}。 40 表9约简结果对比(d=3.5,=0.6) 0 Table 9 Comparison of reduction results (A=3.5.q=0.6) 20 数据集 PRADM DRADM MDRADM 100200300400500600700800900 BLO {1,2,4,5} {1,2,3,4,5} {1.2,3,4,5} 对象数量 FER 集合25 集合26 集合27 图1约简效率对比(a=0.4) TA {1,2,3,4,5} {1,2,3,4,5} 1,2,3,4,5} Fig.1 Comparison of reduction efficiency (a=0.4) 80r QB 集合28 {1,2,3,4,5,6} {1,2,6} -PRADM 70-·DRADM UKM {1,2,3,4,5} {1,2,3,4,5} 60 MDRADM {1,2,3,4,5} 宣50 LD {1,2,3,5,6} {1,2,34,5,6}{1,2,3,4,5,6} 30 AM{1,2,3,4,5,6,7}{1,2,3,45,6,7}{1,2,3,4,5,6,7} 20 MM {1,2,3,5} {1,2,3,4,5} {1,2,3,4,5} 10 01 100200300400500600700800900 表10约简结果对比(=3.5，a=0.7) 对象数量 Table 10 Comparison of reduction results (3.5,q=0.7) 图2约简效率对比(a=0.5) 数据集 PRADM DRADM MDRADM Fig.2 Comparison of reduction efficiency (q=0.5) BL0{1,2,3,4,5} {1,2,3,4,5}{1,2,3,4,5} 80 PRADM FER {3; {3} 3} 70 DM 60 MDRADM TAE {1,2,3,4,5} {12.3.4.5 {1.2.3.4.5} QB {1,5,6} {1,2,3,4,5,6}{1,2,3,4,5,6} UKM{1,2,3,4,5} {1,2,3,4,5} {1,2,3,4,5} 20 LD{1,2,3,4,5,6}{1.2,3,4,5,6}{1,2.3,4,5,6 0 100200300400500600700800900 AM{1,2,3,4,5,6,7}{1.2,3,4,5,6,7}{12,3,4,5,6,7} 对象数量 MM{1,2,3,4,5} {1,2,3,4,5}{1,2,3,4,5} 图3约简效率对比(a=0.6) 表3~6为取2.4，a分别取0.4、0.5、0.6、 Fig.3 Comparison of reduction efficiency (q=0.6) 0.7时，正域保持、分布保持和最大分布保持约简算 80 70 PRADM DRADM 法的约简结果。实验结果表明，MDRADM约简结 60 MDRADM 果为DRADM约简结果的子集，即验证了性质3的 50 正确性，而PRADM约简结果和MDRADM约简结 果没有明显关系。这是因为，当正域为空时，正域 0 约简结果为条件属性中任意一个属性，故PRA 0 100200300400500600700800900 DM的约简结果和MDRADM的约简结果不存在包 对象数量 含关系。当=3.5，=0.4时，对于大部分数据集， 图4约简效率对比(a=0.7) DRADM的约简结果最短，Fertility数据集则在d= Fig.4 Comparison of reduction efficiency (a=0.7)
3.5，α分别取 0.4、0.5、0.6、0.7 ，共进行了 8 组实验， 实验结果如表 3~10 所示，其中：集合 1=集合 7=集 合 17=集合 19=集合 22=集合 28={{1}, {2}, {3}, {4}, {5}, {6}}；集合 2=集合 14=集合 16=集合 18=集合 21=集合 23={{1}, {2}, {3}, {4}, {5}}；集 合 3=集合 20=集合 24={{1}, {2}, {3}, {4}, {5}, {6}, {7}}；集合 4=集合 6={1, 3, 4, 5, 6, 7, 8, 9}；集合 5=集合 8=集合 9=集合 10=集合 26=集合 27={1, 2, 3, 4, 5, 6, 7, 8, 9}；集合 11=集合 12=集合 13={{1, 3, 5},{2, 3, 5},{3, 4, 5},{1, 2, 3, 4, 6},{1, 5, 6},{2, 5, 6},{3, 5, 6}{4, 5, 6}}；集合 15={{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}；集合 25={1, 2, 3, 4, 5, 7, 8, 9}。 表 9 约简结果对比 ( λ= 3.5,α= 0.6 ) Table 9 Comparison of reduction results ( λ= 3.5,α= 0.6 ) 数据集 PRADM DRADM MDRADM BLO {1, 2, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} FER 集合 25 集合 26 集合 27 TA {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB 集合 28 {1, 2, 3, 4, 5, 6} {1, 2, 6} UKM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} LD {1, 2, 3, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM {1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7} MM {1, 2, 3, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} 表 10 约简结果对比 ( λ= 3.5,α= 0.7 ) Table 10 Comparison of reduction results ( λ= 3.5,α= 0.7 ) 数据集 PRADM DRADM MDRADM BLO {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} FER {3} {3} {3} TAE {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} QB {1, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} UKM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} LD {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6} AM {1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7}{1, 2, 3, 4, 5, 6, 7} MM {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} λ 2.4 α λ= 3.5,α= 0.4 λ= 表 3～6 为 取 ， 分别取 0.4、0.5、0.6、 0.7 时，正域保持、分布保持和最大分布保持约简算 法的约简结果。实验结果表明，MDRADM 约简结 果为 DRADM 约简结果的子集，即验证了性质 3 的 正确性，而 PRADM 约简结果和 MDRADM 约简结 果没有明显关系。这是因为，当正域为空时，正域 约简结果为条件属性中任意一个属性，故 PRADM 的约简结果和 MDRADM 的约简结果不存在包 含关系。当 时，对于大部分数据集， DRADM 的约简结果最短，Fertility 数据集则在 2.4，α= 0.7 时最短，但 Liverdisorders 数据集在任何 阈值下均没有冗余属性。 3.2 约简效率对比 λ 2.4 α 本节选取 Mammographic Mass 数据集，对比两 个算法随对象数量的增加耗时变化情况。图 1～ 5 为 取 ， 分别取 0.4、0.5、0.6、0.7、0.8 时，3 个 算法的时间耗费情况；横坐标表示 Mammographic Mass 数据集的对象数量，纵坐标表示运行时间，单 位为 s。 60 50 40 30 20 10 0 䓼㵸ᬢ䬠/s 100 200 300 400 500 600 700 800 900 ᄥ䆍䛻 PRADM DRADM MDRADM 图 1 约简效率对比 (α= 0.4 ) Fig. 1 Comparison of reduction efficiency (α= 0.4 ) 60 70 80 50 40 30 20 10 0 运行时间/s 100 200 300 400 500 600 700 800 900 对象数量 PRADM DRADM MDRADM 图 2 约简效率对比 (α= 0.5 ) Fig. 2 Comparison of reduction efficiency (α= 0.5 ) 60 70 80 50 40 30 20 10 0 运行时间/s 100 200 300 400 500 600 700 800 900 对象数量 PRADM DRADM MDRADM 图 3 约简效率对比 (α= 0.6 ) Fig. 3 Comparison of reduction efficiency (α= 0.6 ) 60 70 80 50 40 30 20 10 0 运行时间/s 100 200 300 400 500 600 700 800 900 对象数量 PRADM DRADM MDRADM 图 4 约简效率对比 (α= 0.7 ) Fig. 4 Comparison of reduction efficiency (α= 0.7 ) ·476· 智 能 系 统 学 报 第 13 卷
第3期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·477· % PRADM 提出的算法是在可辨识矩阵基础上的，其时间和空 80 70 -MDRADM 间复杂度较高，不利于在实际应用中推广，故提出 高效率的约简算法是未来研究方向之一。 0 酒3 参考文献： 0 10 [1]PAWLAK Z.Rough sets[J].International journal of com- 100200300400500600700800900 对象数量 puter information sciences,1982,11(5):341-356. [2]PAWLAK Z.Rough sets:theoretical aspects of reasoning 图5约简效率对比(a=0.8) about data[M].Boston:Kluwer Academic Publishers,1992 Fig.5 Comparison of reduction efficiency(a=0.8) [3)]王国胤，姚一豫，于洪.粗糙集理论与应用研究综述).计 图1~5中虚线表示PRADM随着对象数量增 算机学报，2009,32(7八：1229-1246. 加运行时间变化曲线，空心圆点实线表示MDRADM WANG Guoyin.YAO Yiyu,YU Hong.A survey on rough 随着对象数量增加运行时间变化曲线，交叉点实线 set theory and applications[J].Chinese journal of computers, 表示DRADM随着对象数量增加运行时间变化曲 2009.32(7):1229-1246 线。实验结果表明，在对象数较少情况下，由于差 [4]QIAN Yuhua,LIANG Jiye,PEDRYCZ W,et al.Positive 别矩阵较简单，PRADM、DRADM和MDRADM运 approximation:an accelerator for attribute reduction in 行时间几乎没有差别，但随着对象数量的增加，3种 rough set theory[J].Artificial intelligence,2010,174(9/10): 算法的运行时间差异越来越明显：由于MDRADM 597-618. 差别元素是DRADM差别元素的一个子集，PRA- [5]WANG Feng,LIANG Jiye,QIAN Yuhua.Attribute reduc- DM的差别矩阵为非对称矩阵，故MDRADM的运 tion:A dimension incremental strategy[J].Knowledge- based systems,2013,39:95-108. 行时间小于PRADM和DRADM运行时间。当a分 [6]CHEN Hongmei,LI Tianrui,RUAN Da,et al.A rough-set 别取0.5、0.6、0.7、0.8时，Mammographic Mass数据 based incremental approach for updating approximations 集随着对象的增加，3个算法的耗时差距增大，这是 under dynamic maintenance environments[J].IEEE transac- 由于随着对象的增加差别矩阵愈加复杂，计算量越 tions on knowledge and data engineering,2013,25(2): 大造成的；当α=0.4时，也呈现这样的趋势，但当对 274-284. 象数达到900时，利用吸收率和结合律运算的差别 [7]HU Qinghua,YU Daren,XIE Zongxia.Information-pre- 矩阵较简单，造成时间增长率减小。当取3.5，α分 serving hybrid data reduction based on fuzzy-rough tech- 别取0.4、0.5、0.6、0.7、0.8时，3个算法的时间耗费 niques[J].Pattern recognition letters,2006,27(5):414-423 情况跟λ取2.4时的折线图大致相同，所以本文不作 [8]SKOWRON A,RAUSZER C.The discernibility matrices 详细描述。 and functions in information systems[M]//SLOWINSKI R Intelligent Decision Support.Dordrecht:Springer,1992,11: 4结束语 331-362 [9]KRYSZKIEWICZ M.Rough set approach to incomplete in- 属性约简是粗糙集理论研究的热点问题之一， formation systems[J].Information sciences,1998,112(1/2/3/4): 在实际应用中具有重要意义，主要作用有：1)提取 39-49 更加泛化的规则；2)针对应用中的海量数据，能够 [10]邓大勇，黄厚宽，李向军.不一致决策系统中约简之间的 压缩数据集规模。分布保持约简能够保持信息系统 比较U.电子学报，2007,35(2)：252-255. 在约简前后置信度不变，而人们往往只关注置信度 DENG Dayong,HUANG Houkuan,LI Xiangjun.Compar- 最大的规则，具有广泛的应用价值。 ison of various types of reductions in inconsistent 本文在相关研究成果的基础上，在不协调区间 systems[J].Acta electronica sinica,2007,35(2):252-255. 值决策系统中提出最大分布约简的概念，构造了基 [11]MIAO Duoqian,ZHAO Yan,YAO Yiyu,et al.Relative re- ducts in consistent and inconsistent decision tables of the 于可辨识矩阵的最大分布约简算法，该算法保持了 Pawlak rough set model[J].Information sciences,2009, 在知识约简前后各个规则的最大置信度不变。实验 17924):4140-4150. 选取8组UCI数据集将本文算法与已有的两种约 [12]ZHOU Jie,MIAO Duogian,PEDRYCZ W,et al.Analysis 简算法的约简结果和效率进行对比。实验结果表 of alternative objective functions for attribute reduction in 明，分布约简包含最大分布约简，并且最大分布约 complete decision tables[J].Soft computing,2011,15(8): 简算法比其他两种算法具有更高的效率。由于本文 1601-1616
60 70 90 80 50 40 30 20 10 0 运行时间/s 100 200 300 400 500 600 700 800 900 对象数量 PRADM DRADM MDRADM 图 5 约简效率对比 (α= 0.8 ) Fig. 5 Comparison of reduction efficiency (α= 0.8 ) α α = 0.4 λ 3.5 α λ 2.4 图 1～5 中虚线表示 PRADM 随着对象数量增 加运行时间变化曲线，空心圆点实线表示 MDRADM 随着对象数量增加运行时间变化曲线，交叉点实线 表示 DRADM 随着对象数量增加运行时间变化曲 线。实验结果表明，在对象数较少情况下，由于差 别矩阵较简单，PRADM、DRADM 和 MDRADM 运 行时间几乎没有差别，但随着对象数量的增加，3 种 算法的运行时间差异越来越明显；由于 MDRADM 差别元素是 DRADM 差别元素的一个子集，PRADM 的差别矩阵为非对称矩阵，故 MDRADM 的运 行时间小于 PRADM 和 DRADM 运行时间。当 分 别取 0.5、0.6、0.7、0.8 时，Mammographic Mass 数据 集随着对象的增加，3 个算法的耗时差距增大，这是 由于随着对象的增加差别矩阵愈加复杂，计算量越 大造成的；当 时，也呈现这样的趋势，但当对 象数达到 900 时，利用吸收率和结合律运算的差别 矩阵较简单，造成时间增长率减小。当 取 ， 分 别取 0.4、0.5、0.6、0.7、0.8 时，3 个算法的时间耗费 情况跟 取 时的折线图大致相同，所以本文不作 详细描述。 4 结束语 属性约简是粗糙集理论研究的热点问题之一， 在实际应用中具有重要意义，主要作用有：1) 提取 更加泛化的规则；2) 针对应用中的海量数据，能够 压缩数据集规模。分布保持约简能够保持信息系统 在约简前后置信度不变，而人们往往只关注置信度 最大的规则，具有广泛的应用价值。 本文在相关研究成果的基础上，在不协调区间 值决策系统中提出最大分布约简的概念，构造了基 于可辨识矩阵的最大分布约简算法，该算法保持了 在知识约简前后各个规则的最大置信度不变。实验 选取 8 组 UCI 数据集将本文算法与已有的两种约 简算法的约简结果和效率进行对比。实验结果表 明，分布约简包含最大分布约简，并且最大分布约 简算法比其他两种算法具有更高的效率。由于本文 提出的算法是在可辨识矩阵基础上的，其时间和空 间复杂度较高，不利于在实际应用中推广，故提出 高效率的约简算法是未来研究方向之一。 参考文献： PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341–356. [1] PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Boston: Kluwer Academic Publishers, 1992. [2] 王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[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. [3] 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. [4] WANG Feng, LIANG Jiye, QIAN Yuhua. Attribute reduction: A dimension incremental strategy[J]. Knowledgebased systems, 2013, 39: 95–108. [5] CHEN Hongmei, LI Tianrui, RUAN Da, et al. A rough-set based incremental approach for updating approximations under dynamic maintenance environments[J]. IEEE transactions on knowledge and data engineering, 2013, 25(2): 274–284. [6] HU Qinghua, YU Daren, XIE Zongxia. Information-preserving hybrid data reduction based on fuzzy-rough techniques[J]. Pattern recognition letters, 2006, 27(5): 414–423. [7] SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[M]//SŁOWIŃSKI R. Intelligent Decision Support. Dordrecht: Springer, 1992, 11: 331–362. [8] KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1/2/3/4): 39–49. [9] 邓大勇, 黄厚宽, 李向军. 不一致决策系统中约简之间的 比较[J]. 电子学报, 2007, 35(2): 252–255. DENG Dayong, HUANG Houkuan, LI Xiangjun. Comparison of various types of reductions in inconsistent systems[J]. Acta electronica sinica, 2007, 35(2): 252–255. [10] MIAO Duoqian, ZHAO Yan, YAO Yiyu, et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model[J]. Information sciences, 2009, 179(24): 4140–4150. [11] ZHOU Jie, MIAO Duoqian, PEDRYCZ W, et al. Analysis of alternative objective functions for attribute reduction in complete decision tables[J]. Soft computing, 2011, 15(8): 1601–1616. [12] 第 3 期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·477·
·478· 智能系统学报 第13卷 [13]张文修，米据生，吴伟志.不协调目标信息系统的知识约 148-150.229 简仞.计算机学报，2003,26(1)少：12-18. [19]ZHANG Xiao,MEI Changlin,CHEN Degang,et al.Multi- ZHANG Wenxiu,MI Jusheng,WU Weizhi.Knowledge re- confidence rule acquisition and confidence-preserved at- ductions in inconsistent information systems[J].Chinese tribute reduction in interval-valued decision systems[].In- journal of computers,2003,26(1):12-18. ternational journal of approximate reasoning,2014,55(8): [14纠徐伟华，张文修.基于优势关系下不协调目标信息系统 1787-1804. 的分布约简J.模糊系统与数学，2007,21(4)：124131. [20]史德容，徐伟华.区间值模糊决策序信息系统的分布约 XU Weihua,ZHANG Wenxiu.Distribution reduction in 简0.计算机科学与探索，2017,11(4)652-658. inconsistent information systems based on dominance rela- SHI Derong,XU Weihua.Distribution reduction in inter- tions[J].Fuzzy systems and mathematics,2007,21(4): val-valued fuzzy decision ordered information systems[J]. 124131 Journal of frontiers of computer science and technology, [15)]张楠，苗夺谦，岳晓冬.区间值信息系统的知识约简) 2017,11(4):652-658. 计算机研究与发展，2010.47(8)：1362-1371 作者简介： ZHANG Nan,MIAO Duoqian,YUE Xiaodong.Ap- 尹继亮，男，1994年生，硕士研究 proaches to knowledge reduction in interval-valued inform- 生，主要研究方向为粗糙集、数据挖掘 ation systems[J].Journal of computer research and devel- 与机器学习。 opment,,2010,47(8):1362-1371. [16张楠，许鑫，童向荣，等.不协调区间值决策系统的知识 约简.小型微型计算机系统，2017,38(7)：1585-1589， ZHANG Nan,XU Xin,TONG Xiangrong,et al.Know- ledge reduction in inconsistent interval-valued decision 张楠，男，1979年生，讲师，主要 systems[J].Journal of Chinese computer systems,2017, 研究方向为粗糙集、认知信息学与人 38(7):1585-1589. 工智能。 [1刀张楠，许鑫，童向荣，等.不协调区间值决策系统的分布 约简).计算机科学，2017,449八：78-82,104 ZHANG Nan,XU Xin,TONG Xiangrong,et al.Distribu- tion reduction in inconsistent interval-valued decision sys- tems[J].Computer science,2017,44(9):78-82,104. 童向荣，男，1975年生，教授，主 [18]刘鹏惠，陈子春，秦克云.区间值信息系统的决策属性约 要研究方向为多Agent系统、分布式 人工智能与数据挖掘。 简[J.计算机工程与应用，2009,45(28)：148-150,229 LIU Penghui,CHEN Zichun,QIN Keyun.Decision attrib- ute reduction of interval-valued information system [J].Computer engineering and applications,2009,45(28):
张文修, 米据生, 吴伟志. 不协调目标信息系统的知识约 简[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. [13] 徐伟华, 张文修. 基于优势关系下不协调目标信息系统 的分布约简[J]. 模糊系统与数学, 2007, 21(4): 124–131. XU Weihua, ZHANG Wenxiu. Distribution reduction in inconsistent information systems based on dominance relations[J]. Fuzzy systems and mathematics, 2007, 21(4): 124–131. [14] 张楠, 苗夺谦, 岳晓冬. 区间值信息系统的知识约简[J]. 计算机研究与发展, 2010, 47(8): 1362–1371. ZHANG Nan, MIAO Duoqian, YUE Xiaodong. Approaches to knowledge reduction in interval-valued information systems[J]. Journal of computer research and development, 2010, 47(8): 1362–1371. [15] 张楠, 许鑫, 童向荣, 等. 不协调区间值决策系统的知识 约简[J]. 小型微型计算机系统, 2017, 38(7): 1585–1589. ZHANG Nan, XU Xin, TONG Xiangrong, et al. Knowledge reduction in inconsistent interval-valued decision systems[J]. Journal of Chinese computer systems, 2017, 38(7): 1585–1589. [16] 张楠, 许鑫, 童向荣, 等. 不协调区间值决策系统的分布 约简[J]. 计算机科学, 2017, 44(9): 78–82, 104. ZHANG Nan, XU Xin, TONG Xiangrong, et al. Distribution reduction in inconsistent interval-valued decision systems[J]. Computer science, 2017, 44(9): 78–82, 104. [17] 刘鹏惠, 陈子春, 秦克云. 区间值信息系统的决策属性约 简[J]. 计算机工程与应用, 2009, 45(28): 148–150, 229. LIU Penghui, CHEN Zichun, QIN Keyun. Decision attribute reduction of interval-valued information system [J]. Computer engineering and applications, 2009, 45(28): [18] 148–150, 229. ZHANG Xiao, MEI Changlin, CHEN Degang, et al. Multiconfidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems[J]. International journal of approximate reasoning, 2014, 55(8): 1787–1804. [19] 史德容, 徐伟华. 区间值模糊决策序信息系统的分布约 简[J]. 计算机科学与探索, 2017, 11(4): 652–658. SHI Derong, XU Weihua. Distribution reduction in interval-valued fuzzy decision ordered information systems[J]. Journal of frontiers of computer science and technology, 2017, 11(4): 652–658. [20] 作者简介： 尹继亮，男，1994 年生，硕士研究 生，主要研究方向为粗糙集、数据挖掘 与机器学习。 张楠，男，1979 年生，讲师，主要 研究方向为粗糙集、认知信息学与人 工智能。 童向荣，男，1975 年生，教授，主 要研究方向为多 Agent 系统、分布式 人工智能与数据挖掘。 ·478· 智 能 系 统 学 报 第 13 卷