Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。

论文概况	详细
标题	《Exploratory Undersampling for Class-Imbalance Learning》
作者	Xu-Ying Liu, Jianxin Wu, and Zhi-Hua Zhou
发表期刊	IEEE Transactions on Systems Man Cybernetics-Systems
发表年份	2009
论文影响	不平衡分类问题的经典论文，不平衡集成模型的 baseline 方法
论文代码	Python imbalanced-learn 库有实现(https://imbalanced-learn.org/)

作者单位：

National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China
School of Interactive Computing, College of Computing, Georgia Institute of Technology, Atlanta

研究动机

在现实中数据集通常是不平衡的，不平衡现象会严重影响分类器的性能，因此为类不平衡的数据集设计分类器是一个重要的问题。不考虑班级不平衡的学习算法容易被多数类支配，导致忽略了对少数类的识别。例如在一个不平衡率为 99 的问题中，一个最小化错误率的学习算法可以决定将所有的样本分类为多数类，以达到 1% 的低错误率。然而在这种情况下，所有少数类的例子都会被错误地分类。

文章贡献

本文是不平衡分类问题的经典论文，文中提出了 2 种不平衡集成学习模型都是简单而有效的 baseline 方法。 EasyEnsemble 方法直接对多数类样本进行采样得到几个子集，并使用这些子集分别训练基分类器。BalanceCascade 是使用训练好的分类器来指导后续分类器的采样过程，即在上一个分类器被分类正确的样本将在下一个分类器中移除。两种方法在 16 个 UCI 数据集上的实验表明，与许多现有的类失衡学习方法相比，这两种方法在各个指标上都具有更高的性能。

本文方法

EasyEnsemble

给定少数类训练集 P 和多数类训练集 N，欠采样方法从 N 种随机抽取一个子集 N'(|N'|<|N|)，通常的设置是 |N'|=|P|。EasyEnsemble 方法对 N 进行多次独立采样，得到多个子集 N1, N2, …, Nt。对于每个子集 Ni(1≤i≤t)，使用 Ni 和 P 的所有样本来训练分类器 Hi。分类器 Hi 基于 AdaBoost 进行训练，所有生成的分类器集成后进行最终决策。EasyEnsemble 的伪代码如下所示：

EasyEnsemble 的思想与 BalancedRandomForests 相似，EasyEnsemble 生成 T 个平衡子问题。第 i 个子问题的输出是 AdaBoost 分类器 Hi，该分类器是具有 si 个弱分类器 {hi,j}的集合。hi,j 的另一种观点是将其视为通过集成学习方法提取的特征，此时得到的是一个基于这些特征的线性分类器，从不同子集 Ni 提取的特征包含原始训练集 N 的不同方面的信息，最后收集所有特征 hi,j(i=1,2,…T; j=1,2,..,si）得到最终的集成分类器。

BalanceCascade

EasyEnsemble 使用带有替换的独立随机抽样，是一种在 Ni 上操作的无监督策略。BalanceCascade 则是以监督的方式探索 Ni，它在训练 H1 之后，如果一个例子 x1∈N 被 H1 正确地分类为多数类，则可以推测 x1 在 N 中有一定冗余性，因此在下一次训练就可以从 N 中删除这些正确分类的多数类样本。与 EasyEnsemble 一样，BalanceCascade 也是使用 AdaBoost 进行训练。BalanceCascade 的伪代码如下所示：

BalanceCascade 在第 T 次迭代开始时，N 已经收缩了 T−1 倍，因此它的当前大小为 |N|·f^T−1=|P|。在训练 HT 后 N 将被再次缩小 N，当 N 的大小小于 |P| 时可以停止训练过程。BalanceCascade 中分类器之间的顺序依赖主要用于减少多数类中的冗余信息，这样可以在后续欠采样时得到一个有限的样本空间，从而探索尽可能多的有用信息。

实验结果

数据集和实验设置

本文在 16 个 UCI 数据集上进行测试，数据集的信息如下表所示。每个数据集使用五折交叉验证，重复 10 次取 F1、G-mean 和 AUC 指标的平均值

对比算法有 13 个，分别是 CART、Bagging(Bagg)、AdaBoost(Ada)、AsymBoost(Asym)、SMOTEBoost(SMB)、Undersampling+AdaBoost(Under)、Oversampling+AdaBoost(Over)、SMOTE+AdaBoost(SMOTE)、Chan and Stolfo’s method+AdaBoost(Chan)、Random Forests(RF)、Undersampling+RF(Under-RF)、Oversampling+RF(Over-RF)、Balanced RF(BRF)。这些算法中的 CART 设置一致，启用剪枝，非纯节点必须至少有 10 个示例才能被分割，每个集成模型都有 40 个弱分类器。

训练时间

所有对比方法的运行时间记录在下表，从运行时间可见 Chan、Easy、Cascade、Under 方法性能相当，训练时间最长的是 SMB、Over，其次是 Ada、Asym，最后是 SMOTE。

实验结果

对比方法的平均 AUC 和 t 检验结果如下面三张表所示，此时将 16 个数据集分为两组。第一组包含 6 个“简单”数据集，Ada 在这些数据集上的 AUC 大于 0.95。第二组包含 10 个“困难”数据集，Ada 的 AUC 值小于 0.95。

下面三张表展示了比较方法的平均 F1 值和 t 检验结果。结果表明，在“简单”任务上除了 Asym 的 AUC、F1 与 Ada 相近外，所有不平衡学习方法都低于Ada。在“困难”任务中，不平衡学习方法的 AUC 和 F1 普遍高于 Ada。说明普通方法可以获得高 AUC 的任务，不平衡学习通常对 AUC 和 F1 没有帮助。Easy 和 Cascade 可以减少训练时间，其平均 AUC 值与 Ada 和 Asym 接近。

Easy 和 Cascade 在“困难”任务上的平均 AUC、F1 和 G-mean 都高于几乎所有其他方法，在不同的性能指标上都非常稳健。同时 Easy 和 Cascade 所需的训练时间与 Under 大致相同，并且比其他方法更快。从分类性能和训练时间两方面考虑，本文方法优于其他比较方法。

在“困难”任务上的结果显示，Cascade 的效果不如 Easy，这可能是因为 Cascade 监督级联的抽样方式出现过拟合的问题。从“简单”任务的结果来看，Cascade 在几乎所有数据集上都比 easy 具有更高的性能，表明 Cascade 可以专注于更有用的数据。如果一个类中的样本数量非常少，则这些样本的特征空间会很分散，仅用欠采样很难得到一个有代表性的子集。在这种情况下，关注更多信息丰富的示例可能特别有用。
对于高度不平衡的问题，Easy 的独立随机抽样策略要求子集的数量 T 非常大才能捕捉到 N 中的所有信息。此外由于没有可用的先验信息，Easy 很难确定子集的数量，在计算上不可行。然而对于 Cascade，设置迭代次数要容易得多，因此 Cascade 更适合应用于高度不平衡问题。

集成策略分析

当少数类样本数量有限时，堆叠这些分类器可能会导致过拟合。此处使用 16 个数据集，将 stacking 与 Easy、Cascade 中使用的集成策略进行比较，结果如下表所示。在“简单”任务中，这些策略的性能差异很小。在“困难”任务上 Cascade 的性能优于所有数据集的 stacking，Easy 只有一个数据集的 stacking 效果更好。总的来说，本文提出的方法中使用的集成策略与 stacking 性能之间存在显着差异。

补充说明

基于实验结果，作者给出了以下 3 点补充说明：

EasyEnsemble 和 BalanceCascade 方法比许多其他类不平衡学习方法具有更强的鲁棒性；
不平衡对某些任务是无害的，此时使用不平衡学习方法可能会导致性能退化，因此需要制定一些方法来判断一个任务是否存在不平衡；
在类平衡的任务上，AdaBoost 和 Bagging 可以显著提高决策树的性能，而在存在类不平衡的任务上，AdaBoost 和 Bagging 对决策树的性能没有帮助，有时甚至会起反作用。