第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201804059 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180608.1405.006html 集值信息系统的快速正域约简 陈曼如，张楠，童向荣'，岳晓冬2 (1.烟台大学数据科学与智能技术山东省高校重点实验室，山东烟台264005,2.上海大学计算机工程与科学 学院.上海200444) 摘要：针对集值信息系统正域约简算法在大规模数据集下的运行效率问题，提出一种基于启发式的集值信息 系统快速正域约简算法。通过研究属性和对象在约简过程中对算法运行效率产生的影响，在集值信息系统中 引入属性无关性和属性重要度保序性的相关定义，介绍了使得算法运行效率提升的相关定理、快速算法和应用 实例。通过实验对提出算法的有效性进行分析和验证。实验表明，提出算法的运行效率优于原始算法的运行 效率。 关键词：属性约简：粗糙集；集值信息系统：特征选择；启发式算法；正域约简：快速约简算法；粗糙近似 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)03-0471-08 中文引用格式：陈曼如，张楠，童向荣，等.集值信息系统的快速正域约简J智能系统学报，2019,14(3)：471-478. 英文引用格式：CHEN Manru,,ZHANG Nan,,TONG Xiangrong,.etal.Quick positive region reduction in set-valued information systemsJ.CAAI transactions on intelligent systems,2019,14(3):471-478. Quick positive region reduction in set-valued information systems CHEN Manru',ZHANG Nan',TONG Xiangrong',YUE Xiaodong? (1.Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes,Yantai University,Yantai 264005,China;2.School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China) Abstract:This study aims to propose a quick positive reduction algorithm based on the heuristic method to increase the efficiency of the set-valued positive reduction algorithm under large-scale data.The definitions of attribute independ- ence and attribute importance isotonicity are introduced in the set-valued information system by investigating the influ- ence of an attribute and object on the efficiency of algorithm during the reduction process,and the relevant theorem,fast algorithm,and practical example for improving the efficiency of the algorithm are introduced.Finally,the experimental results show the efficiency and effectiveness of the proposed method and its better efficiency in comparison to that of the original algorithm. Keywords:attribute reduction;rough set;set-valued information systems:feature selection:heuristic algorithm;posit- ive region reduction;quick algorithm reduction;rough approximations 粗糙集理论-(rough set theory)是分析、处理目前，粗糙集理论已经广泛应用于数据挖掘、机 不精确和不确定数据的有效工具。由于粗糙集理 器学习与模式识别等研究领域。 论中的等价关系在实际应用中局限性较大，各种 集值信息系统是重要的单值系统的扩展模 基于二元关系的扩展粗糙集模型3得以发展。 型，其中集值是用来描述不精确和缺失的信息， 收稿日期：2018-04-27.网络出版日期：2018-06-11. 集值信息系统在现实生活中的应用广泛。近年 基金项目：国家自然科学基金项目(61403329,61572418,61702439. 61572419,61502410):山东省自然科学基金项目 来，许多学者对集值系统做了深人、大量的研究 (ZR2018BA004,ZR2016FM42):烟台大学研究生科技 创新基金项目(YDZD1807). 工作。Guan等提出最大相容类的定义解决了同 通信作者：张楠.E-mail:changnan0851@l63.com. 一相容类中对象不一定两两相似的问题，并且提
DOI: 10.11992/tis.201804059 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180608.1405.006.html 集值信息系统的快速正域约简 陈曼如1 ，张楠1 ，童向荣1 ，岳晓冬2 （1. 烟台大学 数据科学与智能技术山东省高校重点实验室，山东 烟台 264005; 2. 上海大学 计算机工程与科学 学院，上海 200444） 摘 要：针对集值信息系统正域约简算法在大规模数据集下的运行效率问题，提出一种基于启发式的集值信息 系统快速正域约简算法。通过研究属性和对象在约简过程中对算法运行效率产生的影响，在集值信息系统中 引入属性无关性和属性重要度保序性的相关定义，介绍了使得算法运行效率提升的相关定理、快速算法和应用 实例。通过实验对提出算法的有效性进行分析和验证。实验表明，提出算法的运行效率优于原始算法的运行 效率。 关键词：属性约简；粗糙集；集值信息系统；特征选择；启发式算法；正域约简；快速约简算法；粗糙近似 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0471−08 中文引用格式：陈曼如, 张楠, 童向荣, 等. 集值信息系统的快速正域约简[J]. 智能系统学报, 2019, 14(3): 471–478. 英文引用格式：CHEN Manru, ZHANG Nan, TONG Xiangrong, et al. Quick positive region reduction in set-valued information systems[J]. CAAI transactions on intelligent systems, 2019, 14(3): 471–478. Quick positive region reduction in set-valued information systems CHEN Manru1 ，ZHANG Nan1 ，TONG Xiangrong1 ，YUE Xiaodong2 (1. Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes, Yantai University, Yantai 264005, China; 2. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China) Abstract: This study aims to propose a quick positive reduction algorithm based on the heuristic method to increase the efficiency of the set-valued positive reduction algorithm under large-scale data. The definitions of attribute independence and attribute importance isotonicity are introduced in the set-valued information system by investigating the influence of an attribute and object on the efficiency of algorithm during the reduction process, and the relevant theorem, fast algorithm, and practical example for improving the efficiency of the algorithm are introduced. Finally, the experimental results show the efficiency and effectiveness of the proposed method and its better efficiency in comparison to that of the original algorithm. Keywords: attribute reduction; rough set; set-valued information systems; feature selection; heuristic algorithm; positive region reduction; quick algorithm reduction; rough approximations 粗糙集理论[1-2] (rough set theory) 是分析、处理 不精确和不确定数据的有效工具。由于粗糙集理 论中的等价关系在实际应用中局限性较大，各种 基于二元关系的扩展粗糙集模型[3-8]得以发展。 目前，粗糙集理论已经广泛应用于数据挖掘、机 器学习与模式识别等研究领域。 集值信息系统是重要的单值系统的扩展模 型，其中集值是用来描述不精确和缺失的信息， 集值信息系统在现实生活中的应用广泛。近年 来，许多学者对集值系统做了深入、大量的研究 工作。Guan 等 [9]提出最大相容类的定义解决了同 一相容类中对象不一定两两相似的问题，并且提 收稿日期：2018−04−27. 网络出版日期：2018−06−11. 基金项目：国家自然科学基金项目 (61403329，61572418，61702439， 61572419， 61502410)；山东省自然科学基金项目 (ZR2018BA004，ZR2016FM42)；烟台大学研究生科技 创新基金项目 (YDZD1807). 通信作者：张楠. E-mail：zhangnan0851@163.com. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019
·472· 智能系统学报 第14卷 出A-相对约简和E-相对约简。Qian等1o提出基 表1集值决策系统 于优势关系的合取型集值序信息系统和吸取型集 Table 1 Set-valued decision systems 值序信息系统并构建了两种粗糙集模型。杨习贝 a a as as d 等在集值系统中提出模糊优势关系，考虑到了 {2} {1,2} {1} {1} {1} 对象之间的优势程度。Huang等提出概率集值 1) {1,2 {1.2} {2) {2} 信息系统和基于巴氏距离的λ-相容关系，更合理 {1} {1,2} {1} {1} {2} 2 地描述了在概率集值信息系统对象间的关系。 X4 {2} {1,2} {1,2} {2} {1} 1 Wei等基于模糊相似类和模糊相似度提出两种 Xs {1.2} 2 {1} {1} 2} 1 不同的模糊粗糙集模型。Zhang等将量化粗糙 X6 {1,2 {1} {2} {1} {2} 2 集和优势粗糙集结合，提出了一种基于大规模集 {1} {1,2} {2} {1} {1,2} 2 值信息系统的特征选择和近似推理的通用框架。 X8 {1} {1} {1,2} {2} {2}1 Skowron等l认为差别矩阵方法虽然可以求 得数据集的所有约简，但是其效率相对于启发式 定义2集值信息系统SIS=(U,AT,V,fD,HAS 算法较低，故应用性较差。由于现实生活中数据 AT,则A在U上的相容关系定义为 信息量的不断增大，集值系统中属性约简算法的 TA={x,y)eU×UNa∈A,a(x)nay≠o}. 等价关系在集值信息系统不再成立，T4满足 效率需要做进一步研究。罗川等6在集值序决策 自反性和对称性，不一定满足传递性。设T(,)为 系统中通过计算粗糙近似提出了基于增加和删除 相容类，定义Ta(x)=y∈UI(x,y)∈Ta,表示与对象 策略的增量式算法；Zhang等1m在集值系统中提 x关于相容关系TA的最大不可分辨对象集合。 出了构造关系矩阵的基本方法并且通过研究属性 U/Ta=(TA(xx∈U形成对论域的一个覆盖，其中 集变化时关系矩阵变化的性质，得到了关系矩阵 任意两个集合都可能相交。 更新的增量式方法；刘莹莹等在集值信息系统 定义3集值信息系统SIS=(U,AT,V,f),XcU, 中通过定义一种新的相似度，提出基于相似度的 ASAT,则在相容关系A下集合X的下、上近似分 启发式算法；马建敏等在集值信息系统中引入 别为A(X)={x∈UITA(x)CX)和A(X)={x∈UTA(x)n 信息量等概念，提出一种新的启发式约简算法。 X≠o}。 X的下近似是在相容关系A下确定属于X的 1基础知识 全体对象集合，而X的上近似是在相容关系A下 1.1集值信息系统相关基础知识 可能属于X的全体对象集合。 定义1集值信息系统是一个四元组SIS= 根据定义3可得：POSA(X)=A(X),BNA(X)=A(X)- (U,AT,Vf),其中：U是非空有限对象的集合，称为 A()。POS(X)称为在相容关系A下集合X的正 论域；AT是非空有限属性的集合；V。是条件属性 域，它表示在相容关系A下可以确定划分到集合 X里的对象集合；BNa(X)为在相容关系A下集合 值集合，有V=UaeAT Va;对于Va∈AT满足f(x,a)∈Va X的边界域，它表示在相容关系A下不能完全确 的集值映射为f:U×AT→2"。 定划分是否属于集合X的对象集合。 若属性集合由条件属性集合C和决策属性集 定义4集值决策系统SIS=(U,AT,Vf),A二AT, 合D组成，DnC=O,f:U×C→2为集值映射， UND(D)={D1,D2,…,Dh,则决策属性D在相容关 f:U×D→V。为单值映射，则该信息系统称为集 系A的下、上近似分别为A(D)=(x∈UID,∈U/ND(D), 值决策系统SDS=(U,CUD,V,f)。 Ta()SD}和A(D)={x∈UID,∈U/ND(D),TA(x)n 为方便起见Vo={1,2,,rl,UND(D)={D, D≠O。其中j∈(1,2，…，IU/ND(D。A(D)也称 D2,,D,其中IND(D)={(x,xx,x)∈U2,fx,D)= 为决策属性集合D在相容关系A下的正域， fx,D。UND(D)表示D在U上的划分。 A(D)=POSA(D)。 例1表1为集值决策系统SDS=(U,CUD,V,f), 1.2集值信息系统的正域约简算法 其中：U={x1,,x4,x,x6,x}为论域，C= 定义5集值决策系统SDS=(U,CUD,V,f), {a1,a2,a,a4,as}为条件属性集合，D={d为决策属 ASC,则决策属性集合D在相容关系A下的近似 性集合。 分类质量定义为
λ 出 A-相对约简和 E-相对约简。Qian 等 [10]提出基 于优势关系的合取型集值序信息系统和吸取型集 值序信息系统并构建了两种粗糙集模型。杨习贝 等 [11]在集值系统中提出模糊优势关系，考虑到了 对象之间的优势程度。Huang 等 [12]提出概率集值 信息系统和基于巴氏距离的 -相容关系，更合理 地描述了在概率集值信息系统对象间的关系。 Wei 等 [13]基于模糊相似类和模糊相似度提出两种 不同的模糊粗糙集模型。Zhang 等 [14]将量化粗糙 集和优势粗糙集结合，提出了一种基于大规模集 值信息系统的特征选择和近似推理的通用框架。 Skowron 等 [15]认为差别矩阵方法虽然可以求 得数据集的所有约简，但是其效率相对于启发式 算法较低，故应用性较差。由于现实生活中数据 信息量的不断增大，集值系统中属性约简算法的 效率需要做进一步研究。罗川等[16]在集值序决策 系统中通过计算粗糙近似提出了基于增加和删除 策略的增量式算法；Zhang 等 [17]在集值系统中提 出了构造关系矩阵的基本方法并且通过研究属性 集变化时关系矩阵变化的性质，得到了关系矩阵 更新的增量式方法；刘莹莹等[18]在集值信息系统 中通过定义一种新的相似度，提出基于相似度的 启发式算法；马建敏等[19]在集值信息系统中引入 信息量等概念，提出一种新的启发式约简算法。 1 基础知识 1.1 集值信息系统相关基础知识 (U,AT,V, f) U Va V = ∪a∈ATVa ∀a ∈ AT f(x,a) ∈ Va f : U ×AT → 2 V 定义 1 集值信息系统是一个四元组 SIS = ，其中： 是非空有限对象的集合，称为 论域；AT 是非空有限属性的集合； 是条件属性 值集合，有 ；对于 满足 的集值映射为 。 C D∩C = Ø f : U ×C → 2 VC f : U × D → VD SDS = (U,C ∪ D,V, f) 若属性集合由条件属性集合 和决策属性集 合 D 组成， ， 为集值映射， 为单值映射，则该信息系统称为集 值决策系统 。 VD = {1,2,···,r} U/IND(D) = {D1, D2,···,Dr} IND(D) = {(xi , xj)|(xi , xj) ∈ U 2 , f(xi ,D) = f(xj ,D)} U/IND(D) 为方便起见 ， ，其中 。 表示 D 在 U 上的划分。 SDS = (U,C ∪ D,V, f) U ={x1, x2, x3, x4, x5, x6, x7, x8} {a1,a2,a3,a4,a5} D = {d} 例 1 表 1 为集值决策系统 ， 其中： 为论域， C = 为条件属性集合， 为决策属 性集合。 表 1 集值决策系统 Table 1 Set-valued decision systems U a1 a2 a3 a4 a5 d x1 {2} {1, 2} {1} {1} {1} 1 x2 {1} {1, 2} {1, 2} {2} {2} 1 x3 {1} {1, 2} {1} {1} {2} 2 x4 {2} {1, 2} {1, 2} {2} {1} 1 x5 {1, 2} {2} {1} {1} {2} 1 x6 {1, 2} {1} {2} {1} {2} 2 x7 {1} {1, 2} {2} {1} {1, 2} 2 x8 {1} {1} {1, 2} {2} {2} 1 定义 2 集值信息系统 SIS = (U,AT,V, f)，∀A ⊆ AT，则 A 在 U 上的相容关系定义为 TA = {(x, y) ∈ U ×U|∀a ∈ A,a(x)∩a(y) , ∅}。 TA TA(x) TA(x) = {y ∈ U|(x, y) ∈ TA} x TA U/TA = {TA(x)|x ∈ U} 等价关系在集值信息系统不再成立， 满足 自反性和对称性，不一定满足传递性。设 为 相容类，定义 ，表示与对象 关于相容关系 的最大不可分辨对象集合。 形成对论域的一个覆盖，其中 任意两个集合都可能相交。 SIS = (U,AT,V, f) X ⊆ U A ⊆ ATA(X) = {x ∈ U|TA(x) ⊆ X} A(X) = {x ∈ U|TA(x)∩ X , ∅} 定义 3 集值信息系统 ， ， ，则在相容关系 A 下集合 X 的下、上近似分 别为 和 。 X 的下近似是在相容关系 A 下确定属于 X 的 全体对象集合，而 X 的上近似是在相容关系 A 下 可能属于 X 的全体对象集合。 POSA(X) = A(X),BNA(X) = A(X)− A(X) POSA(X) BNA(X) 根据定义3可得： 。 称为在相容关系 A 下集合 X 的正 域，它表示在相容关系 A 下可以确定划分到集合 X 里的对象集合； 为在相容关系 A 下集合 X 的边界域，它表示在相容关系 A 下不能完全确 定划分是否属于集合 X 的对象集合。 SIS = (U,AT,V, f) A ⊆ AT U/IND(D) = {D1,D2,··· ,Dr} A(D) = {x ∈ U|Dj ∈ U/IND(D), TA(x) ⊆ Dj} A(D) = {x ∈ U|Dj ∈ U/IND(D),TA(x)∩ Dj , ∅} j ∈ {1,2,··· ,|U/IND(D)|} A(D) A(D) = POSA(D) 定义 4 集值决策系统 ， ， ，则决策属性 D 在相容关 系A的下、上近似分别为 和 。其中 。 也称 为决策属性集合 D 在相容关系 A 下的正域， 。 1.2 集值信息系统的正域约简算法 SDS = (U,C ∪ D,V, f) A ⊆ C 定义 5 集值决策系统 ， ，则决策属性集合 D 在相容关系 A 下的近似 分类质量定义为 ·472· 智 能 系 统 学 报 第 14 卷
第3期 陈曼如，等：集值信息系统的快速正域约简 ·473· Ya(D)= POSA(D) (1) 5)返回R。 IU升 由算法1可得，在3)迭代的过程中，每次选 近似分类质量刻画了在相容关系A下可以正 取一个属性重要度最大的属性加入到R中，在这 确划分到决策属性集合D的对象集合数与论域 个过程中需要不断地计算整个论域上的正域，从 个数的比重。 而使得算法计算量非常大，效率不够理想，很难 定义6集值决策系统SDS=(U,CUD,Vf), 应用在大规模数据集下。 A≤C,则集合A是集值决策系统的一个正区域保 例2表1为集值决策系统SDS=(U,CUD,V,fD, 持属性约简当且仅当以下两个条件成立： 其中，U={1,x2,x3,x4x,6,7,xs}为论域，C={a1,2, 1)Ya(D)=Yc(D); a3,a4,as}为条件属性集合，D={d为决策属性集合。 2)VBCA,YB(D)0,则a属于集值决策 系统SDS的核属性。 Qian等222提出了正向近似的加速原理。本 根据文献[20]给出集值信息系统下经典正域 节在文献[21-22]算法的基础上介绍集值信息系统 属性约简算法(positive region reduction algorithm, 下的正域属性约简算法的加速原理以及相关性 PRRA),见算法1。 质，给出了算法的伪代码描述和两个算法的时间 算法1PRRA 复杂度对比与分析。 输入集值决策系统SDS=(U,CUD,VfD: 定理1集值决策系统SDS=(U,CUD,Vf,设 输出集值决策系统SDS的一个属性约简R。 属性子集P、Q满足PcOcC,则POS(D)CPOSo(D). 1)R=0。 该定理表明，如果两个属性集合存在包含关 2)计算Sigimner(a,C,C,D,U),i∈{1,2，…，lC,如 系，则这两个属性集合相对于决策属性D的正域 果Sigm(a,C,C,D,U)>0,则将a:存入R中。 也存在包含关系。证略。 3)若y(D)=yc(D),则终止；否则对条件属性 定理2集值决策系统SDS=(U,CUD,Vf), C-R进行如下操作： 条件属性集合C={a1,a2,…,agl,属性集合P,= 计算Sigouer(ao,R,C,D,U)=max{Sigu(a,C,D,R, {a1,a2,…,a},i=1,2,…,lC1,则定义： U)},R←RU{aol,其中a∈C-R。若有多个最大 POSP (U,D)=POSE,(U,D)UPOSP (U+1,D) 值，则选择与R组合数最少的属性。 式中：U1=U,U41=U-POSn(U,D) 4)对R中的每个条件属性a进行如下操作： 定理3集值决策系统SDS=(U,CUD,Vf), ①计算yR-iai(D): A,BCC,若U/TA=UIT则POSA(U,D)=POSs(U,D ②若yR-a1(D)=yc(D),则a;为冗余属性，R=R-{ah 证明设U/Ta={X1,X2,…Xh,U/Ta={Y,Y2,… 否则a为非冗余属性，R保持不变。 Y山，如果U/T4=U/T,则X=Y,i=1,2,…,U八，那
γA(D) = |POSA(D)| |U| (1) D 近似分类质量刻画了在相容关系 A 下可以正 确划分到决策属性集合 的对象集合数与论域 个数的比重。 SDS = (U,C ∪ D,V, f) A ⊆ C 定义 6 集值决策系统 ， ，则集合 A 是集值决策系统的一个正区域保 持属性约简当且仅当以下两个条件成立： 1) γA(D) = γC(D) ； 2) ∀B ⊂ A，γB(D) 0 a SDS 对于给定集值决策系统 ， ，若 ，则 属于集值决策 系统 的核属性。 根据文献[20]给出集值信息系统下经典正域 属性约简算法 (positive region reduction algorithm， PRRA)，见算法 1。 算法 1 PRRA 输入 集值决策系统 SDS = (U,C ∪ D,V, f) ； 输出 集值决策系统 SDS 的一个属性约简 R。 1) R = ∅。 Siginner(ai ,C,C,D,U) i ∈ {1,2,··· ,|C|} Siginner(ai ,C,C,D,U) > 0 ai 2) 计算 ， ，如 果 ，则将 存入 R 中。 γR(D) = γC(D) C −R 3) 若 ，则终止；否则对条件属性 进行如下操作： Sigouter(a0,R,C,D,U) = max{Sigouter(ak ,C,D,R, R ← R∪ {a0} ak ∈ C −R 计算 U)}， ，其中 。若有多个最大 值，则选择与 R 组合数最少的属性。 4) 对 R 中的每个条件属性 ai进行如下操作： ①计算 γR−{ai}(D) ； γR−{ai}(D)=γC(D) ai R=R−{ai} ai ②若 ，则 为冗余属性， ， 否则 为非冗余属性，R 保持不变。 5) 返回 R。 由算法 1 可得，在 3) 迭代的过程中，每次选 取一个属性重要度最大的属性加入到 R 中，在这 个过程中需要不断地计算整个论域上的正域，从 而使得算法计算量非常大，效率不够理想，很难 应用在大规模数据集下。 SDS=(U,C ∪ D,V, f) U = {x1, x2, x3, x4, x5, x6, x7, x8} C = {a1,a2, a3,a4,a5} D = {d} 例 2 表 1 为集值决策系统 ， 其中， 为论域， 为条件属性集合， 为决策属性集合。 采用 PRRA 算法对表 1 约简过程如下。 R = {a3,a4} γC(D) = 0.625 1) 表 1 中经求其核属性集为 ，决策 属性 D 相对于条件属性 C 的近似分类质量为 ； 2) 对 C −R 中每个条件属性重复进行如下操作： C −R Sigouter(a1,R,C,D,U) = 0.125 Sigouter(a2,R,C,D,U) = Sigouter(a3,R,C,D,U) = 0.125 根据定义 8 计算 中属性的重要度，其 中， ， 0， 。 a1 a3 (a1,R,C,D,U) = Sigouter(a3,R,C,D,U) = a1 a1 R = R∪ {a1} ={a1,a3,a4} γR(D) = γC(D) = 0.625 由于属性 和属性 的外部属性重要度 Sigouter 0.125， 故选择与 R 组合数最少的属性 。根据算法 1 中 步骤 3) 将 加入 R 中，得 ， 且 ，终止步骤 3)。 γR−{a1 }(D) , γC(D) 3) 去除集合 R 中的冗余属性，由于 ，故集合 R 中无冗余属性，算法终止。 故算法 PRRA 得到约简， R = {a1,a3,a4}。 2 集值系统的快速正域约简 Qian 等 [21-22]提出了正向近似的加速原理。本 节在文献[21-22]算法的基础上介绍集值信息系统 下的正域属性约简算法的加速原理以及相关性 质，给出了算法的伪代码描述和两个算法的时间 复杂度对比与分析。 SDS = (U,C ∪ D,V, f) P Q P ⊂ Q ⊆ C POSP(D) ⊆ POSQ(D)。 定理 1 集值决策系统 ，设 属性子集 、 满足 ，则 该定理表明，如果两个属性集合存在包含关 系，则这两个属性集合相对于决策属性 D 的正域 也存在包含关系。证略。 SDS = (U,C ∪ D,V, f) C = {a1,a2,··· ,a|C|} Pi = {a1,a2,··· ,ai} i = 1,2,··· ,|C| 定理 2 集值决策系统 ， 条件属性集合 ，属性集合 ， ，则定义： POSPi+1 (U,D) = POSPi (U,D)∪POSPi+1 (Ui+1 ,D)。 U1 = U Ui+1 = U −POSPi 式中： ， (U,D)。 SDS = (U,C ∪ D,V, f) A,B ⊆ C U/TA = U/TB POSA(U,D) = POSB(U,D) 定理 3 集值决策系统 ， ，若 ，则 。 U/TA ={X1,X2,···,X|U|} U/TB={Y1,Y2,···, Y|U|} U/TA = U/TB Xi = Yi i = 1,2,··· ,|U| 证明 设 ， ，如果 ，则 ， ，那 第 3 期 陈曼如，等：集值信息系统的快速正域约简 ·473·
·474· 智能系统学报 第14卷 么POSA(U,D)=POSs(UD),证毕。 定理2表明，计算属性重要度时由于删除正 定理4集值决策系统SDS=(U,CUD,V,f), 域和冗余属性集合后属性重要度保持不变，这样 AcC,Ya∈C-A,如果U/TA=U/TAua,那么POSA(U,D)= 在计算属性约简时，每次迭代过程中可以删除候 POPOSAUte(U,D),则属性a为冗余属性。 选集合产生的正域和冗余属性集合，使得算法效 证明设U/TA={X1,X,…,Xl,UTAu4={Y, 率提升。 Y,,Yl,因为U/TA=U/Taa,即POSA(U,D)= 算法2 QPRRA POSAUla(U,D),因此对于任意beC-A-{a,有POSAu 输入集值决策系统SDS=(U,CUD,VfD: (U,D)=POSAUIbUta(U,D)。所以a是约简过程中的 输出集值决策系统SDS的一个属性约简R。 冗余属性，可以被删除。证毕。 1)令i=1,R1=R,U1=U,C1=C,Ca=o,R=o。 定理5集值决策系统SDS=(U,CUD,Vf), 2)对条件属性C,-R进行如下操作：计算 ASC,如果Va,b∈C-A-A,并且Sigouter(a,A,C,D,U- Sig uer(do.R.Ci.D,U)=maxSigue(a,R.Ci,D.U),R Sigoer(b,A,C,D,U≥0，那么Sigouer(a,A,C',D,U)- RU{ao,其中a∈C:-R。若有多个最大值，则选择 Sigouer(b,A,C',D,U≥0。其中，属性集合C'=C-A, 与R组合数最少的属性。 A'=(clPOS (U,D)=POSGute (U.D),cEC-A),U=U- 3)计算U+1=U,-POS(UD)。 POS(U,D)。 证明根据定义Sigouter(a,A,C,D,U)=yAua(D)- 4)计算C={a∈C,-R:U/TR=U/Tual,C41= Ya(D),要度仅取决于ya(D)=POSA(D/IU。由于U= C-C4,令i=i+l。 U-POS(U,D),所以POS(U,D)=o,POS ute(U, 5)若yR(D)=y(D),转到6)，否则转到2)。 D)=POSuta(U,D)-POS(U,D)。又因为C'nA'=O, 可)对C-R中的每个条件属性a,进行如下操作： AcC',故POS(U,D)=POS(U,D)。因此 ①计算yR-a(D)方 Sig(a.A.C.D.U)D)-c(D) ②若yR-a(D)=yc(D),则a为冗余属性，R= Siger(d.A.CD.U)(D-(D) R-{al,否则a为非冗余属性，R保持不变。 IPOSSuta(U.D)-IPOS(U.D) )返回R。 IUI POS UL(U.D)-IPOS (U.D) 在算法2中，候选属性集合的正域随着每轮 IU-I IPOSSUta(U,D)I-IPOS(U,D)I 迭代过程选择属性重要度最大的属性加入而增 IUI POS UL(U,D)I-IPOS(U,D) 大，因此在计算正域时，可以通过叠加的方式计 IUPOSSuta(U,D)I-IPOSS(U.D)I IU 算，无需重新直接计算新的D关于约简属性集合 IUI POSSuta (U,D)I-IPOS(U.D)IUI 的正域，证略。 因为1U/IU≥0，若Sigouter(a,A,C,D,U)≥Sigouer(b, 算法2原理流程如图1所示。集值信息系统 A,C,D,U),Sigoue(a,A,C',D,U)Sigouer(b,A,C',D, 的快速正域约简算法(quick positive region reduc- U)。证毕。 tion algorithm,QPRRA). 评估 候选属性 选取合适属性加入 集合 计算属性 候选属性集合 去正域 去元余 满足终止条件 输出 重要度 属性 图1算法2原理流程 Fig.1 Flow chart for algorithm 2 算法2无需首先求出核属性，直接迭代选择集规模缩小，算法效率提升。在图1中，A对应算 属性重要度最大的属性加入候选属性集合，因此 法步骤2)，计算当前轮次需评估的属性重要度， 对于无核的数据集算法效率提升。在约简过程 B对应算法步骤3)，删除当前轮次的正域，C对应 中，根据属性重要度的保序性，即定理5，算法在 算法步骤4)，删除当前轮次的冗余属性集合。 每轮迭代过程中删除正域和冗余属性，使得数据 下面比较分析PRRA算法和QPRRA算法的
么 POSA(U,D) = POSB(U,D) ，证毕。 SDS = (U,C ∪ D,V, f) A⊆C ∀a∈C−A U/TA=U/TA∪{a} POSA(U,D)= POPOSA∪{a}(U,D) 定理 4 集值决策系统 ， ， ，如果 ，那么 ，则属性 a 为冗余属性。 U/TA = {X1,X2,···,X|U|} U/TA∪{a} = {Y1, Y2,···,Y|U|} U/TA = U/TA∪{a} POSA(U,D) = POSA∪{a}(U,D) b ∈ C − A− {a} POSA∪{b} (U,D) = POSA∪{b}∪{a}(U,D) a 证明 设 ， ，因为 ， 即 ，因此对于任意 ，有 。所以 是约简过程中的 冗余属性，可以被删除。证毕。 SDS = (U,C ∪ D,V, f) A ⊆ C ∀a,b ∈ C − A− A ′ Sigouter(a,A,C,D,U)− Sigouter(b,A,C,D,U) ⩾ 0 Sigouter(a,A,C ′ ,D,U ∗ )− Sigouter(b,A,C ′ ,D,U ∗ ) ⩾ 0 C ′ = C − A ′ A ′ = {c|POSC A (U,D) = POSC A∪{c} (U,D), c ∈ C − A} U ∗ = U− POSC A (U,D) 定理 5 集值决策系统 ， ，如果 ，并且 ，那么 。其中，属性集合 ， ， 。 Sigouter(a,A,C,D,U) = γA∪{a}(D)− γA(D) γA(D) = |POSA(D)|/|U| U −POSC A (U,D) POSC A (U ∗ ,D) = ∅ POSC A∪{a} (U ∗ , D) = POSC A∪{a} (U,D)−POSC A (U,D) C ′∩A ′ =∅ A ⊂ C ′ POSC ′ A (U ∗ ,D) = POSC A (U ∗ ,D) 证明 根据定义 ，要度仅取决于 。由于 U * = ，所以 ， 。又因为 ， ，故 。因此 Sigouter(a,A,C,D,U) Sigouter(a,A,C′ ,D,U∗ ) = γ (C,U) A∪{a} (D)−γ (C,U) A (D) γ (C′ ,U∗ ) A∪{a} (D)−γ (C′ ,U∗ ) A (D) = |U ∗ | |U| |POSC A∪{a} (U,D)| − |POSC A (U,D)| |POSC′ A∪{a} (U∗ ,D)| − |POSC′ A (U∗ ,D)| = |U ∗ | |U| |POSC A∪{a} (U,D)| − |POSC A (U,D)| |POSC A∪{a} (U∗ ,D)| − |POSC A (U∗ ,D)| = |U ∗ | |U| |POSC A∪{a} (U,D)| − |POSC A (U,D)| |POSC A∪{a} (U,D)| − |POSC A (U,D)| = |U ∗ | |U| |U ∗ |/|U|⩾0 Sigouter(a,A,C,D,U)⩾Sigouter(b, A,C,D,U) Sigouter(a,A,C ′ ,D,U ∗ ) ⩾ Sigouter(b,A,C ′ ,D, U ∗ ) 因为 ，若 ，则 。证毕。 定理 2 表明，计算属性重要度时由于删除正 域和冗余属性集合后属性重要度保持不变，这样 在计算属性约简时，每次迭代过程中可以删除候 选集合产生的正域和冗余属性集合，使得算法效 率提升。 算法 2 QPRRA 输入 集值决策系统 SDS = (U,C ∪ D,V, f) ； 输出 集值决策系统 SDS 的一个属性约简 R。 1) 令 i = 1，R1 = R，U1 = U，C1 = C，Cd = ∅，R = ∅。 Ci −R Sigouter(a0,R,Ci ,D,Ui)=max{Sigouter(ak ,R,Ci ,D,Ui)} R ← R∪ {a0} ak ∈ Ci −R 2) 对条件属性 进行如下操作：计算 ， ，其中 。若有多个最大值，则选择 与 R 组合数最少的属性。 Ui+1 = Ui −POSCi R (Ui 3) 计算 ,D)。 C Ui d = {a ∈ Ci −R : U/TR = U/TR∪{a}} Ci+1 = Ci −C Ui d i = i+1 4) 计算 ， ，令 。 γ Ui R (D) = γ Ui Ci 5) 若 (D) ，转到 6)，否则转到 2)。 6) 对 C −R 中的每个条件属性 ak，进行如下操作： ①计算 γR−{ak }(D) ； γR−{ak }(D) = γC(D) ak R− {ak} ak ②若 ，则 为冗余属性，R = ，否则 为非冗余属性，R 保持不变。 7) 返回 R。 在算法 2 中，候选属性集合的正域随着每轮 迭代过程选择属性重要度最大的属性加入而增 大，因此在计算正域时，可以通过叠加的方式计 算，无需重新直接计算新的 D 关于约简属性集合 的正域，证略。 算法 2 原理流程如图 1 所示。集值信息系统 的快速正域约简算法 (quick positive region reduction algorithm，QPRRA)。 候选属性 集合 选取合适属性加入 候选属性集合 Y N 满足终止条件 评估 A B C 输出 去冗余 属性 计算属性 重要度 去正域 图 1 算法 2 原理流程 Fig. 1 Flow chart for algorithm 2 算法 2 无需首先求出核属性，直接迭代选择 属性重要度最大的属性加入候选属性集合，因此 对于无核的数据集算法效率提升。在约简过程 中，根据属性重要度的保序性，即定理 5，算法在 每轮迭代过程中删除正域和冗余属性，使得数据 集规模缩小，算法效率提升。在图 1 中，A 对应算 法步骤 2)，计算当前轮次需评估的属性重要度， B 对应算法步骤 3)，删除当前轮次的正域，C 对应 算法步骤 4)，删除当前轮次的冗余属性集合。 下面比较分析 PRRA 算法和 QPRRA 算法的 ·474· 智 能 系 统 学 报 第 14 卷
第3期 陈曼如，等：集值信息系统的快速正域约简 ·475· 时间复杂度。令T,和T2分别为PRRA算法和 去除R中的冗余属性，由于yR-ai(D)≠yc(D), QPRRA算法的时间复杂度。令IC=m表示数据 i=1,3,4,故R中无冗余属性，算法终止。故算法 集条件属性数，U川=n表示数据集对象数，1Cl=m QPRRA得到约简，即R={a1,a,a4}o 表示第i轮需评估的属性数（已删除第i-1轮所 求冗余属性数)，U=n,为第i轮剩余的对象数。 3实验分析 在算法2中，计算去掉正区域并且删除冗余属性 为了证明提出算法的有效性，实验选取了 集合将最大属性重要度的属性加入到当前约简的 6组UCI标准数据库(http://archive.ics.uci.edu/m- 时间复杂度为02m-i+1n,去冗余过程时间 )中的数据集，为了得到集值数据集对这6组数 复杂度为O(m2n)。而在算法1中，计算核属性的 据集进行预处理，在条件属性集上随机对10%的 时间复杂度为Om2),计算最大属性重要度的属 数据进行对应属性上的并集操作，如表2所示。 性加入到当前约简的时间复杂度为0(m-i+1)2m)。 表2数据集描述 Table 2 Description of data sets 去冗余过程时间复杂度为O(m2m)。PRRA算法时 间复杂度为T1=Om2n+Σm-i+1)2m),QPRRA 编号 数据集 对象数特征数类别数 1 Flag 194 8 算法时间复杂度为T2=0(m2n+∑(m:-i+1)2)。 2 Lung Cancer 32 57 QPRRA算法效率优于PRRA算法。 3 Molecular Biology 106 58 2 例3表1为集值决策系统SDS=(U,CUD, 4 Dermatology 366 35 6 V,f),其中，U={x,x,3,x4,x,x6,x,xg}为论域，C= {a1,a2,a3,a4,as}为条件属性集合，D={d为决策属 5 SCADI 70 206 7 性集合。 6 QSAR Biodegradation 1055 42 9 采用QPRRA算法对表1进行3轮约简。 所有实验在PC机上进行，操作系统为Mi- 第1轮迭代过程：计算C1-R中属性的重要 crosoft Windows7(64b,处理器及其型号为Inter Core 度，分别为Sigouter(a1R,C1,D,U1)=0,Sigu(a2,R,C, i5-2450M,内存为4GB,所有算法均使用MAT- D,U)=0,Sigoer(a3,R,C1,D.U)=0,Sigouer(d.R.C1. LAB7.11.0(R2010b)编写实现。在实验中，分别用 D,Ui)=0.375,Sigouer(a5,R,C1,D,U1)=0。由于Sigouter 上述2种约简算法对6组UCI数据集进行处理， (a,R,C1,D,U)=0.375最大，故R=RU{a4}={aa}, 比较它们约简所耗费的时间。实验中，将上述 U2=U-POSG(U1.D)=x1.X3XsX6 C2 =C1-C= 6组数据集分别分为10等份，用来记录两个算法 a1,a2,a,a4,as,无冗余属性，且y0(D)≠y(D),继 的时间差异。例如，假设数据集有1000个对象， 续循环。 第1号数据集用来表示1~100个对象，第2号数 第2轮迭代过程：计算C2-R中属性的重要 据集用来表示1~200个对象，以此类推，第10号 度，分别为Sigouer(a1R,C1,D,U2)=0,Sigouer(a2,R,C1, 数据集用来表示1~1000个对象。实验一共分为 D.U2)=0,Sigouer(a3.R.C1,D.U2)=0.4,Sigouer(as,R.C1. 3个部分。第1部分为算法PRRA、算法QPRRA、 D,U2)=0。由于Sigoue(a3,R,C1,D,U2)=0.4最大，故 基于相似度的集值信息系统属性约简算法] R=RUla3]=(a3,al.U3=U2-POSG(U2,D)=(x1.Xxsh, (SRA)和基于信息量的集值信息系统属性约简算 C3=C2-C出={a1,a2,a,ash,无冗余属性。且yR(D)≠ 法1(IRA)的约简结果长度和计算时间的比较。 Y哈(D),继续循环。 第2部分为算法PRRA、QPRRA、SRA和IRA随 第3轮迭代过程：计算C,-R中属性的重要 着论域的增大算法计算时间变化的实验。第3部 度，分别为Sigouer(a1,R,C1,D,U3)=0.33,Sigouter(a2,R,C1, 分为数据集Lung Cancer迭代过程中对象和属性 D,U3)=0,Sigouter((as,R,C1,D,U3)=0.33。由于Siguter 的变化。 (a1,R,C1,D,U3)=Sigouer(a,R,C1,D,U3)=0.33,故选择 表2给出了6组数据集的对象数、特征数和 与R组合数最少的属性1。故R=RU{a1}={a1, 类别数的对比，从表中可以看出，本文选取了不 a3,a4},U4=U3-POS(U3,D)={x3,xsl,C4=C3-C4= 同规模的数据集，最大规模数据集为QSAR Bio-- {a1,asl,删除冗余属性a2。且y(D)=y公(D),终止 degradation,对象数有1044个，最小规模数据集 循环。 为Lung Cancer,.对象数有32个，最大特征数数据
T1 T2 |C| = m |U| = n |Ci | = mi i−1 |Ui | = ni O( ∑ |C| i=1 (mi −i+1)2 ni) O(m 2n) O(m 2n) O( ∑ |C| i=1 (m−i+1)2n) O(m 2n) T1 = O(m 2n+ ∑ |C| i=1 (m−i+1)2n) T2 = O(m 2n+ ∑ |C| i=1 (mi −i+1)2 ni) 时间复杂度。令 和 分别为 PRRA 算法和 QPRRA 算法的时间复杂度。令 表示数据 集条件属性数， 表示数据集对象数， 表示第 i 轮需评估的属性数 (已删除第 轮所 求冗余属性数)， 为第 i 轮剩余的对象数。 在算法 2 中，计算去掉正区域并且删除冗余属性 集合将最大属性重要度的属性加入到当前约简的 时间复杂度为 ，去冗余过程时间 复杂度为 。而在算法 1 中，计算核属性的 时间复杂度为 ，计算最大属性重要度的属 性加入到当前约简的时间复杂度为 。 去冗余过程时间复杂度为 。PRRA 算法时 间复杂度为 ， QPRRA 算法时间复杂度为 。 QPRRA 算法效率优于 PRRA 算法。 SDS = (U,C ∪ D, U = {x1, x2, x3, x4, x5, x6, x7, x8} {a1,a2,a3,a4,a5} D = {d} 例 3 表 1 为集值决策系统 V, f )，其中， 为论域，C = 为条件属性集合， 为决策属 性集合。 采用 QPRRA 算法对表 1 进行 3 轮约简。 C1 −R Sigouter(a1,R,C1,D,U1) = 0 Sigouter(a2,R,C1, D,U1) = 0 Sigouter(a3, R,C1,D,U1)=0 Sigouter(a4,R,C1, D,U1) = 0.375 Sigouter(a5,R,C1,D,U1) = 0 Sigouter (a4,R,C1,D,U1) = 0.375 R∪ {a4} = {a4} U2 = U1 −POSC1 R (U1,D)= {x1, x3, x5,x6,x7} C2 = C1 −C U1 d = {a1,a2,a3,a4,a5} γ U1 R (D) ,γ U1 C1 (D) 第 1 轮迭代过程：计算 中属性的重要 度，分别为 ， ， ， ， 。由于 最大，故 R = ， ， ，无冗余属性，且 ，继 续循环。 C2 −R Sigouter(a1,R,C1,D,U2) = 0 Sigouter(a2,R,C1, D,U2) = 0 Sigouter(a3,R,C1,D,U2) = 0.4 Sigouter(a5,R,C1, D,U2) = 0 Sigouter(a3,R,C1,D,U2) = 0.4 R =R∪ {a3}={a3,a4},U3 =U2−POSC2 R (U2,D)= {x1, x3, x5}, C3 =C2−C U2 d = {a1,a2,a3,a5} γ U2 R (D) , γ U2 C2 (D) 第 2 轮迭代过程：计算 中属性的重要 度，分别为 ， ， ， 。由于 最大，故 ，无冗余属性。且 ，继续循环。 C3 −R Sigouter(a1,R,C1,D,U3)=0.33 Sigouter(a2,R,C1, D,U3)=0 Sigouter(a5,R,C1,D,U3) = 0.33 (a1,R,C1,D,U3) =Sigouter(a5,R,C1,D,U3) = 0.33 R a1 R = R∪ {a1} = {a1, a3,a4} U4 = U3−POSC3 R (U3,D)= {x3, x5} C4 = C3 −C U3 d = {a1,a5} a2 γ U3 R (D) = γ U3 C3 (D) 第 3 轮迭代过程：计算 中属性的重要 度，分别为 ， ， 。由于 Sigouter ，故选择 与 组合数最少的属性 。故 ， ， ，删除冗余属性 。且 ，终止 循环。 γR−{ai}(D) , γC(D) i = 1,3,4 R = {a1,a3,a4} 去除 R 中的冗余属性，由于 ， ，故 R 中无冗余属性，算法终止。故算法 QPRRA 得到约简，即 。 3 实验分析 为了证明提出算法的有效性，实验选取了 6 组 UCI 标准数据库 (http://archive.ics.uci.edu/ml/) 中的数据集，为了得到集值数据集对这 6 组数 据集进行预处理，在条件属性集上随机对 10% 的 数据进行对应属性上的并集操作，如表 2 所示。 所有实验在 PC 机上进行，操作系统为 Microsoft Windows 7(64 b)，处理器及其型号为 Inter Core i5-2450M，内存为 4 GB，所有算法均使用 MATLAB7.11.0(R2010b) 编写实现。在实验中，分别用 上述 2 种约简算法对 6 组 UCI 数据集进行处理， 比较它们约简所耗费的时间。实验中，将上述 6 组数据集分别分为 10 等份，用来记录两个算法 的时间差异。例如，假设数据集有 1 000 个对象， 第 1 号数据集用来表示 1~100 个对象，第 2 号数 据集用来表示 1~200 个对象，以此类推，第 10 号 数据集用来表示 1~1 000 个对象。实验一共分为 3 个部分。第 1 部分为算法 PRRA、算法 QPRRA、 基于相似度的集值信息系统属性约简算法[ 1 8 ] (SRA) 和基于信息量的集值信息系统属性约简算 法 [19] (IRA) 的约简结果长度和计算时间的比较。 第 2 部分为算法 PRRA、QPRRA、SRA 和 IRA 随 着论域的增大算法计算时间变化的实验。第 3 部 分为数据集 Lung Cancer 迭代过程中对象和属性 的变化。 表 2 给出了 6 组数据集的对象数、特征数和 类别数的对比，从表中可以看出，本文选取了不 同规模的数据集，最大规模数据集为 QSAR Biodegradation，对象数有 1 044 个，最小规模数据集 为 Lung Cancer，对象数有 32 个，最大特征数数据 表 2 数据集描述 Table 2 Description of data sets 编号 数据集 对象数 特征数 类别数 1 Flag 194 29 8 2 Lung Cancer 32 57 2 3 Molecular Biology 106 58 2 4 Dermatology 366 35 6 5 SCADI 70 206 7 6 QSAR Biodegradation 1 055 42 9 第 3 期 陈曼如，等：集值信息系统的快速正域约简 ·475·
·476· 智能系统学报 第14卷 集SCADI,.特征数有206个，而Flag的特征数为 法PRRA、QPRRA、IRA和SRA的计算时间和选 29个，在数据集中为特征数最少的。6组数据集 择特征数的对比，可以看出，算法QPRRA 有不同的类别数，最大类别数数据集QSAR Bio- 和PRRA约简结果长度优于算法SRA和IRA,算 degrada-tion,类别数为9，数据集Lung Cancer和 法OPRRA效率明显优于算法PRRA和IRA。图2 Molecular Biology类别数最小为2。表3给出了算 为4种算法的实验对比。 表3算法PRRA和QPRRA的计算时间和约简结果 Table 3 Time regurired and attribute reduction of the algorithms PRRA IRA SRA OPRRA 数据集 原始特征 约简 时间s 约简 时间/s 约简 时间s 约简 时间s Flag 29 11 130.7 13 102.5 14 36.8 11 30.1 Lung Cancer 57 8 37.9 12 37.5 12 10.9 8 5.2 Molecular Biology 58 6 74.6 个 66.2 > 14.8 6 11.4 Dermatology 35 13 263.4 17 251.4 17 139.2 12 80.8 SCADI 206 19 4315.0 26 8446.9 27 569.2 19 422.1 QSAR Biodegradation 42 15 7731.3 22 6730.4 24 1259.6 15 1266.8 从图2和表3可以看出，算法QPRRA效率优 算法求核的时间，并且在每轮迭代过程中，不仅 于其他3个算法效率，在数据集QSAR Biodegra 删除了当前轮次候选属性集合产生的正域，也删 dation上，算法SRA略优于算法QPRRA。例如， 除了当前轮次产生的冗余属性集合，使得数据集 对于数据集Lung Cancer,.算法PRRA时间耗费为 规模不断变小，算法运行时间缩短。从表4可得， 37.9s.算法QPRRA时间耗费为5.2s,加速比达到 Lung Cancer数据集核为空，在每轮迭代过程中删 了72，实验效果明显。因为对于核为空的数据集 除了正域和冗余属性，使得数据集规模缩小，算 而言，QPRRA算法无需计算核属性集合，节省了 法效率提升。 140 40 -QPRRA -QPRRA 120 -A-PRRA 35 A-PRRA +SRA 100 30 SRA 令-IRA 25 合IRA 80 20 60 15 40 10 20 5 4 6 4 6 10 论域大小 论域大小 (a)Flag (b)Lung Cancer 0 300 70 -e-QPRRA -0OPRRA APRRA 250 A-PRRA 60 +SRA SRA 合-IRA 200 令-RA 兰40 兰150 100 10 50 4 6 4 6 8 10 论域大小 论域大小 (c)Molecular Biology (d)Dermatology
集 SCADI，特征数有 206 个，而 Flag 的特征数为 29 个，在数据集中为特征数最少的。6 组数据集 有不同的类别数，最大类别数数据集 QSAR Biodegrada-tion，类别数为 9，数据集 Lung Cancer 和 Molecular Biology 类别数最小为 2。表 3 给出了算 法 PRRA、QPRRA、IRA 和 SRA 的计算时间和选 择特征数的对比，可以看出，算 法 QPRRA 和 PRRA 约简结果长度优于算法 SRA 和 IRA，算 法 QPRRA 效率明显优于算法 PRRA 和 IRA。图 2 为 4 种算法的实验对比。 表 3 算法 PRRA 和 QPRRA 的计算时间和约简结果 Table 3 Time regurired and attribute reduction of the algorithms 数据集 原始特征 PRRA IRA SRA QPRRA 约简 时间/s 约简 时间/s 约简 时间/s 约简 时间/s Flag 29 11 130.7 13 102.5 14 36.8 11 30.1 Lung Cancer 57 8 37.9 12 37.5 12 10.9 8 5.2 Molecular Biology 58 6 74.6 7 66.2 7 14.8 6 11.4 Dermatology 35 13 263.4 17 251.4 17 139.2 12 80.8 SCADI 206 19 4 315.0 26 8 446.9 27 569.2 19 422.1 QSAR Biodegradation 42 15 7 731.3 22 6 730.4 24 1 259.6 15 1 266.8 从图 2 和表 3 可以看出，算法 QPRRA 效率优 于其他 3 个算法效率，在数据集 QSAR Biodegra dation 上，算法 SRA 略优于算法 QPRRA。例如， 对于数据集 Lung Cancer，算法 PRRA 时间耗费为 37.9 s，算法 QPRRA 时间耗费为 5.2 s，加速比达到 了 7.2，实验效果明显。因为对于核为空的数据集 而言，QPRRA 算法无需计算核属性集合，节省了 算法求核的时间，并且在每轮迭代过程中，不仅 删除了当前轮次候选属性集合产生的正域，也删 除了当前轮次产生的冗余属性集合，使得数据集 规模不断变小，算法运行时间缩短。从表 4 可得， Lung Cancer 数据集核为空，在每轮迭代过程中删 除了正域和冗余属性，使得数据集规模缩小，算 法效率提升。 0 2 4 6 8 10 20 40 60 80 100 120 140 论域大小 t/s QPRRA PRRA SRA IRA (a) Flag 0 2 4 6 8 10 5 10 15 20 25 30 35 40 论域大小 t/s QPRRA PRRA SRA IRA (b) Lung Cancer 0 2 4 6 8 10 10 20 30 40 50 60 70 80 论域大小 t/s QPRRA PRRA SRA IRA (c) Molecular Biology 0 2 4 6 8 10 50 100 150 200 250 300 论域大小 t/s QPRRA PRRA SRA IRA (d) Dermatology ·476· 智 能 系 统 学 报 第 14 卷
第3期 陈曼如，等：集值信息系统的快速正域约简 ·477· 支10 -OPRRA -QPRRA A-PRRA 5 A-PRRA -SRA -IRA 6 SRA -RA 3 的￥ 4 6 8 10 0 6 8 10 论域大小 论域大小 (e)SCADI (f)QSAR Biodegradation 图2算法PRRA和算法OPRRA计算时间 Fig.2 Time reguired for PRRA and QPRRA versus the data size 表4算法PRRA和QPRRA在Lung Cancer数据集上每 参考文献： 轮迭代对象和属性的变化 Table 4 Changes of the number of objects and attributes [1]PAWLAK Z.Rough sets[J].International journal of com- within each loop of algorithms PRRA and QPRRA puter and information sciences,1982,11(5):341-356. on Lung Cancer [2]王国胤，姚一豫，于洪.粗糙集理论与应用研究综述 PRRA QPRRA 计算机学报，2009,32(7)：1229-1246 迭代次数 对象数 属性数 对象数 属性数 WANG Guoyin,YAO Yiyu,YU Hong.A survey on rough 32 55 29 55 set theory and applications[J].Chinese journal of com- 2 32 54 25 54 puters,.2009,32(7)1229-1246. 3 32 53 22 53 [3]MIAO Duogian.ZHAO Yan,YAO Yiyu,et al.Relative re- 少 ducts in consistent and inconsistent decision tables of the 4 32 52 18 Pawlak rough set model[J].Information sciences,2009, 51 14 47 179(24):4140-4150. 6 32 50 > 2 [4]LI Hua,LI Deyu,ZHAI Yanhui,et al.A novel attribute re- 7 32 49 4 25 duction approach for multi-label data based on rough set 8 32 48 2 12 theory[J].Information sciences,2016,367/368:827-847. [5]YAO Yiyu,ZHAO Yan.Attribute reduction in decision- 4结束语 theoretic rough set models[J].Information sciences,2008. 178(17):3356-3373. 本文提出了一种在集值信息系统下的正域属 [6]JIA Xiuyi,SHANG Lin,ZHOU Bin,et al.Generalized at- 性保持约简快速算法，算法无需计算核属性集 tribute reduct in rough set theory[J.Knowledge-based sys- 合，直接开始迭代选择属性重要度最大的属性加 tems,2016,91:204-218. 入候选属性集合，每轮迭代过程中删除一部分正 [7]张楠，苗夺谦，岳晓冬，区间值信息系统的知识约简 域，使得数据集对象数不断减少，算法效率提升， 计算机研究与发展，2010,47(8：1362-1371 在删除一部分正域的同时，删除冗余的属性集 ZHANG Nan,MIAO Duoqian,YUE Xiaodong.Ap- 合，使得算法的效率进一步提升。实验选取6组 proaches to knowledge reduction in interval-valued in- UCI数据集对提出算法的有效性进行验证，实验 formation systems[J].Journal of computer research and de- velopment,.2010,47(8):1362-1371 表明：提出算法的效率优于经典算法效率，实现 [8]HU Qinghua,ZHAO Hui,XIE Zongxia,et al.Consistency 了对经典算法的优化，尤其是在无核数据集上加 based attribute reduction[C]//Advances in Knowledge Dis- 速效果明显，因为省去了计算核属性集的时间， covery and Data Mining.Berlin,Heidelberg,Germany, 这使得该算法能更好地应用于较大规模数据的处 2007:96-107. 理。本文是基于删除正域和冗余属性机制基础上 [9]GUAN Yanyong,WANG Hongkai.Set-valued informa- 进行的研究，对每次迭代过程中产生正域和冗余 tion systems[J].Information sciences,2006,176(17): 属性较少的数据集加速效果不够明显，故提出算 2507-2525 法的普遍适用性是未来研究方向之一。 [10]QIAN Yuhua,DANG Chuanyin,LIANG Jiye,et al.Set-
表 4 算法 PRRA 和 QPRRA 在 Lung Cancer 数据集上每 轮迭代对象和属性的变化 Table 4 Changes of the number of objects and attributes within each loop of algorithms PRRA and QPRRA on Lung Cancer 迭代次数 PRRA QPRRA 对象数 属性数 对象数 属性数 1 32 55 29 55 2 32 54 25 54 3 32 53 22 53 4 32 52 18 52 5 32 51 14 47 6 32 50 7 42 7 32 49 4 25 8 32 48 2 12 4 结束语 本文提出了一种在集值信息系统下的正域属 性保持约简快速算法，算法无需计算核属性集 合，直接开始迭代选择属性重要度最大的属性加 入候选属性集合，每轮迭代过程中删除一部分正 域，使得数据集对象数不断减少，算法效率提升， 在删除一部分正域的同时，删除冗余的属性集 合，使得算法的效率进一步提升。实验选取 6 组 UCI 数据集对提出算法的有效性进行验证，实验 表明：提出算法的效率优于经典算法效率，实现 了对经典算法的优化，尤其是在无核数据集上加 速效果明显，因为省去了计算核属性集的时间， 这使得该算法能更好地应用于较大规模数据的处 理。本文是基于删除正域和冗余属性机制基础上 进行的研究，对每次迭代过程中产生正域和冗余 属性较少的数据集加速效果不够明显，故提出算 法的普遍适用性是未来研究方向之一。 参考文献： PAWLAK Z. Rough sets[J]. International journal of computer and information sciences, 1982, 11(5): 341–356. [1] 王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[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. [2] 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. [3] LI Hua, LI Deyu, ZHAI Yanhui, et al. A novel attribute reduction approach for multi-label data based on rough set theory[J]. Information sciences, 2016, 367/368: 827–847. [4] YAO Yiyu, ZHAO Yan. Attribute reduction in decisiontheoretic rough set models[J]. Information sciences, 2008, 178(17): 3356–3373. [5] JIA Xiuyi, SHANG Lin, ZHOU Bin, et al. Generalized attribute reduct in rough set theory[J]. Knowledge-based systems, 2016, 91: 204–218. [6] 张楠, 苗夺谦, 岳晓冬. 区间值信息系统的知识约简[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. [7] HU Qinghua, ZHAO Hui, XIE Zongxia, et al. Consistency based attribute reduction[C]//Advances in Knowledge Discovery and Data Mining. Berlin, Heidelberg, Germany, 2007: 96–107. [8] GUAN Yanyong, WANG Hongkai. Set-valued information systems[J]. Information sciences, 2006, 176(17): 2507–2525. [9] [10] QIAN Yuhua, DANG Chuanyin, LIANG Jiye, et al. Set- 0 2 4 6 8 10 1 2 3 4 5 6 论域大小 t/s QPRRA PRRA SRA IRA (e) SCADI 0 2 4 6 8 10 1 2 3 4 5 6 7 8 论域大小 t/s QPRRA PRRA SRA IRA (f) QSAR Biodegradation ×103 ×103 图 2 算法 PRRA 和算法 QPRRA 计算时间 Fig. 2 Time reguired for PRRA and QPRRA versus the data size 第 3 期 陈曼如，等：集值信息系统的快速正域约简 ·477·
·478· 智能系统学报 第14卷 valued ordered information systems[J].Information sci- MA Jianmin,ZHANG Wenxiu.Information quantity- ences,.2009,179(16):2809-2832 based attribute reduction in set-valued information sys- [11]杨习贝，张再跃，张明.集值信息系统中的模糊优势关 tems[J].Fuzzy systems and mathematics,2013,27(2): 系粗糙集[).计算机科学，2011,38(2)：234-237. 177-182 YANG Xibei,ZHANG Zaiyue,ZHANG Ming.Fuzzy [20]苗夺谦，李道国.粗糙集理论、算法与应用[M.北京：清 dominance-based rough set in set-valued information sys- 华大学出版社，2008」 tem[J].Computer science,2011,38(2):234-237. [21]QIAN Yuhua,LIANG Jiye,PEDRYCZ W.et al.Positive [12]HUANG Yanyong,LI Tianrui,LUO Chuan,et al.Dy- approximation:an accelerator for attribute reduction in namic variable precision rough set approach for probabil- rough set theory[J].Artificial intelligence,2010,174(9/10): istic set-valued information systems[J].Knowledge-based 597-618. systems.2017,122:131-147. [22]钱宇华，梁吉业，王锋.面向非完备决策表的正向近似 [13]WEI Wei,CUI Junbiao,LIANG Jiye,et al.Fuzzy rough 特征选择加速算法[J.计算机学报，2011,34(3)： approximations for set-valued data[J].Information sci- 435-442. ences,2016.360:181-201. [14]ZHANG Hongying,YANG Shuyun.Feature selection QIAN Yuhua,LIANG Jiye,WANG Feng.A positive-ap- proximation based accelerated algorithm to feature selec- and approximate reasoning of large-scale set-valued de- tion from incomplete decision tables[].Chinese journal cision tables based on a-dominance-based quantitative rough sets[J].Information sciences,2017,378:328-347. of computers,2011,34(3):435-442. [15]SKOWRON A.RAUSZER C.The discernibility matrices 作者简介： and functions in information systems[Cl//Intelligent De- 陈曼如，女，1993年生，硕士研究 cision Support Theory and Decision Library.Dordrecht, 生，主要研究方向为粗糙集、数据挖掘 Netherlands,1992:331-362 与机器学习。 [16]LUO Chuan,LI Tianrui,CHEN Hongmei,et al.Fast al- gorithms for computing rough approximations in set-val- ued decision systems while updating criteria values[J].In- formation sciences,2015,299:221-242. [17]ZHANG Junbo,LI Tianrui,RUAN Da,et al.Rough sets 张楠.男，1979年生，博士研究 based matrix approaches with dynamic attribute variation 生，主要研究方向为粗糙集、认知信息 in set-valued information systems[J].International journ- 学与人工智能。 al of approximate reasoning,2012,53(4):620-635. [18]刘莹莹，吕跃进.基于相似度的集值信息系统属性约简 算法[】.南京大学学报（自然科学版），2015,51(2)： 384389 LIU Yingying,LYU Yuejin.Attribute reduction in set- 童向荣，男，1975年生.教授，主 要研究方向为多Agent系统、分布式 valued information system based on similarity[J].Journal 人工智能与数据挖掘技术。发表学术 of Nanjing university(natural sciences),2015,51(2): 论文50余篇，被SCI检索2篇、EI检 384389 索20余篇。 [19]马建敏，张文修.基于信息量的集值信息系统的属性约 简.模糊系统与数学，2013,272)：177-182
valued ordered information systems[J]. Information sciences, 2009, 179(16): 2809–2832. 杨习贝, 张再跃, 张明. 集值信息系统中的模糊优势关 系粗糙集[J]. 计算机科学, 2011, 38(2): 234–237. YANG Xibei, ZHANG Zaiyue, ZHANG Ming. Fuzzy dominance-based rough set in set-valued information system[J]. Computer science, 2011, 38(2): 234–237. [11] HUANG Yanyong, LI Tianrui, LUO Chuan, et al. Dynamic variable precision rough set approach for probabilistic set-valued information systems[J]. Knowledge-based systems, 2017, 122: 131–147. [12] WEI Wei, CUI Junbiao, LIANG Jiye, et al. Fuzzy rough approximations for set-valued data[J]. Information sciences, 2016, 360: 181–201. [13] ZHANG Hongying, YANG Shuyun. Feature selection and approximate reasoning of large-scale set-valued decision tables based on α-dominance-based quantitative rough sets[J]. Information sciences, 2017, 378: 328–347. [14] SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[C]//Intelligent Decision Support Theory and Decision Library. Dordrecht, Netherlands, 1992: 331–362. [15] LUO Chuan, LI Tianrui, CHEN Hongmei, et al. Fast algorithms for computing rough approximations in set-valued decision systems while updating criteria values[J]. Information sciences, 2015, 299: 221–242. [16] ZHANG Junbo, LI Tianrui, RUAN Da, et al. Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems[J]. International journal of approximate reasoning, 2012, 53(4): 620–635. [17] 刘莹莹, 吕跃进. 基于相似度的集值信息系统属性约简 算法[J]. 南京大学学报 (自然科学版), 2015, 51(2): 384–389. LIU Yingying, LYU Yuejin. Attribute reduction in setvalued information system based on similarity[J]. Journal of Nanjing university (natural sciences), 2015, 51(2): 384–389. [18] 马建敏, 张文修. 基于信息量的集值信息系统的属性约 简[J]. 模糊系统与数学, 2013, 27(2): 177–182. [19] MA Jianmin, ZHANG Wenxiu. Information quantitybased attribute reduction in set-valued information systems[J]. Fuzzy systems and mathematics, 2013, 27(2): 177–182. 苗夺谦, 李道国. 粗糙集理论、算法与应用[M]. 北京: 清 华大学出版社, 2008. [20] 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. [21] 钱宇华, 梁吉业, 王锋. 面向非完备决策表的正向近似 特征选择加速算法[J]. 计算机学报, 2011, 34(3): 435–442. QIAN Yuhua, LIANG Jiye, WANG Feng. A positive-approximation based accelerated algorithm to feature selection from incomplete decision tables[J]. Chinese journal of computers, 2011, 34(3): 435–442. [22] 作者简介： 陈曼如，女，1993 年生，硕士研究 生，主要研究方向为粗糙集、数据挖掘 与机器学习。 张楠，男，1979 年生，博士研究 生，主要研究方向为粗糙集、认知信息 学与人工智能。 童向荣，男，1975 年生，教授，主 要研究方向为多 Agent 系统、分布式 人工智能与数据挖掘技术。发表学术 论文 50 余篇，被 SCI 检索 2 篇、EI 检 索 20 余篇。 ·478· 智 能 系 统 学 报 第 14 卷