第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201905051 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190828.1806.010html 面向一致性样本的属性约简 高媛'，陈向坚，王平心2，杨习贝 (1.江苏科技大学计算机学院，江苏镇江212003：2.江苏科技大学理学院，江苏镇江212003) 摘要：作为粗糙集理论的一个核心内容，属性约简致力于根据给定的约束条件删除数据中的冗余属性。基于 贪心策略的启发式算法是求解约简的一种有效手段，这一手段通常使用数据中的全部样本来度量属性的重要 度从而进一步得到约简子集。但实际上，不同样本对于属性重要度计算的贡献是不同的，有些样本对重要度贡 献不高甚至几乎没有贡献，且当数据中的样本数过大时，利用全部样本进行约简求解会使得时间消耗过大而难 以接受。为了解决这一问题，提出了一种基于一致性样本的属性约简策略。具体算法大致由3个步骤组成.首 先，将满足一致性原则的样本挑选出来；其次，将这些选中的样本组成新的决策系统；最后，利用启发式框架在 新的决策系统中求解约简。实验结果表明：与基于聚类采样的属性约简算法相比，所提方法能够提供更高的分 类精度。 关键词：属性约简：分类精度：聚类；一致性样本：集成：启发式算法：邻域粗糙集；多准则 中图分类号：TP181文献标志码：A文章编号：1673-4785(2019)06-1170-09 中文引用格式：高媛，陈向坚，王平心，等.面向一致性样本的属性约简.智能系统学报，2019,14(6)：1170-1178. 英文引用格式：GAO Yuan,CHEN Xiangjian,WANG Pingxin,ctal.Attribute reduction over consistent samplesJ.CAAI transac- tions on intelligent systems,2019,14(6):1170-1178. Attribute reduction over consistent samples GAO Yuan',CHEN Xiangjian',WANG Pingxin',YANG Xibei (1.School of Computer,Jiangsu University of Science and Technology,Zhenjiang 212003,China;2.School of Science,Jiangsu Uni- versity of Science and Technology,Zhenjiang 212003,China) Abstract:As one of the key topics in rough sets theory,attribute reduction aims to remove redundant attributes in a data set according to a given constraint condition.Based on greedy strategy,the heuristic algorithm is an effective strategy in finding reductions.Traditional heuristic algorithms usually need to scan all samples in a data set to compute the signific- ance of attributes to further obtain a reduction.However,different samples have different contributions to the process of computing significance.Some samples have little relation to the significance,and some even have no contribution to the significance.Therefore,scanning all samples to compute reductions may require too much time,and the time may be un- acceptable if the number of samples is too large.To fill such a gap,we have proposed an attribute reduction algorithm with sample selection,which is based on the consistent principle.The algorithm is composed of three stages.First,the samples that satisfy the consistent principle were selected,second,a new decision system was constructed with these se- lected samples;finally,reductions were derived from the heuristic algorithm over the new decision system.Experiment- al results demonstrated that,compared with the attribute reduction algorithm with a cluster-based sample selection,our new algorithm can offer better classification accuracy. Keywords:attribute reduction;classification accuracy;clustering:consistent samples;ensemble;heuristic algorithm; neighborhood rough set;multiple criteria 收稿日期：2019-05-27.网络出版日期：2019-08-29 粗糙集-是Pawlak提出的一种用以刻画不 基金项目：国家自然科学基金项目(61572242,61503160)：江苏 省研究生科研创新计划项目(KYCX191697). 确定性的建模方法。由于经典粗糙集所使用的等 通信作者：杨习贝.E-mail:jsjxy_yxb@2just.edu.cn.. 价关系仅仅适用于符号型数据，为了弥补这一不
DOI: 10.11992/tis.201905051 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190828.1806.010.html 面向一致性样本的属性约简 高媛1 ，陈向坚1 ，王平心2 ，杨习贝1 （1. 江苏科技大学 计算机学院，江苏 镇江 212003; 2. 江苏科技大学 理学院，江苏 镇江 212003） 摘 要：作为粗糙集理论的一个核心内容，属性约简致力于根据给定的约束条件删除数据中的冗余属性。基于 贪心策略的启发式算法是求解约简的一种有效手段，这一手段通常使用数据中的全部样本来度量属性的重要 度从而进一步得到约简子集。但实际上，不同样本对于属性重要度计算的贡献是不同的，有些样本对重要度贡 献不高甚至几乎没有贡献，且当数据中的样本数过大时，利用全部样本进行约简求解会使得时间消耗过大而难 以接受。为了解决这一问题，提出了一种基于一致性样本的属性约简策略。具体算法大致由 3 个步骤组成，首 先，将满足一致性原则的样本挑选出来；其次，将这些选中的样本组成新的决策系统；最后，利用启发式框架在 新的决策系统中求解约简。实验结果表明：与基于聚类采样的属性约简算法相比，所提方法能够提供更高的分 类精度。 关键词：属性约简；分类精度；聚类；一致性样本；集成；启发式算法；邻域粗糙集；多准则 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2019)06−1170−09 中文引用格式：高媛, 陈向坚, 王平心, 等. 面向一致性样本的属性约简 [J]. 智能系统学报, 2019, 14(6): 1170–1178. 英文引用格式：GAO Yuan, CHEN Xiangjian, WANG Pingxin, et al. Attribute reduction over consistent samples[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1170–1178. Attribute reduction over consistent samples GAO Yuan1 ，CHEN Xiangjian1 ，WANG Pingxin2 ，YANG Xibei1 (1. School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212003, China; 2. School of Science, Jiangsu University of Science and Technology, Zhenjiang 212003, China) Abstract: As one of the key topics in rough sets theory, attribute reduction aims to remove redundant attributes in a data set according to a given constraint condition. Based on greedy strategy, the heuristic algorithm is an effective strategy in finding reductions. Traditional heuristic algorithms usually need to scan all samples in a data set to compute the significance of attributes to further obtain a reduction. However, different samples have different contributions to the process of computing significance. Some samples have little relation to the significance, and some even have no contribution to the significance. Therefore, scanning all samples to compute reductions may require too much time, and the time may be unacceptable if the number of samples is too large. To fill such a gap, we have proposed an attribute reduction algorithm with sample selection, which is based on the consistent principle. The algorithm is composed of three stages. First, the samples that satisfy the consistent principle were selected; second, a new decision system was constructed with these selected samples; finally, reductions were derived from the heuristic algorithm over the new decision system. Experimental results demonstrated that, compared with the attribute reduction algorithm with a cluster-based sample selection, our new algorithm can offer better classification accuracy. Keywords: attribute reduction; classification accuracy; clustering; consistent samples; ensemble; heuristic algorithm; neighborhood rough set; multiple criteria 粗糙集[1-2] 是 Pawlak 提出的一种用以刻画不 确定性的建模方法。由于经典粗糙集所使用的等 价关系仅仅适用于符号型数据，为了弥补这一不 收稿日期：2019−05−27. 网络出版日期：2019−08−29. 基金项目：国家自然科学基金项目 (61572242，61503160)；江苏 省研究生科研创新计划项目 (KYCX19_1697). 通信作者：杨习贝. E-mail：jsjxy_yxb@just.edu.cn. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019
第6期 高媛，等：面向一致性样本的属性约简 ·1171· 足，涌现出了一批可以处理复杂类型数据的拓展 中[x]。表示与x属于同一个决策类的样本的 粗糙集模型B。 集合。 众所周知，无论是在经典粗糙集还是在众多 定义1给定一个决策系统DS,VACAT,则邻 拓展粗糙集研究中，属性约简610一直扮演着核 域关系定义为 心角色。根据问题求解需求的不同，属性约简可 Na={x,y)∈U×U:(x,y)≤61 (1) 以使用不同的度量准则加以定义，因此其具有丰 其中，x,y∈U,(x,y)表示样本x与y之间的欧氏 富的解释与含义。例如近似质量可以用来度量数 距离，>0称为邻域半径。 据中的确定性程度，条件熵可以用来描述条件属 则由式(1)，容易得到关于A样本x的邻域： 性相对于决策属性的鉴别能力。属性约简，就可 6a(x)={ylr(x,y)≤6l (2) 以依据这些度量准则，找到数据中的冗余属性并 定义2给定一个决策系统DS,UIND(D)= 加以删除，以达到满足度量准则所对应的约束条 {X,X2,,X,},VACAT,YX。∈UIND(D),X2关于 件。通过这一策略，还能够使得后续的学习过程 A的下近似集和上近似集分别定义为 仅需在一部分属性上构建模型，从而达到降低学 NX,={x∈U6a(w)∈Xp} (3) 习难度以及降低学习时间消耗的目的。 NaX2={x∈U6a()nX,≠} (4) 目前在粗糙集理论中，穷举法与启发式方法 定义32！给定一个决策系统DS,UND(D)= 被公认为是求解约简的两大类基本方法。然而很 {X,X,,X,},VACAT,D关于A的近似质量定义 多穷举搜索与启发式搜索策略都将数据集中的所 如下： 有样本视为同等重要，当样本量非常巨大时，这 会带来较低的约简求解效率。为解决这一问题， y(A,D)= (5) 已有众多学者将样本选择的概念引入到约简求解 过程中。样本选择的概念最早是由Hat提出，他 其中UU表示集合X的基数。 提出了压缩近邻规则，随后亦有学者提出了很 显然0≤4，D)≤1成立。(4，D)表示根据条 多改进策略，如缩减最近邻)、有序最近邻)和 件属性A,那些确定属于某一决策类别的样本占 快速压缩最近邻，等。当涉及约简求解的问题 总体样本的比例。 时，已有学者s9关注到不同的样本对属性重要 条件嫡是属性约简中另外一种常用的度量准 度评价的贡献是不同的，如王熙照等提出的K 则，它能反映条件属性相对于决策属性的鉴别能 means样本选择算法将远离类簇中心点的样本视 力。根据不同的需求，很多学者设计并定义了多 为重要的：随后Xu等将这种方法应用到多标 种形式的条件嫡22，一种经典的形式可定义为： 记数据的维度压缩问题中。但他们在追求时间效 定义421给定一个决策系统DS,VACAT, 率的同时忽略了约简在测试集上的分类性能。 D关于A的条件嫡定义如下： 基于以上分析，笔者提出了一种基于样本一 ENT(A,D)=- 1>1og A(x)0[xII (6) IUI 致性原则的样本选择算法（以下简称为一致性采 样)，一致性采样的主要思想为：1)给定一个样本， 显然，条件嫡的值越小，条件属性相对于决策 找到距离自己最近的邻居；2)判断这一邻居是否 属性鉴别能力越大。 与自身属于同一类别，若属于同一类别，则将该 样本选中；3)最后将所有选中的样本组成一个新 2属性约简 的数据集。 属性约简作为粗糙集领域的一个核心内容， 1基础知识 其主要目的是根据某一给定的约束条件来去除全 部属性中的冗余、不相关的属性。目前求解约简 在粗糙集理论中，一个决策系统可表示为一 的常用策略包括穷举式算法和启发式算法。虽然 个二元组DS=,U是所有样本构成的 前者可以得到一个数据中的所有约简，但当数据 非空有限集合，即论域；AT是所有条件属性的集 维数急剧升高时，它的时间消耗随之增大，过大 合；D是决策属性的集合且AT∩D=O。当D的取 的时间消耗导致算法并不适用于处理实际问题。 值都为离散型时，可得UND(D)={X,X2,,X,}, 与穷举式算法不同，启发式算法因其较高的时间 其表示根据决策属性D所诱导出的论域上的划 效率得到了众多学者的青睐，它运用贪心策略，每 分，对于X,∈UNDD),X表示第p个决策类，其 次迭代过程中其将属性重要度最大的属性加入到
足，涌现出了一批可以处理复杂类型数据的拓展 粗糙集模型[3-5]。 众所周知，无论是在经典粗糙集还是在众多 拓展粗糙集研究中，属性约简[6-10] 一直扮演着核 心角色。根据问题求解需求的不同，属性约简可 以使用不同的度量准则加以定义，因此其具有丰 富的解释与含义。例如近似质量可以用来度量数 据中的确定性程度，条件熵可以用来描述条件属 性相对于决策属性的鉴别能力。属性约简，就可 以依据这些度量准则，找到数据中的冗余属性并 加以删除，以达到满足度量准则所对应的约束条 件。通过这一策略，还能够使得后续的学习过程 仅需在一部分属性上构建模型，从而达到降低学 习难度以及降低学习时间消耗的目的。 目前在粗糙集理论中，穷举法与启发式方法 被公认为是求解约简的两大类基本方法。然而很 多穷举搜索与启发式搜索策略都将数据集中的所 有样本视为同等重要，当样本量非常巨大时，这 会带来较低的约简求解效率。为解决这一问题， 已有众多学者将样本选择的概念引入到约简求解 过程中。样本选择的概念最早是由 Hart 提出，他 提出了压缩近邻规则[11] ，随后亦有学者提出了很 多改进策略，如缩减最近邻[12] 、有序最近邻[13] 和 快速压缩最近邻[14] 等。当涉及约简求解的问题 时，已有学者[15-19] 关注到不同的样本对属性重要 度评价的贡献是不同的，如王熙照等[15] 提出的 Kmeans 样本选择算法将远离类簇中心点的样本视 为重要的；随后 Xu 等 [19] 将这种方法应用到多标 记数据的维度压缩问题中。但他们在追求时间效 率的同时忽略了约简在测试集上的分类性能。 基于以上分析，笔者提出了一种基于样本一 致性原则的样本选择算法 (以下简称为一致性采 样)，一致性采样的主要思想为：1) 给定一个样本， 找到距离自己最近的邻居；2) 判断这一邻居是否 与自身属于同一类别，若属于同一类别，则将该 样本选中；3) 最后将所有选中的样本组成一个新 的数据集。 1 基础知识 Ø ··· ∀ 在粗糙集理论中，一个决策系统可表示为一 个二元组 DS=, U 是所有样本构成的 非空有限集合，即论域；AT 是所有条件属性的集 合；D 是决策属性的集合且 AT∩D= 。当 D 的取 值都为离散型时，可得 U/IND (D)={X1 , X2 , , Xq}， 其表示根据决策属性 D 所诱导出的论域上的划 分，对于 Xp∈U/IND(D), Xp 表示第 p 个决策类，其 中 [ x ] D 表示与 x 属于同一个决策类的样本的 集合。 定义 1 给定一个决策系统 DS, ∀ A ⊆ AT, 则邻 域关系定义为 NA = {(x, y) ∈ U ×U : r(x, y) ⩽ δ} (1) 其中， ∀ x, y∈U, r(x, y) 表示样本 x 与 y 之间的欧氏 距离，δ>0 称为邻域半径。 则由式 (1)，容易得到关于 A 样本 x 的邻域： δA (x) = {y|r(x, y) ⩽ δ} (2) ··· ∀ ⊆ ∀ 定义 2 给定一个决策系统 DS, U/IND(D)= {X1 , X2 , , Xq}, A AT, Xp∈U/IND(D), Xp 关于 A 的下近似集和上近似集分别定义为 NAXp = {x ∈ U|δA (x) ⊆ Xp} (3) NAXp = {x ∈ U|δA (x)∩ Xp , ϕ} (4) ··· ∀ ⊆ 定义 3 [20] 给定一个决策系统 DS, U/IND(D)= {X1 , X2 , , Xq}, A AT, D 关于 A 的近似质量定义 如下： γ(A,D)= ∪q p=1 NAXp |U| (5) 其中|U|表示集合 X 的基数。 显然 0≤γ(A, D)≤1 成立。γ(A, D) 表示根据条 件属性 A, 那些确定属于某一决策类别的样本占 总体样本的比例。 条件熵是属性约简中另外一种常用的度量准 则，它能反映条件属性相对于决策属性的鉴别能 力。根据不同的需求，很多学者设计并定义了多 种形式的条件熵[21-25] ，一种经典的形式可定义为： 定义 4 ∀ ⊆ [25] 给定一个决策系统 DS, A AT, D 关于 A 的条件熵定义如下： ENT(A,D) = − 1 |U| ∑ x∈U log |δA(x)∩[x]D| |U| (6) 显然，条件熵的值越小，条件属性相对于决策 属性鉴别能力越大。 2 属性约简 属性约简作为粗糙集领域的一个核心内容， 其主要目的是根据某一给定的约束条件来去除全 部属性中的冗余、不相关的属性。目前求解约简 的常用策略包括穷举式算法和启发式算法。虽然 前者可以得到一个数据中的所有约简，但当数据 维数急剧升高时，它的时间消耗随之增大，过大 的时间消耗导致算法并不适用于处理实际问题。 与穷举式算法不同，启发式算法因其较高的时间 效率得到了众多学者的青睐，它运用贪心策略，每 次迭代过程中其将属性重要度最大的属性加入到 第 6 期 高媛，等：面向一致性样本的属性约简 ·1171·
·1172· 智能系统学报 第14卷 潜在约简集合中，直至满足约束条件则终止算法。 学者的重视。如Yang与Yao2提出的集成选择 因此，接下来需要给出属性重要度的表达式。 器极大地丰富了约简的求解策略：随后，Li等2刃 Sig,(ai.A.D)=y(AUlal,D)-y(A.D)(7) 利用这一思想设计了基于调和平均的多准则属性 SigENT(ai,A,D)=ENT(A,D)-ENT(AU(ai),D)(8) 约简。Lu等进一步利用集成思想，将其扩展 对于近似质量（利用式(7）来计算属性重要 应用到半监督领域中。一般来说，多准则启发式 度)，a的重要度越大，表示a:对其值的提升效果 算法可由算法2实现。 越明显。而对于条件熵而言（利用式(8）来计算属 算法2多准则启发式算法 性重要度)，a,的重要度越大，则表示a,对其值的 输入决策系统DS=,半径6 降低效果越明显。 输出一个多准则约简：A 定义5给定一个决策系统DS,YA仁AT,A是 1)计算p(AT,D),p2(AT,D),,pm(AT,Di DS中的一个关于o的约简当且仅当： 2)A←-中 (1)p(4,D)满足约束条件： 3) (2)YA'≤A,(A',D)不满足约束条件。 (1)For1≤k≤m 在定义5中，“o”可以是“y”也可以是“ENT”。 Ha,∈AT-A,计算属性a,的重要度Sig,(a,A,D) 当=y时，约束条件可以定义为4，D)≥AT,D), 选出重要度最大的属性哈 它表示利用约简A中的属性计算的近似质量值应 End For 不低于利用全部属性(AT)计算的近似质量值；而 (2)在{，，…，}中选择一个出现频次最高 当O=ENT时，约束条件则定义为ENT(A,D)≤ 的属性b; ENT(AT,D),它表示利用约简A中的属性计算的 (3)A=AU{b} 条件熵值应不高于利用全部属性(AT)计算的条 (4)计算p(AD),p2(A,D),p(A,D) 件熵值。 4)如果对于任意的1≤k≤m),P(A,D)满足 算法1给出了一个求解定义5所示0约简的 约束条件，则直接转至步骤5)，否则转至步骤3)： 启发式框架型描述。 5)返回A。 算法1启发式算法 算法2的时间复杂度为O(mAT)。在每 输入决策系统DS=,半径6 次迭代过程，3)将m个准则下重要度最大的属性 输出一个关于0的约简：A 分别选择出来并记录每个属性出现的频次，选取 1)计算p(AT,D) 频次最高的属性加入到潜在约简集合中：1)如果 2)A←-φ 出现频次最高的属性是唯一的，则直接将其加入 3): 到潜在约简集合中；2)否则，出现频次最高的属 (I)Ya,eAT-A,计算属性a,的重要度Sig(an 性发生冲突情况，即两个或多个属性的频次同 A.D); 时达到最高，则需要进行选择，为了保证算法的 (2)选出一个重要度最大的属性b,令A=AU{b: 稳定性，将位置靠前的属性加入到潜在约简集 (3)计算p(A,D: 合中。 4)如果p(4,D)满足约束条件，则直接转至5) 5)返回A 3一致性采样约简 算法1的时间复杂度为OU·AT),其中 显然，第2节所示的两个算法都是基于扫描 为论域中样本数目，AT为条件属性数目。 数据中的全部样本来实现的。但当数据体量较大 算法1是基于单准则设计的，而运用基于单 时，这种求解策略的时间消耗较高。为了进一步 准则的算法得到的约简往往仅能满足一个约束条 压缩算法的时间消耗，可以将样本选择的方法引 件，而此约简结果可能无法满足其他约束条件。 入到约简求解过程中。不同的样本选择方法会选 例如：仅使用近似质量得到的约简满足自身的约 取不同的样本，进而产生不同的分类效果。本文 束条件，但它往往无法同时提高分类能力，这主 将一致性从样本间距离与样本的决策属性值角度 要是因为近似质量是用来描述数据中的确定性程 出发，目的是使得算法可以利用选择出的样本获 度，而与数据的分类关系不大。为了弥补这一局 取更高的分类精度。算法大致分为两个主要部 限，近年来，根据多准则设计的约简也开始受到 分：1)要全部样本组成的决策系统上进行采样处
潜在约简集合中，直至满足约束条件则终止算法。 因此，接下来需要给出属性重要度的表达式。 Sigγ (ai ,A,D) = γ(A∪{ai},D)−γ(A,D) (7) SigENT (ai ,A,D) = ENT(A,D)−ENT(A∪{ai},D) (8) 对于近似质量 (利用式 (7) 来计算属性重要 度)，ai 的重要度越大，表示 ai 对其值的提升效果 越明显。而对于条件熵而言 (利用式 (8) 来计算属 性重要度)，ai 的重要度越大，则表示 ai 对其值的 降低效果越明显。 定义 5 给定一个决策系统 DS, ∀ A ⊆ AT, A 是 DS 中的一个关于 φ 的约简当且仅当： (1) φ(A, D) 满足约束条件； (2) ∀ A' A ⊆ , φ(A', D) 不满足约束条件。 在定义 5 中，“φ”可以是“γ”也可以是“ENT”。 当 φ=γ 时，约束条件可以定义为 γ(A, D)≥γ(AT, D), 它表示利用约简 A 中的属性计算的近似质量值应 不低于利用全部属性 (AT) 计算的近似质量值；而 当 φ=ENT 时，约束条件则定义为 ENT(A, D)≤ ENT (AT, D), 它表示利用约简 A 中的属性计算的 条件熵值应不高于利用全部属性 (AT) 计算的条 件熵值。 算法 1 给出了一个求解定义 5 所示 φ 约简的 启发式框架型描述。 算法 1 启发式算法 输入 决策系统 DS=, 半径 δ 输出 一个关于 φ 的约简：A 1) 计算 φ(AT, D); 2) A←ϕ; 3)： (1) ∀ ai∈AT−A,计算属性 ai 的重要度 Sigφ (ai , A, D); (2) 选出一个重要度最大的属性 b, 令 A=A∪{b}; (3) 计算 φ(A, D); 4) 如果 φ(A, D) 满足约束条件，则直接转至 5) 5) 返回 A 算法 1 的时间复杂度为 O(|U| 2 ·|AT|2 )，其中 |U|为论域中样本数目，|AT|为条件属性数目。 算法 1 是基于单准则设计的，而运用基于单 准则的算法得到的约简往往仅能满足一个约束条 件，而此约简结果可能无法满足其他约束条件。 例如：仅使用近似质量得到的约简满足自身的约 束条件，但它往往无法同时提高分类能力，这主 要是因为近似质量是用来描述数据中的确定性程 度，而与数据的分类关系不大。为了弥补这一局 限，近年来，根据多准则设计的约简也开始受到 学者的重视。如 Yang 与 Yao[26] 提出的集成选择 器极大地丰富了约简的求解策略；随后，Li 等 [27] 利用这一思想设计了基于调和平均的多准则属性 约简。Liu 等 [21] 进一步利用集成思想，将其扩展 应用到半监督领域中。一般来说，多准则启发式 算法可由算法 2 实现。 算法 2 多准则启发式算法 输入 决策系统 DS=, 半径 δ 输出 一个多准则约简：A 1) 计算 φ ··· 1 (AT, D), φ2 (AT, D), , φm(AT, D); 2) A←ϕ; 3) (1) For 1 ≤ k ≤ m ∀ Sigφk (ai ,A,D) a j k ai∈AT−A，计算属性 ai 的重要度 ; 选出重要度最大的属性 ; End For a j 1 a j 2 , ··· a j (2) 在{ , , }m 中选择一个出现频次最高 的属性 b; (3) A=A∪{b}; (4) 计算 φ ··· 1 (A, D), φ2 (A, D), , φm(A, D); 4) 如果对于任意的 k(1≤k≤m), φk (A, D) 满足 约束条件，则直接转至步骤 5); 否则转至步骤 3); 5) 返回 A。 算法 2 的时间复杂度为 O(m·|U| 2 ·|AT|2 )。在每 次迭代过程，3) 将 m 个准则下重要度最大的属性 分别选择出来并记录每个属性出现的频次，选取 频次最高的属性加入到潜在约简集合中：1) 如果 出现频次最高的属性是唯一的，则直接将其加入 到潜在约简集合中；2) 否则，出现频次最高的属 性发生冲突情况，即两个或多个属性的频次同 时达到最高，则需要进行选择，为了保证算法的 稳定性，将位置靠前的属性加入到潜在约简集 合中。 3 一致性采样约简 显然，第 2 节所示的两个算法都是基于扫描 数据中的全部样本来实现的。但当数据体量较大 时，这种求解策略的时间消耗较高。为了进一步 压缩算法的时间消耗，可以将样本选择的方法引 入到约简求解过程中。不同的样本选择方法会选 取不同的样本，进而产生不同的分类效果。本文 将一致性从样本间距离与样本的决策属性值角度 出发，目的是使得算法可以利用选择出的样本获 取更高的分类精度。算法大致分为两个主要部 分：1) 要全部样本组成的决策系统上进行采样处 ·1172· 智 能 系 统 学 报 第 14 卷
第6期 高媛，等：面向一致性样本的属性约简 ·1173· 理以构建含有较少样本个数的新决策系统：2)随 (3)A=AU{b}; 后，将一致性采样的思想应用到属性约简的求解 (4)计算p1(A,D),p2(4,D),5pm(4,D)月 过程中。具体算法流程如下所示。 5)如果对于任意的1≤k≤m),p(A,D)满足 算法3一致性采样约简算法 约束条件，则直接转至步骤6)；否则转至步骤4)； 输入决策系统DS=,半径d: 6)返回A。 输出一个约简A。 算法3的时间复杂度为OU+mUT2AT)。 1) 其中，U为新的决策系统中样本的个数。步骤 (1)令U=0: 1为样本选择的过程，将一致性样本选择出来的 (2)yeU,计算样本之间距离(x,y): 时间复杂度为O)。而之后的步骤则是用启发 (3)对x,)进行排序； 式算法求解约简，由于使用的是新的决策系统， (4)取距离测试样本y最近的样本，若二者的 则时间复杂度为O(mUAT)。这里的启发式 决策值相同，则选中该测试样本并将其加入到中； 算法可以为单准则属性约简算法也可以为多准则 (⑤)将新选中的样本组成新的决策系统DS= 属性约简算法，当m=1时则简化为单准则属性约 : 简算法。换言之，无论单准则还是多准则约简算 2)在新的决策系统DS中计算p1(AT,D), 法，都可先经过采样后再根据具体需求设计相应 p2(AT,D),…,p(AT,D)月 的属性约简算法。 3)A←-0： 4) 4实验分析 (1)For1≤k≤m Ha∈AT-A,计算属性a,的重要度Sig,(a,A,D); 为了验证算法3的有效性，笔者从UCI数据 选出重要度最大的属性 集中选取了8组数据，数据的基本描述如表1所 End For 列。实验环境为PC机，双核2.60 GHz CPU, (2)在{d,}中选择一个出现频次最高的 8GB内存，windows 10操作系统，Matlab R2016a 属性b: 实验平台。 表1数据描述 Table 1 Data sets description D 数据集 样本数 属性数 决策类数 Gesture Phase Segmentation 9901 ⊙ 5 2 MAGIC Gamma Telescope 19020 11 2 QSAR Biodegradation 1055 41 2 4 Sonar 208 61 2 5 Statlog (German Credit Data) 1000 25 2 6 Ultrasonic Flowmeter Diagnostics 180 44 4 7 Wall-Following Robot Navigation Data 5466 25 4 8 Wine 178 13 3 实验采用了5折交叉验证的方法，并且选取 用A2中的属性计算分类精度；依次类推，第5次 了10个不同的半径6，其值分别为0.03,0.06，…， 使用UUU2U…UU,作为训练集求得约简A,使 0.3.5折交叉验证的具体实施过程是将实验数据 用U,作为测试集并在其中利用A中的属性计算 中的样本平均分成5份，即U,U2,U,U。第一 分类精度。 次使用U2 UU0...0U,作为训练集求得约简A1, 本组实验选取了近似质量、条件嫡以及多准 使用U,作为测试集并在其中利用A,中的属性计 则（同时满足近似质量和条件嫡的约束条件）作 算分类精度；第2次使用U,UU,U.UU,作为训 为约简的度量准则。实验将一致性采样属性约简 练集求得约简A2,使用U作为测试集并在其中利 算法与基于K-means采样I的属性约简算法（这
理以构建含有较少样本个数的新决策系统；2) 随 后，将一致性采样的思想应用到属性约简的求解 过程中。具体算法流程如下所示。 算法 3 一致性采样约简算法 输入 决策系统 DS=, 半径 δ； 输出 一个约简 A。 1) (1) 令 U'=Ø; (2) ∀ y∈U, 计算样本之间距离 r(x, y); (3) 对 r(x, y) 进行排序； (4) 取距离测试样本 y 最近的样本，若二者的 决策值相同，则选中该测试样本并将其加入到 U'中； (5) 将新选中的样本组成新的决策系统 DS'= ; ··· 2) 在新的决策系统 DS'中计算 φ1 (AT, D), φ2 (AT, D), , φm(AT, D); 3) A←Ø; 4) (1) For 1≤k≤m ∀ Sigφk (ai ,A,D) a j k ai∈AT−A，计算属性 ai 的重要度 ; 选出重要度最大的属性 ; End For a j 1 ··· a j (2) 在{ , , }m 中选择一个出现频次最高的 属性 b; (3) A=A∪{b}; (4) 计算 φ ··· 1 (A, D), φ2 (A, D), , φm(A, D); 5) 如果对于任意的 k(1≤k≤m), φk (A, D) 满足 约束条件，则直接转至步骤 6) ; 否则转至步骤 4) ; 6) 返回 A。 算法 3 的时间复杂度为 O(|U| 2 +m·|U'| 2 ·|AT|2 )。 其中，|U'|为新的决策系统中样本的个数。步骤 1 为样本选择的过程，将一致性样本选择出来的 时间复杂度为 O(|U| 2 )。而之后的步骤则是用启发 式算法求解约简，由于使用的是新的决策系统， 则时间复杂度为 O(m·|U'| 2 ·|AT|2 )。这里的启发式 算法可以为单准则属性约简算法也可以为多准则 属性约简算法，当 m=1 时则简化为单准则属性约 简算法。换言之，无论单准则还是多准则约简算 法，都可先经过采样后再根据具体需求设计相应 的属性约简算法。 4 实验分析 为了验证算法 3 的有效性，笔者从 UCI 数据 集中选取了 8 组数据，数据的基本描述如表 1 所 列。实验环境为 PC 机，双核 2.60 GHz CPU， 8 GB 内存，windows 10 操作系统，Matlab R2016a 实验平台。 表 1 数据描述 Table 1 Data sets description ID 数据集 样本数 属性数 决策类数 1 Gesture Phase Segmentation 9 901 19 5 2 MAGIC Gamma Telescope 19 020 11 2 3 QSAR Biodegradation 1 055 41 2 4 Sonar 208 61 2 5 Statlog (German Credit Data) 1 000 25 2 6 Ultrasonic Flowmeter Diagnostics 180 44 4 7 Wall-Following Robot Navigation Data 5 466 25 4 8 Wine 178 13 3 ··· ··· ··· 实验采用了 5 折交叉验证的方法，并且选取 了 10 个不同的半径 δ, 其值分别为 0.03，0.06， ， 0.3。5 折交叉验证的具体实施过程是将实验数据 中的样本平均分成 5 份，即 U1 , U2 , ∪ , U5。第一 次使用 U2∪U3∪ ∪U5 作为训练集求得约简 A1， 使用 U1 作为测试集并在其中利用 A1 中的属性计 算分类精度；第 2 次使用 U1∪U3∪…∪U5 作为训 练集求得约简 A2，使用 U2 作为测试集并在其中利 ··· 用 A2 中的属性计算分类精度；依次类推，第 5 次 使用 U1∪U2∪ ∪U4 作为训练集求得约简 A5，使 用 U5 作为测试集并在其中利用 A5 中的属性计算 分类精度。 本组实验选取了近似质量、条件熵以及多准 则 (同时满足近似质量和条件熵的约束条件) 作 为约简的度量准则。实验将一致性采样属性约简 算法与基于 K-means 采样[15] 的属性约简算法 (这 第 6 期 高媛，等：面向一致性样本的属性约简 ·1173·
·1174· 智能系统学报 第14卷 里K的取值等于数据的决策类数目)进行对比分 时，分别采用了邻域分类器NEC)2和SVM分类 析。在上述8组数据集上分别计算并比较了基于 器9，实验结果如图1、图2所示。 这3种约简的分类精度。其中，在计算分类精度 Gesture Phase Segmentation MAGIC Gamma Telescope 0.45 0.75 -B-KS-A OS-A 0.70 0.40 8 0.65 os-t 0.60 6 bB.. 0.55 0.50 0.30 0.45 g 0.03 0.12 0.21 0.30 0.03 0.12 0.21 0.30 (a)数据1 (b)数据2 QSAR Biodegradation Sonar 0.95 0.65 KS-A 0.90 KS 0.85 0 os 一一 0.80 G.e 0.75 0.55 0.70 0.65 0.50 .03 0.12 0.21 0.30 0.03 0.12 0.21 0.30 (c)数据3 (d数据4 Statlog(German Credit Data) Ultrasonic Flowmeter Diagnostics 0.72 0.55 0.50 0.71 0.45 0.40 KS-A OS 0.35 0.699 8意8 .0 0.30 0.68 0.25 0.03 0.12 0.21 0.30 0.03 0.12 0.21 0.30 (e)数据5 ()数据6 Wall-Following Robot Navigation Data Wine 0.65 -BKS-A 0.75r ®KS-A 0.60 OS-E 0.70 0.65 ☒0.55里6g￥一食：尚：---◆-* 0.60 0.55 D-- 0.45 --p 0.50 0.40 0.45 .03 0.12 0.21 0.30 0.03 0.12 0.21 0.30 (g)数据7 (h)数据8 图1邻域分类器下分类精度的对比 Fig.1 Comparisons among classification accuracies with using NEC
里 K 的取值等于数据的决策类数目) 进行对比分 析。在上述 8 组数据集上分别计算并比较了基于 这 3 种约简的分类精度。其中，在计算分类精度 时，分别采用了邻域分类器 (NEC)[28] 和 SVM 分类 器 [29] ，实验结果如图 1、图 2 所示。 0.03 0.12 0.21 0.30 0.30 0.35 0.40 0.45 分类精度 Gesture Phase Segmentation KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U 0.03 0.12 0.21 0.30 0.45 0.50 0.55 0.60 0.65 0.70 0.75 分类精度 MAGIC Gamma Telescope KS-A OS-A KS-E OS-E KS-U OS-U (a) 数据1 (b) 数据2 0.03 0.12 0.21 0.30 0.65 0.70 0.75 0.80 0.85 0.90 0.95 分类精度 QSAR Biodegradation 0.03 0.12 0.21 0.30 0.50 0.55 0.60 0.65 分类精度 Sonar (c) 数据3 (d) 数据4 0.03 0.12 0.21 0.30 0.68 0.69 0.70 0.71 0.72 分类精度 Statlog (German Credit Data) 0.03 0.12 0.21 0.30 0.25 0.30 0.35 0.40 0.45 0.50 0.55 分类精度 Ultrasonic Flowmeter Diagnostics (e) 数据5 (f) 数据6 0.03 0.12 0.21 0.30 0.40 0.45 0.50 0.55 0.60 0.65 分类精度 Wall-Following Robot Navigation Data 0.03 0.12 0.21 0.30 0.45 0.50 0.55 0.60 0.65 0.70 0.75 分类精度 Wine (g) 数据7 (h) 数据8 δ δ δ δ δ δ δ δ 图 1 邻域分类器下分类精度的对比 Fig. 1 Comparisons among classification accuracies with using NEC ·1174· 智 能 系 统 学 报 第 14 卷
第6期 高媛，等：面向一致性样本的属性约简 ·1175· Gesture Phase Segmentation MAGIC Gamma Telescope 0.720 0.76 0.74 0.715 0.72 0.710 0.70 0.68 0.705 0.66 0.700 0.64 KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U (a)数据1 (b)数据2 QSAR Biodegradation Sonar 0.86 0.84 0.70 T 0.82 0.80 0.65 08 0.76 0.60 0.74 0.72 0.55 0.70 KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U (c)数据3 (d)数据4 Statlog(German Credit Data) Ultrasonic Flowmeter Diagnostics 0.720 0.65 0.60 白 目 0.715 0.55 0.710 F0.50 0.45 0.705 0.40 0.35 0.700 0.30 KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U (e)数据5 ()数据6 Wall-Following Robot Navigation Data Wine 0.66 0.64 0.85 0.62 0.60 0.80 0.58 0.75 0.56 0.54 0.52 0.70 0.50 0.65 KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U (g)数据7 h)数据8 图2SVM分类器下分类精度的对比 Fig.2 Comparisons among classification accuracies with using SVM 在以下的结果图中，用KS-A、KS-E、KS-U分 的分类效果： 别表示基于K-means采样的近似质量约简、条件 2)在3个度量准则的比较中，利用条件嫡约 嫡约简、多准则约简，OS-A、OS-E、OS-U分别表 简能够大体上使得分类精度达到最高。此外，一 示基于一致性采样的近似质量约简、条件熵约 致性采样相较于K-means采样来说，当利用近似 简、多准则约简。 质量作为约简的度量准则时，约简在测试样本上 观察图1可以发现，在10个半径下，不难得 分类效果的提升最为明显。这主要是因为相较 出如下结论： 于K-means采样来说，一致性采样能够使得较多 1)相较于基于K-means采样的约简，利用基 的样本落入下近似集中，从而较大幅度地提升近 于一致性采样的约简在测试样本上可以获得更好 似质量的值，使得在约简迭代过程中，需要更多
KS-A OS-A KS-E OS-E KS-U OS-U 0.700 0.705 0.710 0.715 0.720 分类精度 Gesture Phase Segmentation KS-A OS-A KS-E OS-E KS-U OS-U 0.64 0.66 0.68 0.70 0.72 0.74 0.76 分类精度 MAGIC Gamma Telescope (a) 数据1 (b) 数据2 KS-A OS-A KS-E OS-E KS-U OS-U 0.70 0.72 0.74 0.76 0.78 0.80 0.82 0.84 0.86 分类精度 QSAR Biodegradation KS-A OS-A KS-E OS-E KS-U OS-U 0.55 0.60 0.65 0.70 分类精度 Sonar (c) 数据3 (d) 数据4 KS-A OS-A KS-E OS-E KS-U OS-U 0.700 0.705 0.710 0.715 0.720 分类精度 Statlog (German Credit Data) KS-A OS-A KS-E OS-E KS-U OS-U 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 分类精度 Ultrasonic Flowmeter Diagnostics (e) 数据5 (f) 数据6 KS-A OS-A KS-E OS-E KS-U OS-U 0.50 0.52 0.54 0.56 0.58 0.60 0.62 0.64 0.66 分类精度 Wall-Following Robot Navigation Data KS-A OS-A KS-E OS-E KS-U OS-U 0.65 0.70 0.75 0.80 0.85 分类精度 Wine (g) 数据7 (h) 数据8 图 2 SVM 分类器下分类精度的对比 Fig. 2 Comparisons among classification accuracies with using SVM 在以下的结果图中，用 KS-A、KS-E、KS-U 分 别表示基于 K-means 采样的近似质量约简、条件 熵约简、多准则约简，OS-A、OS-E、OS-U 分别表 示基于一致性采样的近似质量约简、条件熵约 简、多准则约简。 观察图 1 可以发现，在 10 个半径下，不难得 出如下结论： 1) 相较于基于 K-means 采样的约简，利用基 于一致性采样的约简在测试样本上可以获得更好 的分类效果； 2) 在 3 个度量准则的比较中，利用条件熵约 简能够大体上使得分类精度达到最高。此外，一 致性采样相较于 K-means 采样来说，当利用近似 质量作为约简的度量准则时，约简在测试样本上 分类效果的提升最为明显。这主要是因为相较 于 K-means 采样来说，一致性采样能够使得较多 的样本落入下近似集中，从而较大幅度地提升近 似质量的值，使得在约简迭代过程中，需要更多 第 6 期 高媛，等：面向一致性样本的属性约简 ·1175·
·1176· 智能系统学报 第14卷 的属性被加入到约简集合中。 因为多准则约简同时满足近似质量与条件熵的约 观察图2，不难得出如下结论： 束条件，较多的约束条件需要较多的属性才能完 1)由于SVM分类器在计算分类精度时没有 成目标。 使用半径这一参数，所以本文主要比较两者的分 观察图3可以发现，相较于K-means采样，利 类精度的平均值，可以发现相较于基于K-means 采样的约简，基于一致性采样的约简在测试样本 用一致性采样进行约简求解，大体上需要更多的 上能够提供较高的分类精度； 时间消耗，这主要是因为利用一致性采样得到的 2)在3个度量准则的比较中，利用多准则策 样本数量往往比利用K-means采样所得到的样本 略大体上可以使得分类精度达到最高，这主要是 数量多，这一事实可以参照表2。 200 Gesture Phase Segmentation 150 MAGIC Gamma Telescope 150 100 100 50 50 0-0--0-g-g-.0.0-6 .03 0.12 0.21 0.30 0.03 0.12 0.21 0.30 (a)数据1 (b)数据2 QSAR Biodegradation Sonar 0.8 A 6 5 0.6 41 0.4 0.2 8ge:8900中 803 0.12 021 0.30 0.12 0.21 0.30 (c)数据3 (d)数据4 Statlog(German Credit Data) Ultrasonic Flowmeter Diagnostics 1.0 0.20 KS-A OS-A 0.8 0.15 0.6 OS-U 0.10 OS-U ggg8 0.45 0-. 0.05 0.2 合：8：多苏业 0.03 0.12 0.21 0.30 0.12 0.21 0.30 (e)数据5 ()数据6 Wall-Following Robot Navigation Data Wine 100 0.08- 00-000 -- 0.06 ::0::来B::g5 60 -.-KS-E -KS-A - RS-6 0.04 OS-A 40 KS -e-OS-U 20 0.021 e-OS-U 0.12 0.21 0.30 86 0.12 0.21 0.30 (g)数据7 h)数据8 图3约简求解的时间消耗对比 Fig.3 Comparisons among elapsed time for computing reducts
的属性被加入到约简集合中。 观察图 2，不难得出如下结论： 1) 由于 SVM 分类器在计算分类精度时没有 使用半径这一参数，所以本文主要比较两者的分 类精度的平均值，可以发现相较于基于 K-means 采样的约简，基于一致性采样的约简在测试样本 上能够提供较高的分类精度； 2) 在 3 个度量准则的比较中，利用多准则策 略大体上可以使得分类精度达到最高，这主要是 因为多准则约简同时满足近似质量与条件熵的约 束条件，较多的约束条件需要较多的属性才能完 成目标。 观察图 3 可以发现，相较于 K-means 采样，利 用一致性采样进行约简求解，大体上需要更多的 时间消耗，这主要是因为利用一致性采样得到的 样本数量往往比利用 K-means 采样所得到的样本 数量多，这一事实可以参照表 2。 0.03 0.12 0.21 0.30 0 50 100 150 200 时间消耗/s 时间消耗/s 时间消耗/s 时间消耗/s 时间消耗/s 时间消耗/s 时间消耗/s 时间消耗/s Gesture Phase Segmentation 0.03 0.12 0.21 0.30 0 50 100 150 MAGIC Gamma Telescope (a) 数据1 (b) 数据2 0.03 0.12 0.21 0.30 0 1 2 3 4 5 6 7 QSAR Biodegradation 0.03 0.12 0.21 0.30 0 0.2 0.4 0.6 0.8 Sonar (c) 数据3 (d) 数据4 0.03 0.12 0.21 0.30 0.2 0.4 0.6 0.8 1.0 Statlog (German Credit Data) 0.03 0.12 0.21 0.30 0 0.05 0.10 0.15 0.20 Ultrasonic Flowmeter Diagnostics (e) 数据5 (f) 数据6 0.03 0.12 0.21 0.30 0 20 40 60 80 100 Wall-Following Robot Navigation Data 0.03 0.12 0.21 0.30 0 0.02 0.04 0.06 0.08 Wine (g) 数据7 (h) 数据8 KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U KS-A OS-A KS-E OS-E KS-U OS-U δ δ δ δ δ δ δ δ 图 3 约简求解的时间消耗对比 Fig. 3 Comparisons among elapsed time for computing reducts ·1176· 智 能 系 统 学 报 第 14 卷
第6期 高媛，等：面向一致性样本的属性约简 ·1177· 表2采样后数目 semble rough subspaces[J].Pattern recognition,2007, Table 2 Number of data after sample selection 40(12:3728-3739 K-means采样 一致性采样 [6]JIA Xiuyi,SHANG Lin,ZHOU Bing,et al.Generalized at- ID 样本数 (占总样本 (占总样本 tribute reduct in rough set theory[J].Knowledge-based sys- 比例/%) 比例%) tems,2016.91:204-218. 9901 3511(35.46) 7400(74.27) [7]YANG Xibei,QI Yunsong,SONG Xiaoning,et al.Test 、2 19020 6144(32.30) 12310(64.72) cost sensitive multigranulation rough set:model and min- imal cost selection[J].Information sciences,2013,250: 3 1055 347(32.89) 887(84.08) 184-199. 4 208 66(31.73) 143(68.75) [8]CHEN Degang,YANG Yanyan,DONG Ze.An increment- 1000 382(38.20) 537(53.70) al algorithm for attribute reduction with variable precision 6 180 4525.00) 133(73.88) rough sets[J].Applied soft computing,2016,45:129-149. [9]YANG Xibei,LIANG Shaochen,YU Hualong,et al. > 5466 2154(39.41) 3835(70.16) Pseudo-label neighborhood rough set:measures and attrib- 178 62(34.83) 136(76.41) ute reductions[J].International journal of approximate reasoning.2019,105:112-129. 5结束语 [10]FERONE A.Feature selection based on composition of rough sets induced by feature granulation[J].Internation- 为了提高约简的求解效率，本文提出一种基 al journal of approximate reasoning,2018,101:276-292. 于一致性原则的采样方法。进一步地，将基于一 [11]HART P.The condensed nearest neighbor rule 致性采样与基于聚类采样所求得的约简结果进行 (Corresp.)[J].IEEE transactions on information theor, 对比分析，实验结果表明，相较于聚类采样，一致 1968,14(3):515-516 性采样的约简结果可以有效地提升分类器的分类 [12]GATES G.The reduced nearest neighbor rule 性能。在这一工作的基础上，本文将就以下问题 (Corresp.)[J].IEEE transactions on information theory, 展开进一步探讨： 1972,18(3):431-433. 1)本文仅仅从整体角度考虑度量准则，在之 [13]TOMEK I.Two modifications of CNN[J].IEEE transac- 后的研究中可以进一步引入一些局部度量准则0 tions on systems,man,and cybernetics,1976,SMC- 如：局部近似质量、局部条件熵等。 6(11769-772. [14]ANGIULLI F.Fast nearest neighbor condensation for 2)本文算法及所使用的对比算法都仅仅是建 large data sets classification[J].IEEE transactions on 立在一种采样技术的基础上的，今后可以尝试使 knowledge and data engineering,2007,19(11): 用混合采样的方法刚以进一步地提升约简的性能。 1450-1464. 参考文献： [15]王熙照，王婷婷，翟俊海.基于样例选取的属性约简算 法).计算机研究与发展，2012,49(11)：2305-2310. [1]PAWLAK Z.Rough sets:Theoretical aspects of reasoning WANG Xizhao,WANG Tingting,ZHAI Junhai.An at- about data[M].Dordrecht:Kluwer Academic Publishers, tribute reduction algorithm based on instance selection[J]. 1991. Journal of computer research and development,2012, [2]PAWLAK Z.GRZYMALA-BUSSE J.SLOWINSKI R.et 4911):2305-2310. al.Rough sets[J].Communications of the ACM.1995. [16]ZHAI Junhai,WANG Xizhao,PANG Xiaohe.Voting- 38(11)88-95 based instance selection from large data sets with mapre- [3]CHEN Hongmei,LI Tianrui,LUO Chuan,et al.A de- duce and random weight networks[J].Information sci- cision-theoretic rough set approach for dynamic data min- ences..2016,367-368:1066-1077. ing[J].IEEE transactions on fuzzy systems,2015,23(6): [17]ZHAI Junhai.LI Ta.WANG Xizhao.A cross-selection 1958-1970 instance algorithm[J].Journal of intelligent and fuzzy sys- [4]WANG Changzhong,HU Qinghua,WANG Xizhao,et al. tems,2016,30(2):717-728. Feature selection based on neighborhood discrimination in- [18]杨习贝，颜旭，徐苏平，等.基于样本选择的启发式属性 dex[J].IEEE transactions on neural networks and learning 约简方法研究).计算机科学，2016,43(1)40-43， systems,.2018,29(7):2986-2999 YANG Xibei,YAN Xu,XU Suping,et al.New heuristic [5]HU Qinghua,YU Daren,XIE Zongxia,et al.EROS:En- attribute reduction algorithm based on sample
表 2 采样后数目 Table 2 Number of data after sample selection ID 样本数 K-means采样 (占总样本 比例/%) 一致性采样 (占总样本 比例/%) 1 9 901 3 511(35.46) 7 400(74.27) 2 19 020 6 144(32.30) 12 310(64.72) 3 1 055 347(32.89) 887(84.08) 4 208 66(31.73) 143(68.75) 5 1 000 382(38.20) 537(53.70) 6 180 45(25.00) 133(73.88) 7 5 466 2 154(39.41) 3 835(70.16) 8 178 62(34.83) 136(76.41) 5 结束语 为了提高约简的求解效率，本文提出一种基 于一致性原则的采样方法。进一步地，将基于一 致性采样与基于聚类采样所求得的约简结果进行 对比分析，实验结果表明，相较于聚类采样，一致 性采样的约简结果可以有效地提升分类器的分类 性能。在这一工作的基础上，本文将就以下问题 展开进一步探讨： 1) 本文仅仅从整体角度考虑度量准则，在之 后的研究中可以进一步引入一些局部度量准则[30] 如：局部近似质量、局部条件熵等。 2) 本文算法及所使用的对比算法都仅仅是建 立在一种采样技术的基础上的，今后可以尝试使 用混合采样的方法[31] 以进一步地提升约简的性能。 参考文献： PAWLAK Z. Rough sets: Theoretical aspects of reasoning about data[M]. Dordrecht: Kluwer Academic Publishers, 1991. [1] PAWLAK Z, GRZYMALA-BUSSE J, SLOWINSKI R, et al. Rough sets[J]. Communications of the ACM, 1995, 38(11): 88–95. [2] CHEN Hongmei, LI Tianrui, LUO Chuan, et al. A decision-theoretic rough set approach for dynamic data mining[J]. IEEE transactions on fuzzy systems, 2015, 23(6): 1958–1970. [3] WANG Changzhong, HU Qinghua, WANG Xizhao, et al. Feature selection based on neighborhood discrimination index[J]. IEEE transactions on neural networks and learning systems, 2018, 29(7): 2986–2999. [4] [5] HU Qinghua, YU Daren, XIE Zongxia, et al. EROS: Ensemble rough subspaces[J]. Pattern recognition, 2007, 40(12): 3728–3739. JIA Xiuyi, SHANG Lin, ZHOU Bing, et al. Generalized attribute reduct in rough set theory[J]. Knowledge-based systems, 2016, 91: 204–218. [6] 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. [7] CHEN Degang, YANG Yanyan, DONG Ze. An incremental algorithm for attribute reduction with variable precision rough sets[J]. Applied soft computing, 2016, 45: 129–149. [8] YANG Xibei, LIANG Shaochen, YU Hualong, et al. Pseudo-label neighborhood rough set: measures and attribute reductions[J]. International journal of approximate reasoning, 2019, 105: 112–129. [9] FERONE A. Feature selection based on composition of rough sets induced by feature granulation[J]. International journal of approximate reasoning, 2018, 101: 276–292. [10] HART P. The condensed nearest neighbor rule (Corresp.)[J]. IEEE transactions on information theor, 1968, 14(3): 515–516. [11] GATES G. The reduced nearest neighbor rule (Corresp.)[J]. IEEE transactions on information theory, 1972, 18(3): 431–433. [12] TOMEK I. Two modifications of CNN[J]. IEEE transactions on systems, man, and cybernetics, 1976, SMC- 6(11): 769–772. [13] ANGIULLI F. Fast nearest neighbor condensation for large data sets classification[J]. IEEE transactions on knowledge and data engineering, 2007, 19(11): 1450–1464. [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] ZHAI Junhai, WANG Xizhao, PANG Xiaohe. Votingbased instance selection from large data sets with mapreduce and random weight networks[J]. Information sciences, 2016, 367-368: 1066–1077. [16] ZHAI Junhai, LI Ta, WANG Xizhao. A cross-selection instance algorithm[J]. Journal of intelligent and fuzzy systems, 2016, 30(2): 717–728. [17] 杨习贝, 颜旭, 徐苏平, 等. 基于样本选择的启发式属性 约简方法研究 [J]. 计算机科学, 2016, 43(1): 40–43. YANG Xibei, YAN Xu, XU Suping, et al. New heuristic attribute reduction algorithm based on sample [18] 第 6 期 高媛，等：面向一致性样本的属性约简 ·1177·
·1178· 智能系统学报 第14卷 selection[J].Computer science,2016,43(1):40-43. [29]WANG Rui,LI Wei,LI Rui,et al.Automatic blur type [19]XU Suping,YANG Xibei,YU Hualong,et al.Multi-la- classification via ensemble SVM[J].Signal processing: bel learning with label-specific feature reduction[J]. image communication,2019,71:24-35. Knowledge-based systems,2016,104:52-61. [30]CHEN Degang,ZHAO Suyun.Local reduction of de- [20]GAO Yuan,CHEN Xiangjian,YANG Xibei,et al.Neigh- cision system with fuzzy rough sets[J].Fuzzy sets and borhood attribute reduction:a multicriterion strategy systems,,2010,161(13):1871-1883. based on sample selection[J].Information,2018,9(11): [31]孟军，张晶，姜丁菱，等.结合近邻传播聚类的选择性集 282. 成分类方法[J.计算机研究与发展，2018,55(5)： [21]LIU Keyu,YANG Xibei,YU Hualong,et al.Rough set 986-993. based semi-supervised feature selection via ensemble se- MENG Jun,ZHANG Jing,JIANG Dingling,et al.Select- lector[J].Knowledge-based systems,2019,165:282-296. ive ensemble classification integrated with affinity [22]DAI Jianhua,WANG Wentao,XU Qing,et al.Uncer- propagation clustering[J].Journal of computer research tainty measurement for interval-valued decision systems and development,2018,55(5):986-993. based on extended conditional entropy[J].Knowledge- based systems,2012,27:443-450. 作者简介： [23]ZHANG Xiao,MEI Changlin,CHEN Degang,et al.Fea- 高媛，女，1994年生，硕士研究 生，主要研究方向为粗糙集理论、机器 ture selection in mixed data:a method using a novel fuzzy 学习。 rough set-based information entropy[J].Pattern recogni- tion,2016,56:1-15. [24]LIN Jianhua.Divergence measures based on the Shannon entropy[J].IEEE transactions on information theory, 1991,37(1145-151. [25]HU Qinghua,CHE Xunjian,ZHANG Lei,et al.Rank en- 陈向坚，女，1983年生，副教授 博士，主要研究方向为模糊神经网络 tropy-based decision trees for monotonic classification[J]. 与智能控制。主持国家自然科学基金 IEEE transactions on knowledge and data engineering, 项目1项，发表学术论文20余篇。 2012,24(11:2052-2064. [26]YANG Xibei,YAO Yiyu.Ensemble selector for attribute reduction[J].Applied soft computing,2018,70:1-11. [27]LI Jingzheng,YANG Xibei,SONG Xiaoning,et al. 王平心，男，1980年生，副教授 Neighborhood attribute reduction:a multi-criterion ap- 博士，主要研究方向为矩阵分析与粒 proach[J].International journal of machine learning and 计算。主持国家自然科学基金项目 cybernetics,2019,10(4):731-742 1项，发表学术论文30余篇。 [28]HU Qinghua,YU Daren,XIE Zongxia.Neighborhood classifiers[J].Expert systems with applications,2008, 34(2):866-876
selection[J]. Computer science, 2016, 43(1): 40–43. XU Suping, YANG Xibei, YU Hualong, et al. Multi-label learning with label-specific feature reduction[J]. Knowledge-based systems, 2016, 104: 52–61. [19] GAO Yuan, CHEN Xiangjian, YANG Xibei, et al. Neighborhood attribute reduction: a multicriterion strategy based on sample selection[J]. Information, 2018, 9(11): 282. [20] LIU Keyu, YANG Xibei, YU Hualong, et al. Rough set based semi-supervised feature selection via ensemble selector[J]. Knowledge-based systems, 2019, 165: 282–296. [21] DAI Jianhua, WANG Wentao, XU Qing, et al. Uncertainty measurement for interval-valued decision systems based on extended conditional entropy[J]. Knowledgebased systems, 2012, 27: 443–450. [22] 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. [23] LIN Jianhua. Divergence measures based on the Shannon entropy[J]. IEEE transactions on information theory, 1991, 37(1): 145–151. [24] HU Qinghua, CHE Xunjian, ZHANG Lei, et al. Rank entropy-based decision trees for monotonic classification[J]. IEEE transactions on knowledge and data engineering, 2012, 24(11): 2052–2064. [25] YANG Xibei, YAO Yiyu. Ensemble selector for attribute reduction[J]. Applied soft computing, 2018, 70: 1–11. [26] LI Jingzheng, YANG Xibei, SONG Xiaoning, et al. Neighborhood attribute reduction: a multi-criterion approach[J]. International journal of machine learning and cybernetics, 2019, 10(4): 731–742. [27] HU Qinghua, YU Daren, XIE Zongxia. Neighborhood classifiers[J]. Expert systems with applications, 2008, 34(2): 866–876. [28] WANG Rui, LI Wei, LI Rui, et al. Automatic blur type classification via ensemble SVM[J]. Signal processing: image communication, 2019, 71: 24–35. [29] CHEN Degang, ZHAO Suyun. Local reduction of decision system with fuzzy rough sets[J]. Fuzzy sets and systems, 2010, 161(13): 1871–1883. [30] 孟军, 张晶, 姜丁菱, 等. 结合近邻传播聚类的选择性集 成分类方法 [J]. 计算机研究与发展, 2018, 55(5): 986–993. MENG Jun, ZHANG Jing, JIANG Dingling, et al. Selective ensemble classification integrated with affinity propagation clustering[J]. Journal of computer research and development, 2018, 55(5): 986–993. [31] 作者简介： 高媛，女，1994 年生，硕士研究 生，主要研究方向为粗糙集理论、机器 学习。 陈向坚，女，1983 年生，副教授， 博士，主要研究方向为模糊神经网络 与智能控制。主持国家自然科学基金 项目 1 项，发表学术论文 20 余篇。 王平心，男，1980 年生，副教授， 博士，主要研究方向为矩阵分析与粒 计算。主持国家自然科学基金项目 1 项，发表学术论文 30 余篇。 ·1178· 智 能 系 统 学 报 第 14 卷
