基于协同进化机制的欠采样方法

D0I:10.13374/.issn1001-053x.2011.12.020 第33卷第12期 北京科技大学学报 Vol.33 No.12 2011年12月 Journal of University of Science and Technology Beijing Dec.2011 基于协同进化机制的欠采样方法 翟云12)✉杨炳儒) 王树鹏》张德政》安冰” 1)聊城大学计算机学院，聊城2520592)北京科技大学计算机与通信工程学院，北京100083 3)中国科学院计算技术研究所，北京100190 ☒通信作者，E-mail:yunfei_.2001_1@yahoo.com.cn 摘要针对非平衡数据集分类中“少数类样本精度难以提高”这一瓶颈问题，提出了一种基于协同进化机制的欠采样方法. 此方法将少数类样本与多数类样本划分为两类种群，采用种群协同进化原理，利用提出的动态交叉变异算子自适应协同进化 过程，实现种群间自动调节和自动适应.仿真试验结果表明，此采样方法增强了局部随机搜索能力，改善了种群的分布特性， 加强了算法的全局收敛能力，在不降低多数类样本分类性能的基础上有效提高了少数类样本的精度.与其他经典重采样方法 相比，本文办法抗噪能力好，具有更强的鲁棒性. 关键词非平衡数据集；分类；采样；协同进化；自适应算法 分类号TP181 Under-sampling method based on cooperative co-evolutionary mechanism ZHAI Yun'2☒，YANG Bing-u,WANG Shu-peng2》,ZHANG De--heng2,AN Bing' 1)College of Computer Science,Liaocheng University,Liaocheng 252059,China 2)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China 3)Institute of Computer Technology,China Academy of Sciences,Beijing 100190,China Corresponding author,E-mail:yunfei_2001_1@yahoo.com.cn ABSTRACT For the bottleneck of improving the accuracy of minority class samples within the paradigm of imbalanced datasets,a novel under-sampling method based on the cooperative co-evolutionary mechanism was presented in this paper.During the employment of the method,the majority and the minority samples were divided into two populations,which adopted the cooperative co-evolutionary mechanism,dynamically adaptive crossovers and mutation operators to automatically adjust the evolution process within populations. Simulation results prove that the method enhances the capacity of local search,improves the distribution characteristics of populations and strengthens the capacity of global convergence.Moreover,the method notably improves the accuracy of the minority samples with- out degrading that of the majority ones.Compared to other classical resampling methods,the method shows good noise immunity with more powerful robustness. KEY WORDS imbalanced datasets;classification:sampling:cooperative co-evolution:adaptive algorithms 在两分类数据集中，当其中一类样本数量相当 处理非平衡数据集分类问题的方法在样本层次归为 少时被称为少数类(minority class),而另一类则被 两类：过采样技术和欠采样技术.尽管文献]论证 称为多数类(majority class),具有这样特征的两分 了过采样方法的有效性，但Drummond认为，欠采样 类数据集则被称为非平衡数据集，该分类问题被称 技术在多数时间优于过采样技术回.此外，文献 作非平衡数据集分类问题，少数类样本和多数类样 B]提出了一种基于聚类的欠采样方法，该方法选 本分别被称为正样本（positive examples)和负样本 择具有代表性的训练样本来提高少数类样本精度 (negative examples).随着研究的不断深入，界内把 Kim提出了一种基于自组织映射的欠采样技术， 收稿日期：2010-12-10 基金项目：国家高技术研究发展计划重大专项(2009AA01403):国家自然科学基金资助项目(61003260：60875029：61070101)

第 33 卷 第 12 期 2011 年 12 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 33 No． 12 Dec． 2011 基于协同进化机制的欠采样方法 翟 云1，2) 杨炳儒2) 王树鹏3) 张德政2) 安 冰1) 1) 聊城大学计算机学院，聊城 252059 2) 北京科技大学计算机与通信工程学院，北京 100083 3) 中国科学院计算技术研究所，北京 100190 通信作者，E-mail: yunfei_2001_1@ yahoo． com． cn 摘 要 针对非平衡数据集分类中“少数类样本精度难以提高”这一瓶颈问题，提出了一种基于协同进化机制的欠采样方法． 此方法将少数类样本与多数类样本划分为两类种群，采用种群协同进化原理，利用提出的动态交叉变异算子自适应协同进化 过程，实现种群间自动调节和自动适应． 仿真试验结果表明，此采样方法增强了局部随机搜索能力，改善了种群的分布特性， 加强了算法的全局收敛能力，在不降低多数类样本分类性能的基础上有效提高了少数类样本的精度． 与其他经典重采样方法 相比，本文办法抗噪能力好，具有更强的鲁棒性． 关键词 非平衡数据集; 分类; 采样; 协同进化; 自适应算法 分类号 TP181 Under-sampling method based on cooperative co-evolutionary mechanism ZHAI Yun1，2) ，YANG Bing-ru2) ，WANG Shu-peng3) ，ZHANG De-zheng2) ，AN Bing1) 1) College of Computer Science，Liaocheng University，Liaocheng 252059，China 2) School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China 3) Institute of Computer Technology，China Academy of Sciences，Beijing 100190，China Corresponding author，E-mail: yunfei_2001_1@ yahoo． com． cn ABSTRACT For the bottleneck of improving the accuracy of minority class samples within the paradigm of imbalanced datasets，a novel under-sampling method based on the cooperative co-evolutionary mechanism was presented in this paper． During the employment of the method，the majority and the minority samples were divided into two populations，which adopted the cooperative co-evolutionary mechanism，dynamically adaptive crossovers and mutation operators to automatically adjust the evolution process within populations． Simulation results prove that the method enhances the capacity of local search，improves the distribution characteristics of populations and strengthens the capacity of global convergence． Moreover，the method notably improves the accuracy of the minority samples with￾out degrading that of the majority ones． Compared to other classical resampling methods，the method shows good noise immunity with more powerful robustness． KEY WORDS imbalanced datasets; classification; sampling; cooperative co-evolution; adaptive algorithms 收稿日期: 2010--12--10 基金项目: 国家高技术研究发展计划重大专项( 2009AA01403) ; 国家自然科学基金资助项目( 61003260; 60875029; 61070101) 在两分类数据集中，当其中一类样本数量相当 少时被称为少数类( minority class) ，而另一类则被 称为多数类( majority class) ，具有这样特征的两分 类数据集则被称为非平衡数据集，该分类问题被称 作非平衡数据集分类问题，少数类样本和多数类样 本分别被称为正样本( positive examples) 和负样本 ( negative examples) ． 随着研究的不断深入，界内把 处理非平衡数据集分类问题的方法在样本层次归为 两类: 过采样技术和欠采样技术． 尽管文献［1］论证 了过采样方法的有效性，但 Drummond 认为，欠采样 技术在多数时间优于过采样技术［2］． 此外，文献 ［3］提出了一种基于聚类的欠采样方法，该方法选 择具有代表性的训练样本来提高少数类样本精度． Kim 提出了一种基于自组织映射的欠采样技术［4］． DOI:10.13374/j.issn1001-053x.2011.12.020

第12期 翟云等：基于协同进化机制的欠采样方法 ·1551· 文献5]提出了EasyEnsemble和BalanceCascade两 群体，每个子群体代表求解问题的一个子目标，所有 种策略作为欠采样学习的方法.尽管上述欠采样技 子群体在独立进化的同时，子群体之间基于信息迁 术在一定程度上解决了非平衡数据集分类问题，但 移与知识共享，共同进化.最常见的协同进化模型 仍存在若干亟需改进之处：(1)欠采样技术由于丢 是邻域模型（neighborhood model)与孤岛模型 弃分类过程中部分潜在的重要数据而可能会影响分 (island model).这两种模型将群体中的个体划分为 类器的性能；(2)传统的欠采样方法一般通过各种 若干子群体，每一子群体代表解空间中一个子区域 策略在多数类样本中选取与少数类样本等同数量的 (子空间)，其中每一个体代表问题的一个解因.每 样本，实现样本集数量平衡，进而达到提高少数类样 一个子群体用单独的种群演化，问题的解由来自不 本精度之目的，但这些方法带有极大的随机性和偶 同种群的个体组成，通过问题分解，搜索空间变小， 然性，而且对分类器依赖性强，移植性能较差，泛化 更容易维持多样性.在协同进化过程中，假设一个 能力有限：(3)传统的欠采样方法往往使用确定性 待求解问题的解空间被映射为一个包含m个个体 的采样技术，即仅简单地通过随机选取部分多数类 的群体，其中每一个体均由一个n维向量表示，则 样本达到样本类间数量平衡的目的，这种方法往往 群体中所有个体划分为个一维向量个体，然后 有可能使得分类精度永远达不到最优点，因而限制 同一分量方向上的m个一维向量相互组合，从而 了算法的应用范围. 形成n个子群体.此时每个子群体并不能独立完 协同进化机制属于一种自适应概率搜索技术， 成求解优化问题，必须由来自n个不同子群体中 随着进化的不断进行，新群体中总会产生更多性能 的n个个体共同组合构成.因此在协同进化过程 优良的个体，而这些个体将更有助于提升整体分类 中，所有子群体必须进行相互协调，以提高各自和 精度.而且在样本分类过程中，样本并非孤立存在 全局的性能 的，而是与其他样本或多或少存在某种关联（亲和 或排斥)，进而从宏观上表现出样本子集对整体样 2基于协同进化机制的欠采样方法 本分类精度的影响.基于此，笔者提出了一种基于 2.1种群划分 协同进化机制的欠采样方法，主要思想是把多数类 定义1训练样本集Ω中，多数类样本和少数 样本和少数类样本视为两个种群，根据需要将多数 类样本规模分别为M和N,把M个多数类样本组成 类样本进而划分为若干子种群，在协同进化框架下 的种群称作多数类样本群R,由N个少数类样本组 实现多种群的协同进化，在以不牺牲多数类样本精 成的种群称作少数类样本群X.则2=RUX,R∩ 度的前提下，提高了少数类样本的精度，进而提升了 X=O.在保持样本分布前提下，把多数类样本群 数据集整体分类性能. R分为n个规模相等的子集，记作D,D2,,Dn,则 1协同进化机制 有R=UD 协同进化是模仿自然界生态系统中物种间的进 定义2在协同进化过程中，由每个样本子集 化机制而得到的进化计算思想，它借鉴了种群协同 D构成的种群称作样本种群，i=1,2,,n,种群中 原理，实现了种群间的自动调节和自动适应.所谓 每个元素称为样本染色体（样本个体）.少数类样本 协同进化，是指将目标空间中的群体划分为若干子 群公构成一个独立而又特殊的样本种群 样本 0100101.0 D 本 11010011 样 00001111 样本： 0000100.1 多数类划分子集 构造染色体 形成样本子群个 样木 样本 样本- 10101D1.1 样 1000111.0 D - 样本 10111D11 10011111 D. 图1样本子群划分 Fig.1 Division of sample sub-populations

第 12 期 翟 云等: 基于协同进化机制的欠采样方法 文献［5］提出了 EasyEnsemble 和 BalanceCascade 两 种策略作为欠采样学习的方法． 尽管上述欠采样技 术在一定程度上解决了非平衡数据集分类问题，但 仍存在若干亟需改进之处: ( 1) 欠采样技术由于丢 弃分类过程中部分潜在的重要数据而可能会影响分 类器的性能; ( 2) 传统的欠采样方法一般通过各种 策略在多数类样本中选取与少数类样本等同数量的 样本，实现样本集数量平衡，进而达到提高少数类样 本精度之目的，但这些方法带有极大的随机性和偶 然性，而且对分类器依赖性强，移植性能较差，泛化 能力有限; ( 3) 传统的欠采样方法往往使用确定性 的采样技术，即仅简单地通过随机选取部分多数类 样本达到样本类间数量平衡的目的，这种方法往往 有可能使得分类精度永远达不到最优点，因而限制 了算法的应用范围． 协同进化机制属于一种自适应概率搜索技术， 随着进化的不断进行，新群体中总会产生更多性能 优良的个体，而这些个体将更有助于提升整体分类 精度． 而且在样本分类过程中，样本并非孤立存在 的，而是与其他样本或多或少存在某种关联( 亲和 或排斥) ，进而从宏观上表现出样本子集对整体样 本分类精度的影响． 基于此，笔者提出了一种基于 协同进化机制的欠采样方法，主要思想是把多数类 样本和少数类样本视为两个种群，根据需要将多数 类样本进而划分为若干子种群，在协同进化框架下 实现多种群的协同进化，在以不牺牲多数类样本精 度的前提下，提高了少数类样本的精度，进而提升了 数据集整体分类性能． 图 1 样本子群划分 Fig． 1 Division of sample sub-populations 1 协同进化机制 协同进化是模仿自然界生态系统中物种间的进 化机制而得到的进化计算思想，它借鉴了种群协同 原理，实现了种群间的自动调节和自动适应． 所谓 协同进化，是指将目标空间中的群体划分为若干子 群体，每个子群体代表求解问题的一个子目标，所有 子群体在独立进化的同时，子群体之间基于信息迁 移与知识共享，共同进化． 最常见的协同进化模型 是邻 域 模 型 ( neighborhood model ) 与 孤 岛 模 型 ( island model) ． 这两种模型将群体中的个体划分为 若干子群体，每一子群体代表解空间中一个子区域 ( 子空间) ，其中每一个体代表问题的一个解［6］． 每 一个子群体用单独的种群演化，问题的解由来自不 同种群的个体组成，通过问题分解，搜索空间变小， 更容易维持多样性． 在协同进化过程中，假设一个 待求解问题的解空间被映射为一个包含 m 个个体 的群体，其中每一个体均由一个 n 维向量表示，则 群体中所有个体划分为 n 个一维向量个体，然后 同一分量方向上的 m 个一维向量相互组合，从而 形成 n 个子群体． 此时每个子群体并不能独立完 成求解优化问题，必须由来自 n 个不同子群体中 的 n 个个体共同组合构成． 因此在协同进化过程 中，所有子群体必须进行相互协调，以提高各自和 全局的性能． 2 基于协同进化机制的欠采样方法 2. 1 种群划分 定义 1 训练样本集 Ω 中，多数类样本和少数 类样本规模分别为 M 和 N，把 M 个多数类样本组成 的种群称作多数类样本群 R，由 N 个少数类样本组 成的种群称作少数类样本群． 则 Ω = R∪，R∩  = ． 在保持样本分布前提下，把多数类样本群 R 分为 n 个规模相等的子集，记作 D1，D2，…，Dn，则 有 R = ∪ n i = 1 Di ． 定义 2 在协同进化过程中，由每个样本子集 Di 构成的种群称作样本种群，i = 1，2，…，n，种群中 每个元素称为样本染色体( 样本个体) ． 少数类样本 群构成一个独立而又特殊的样本种群． ·1551·

·1552· 北京科技大学学报 第33卷 如图1所示，一个样本染色体有r个基因组成， 本组合种群进化I代，由于样本种群和样本组合种 每个基因表示一个样本，当基因位为1时，说明该样 群内在的关联性，使得它们一方面独立完成各自种 本被选中参与进化过程，当基因位为0时，说明该样 群内的进化过程，同时发生协同进化，两者的关系如 本未被选中.由图2可知，样本种群SbP:对应着 图2所示.进化起始，全部样本染色体基因位全部 由m个这样的样本染色体构成的样本子集D 置1，随着进化过程的深入，选择出的部分具有代表 定义3对d:∈SubP:,i=1,2,…,n,令 性的精英样本染色体基因位置1，而未被选中的基 ComP,=出d对i≠j,d≠d5,则称CONM=NU 因位置0.考虑到此类样本数量较少，故使其所有样 本均参与进化，因此在进化过程中这部分染色体基 UComP:为样本组合种群 = 因位保持不变 在整个协同进化过程中，样本种群进化L代，样 #1 #2 SubP 5.11.4.…23 10.12,41,…6 7.18.6,…29 组合#1 21 31 Min 果”” y #1 2 并m 组合# SubP 15.9.22.…43 41,16.2.…5 5,23.1.7 7 组合# Min #1 #2 #m Suhp 33.12.5.…23 43.31,4,…2 9.11.47.…13 所有少数类样本 图2双群协同进化机制 Fig.2 Cooperative Co-evolutionary mechanism between two populations 2.2适应度函数 j个个体的适应度；(2)Reduction(SubP)为SubP: 基于协同进化机制的欠采样方法(under-sam- 第j个个体的压缩率，记为Reduction(SubP,)= pling method based on cooperative co-evolutionary mechanism,UMCCM)既考虑到了少数类样本的分 1SbP,式中1 SSubP,I为SubP,中染色体基因位 ISSubP,I 类精度，同时力图通过在多数类样本中遴选出具有 为1的个数，即选中的样本数目，ISubP,I为SubP 代表性的部分样本参与协同进化，这部分样本能充 中所有样本个数：(3)Pre(SubP)为SubP:的第j个 分体现出多数类样本集的整体特征，从而使用它们 个体的分类精度，即在SubP,中，仅仅利用选中的 进行分类时不仅不会降低分类性能，反而通过精简 ISubP,I个样本去预测该子种群全体样本的精度； 搜索空间，进而提高搜索效率.基于此，适应度函数 (4)Difference(SubP)为SubP,的第j个个体参与和 主要考虑以下因素.(1)少数类样本分类精度.非 未参与某一组合两种情况下适应度的差值，表示为 平衡数据分布环境下，如何通过有效处理样本集使 1 不同样本数量趋于平衡，从而在不降低多数类样本 Diference(sbr,）=7A IFitness(Comn）- 分类精度的前提下尽可能地提高少数类样本精度是 Fitnesst(Comm）l (2) 最终目标.(2)对多数类样本而言，主要考虑分类精 式中：Fitnesswih(Coma)为SubP:的第j个个体参与 度、压缩率和区分度三个性能指标，采用以下适应度 该组合时的适应度；Fitness仙ut(（Comm）为SubP:的 函数对多数类样本种群进化性能评估 第j个个体未参与该组合时的适应度.当Difference Fitness (SubP)=aReduction(SubP)+ (SubP:)小于区分度阈值入时，说明该个体对整体分类 B-Pre(SubP)+yDifference(SubP) (1) 精度贡献不大，可将其从所有参与的组合中删除 式中，a+B+y=L.对式(1)作如下说明：(1)Fitness 基于以上分析，采用以下适应度函数作为对整 (SubP)为样本子集D:对应的样本种群SubP,的第 体性能的评估：

北 京 科 技 大 学 学 报 第 33 卷 如图 1 所示，一个样本染色体有 r 个基因组成， 每个基因表示一个样本，当基因位为 1 时，说明该样 本被选中参与进化过程，当基因位为 0 时，说明该样 本未被选中． 由图 2 可知，样本种群 SubPi 对应着 由 m 个这样的样本染色体构成的样本子集 Di ． 定义 3 对 d' i ∈ SubPi，i = 1，2，…，n，令 ComPi = ∪ n i = 1 d' i，对i≠j，d' i ≠d' j ，则称 COM = ∪ ∪ m i = 1 ComPi为样本组合种群． 在整个协同进化过程中，样本种群进化 L 代，样 本组合种群进化 I 代，由于样本种群和样本组合种 群内在的关联性，使得它们一方面独立完成各自种 群内的进化过程，同时发生协同进化，两者的关系如 图 2 所示． 进化起始，全部样本染色体基因位全部 置 1，随着进化过程的深入，选择出的部分具有代表 性的精英样本染色体基因位置 1，而未被选中的基 因位置 0. 考虑到此类样本数量较少，故使其所有样 本均参与进化，因此在进化过程中这部分染色体基 因位保持不变． 图 2 双群协同进化机制 Fig． 2 Cooperative Co-evolutionary mechanism between two populations 2. 2 适应度函数 基于协同进化机制的欠采样方法( under-sam￾pling method based on cooperative co-evolutionary mechanism，UMCCM) 既考虑到了少数类样本的分 类精度，同时力图通过在多数类样本中遴选出具有 代表性的部分样本参与协同进化，这部分样本能充 分体现出多数类样本集的整体特征，从而使用它们 进行分类时不仅不会降低分类性能，反而通过精简 搜索空间，进而提高搜索效率． 基于此，适应度函数 主要考虑以下因素． ( 1) 少数类样本分类精度． 非 平衡数据分布环境下，如何通过有效处理样本集使 不同样本数量趋于平衡，从而在不降低多数类样本 分类精度的前提下尽可能地提高少数类样本精度是 最终目标． ( 2) 对多数类样本而言，主要考虑分类精 度、压缩率和区分度三个性能指标，采用以下适应度 函数对多数类样本种群进化性能评估． Fitness( SubPij ) = α·Reduction( SubPij ) + β·Pre( SubPij ) + γ·Difference( SubPij ) ( 1) 式中，α + β + γ = 1. 对式( 1) 作如下说明: ( 1) Fitness ( SubPij ) 为样本子集 Di 对应的样本种群 SubPi 的第 j 个个体的适应度; ( 2) Reduction( SubPij ) 为 SubPi 第 j 个个体的压缩率，记 为 Reduction ( SubPij ) = | SSubPi | | SubPi | ，式中 | SSubPi | 为 SubPi 中染色体基因位 为 1 的个数，即选中的样本数目，| SubPi | 为 SubPi 中所有样本个数; ( 3) Pre( SubPij ) 为 SubPi 的第 j 个 个体的分类精度，即在 SubPi 中，仅仅利用选中的 | SubPi |个样本去预测该子种群全体样本的精度; ( 4) Difference( SubPij ) 为 SubPi 的第 j 个个体参与和 未参与某一组合两种情况下适应度的差值，表示为 Difference( SubPij ) = 1 l ∑ l m = 1 | Fitnesswith ( Comim ) － Fitnesswithout ( Comim ) | ( 2) 式中: Fitnesswith ( Comim ) 为 SubPi 的第 j 个个体参与 该组合时的适应度; Fitnesswithout ( Comim ) 为 SubPi 的 第 j 个个体未参与该组合时的适应度． 当 Difference ( SubPij ) 小于区分度阈值 λ 时，说明该个体对整体分类 精度贡献不大，可将其从所有参与的组合中删除． 基于以上分析，采用以下适应度函数作为对整 体性能的评估: ·1552·

第12期 翟云等：基于协同进化机制的欠采样方法 ·1553· Fitness (Com,)=a'.Prei (Com,)+B'Pre(Com,) 概率P。是决定算法跳出局部最优解的一个关键因 (3) 素，如果取值过大，遗传算法会变成随机搜索方法， 对式(3)说明如下：(1)Fitness(Com:)表示在进化过 而P。较小，则不宜产生新的个体，影响了个体的多 程中第i个组合ComP:的适应度，Fitness(Com;)越 样性.为此，笔者提出一种自适应交叉变异算子，使 大，表示该组合对进化环境适应程度越高：(2)Prein P。和P能随适应度自动改变.具体做法为：当种 表示在组合ComP,中，少数类样本的分类精度；(3) 群收敛时，减小P。、增大P,即降低交叉概率，提高 Pre(Com,)表示在组合ComP,中，多数类样本的 变异概率，以保持个体的多样性，同时避免了种群早 分类精度：(4)α和B是权重因子，°+B=1.为提 熟；当种群个体发散时，增大P。,减小P,即提高交 高少数类样本分类精度，在协同进化过程中可适当 叉概率，降低变异概率，使种群趋于收敛 提高α值，对少数类样本进行合理偏置. 1 11 Pei =k +2了 综上所述，式(1)体现了欠采样的思想，但这种 1+exp [2 Fitness;Fitness,)] 欠采样不是随机的，而是综合考虑到了压缩率、精度 (5) 和区分度三个性能指标，从而可以确保找到多数类 1 (6) 样本的最优组合.式(3)则可确保两类样本是内在 Pk+exp (Fitness,-Fitness)] 统一的整体，在进化过程中体现出一种协同关系，从 式(5)和式(6)中，P.和P分别为第i个种群的交 而确保少数类样本精度的提高不会以降低多数类样 叉概率和变异概率，Fitness,为适应度大于该种群个 本精度为代价. 体平均适应度的个体的平均适应度，Fitness,为适应 2.3自适应进化算子 度小于该种群个体平均适应度的所有个体的平均适 文献]己经证明，对于任意初始种群，经过有 应度.调节因子k,k3,k,>0,k2<0.由于4= 限次迭代，由选择算子按适应度进行重复选择，最终 Fitness,-Fitness,2≥0，所以P.取值范围在0.5，l] 可以使得全局寻优概率密度在评价函数的峰值处不 之间，P取值范围在D,0.5].从式(5)和式(6)可 断增强，并收敛到最大适应度个体点.UMCCM在整 知，P,和P根据△的变化动态地自适应调整，△越 个协同进化中，样本种群进化L代，样本组合种群进 大，说明种群越发散，此时P会增大，P会变小，反 化I代，两个种群按照遗传算法进行进化.考虑到 之亦然 样本组合种群在变异过程中会对样本种群产生重大 可见，自适应策略能使P。和P在保持种群多 影响，在生成新组合过程中，采用稳定态遗传算法 样性的同时，保证了算法的收敛性 (steady-state genetic algorithm)图，保证了样本种群 2.3.2样本组合种群的进化过程 的进化速度快于样本组合种群. 样本组合种群进化过程中，个体选择亦采用轮 2.3.1样本种群的进化过程 盘赌选择方法，对所选个体进行两点交叉.如图2 (1)选择：采用轮盘赌选择方法，即按照适应度 所示，交叉和变异均发生在样本种群.例如，对第 比例选择样本.对于给定的规模为m的群体G= 个组合按概率P进行交叉时，将对所选个体在样本 {x1,x2,…,xm},样本x:的适应度为f,则x:被选择 种群中对应的两个个体（按轮盘赌选择方法选择） 的概率为 进行交叉.此时进行双替代：一方面，交叉生成的个 体替代该样本种群中适应度最差的个体；另一方面， P= (4) 该个体替代组合种群中对应的个体.可见，样本组 i=1 合种群的交叉过程对两个种群同时产生了影响：反 可见，适应度较高的样本，由于在轮盘中占有较大的 之，样本种群变异过程中，产生的个体同时也进行双 份额，被选中的机会也响应较大，它的遗传因子就会 替代。这种机制使得随着进化的不断进行，新群体 在种群中扩大. 中总会产生更多性能优良的个体，而这些个体将更 (2)交叉和变异：交叉概率P。和变异概率P 有助于提升少数类样本的分类精度.基于此，UMC- 在影响进化行为和性能方面起到了关键作用，直接 CM协同机制算法描述如下 影响到算法的收敛性.P。越大，新样本产生的速度 输入：训练集S={(x,y1）,(x2y2),,（xn, 就越快，但P。过大时进化模式被破坏的可能性也越 y）},近邻数k,种群迭代数L,L. 大，使得高适应度的个体结构很快被破坏：而P。过 输出：少数类样本精度Premin 小时又会延缓新个体的产生，导致算法早熟.变异 Step 1 Initialize SubP

第 12 期 翟 云等: 基于协同进化机制的欠采样方法 Fitness( Comi ) = α'·Premin ( Comi ) + β'·Premaj ( Comi ) ( 3) 对式( 3) 说明如下: ( 1) Fitness( Comi ) 表示在进化过 程中第 i 个组合 ComPi 的适应度，Fitness( Comi ) 越 大，表示该组合对进化环境适应程度越高; ( 2) Premin 表示在组合 ComPi 中，少数类样本的分类精度; ( 3) Premaj ( Comi ) 表示在组合 ComPi 中，多数类样本的 分类精度; ( 4) α'和 β'是权重因子，α' + β' = 1. 为提 高少数类样本分类精度，在协同进化过程中可适当 提高 α'值，对少数类样本进行合理偏置． 综上所述，式( 1) 体现了欠采样的思想，但这种 欠采样不是随机的，而是综合考虑到了压缩率、精度 和区分度三个性能指标，从而可以确保找到多数类 样本的最优组合． 式( 3) 则可确保两类样本是内在 统一的整体，在进化过程中体现出一种协同关系，从 而确保少数类样本精度的提高不会以降低多数类样 本精度为代价． 2. 3 自适应进化算子 文献［7］已经证明，对于任意初始种群，经过有 限次迭代，由选择算子按适应度进行重复选择，最终 可以使得全局寻优概率密度在评价函数的峰值处不 断增强，并收敛到最大适应度个体点． UMCCM 在整 个协同进化中，样本种群进化 L 代，样本组合种群进 化 I 代，两个种群按照遗传算法进行进化． 考虑到 样本组合种群在变异过程中会对样本种群产生重大 影响，在生成新组合过程中，采用稳定态遗传算法 ( steady-state genetic algorithm) ［8］，保证了样本种群 的进化速度快于样本组合种群． 2. 3. 1 样本种群的进化过程 ( 1) 选择: 采用轮盘赌选择方法，即按照适应度 比例选择样本． 对于给定的规模为 m 的群体 G = { x1，x2，…，xm } ，样本 xi 的适应度为 fi，则 xi 被选择 的概率为 P = fi ∑ m i = 1 fi ． ( 4) 可见，适应度较高的样本，由于在轮盘中占有较大的 份额，被选中的机会也响应较大，它的遗传因子就会 在种群中扩大． ( 2) 交叉和变异: 交叉概率 Pc 和变异概率 Pm 在影响进化行为和性能方面起到了关键作用，直接 影响到算法的收敛性． Pc 越大，新样本产生的速度 就越快，但 Pc 过大时进化模式被破坏的可能性也越 大，使得高适应度的个体结构很快被破坏; 而 Pc 过 小时又会延缓新个体的产生，导致算法早熟． 变异 概率 Pm 是决定算法跳出局部最优解的一个关键因 素，如果取值过大，遗传算法会变成随机搜索方法， 而 Pm 较小，则不宜产生新的个体，影响了个体的多 样性． 为此，笔者提出一种自适应交叉变异算子，使 Pc 和 Pm 能随适应度自动改变． 具体做法为: 当种 群收敛时，减小 Pc、增大 Pm，即降低交叉概率，提高 变异概率，以保持个体的多样性，同时避免了种群早 熟; 当种群个体发散时，增大 Pc，减小 Pm，即提高交 叉概率，降低变异概率，使种群趋于收敛． Pci = k1 { 1 1 + exp［k2 ( Fitness1 － Fitness2) ］+ } 1 2 ( 5) Pmi = k3 { 1 1 + exp［k4 ( Fitness1 － Fitness2 } ) ］ ( 6) 式( 5) 和式( 6) 中，Pci和 Pmi分别为第 i 个种群的交 叉概率和变异概率，Fitness1为适应度大于该种群个 体平均适应度的个体的平均适应度，Fitness2为适应 度小于该种群个体平均适应度的所有个体的平均适 应度． 调 节 因 子 k1，k3，k4 ＞ 0，k2 ＜ 0. 由 于 Δ = Fitness1 － Fitness2≥0，所以 Pci取值范围在［0. 5，1］ 之间，Pmi取值范围在［0，0. 5］． 从式( 5) 和式( 6) 可 知，Pci和 Pmi根据 Δ 的变化动态地自适应调整，Δ 越 大，说明种群越发散，此时 Pci会增大，Pmi会变小，反 之亦然． 可见，自适应策略能使 Pc 和 Pm 在保持种群多 样性的同时，保证了算法的收敛性． 2. 3. 2 样本组合种群的进化过程 样本组合种群进化过程中，个体选择亦采用轮 盘赌选择方法，对所选个体进行两点交叉． 如图 2 所示，交叉和变异均发生在样本种群． 例如，对第 i 个组合按概率 Pmi进行交叉时，将对所选个体在样本 种群中对应的两个个体( 按轮盘赌选择方法选择) 进行交叉． 此时进行双替代: 一方面，交叉生成的个 体替代该样本种群中适应度最差的个体; 另一方面， 该个体替代组合种群中对应的个体． 可见，样本组 合种群的交叉过程对两个种群同时产生了影响; 反 之，样本种群变异过程中，产生的个体同时也进行双 替代． 这种机制使得随着进化的不断进行，新群体 中总会产生更多性能优良的个体，而这些个体将更 有助于提升少数类样本的分类精度． 基于此，UMC￾CM 协同机制算法描述如下． 输入: 训练集 S = { ( x1，y1 ) ，( x2，y2 ) ，…，( xn， yn ) } ，近邻数 k，种群迭代数 L，I． 输出: 少数类样本精度 Premin ． Step 1 Initialize SubPi ·1553·

·1554· 北京科技大学学报 第33卷 Step 2 Initialize ComP progress=false Step 3 progress =true end Step 4 while (progress) output(Premin） for(i=l;i≤n;i++) end Fitness(Com;) 3试验验证 P= Fitness(Com,) ∑Fitness(Com,) 3.1评价指标 非平衡数据集两分类问题中，准确率已不适合 Two-point-crossover(Com,) 作为衡量分类精度的性能指标，而采用TP-rate和 Mutate(Com,) FP-ate作为性能指标： Calculate(Fitness) TP-rate= TP (7) Calculate(Fitness2) TP+FN A=Fitness-Fitness2 FP FP-ate=TN +FP (8) if△≤r progress =false 式中，TP和TN分别为预测正确的正样本和负样本 end 数，FP为原本属于负类的样本错误地预测为正类的 样本数，N为原本属于正类的样本错误地预测为负 for(=1:j≤mj++） Fitness(SubP) 类的样本数. Fitness(SubP) Kubat和Matwin提出了将G-means作为衡量非 Pi= 平衡数据集分类精度的性能指标，由于G-means是 ∑Fitness(SubP,) 引 TP-ate和FP-rate的几何均值，故Kubat和Matwin HUX-crossover(SubP,-SubP) 认为其能较好地反映分类性能四 Mutate(SubP) G-means /TP-rate x TN-rate (9) Copy (SubP)to all Com,with 为综合考察TP-ate和FP-ate,同时采用了受试 SubP 者操作特征（receiver operating characteristic, Fitness (all-Com,) ROC)@作为衡量少数类样本分类精度的指标. Calculate(Fitness) 3.2数据集 Calculate(Fitness,) 综合样本集非平衡度、样本规模和属性个数等 A=Fitness-Fitness2 因素，选用差异较大的五个UCI数据集，如表1 f△≤r 所示 表1实验所用UC数据集 Table 1 UCI data sets 数据集 属性数目 概念/反概念 少数类样本数量 多数类样本数量 非平衡度 German 20 Bad/Good 300 700 2.33 Vehicle 18 Van/Remainder 199 647 3.25 Satimage 36 4/Remainder 626 5809 9.28 Flag 28 White/Remainder 17 177 10.42 Nursery Not-recom/Remainder 328 12632 38.51 3.3 UMCCM参数确定 行十次十交叉试验时，TP-rate、TN-rate和G-means 参数对分类器性能起到至关重要的作用.在式 结果如图3所示.可见，当α值变化时，多数类样本 (1)中，=B=y=1/3恒定不变；为确定式(3)中 精度影响较小，而少数类样本精度波动较大.当 和B值，令权重因子分别取4/5、2/3、1/2、1/3、1/4 aα'=23时，分类器在十次十交叉试验中综合性能 和1/5.以Vehicle数据集为例，当在该数据集上执 最优.在其他数据集中均得到相同结论

北 京 科 技 大 学 学 报 第 33 卷 Step 2 Initialize ComPi Step 3 progress = true Step 4 while ( progress) for ( i = 1; i≤n; i + + ) Fitness( Comi ) Pi = Fitness( Comi ) ∑ n i = 1 Fitness( Comi ) Two-point-crossover( Comi ) Mutate( Comi ) Calculate( Fitness1 ) Calculate( Fitness2 ) Δ = Fitness1 － Fitness2 if Δ≤τ progress = false end for ( j = 1; j≤m; j + + ) Fitness( SubPj ) Pj = Fitness( SubPj ) ∑ m i = 1 Fitness( SubPj ) HUX-crossover( SubPi-SubPj ) Mutate( SubPj ) Copy ( SubPj ) to all Comt with SubPj Fitness( all-Comi ) Calculate( Fitness1 ) Calculate( Fitness2 ) Δ = Fitness1 － Fitness2 if Δ≤τ progress = false end output( Premin ) end 3 试验验证 3. 1 评价指标 非平衡数据集两分类问题中，准确率已不适合 作为衡量分类精度的性能指标，而采用 TP-rate 和 FP-rate 作为性能指标: TP-rate = TP TP + FN ( 7) FP-rate = FP TN + FP ( 8) 式中，TP 和 TN 分别为预测正确的正样本和负样本 数，FP 为原本属于负类的样本错误地预测为正类的 样本数，FN 为原本属于正类的样本错误地预测为负 类的样本数． Kubat 和 Matwin 提出了将 G-means 作为衡量非 平衡数据集分类精度的性能指标，由于 G-means 是 TP-rate 和 FP-rate 的几何均值，故 Kubat 和 Matwin 认为其能较好地反映分类性能［9］． G-means = 槡TP-rate × TN-rate ( 9) 为综合考察 TP-rate 和 FP-rate，同时采用了受试 者 操 作 特 征 ( receiver operating characteristic， ROC) ［10］作为衡量少数类样本分类精度的指标． 3. 2 数据集 综合样本集非平衡度、样本规模和属性个数等 因素，选用差异较大的五个 UCI 数据集［11］，如表 1 所示． 表 1 实验所用 UCI 数据集 Table 1 UCI data sets 数据集 属性数目 概念/反概念 少数类样本数量 多数类样本数量 非平衡度 German 20 Bad /Good 300 700 2. 33 Vehicle 18 Van /Remainder 199 647 3. 25 Satimage 36 4 /Remainder 626 5809 9. 28 Flag 28 White /Remainder 17 177 10. 42 Nursery 8 Not-recom/Remainder 328 12632 38. 51 3. 3 UMCCM 参数确定 参数对分类器性能起到至关重要的作用． 在式 ( 1) 中，α = β = γ = 1 /3 恒定不变; 为确定式( 3) 中 α' 和 β'值，令权重因子 α'分别取 4 /5、2 /3、1 /2、1 /3、1 /4 和 1 /5. 以 Vehicle 数据集为例，当在该数据集上执 行十次十交叉试验时，TP-rate、TN-rate 和 G-means 结果如图 3 所示． 可见，当 α'值变化时，多数类样本 精度影响较小，而少数类样本精度波动较大． 当 α' = 2 /3 时，分类器在十次十交叉试验中综合性能 最优． 在其他数据集中均得到相同结论． ·1554·