第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.201705027 网络出版地址：htp:/kns.cmki.net/kcms/detail/23.1538.TP.20170705.1654.004.html 变精度下不完备邻域决策系统的属性约简算法 王映龙，曾淇'，钱文彬，杨珺2 (1.江西农业大学计算机与信息工程学院，江西南昌330045：2.江西农业大学软件学院，江西南昌330045) 摘要：邻域粗糙集模型在处理完备的数值型数据中得到广泛应用，但针对不完备的数值型和符号型混合数据进行 属性约简的讨论相对较少。为此，首先结合邻域粗糙集给出了可变精度模型下不完备邻域决策系统的上、下近似算 子及属性约简：然后通过邻域粒化的方法构建了广义邻域下可变精度的粗糙集模型，并提出了一种属性重要度的评 价方法：在此基础上，设计出了面向不完备邻域决策系统的属性约简算法，该算法可直接处理不完备的数值型和符 号型混合数据：最后，通过实例分析验证了本文提出的算法能够求解出变精度下不完备邻域决策系统的属性约简 结果。 关键词：粗糙集理论；邻域关系；不完备信息系统：变精度分类粗糙集；粒计算；多粒度：约简；决策粗糙集 中图分类号：TP311文献标志码：A文章编号：1673-4785(2017)03-0386-06 中文引用格式：王映龙，曾淇，钱文彬，等.变精度下不完备邻域决策系统的属性约简算法[J].智能系统学报，2017,12 (3):386-391. 英文引用格式：WANG Yinglong,ZENG Qi,QIAN Wenbin,etal.Attribute reduction algorithm of the incomplete neighborhood decision system with variable precision[].CAAI transactions on intelligent systems,2017,12(3):386-391. Attribute reduction algorithm of the incomplete neighborhood decision system with variable precision WANG Yinglong',ZENG Qi',QIAN Wenbin2,YANG Jun? (1.School of Computer and Information Engineering,Jiangxi Agricultural University,Nanchang 330045,China;2.School of Software,Jiangxi Agricultural University,Nanchang 330045,China) Abstract:Neighborhood rough set model has been widely used in numerical data processing complete,but the discussion of attribute reduction for numeric and symbolic mixed incomplete data is relatively small.Therefore,to resolve this problem,by combining the neighborhood rough set,first,the upper and lower approximation operators and the attribute reduction of the incomplete neighborhood decision system were analyzed based on the variable precision model.Subsequently,based on the generalized neighborhood relation,a rough set model was constructed using the neighborhood granulation method.Furthermore,a method evaluating the attribute significance degree was proposed.Based on this method,an attribute reduction algorithm for the incomplete neighborhood decision system was designed,which can deal with incomplete values directly type and symbolic mixed data.Finally,through the example analysis,the algorithm can solve the attribute reduction result of incomplete neighborhood decision system with variable precision. Keywords:rough set theory;neighborhood relation;incomplete information system;variable precision classification; granular computing;multi-granulation;reducation;decision-theoretic rough sets 波兰数学家Pawlak提出的粗糙集理论能有效处理信息系统中不精确、不确定信息[)，其在模式 识别、市场决策、医疗诊断等领域广泛应用2】。经 收稿日期：2017-05-19.网络出版日期：2017-07-05. 基金项目：国家自然科学基金项目(61502213,71461013,61462038)：江西省自 典Pawlak粗糙集理论的研究对象是完备的信息决 然科学基金项目(20151BAB217009,20132BAB201045):江西省教 策表。然而在现实生活中，往往很多决策系统存在 育厅科学技术项目(GJ150399,GJ150505). 通信作者：钱文彬.E-mail:qianwenbinl027@126.com 多种数据类型，如连续型数据、不完备型数据和集
第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０５０２７ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０７０５．１６５４．００４．ｈｔｍｌ 变精度下不完备邻域决策系统的属性约简算法 王映龙１ ，曾淇１ ，钱文彬２ ，杨珺２ （１．江西农业大学 计算机与信息工程学院，江西 南昌 ３３００４５； ２．江西农业大学 软件学院，江西 南昌 ３３００４５） 摘 要：邻域粗糙集模型在处理完备的数值型数据中得到广泛应用，但针对不完备的数值型和符号型混合数据进行 属性约简的讨论相对较少。 为此，首先结合邻域粗糙集给出了可变精度模型下不完备邻域决策系统的上、下近似算 子及属性约简；然后通过邻域粒化的方法构建了广义邻域下可变精度的粗糙集模型，并提出了一种属性重要度的评 价方法；在此基础上，设计出了面向不完备邻域决策系统的属性约简算法，该算法可直接处理不完备的数值型和符 号型混合数据；最后，通过实例分析验证了本文提出的算法能够求解出变精度下不完备邻域决策系统的属性约简 结果。 关键词：粗糙集理论；邻域关系；不完备信息系统；变精度分类粗糙集；粒计算；多粒度；约简；决策粗糙集 中图分类号：ＴＰ３１１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３８６－０６ 中文引用格式：王映龙， 曾淇， 钱文彬， 等． 变精度下不完备邻域决策系统的属性约简算法 ［ Ｊ ］． 智能系统学报， ２０１７， １２ （３）： ３８６－３９１． 英文引用格式：ＷＡＮＧ Ｙｉｎｇｌｏｎｇ， ＺＥＮＧ Ｑｉ， ＱＩＡＮ Ｗｅｎｂｉｎ， ｅｔ ａｌ． Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ ｗｉｔｈ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３８６－３９１． Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ ｗｉｔｈ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ＷＡＮＧ Ｙｉｎｇｌｏｎｇ １ ， ＺＥＮＧ Ｑｉ １ ， ＱＩＡＮ Ｗｅｎｂｉｎ ２ ， ＹＡＮＧ Ｊｕｎ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｘｉ Ａｇｒｉｃｕｌｔｕｒａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｎａｎｃｈａｎｇ ３３００４５， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｓｏｆｔｗａｒｅ， Ｊｉａｎｇｘｉ Ａｇｒｉｃｕｌｔｕｒａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｎａｎｃｈａｎｇ ３３００４５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｎｅｉｇｈｂｏｒｈｏｏｄ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ｈａｓ ｂｅｅｎ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｎｕｍｅｒｉｃａｌ ｄａｔａ ｐｒｏｃｅｓｓｉｎｇ ｃｏｍｐｌｅｔｅ， ｂｕｔ ｔｈｅ ｄｉｓｃｕｓｓｉｏｎ ｏｆ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｆｏｒ ｎｕｍｅｒｉｃ ａｎｄ ｓｙｍｂｏｌｉｃ ｍｉｘｅｄ ｉｎｃｏｍｐｌｅｔｅ ｄａｔａ ｉｓ ｒｅｌａｔｉｖｅｌｙ ｓｍａｌｌ． Ｔｈｅｒｅｆｏｒｅ， ｔｏ ｒｅｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ， ｂｙ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｒｏｕｇｈ ｓｅｔ， ｆｉｒｓｔ， ｔｈｅ ｕｐｐｅｒ ａｎｄ ｌｏｗｅｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｐｅｒａｔｏｒｓ ａｎｄ ｔｈｅ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｏｆ ｔｈｅ ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ ｗｅｒｅ ａｎａｌｙｚｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｍｏｄｅｌ． Ｓｕｂｓｅｑｕｅｎｔｌｙ， ｂａｓｅｄ ｏｎ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ｎｅｉｇｈｂｏｒｈｏｏｄ ｒｅｌａｔｉｏｎ， ａ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ｗａｓ ｃｏｎｓｔｒｕｃｔｅｄ ｕｓｉｎｇ ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｎｕｌａｔｉｏｎ ｍｅｔｈｏｄ． Ｆｕｒｔｈｅｒｍｏｒｅ， ａ ｍｅｔｈｏｄ ｅｖａｌｕａｔｉｎｇ ｔｈｅ ａｔｔｒｉｂｕｔｅ ｓｉｇｎｉｆｉｃａｎｃｅ ｄｅｇｒｅｅ ｗａｓ ｐｒｏｐｏｓｅｄ． Ｂａｓｅｄ ｏｎ ｔｈｉｓ ｍｅｔｈｏｄ， ａｎ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ ｗａｓ ｄｅｓｉｇｎｅｄ， ｗｈｉｃｈ ｃａｎ ｄｅａｌ ｗｉｔｈ ｉｎｃｏｍｐｌｅｔｅ ｖａｌｕｅｓ ｄｉｒｅｃｔｌｙ ｔｙｐｅ ａｎｄ ｓｙｍｂｏｌｉｃ ｍｉｘｅｄ ｄａｔａ． Ｆｉｎａｌｌｙ， ｔｈｒｏｕｇｈ ｔｈｅ ｅｘａｍｐｌｅ ａｎａｌｙｓｉｓ， ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｓｏｌｖｅ ｔｈｅ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｒｅｓｕｌｔ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ ｗｉｔｈ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ． Ｋｅｙｗｏｒｄｓ： ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｒｅｌａｔｉｏｎ； ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ； ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ； ｇｒａｎｕｌａｒ ｃｏｍｐｕｔｉｎｇ； ｍｕｌｔｉ⁃ｇｒａｎｕｌａｔｉｏｎ； ｒｅｄｕｃａｔｉｏｎ； ｄｅｃｉｓｉｏｎ⁃ｔｈｅｏｒｅｔｉｃ ｒｏｕｇｈ ｓｅｔｓ 收稿日期：２０１７－０５－１９． 网络出版日期：２０１７－０７－０５． 基金项目：国家自然科学基金项目（６１５０２２１３，７１４６１０１３，６１４６２０３８）；江西省自 然科学基金项目（２０１５１ＢＡＢ２１７００９，２０１３２ＢＡＢ２０１０４５）；江西省教 育厅科学技术项目（ＧＪＪ１５０３９９，ＧＪＪ１５０５０５）． 通信作者：钱文彬． Ｅ⁃ｍａｉｌ：ｑｉａｎｗｅｎｂｉｎ１０２７＠ １２６．ｃｏｍ． 波兰数学家 Ｐａｗｌａｋ 提出的粗糙集理论能有效 处理信息系统中不精确、不确定信息［１］ ，其在模式 识别、市场决策、医疗诊断等领域广泛应用［２－３］ 。 经 典 Ｐａｗｌａｋ 粗糙集理论的研究对象是完备的信息决 策表。 然而在现实生活中，往往很多决策系统存在 多种数据类型，如连续型数据、不完备型数据和集
第3期 王映龙，等：变精度下不完备邻域决策系统的属性约简算法 ·387· 值型数据等4)。由于经典粗糙集在处理连续型数 决策系统，对于Hx∈U,定义x在CUD上的邻域信 据时需进行离散化预处理，将不可避免地造成信息 息粒子为N(x)={yly∈U,AM(x,y)≤8,8≥0}，其 的丢失，且对于含有不完备型数据的决策系统，传 中6表示邻域半径，△M:U×U→R为U上的一定度 统的粗糙集模型较难直接处理。近年来，针对混 量，满足以下性质： 合、模糊、不完备的粗糙集模型扩展及应用成为粒 1)Hx,y∈U,△M(x,y)≥0，当△M(x,y)=0 度计算研究的热点问题-)。 时，Va:∈A,a,(x)=a(y): 基于粒计算的属性约简研究已取得许多有意 2)Vx,y∈U,△4(x,y)=△M(y,x): 义的成果[4-18)：文献[14]研究了混合数据下的知识 3)Hx,y,z∈U,△M(x,z)≤AA(x,y)+△M(y,z)。 发现及邻域粒化问题：文献[15]提出了悲观多粒度 对于连续型的数据，采用欧式距离度量： 粗糙集的概念，解决了利用“求同消异”的决策策略 处理多个不可分辨关系之间存在相互独立的情况： △A(x,y）= ∑la,(x)-a,(y) dj 文献[16]将多粒度粗糙集扩展到邻域多粒度粗糙 对于符号型的数据，可定义： 集；为提高分类的效果，文献[17]在多粒度粗糙集 0, a,(x)=a(y) 的基础上引入了错误分类率的概念，即在允许一定 △A(x,y）= 0,a:（x)≠a:(y) 程度分类率的前提下，寻找数据之间的相关性，以 当6=0时，变为经典粗糙集模型。 解决属性间不确定关系的数据分类问题：对于不完 定义2)将邻域等价关系扩展到符号型、连 备信息系统，文献[18]提出了一种基于容差关系的 续型和缺失型等未知属性共存下的不完备模糊系 不完备可变精度多粒度粗糙集模型。 统，可得到以下广义邻域关系： 上述研究分别针对不完备粗糙集、变精度粗糙 R(x)={(x,y）∈U2:Ha∈xnf(x)= 集进行研究。由于现实生活中同时存在大量的不 fi(y),a(x)∈δ(y,a)Ua(y)∈ 完备、连续数值型、符号型属性数据的情况，现有的 8(x,a)Ua(x)=*Ua(y)=*} 邻域粗糙集计算方法对上述情况和数据集的可控 广义邻域关系满足自反性，但不一定满足对称 性调节划分的讨论相对较少。为此，本文结合多粒 性和传递性，因为任意样本与其自身是不可分辨 度粗糙集，分析了可变精度模型下不完备邻域决策 的，所以任何等价关系均满足自反性。在这里放宽 系统的上、下近似算子及属性约简，并通过邻域粒 了对称性和传递性的限制，扩展了应用范围。 化方法构建了广义邻域下可变精度的粗糙集模型： 在此基础上，构造了一种衡量属性重要度的方法， 定义31)给定DS=(U,C,D,V)是不完备邻 并设计了不完备邻域系统的属性约简算法：最后， 域决策系统，BCC,N(B)是DS上关于B的邻域关 通过实例分析验证了算法的有效性。 系所构成的邻域粒子族，对于Hx二U在B上的邻域， 记为N(x),则x在DS上的下近似和上近似分别为 1 基本知识 PB(x)={x∈U|Ng(x)Cx,PB(x)={x∈UNs(x)n 给定一个决策系统DS=(U,C,D,),其中：U= x≠中}，x的邻域近似边界为bnrs(x)=PB(x)-Pa(x)。 {x1,x2,…,x}表示非空有限样本集合，称为论域：C 是条件属性集合；D是决策属性，C∩D=中，若D=中， P(x)是可能包含x的邻域信息粒子组合的集 则决策系统转换为信息系统。V为属性值域，对于 合，P(x)是包含x的邻域信息粒子组合的集合，与 HaeC,V。为属性a的值域；x,(a)为样本x:在属性 x无关的邻域信息粒子集合为U-Ps(x),记为~x。 a上的取值。对于属性子集RCC,可得到R在U上 定义4给定DS=(U,C,D,V)是不完备邻域 的划分U/R={R1,R2,…,Rm}。 决策系统，X和Y是U上的两个非空子集，定义集 如果V中包含连续型和符号型等属性类型的 合X关于集合Y的相对错误分类率： 对象，则该决策系统称为邻域决策系统。在邻域决 x n Y |X>0 策系统中，当部分样本的条件属性值缺失时，则该 e(X,Y)= 邻域决策系统称为不完备邻域决策系统，缺失值用 0,x|=0 “*”表示。 如果将集合X中的元素分到集合Y中，则出现 定义1设DS=(,C,D,V)是不完备邻域 分类错误的比例为e(X,Y)×100%
值型数据等［４－６］ 。 由于经典粗糙集在处理连续型数 据时需进行离散化预处理，将不可避免地造成信息 的丢失，且对于含有不完备型数据的决策系统，传 统的粗糙集模型较难直接处理。 近年来，针对混 合、模糊、不完备的粗糙集模型扩展及应用成为粒 度计算研究的热点问题［７－１３］ 。 基于粒计算的属性约简研究已取得许多有意 义的成果［１４－１８］ ：文献［１４］研究了混合数据下的知识 发现及邻域粒化问题；文献［１５］提出了悲观多粒度 粗糙集的概念，解决了利用“求同消异”的决策策略 处理多个不可分辨关系之间存在相互独立的情况； 文献［１６］将多粒度粗糙集扩展到邻域多粒度粗糙 集；为提高分类的效果，文献［１７］ 在多粒度粗糙集 的基础上引入了错误分类率的概念，即在允许一定 程度分类率的前提下，寻找数据之间的相关性，以 解决属性间不确定关系的数据分类问题；对于不完 备信息系统，文献［１８］提出了一种基于容差关系的 不完备可变精度多粒度粗糙集模型。 上述研究分别针对不完备粗糙集、变精度粗糙 集进行研究。 由于现实生活中同时存在大量的不 完备、连续数值型、符号型属性数据的情况，现有的 邻域粗糙集计算方法对上述情况和数据集的可控 性调节划分的讨论相对较少。 为此，本文结合多粒 度粗糙集，分析了可变精度模型下不完备邻域决策 系统的上、下近似算子及属性约简，并通过邻域粒 化方法构建了广义邻域下可变精度的粗糙集模型； 在此基础上，构造了一种衡量属性重要度的方法， 并设计了不完备邻域系统的属性约简算法；最后， 通过实例分析验证了算法的有效性。 １ 基本知识 给定一个决策系统 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ），其中：Ｕ＝ ｛ｘ１ ，ｘ２ ，…，ｘｎ ｝表示非空有限样本集合，称为论域；Ｃ 是条件属性集合；Ｄ 是决策属性，Ｃ∩Ｄ＝ϕ，若 Ｄ＝ϕ， 则决策系统转换为信息系统。 Ｖ 为属性值域，对于 ∀ａ∈Ｃ，Ｖａ 为属性 ａ 的值域；ｘｉ（ａ）为样本 ｘｉ 在属性 ａ 上的取值。 对于属性子集 Ｒ⊆Ｃ，可得到 Ｒ 在 Ｕ 上 的划分 Ｕ／ Ｒ ＝ ｛Ｒ１ ，Ｒ２ ，…，Ｒｍ ｝。 如果 Ｖ 中包含连续型和符号型等属性类型的 对象，则该决策系统称为邻域决策系统。 在邻域决 策系统中，当部分样本的条件属性值缺失时，则该 邻域决策系统称为不完备邻域决策系统，缺失值用 “∗”表示。 定义 １ ［１４］ 设 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ）是不完备邻域 决策系统，对于∀ｘ∈Ｕ，定义 ｘ 在 Ｃ∪Ｄ 上的邻域信 息粒子为 ＮＡ（ｘ）＝ ｛ｙ ｙ∈Ｕ，ΔＡ（ｘ，ｙ）≤δ，δ≥０｝，其 中 δ 表示邻域半径，ΔＡ：Ｕ×Ｕ→Ｒ 为 Ｕ 上的一定度 量，满足以下性质： １）∀ｘ，ｙ∈Ｕ， ΔＡ（ ｘ，ｙ） ≥０， 当 ΔＡ（ ｘ，ｙ） ＝ ０ 时， ∀ａｉ∈Ａ，ａｉ（ｘ）＝ ａｉ（ｙ）； ２）∀ｘ，ｙ∈Ｕ，ΔＡ（ｘ，ｙ）＝ ΔＡ（ｙ，ｘ）； ３）∀ｘ，ｙ，ｚ∈Ｕ，ΔＡ（ｘ，ｚ）≤ΔＡ（ｘ，ｙ）＋ΔＡ（ｙ，ｚ）。 对于连续型的数据，采用欧式距离度量： ΔＡ（ｘ，ｙ） ＝ ∑ａｉ∈Ａ ａｉ（ｘ） － ａｉ（ｙ） ２ 对于符号型的数据，可定义： ΔＡ（ｘ，ｙ） ＝ ０， ａｉ（ｘ） ＝ ａｉ（ｙ） {¥， ａｉ（ｘ） ≠ ａｉ（ｙ） 当 δ ＝ ０ 时，变为经典粗糙集模型。 定义 ２ ［１９］ 将邻域等价关系扩展到符号型、连 续型和缺失型等未知属性共存下的不完备模糊系 统，可得到以下广义邻域关系： Ｒ（ｘ） ＝ ｛（ｘ，ｙ） ∈ Ｕ ２ ：∀ａ ∈ ｘ ∩ ｆ １（ｘ） ＝ ｆ １（ｙ），ａ（ｘ） ∈ δ（ｙ，ａ） ∪ ａ（ｙ） ∈ δ（ｘ，ａ） ∪ ａ（ｘ） ＝ ∗ ∪ ａ（ｙ） ＝ ∗｝ 广义邻域关系满足自反性，但不一定满足对称 性和传递性，因为任意样本与其自身是不可分辨 的，所以任何等价关系均满足自反性。 在这里放宽 了对称性和传递性的限制，扩展了应用范围。 定义 ３ ［１９］ 给定 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ）是不完备邻 域决策系统，Ｂ⊆Ｃ，Ｎ（Ｂ）是 ＤＳ 上关于 Ｂ 的邻域关 系所构成的邻域粒子族，对于∀ｘ⊆Ｕ 在 Ｂ 上的邻域， 记为 ＮＢ（ｘ），则 ｘ 在 ＤＳ 上的下近似和上近似分别为 ＰＢ（ｘ）＝ ｛ｘ∈Ｕ ＮＢ（ｘ）⊆ｘ｝，ＰＢ（ｘ）＝ ｛ｘ∈Ｕ ＮＢ（ｘ）∩ ｘ≠ϕ｝，ｘ 的邻域近似边界为 ｂｎｒＢ（ｘ）＝ ＰＢ（ｘ）－ＰＢ（ｘ）。 ＰＢ （ｘ）是可能包含 ｘ 的邻域信息粒子组合的集 合，ＰＢ （ｘ）是包含 ｘ 的邻域信息粒子组合的集合，与 ｘ 无关的邻域信息粒子集合为 Ｕ－ＰＢ （ｘ），记为～ ｘ。 定义 ４ 给定 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ） 是不完备邻域 决策系统，Ｘ 和 Ｙ 是 Ｕ 上的两个非空子集，定义集 合 Ｘ 关于集合 Ｙ 的相对错误分类率： ｅ（Ｘ，Ｙ） ＝ １ － Ｘ ∩ Ｙ Ｘ ， Ｘ ＞ ０ ０， Ｘ ＝ ０ ì î í ïï ïï 如果将集合 Ｘ 中的元素分到集合 Ｙ 中，则出现 分类错误的比例为 ｅ（Ｘ，Ｙ）×１００％。 第 ３ 期 王映龙，等：变精度下不完备邻域决策系统的属性约简算法 ·３８７·
·388· 智能系统学报 第12卷 2 不完备可变精度粗糙集模型 在不完备邻域决策系统DS=(U,C,D,V)中，条 件属性集合为C={C1,C2,C,C4},决策属性集为 定义5给定DS=(U,C,D,V)是不完备邻域 D={d1,d2},{C1,C2,C3}为连续型数值属性，{C,} 决策系统，B二C,决策属性集合D={d1,d2,…,dn}, 为符号型属性，下面通过表1的实例说明。 0≤k<0.5,在可变精度k下，属性集B相对于决策属 表1不完备邻域决策系统(1) 性D的上、下近似分别为 Table 1 Incomplete neighborhood decision system(1) ph(d)=xEUle(Np(x),d;)<1-k U D P(d)={x∈Ule(Ns(x),d:)≤k 0.1 2.1 3.0 2 在可变精度k下，属性集B相对于决策属性D 0.2 2.2 T 的边界域为BN(d)=Pe(d)-Pe(d),负区域为 NEG(d)=U-Pg(d:),正区域为POS=UPa(d:)。 0.2 3.2 2 决策属性值d,在可变精度k的上近似是U中 2.0 3.1 以不小于k的分类样本划分到d上的邻域信息粒 0.2 2.2 3.1 T 2 子的集合，下近似是U中以不小于1-k的分类样本 划分到d:上的邻域信息粒子的集合。根据多粒度 令6=0.1，k=0.2,因为样本x1与x的决策属 粗糙集的思想，在可变精度不完备邻域决策系统 性D取值不同，就算连续型的属性值都在邻域范 中，通过对邻域粒度δ和可变精度k的控制来区分 围内，符号型条件属性取值相同，也不能视为同一 不同的信息。邻域粒度δ越小，可变精度k取值越 类：因为当k=0.2时，即两个样本在C1,C2,C3,Ca 优，区分能力越强。 属性中只能有一个属性取值不同或不在同一邻域 定理1由定义5可得以下性质： 中，所以x1,x2属于同一类，x1与x3,x4不属于同 1)P(d)PB(d:),P(d)ph(d,); 一类。 2)对于B'CBCA,则存在P(d:)CP(d), 定义6给定DS=(U,C,D,V)是不完备邻域 P(d,)P(d)。 决策系统，BCC,决策属性集合D={d1,d2,…,dn}, 证明1)Hx∈Ps(d:),由定义4可得，至少 如果Ha∈B,y.(d)=y(d),称属性a对于集合B 3BEA,使得N(x)二X成立，再由定义3和定义5 是冗余的；如果y.(d)<y(d),则称a是必要的； 可知，e(Ns(x),d:)≤k,于是x∈Ps(d:),从而 如果Ha∈B,属性a对于集合B都是必不可少的， P(d:)CP(d),类似可证P(d:)≤Ps(d,),证毕。 称B是独立的。决策属性d:对属性集合B的依赖 2)由定义5可得，对于Hx∈U,则有e(N(x), 度为 d:)<1-k成立，因为B'CBCA,则e(Ng(x),d:)= POS(d,) Ya=- 1IN(041-(04 | IN(x)I N(x) =e(N(x),d:)< 定义7给定DS=(U,C,D,V)是不完备邻域 1-k,即x∈Ps(d:),所以P(d:)CP(d:)。类似可 决策系统，决策属性集合D={d1,d2,…,dn},BCC, 若属性子集B是不完备邻域决策系统的一个约简 证P(d,)SP(d,),证毕。 集，则B满足： 从以上性质可知：随着可变精度k的增大，{d} 的正区域和负区域减小，而边界域则增大：反之，随 1)y(d)=y(d): 着k的减小，{d:}的正区域和负区域将增大，而边界 2）Ha∈B,y.(d)≠y(d)。 域在缩小。如上所说，在一个合适的可变精度k范 该定义的条件1)保证了在可变精度k下，约简 围下，d有较大的可分辨性。 集与系统中含有全部条件属性时的集合具有相同 性质1在不完备邻域决策系统中，对缺失的 的分辨能力；条件2)保证了属性子集B是独立的， 条件属性值的判定：当决策属性值一致时，如果符 所有的属性都是必不可少的，没有冗余的属性。这 号型条件属性取值相同，连续型属性取值在相同邻 一定义与经典粗糙集模型中的定义在形式上是完 域内的对象归为同一类，否则视为不同类。 全一致的。然而，由于该模型定义了数值空间中的
２ 不完备可变精度粗糙集模型 定义 ５ 给定 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ） 是不完备邻域 决策系统，Ｂ⊆Ｃ，决策属性集合 Ｄ＝ ｛ｄ１ ，ｄ２ ，…，ｄｎ ｝， ０≤ｋ＜０．５，在可变精度 ｋ 下，属性集 Ｂ 相对于决策属 性 Ｄ 的上、下近似分别为 Ｐ ｋ Ｂ （ｄｉ） ＝ ｛ｘ ∈ Ｕ ｅ（ＮＢ（ｘ） ，ｄｉ） ＜ １ － ｋ｝ Ｐ ｋ Ｂ （ｄｉ） ＝ ｛ｘ ∈ Ｕ ｅ（ＮＢ（ｘ） ，ｄｉ） ≤ ｋ｝ 在可变精度 ｋ 下，属性集 Ｂ 相对于决策属性 Ｄ 的边界域为 ＢＮ ｋ Ｂ（ ｄｉ ） ＝ ＰＢ （ ｄｉ ） －ＰＢ （ ｄｉ ），负区域为 ＮＥＧ ｋ Ｂ（ｄｉ）＝ Ｕ－ＰＢ （ｄｉ），正区域为 ＰＯＳ ｋ Ｂ ＝∪ｉ≤ｎ ＰＢ （ｄｉ）。 决策属性值 ｄｉ 在可变精度 ｋ 的上近似是 Ｕ 中 以不小于 ｋ 的分类样本划分到 ｄｉ 上的邻域信息粒 子的集合，下近似是 Ｕ 中以不小于 １－ｋ 的分类样本 划分到 ｄｉ 上的邻域信息粒子的集合。 根据多粒度 粗糙集的思想，在可变精度不完备邻域决策系统 中，通过对邻域粒度 δ 和可变精度 ｋ 的控制来区分 不同的信息。 邻域粒度 δ 越小，可变精度 ｋ 取值越 优，区分能力越强。 定理 １ 由定义 ５ 可得以下性质： １） Ｐ ｋ Ｂ （ｄｉ）⊆ＰＢ （ｄｉ），Ｐ ｋ Ｂ （ｄｉ）⊆Ｐ Ｂ （ｄｉ）； ２） 对于 Ｂ′⊆Ｂ⊆Ａ，则存在Ｐ ｋ Ｂ′ （ ｄｉ ） ⊆Ｐ ｋ Ｂ （ ｄｉ ）， Ｐ ｋ Ｂ′（ｄｉ）⊆Ｐ ｋ Ｂ （ｄｉ）。 证明 １） ∀ｘ∈ＰＢ （ ｄｉ ），由定义 ４ 可得，至少 ∃Ｂ∈Ａ，使得 ＮＢ（ｘ）⊆Ｘ 成立，再由定义 ３ 和定义 ５ 可知，ｅ （ ＮＢ （ ｘ） ， ｄｉ ） ≤ ｋ，于是 ｘ ∈ ＰＢ （ ｄｉ ），从而 Ｐ ｋ Ｂ （ｄｉ）⊆ＰＢ （ｄｉ），类似可证Ｐ ｋ Ｂ （ｄｉ）⊆ＰＢ （ｄｉ），证毕。 ２）由定义 ５ 可得，对于∀ｘ∈Ｕ，则有 ｅ（ＮＢ（ｘ） ， ｄｉ）＜１－ｋ 成立，因为 Ｂ′⊆Ｂ⊆Ａ，则 ｅ（ＮＢ′（ ｘ），ｄｉ ） ＝ １－ ＮＢ′（ｘ）∩ｄｉ ＮＢ′（ｘ） ＜１－ ＮＢ（ｘ）∩ｄｉ ＮＢ（ｘ） ＝ ｅ（ＮＢ （ ｘ），ｄｉ ） ＜ １－ｋ，即 ｘ∈ＰＢ （ｄｉ），所以Ｐ ｋ Ｂ′（ｄｉ）⊆Ｐ ｋ Ｂ （ｄｉ）。 类似可 证 Ｐ ｋ Ｂ′（ｄｉ）⊆Ｐ ｋ Ｂ （ｄｉ），证毕。 从以上性质可知：随着可变精度 ｋ 的增大，｛ｄｉ｝ 的正区域和负区域减小，而边界域则增大；反之，随 着 ｋ 的减小，｛ｄｉ｝的正区域和负区域将增大，而边界 域在缩小。 如上所说，在一个合适的可变精度 ｋ 范 围下，ｄｉ 有较大的可分辨性。 性质 １ 在不完备邻域决策系统中，对缺失的 条件属性值的判定：当决策属性值一致时，如果符 号型条件属性取值相同，连续型属性取值在相同邻 域内的对象归为同一类，否则视为不同类。 在不完备邻域决策系统 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ）中，条 件属性集合为 Ｃ ＝ ｛Ｃ１ ，Ｃ２ ，Ｃ３ ，Ｃ４ ｝，决策属性集为 Ｄ＝ ｛ｄ１ ，ｄ２ ｝，｛Ｃ１ ，Ｃ２ ，Ｃ３ ｝为连续型数值属性，｛Ｃ４ ｝ 为符号型属性，下面通过表 １ 的实例说明。 表 １ 不完备邻域决策系统（１） Ｔａｂｌｅ １ Ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ（１） Ｕ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｄ ｘ１ ０．１ ２．１ ３．０ Ｔ １ ｘ２ ０．２ ２．２ ∗ Ｔ １ ｘ３ ０．２ ∗ ３．２ Ｔ １ ｘ４ ∗ ２．０ ３．１ Ｆ １ ｘ５ ０．２ ２．２ ３．１ Ｔ ２ 令 δ ＝ ０ １，ｋ ＝ ０ ２，因为样本 ｘ１ 与 ｘ５ 的决策属 性 Ｄ 取值不同，就算连续型的属性值都在邻域范 围内，符号型条件属性取值相同，也不能视为同一 类；因为当 ｋ ＝ ０ ２ 时，即两个样本在 Ｃ１ ，Ｃ２ ，Ｃ３ ，Ｃ４ 属性中只能有一个属性取值不同或不在同一邻域 中，所以 ｘ１ ，ｘ２ 属于同一类，ｘ１ 与 ｘ３ ，ｘ４ 不属于同 一类。 定义 ６ 给定 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ） 是不完备邻域 决策系统，Ｂ⊆Ｃ，决策属性集合 Ｄ＝ ｛ｄ１ ，ｄ２ ，…，ｄｎ ｝， 如果∀ａ∈Ｂ，γ ｋ Ｂ－ａ（ｄ）＝ γ ｋ Ｂ（ｄ），称属性 ａ 对于集合 Ｂ 是冗余的；如果 γ ｋ Ｂ－ａ（ ｄ） ＜γ ｋ Ｂ（ ｄ），则称 ａ 是必要的； 如果∀ａ∈Ｂ，属性 ａ 对于集合 Ｂ 都是必不可少的， 称 Ｂ 是独立的。 决策属性 ｄｉ 对属性集合 Ｂ 的依赖 度为 γ ｋ Ｂ ＝ ＰＯＳ ｋ Ｂ（ｄｉ） Ｕ 定义 ７ 给定 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ）是不完备邻域 决策系统，决策属性集合 Ｄ＝ ｛ｄ１ ，ｄ２ ，…，ｄｎ ｝，Ｂ⊆Ｃ， 若属性子集 Ｂ 是不完备邻域决策系统的一个约简 集，则 Ｂ 满足： １） γ ｋ Ｂ（ｄ）＝ γ ｋ Ｃ（ｄ）； ２） ∀ａ∈Ｂ， γ ｋ Ｂ－ａ（ｄ）≠γ ｋ Ｂ （ｄ）。 该定义的条件 １）保证了在可变精度 ｋ 下，约简 集与系统中含有全部条件属性时的集合具有相同 的分辨能力；条件 ２）保证了属性子集 Ｂ 是独立的， 所有的属性都是必不可少的，没有冗余的属性。 这 一定义与经典粗糙集模型中的定义在形式上是完 全一致的。 然而，由于该模型定义了数值空间中的 ·３８８· 智 能 系 统 学 报 第 １２ 卷
第3期 王映龙，等：变精度下不完备邻域决策系统的属性约简算法 .389. 粒化和逼近，而经典粗糙集是定义在离散空间的， 时间复杂度为O(U),第3步的最坏时间复杂度 因此适合于完全不同的应用场合。 为0(|C2|Ulog2|U|),第4步的时间复杂度为 定义8给定DS=(U,C,D,V)是不完备邻域 O(1),第5步的最坏时间复杂度为O(|C-RED|2。 决策系统，BCC,对于Ha∈C-B,则属性a相对于B |Ulog2|U),第6和第7步的时间复杂度为O(1)。 的重要性计算方式为 由上述分析可知，本算法的时间复杂度主要由步骤 SIG(a,B,D)=Yuial (D)-YB(D) 3和步骤6的计算耗时所决定，因此该算法的最坏 3变精度下不完备邻域系统的属性 时间复杂度为0(|C2|U1og2|U)；由于算法无 需额外的储存空间，可知算法的最坏空间复杂度为 约简 O(|U|C+U)。文献[12]在完备决策系统下设 3.1变精度下不完备邻域系统的属性约简算法 计了变精度悲观多粒度粗糙集的下近似分布粒度 当处理高维的大规模数据时，为减少计算时间 约简算法，其时间复杂度为0(U2|C2):文献 和保证知识获取的简洁，去除冗余属性尤为必要。 [13]在信息观下提出了基于不一致邻域矩阵的属 为此，本文针对不完备邻域决策系统，在可变精度 性约简算法，其时间复杂度为O(|U2|C3),空间 粗糙集模型下，提出了一种基于属性重要度指标的 复杂度为0(|02|C|)。本文的算法在计算效率和 属性约简算法。首先，根据决策属性对原样本集合 存储空间上具有一定优势，且能处理不完备的邻域 做初步划分，再根据可变精度k值和邻域半径8值， 数据，算法的扩展性较好。 计算邻域关系V:及对应属性依赖度Y,(D),然后 3.2与经典粗糙集及邻域模型比较 采用贪心式搜索方法，每次计算剩余属性的属性重 与经典粗糙集及邻域模型相比较，本文提出的 要度，从中选择属性重要度最大的属性加入约简集 变精度不完备邻域系统的属性约简模型具有以下 合中，直到约简结果中属性集合的重要度等于原始 优点： 属性集的重要度，即得到不完备邻域决策系统的属 1)经典粗糙集的属性约简适用于离散型属性 性约简结果。由此，变精度下不完备邻域系统的属 约简，需先离散化连续型数据，这将不可避免地造 性约简算法描述如下。 成信息的丢失。而变精度不完备邻域系统的属性 输入不完备邻域决策系统DS=(U,C,D,V), 约简模型既可处理离散型属性约简，也可直接用于 邻域半径8，可变精度k。 连续型属性约简。本文的属性约简模型是对经典 输出属性约简结果RED。 粗糙集模型的扩展。 1)初始化RED=中： 2)对于含有不完备型数据的决策系统，经典的 2)根据决策属性D的值对论域U进行划分 粗糙集模型较难直接处理，而本文提出的属性约简 U/D={D1,D2,…,Dm} 模型可直接对数据进行分析，并在可变精度的调节 3)根据可变精度k值和邻域半径δ值，计算邻 下，能得到数据不同层次的信息粒度。 域关系N,及对应属性依赖度y(D); 3)变精度不完备邻域系统的属性约简模型是 对邻域模型的进一步扩展，基于邻域的属性约简需 4)选取y(D)中的最大值，令RED=C:; 计算各样本的邻域，而本文的属性约简模型因为在 5)对于HC:∈C-RED,根据定义6和定义7计 可变精度的调控下先对样本进行初步筛选，再进行 算属性的重要度SIG(C:,RED,D)=Ymuc(D)- 邻域计算，有效减少了计算量。 y(D),选取属性重要度最大的条件属性：其满足 SIG(C:,RED,D)=max{SIG(C:,RED,D)},并将属 4实例分析 性C:放入RED; 为了验证该方法的有效性，我们选择了一个不 6)如果ym(D)≠y(D),则算法回到5)，否则 完备邻域决策系统进行详细分析，表2中共有10个 执行7)： 样本对象，条件属性集为{C,C2,C,C4},决策属 7)输出约简RED,算法结束。 性为{D}。设置邻域半径8=0.1，即两样本之间的 算法复杂度分析： 邻域半径小于等于0.1：可变精度k=0.2,即两个样 算法的第1步的时间复杂度为0(1)，第2步的 本在条件属性集中只能有一个属性取值不同或不
粒化和逼近，而经典粗糙集是定义在离散空间的， 因此适合于完全不同的应用场合。 定义 ８ 给定 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ） 是不完备邻域 决策系统，Ｂ⊆Ｃ，对于∀ａ∈Ｃ－Ｂ，则属性 ａ 相对于 Ｂ 的重要性计算方式为 ＳＩＧ（ａ，Ｂ，Ｄ） ＝ γ ｋ Ｂ∪｛ａ｝（Ｄ） － γ ｋ Ｂ（Ｄ） ３ 变精度下不完备邻域系统的属性 约简 ３．１ 变精度下不完备邻域系统的属性约简算法 当处理高维的大规模数据时，为减少计算时间 和保证知识获取的简洁，去除冗余属性尤为必要。 为此，本文针对不完备邻域决策系统，在可变精度 粗糙集模型下，提出了一种基于属性重要度指标的 属性约简算法。 首先，根据决策属性对原样本集合 做初步划分，再根据可变精度 ｋ 值和邻域半径 δ 值， 计算邻域关系 ＮＡ 及对应属性依赖度 γ ｋ Ｃｉ （Ｄ），然后 采用贪心式搜索方法，每次计算剩余属性的属性重 要度，从中选择属性重要度最大的属性加入约简集 合中，直到约简结果中属性集合的重要度等于原始 属性集的重要度，即得到不完备邻域决策系统的属 性约简结果。 由此，变精度下不完备邻域系统的属 性约简算法描述如下。 输入 不完备邻域决策系统 ＤＳ ＝ （Ｕ，Ｃ，Ｄ，Ｖ）， 邻域半径 δ，可变精度 ｋ。 输出 属性约简结果 ＲＥＤ。 １）初始化 ＲＥＤ＝ϕ； ２） 根据决策属性 Ｄ 的值对论域 Ｕ 进行划分 Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，…，Ｄｍ ｝； ３）根据可变精度 ｋ 值和邻域半径 δ 值，计算邻 域关系 ＮＡ 及对应属性依赖度 γ ｋ Ｃｉ （Ｄ）； ４）选取 γ ｋ Ｃｉ （Ｄ）中的最大值，令 ＲＥＤ＝Ｃｉ； ５）对于∀Ｃｉ∈Ｃ－ＲＥＤ，根据定义 ６ 和定义 ７ 计 算属性的重要度 ＳＩＧ（Ｃｉ，ＲＥＤ，Ｄ）＝ γ ｋ ＲＥＤ∪｛Ｃｉ ｝ （Ｄ） － γ ｋ ＲＥＤ（Ｄ），选取属性重要度最大的条件属性： 其满足 ＳＩＧ（Ｃｉ，ＲＥＤ，Ｄ）＝ ｍａｘ｛ＳＩＧ（Ｃｉ，ＲＥＤ，Ｄ）｝，并将属 性 Ｃｉ 放入 ＲＥＤ； ６）如果 γ ｋ ＲＥＤ（Ｄ）≠γ ｋ Ｃ（Ｄ），则算法回到 ５），否则 执行 ７）； ７）输出约简 ＲＥＤ，算法结束。 算法复杂度分析： 算法的第 １ 步的时间复杂度为 Ｏ（１），第 ２ 步的 时间复杂度为 Ｏ（ Ｕ ），第 ３ 步的最坏时间复杂度 为 Ｏ（ Ｃ ２ Ｕ ｌｏｇ２ Ｕ ），第 ４ 步的时间复杂度为 Ｏ（１），第 ５ 步的最坏时间复杂度为 Ｏ（ Ｃ－ＲＥＤ ２ 。 Ｕ ｌｏｇ２ Ｕ ），第 ６ 和第 ７ 步的时间复杂度为Ｏ（１）。 由上述分析可知，本算法的时间复杂度主要由步骤 ３ 和步骤 ６ 的计算耗时所决定，因此该算法的最坏 时间复杂度为 Ｏ（ Ｃ ２ Ｕ ｌｏｇ２ Ｕ ）； 由于算法无 需额外的储存空间，可知算法的最坏空间复杂度为 Ｏ（ Ｕ Ｃ ＋ Ｕ ）。 文献［１２］在完备决策系统下设 计了变精度悲观多粒度粗糙集的下近似分布粒度 约简算法，其时间复杂度为 Ｏ（ Ｕ ２ Ｃ ２ ）；文献 ［１３］在信息观下提出了基于不一致邻域矩阵的属 性约简算法，其时间复杂度为 Ｏ（ Ｕ ２ Ｃ ３ ），空间 复杂度为 Ｏ（ Ｕ ２ Ｃ ）。 本文的算法在计算效率和 存储空间上具有一定优势，且能处理不完备的邻域 数据，算法的扩展性较好。 ３．２ 与经典粗糙集及邻域模型比较 与经典粗糙集及邻域模型相比较，本文提出的 变精度不完备邻域系统的属性约简模型具有以下 优点： １）经典粗糙集的属性约简适用于离散型属性 约简，需先离散化连续型数据，这将不可避免地造 成信息的丢失。 而变精度不完备邻域系统的属性 约简模型既可处理离散型属性约简，也可直接用于 连续型属性约简。 本文的属性约简模型是对经典 粗糙集模型的扩展。 ２）对于含有不完备型数据的决策系统，经典的 粗糙集模型较难直接处理，而本文提出的属性约简 模型可直接对数据进行分析，并在可变精度的调节 下，能得到数据不同层次的信息粒度。 ３）变精度不完备邻域系统的属性约简模型是 对邻域模型的进一步扩展，基于邻域的属性约简需 计算各样本的邻域，而本文的属性约简模型因为在 可变精度的调控下先对样本进行初步筛选，再进行 邻域计算，有效减少了计算量。 ４ 实例分析 为了验证该方法的有效性，我们选择了一个不 完备邻域决策系统进行详细分析，表 ２ 中共有 １０ 个 样本对象，条件属性集为｛Ｃ１ ， Ｃ２ ， Ｃ３ ， Ｃ４ ｝， 决策属 性为｛Ｄ｝。 设置邻域半径 δ ＝ ０．１，即两样本之间的 邻域半径小于等于 ０．１；可变精度 ｋ ＝ ０．２，即两个样 本在条件属性集中只能有一个属性取值不同或不 第 ３ 期 王映龙，等：变精度下不完备邻域决策系统的属性约简算法 ·３８９·
·390. 智能系统学报 第12卷 在同一邻域中。 完备邻域决策系统的属性约简为{C1,C2,C3}。 表2不完备邻域决策系统(2) 上述实例是对10组样本对象进行的计算和分 Table 2 Incomplete neighborhood decision system(2) 析，本文算法中可变精度k值和邻域半径δ值是可 0 C C C3 0> 变的，在现实应用中可根据具体需求设定可变精度 0.3 0.3 0.75 2 poor 和邻域半径以满足知识的细化程度。 0.5 0.2 0.8 T poor 通过上述实例分析，利用本文的算法计算属性 0.5 T 800d 约简结果需执行0(|C2|Ulog2|U2)次，文献 [12]中的算法需要执行0(|c21U2)次，本文在一 XA 0.9 0.8 0.4 T 800d 定程度降低了算法的计算复杂性。在存储空间上， 145 good 本文算法需50个储存空间，而文献[13]构建矩阵 0.3 0.4 poor 需400个空间用于存储邻域矩阵元素，本文算法占 0.4 0.95 F poor 用的空间相对较少。因此，本文所提出的算法在计 0.2 0.8 F good 算效率上具有优势，并较好地减少算法对存储空间 0.25 0.75 0.6 800d 的消耗。 0.2 0.6 poor 5结束语 首先根据算法第2)步可计算出不完备邻域决 策系统在决策属性{D)下的划分为{D,D2},即 针对不完备邻域决策系统的属性约简问题，本 D(x)=1x3,x4,xs,x8,x 文通过邻域粒化的方法，构建了广义邻域下可变精 D2(x)={x1,x2,x6,x7,x10} 度的粗糙集模型，同时构造了一种属性重要度的评 根据邻域半径8=0.1和可变精度k=0.2,通过 价方法，并设计了不完备邻域系统的属性约简算 算法的第3)步可分别计算每个属性的邻域关系和 法。通过实例分析，该方法能对不完备的数值型和 所对应的依赖度，即 符号型混合数据进行属性约简。在大数据时代，数 D)=2(D)=4 据的不断产生，需实时更新信息系统，下一步将在 5 此背景下研究，当不完备邻域决策系统中的数据动 发=品发m)品 态变化时如何对属性约简进行增量更新。 根据算法第4)步，因为{y(D)}中依赖度的最 参考文献： 大值所对应的属性为C2,则令RED={C2}。继续执 [1]PAWLAK Z.Rough sets and intelligent data analysis[J]. 行算法第5)步，在{C-RED条件属性集中，依次计 Information sciences,2002,147(1):1-12. 算剩余属性的重要度，可得 [2]ZHANG Junbo,WONG Jiansyuan,PAN Yi,et al,A parallel matrix-based method for computing approximations SIG(C,RED,D)=Y(D)-(D)= 10 in incomplete information systems[J].IEEE transactions on knowledge and data engineering,2015,27(2):326-339. SIG(C3,RED,D)=Yu(D)-(D)= 5 [3]WU Weizhi,QIAN Yuhua,LI Tongjun,et al.On rule SIG(Ca,RED,D)=YURED(D)-Y(D)=0 acquisition in incomplete multi-scale decision tables[J]. Information sciences,2017,378:282-302. 则可知C,为所对应的属性重要度最大的属性，将属 [4]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M] 性C,放入RED中，有RED={C2,C3}。 北京：科学出版社，2001：123-131. 再根据算法第6)步，由于此时yn(D)≠Y [5]刘芳，李天瑞.基于边界域的不完备信息系统属性约简 (D),则算法回到5)，同样可计算出C,为剩余属性 方法[].计算机科学，2016,43(3)：242-245， 中属性重要度最大的属性，将属性C,放入RED中， LIU Fang,LI Tianrui.Method for attribute reduction based on rough sets boundary regions[J].Computer science, 有RED={C2,C3,C,}。转至算法的第6)步，由于此 2016,43(3):242-245. 时yn(D)=y(D),则算法转至第7)，输出属性约 [6]WU Jianrong,KAI Xuewen,LI Jiaojiao.Atoms of monotone 简结果。因此，按照以上算法步骤，当δ=0.1时，不 set-valued measures and integrals J].Fuzzy sets and
在同一邻域中。 表 ２ 不完备邻域决策系统（２） Ｔａｂｌｅ ２ Ｉｎｃｏｍｐｌｅｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ（２） Ｕ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｄ ｘ１ ０．３ ０．３ ０．７５ Ｔ ｐｏｏｒ ｘ２ ０．５ ０．２ ０．８ Ｔ ｐｏｏｒ ｘ３ １ ∗ ０．５ Ｔ ｇｏｏｄ ｘ４ ０．９ ０．８ ０．４ Ｔ ｇｏｏｄ ｘ５ ∗ ０．６ ０．４５ Ｆ ｇｏｏｄ ｘ６ ０．３ ０．４ ∗ Ｆ ｐｏｏｒ ｘ７ ０ ０．４ ０．９５ Ｆ ｐｏｏｒ ｘ８ ０．２ ∗ ０．８ Ｆ ｇｏｏｄ ｘ９ ０．２５ ０．７５ ０．６ Ｆ ｇｏｏｄ ｘ１０ ０．２ ０．６ ∗ ∗ ｐｏｏｒ 首先根据算法第 ２）步可计算出不完备邻域决 策系统在决策属性{Ｄ}下的划分为｛Ｄ１ ，Ｄ２ ｝，即 Ｄ１（ｘ） ＝ ｛ｘ３ ，ｘ４ ，ｘ５ ，ｘ８ ，ｘ９ ｝ Ｄ２（ｘ） ＝ ｛ｘ１ ，ｘ２ ，ｘ６ ，ｘ７ ，ｘ１０ ｝ 根据邻域半径 δ ＝ ０．１ 和可变精度 ｋ ＝ ０．２，通过 算法的第 ３）步可分别计算每个属性的邻域关系和 所对应的依赖度，即 γ ０．２ Ｃ１ （Ｄ） ＝ １ ２ γ ０．２ Ｃ２ （Ｄ） ＝ ４ ５ γ ０．２ Ｃ３ （Ｄ） ＝ ７ １０ γ ０．２ Ｃ４ （Ｄ） ＝ １ １０ 根据算法第 ４）步，因为｛γ ｋ Ｃｉ （Ｄ）｝中依赖度的最 大值所对应的属性为 Ｃ２ ，则令 ＲＥＤ＝ ｛Ｃ２ ｝。 继续执 行算法第 ５）步，在｛Ｃ－ＲＥＤ｝条件属性集中，依次计 算剩余属性的重要度，可得 ＳＩＧ（Ｃ１ ，ＲＥＤ，Ｄ） ＝ γ ０．２ Ｃ１∪ＲＥＤ（Ｄ） － γ ０．２ ＲＥＤ（Ｄ） ＝ １ １０ ＳＩＧ（Ｃ３ ，ＲＥＤ，Ｄ） ＝ γ ０．２ Ｃ３∪ＲＥＤ（Ｄ） － γ ０．２ ＲＥＤ（Ｄ） ＝ １ ５ ＳＩＧ（Ｃ４ ，ＲＥＤ，Ｄ） ＝ γ ０．２ Ｃ４∪ＲＥＤ（Ｄ） － γ ０．２ ＲＥＤ（Ｄ） ＝ ０ 则可知 Ｃ３ 为所对应的属性重要度最大的属性，将属 性 Ｃ３ 放入 ＲＥＤ 中，有 ＲＥＤ＝ ｛Ｃ２ ，Ｃ３ ｝。 再根据算法第 ６） 步，由于此时 γ ｋ ＲＥＤ （Ｄ） ≠γ ｋ Ｃ （Ｄ），则算法回到 ５），同样可计算出 Ｃ１ 为剩余属性 中属性重要度最大的属性，将属性 Ｃ１ 放入 ＲＥＤ 中， 有 ＲＥＤ＝ ｛Ｃ２ ，Ｃ３ ，Ｃ１ ｝。 转至算法的第 ６）步，由于此 时 γ ｋ ＲＥＤ（Ｄ）＝ γ ｋ Ｃ（Ｄ），则算法转至第 ７），输出属性约 简结果。 因此，按照以上算法步骤， 当 δ ＝ ０．１ 时，不 完备邻域决策系统的属性约简为｛Ｃ１ ，Ｃ２ ，Ｃ３ ｝。 上述实例是对 １０ 组样本对象进行的计算和分 析，本文算法中可变精度 ｋ 值和邻域半径 δ 值是可 变的，在现实应用中可根据具体需求设定可变精度 和邻域半径以满足知识的细化程度。 通过上述实例分析，利用本文的算法计算属性 约简结果需执行 Ｏ （ Ｃ ２ Ｕ ｌｏｇ２ Ｕ ２ ） 次，文献 ［１２］中的算法需要执行 Ｏ（ Ｃ ２ Ｕ ２ ）次，本文在一 定程度降低了算法的计算复杂性。 在存储空间上， 本文算法需 ５０ 个储存空间，而文献［１３］ 构建矩阵 需 ４００ 个空间用于存储邻域矩阵元素，本文算法占 用的空间相对较少。 因此，本文所提出的算法在计 算效率上具有优势，并较好地减少算法对存储空间 的消耗。 ５ 结束语 针对不完备邻域决策系统的属性约简问题，本 文通过邻域粒化的方法，构建了广义邻域下可变精 度的粗糙集模型，同时构造了一种属性重要度的评 价方法，并设计了不完备邻域系统的属性约简算 法。 通过实例分析，该方法能对不完备的数值型和 符号型混合数据进行属性约简。 在大数据时代，数 据的不断产生，需实时更新信息系统，下一步将在 此背景下研究，当不完备邻域决策系统中的数据动 态变化时如何对属性约简进行增量更新。 参考文献： ［１］ ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ ａｎｄ ｉｎｔｅｌｌｉｇｅｎｔ ｄａｔａ ａｎａｌｙｓｉｓ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００２， １４７（１）： １－１２． ［２］ ＺＨＡＮＧ Ｊｕｎｂｏ， ＷＯＮＧ Ｊｉａｎｓｙｕａｎ， ＰＡＮ Ｙｉ， ｅｔ ａｌ， Ａ ｐａｒａｌｌｅｌ ｍａｔｒｉｘ⁃ｂａｓｅｄ ｍｅｔｈｏｄ ｆｏｒ ｃｏｍｐｕｔｉｎｇ ａｐｐｒｏｘｉｍａｔｉｏｎｓ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１５， ２７（２）：３２６－３３９． ［３］ ＷＵ Ｗｅｉｚｈｉ， ＱＩＡＮ Ｙｕｈｕａ， ＬＩ Ｔｏｎｇｊｕｎ， ｅｔ ａｌ． Ｏｎ ｒｕｌｅ ａｃｑｕｉｓｉｔｉｏｎ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｍｕｌｔｉ⁃ｓｃａｌｅ ｄｅｃｉｓｉｏｎ ｔａｂｌｅｓ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１７， ３７８： ２８２－３０２． ［４］张文修， 吴伟志， 梁吉业， 等． 粗糙集理论与方法［Ｍ］． 北京：科学出版社， ２００１： １２３－１３１． ［５］刘芳，李天瑞． 基于边界域的不完备信息系统属性约简 方法［Ｊ］． 计算机科学， ２０１６， ４３（３）： ２４２－２４５． ＬＩＵ Ｆａｎｇ， ＬＩ Ｔｉａｎｒｕｉ． Ｍｅｔｈｏｄ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｒｏｕｇｈ ｓｅｔｓ ｂｏｕｎｄａｒｙ ｒｅｇｉｏｎｓ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１６， ４３（３）： ２４２－２４５． ［６］ＷＵ Ｊｉａｎｒｏｎｇ， ＫＡＩ Ｘｕｅｗｅｎ， ＬＩ Ｊｉａｏｊｉａｏ． Ａｔｏｍｓ ｏｆ ｍｏｎｏｔｏｎｅ ｓｅｔ⁃ｖａｌｕｅｄ ｍｅａｓｕｒｅｓ ａｎｄ ｉｎｔｅｇｒａｌｓ ［ Ｊ ］． Ｆｕｚｚｙ ｓｅｔｓ ａｎｄ ·３９０· 智 能 系 统 学 报 第 １２ 卷
第3期 王映龙，等：变精度下不完备邻域决策系统的属性约简算法 ·391· systems,2015,183:972-979 approximation [J].Journal of software,2008,19(3): [7]王国胤，张清华.不同知识粒度下粗糙集的不确定性研 640-649. 究[J].计算机学报，2008,31(9)：1588-1598 [15 QIAN Yuhua,LI Shunyong,LIANG Jiye.Pessimistic WANG Guoyin,ZHANG Qinghua.Uncertainty of rough set rough set based decisions:a multigranulation fusion in different knowledge granularities[J].Chinese journal of strategy[J].Information sciences,2014,264:196-210. computers,2008,31(9):1588-1598. [16]LIN Guoping,QIAN Yuhua,LI Jinjin.Neighborhood based [8]钱文彬，杨炳儒，谢永红，等.一种基于属性度量的快速 multigranulation rough sets [J].International journal of 属性约简算法[J].小型微型计算机系统，2014,35(6)： approximate reasoning,2012,7(53):1080-1093. 1407-1411. [17]沈家兰，汪小燕，申元霞.可变程度多粒度粗糙集[J] QIAN Wenbin,YANG Bingru,XIE Yonghong,et al.A 小型微型计算机系统，2016,37(05)：1012-1016 quick algorithm for attribute reduction based on attribute SHEN Jialan,WANG Xiaoyan,SHEN Yuanxia.Variable measure[J].Journal of chinese computer systems,2014, Grade multi-granulation rough set [J].Journal of Chinese 35(6):1407-1411. computer systems,2016,37(5):1012-1016. [9]鞠恒荣，马兴斌，杨习贝，等.不完备信息系统中测试 [18]许韦，吴陈，杨习贝.基于容差关系的不完备可变精度 代价敏感的可变精度分类粗糙集[J].智能系统学报， 多粒度粗糙集[J].计算机应用研究，2013,30(6)： 2014,9(2):219-223. 1712-1715. JU Hengrong,MA Xingbin,YANG Xibei,et al.Test-cost- XU Wei,WU Chen,YANG Xibei.Incomplete variable sensitive based variable precision classification rough set in precision multigranularity rough set based on tolerance incomplete information system[.CAAI transactions on relation[J].Application research of computers,2013,30 intelligent systems,2014,9(2):219-223. (6):1712-1715. [10]陈吴，杨俊安，庄镇泉.变精度粗糙集的属性核和最小属 [19]徐久成，张灵均，孙林，等.广义邻域关系下不完备混 性约简算法[J].计算机学报，2012,35(5)：1011-1017. 合决策系统的约简[J].计算机科学，2013,40(4)： CHEN Hao,YANG Junan,ZHUANG Zhenquan.The core 244-248. of attributes and minimal attributes reduction in variable XU Jiucheng,ZHANG Lingjun,SUN Lin,et al. precision rough set[J].Chinese journal of computers, Reduction in incomplete hybrid decision systems based on 2012,35(5):1011-1017. generalized neighborhood relationship[].Computer [11]张清华，薛玉斌，王国胤.粗糙集的最优近似集[J].软 science,2013,40(4):244-248. 件学报，2016,27(2)：295-308. 作者简介： ZHANG Qinghua,XUE Yubin,WANG Guoyin.Optimal 王映龙，男，1970年生，教授，博士， approximate sets of rough sets[J].Journal of software, 主要研究方向为知识发现、数据挖掘和 2016,27(2):295-308. 计算智能。 [12]孟慧丽，马媛媛，徐久成.基于下近似分布粒度熵的变 精度悲观多粒度粗糙集粒度约简[J].计算机科学， 2016,43(2):83-85,104. MENG Huili,MA Yuanyuan,XU Jiucheng.Granularity reduct of variable precision pessimistic multi-granulation 曾祺，女，1991年生，硕士研究生. rough set based on granularity entropy of lower approximate 主要研究方向为粗糙集理论与知识 distribution[J].Computer science,2016.43(2):83- 发现。 85,104. [13]续欣莹，刘海涛，谢珺，等.信息观下基于不一致邻域 矩阵的属性约简[J].控制与决策，2016,31(1)： 130-136. XU Xinying,LIU Haitao,XIE Jun,et al.Attribute 钱文彬，男，1984年生，讲师，博士， reduction based on inconsistent neighborhood matrix under 主要研究方向为粗糙集、粒计算与知识 information view[J].Control and decision,2016,31(1): 发现。 130-136. [14]胡清华，于达仁，谢宗霞.基于邻域粒化和粗糙逼近的 数值属性约简[J].软件学报，2008,19(3)：640-649. HU Qinghua,YU Daren,XIE Zongxia.Numerical attribute reduction based on neighborhood granulation and rough
ｓｙｓｔｅｍｓ， ２０１５， １８３： ９７２－９７９． ［７］王国胤， 张清华． 不同知识粒度下粗糙集的不确定性研 究［Ｊ］． 计算机学报，２００８， ３１（９）：１５８８－１５９８． ＷＡＮＧ Ｇｕｏｙｉｎ， ＺＨＡＮＧ Ｑｉｎｇｈｕａ． Ｕｎｃｅｒｔａｉｎｔｙ ｏｆ ｒｏｕｇｈ ｓｅｔ ｉｎ ｄｉｆｆｅｒｅｎｔ ｋｎｏｗｌｅｄｇｅ ｇｒａｎｕｌａｒｉｔｉｅｓ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００８， ３１（９）： １５８８－１５９８． ［８］钱文彬，杨炳儒，谢永红，等． 一种基于属性度量的快速 属性约简算法［Ｊ］． 小型微型计算机系统， ２０１４， ３５（６）： １４０７－１４１１． ＱＩＡＮ Ｗｅｎｂｉｎ， ＹＡＮＧ Ｂｉｎｇｒｕ， ＸＩＥ Ｙｏｎｇｈｏｎｇ， ｅｔ ａｌ． Ａ ｑｕｉｃｋ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ａｔｔｒｉｂｕｔｅ ｍｅａｓｕｒｅ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１４， ３５（６）： １４０７－１４１１． ［９］鞠恒荣， 马兴斌， 杨习贝， 等． 不完备信息系统中测试 代价敏感的可变精度分类粗糙集［ Ｊ］． 智能系统学报， ２０１４， ９（２）：２１９－２２３． ＪＵ Ｈｅｎｇｒｏｎｇ， ＭＡ Ｘｉｎｇｂｉｎ， ＹＡＮＧ Ｘｉｂｅｉ， ｅｔ ａｌ． Ｔｅｓｔ⁃ｃｏｓｔ⁃ ｓｅｎｓｉｔｉｖｅ ｂａｓｅｄ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１４， ９（２）： ２１９－２２３． ［１０］陈昊， 杨俊安， 庄镇泉． 变精度粗糙集的属性核和最小属 性约简算法［Ｊ］． 计算机学报， ２０１２， ３５（５）： １０１１－１０１７． ＣＨＥＮ Ｈａｏ， ＹＡＮＧ Ｊｕｎａｎ， ＺＨＵＡＮＧ Ｚｈｅｎｑｕａｎ． Ｔｈｅ ｃｏｒｅ ｏｆ ａｔｔｒｉｂｕｔｅｓ ａｎｄ ｍｉｎｉｍａｌ ａｔｔｒｉｂｕｔｅｓ ｒｅｄｕｃｔｉｏｎ ｉｎ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｒｏｕｇｈ ｓｅｔ ［ Ｊ ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０１２， ３５（５）：１０１１－１０１７． ［１１］张清华，薛玉斌，王国胤． 粗糙集的最优近似集［ Ｊ］． 软 件学报， ２０１６， ２７（２）：２９５－３０８． ＺＨＡＮＧ Ｑｉｎｇｈｕａ， ＸＵＥ Ｙｕｂｉｎ， ＷＡＮＧ Ｇｕｏｙｉｎ． Ｏｐｔｉｍａｌ ａｐｐｒｏｘｉｍａｔｅ ｓｅｔｓ ｏｆ ｒｏｕｇｈ ｓｅｔｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２０１６， ２７（２）： ２９５－３０８． ［１２］孟慧丽，马媛媛，徐久成． 基于下近似分布粒度熵的变 精度悲观多粒度粗糙集粒度约简［ Ｊ］． 计算机科学， ２０１６， ４３（２）： ８３－８５，１０４． ＭＥＮＧ Ｈｕｉｌｉ， ＭＡ Ｙｕａｎｙｕａｎ， ＸＵ Ｊｉｕｃｈｅｎｇ． Ｇｒａｎｕｌａｒｉｔｙ ｒｅｄｕｃｔ ｏｆ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｐｅｓｓｉｍｉｓｔｉｃ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ ｂａｓｅｄ ｏｎ ｇｒａｎｕｌａｒｉｔｙ ｅｎｔｒｏｐｙ ｏｆ ｌｏｗｅｒ ａｐｐｒｏｘｉｍａｔｅ ｄｉｓｔｒｉｂｕｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１６， ４３ （ ２）： ８３ － ８５，１０４． ［１３］续欣莹， 刘海涛， 谢珺， 等． 信息观下基于不一致邻域 矩阵的属性约简 ［ Ｊ］． 控制与决策， ２０１６， ３１ （ １）： １３０－１３６． ＸＵ Ｘｉｎｙｉｎｇ， ＬＩＵ Ｈａｉｔａｏ， ＸＩＥ Ｊｕｎ， ｅｔ ａｌ． Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｉｎｃｏｎｓｉｓｔｅｎｔ ｎｅｉｇｈｂｏｒｈｏｏｄ ｍａｔｒｉｘ ｕｎｄｅｒ ｉｎｆｏｒｍａｔｉｏｎ ｖｉｅｗ［Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ ｄｅｃｉｓｉｏｎ， ２０１６， ３１（１）： １３０－１３６． ［１４］胡清华，于达仁， 谢宗霞． 基于邻域粒化和粗糙逼近的 数值属性约简［Ｊ］． 软件学报， ２００８， １９（３）： ６４０－６４９． ＨＵ Ｑｉｎｇｈｕａ， ＹＵ Ｄａｒｅｎ， ＸＩＥ Ｚｏｎｇｘｉａ． Ｎｕｍｅｒｉｃａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｎｕｌａｔｉｏｎ ａｎｄ ｒｏｕｇｈ ａｐｐｒｏｘｉｍａｔｉｏｎ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２００８， １９ （ ３）： ６４０－６４９． ［ １５ ］ ＱＩＡＮ Ｙｕｈｕａ， ＬＩ Ｓｈｕｎｙｏｎｇ， ＬＩＡＮＧ Ｊｉｙｅ． Ｐｅｓｓｉｍｉｓｔｉｃ ｒｏｕｇｈ ｓｅｔ ｂａｓｅｄ ｄｅｃｉｓｉｏｎｓ： ａ ｍｕｌｔｉｇｒａｎｕｌａｔｉｏｎ ｆｕｓｉｏｎ ｓｔｒａｔｅｇｙ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１４， ２６４： １９６－２１０． ［１６］ＬＩＮ Ｇｕｏｐｉｎｇ， ＱＩＡＮ Ｙｕｈｕａ， ＬＩ Ｊｉｎｊｉｎ． Ｎｅｉｇｈｂｏｒｈｏｏｄ ｂａｓｅｄ ｍｕｌｔｉｇｒａｎｕｌａｔｉｏｎ ｒｏｕｇｈ ｓｅｔｓ ［ Ｊ ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１２， ７（５３）： １０８０－１０９３． ［１７］沈家兰， 汪小燕， 申元霞． 可变程度多粒度粗糙集［ Ｊ］． 小型微型计算机系统， ２０１６， ３７（０５）： １０１２－１０１６． ＳＨＥＮ Ｊｉａｌａｎ， ＷＡＮＧ Ｘｉａｏｙａｎ， ＳＨＥＮ Ｙｕａｎｘｉａ． Ｖａｒｉａｂｌｅ Ｇｒａｄｅ ｍｕｌｔｉ⁃ｇｒａｎｕｌａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１６， ３７（５）： １０１２－１０１６． ［１８］许韦，吴陈，杨习贝． 基于容差关系的不完备可变精度 多粒度粗糙集［ Ｊ］． 计算机应用研究， ２０１３， ３０ （ ６）： １７１２－１７１５． ＸＵ Ｗｅｉ， ＷＵ Ｃｈｅｎ， ＹＡＮＧ Ｘｉｂｅｉ． Ｉｎｃｏｍｐｌｅｔｅ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｍｕｌｔｉｇｒａｎｕｌａｒｉｔｙ ｒｏｕｇｈ ｓｅｔ ｂａｓｅｄ ｏｎ ｔｏｌｅｒａｎｃｅ ｒｅｌａｔｉｏｎ［Ｊ］． Ａｐｐｌｉｃａｔｉｏｎ ｒｅｓｅａｒｃｈ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０１３， ３０ （６）：１７１２－１７１５． ［１９］徐久成， 张灵均， 孙林， 等． 广义邻域关系下不完备混 合决策系统的约简［ Ｊ］． 计算机科学， ２０１３， ４０ （ ４）： ２４４－２４８． ＸＵ Ｊｉｕｃｈｅｎｇ， ＺＨＡＮＧ Ｌｉｎｇｊｕｎ， ＳＵＮ Ｌｉｎ， ｅｔ ａｌ． Ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｈｙｂｒｉｄ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍｓ ｂａｓｅｄ ｏｎ ｇｅｎｅｒａｌｉｚｅｄ ｎｅｉｇｈｂｏｒｈｏｏｄ ｒｅｌａｔｉｏｎｓｈｉｐ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１３， ４０（４）： ２４４－２４８． 作者简介： 王映龙，男，１９７０ 年生，教授，博士， 主要研究方向为知识发现、数据挖掘和 计算智能。 曾淇，女，１９９１ 年生， 硕士研究生， 主要研究方向为粗糙集理论与知识 发现。 钱文彬，男，１９８４ 年生，讲师，博士， 主要研究方向为粗糙集、粒计算与知识 发现。 第 ３ 期 王映龙，等：变精度下不完备邻域决策系统的属性约简算法 ·３９１·