第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·