作者单位：

1. School of Artificial Intelligence, Jilin University
2. Key Lab of Symbolic Computation and Knowledge Engineering of MOE, Jilin University
3. Microsoft Research

研究动机

许多实际下的分类任务生成的数据集是非常不平衡的，且真实数据集可能包含噪声、缺失值等不利因素，这种高度不平衡、大规模、有噪声的数据给下游分类任务带来了挑战。传统的一些分类算法在不平衡数据集上表现不佳，当数据集规模更大或噪声更多时性能可能会更糟。这是因为经典的方法假设正样本和负样本之间的相对平衡分布，导致了少数类通常被忽略。
现有的解决不平衡问题的方法可以分为 3 类，分别是数据级方法、算法级方法、集成方法。数据级方法将样本进行重采样，由于该方法是基于距离进行设计，它可能不适用于具有分类特征或缺失值的数据集，同时算法的时空开销非常大。算法级方法直接修改现有的学习算法，这种方法通常需要依赖专家的先验知识。集成方法将前面的方法之一与集成学习算法相结合，也存在训练成本大、适用性差、欠拟合或过拟合的问题。

文章贡献

目前很多方法都不能很好地处理高度不平衡、大规模和有噪声的分类任务，主要原因是它们忽视了不平衡学习所隐含的困难。本文引入“分类硬度”的概念来刻画不平衡问题的困难所在，该概念表示为特定分类器正确分类样本的难度。基于这个概念，本文提出了一种新的学习框架——自定步速集成(self-pace Ensemble，SPE)。SPE 通过考虑分类硬度在数据集上的分布，根据硬度分布迭代选择信息量最大的多数数据样本，欠采样策略由自定节奏程序控制。这种过程使 SPE 框架逐渐集中在较难的数据样本上，同时仍然保留容易样本分布的知识，以防止过拟合。通过大量的实验表明，与现有方法相比，SPE 具有准确、快速、鲁棒性好、适应性强等优点。

分类硬度分布

分类硬度的定义

作者在文中介绍了“分类硬度(classification hardness)”的概念，首先用符号 H 表示分类硬度函数。硬度函数可以是任意由单个样本误差之和计算得到整体误差的函数，例如绝对误差、平方误差和交叉熵损失。设 F 为一个训练好的分类器，F(x) 表示输入 x 时分类器输出为正实例的概率，则样本 (x, y) 相对于 F 的分类硬度为函数 H(x, y, F)。

分类硬度的优点

分类硬度的概念对于不平衡问题有两个优点，首先是可以在一定程度上反映不平衡比和任务难度之间的关系。在不同的任务下，同样的失衡比例不见得也有相同的解决问题的难度。作者给出了一个例子如下图所示，在 (a) 中数据集由两个不相交的高斯分量生成，增大不平衡比不会增加任务的难度。而 (d) 中的数据集由多个重叠的高斯分量生成，不平衡比的增加会导致任务难度的增加。如果以分类硬度的角度来看，随着失衡比的增大，在图 (e) 和图 (f) 中难分样本的数量增加明显，在图 (b) 和图 (c) 中保持不变。

第二是可以在一定程度上反映数据采样策略与分类器能力之间的关系。不同的分类器在不平衡数据分类上的性能往往不同，而现有的一些抽样方法忽略了基分类器的特性。例如上图中对于相同的数据集，KNN 和 Adaboost 显示的硬度分布不同。因此在算法中考虑分类硬度，提出的框架就能基于具体的模型对分类器进行优化。

分类硬度视角下的样本类型

作者根据硬度值，将不平衡数据样本分为 3 种类型：trivial、noise、borderline。

1. trivial 样本：数据集中大多数的样本都是 trivial 样本，模型能较为容易地对 trivial 样本进行分类，例如上图中 (e) 和 (f) 的蓝色样本。为了防止过拟合，算法需要保留一部分 trivial 样本对模型的分类打下基础；
2. noise 样本：noise 样本的数量在数据集中的比例较少，它们贡献了很大的硬度值，如上图中的暗红色的样本。noise 样本通常是由难以区分的重叠或异常值引起的，强制模型去学习这样的样本可能会导致严重的过拟合；
3. borderline 样本：borderline 样本指的是非 trivial 也非 noise 的样本，在训练过程中这类样本的信息量最大。例如上图中浅红色的点非常接近当前模型的决策边界，扩大 borderline 样本的权重通常有助于提高模型的性能。

由于在实践中很难对样本做出明确的区分，作者选择了以 soft 方式对数据样本进行分类。

本文方法

自定步速欠采样

本文 SPE 的目标是设计一种欠采样机制，在减少 trivial、noise 样本影响的同时扩大 borderline 样本的重要性，主要通过引入“硬度协调”的概念和自定步速的训练过程实现。

硬度协调

首先根据硬度值将所有多数类样本分成 k 个箱子，每个桶表示一个特定的硬度级别，其中 k 为超参数。在保持每个桶中的总硬度贡献相同时，将大多数实例欠采样到平衡数据集中。因为在训练过程中集成分类器将逐渐拟合训练集，导致 trivial 样本的总量增长，所以算法不能简单地在所有的迭代中使用硬度调和。为了应对这个问题，本文引入“自定步速因子”来执行自协调欠采样。

自定步速因子

此步将从协调每个桶的硬度贡献开始，逐步降低那些具有大量样本的桶的样本概率，这个下降的水平由自定步速因子 α 控制。初始状态时 α=0，当 α 增大时算法将更多地关注较硬的样本。在前几次迭代中，算法主要关注信息丰富的 borderline 样本，异常值和噪声对模型的泛化能力影响不大。在后来的迭代中，当 α 非常大时本文的模型仍然保留了合理比例的高置信度样本作为“骨架”，防止了模型过拟合。

算法定义

SPE 算法的定义涉及到的一些符号和含义如下：

此时 Bι 可以由如下公式定义：

SPE 算法的步骤如下伪代码所示，在每次迭代中算法将更新硬度值，以选择对当前集成最有利的数据样本。使用 tan 函数来控制自定步速因子 α 的生长，第一次迭代中的 α=0，在最后一次迭代中的 α→∞。

实验结果

合成数据集实验

数据集和实验设置

合成数据集程 4×4 棋盘状，数据集包含 16 个高斯分量，所有高斯分量共享相同的协方差矩阵 0.1×I2。将少数样本的数量 |P| 设为 1000，多数样本的数量 |N| 设为 10000。训练集 D、验证集 Ddev 和测试集 Dtest 分别从同一原始分布中独立采样。

合成数据集的实验设置如下：

合成数据实验结果

下表展示了各个算法使用的超参数和实验结果，可见在合成数据集上 SPE 优于其他方法。

下图是各个算法的可视化效果，该图显示几种不平衡算法在数据集上训练/预测情况：

• Clean 试图清除被少数数据点包围的大多数异常值，保留了所有 trivial 样本，因此模型无法关注更多信息的数据；
• SMOTE 由于无法区分的重叠而过度概括了少数类；
• Easy 算法进行简单的随机欠采样，导致多数样本的一部分信息丢失；
• Cascade 在后期迭代中保留了许多异常值，导致了过拟合；
• SPE 通过考虑数据集上的分类硬度分布，得到了更加准确和鲁棒的结果。

类重叠下的鲁棒性

作者测试了 SPE 在高斯分量具有不同程度重叠时的鲁棒性，通过替换原协方差矩阵从 0.1×I2 到 0.05×I2 和 0.15×I2 来控制重叠，协方差矩阵的协方差因子越小则分布重叠越少。保持样本量和不平衡比相同，分别对三个不同的棋盘数据集进行采样。
下图显示了在训练过程中 AUC-PRC 的变化情况，在较后的迭代中 Cascade 的性能下降明显，这是因为 Cascade 在噪声样本上过拟合。相比之下，SPE 通过保持合理比例的 trivial、borderline 样本来缓解这个问题。

真实数据集实验

数据集和实验设置

本文选择了几个高度不平衡的真实数据集进行实验，这些数据集的详细信息如下表所示。

真实数据集的实验设置如下：

真实数据实验结果

由于缺乏合适的距离度量和过高计算成本，Clean 和 SMOTE 的部分实验无法进行。下表中展示了各个算法使用的实验结果，可见 SPE 在所有数据集上展示了最佳性能。

和重采样方法比较

此处进一步和基于重采样的不平衡学习方法进行比较，这些算法如下表所示。

由于在大规模数据集上运行重采样方法可能非常缓慢，且在具有非数值特征的数据集上难以定义适当的距离度量。因此这些算法只在 Credit Fraud 数据集上运行，该数据集有 284807 个样本，并且只包含归一化的数值特征。使用 5 种不同的分类器，分别是逻辑回归(LR)、KNN、DT、AdaBoost、GBDT。
实验结果如下表所示，其中 ORG 是指在原始训练集上不重采样直接训练。从实验数据可见，SPE 显著提高了各基分类器在高度不平衡数据集上的性能。与其他重采样方法相比，SPE 需要的训练数据和处理时间都非常少。

大多数重采样方法只能在与特定分类器结合时才能获得更好的结果(优于ORG)，这是因为这些方法无法考虑分类器本身的能力。同时在不平衡比率的数据集上，少数类通常表达能力较差。因此直接应用重采样，特别是依赖于少数对象之间关系的过采样，反而会降低分类性能。

和集成方法比较

此处进一步和不平衡集成学习方法进行比较，实验设置如下表所示。

下表展示了 5 种集成方法和 SPE 的实验结果和使用样本的数量，相比之下 SPE 使用的训练数据要少得多，在 4 个评价标准上明显优于其他方法。

在 Credit Fraud、Payment Simulation 数据集上进行了详细的实验，结果如下图所示。从结果中可以看到，SPE 能在很少的数据上获得理想的结果。与 SPE 相比，其他方法稳定性较差、随机性较大。

存在缺失值时的稳定性

最后测试了在数据集中存在缺失值时，不同集成方法的鲁棒性。为了模拟缺失值的情况，实验时从训练和测试数据集中的所有特征中随机选择值替换为无意义的 0。在 Credit Fraud 数据集上测试了所有方法，缺失值的比例设为 0%、25%、50%、75%。
结果报告如下表所示，可以看到 SPE 在不同缺失程度下表现出稳健的性能，而其他方法在缺失率较高时表现不佳。

调参实验

SPE 有 3 个主要超参数，分别是基分类器数 n、桶数 k、硬度函数 H，此处通过实验验证 k 和 H 的不同选择的影响。SPE 在两个数据集上将 k 从 1 调整至 50。硬度函数测试了 3 种，分别是绝对误差(AE)、平方误差(SE)和交叉熵(CE)，这些函数的公示如下所示。

实验结果如下图所示，结果表明 SPE 对 k 和 H 的不同选择具有鲁棒性。由于 k 决定硬度分布近似的程度，因此设置较小的 k 可能会导致性能不佳。

优点和创新点

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

1. 相比于其他工作，本文并没有局限于对不平衡率进行分析，并提出了“分类硬度”的概念对不平衡问题进行刻画，非常新颖；
2. 基于分类硬度的概念，将样本分为 3 种不同的类型。除了关注更重要的边界样本，SPE 也没有过度删除易分样本，在一定程度上避免了过拟合；
3. 对于每个数据子集，SPE 设计了一个自适应机制来调节对不同类型样本的考虑程度，和基分类器更加适配；
4. 实验数据丰富有力，合成数据集和真实数据集上进行了实验，并与多种类型的算法来评价本文提出的算法的优势，说服力强。

本栏目推荐文章
• 《Ensemble deep learning: A review》阅读笔记
• Supervised Machine Learning : Regression and Classification
• 《Progressive Learning of Category-Consistent Multi-Granularity Features for Fine-Grained Visual Classification》阅读笔记
• Paper Reading: Oversampling with Reliably Expanding Minority Class Regions for Imbalanced Data Learning
• Fine-grained Visual Classification with High-temperature Refinement and Background Suppression
• CA-TCC: 半监督时间序列分类的自监督对比表征学习《Self-supervised Contrastive Representation Learning for Semi-supervised Time-Series Classification》(时间序列、时序表征、时间和上下文对比、对比学习、自监督学习、半监督学习、TS-TCC的扩展版)
• Multivariate time series classification pytorch lstm
• Kaggle:Otto Group Classification
• 《A Survey on Deep Learning-based Fine-grained Object Classification and Semantic Segmentation》阅读笔记
• CART（Classification and Regression Trees）

Classification Imbalanced Self-paced Ensemble Massiveclassification imbalanced self-paced ensemble multiobjective classifiers imbalanced ensemble imbalanced selecting ensemble learning class-imbalanced classification re-balancing classification hashing-based undersampling imbalanced massive self-paced metasurface antennas dynamic massive ensemble mensa unsupervised adaptation ensemble