第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201706080 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180404.1544.014.html 重要度集成的属性约简方法研究 李京政'，杨习贝2，窦慧莉，王平心，陈向坚 (1.江苏科技大学计算机学院，江苏镇江212003；2.南京理工大学经济管理学院，江苏南京210094,3.江苏科技大 学数理学院.江苏镇江212003) 摘要：启发式算法在求解约简的过程中逐步加入重要度最高的属性，但其忽视了数据扰动将会直接引起重要度计 算的波动问题，从而造成约简结果的不稳定。鉴于此，提出了一种基于集成属性重要度的启发式算法框架。首先，在 原始数据上进行多重采样：然后，在每次循环过程中分别计算各个采样结果上的属性重要度并对这些重要度进行集 成：最后，将集成重要度最大的属性加入到约简中去。利用邻域粗糙集方法进行的实验结果表明，基于集成重要度的 属性约简算法不仅能够获取更加稳定的约简，而且利用所生成的约简能够得到一致性较高的分类结果。 关键词：属性约简；分类；聚类；数据扰动：集成：启发式算法；邻域粗糙集；稳定性 中图分类号：TP391文献标志码：A文章编号：1673-4785(2018)03-0414-08 中文引用格式：李京政，杨习贝，窦慧莉，等.重要度集成的属性约简方法研究.智能系统学报，2018,133：414421. 英文引用格式：LI Jingzheng,YANG Xibei,,DOU Huili,etal.Research on ensemble significance based attribute reduction ap- proach[J].CAAI transactions on intelligent systems,2018,13(3):414-421. Research on ensemble significance based attribute reduction approach LI Jingzheng',YANG Xibei2,DOU Huili,WANG Pingxin,CHEN Xiangjian' (1.School of Computer,Jiangsu University of Science and Technology,Zhenjiang 212003,China;2.School of Economics and Man- agement,Nanjing University of Science and Technology,Nanjing 210094,China;3.School of Mathematics and Physics,Jiangsu University of Science and Technology,Zhenjiang 212003,China) Abstract:In the process of computing reduct using a heuristic algorithm,the attribute with the highest importance is gradually added in.However,this approach neglects the fluctuation of important calculations which is directly caused by data perturbation.Notably,such fluctuation may lead to an unstable reduct result.To eliminate such an anomaly,a framework consisting of a heuristic algorithm based on the importance of the ensemble attribute was proposed.In this approach,firstly,multiple sampling is executed for raw data;secondly,in each cycle,the importance of each attribute is computed on the basis of each sampling and the importance indices are integrated;finally,the attribute with the highest importance is added into the reduct.The experimental results obtained by utilizing the neighborhood rough set method show that the new approach not only obtains a more stable reduct,but also attains the classification results with high uni- formity. Keywords:attribute reduction;classification;clustering;data perturbation;ensemble;heuristic algorithm;neighbor- hood rough set;stability 作为粗糙集理论1研究的核心内容，属性约 所得到的性能或达到与其基本相当的性能。近年 简问题一直是众多学者关心的焦点。所谓属性 来，根据不同的需求目标以及不同类型的拓展粗糙 约简，是在给定某一度量标准的前提下，期望利用 集模型5，众多研究者提出了诸如信息嫡9、决策代 较少的属性，能够超越利用原始数据中所有的属性 价10山、分类刻画2等类型的度量标准作为属性约 简的定义。这些不同类型的属性约简大体上可以被 收稿日期：2017-06-24.网络出版日期：2018-04-04。 基金项目：国家自然科学基金项目(61572242,61503160.61502211)： 划分为两大类：1)面向粗糙集不确定性度量的 江苏省高校哲学社会科学基金项目(2015SJD769):中国 博士后科学基金项目(2014M550293). 属性约简：2)面向粗糙集学习性能的属性约简。 通信作者：杨习贝.E-mail:zhenjiangyangxibei@163.com. 为了从数据中获取约简，在粗糙集领域的研究
DOI: 10.11992/tis.201706080 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180404.1544.014.html 重要度集成的属性约简方法研究 李京政1 ，杨习贝1,2，窦慧莉1 ，王平心3 ，陈向坚1 （1. 江苏科技大学 计算机学院, 江苏 镇江 212003; 2. 南京理工大学 经济管理学院, 江苏 南京 210094; 3. 江苏科技大 学 数理学院, 江苏 镇江 212003） 摘 要：启发式算法在求解约简的过程中逐步加入重要度最高的属性，但其忽视了数据扰动将会直接引起重要度计 算的波动问题，从而造成约简结果的不稳定。鉴于此，提出了一种基于集成属性重要度的启发式算法框架。首先，在 原始数据上进行多重采样；然后，在每次循环过程中分别计算各个采样结果上的属性重要度并对这些重要度进行集 成；最后，将集成重要度最大的属性加入到约简中去。利用邻域粗糙集方法进行的实验结果表明，基于集成重要度的 属性约简算法不仅能够获取更加稳定的约简，而且利用所生成的约简能够得到一致性较高的分类结果。 关键词：属性约简；分类；聚类；数据扰动；集成；启发式算法；邻域粗糙集；稳定性 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2018)03−0414−08 中文引用格式：李京政, 杨习贝, 窦慧莉, 等. 重要度集成的属性约简方法研究[J]. 智能系统学报, 2018, 13(3): 414–421. 英文引用格式：LI Jingzheng, YANG Xibei, DOU Huili, et al. Research on ensemble significance based attribute reduction approach[J]. CAAI transactions on intelligent systems, 2018, 13(3): 414–421. Research on ensemble significance based attribute reduction approach LI Jingzheng1 ，YANG Xibei1,2 ，DOU Huili1 ，WANG Pingxin3 ，CHEN Xiangjian1 (1. School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212003, China; 2. School of Economics and Management, Nanjing University of Science and Technology, Nanjing 210094, China; 3. School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang 212003, China) Abstract: In the process of computing reduct using a heuristic algorithm, the attribute with the highest importance is gradually added in. However, this approach neglects the fluctuation of important calculations which is directly caused by data perturbation. Notably, such fluctuation may lead to an unstable reduct result. To eliminate such an anomaly, a framework consisting of a heuristic algorithm based on the importance of the ensemble attribute was proposed. In this approach, firstly, multiple sampling is executed for raw data; secondly, in each cycle, the importance of each attribute is computed on the basis of each sampling and the importance indices are integrated; finally, the attribute with the highest importance is added into the reduct. The experimental results obtained by utilizing the neighborhood rough set method show that the new approach not only obtains a more stable reduct, but also attains the classification results with high uniformity. Keywords: attribute reduction; classification; clustering; data perturbation; ensemble; heuristic algorithm; neighborhood rough set; stability 作为粗糙集理论[1-2]研究的核心内容，属性约 简 [3-4]问题一直是众多学者关心的焦点。所谓属性 约简，是在给定某一度量标准的前提下，期望利用 较少的属性，能够超越利用原始数据中所有的属性 所得到的性能或达到与其基本相当的性能。近年 来，根据不同的需求目标以及不同类型的拓展粗糙 集模型[5-8] ，众多研究者提出了诸如信息熵[9] 、决策代 价 [10-11] 、分类刻画[12]等类型的度量标准作为属性约 简的定义。这些不同类型的属性约简大体上可以被 划分为两大类[13-14] ：1) 面向粗糙集不确定性度量的 属性约简；2) 面向粗糙集学习性能的属性约简。 为了从数据中获取约简，在粗糙集领域的研究 收稿日期：2017−06−24. 网络出版日期：2018−04−04. 基金项目：国家自然科学基金项目 (61572242，61503160，61502211)； 江苏省高校哲学社会科学基金项目 (2015SJD769)；中国 博士后科学基金项目 (2014M550293). 通信作者：杨习贝. E-mail：zhenjiangyangxibei@163.com. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018
第3期 李京政，等：重要度集成的属性约简方法研究 ·415· 中有两大类方法：穷举法与启发式方法。分辨矩阵 以得到所有决策类的合集形如X1,X2,…,X}。VBCAT, 与回溯策略是穷举法的典型算法，虽然穷举法可以 D关于B的下近似和上近似分别定义为 帮助我们得到所有的约简，但由于其计算复杂度过 (3) 高，并不适用于现实世界中的大规模数据处理。启 发式算法是借助贪心的搜索策略求得数据中的一个 约简，虽然启发式算法有可能陷入局部最优，仅能 ND=Nsx, (4) =1 得到超约简，但因其速度优势依然得到了广大研究 对于任一决策类X有 学者的认可。 NsX:={x∈U6s(x)≤X (5) 在启发式约简求解过程中，属性重要度扮演着 NaX:={∈U16s(x)nX≠O} (6) 重要的角色，在向约简集合不断增加属性的过程 定义2给定一个决策系统DS,YBAT,D相 中，每次都加入重要度最大的属性，直至满足所定 对于对B的依赖度为 义的约简标准。但不难发现属性重要度的计算都是 INDI Y(B.D)= 基于计算所有样本的基础上，这会带来两个问题： IUI (7) 1)每次计算都需要扫描所有样本，时间消耗过大； 式中WD与U分别表示集合ND与U的基数。 2)未考虑数据扰动带来的属性重要度变化问题。 显然0≤B,D)≤1成立。(B,D)表示属于条件 虽然王熙照等已经提出了利用边界样本求解属性 属性B的基础上，某种决策类的样本占总体样本的 重要度的方法，这一思想可以进一步降低启发式约 比例。若NsD越大，则依赖度越高。 简求解的时间消耗6，但他们没有考虑数据扰动问 题。微小的数据扰动有可能会使约简的结果大相径 2属性约简 庭，这不仅表明约简本身不具备稳定性，而且也会 2.1属性重要度与启发式算法 致使根据约简所得到的分类及预测等结果也呈现不 定义3给定一决策系统DS,VBCAT,B被称 稳定性。针对上述问题，笔者期望利用启发式算法， 为-个约简当组仅当y(B,D)=y(AT,D)且B'CB.y(B,D)≠ 求得具有较高稳定性的约简。借助集成学习1的 Y(AT,D 基本思想，可以设计一种集成属性重要度的计算方 定义3所示的约简是一个能够保持决策系统中 法，对由不同边界样本所得到的属性重要度进行集 依赖度不发生变化的最小属性子集。根据定义2所 成，其目的是使属性重要度的输出更为鲁棒。 示的依赖度，可以进一步考察属性的重要度。 给定一个决策系统DS,VBCAT,且对于任意的 1 邻域粗糙集 a∈AT-B,如果y(BU{a,D)=yB,D),那么就表明属 在粗糙集理论中，一个决策系统可以表示为二 性a对于计算依赖度没有带来任何贡献，a是冗余 元组DS=(U,ATUD),其中U是一个非空有限的对 的；如果y(BU{a,D)>y(B,D),那么就表示加入属性 象集合，即论域；AT是所有条件属性集合；D是所 α后可以提高依赖度，从而降低不确定性程度。根 有快策属性的合集且AT∩D=O。 据这样的分析，可以构建如式（⑧）所示的属性重要度： 给定论域U={1,,…,x,邻域是建立在某一 Sig(a,B,D)=y(BUal,D)-y(B,D) (8) 种度量标准上，通过给定半径考察样本的邻居。不 根据上述属性重要度，算法1构建了一个启发 妨假设M=(C)an为论域上的相似度矩阵，r表示对 式求解过程，其目标是获得以式(8)所示重要度为 象x,与x,之间的距离度量，给定半径6∈[0,1]， 依据的属性排序序列。 1x,∈U,x,的邻域区间为 算法1启发式算法 n)=+6x(）（ 输入邻域决策系统DS=(U,ATUD)。 机千有 输出属性排序sCq。 式中：，min表示样本x中与样本x,距离的最小 1j浅m,j料 1)seq←-0，seq,D)=0: 值表示样本y中与样本x,距离的最大 2)若AT-seq=0,则转至5)，否则转至3)： 值。采用邻域区间的方式考察样本的邻居可以避免 3)Va,∈AT-seqi 因半径过小而产生空邻域的情形。借助邻域区间， 4)选择a,满足Sig(a,seq,D)戶max{Sig(a,seq, x,∈U,其邻域为 D):Ha,∈AT-seq},令seq=seqU{a},返回2)，计算 (x)={x∈Ux+x,r≤Int(x)} (2) Sig(a,seq,D); 定义19201给定一个决策系统DS,根据D可 5)输出seq
中有两大类方法：穷举法与启发式方法。分辨矩阵 与回溯策略是穷举法的典型算法，虽然穷举法可以 帮助我们得到所有的约简，但由于其计算复杂度过 高，并不适用于现实世界中的大规模数据处理。启 发式算法是借助贪心的搜索策略求得数据中的一个 约简，虽然启发式算法有可能陷入局部最优，仅能 得到超约简，但因其速度优势依然得到了广大研究 学者的认可。 在启发式约简求解过程中，属性重要度扮演着 重要的角色，在向约简集合不断增加属性的过程 中，每次都加入重要度最大的属性，直至满足所定 义的约简标准。但不难发现属性重要度的计算都是 基于计算所有样本的基础上，这会带来两个问题： 1) 每次计算都需要扫描所有样本，时间消耗过大； 2) 未考虑数据扰动带来的属性重要度变化问题。 虽然王熙照等[15]已经提出了利用边界样本求解属性 重要度的方法，这一思想可以进一步降低启发式约 简求解的时间消耗[16] ，但他们没有考虑数据扰动问 题。微小的数据扰动有可能会使约简的结果大相径 庭，这不仅表明约简本身不具备稳定性，而且也会 致使根据约简所得到的分类及预测等结果也呈现不 稳定性。针对上述问题，笔者期望利用启发式算法， 求得具有较高稳定性的约简。借助集成学习[17-18]的 基本思想，可以设计一种集成属性重要度的计算方 法，对由不同边界样本所得到的属性重要度进行集 成，其目的是使属性重要度的输出更为鲁棒。 1 邻域粗糙集 DS = ⟨U,AT∪ D⟩ 在粗糙集理论中，一个决策系统可以表示为二 元组 ，其中 U 是一个非空有限的对 象集合，即论域；AT 是所有条件属性集合；D 是所 有决策属性的合集且 AT∩D=Ø。 U = {x1, x2,··· , xn} M = (ri j)n×n ∀ 给定论域 ，邻域是建立在某一 种度量标准上，通过给定半径考察样本的邻居。不 妨假设 为论域上的相似度矩阵，rij 表示对 象 xi 与 xj 之间的距离度量，给定半径 δ∈[0, 1]， xi∈U，xi 的邻域区间为 Int(xi) = min 1⩽j⩽n, j,i ri j +δ×( max 1⩽j⩽n, j,i ri j − min 1⩽j⩽n, j,i ri j) (1) min 1⩽j⩽n, j,i ri j max 1⩽j⩽n, j,i ri j ∀ 式中： 表示样本 xj 中与样本 xi 距离的最小 值， 表示样本 xj 中与样本 xi 距离的最大 值。采用邻域区间的方式考察样本的邻居可以避免 因半径过小而产生空邻域的情形。借助邻域区间， xi∈U，其邻域为 δ(xi) = {xi ∈ U|xj , xi ,ri j ⩽ Int(xi)} (2) 定义 1 [19-20] 给定一个决策系统 DS，根据 D 可 以得到所有决策类的合集形如 {X1,X2,··· ,Xn}。∀ B ⊆ AT， D 关于 B 的下近似和上近似分别定义为 NBD = ∪N i=1 NBXi (3) NBD = ∪N i=1 NBXi (4) 对于任一决策类 Xi 有 NBXi = {xi ∈ U|δB(xi) ⊆ Xi} (5) NBXi = {xi ∈ U|δB(xi)∩ Xi , Ø} (6) 定义 2 给定一个决策系统 DS，∀ B ⊆ AT，D 相 对于对 B 的依赖度为 γ(B,D) = |NBD| |U| (7) 式中|NBD|与|U|分别表示集合 NBD 与 U 的基数。 NBD 显然 0≤γ(B, D)≤1 成立。γ(B, D) 表示属于条件 属性 B 的基础上，某种决策类的样本占总体样本的 比例。若 越大，则依赖度越高。 2 属性约简 2.1 属性重要度与启发式算法 ∀ ⊆ γ(B,D)=γ(AT,D) ∀B ′ ⊆B γ(B ′ ,D), γ(AT,D) 定义 3 给定一决策系统 DS， B AT，B 被称 为一个约简当且仅当 且 ， 。 定义 3 所示的约简是一个能够保持决策系统中 依赖度不发生变化的最小属性子集。根据定义 2 所 示的依赖度，可以进一步考察属性的重要度。 ∀ ⊆ γ(B∪ {a},D) = γ(B,D) γ(B∪ {a},D) > γ(B,D) 给定一个决策系统 DS， B AT，且对于任意的 a∈AT–B，如果 ，那么就表明属 性 a 对于计算依赖度没有带来任何贡献，a 是冗余 的；如果 ，那么就表示加入属性 a 后可以提高依赖度，从而降低不确定性程度。根 据这样的分析，可以构建如式 (8) 所示的属性重要度： Sig(a,B,D) = γ(B∪ {a},D)−γ(B,D) (8) 根据上述属性重要度，算法 1 构建了一个启发 式求解过程，其目标是获得以式 (8) 所示重要度为 依据的属性排序序列。 算法 1 启发式算法 输入 邻域决策系统 DS = ⟨U,AT∪ D⟩。 输出 属性排序 seq。 1) seq←Ø，γ(seq, D)=0； 2) 若 AT–seq = Ø，则转至 5)，否则转至 3)； 3) ∀ ai∈AT–seq; ∀ 4) 选择 aj，满足 Sig(aj , seq, D)=max{Sig(ai , seq, D): ai∈AT–seq}，令 seq=seq∪{aj}，返回 2),计算 Sig(ai , seq, D)； 5) 输出 seq。 第 3 期 李京政，等：重要度集成的属性约简方法研究 ·415·
·416· 智能系统学报 第13卷 2.2集成属性重要度 4)for r=Itok 算法1在迭代过程中，求解属性重要度是利用 Ya,∈AT-seq,计算属性a,在决策系统DS,上 全体样本所得到的依赖度差异，如式(8)。但这种重 的重要度Sig(a。ATD): 要度计算方法忽视了数据扰动对重要度计算产生的 end for 影响，当样本集发生变化时，属性重要度势必也会 5)Ya,∈AT-seq,融合属性a,在各个决策系统 发生相应的变化，从而导致约简变化。如何降低样 上的重要度： 本集变化所引起的约简变化程度，其本质是期望所 求约简应尽可能稳定、鲁棒，因此需要重新考察属 sig.(dAT.D) 性重要度的计算方法。 Sig(ai,AT,D)= 从分类学习的角度来看，不同样本对学习性能 6)选择a,满足Sig(a,seq,D)Fmax{Sig(a,seq, 的贡献程度是不相同的。一般来说，那些对于学习性 D:Ya,∈AT-seq},令seq=seqU{a,返▣3)： 能影响比较重要的样本大都分布在边界区域上s。 7)输出seq。 从这一考虑出发，可以将边界区域的样本挑选出 在邻域粗糙集上求解属性重要度的时间复杂度 来，作为计算属性重要度的依据。一个可行且直观 为O(U×n),其中U表示论域中对象个数，n代表条 的办法是采用聚类算法对原始样本集进行聚类，在 件属性个数，算法1的时间复杂度为O(UP×n)。k 各类簇中挑选出距离类簇中心较远的样本，将这些 means聚类的时间复杂度为O(NxTxU),N为类簇个 样本组合成一个新的决策系统，这实际上是一个采 数，T为迭代次数。算法3的时间消耗为k×N×T×U+ 样的过程（具体描述如算法2所示）。又因为传统的 k×[U×m,其中[U刀是一个不确定集，表示每次k 聚类算法，如k-means聚类的结果并不稳定，其初始 means聚类采样的对象个数，聚类次数k为常数，故 类簇中心是随机选取的，故可以在原始样本集上通 算法3的时间复杂度为O([U×n)。通过大量实验 过多次聚类后得到多个决策系统，分别在这多个决 表明[U)<U,所以在聚类次数较少的前提下，算法 策系统上求得各个属性的重要度并进行融合，最后 3的时间消耗一般小于算法1。 选择融合重要度较高的属性，其具体描述如算法 3实验分析 3所示。 算法2基于k-means聚类的采样 为了验证所提算法的有效性，本文从UCI数据 输入邻域决策系统DS=(U,ATUD)。 集中选择了9组数据，数据的基本描述如表1所 输出采样后的决策系统DS'。 示。实验中取k=5,即进行5次聚类采样，由算法 1)U'=0; 3得到的属性序列不仅和传统的启发式算法比较， 2)利用k-means聚类获得U上的类簇C= 而且和王熙照等1提出的基于样例选取的求解属 C,C2,…,Cw,其中N为决策类的个数： 性重要度算法对比分析。 3)for j=1 to N 表1实验数据的基本信息 ①计算类簇C中每个样本到类簇中心的平均 Table 1 Data sets description 距离d: 数据集 ②将C,中到类簇中心的距离大于平均距离 数据集名称 样本数属性数决策类数 编号 d的样本挑选出来加人U'; Dermatology 366 35 6 end for Diabetic Retinopathy 2 1151 20 4)输出DS'。 Debrecen 算法3重要度集成的启发式算法 2 Ecoli 336 8 输入邻域决策系统DS=(U,ATUD),采样次 Ionosphere 351 35 数k 5 Iris 150 输出属性排序seq。 Parkinson Multiple 1)seq-0,y(seq,D)0; 6 1208 27 Sound Recordings 2)for r=1to k 7 Pima Indians Diabetes 768 9 2 利用算法2进行采样得到决策系统DS: Tic-Tac-Toe Endgame 958 9 2 end for 9 Yeast 1484 9 10 3)若AT-seq=0,则转至7)，否则转至4)：
2.2 集成属性重要度 算法 1 在迭代过程中，求解属性重要度是利用 全体样本所得到的依赖度差异，如式 (8)。但这种重 要度计算方法忽视了数据扰动对重要度计算产生的 影响，当样本集发生变化时，属性重要度势必也会 发生相应的变化，从而导致约简变化。如何降低样 本集变化所引起的约简变化程度，其本质是期望所 求约简应尽可能稳定、鲁棒，因此需要重新考察属 性重要度的计算方法。 从分类学习的角度来看，不同样本对学习性能 的贡献程度是不相同的。一般来说，那些对于学习性 能影响比较重要的样本大都分布在边界区域上[15-16]。 从这一考虑出发，可以将边界区域的样本挑选出 来，作为计算属性重要度的依据。一个可行且直观 的办法是采用聚类算法对原始样本集进行聚类，在 各类簇中挑选出距离类簇中心较远的样本，将这些 样本组合成一个新的决策系统，这实际上是一个采 样的过程 (具体描述如算法 2 所示)。又因为传统的 聚类算法，如 k-means 聚类的结果并不稳定，其初始 类簇中心是随机选取的，故可以在原始样本集上通 过多次聚类后得到多个决策系统，分别在这多个决 策系统上求得各个属性的重要度并进行融合，最后 选择融合重要度较高的属性，其具体描述如算法 3 所示。 算法 2 基于 k-means 聚类的采样 输入 邻域决策系统 DS = ⟨U,AT∪ D⟩。 DS 输出 采样后的决策系统 ′。 U ′ 1) = Ø ； {C1,C2,··· ,CN} 2) 利用 k-means 聚类获得 U 上的类簇 C = ，其中 N 为决策类的个数； 3) for j = 1 to N dj ①计算类簇 Cj 中每个样本到类簇中心的平均 距离 ； dj U ′ ②将 Cj 中到类簇中心的距离大于平均距离 的样本挑选出来加入 ； end for DS′ 4) 输出 。 算法 3 重要度集成的启发式算法 输入 邻域决策系统 DS = ⟨U,AT∪ D⟩ ，采样次 数 k； 输出 属性排序 seq。 1) seq←Ø，γ(seq, D)=0； 2) for r = 1 to k 利用算法 2 进行采样得到决策系统 DSr； end for 3) 若 AT–seq = Ø，则转至 7)，否则转至 4)； 4) for r = 1 to k ∀ ai∈AT–seq，计算属性 ai 在决策系统 DSr 上 的重要度 Sigr (ai , AT, D)； end for 5) ∀ ai∈AT– seq，融合属性 ai 在各个决策系统 上的重要度： Sig(ai ,AT,D) = ∑K r=1 Sigr(ai ,AT,D) k ; ∀ 6) 选择 aj，满足 Sig(aj , seq, D)=max{Sig(ai , seq, D)： ai∈AT–seq}，令 seq=seq∪{aj}，返回 3)； 7) 输出 seq。 U 2 U 2 n 3 k×N ×T ×U+ k×[U] 2 ×n 3 [U] 2 ×n 3 在邻域粗糙集上求解属性重要度的时间复杂度 为 O( ×n)，其中 U 表示论域中对象个数，n 代表条 件属性个数，算法 1 的时间复杂度为 O( × )。kmeans 聚类的时间复杂度为 O(N×T×U)，N 为类簇个 数，T 为迭代次数。算法 3 的时间消耗为 ，其中[U]是一个不确定集，表示每次 kmeans 聚类采样的对象个数，聚类次数 k 为常数，故 算法 3 的时间复杂度为 O( )。通过大量实验 表明[U]<U，所以在聚类次数较少的前提下，算法 3 的时间消耗一般小于算法 1。 3 实验分析 为了验证所提算法的有效性，本文从 UCI 数据 集中选择了 9 组数据，数据的基本描述如表 1 所 示。实验中取 k=5，即进行 5 次聚类采样，由算法 3 得到的属性序列不仅和传统的启发式算法比较， 而且和王熙照等 [15]提出的基于样例选取的求解属 性重要度算法对比分析。 表 1 实验数据的基本信息 Table 1 Data sets description 数据集 编号 数据集名称 样本数 属性数 决策类数 1 Dermatology 366 35 6 2 Diabetic Retinopathy Debrecen 1 151 20 2 3 Ecoli 336 8 8 4 Ionosphere 351 35 2 5 Iris 150 4 3 6 Parkinson Multiple Sound Recordings 1 208 27 2 7 Pima Indians Diabetes 768 9 2 8 Tic-Tac-Toe Endgame 958 9 2 9 Yeast 1 484 9 10 ·416· 智 能 系 统 学 报 第 13 卷
第3期 李京政，等：重要度集成的属性约简方法研究 ·417· 为了比较3种约简算法在样本扰动情况下属性 式中：seg:与seq表示第i和第j个属性排序结果； 的排序结果，采用了5折交叉验证来实现。具体过 d=5表示5折交叉验证；Sim表示序列之间的相似 程为：在每个数据集上，将数据集随机地平均分成 性，可采用Spearman排序关联系数进行计算： 5份，即U,U2…,U5。第一次使用U2UU3UUU 求得属性排序结果seq;第二次使用U1UU3U.UU Sim(sed.seq)=1-6x(sed-sedp 台n×2-1) (10) 求得属性排序结果seq2;依次类推，第5次使用U1U 式中：n表示属性个数，seq表示第I个属性在第i个 U2UUU求得属性排序结果seqso 序列中的排序值，本文将排在最前端的属性排序值 3.1 属性序列的稳定性比较 定为n,往后依次减1。 度量属性序列的稳定性，就是在样本扰动时度 表2列出了4个不同的邻域半径下3种约简算 量不同属性序列之间的相似性，相似性越高，说明 法所求得的属性序列的稳定性结果。 所得到的属性序列越稳定，可使用式(9)计算属性 观察表2可以发现，在大多数的半径参数6下， 序列的相似性： 利用算法3所求得的属性序列相似度都比利用算 -1 Sim(seq:,seq) 法1及文献[15]算法所求得的属性序列相似度高， i=l ji+1 这说明算法3在增加属性的过程中所得到的属性序 Sta= (9) d×(d-1) 列是比较稳定的。 表2属性序列的稳定性对比 Table 2 Comparisons of stabilities of attribute sequences 数据 -0.1 d=0.2 -0.3 =0.4 平均值 集编 文献[15] 文献[15] 文献15] 文献[15] 文献[15 算法1算法3 算法1算法3 算法1算法3 算法1算法3 算法1算法3 号 算法 算法 算法 算法 算法 10.31240.49170.32510.34340.50560.21320.32360.5720023850.45660.53120.39290.35900.52510.2924 20.29700.50790.34700.26330.38160.30950.38540.47670.24680.47330.47460.54700.35480.46020.3626 30.80360.76430.52860.41430.62860.44320.15710.60710.38930.26070.79290.52140.40890.69820.4706 40.22930.49110.15240.29130.24870.39810.38530.40470.12650.29340.30770.38800.29980.36300.2662 50.20000.68000.20000.26000.20000.10000.26000.36000.32000.88000.56000.28000.40000.45000.2250 60.35370.40790.36470.26740.26270.24010.12090.3773021710.32530.46770.21150.26680.37890.2584 70.40240.60950.20950.21190.48330.25480.19050.26190.27060.38330.51900.36670.29700.46840.2754 80.28570.46350.36900.23570.54760.41070.40480.53100.26900.32530.20840.38810.31290.43760.3592 90.41900.61670.26800.17860.30950.21480.31900.42140.16470.40710.54050.26740.33090.47200.2287 此外，为了检验新算法约简结果稳定性在统计 [15]的算法的APV值均小于显著性水平a=0.05,这 学上是否具有显著性差异，对各算法的属性序列稳 意味着算法3与其余两种算法有着显著性的差异。 定性的值，采用Friedman检验2分别计算它们的秩 3.2分类结果的一致性比较 及APV(adjusted p-value),判断其是否拒绝原假设。 在求解属性排序序列的过程中，将重要度较大 其中，显著性水平α设为0.05。统计分析结果如表3 的属性逐个添加到约简结果中。在属性序列逐步增 所示。 长的过程中，不同序列在同一分类器上也会产生不 表3各个算法的统计结果 同的分类结果。借助交叉验证，由属性序列seqm 1coumsAT Table 3 Statistical results of various algorithms 与seqm可构造联合分布矩阵，如表4所示。 1cnumcAT 算法 秩 APV 表4联合分布矩阵 算法1 2.33 8.14×10 Table 4 Joint distribution matrix 算法3 1.00 真实情况 seqim(x)=d(x)seqmum(x)d(x) 文献[15]算法 2.67 0.4×102 umAT aunmA灯 segmum (x)=d(x) au bw 从表3可以看出，算法3在各个算法里的秩最 seqm(x)≠dx) 小，这表明算法3性能最好。此外，算法1与文献 1snumsAT du
U1,U2,··· ,U5 U2 ∪U3 ∪ ··· ∪U5 U1 ∪U3 ∪ ··· ∪U5 U1∪ U2 ∪ ··· ∪U4 为了比较 3 种约简算法在样本扰动情况下属性 的排序结果，采用了 5 折交叉验证来实现。具体过 程为：在每个数据集上，将数据集随机地平均分成 5 份，即 。第一次使用 求得属性排序结果 seq1；第二次使用 求得属性排序结果 seq2；依次类推，第 5 次使用 求得属性排序结果 seq5。 3.1 属性序列的稳定性比较 度量属性序列的稳定性，就是在样本扰动时度 量不同属性序列之间的相似性，相似性越高，说明 所得到的属性序列越稳定，可使用式 (9)[21]计算属性 序列的相似性： Sta = 2 ∑d−1 i=1 ∑d j=i+1 Sim(seqi ,seqj) d ×(d −1) (9) 式中： seqi与 seqj 表示第 i 和第 j 个属性排序结果； d=5 表示 5 折交叉验证；Sim 表示序列之间的相似 性，可采用 Spearman 排序关联系数进行计算： Sim(seqi ,seqj) = 1−6× ∑n l=1 (seql i −seql j ) 2 n×(n 2 −1) (10) seql 式中：n 表示属性个数， i表示第 l 个属性在第 i 个 序列中的排序值，本文将排在最前端的属性排序值 定为 n，往后依次减 1。 表 2 列出了 4 个不同的邻域半径下 3 种约简算 法所求得的属性序列的稳定性结果。 观察表 2 可以发现，在大多数的半径参数 δ 下， 利用算法 3 所求得的属性序列相似度都比利用算 法 1 及文献[15]算法所求得的属性序列相似度高， 这说明算法 3 在增加属性的过程中所得到的属性序 列是比较稳定的。 此外，为了检验新算法约简结果稳定性在统计 学上是否具有显著性差异，对各算法的属性序列稳 定性的值，采用 Friedman 检验[22]分别计算它们的秩 及 APV(adjusted p-value)，判断其是否拒绝原假设。 其中，显著性水平 α 设为 0.05。统计分析结果如表 3 所示。 从表 3 可以看出，算法 3 在各个算法里的秩最 小，这表明算法 3 性能最好。此外，算法 1 与文献 [15]的算法的 APV 值均小于显著性水平 α=0.05，这 意味着算法 3 与其余两种算法有着显著性的差异。 3.2 分类结果的一致性比较 seqnum u 1⩽num⩽AT seqnum v 1⩽num⩽AT 在求解属性排序序列的过程中，将重要度较大 的属性逐个添加到约简结果中。在属性序列逐步增 长的过程中，不同序列在同一分类器上也会产生不 同的分类结果。借助交叉验证，由属性序列 与 可构造联合分布矩阵，如表 4 所示。 表 2 属性序列的稳定性对比 Table 2 Comparisons of stabilities of attribute sequences 数据 集编 号 δ=0.1 δ=0.2 δ=0.3 δ=0.4 平均值 算法 1 算法 3 文献[15] 算法 算法 1 算法 3 文献[15] 算法 算法 1 算法 3 文献[15] 算法 算法 1 算法 3 文献[15] 算法 算法 1 算法 3 文献[15] 算法 1 0.312 4 0.491 7 0.325 1 0.343 4 0.505 6 0.213 2 0.323 6 0.572 0 0.238 5 0.456 6 0.531 2 0.392 9 0.359 0 0.525 1 0.292 4 2 0.297 0 0.507 9 0.347 0 0.263 3 0.381 6 0.309 5 0.385 4 0.476 7 0.246 8 0.473 3 0.474 6 0.547 0 0.354 8 0.460 2 0.362 6 3 0.803 6 0.764 3 0.528 6 0.414 3 0.628 6 0.443 2 0.157 1 0.607 1 0.389 3 0.260 7 0.792 9 0.521 4 0.408 9 0.698 2 0.470 6 4 0.229 3 0.491 1 0.152 4 0.291 3 0.248 7 0.398 1 0.385 3 0.404 7 0.126 5 0.293 4 0.307 7 0.388 0 0.299 8 0.363 0 0.266 2 5 0.200 0 0.680 0 0.200 0 0.260 0 0.200 0 0.100 0 0.260 0 0.360 0 0.320 0 0.880 0 0.560 0 0.280 0 0.400 0 0.450 0 0.225 0 6 0.353 7 0.407 9 0.364 7 0.267 4 0.262 7 0.240 1 0.120 9 0.377 3 0.217 1 0.325 3 0.467 7 0.211 5 0.266 8 0.378 9 0.258 4 7 0.402 4 0.609 5 0.209 5 0.211 9 0.483 3 0.254 8 0.190 5 0.261 9 0.270 6 0.383 3 0.519 0 0.366 7 0.297 0 0.468 4 0.275 4 8 0.285 7 0.463 5 0.369 0 0.235 7 0.547 6 0.410 7 0.404 8 0.531 0 0.269 0 0.325 3 0.208 4 0.388 1 0.312 9 0.437 6 0.359 2 9 0.419 0 0.616 7 0.268 0 0.178 6 0.309 5 0.214 8 0.319 0 0.421 4 0.164 7 0.407 1 0.540 5 0.267 4 0.330 9 0.472 0 0.228 7 表 3 各个算法的统计结果 Table 3 Statistical results of various algorithms 算法 秩 APV 算法 1 2.33 8.14×10–4 算法 3 1.00 — 文献[15]算法 2.67 0.4×10–2 表 4 联合分布矩阵 Table 4 Joint distribution matrix 真实情况 seqnum u 1⩽num⩽AT (x) = d(x) seqnum u 1⩽num⩽AT (x) , d(x) seqnum v 1⩽num⩽AT (x) = d(x) auv buv seqnum v 1⩽num⩽AT (x) , d(x) cuv duv 第 3 期 李京政，等：重要度集成的属性约简方法研究 ·417·
·418 智能系统学报 第13卷 在表4中，当前segm包含num个条件属性， 1.00 seqm(x)表示利用交叉验证第u轮由属性序列 0.95 1EnumgA灯 segm在某一种分类器上对样本x做出的预测结 0.90 果。Yx∈U,若seqm(x)=d(x),表示利用当前的属 lsnumAT 0.85 性序列，可以做出正确的分类结果；反之，则表示做 0.80 算法1(6=0. 出的分类结果是错误的。基于联合分布矩阵，采用 算法3(8= Yule提出的Q-统计量方法来度量两种算法的约简 0.75 在分类器上分类结果的一致性，一致性的度量是反 文献15算法 0.70 映分类性能稳定性的指标，其计算式为 3 Q=dada-bacm 属性数目/个 (11) (c)Ecoli audin +buvCin 式中Q的取值范围为[-1,1]。Q值为0时，表示两 1.00 个排序序列在同一分类器上的预测结果毫不相关： 0.95 Q值越大，表示当前两个排序结果在同一分类器上 0.90 0.85 的预测结果的一致性越高。整体的一致性可取平均 0.80 值Q作为分类结果的稳定性指标。实验中采用 0.75 KNN分类器去分类，因为不同的数据集对K的敏 0.70 算法1(6=0 感程度不一样，为了降低K的取值对分类结果影 0.65 0 响，每个数据集对K寻优，在最佳的K值情况下，再 0.60 法(6=0.1 0.55 文献15算法(=0.4) 比较各个算法下的分类性能。按照表1顺序，K 0.50 分别取值为3、5、9、3、5、9、7、3、5。为了能直观比 10 15 20 25 30 较3种约简算法分类结果的一致性，以及不同邻域 属性数目/个 (d)Ionosphere 半径参数下对分类结果一致性的影响，分别在邻域 参数=0.1与6=0.4时完成本组实验。实验结果如 1.0 图1所示。 0.9 1.0 0.8 106 0.9 0.7 0.8 0.6 0.7 0.6 算法1(=0.1) 1=04】 05 算法1(=0.1) 0 0.4 法1(d=0.4 0.2 文藏[15]算法=0.1) 0.3 天3d=0.4 文献15算法8=0.4) 0.2 文献[151算法(8=0.1) 文献15算法(=0.4) 1.0 1.5 2.0 2.53.0 3.5 4.0 0.1 属性数目/个 10 15 20 25 30 (e)Iris 属性数目/个 (a)Dermatology 1.0 1.0 0.9 0.9 0.8 8 0.7 0 0.5 0.6 0.4 中 0.1 0 0.5 02 0 8 0.4 0. 文献[15]算法(=0.1) 南状15=0.1】 文献[15]算法(=0.4) 0 文献i5算法8-0.4 0.3 2 4 681012141618 10 15 20 25 属性数目/个 属性数目/个 (b)Diabetic Retinopathy Debrecen (f)Parkinson Multiple Sound Recording
seqnum u 1⩽num⩽AT seqnum u 1⩽num⩽AT seqnum u 1⩽num⩽AT∀ seqnum u 1⩽num⩽AT (x) = d(x) 在表 4 中，当前 包含 num 个条件属性， (x) 表示利用交叉验证第 u 轮由属性序列 在某一种分类器上对样本 x 做出的预测结 果。 x∈U，若 ，表示利用当前的属 性序列，可以做出正确的分类结果；反之，则表示做 出的分类结果是错误的。基于联合分布矩阵，采用 Yule 提出的 Q-统计量方法来度量两种算法的约简 在分类器上分类结果的一致性，一致性的度量是反 映分类性能稳定性的指标，其计算式为 Q = auvduv −buvcuv auvduv +buvcuv (11) Q 式中 Q 的取值范围为[−1, 1]。Q 值为 0 时，表示两 个排序序列在同一分类器上的预测结果毫不相关； Q 值越大，表示当前两个排序结果在同一分类器上 的预测结果的一致性越高。整体的一致性可取平均 值 作为分类结果的稳定性指标。实验中采用 KNN 分类器去分类，因为不同的数据集对 K 的敏 感程度不一样，为了降低 K 的取值对分类结果影 响，每个数据集对 K 寻优，在最佳的 K 值情况下，再 比较各个算法下的分类性能。按照表 1 顺序，K 分别取值为 3、5、9、3、5、9、7、3、5。为了能直观比 较 3 种约简算法分类结果的一致性，以及不同邻域 半径参数下对分类结果一致性的影响，分别在邻域 参数 δ=0.1 与 δ=0.4 时完成本组实验。实验结果如 图 1 所示。 (a) Dermatology 5 10 15 20 25 30 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ᆊᕓⰚ/͖ ܲㆧ㏿̬㜠ᕓ ッ∁1(δ=0.1) ッ∁1(δ=0.4) ッ∁3(δ=0.1) ッ∁3(δ=0.4) ᪳⡚[15]ッ∁(δ=0.1) ᪳⡚[15]ッ∁(δ=0.4) ッ∁1(δ=0.1) ッ∁1(δ=0.4) ッ∁3(δ=0.1) ッ∁3(δ=0.4) ᪳⡚[15]ッ∁(δ=0.1) ᪳⡚[15]ッ∁(δ=0.4) (b) Diabetic Retinopathy Debrecen 2 4 6 8 10 12 14 16 18 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ᆊᕓⰚ/͖ ܲㆧ㏿̬㜠ᕓ 0 5 10 15 20 25 30 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 属性数目/个 分类结果一致性 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (d) Ionosphere 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (f) Parkinson Multiple Sound Recording 5 10 15 20 25 0.4 0.5 0.6 0.7 0.8 0.9 1.0 属性数目/个 分类结果一致性 1.0 1.5 2.0 2.5 3.0 3.5 4.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 属性数目/个 分类结果一致性 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (e) Iris 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 1 2 3 4 5 6 7 0.70 0.75 0.80 0.85 0.90 0.95 1.00 属性数目/个 分类结果一致性 (c) Ecoli 0 0.3 ·418· 智 能 系 统 学 报 第 13 卷
第3期 李京政，等：重要度集成的属性约简方法研究 ·419· 1.0 1.0 0.9 0.9 ooo。09883geg2ee9 00 0.8 0.7 算法1(=0.1) 算法1(6=0.1) 于1=0.4 0.4 算法3=0.1) 0.4 文献[15]算法(=0.1)】 算法300.4 文献15算法(8=0.4 0.3 15]算法（心=0.1） 文献15算法(6=0.4】 0.3 3 4.5678 02 属性数目/个 5 10 15 20 25 30 (g)Pima Indians Diabetes 属性数目/个 (a)Dermatology 1.00 0.80 0.95 0.75 0.90 0.70 0.85 算法1(8=0.1) 0.65 算法1(0=0.1) 算法1(=0.4) 0.80 文[151算法(=0.1) 0.60 文献15]算法（识 .4 0.75 8出 2 3 4 5 6 7 0.55 属性数目/个 6 81012 141618 (h)Tic-Tac-Toe Endgame 属性数目/个 (b)Diabetic Retinopathy Debrecen 1.0 0.95 0.90 S565452 算法1(=0.1) 0 0.65 算法1(=0.1) 算法1(=0.4】 算法36=0.4) 0- 算法3(=0.1) 文献151算法(=0.1) 060 算法3(=0.4) 文献15送8=0.4 0.55 文献 (=0.1) 3 45 6 7 0.50 属性数目/个 3 (i)Yeast 属性数目/个 (c)Ecoli 图1分类结果一致性的对比 0.94 Fig.1 Comparisons of classification agreements 0.92 由图1可知，随着属性逐个加入排序序列中在 0.90 相同的邻域半径参数下，算法3在依次增加属性时 0.88 做出分类结果的一致性总体比算法1以及文献[15] 0.86 算法要高，验证了由算法3求得属性序列做出分类 0.84 0.82 算法1（心=0.1） 结果的稳定性要高于算法1以及文献[15]算法。 中 算法1(=0.4) 0.80 40 但法3=01 3.3分类精度比较 算法3=0.41 法(=0.1) 随着当前重要度最大的属性逐渐加入到属性序 0.78 列中去，进一步考虑当前属性序列的分类精度，对 0.76 5 10 1520 25 30 此，分别在邻域参数=0.1与=0.4时比较了3种 属性数目/个 约简算法的分类精度，实验结果如图2所示。 (d)Ionosphere
由图 1 可知，随着属性逐个加入排序序列中在 相同的邻域半径参数下，算法 3 在依次增加属性时 做出分类结果的一致性总体比算法 1 以及文献[15] 算法要高，验证了由算法 3 求得属性序列做出分类 结果的稳定性要高于算法 1 以及文献[15]算法。 3.3 分类精度比较 随着当前重要度最大的属性逐渐加入到属性序 列中去，进一步考虑当前属性序列的分类精度，对 此，分别在邻域参数 δ=0.1 与 δ=0.4 时比较了 3 种 约简算法的分类精度，实验结果如图 2 所示。 1 2 3 4 5 6 7 8 0.4 0.5 0.6 0.7 0.8 0.9 1.0 属性数目/个 分类结果一致性 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (g) Pima Indians Diabetes 1 2 3 4 5 6 7 8 0.75 0.80 0.85 0.90 0.95 1.00 属性数目/个 分类结果一致性 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (h) Tic-Tac-Toe Endgame 1 2 3 4 5 6 7 8 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 属性数目/个 分类结果一致性 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (i) Yeast 0.3 图 1 分类结果一致性的对比 Fig. 1 Comparisons of classification agreements (a) Dermatology 5 10 15 20 25 30 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 属性数目/个 分类精度 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) (b) Diabetic Retinopathy Debrecen 2 4 6 8 10 12 14 16 18 0.55 0.60 0.65 0.70 0.75 0.80 属性数目/个 分类精度 1 2 3 4 5 6 7 0.70 0.65 0.60 0.55 0.50 0.75 0.80 0.85 0.90 0.95 属性数目/个 分类精度 (c) Ecoli 5 10 15 20 25 30 0.76 0.78 0.80 0.82 0.84 0.86 0.88 0.90 0.92 0.94 属性数目/个 分类精度 (d) Ionosphere 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 第 3 期 李京政，等：重要度集成的属性约简方法研究 ·419·
·420· 智能系统学报 第13卷 1.00 0.75 0.95 0.70 0.90 0.85 0.65 0.80 0.60 0.75 0.55 0.70 算法1(=0.1) 0.50 算法1(=0.1) 0.4 算法1(=0.4) 0.65 0. 算法3(=0.1) 算法3(=0.4) 0.45 算法30 0.60 法(=0.1) 文献[15]算法=0.1) 0.55 文献 15j算法(=0.4 0.40 文献15算法=0.4) 0.50 0.35 4 5 6 1.0 1.5 2.02.5 3.0 3.5 4.0 属性数目/个 属性数目个 (e)Iris (i)Yeast 0.80 图2分类精度的对比 Fig.2 Comparisons of classification accuracies 0.75 00身8有g888880烤参8国 通过图2可知，在相同的邻域半径参数下，随 0.70 着属性逐个加入到排序序列中，其分类精度也在不 断提高，当属性达到一定个数时，分类精度也趋于 0.65 平稳。总体来说，由算法1、算法3和文献[15]的算 .4 0. 算法3(8=0.1) 法得到的属性序列的分类精度是差不多的。尽管算 0.60 8 算法3(=0.4) 文献[15算法(=0.1) 文献15法-0.4) 法3得到的属性序列在样本扰动下的稳定性以及分 0.55 类结果的一致性较算法1和文献[15]的算法能够得 10 20 25 属性数目/个 到提升，但是未能有效提升属性序列的分类精度。 (f)Parkinson Multiple Sound Recording 4结束语 0.95 利用邻域粗糙集求解约简时，提出了一种可以 0.90 得到稳定约简的启发式算法框架。这种新的算法在 0.85 多次采样基础上利用集成的思想求解属性重要度， 0.80 从而可以用来提高约简的稳定性。实验结果表明， 算法1(=0.1) 新算法在有效地提升约简稳定性的同时，亦能提高 0.70 041 由约简所做出分类结果的稳定性。在本文工作的基 0.65 础上，下一步工作主要有：1)针对稳定的属性约简 文[153 1法(=0.1) 文献15]算法(=0.4) 与分类度量指标之间的关系进行深入讨论，以期能 4 5 6 > 够在获得稳定约简的基础上，提升分类精度等相应 属性数目/个 的学习性能：2)文中聚类采样方法未能考虑到原始 (g)Pima Indians Diabetes 样本分布情况，对于某些非凸型分布的样本，或许 0.84 算法1(=0.1) 不能有效地抽取到边界样本。进一步考虑数据的分 0.82 0.80 法3(6=0.1) 布情况，寻求更有效的方法抽取到边界样本也是笔 算法3(=0.4) 0.78 者的下一步工作。 0.76 0.74 参考文献： 0.72 [1]PAWLAK Z.Rough sets:theoretical aspects of reasoning about data[M].Boston,Mass,USA:Kluwer Academic Pub- 0.68 0.66 lishers,1991. 0.64 [2]PAWLAK Z.Rough sets[J].International journal of com 3 45 6 7 puter&information sciences,1982,11(5):341-356. 属性数目/个 [3]JU Hengrong,LI Huaxiong,YANG Xibei,et al.Cost-sensit- (h)Tic-Tac-Toe Endgame ive rough set:a multi-granulation approach[J].Knowledge-
通过图 2 可知，在相同的邻域半径参数下，随 着属性逐个加入到排序序列中，其分类精度也在不 断提高，当属性达到一定个数时，分类精度也趋于 平稳。总体来说，由算法 1、算法 3 和文献[15]的算 法得到的属性序列的分类精度是差不多的。尽管算 法 3 得到的属性序列在样本扰动下的稳定性以及分 类结果的一致性较算法 1 和文献[15]的算法能够得 到提升，但是未能有效提升属性序列的分类精度。 4 结束语 利用邻域粗糙集求解约简时，提出了一种可以 得到稳定约简的启发式算法框架。这种新的算法在 多次采样基础上利用集成的思想求解属性重要度， 从而可以用来提高约简的稳定性。实验结果表明， 新算法在有效地提升约简稳定性的同时，亦能提高 由约简所做出分类结果的稳定性。在本文工作的基 础上，下一步工作主要有：1) 针对稳定的属性约简 与分类度量指标之间的关系进行深入讨论，以期能 够在获得稳定约简的基础上，提升分类精度等相应 的学习性能；2) 文中聚类采样方法未能考虑到原始 样本分布情况，对于某些非凸型分布的样本，或许 不能有效地抽取到边界样本。进一步考虑数据的分 布情况，寻求更有效的方法抽取到边界样本也是笔 者的下一步工作。 参考文献： PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Boston, Mass, USA: Kluwer Academic Publishers, 1991. [1] PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341–356. [2] JU Hengrong, LI Huaxiong, YANG Xibei, et al. Cost-sensitive rough set: a multi-granulation approach[J]. Knowledge- [3] 1 2 3 4 5 6 7 8 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 属性数目/个 分类精度 (i) Yeast 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 图 2 分类精度的对比 Fig. 2 Comparisons of classification accuracies 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 1.0 1.5 2.0 2.5 3.0 3.5 4.0 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 属性数目/个 分类精度 (f) Parkinson Multiple Sound Recording 5 10 15 20 25 0.55 0.60 0.65 0.70 0.75 0.80 属性数目/个 分类精度 (e) Iris 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 1 2 3 4 5 6 7 8 0.65 0.70 0.75 0.80 0.85 0.90 0.95 属性数目/个 分类精度 (g) Pima Indians Diabetes 1 2 3 4 5 6 7 8 0.74 0.72 0.70 0.68 0.66 0.64 0.76 0.78 0.80 0.82 0.84 属性数目/个 分类精度 (h) Tic-Tac-Toe Endgame 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) 算法1(δ=0.1) 算法1(δ=0.4) 算法3(δ=0.1) 算法3(δ=0.4) 文献[15]算法(δ=0.1) 文献[15]算法(δ=0.4) ·420· 智 能 系 统 学 报 第 13 卷
第3期 李京政，等：重要度集成的属性约简方法研究 ·421· based systems,2017,123:137-153,doi:10.1016/j.knosys. [16)杨习贝，颜旭，徐苏平，等.基于样本选择的启发式属性 2017.02.019 约简方法研究U.计算机科学，2016,43(1)：40-43。 [4]XU Suping,YANG Xibei,YU Hualong,et al.Multi-label YANG Xibei,YAN Xu,XU Suping,et al.New heuristic learning with label-specific feature reduction[J].Know- attribute reduction algorithm based on sample selection[J]. ledge-based systems,2016,104:52-61. Computer science,2016,43(1):40-43. [5]DUBOIS D,PRADE H.Rough fuzzy sets and fuzzy rough [17]LI Yun,SI J,ZHOU Guojing,et al.FREL:a stable feature sets[J].International journal of general systems,1990, selection algorithm[J].IEEE transactions on neural net- 172/3):191-209 works and learning systems,2014,26(7):1388-1402. [6]胡清华，于达仁，谢宗霞.基于邻域粒化和粗糙逼近的数 [18]周林，平西建，徐森，等.基于谱聚类的聚类集成算法叮 值属性约简.软件学报，2008.19(3)：640-649。 自动化学报，2012,38(8)：1335-1342. HU Qinghua,YU Daren,XIE Zongxia.Numerical attribute ZHOU Lin,PING Xijian,XU Sen,et al.Cluster ensemble reduction based on neighborhood granulation and rough ap- based on spectral clustering[J].Acta automatica sinica, 2012.38(8):1335-1342. proximation[J].Journal of software,2008,19(3):640-649. [19]YANG Xibei,ZHANG Ming,DOU Huili,et al.Neighbor- [7]YANG Xibei,CHEN Zehua,DOU Huili,et al.Neighbor- hood systems-based rough sets in incomplete information hood system based rough set:models and attribute reduc- system[J].Knowledge-based systems,2011,24(6): tions[J].International journal of uncertainty,fuzziness and 858-867. knowledge-based systems,2012,20(3):399-419 [20]QIAN Yuhua,WANG Qi,CHENG Honghong,et al. [8]LIANG Jiye,WANG Feng,DANG Chuangyin,et al.An ef- Fuzzy-rough feature selection accelerator[J].Fuzzy sets ficient rough feature selection algorithm with a multi-granu- and systems,.2014,258:61-78. lation view[J].International journal of approximate reason- [21]LI Jingzheng,YANG Xibei,SONG Xiaoning,et al.Neigh- ing.2012.53(6):912-926 borhood attribute reduction:a multi-criterion approach[J]. [9]ZHANG Xiao,MEI Changlin,CHEN Degang,et al.Fea- International journal of machine learning and cybernetics. ture selection in mixed data:a method using a novel fuzzy 2017,doi:10.1007/s13042-017-0758-5. rough set-based information entropy[J].Pattern recognition, [22]DEMSAR J.Statistical comparisons of classifiers over 2016,56:1-15. multiple data sets[J.Journal of machine learning research, [10]JU Hengrong,YANG Xibei,YU Hualong,et al.Cost-sens- 2006,7:1-30. itive rough set approach[J].Information sciences,2016, 作者简介： 355-356:282-298. 李京政，男，1993年生，硕士研究 [11]JIA Xiuyi,LIAO Wenhe,TANG Zhenmin,et al.Minim- 生，主要研究方向为粗糙集理论、机器 um cost attribute reduction in decision-theoretic rough set 学习。 models[J].Information sciences,2013,219:151-167. [12]YANG Xibei,QI Yunsong,SONG Xiaoning,et al.Test cost sensitive multigranulation rough set:model and min- imal cost selection[J].Information sciences,2013,250: 184199. 杨习贝，男.1980年生，副教授 [13]MIN Fan,HE Huaping,QIAN Yuhua,et al.Test-cost-sens- 博士后，主要研究方向为粗糙集理论 itive attribute reduction[J].Information sciences,2011, 粒计算、机器学习。发表学术论文 181(22):4928-4942. 100余篇，被SCI检索50余篇，出版 [14]SONG Jingjing,TSANG E CC,CHEN Degang,et al. 英文专著一部。 Minimal decision cost reduct in fuzzy decision-theoretic rough set model[J].Knowledge-based systems,2017,126: 104-112,doi:10.1016M.knosys..2017.03.013. 实慧莉，女，1980年生，助理研究 [1]王熙照，王婷婷，翟俊海.基于样例选取的属性约简算法 员，主要研究方向为粒计算、智能信息 [).计算机研究与发展，2012,4911)：2305-2310. 处理。 WANG Xizhao,WANG Tingting,ZHAI Junhai.An attrib- ute reduction algorithm based on instance selection[J]. Journal of computer research and development,2012, 49(11:2305-2310
based systems, 2017, 123: 137–153, doi: 10.1016/j.knosys. 2017.02.019. XU Suping, YANG Xibei, YU Hualong, et al. Multi-label learning with label-specific feature reduction[J]. Knowledge-based systems, 2016, 104: 52–61. [4] DUBOIS D, PRADE H. Rough fuzzy sets and fuzzy rough sets[J]. International journal of general systems, 1990, 17(2/3): 191–209. [5] 胡清华, 于达仁, 谢宗霞. 基于邻域粒化和粗糙逼近的数 值属性约简[J]. 软件学报, 2008, 19(3): 640–649. HU Qinghua, YU Daren, XIE Zongxia. Numerical attribute reduction based on neighborhood granulation and rough approximation[J]. Journal of software, 2008, 19(3): 640–649. [6] YANG Xibei, CHEN Zehua, DOU Huili, et al. Neighborhood system based rough set: models and attribute reductions[J]. International journal of uncertainty, fuzziness and knowledge-based systems, 2012, 20(3): 399–419. [7] LIANG Jiye, WANG Feng, DANG Chuangyin, et al. An efficient rough feature selection algorithm with a multi-granulation view[J]. International journal of approximate reasoning, 2012, 53(6): 912–926. [8] ZHANG Xiao, MEI Changlin, CHEN Degang, et al. Feature selection in mixed data: a method using a novel fuzzy rough set-based information entropy[J]. Pattern recognition, 2016, 56: 1–15. [9] JU Hengrong, YANG Xibei, YU Hualong, et al. Cost-sensitive rough set approach[J]. Information sciences, 2016, 355-356: 282–298. [10] JIA Xiuyi, LIAO Wenhe, TANG Zhenmin, et al. Minimum cost attribute reduction in decision-theoretic rough set models[J]. Information sciences, 2013, 219: 151–167. [11] YANG Xibei, QI Yunsong, SONG Xiaoning, et al. Test cost sensitive multigranulation rough set: model and minimal cost selection[J]. Information sciences, 2013, 250: 184–199. [12] MIN Fan, HE Huaping, QIAN Yuhua, et al. Test-cost-sensitive attribute reduction[J]. Information sciences, 2011, 181(22): 4928–4942. [13] SONG Jingjing, TSANG E C C, CHEN Degang, et al. Minimal decision cost reduct in fuzzy decision-theoretic rough set model[J]. Knowledge-based systems, 2017, 126: 104–112, doi: 10.1016/j.knosys.2017.03.013. [14] 王熙照, 王婷婷, 翟俊海. 基于样例选取的属性约简算法 [J]. 计算机研究与发展, 2012, 49(11): 2305–2310. WANG Xizhao, WANG Tingting, ZHAI Junhai. An attribute reduction algorithm based on instance selection[J]. Journal of computer research and development, 2012, 49(11): 2305–2310. [15] 杨习贝, 颜旭, 徐苏平, 等. 基于样本选择的启发式属性 约简方法研究[J]. 计算机科学, 2016, 43(1): 40–43. YANG Xibei, YAN Xu, XU Suping, et al. New heuristic attribute reduction algorithm based on sample selection[J]. Computer science, 2016, 43(1): 40–43. [16] LI Yun, SI J, ZHOU Guojing, et al. FREL: a stable feature selection algorithm[J]. IEEE transactions on neural networks and learning systems, 2014, 26(7): 1388–1402. [17] 周林, 平西建, 徐森, 等. 基于谱聚类的聚类集成算法[J]. 自动化学报, 2012, 38(8): 1335–1342. ZHOU Lin, PING Xijian, XU Sen, et al. Cluster ensemble based on spectral clustering[J]. Acta automatica sinica, 2012, 38(8): 1335–1342. [18] YANG Xibei, ZHANG Ming, DOU Huili, et al. Neighborhood systems-based rough sets in incomplete information system[J]. Knowledge-based systems, 2011, 24(6): 858–867. [19] QIAN Yuhua, WANG Qi, CHENG Honghong, et al. Fuzzy-rough feature selection accelerator[J]. Fuzzy sets and systems, 2014, 258: 61–78. [20] LI Jingzheng, YANG Xibei, SONG Xiaoning, et al. Neighborhood attribute reduction: a multi-criterion approach[J]. International journal of machine learning and cybernetics, 2017, doi: 10.1007/s13042-017-0758-5. [21] DEMŠAR J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of machine learning research, 2006, 7: 1–30. [22] 作者简介： 李京政，男，1993 年生，硕士研究 生，主要研究方向为粗糙集理论、机器 学习。 杨习贝，男，1980 年生，副教授， 博士后，主要研究方向为粗糙集理论、 粒计算、机器学习。发表学术论文 100 余篇，被 SCI 检索 50 余篇，出版 英文专著一部。 窦慧莉，女，1980 年生，助理研究 员，主要研究方向为粒计算、智能信息 处理。 第 3 期 李京政，等：重要度集成的属性约简方法研究 ·421·