作者单位：

1. ICMC at University of S˜ao Paulo (USP), Brazil.
2. Southern University of Science and Technology Department of Compute Science and Engineering Shenzhen 518055, China.

研究动机

很多真实的分类数据集都呈现不平衡的类分布，特别是在预测少数类的样本时，这种情况会降低许多经典分类算法的有效性。在机器学习中，不平衡学习问题有两种不同的处理方式：数据层面和算法层面。大多数现有的不平衡学习技术只针对两类场景设计和测试，但当存在多个类的数据集时这些方法可能并不适用。此外多类问题可能有不同的目的，例如具有多个类的数据集可以有多个主类，即需要在分类器方面具有高度准确性的多个类。

文章贡献

大多数处理不平衡学习的技术都是针对二分类问题提出的，这些方法并不一定适用于不平衡的多分类任务。针对这些问题，本文提出了一种新的自适应方法——基于多目标遗传抽样的分类器集成(E-MOSAIC)。E-MOSAIC 将训练数据集中提取的样本编码为个体进行进化，通过多目标优化过程搜索能够在所有类别中产生具有高预测精度的分类器的实例的最佳组合。E-MOSAIC 还兼顾了分类器的多样性，这些分类器被组合成一个专门为不平衡学习设计的集成。本文在 20 个不平衡多类数据集进行了实验，和包括基于采样、主动学习、成本敏感和 Boosting 的方法进行对比，实验结果表明该方法对多类精度指标 mAUC 和 G-mean 的预测性能更优。

本文方法

采样和训练模型

首先从训练集中得到 n 个平衡样本，每个样本具有相同数量的每个类的实例。样本量是根据训练集中少数类的实例数量来选择的，使用 90% 的最少数类的实例来组成。例如一个数据集有 3 个类和 50 个少数类实例，则样本量为 0.9503=45。
每个样本被编码为 GA 种的一个个体，用一个二进制向量表示，其中每个元素代表训练集的一个实例，1 和 0 分别表示选择和忽略实例。在采样过程之后，为每个个体生成一个 MLP 模型。

适应度评估

使用训练集对训练后的 MLP 进行验证，对每个类别的预测精度使用 PPV 度量进行估计。分类器 c 相对于类 i 的 PPV 根据如下公式计算，由于第一代样本是平衡的，因此使用这些样本诱导的分类器不会受到不平衡的影响。

E-MOSAIC 使用基于 NSGA-II 的多目标遗传算法来进化平衡样本的组合，每个样本用于诱导一个基分类器，并评估这些样本诱导的分类器对每个类别的预测精度。E-MOSAIC 将分类器的多样性作为进化过程中的次要目标，这部分使用了 PFC 多样性度量。PFC 通过与当前种群中所有个体的成对比较来计算每个个体的 PFC，如果两个或两个以上的个体具有相同的非优势等级，则 PFC 较高的个体将更优。

选择和生成算子

非优势等级用于选择个体，通过交叉、变异算子生成下一代。选择算子使用大小为 3 的锦标赛选择，如果出现平局则选择 PFC 最高的个体。选择的父母数量将等于当前种群中的个体数量，使用单点交叉算子产生两个新个体，并有一定概率发生突变。
生成的下一代示例中每个类的实例数量不再受到限制，因此如果在交叉和突变时有一个样本是不平衡的，但它得到了比其他样本更高的适应度，则它将被选择为下一代。具有高适应度的相同个体在交叉变异中被选择的概率更高，增加了相同解决方案的数量。由于 E-MOSAIC 的目标是得到一个具有高准确性的分类器的多样化集称，因此交叉变异后相同的个体被淘汰。如果此时个体数量少于初始种群大小，则进行新的繁殖和突变过程。

下一代和终止条件

组成新一代的个体是基于每个个体的非优势等级，首先选择非显性水平较高的个体，然后选择那些不受第一个个体支配的个体，直到达到默认的种群规模。此时即使使用精英保留也不能保证这些个体的集合比上一代的集合具有更高的预测精度，这是因为在连续几代中模型之间的多样性可能停滞甚至减少，从而阻碍了集成的预测性能。
在初始种群和每一代之后，当前代中所有个体的分类模型由该代的分类器的集合组成。该集成基于整个训练数据集进行评估，并使用 G-mean 和 mAUC 进行度量。如果当前的分类器集合相比之前保存的集合在两个指标上持平或更优，并且没有一个更差，则更新当前的种群为最优种群。如果最优种群在 5 次进化后没有被替换，或者当 G-mean 或 mAUC 指标达到其最大值时停止迭代。当向分类器输入一个新实例时，该示例的类别由每个分类器的输出的多数投票确定。

实验结果

数据集和实验设置

对比算法方面，数据级层面选择 ROS、RUS、随机固定大小抽样(RFS)和不采样(NoS)，算法层面选择 DyS、基于 MLP 的主动学习(AL)，成本敏感学习方面选择误分类成本最小化(MMC)和 Rescale^new，以及将基分类器替换为 MLP 的 SAMME 算法。
数据集方面选择了 20 个 UCI 数据集，数据集的详细信息如下表所示。

实验都使用 MLP 作为基分类器，MLP 的参数如下表所示，学习率设置为 0.1。E-MOSAIC 的种群数设置为 30 个个体，突变率设为 0.1，交叉率设为 1。

采用五折交叉验证，每种方法执行 10 次取平均，评价指标选择 G-Mean 和 MAUC。

和数据级别方法对比

下图分别给出了 E-MOSAIC、ROS、RUS、RFS 和 NoS 在每个数据集的 MAUC 和 G-mean 的平均值。E-MOSAIC 在大多数数据集中优于其他方法，呈现出最佳的整体预测性能。

和算法级方法对比

下图展示了 E-MOSAIC、DyS、AL、MMC、Rescale、SAMME 方法的 MAUC 和 G-mean 指标的平均值。

下表展示了 E-MOSAIC 在与算法级方法两两比较中获得的胜、平、输的数量，可以明显地看出 E-MOSAIC 相比其他比较的方法具有较大的优势。

少数类样本量的影响

从上面的结果可以看出在部分数据集上，E-MOSAIC 并没有达到所有方法的最佳效果。尤其是少数类的实例数量与多数类的实例数量相比非常低的情况下，此时欠采样会丢弃多数类的实例从而丢失了大量信息。
例如在 chess 数据集上，由于少数类样本太少导致算法的样本量不够大，无法很好地代表大多数类别。从下表可以看到，较小的类的分类准确率通常高于较大的类，特别是当最少数类的实例数量很低的时候。

优点和创新点

个人认为，本文有如下一些优点和创新点可供参考学习：

1. 不同于很多不平衡的二分类问题，本文的算法针对多分类问题利用 GA 实现了子集的抽样并训练了一个集成分类器，在多分类场景下得到了应用；
2. 本文的 GA 使用了多目标优化，在保证精度的同时提高了集成中的基分类器的多样性，进而提高了总体性能；
3. GA 的进化过程从平衡的状态开始，然后允许不平衡个体的出现避免了对少数类的过度关注，是一种折中的解决方案。

本栏目推荐文章
• 《Ensemble deep learning: A review》阅读笔记
• 【五期李伟平】CCF-B（TFS'23）Consensus Reaching Process With Multiobjective Optimization for Large-Scale Group Decision Making With Cooperative Game
• Vision Transformer with Super Token Sampling
• Paper Reading: Oversampling with Reliably Expanding Minority Class Regions for Imbalanced Data Learning
• Class-Incremental Learning with Generative Classifiers(CVPR2021W)
• speculative-sampling笔记
• 【论文阅读笔记】【OCR-文本检测】 Few Could Be Better Than All: Feature Sampling and Grouping for Scene Text Detection
• Paper Reading: Sample and feature selecting based ensemble learning for imbalanced problems
• Metropolis Algorithms for Representative Subgraph Sampling
• Sampling from Large Graphs

Multiobjective Classifiers Imbalanced Ensemble Samplingmultiobjective classifiers imbalanced ensemble classification imbalanced self-paced ensemble imbalanced selecting ensemble learning model-based imbalanced synthetic sampling multiobjective classifiers with multiobjective optimization large-scale ensemble graph construction classifiers tree-based classification classifiers hundreds problems