robot520/Class-Imbalance

Cost-Sensitive Learning / Resampling / SMOTE etc.

• Author： 马肖
• E-Mail： maxiaoscut@aliyun.com
• GitHub： https://github.com/Albertsr

---

第一部分：代价敏感综述

1. 代价敏感与非代价敏感算法的区别

1.1 关键区别：

• cost-sensitive Learning对不同的分类错误赋予不同的代价
• cost-insensitive Learning不区分不同分类的错误的代价

1.2 算法目标不同

• cost-sensitive Learning以最小的代价为目标
• cost-insensitive Learning以最小的分类误差为目标

---

2. 基于代价矩阵的分类决策

2.1 代价矩阵的定义

2.2 在欺诈识别等业务场景：FN的代价大于FP的代价

• FN是指没有识别出真实的欺诈交易，FP是指将正常交误判为欺诈交易。显然FN的代价大于FP的代价

2.3 样本x被预测为正类的充要条件

• 期望代价

  

• 样本x被预测为正类的充要条件：被分类为正样本的期望代价更小

• 阈值的设定

  

---

3. 代价敏感算法的分类

3.1 Direct methods（直接法）

• 算法构建过程中就已考虑不同分类错误的代价
• incorporates the misclassification costs into the learning algorithm, to design classifiers that are cost-sensitive in themselves

3.2 Wrapper-based methods (封装法)

• 在不改变算法本身的情况下，将非代价敏感算法转化为代价敏感算法，也称为meta-learning method

• 主要分为两大类

  • Thresholding(阈值法)
  • Sampling(采样法)
    • Weighting(权重法)
    • Costing

3.3 分类结构图

---

第二部分：Thresholding、Sampling与Weighting

1. Thresholding(阈值法)

• 多数情况下样本被正确分类的代价为0，因此阈值默认取

  

• 非代价敏感算法的阈值一般设定为0.5，改变此阈值则间接实现了代价敏感学习

  

• Thresholding的相关理论阐述

  • 论文：Cost-Sensitive Learning and the Class Imbalance Problem

  

---

2. Sampling(采样法)

2.1 Sampling(采样法)与Thresholding(阈值法)之间可相互转换

• Charles Elkan在论文The Foundations of Cost-Sensitive Learning中明确地指出了阈值与负样本比例之间的转换关系

• Theorem 1解读： 设算法将样本推断为正样本的初始阈值为p'，为了达到目标阈值p，则训练集中负样本的数量应从初始值n'变为n，且满足以下比例关系：

  

• 阈值的变化趋势与负样本数成正比关系：为了达到更小的目标阈值，则应对负样本进行欠采样(Under Sampling)

• Theorem 1为Sampling(采样法)提供了坚实理论基础: 严格论述了在二分类问题中，如何改变训练集中负样本的比例，使得非代价敏感算法学习到代价最小化的决策边界

  

2.2 过采样与欠采样

• 常见的过采样方法

  • SMOTE
  • Borderline_SMOTE
  • ADASYN
  • BOS：Borderline Over_Sampling (基于正类支持向量的线性外插与内插)

• 欠采样及其缺点：

  • UnderSampling(欠采样综述)
  • 欠抽样的缺点
    • 欠采样可能会丢失有价值的样本
    • 模型学习到的决策边界与理想边界之间角度偏离较大

2.3 实证分析：过采样方法性能对比

• 对比代码： oversampling_contrast.py

• 对比结果：

  • Coverage、G_Mean的定义： 模型评估指标

  

• 对比结论

  • 过采样算法的表现与具体的数据集、模型评估指标等多方面因素有关，不存在持续占优的过采样算法
  • 通常将少类样本视为正样本，所有过采样算法均有效地增加了正样本的数量，对Recall均有明显提升作用
  • BOS_SVM能灵活地选择内插或外插方式，生成的新样本更具合理性，有助于提升分类器的综合表现，AUC、G_Mean等指标也证明了此结论

---

3. Weighting(权重法)

3.1 Weighting等价于Sampling

• 高样本权重(大于1)可以视为对样本的复制，即为Over_Sampling；低样本权重(小于1)可以视为对样本的删减，即为Under_Sampling

  

• 样本的权重应与其被误分的代价成比： 少类样本一般为正样本，FN的代价高于FP的代价；应用Weighting(权重法)时，应对正样本赋予更高的权重

3.2 Weighting的实现

• 运用fit方法中的sample_weight参数实现

  • sklearn实现的监督算法、XGBoost、LightGBM均提供了fit方法，均含有sample_weight参数

  • 以sklearn文档为例： fit方法中的参数sample_weightt

    

• scale_pos_weight参数：

  • XGBoost与LightGBM不仅提供了sample_weight参数，还提供了scale_pos_weight参数

  • XGBOOST相关文档

• LightGBM相关文档

• 若scale_pos_weight的取值设定为某常数ratio，则等价于将正样本权重设置为ratio，负样本的权重设置为1；
• 代码验证： scale_pos_weight.py

---

4. Charles Elkan、Chris Drummond为Sampling、Weighting提供了理论基础

4.1 Charles Elkan明确指出Theroem 1既适用于Weighting，也适用于Sampling

4.2 Chris Drummond明确指出，在二分类问题中，各类别的先验概率与误分代价可相互转换

• 正样本的先验概率加倍，等价于FN的代价加倍或FP的代价减半

  

• 论文原文

  

4.3 理论小结

• Charles Elkan提出的Theroem 1论述了负样本在训练集中的占比与阈值之间的转换关系，并给出了严格的转换公式
• 在TP、TN的代价为0时，非代价敏感算法判定为正样本的后验概率阈值为0.5；若此阈值变更为[0, 1]区间内的其他值，则非代价敏感学习转化为代价敏感学习
• Sampling（或Weighting）通过改变正、负样本在训练集中的占比，内生地改变了阈值，从而间接实现了代价敏感学习

---

5. Ensemble(集成法)

5.1 AdaCost

• 代码实现： adacost.py

5.1 EasyEnsemble & BalanceCascade

• 论文： Exploratory Undersampling for Class-Imbalance Learning

• EasyEnsemble

  

• BalanceCascade

  

---

第三部分：论文解读与Reference

1. 经典论文《The Foundations of Cost-Sensitive Learning》解读

1.1 主要结论

• Theorem 1： 设算法将样本推断为正样本的初始阈值为p'，为了达到目标阈值p，则训练集中负样本的数量应从初始值n'变为n，且满足以下比例关系：

  

  • 若p<p'，则n<n'；若p>p'，则n>n'
  • 为了达到更小的目标阈值，则应对负样本进行欠采样(Under Sampling)

• Theorem 2： 若训练集中正类样本的先验概率由b变为b'，则从训练集中随机抽取的样本x为正样本的后验概率由p变为p'，其中

  

• Theorem 3： 对于二分类问题，若决策树的生成过程中以p(1-p)的平方根形式衡量数据集的不纯度，则训练集中正、负样本的先验概率变化不影响决策树的结构；其中p为数据集中正样本的先验概率

1.2 定理的证明

• 先证明Theorem 2

• 再证明Theorem 1

• Theorem 3的证明
  • 略，请查阅原论文；

---

2. Reference

• The Foundations of Cost-Sensitive Learning

• Cost-Sensitive Learning and the Class Imbalance Problem

• Exploiting the Cost (In)sensitivity of Decision Tree Splitting Criteria

• Cost-Sensitive Learning vs. Sampling: Which is Best for Handling Unbalanced Classes with Unequal Error Costs?

• Analysis and Visualization of Classifier Performance_ Comparison under Imprecise Class and Cost Distributions