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