目录
Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。
| 论文概况 | 详细 |
|---|---|
| 标题 | 《Multi-class Imbalance Classification Based on Data Distribution and Adaptive Weights》 |
| 作者 | Shuxian Li, Liyan Song, Xiaoyu Wu, Zheng Hu, Yiu-ming Cheung, Xin Yao |
| 发表期刊 | IEEE Transactions on Knowledge and Data Engineering(TKDE) |
| 发表年份 | 2024 |
| 期刊等级 | 中科院 SCI 期刊分区(2022年12月最新升级版）2 区，CCF-A |
| 论文代码 | 文中未公开 |
作者单位：
- Research Institute of Trustworthy Autonomous Systems, Southern University of Science and Technology, China.
- Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, China.
- Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China.
- Faculty of Computing, Harbin Institute of Technology, Harbin, China.
- RAMS Reliability Technology Lab, Huawei Technologies Co., Ltd, Shenzhen, China.
- Lingnan University, Hong Kong SAR, China
- School of Computer Science, University of Birmingham, UK.
研究动机
多分类不平衡问题在实际应用中很常见，数据中未处理的不平衡情况经常导致错误分类、误导甚至错误的结果，这对数据集的管理和使用构成了重大挑战。现有的策略通常依赖于类别的样本规模来处理不平衡，但是还应当考虑获取其他信息来更好地反映类不平衡。采用不平衡比会给同一类的训练样本赋予相同的权重值，无法反映同一类训练样本之间的差异。也就是说，类失衡率只能区分属于不同类的“类间”训练样本。同时这些不平衡信息是预先基于整个训练集计算的，它们的值在整个训练过程中保持不变。这个因素导致训练样本的权重不能适应当前的训练状态，可能会阻碍类不平衡机制更好地处理多类不平衡。从这个意义上说，利用当前的训练状态来分配一个“自适应”的样本权重，将进一步缓解多类不平衡问题。
文章贡献
针对当前多分类不平衡问题仅依靠不平衡比，以及数据集的不平衡信息无法在训练过程中动态调整的问题。本文首先提出了基于自适应分布的样本权值，将类间不平衡比、类内密度变量和自适应裕度综合起来处理多类不平衡。接着将提出的自适应样本权值与 AdaBoost 学习框架相结合，提出了 AdaBoost.AD 算法，并为其提供了理论支持。通过多个不平衡数据集的实验，结果表明所提出的 AdaBoost.AD 相比现有方法具有更强的预测性能，并验证了自适应权重各个组成部分的有效性。
基于样本权重的数据分布
本文采用 AdaBoost 作为多分类学习框架，假设有一个由 n 个训练样本{(Xi, yi)} 组成的数据集，用于构建处理 c 类分类问题的基学习器集合。其中 Xi∈Rd 表示第 i 个训练样本的 d 维输入特征，yi∈{1,…,c} 表示第 i 个训练样本的标签。
假设 AdaBoost 集成总共有 m 个训练 epoch，则有 m 个基学习器 {ht(·)}，每个基学习器与一个模型权值 βt 相关联。
类间数据分布
令 yi∈{1,…,c} 和 N(y) 为给定标签为 y 的训练样本个数的非负函数。按照处理类不平衡的常规方法，使用公式(1)定义基于类大小的训练样本（X, y）的多类不平衡比率，其中 miny'N(y') 为最小类的样本数量。
不平衡比较大(较小)的训练样本说明可以提供给模型训练的数据信息相对充足(不足)，因此可能需要将较低(较高)的权重与这些训练样本关联起来。但仅根据不平衡比推导样本权重会导致同一类训练样本的权重相同，而没有考虑到同一类训练样本之间的差异，因此本文将引入一个因子来描述每个类的类内数据分布。
类内数据分布
此处将生成该类内每个训练样本的密度来描述同一类训练样本之间数据分布的差异，密度是根据该数据的邻域内同一类的样本数量来决定的，并且具有统一的密度尺度。因此相关的样本权重不仅反映了类间数据分布的信息，还反映了类内数据分布的信息。
一个样例如下图所示，在两个具有不同类内分布属性的区域中，1 类样本(蓝点)与 2 类样本(红点)重叠。“密集”区域包含更多的1类样本，而“稀疏”区域包含更少的 1 类样本。在密集区域无法处理 1 类样本可能会导致分类模型的预测性能比在稀疏区域下降得更明显，因此在密集(稀疏)区域对类 1 的训练样本进行过拟合(欠拟合)，以获得更好的整体预测性能。
用 N(Xi) 表示整个训练样本中 Xi 的第 k 近邻集，其中 k 是预定义参数。假设 N(Xi) 中有 ki≤k 个样本与 yi 属于同一类，将 N(Xi) 的子集命名类内邻居集，记为 N(Xi, yi)1。用 N(Xi, yi)j 表示在 j=1,…,ki 的类邻居集中 Xi 的第 j 个类内邻居，定义 (Xi, yi) 的一般密度为公式(2)。其中 d(·,·) 表示两个训练样本的距离，T 是基于所有训练样本确定的常数。本文使用欧几里得距离作为距离度量，设置 k=5。
常数 T 定义为 ∑ni=1ρ(Xi, yi)/n，它可以被认为是在所有训练样本中单位样本密度的归一化项，因此ρ(Xi, yi) 被命名为一般密度。一般密度值大于(小于) 1 (基准单位)的训练样本表明：与基准密度相比它们位于更密集(稀疏)的区域。
为了明确量化类内数据分布的差异，定义训练样本（Xi, yi）的逆类内密度为公式(3)，其中 Zi 表示归一化项。其中子集 Ci 包含与 yi 相同标签的训练样本，||Ci||为子训练集的大小，每个类的类内密度值将具有单位逆密度。
也就是每个类的训练样本将得出一个统一的逆类内密度，较小(较大)的值表示希望有较大(较小)的样本权重来处理类不平衡。
基于分布的样本权重
类间不平衡较小、类内密度值相反的训练样本将被赋予更高的权重，使训练过程更加关注它们。该信息可以合并到单个数据分布因子中，定义为公式(4)，α(·) 的范围为 (0,1)。
假设新的迭代轮次为 t+1，则 AdaBoost 集成中训练样本 (X, y) 的权值可以重新表述为公式(5)。ω(t)(·) 表示在前一轮 t 迭代确定的样本权值，βt 表示在 t 构建的基础学习器 ht(·) 的权值，1[condition] 表示条件函数。如此，可以将基于样本权值的数据分布直接编码到 AdaBoost 集成学习框架中。
自适应样本权重
由于样本的类间不平衡比和逆类内密度是基于整个训练集预先计算的，因此它们的值在 AdaBoost 训练过程中保持静态。非自适应的权值不能反映最新的训练状态，利用当前的训练状态来分配样本权值可能会进一步缓解多类不平衡问题。此处将提出通过目前训练样本被分类正确的概率差来量化最新的训练状态，实现基于自适应分布的样本权值。
跟踪当前的训练状态
使用 o(t)(X, y') 表示 AdaBoost 的 t 个基学习器的输出，将 X 投票给类 y'∈{1,…,c} 可以表示为公式(6)。
hν(·) 为之前在第 ν 代构建的基学习器，此时 X 被预测为 c 类的概率可以量化为公式(7)。
在所有类的所有训练样本上重复上述计算，可以得到一个如下表所示的概率矩阵，记录每个训练样本在 t 代上被预测到每个类的概率。
本文考虑将最新的训练状态量化为训练样本被正确分类的概率与迄今为止在整个训练过程中最不正确分类的概率之差，将其定义为自适应裕度。根据概率矩阵，任意训练样本 (X, y) 的自适应裕度可表示为公式(8)。P(t)(X, y) 表示 X 能够被正确分类的概率，maxy'≠yP(t)(X, y′) 表示 X 被错误分类的最大概率，σ(t)(·) 的取值范围是 0~2。
σ(t)(Xi)=1 的情况对应 P(t)(Xi, yi)=maxy'≠yP(t)(Xi, y')，表示当前 AdaBoost 在预测中所面临的最高不确定性。σ(t)(·)>1 的训练样本表示可以被正确预测，σ(t)(·)<1 则表示将被错误地分类，因此可以用 σ(t)(·) 来表示正确预测训练样本X的难度。
基于自适应分布的样本权重
训练时需要对自适应裕度较小的样本赋予更高的权重，使训练时更加关注这些样本，从而更好地处理最新的类不平衡问题。可将自适应裕度因子进一步纳入公式(4)的静态数据分布因子中，得到自适应数据分布因子为公式(9)，α(t)(·) 的取值范围是（0,1）。
则 AdaBoost 中训练样本 (X, y) 在第 t+1 迭代的权值可以定义为公式(10)，其中 ω(t)(X, y) 表示在前一个 t 迭代确定的自适应样本权值。其他符号与公式(5)相同，关键区别在于此时的 α(t)(·) 具有自适应性质。
基于自适应分布的样本权重的 Adaboost
此处将基于自适应分布的样本权重纳入 AdaBoost 集成框架中，将设计的方法称为 AdaBoost Ensemble with Adaptive Distribution based Sample Weight (AdaBoost.AD)。
AdaBoost.AD 算法
AdaBoost.AD 的流程如下伪代码所示，它遵循了经典 AdaBoost 的学习过程，两个关键步骤在于：模型权值的计算和样本权值的更新。迭代 t 构建的基学习器 ht(·) 的模型权值 βt 和下一个代的样本权值 ω(t+1)(·) 是 AdaBoost.AD 算法中两个的可学习变量。
给定在 t 代确定的样本权值 ω(t)(·)，则新构建的基学习器的模型权值 ht(·) 如公式(11)所示。AD 是根据正确预测数与错误预测数的比值来计算的，通常情况下分母会小于分子，所以通常情况下 βt>0。
接着根据 ht(·) 及其模型权值 βt 更新样本权值，t+1 代的训练样本 (Xi, yi) 的权值表示为公式(12)。
在训练过程中，较大的 α(t)(·) 对应的训练样本将产生更高的样本权值，可能有利于自适应地缓解随训练过程变化的类不平衡问题。在 AdaBoost.AD 中，测试样本 X 的预测过程如公式(13)所示。
理论分析
AdaBoost.AD 理论分析的相关符号定义如下表所示。
在经典 AdaBoost 中使用指数损失函数，在公式(9)中的自适应数据分布因子 α(v)(Xi, yi) 包含了计算模型权重的信息，因此每个 α(v)(Xi, yi) 应与每个基学习器的样本损失一致，如公式(14)所示。
L(t)(Xi, yi) 分解为三个分量的乘积，定义 ω(t)(Xi, yi) 为公式(15)。
此时可以将公式(14)重写为公式(16)。
此时 (Xi, yi) 在第 t+1 代时的样本权值迭代公式可以用公式(17)进行推导。其中 ct=exp(βt/2) 是一个常数，因此可以从样本权值中剔除。
因此最终样本权值可以简化为如下公式，此时即可对公式(10)和公式(12)中的基于自适应数据分布因子设计的样本权值提供理论支持。
对于基学习器的模型权值，通常该权重应该通过最小化优化函数得到，如公式所示：
为了使目标最小化，每个模型权重 βt 的偏导数应为 0，如下公式所示：
此时全部的训练样本可以分为正确分类和错误分类两个部分，可将上式改写为如下形式。通过恒等变形后即可推出公式(11)，此处为模型权值 βt 的表达式提供了理论支持。
实验结果
数据集和实验设置
实验使用 12 个多分类不平衡数据集和 8 个二分类不平衡数据集，这些数据集的基本信息如下表所示。实验通过 10 次 5 折交叉验证，评估指标选择 G-mean 和 Avg-AUC，并对结果进行 Friedman 检验。
AdaBoost.AD（简称为 AdaAD）将与两组多分类集成方法进行比较，其中经典 AdaBoost 方法将使用 ADASYN 来处理类不平衡。
| 算法类型 | 数量 | 对比算法 |
|---|---|---|
| 经典 AdaBoost 方法 | 3 | AdaBoost.M1、AdaBoost.M2、AdaBoost.NC |
| 基于 Adaboost 的多分类不平衡方法 | 两个版本的 LexiBoost、Dual-LexiBoost、JanEnsemble |
对比实验
以下两张表分别展示了各算法在 G-mean 和 Avg-AUC 方面的预测性能，可见 AdaBoost.AD 在 20 个数据集中的 12 个上表现优于其他方法，说明了其预测性能的优越性。Friedman 检验在显著性水平 0.05 下拒绝，意味着这些方法的性能显著不同。
消融实验
该部分分析了类间不平衡比、逆类内密度和自适应边际因子对模型的性能影响，分别从 AdaBoost.AD 的样本权值中去除这 3 个分量得到 3 种变体。
| 变体 | 说明 |
|---|---|
| AdaAD-imb | 消除类别间失衡比例 |
| AdaAD-den | 消除逆类别内密度 |
| AdaAD-mrg | 消除自适应边际因子 |
以下两张表分别展示了各算法在 G-mean 和 Avg-AUC 方面的预测性能，从 Friedman 检验可见这些算法之间存在显著差异。
优点和创新点
个人认为，本文有如下一些优点和创新点可供参考学习：
- 现有大部分不平衡学习方法都仅依靠不平衡比作为不平衡信息，仅考虑不平衡比仅有助于不同类别的样本，但对于同一种类别的难分样本难以提升。本文提出的自适应权重还考虑了样本的密度和裕度，能够以粒度更细的视角来改善不平衡学习的效果。
- 本文将提出的自适应样本权重与 AdaBoost 结合，使其能够在训练期间动态地调整样本的权重，从而在不平衡问题上获得更优的性能，并且通过公式推导对其进行了理论验证。