分类中解决类别不平衡问题

1.什么是类别不平衡问题

如果不同类别的训练样例数目稍有差别，通常影响不大，但若差别很大，则会对学习过程造成困扰。例如有998个反例，但是正例只有2个，那么学习方法只需要返回一个永远将新样本预测为反例的学习器，就能达到99.8%的精度；然而这样的学习器往往没有价值，因为它不能预测出任何正例。

类别不平衡（class-imbalance）就是指分类任务中不同类别的训练样例数目差别很大的情况。在现实的分类学习任务中，我们经常会遇到类别不平衡，例如在通过拆分法解决多分类问题时，即使原始问题中不同类别的训练样例数目相当，在使用OvR（一对其余，One vs. Rest，简称OvR）、MvM（多对多，Many vs. Many，简称MvM）策略后产生的二分类任务扔可能出现类别不平衡现象，因此有必要了解类别不平衡性处理的基本方法。

2.解决类别不平衡问题

2.1欠采样方法

(1)什么是欠采样方法

直接对训练集中多数类样本进行“欠采样”（undersampling），即去除一些多数类中的样本使得正例、反例数目接近，然后再进行学习。

(2)随机欠采样方法

随机欠采样顾名思义即从多数类 S_{maj} 中随机选择一些样样本组成样本集 E 。然后将样本集 E 从 S_{maj} 中移除。新的数据集 S_{new-maj}=S_{maj}-E 。

缺点：

随机欠采样方法通过改变多数类样本比例以达到修改样本分布的目的，从而使样本分布较为均衡，但是这也存在一些问题。对于随机欠采样，由于采样的样本集合要少于原来的样本集合，因此会造成一些信息缺失，即将多数类样本删除有可能会导致分类器丢失有关多数类的重要信息。

为了克服随机欠采样方法导致的信息缺失问题，又要保证算法表现出较好的不均衡数据分类性能，出现了欠采样法代表性的算法EasyEnsemble和BalanceCascade算法。

(3)欠采样代表性算法-EasyEnsemble

算法步骤：

1)从多数类中有放回的随机采样n次，每次选取与少数类数目相近的样本个数，那么可以得到n个样本集合记作 \left\{ S_{1maj},S_{2maj},...,S_{nmaj} \right\} 。

2)然后，将每一个多数类样本的子集与少数类样本合并并训练出一个模型，可以得到n个模型。

3)最终将这些模型组合形成一个集成学习系统，最终的模型结果是这n个模型的平均值。

(4)欠采样代表性算法-BalanceCascade

BalanceCascade算法基于Adaboost，将Adaboost作为基分类器，其核心思路是：

1)在每一轮训练时都使用多数类与少数类数量相等的训练集，训练出一个Adaboost基分类器。

2)然后使用该分类器对全体多数类进行预测，通过控制分类阈值来控制假正例率（False Positive Rate）,将所有判断正确的类删除。

3)最后，进入下一轮迭代中，继续降低多数类数量。

扩展阅读：

Liu X Y, Wu J, Zhou Z H. Exploratory undersampling for class-imbalance learning[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(2): 539-550.

这篇论文提出了两种欠采样的方法：EasyEnsemble和BalanceCascade。

2.2过采样方法

(1)什么是过采样方法

对训练集里的少数类进行“过采样”（oversampling），即增加一些少数类样本使得正、反例数目接近，然后再进行学习。

(2)随机过采样方法

随机过采样是在少数类 S_{min} 中随机选择一些样本，然后通过复制所选择的样本生成样本集 E ，将它们添加到 S_{min} 中来扩大原始数据集从而得到新的少数类集合 S_{new-min} 。新的数据集 S_{new-min}=S_{min}+E 。

缺点：

对于随机过采样，由于需要对少数类样本进行复制来扩大数据集，造成模型训练复杂度加大。另一方面也容易造成模型的过拟合问题，因为随机过采样是简单的对初始样本进行复制采样，这就使得学习器学得的规则过于具体化，不利于学习器的泛化性能，造成过拟合问题。

为了解决随机过采样中造成模型过拟合问题，又能保证实现数据集均衡的目的，出现了过采样法代表性的算法SMOTE和Borderline-SMOTE算法。

(3)过采样代表性算法-SMOTE

SMOTE全称是Synthetic Minority Oversampling即合成少数类过采样技术。SMOTE算法是对随机过采样方法的一个改进算法，由于随机过采样方法是直接对少数类进行重采用，会使训练集中有很多重复的样本，容易造成产生的模型过拟合问题。而SOMT算法的基本思想是对每个少数类样本 x_{i} ，从它的最近邻中随机选择一个样本 \hat{x_{i}} （ \hat{x_{i}} 是少数类中的一个样本），然后在 x_{i} 和 \hat{x_{i}} 之间的连线上随机选择一点作为新合成的少数类样本。

SMOTE算法合成新少数类样本的算法描述如下：

1).对于少数类中的每一个样本 x_{i} ，以欧氏距离为标准计算它到少数类样本集 S_{min} 中所有样本的距离，得到其k近邻。

2).根据样本不平衡比例设置一个采样比例以确定采样倍率N，对于每一个少数类样本 x_{i} ，从其k近邻中随机选择若干个样本，假设选择的是 \hat{x_{i}} 。

3).对于每一个随机选出来的近邻 \hat{x_{i}} ，分别与 x_{i} 按照如下公式构建新的样本。

x_{new}=x_{i}+rand(0,1)\times(\hat{x_{i}}-x_{i})

我们用图文表达的方式，再来描述一下SMOTE算法。

1).先随机选定一个少数类样本 x_{i} 。

2).找出这个少数类样本 x_{i} 的K个近邻（假设K=5），5个近邻已经被圈出。

3).随机从这K个近邻中选出一个样本 \hat{x_{i}} （用绿色圈出来了）。

4).在少数类样本 x_{i} 和被选中的这个近邻样本 \hat{x_{i}} 之间的连线上，随机找一点。这个点就是人工合成的新的样本点（绿色正号标出）。

SMOTE算法摒弃了随机过采样复制样本的做法，可以防止随机过采样中容易过拟合的问题，实践证明此方法可以提高分类器的性能。但是SMOTE算法也存以下两个缺点：

1)由于对每个少数类样本都生成新样本，因此容易发生生成样本重叠的问题。

2)在SMOTE算法中，出现了过度泛化的问题，主要归结于产生合成样本的方法。特别是，SMOTE算法对于每个原少数类样本产生相同数量的合成数据样本，而没有考虑其邻近样本的分布特点，这就使得类间发生重复的可能性增大。

解释缺点2)的原因：结合前面所述的SMOTE算法的原理，SMOTE算法产生新的人工少数类样本过程中，只是简单的在同类近邻之间插值，并没有考虑少数类样本周围多数类样本的分布情况。如3图所示，绿色正号1、2分布在多数类样本周围，它们离多数类样本最近，这就导致它们有可能被划分成多数类样本。因此从3图中可以看出，SMOTE算法的样本生成机制存在一定的盲目性。

为了克服以上两点的限制，多种不同的自适应抽样方法相继被提出，其中具有代表性的算法包括Borderline-SMOTE算法。

扩展阅读：

Chawla N V, Bowyer K W, Hall L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of artificial intelligence research, 2002, 16: 321-357.

这篇论文提出了SMOTE算法。

(4)Borderline-SMOTE算法介绍

对于Borderline-SMOTE算法最感兴趣的就是用于识别少数类种子样本的方法。在Borderline-SMOTE算法中，识别少数类种子样本的过程如下：

1)首先，对于每个 x_{i}\subset S_{min} ,确定一系列最近邻样本集，成该数据集为 S_{i-KNN} ，且 S_{i-KNN}\subset S 。

2)然后，对每个样本 x_{i} ，判断出最近邻样本集中属于多数类样本的个数，即： \left| S_{i-KNN}\cap S_{maj} \right| 。

3)最后，选择满足下面不等式的 x_{i} 。

\frac{k}{2}<\left| S_{i-KNN}\cap S_{maj} \right|<k

上面式子表明，只有最近邻样本集中多数类多于少数类的那些 x_{i} 才会被选中形成“危险集”(DANGER)。因此，DANGER集中的样本代表少数类样本的边界（最容易被错分的样本）。然后对DANGER集中使用SMOTE算法在边界附近产生人工合成少数类样本。

我们可以看出，如果 \left| S_{i-KNN}\cap S_{maj} \right| = k 。即： x_{i} 的所有k个最近邻样本都属于多类。如4图所示的样本点C，我们就认为样本点C是噪声且它不能生成合成样本。

通过上面的介绍，我们对Borderline-SMOTE算法有了一定的了解。为了让大家理解的更透彻这个算法，我再给大家画一个流程图，详细介绍一下。

流程图5中，训练样本集为F，少数类样本 S_{min}=\left\{ f_{1},f_{2},...,f_{n} \right\} 。

1)步骤一：

(i)计算少数类样本集 S_{min} 中每一个样本在训练集F中的k个最近邻。

(ii)然后，根据这k个最近邻对 S_{min} 中的样本进行归类：

假设这k个最近邻都是多数类样本，则我们将该样本定义为噪声样本，将它放在 N^{'} 集合中。
反正k个最近邻都是少数类样本则该样本是远离分类边界的，将其放入S集合中。
最后，K个最近邻即有多数类样本又有少数类样本，则认为是边界样本，放入B集合中。

2)步骤二：

(i)设边界样本集 B=\{f_{1}^{'},f_{2}^{'},...,f_{n}^{'}\} ，计算B集合中的每一个样本 f_{i}^{'},i=1,2,...,n ，在少数类样本集 S_{min} 中的K个最近邻，组成集合 f_{ij} 。

(ii)随机选出s(1<s<n)个最近邻。

(iii)计算出它们各自与该样本之间的全部属性的差值 d_{ij} 。 d_{ij}=f_{i}^{'}-f_{ij},j=1,2,...s 。

(iv)然后乘以一个随机数 r_{ij} , r_{ij}\in(0,1) 。如果 f_{ij}是 N^{'} 集合或S集合中的样本，则 r_{ij}\in(0,0.5) 。

(v)最后生成的人工少数类样本为： h_{ij}=f_{i}^{'}+r_{ij} \ast d_{ij},j=1,2,...,s 。

3)步骤三:

重复步骤2的过程，直到生成人工少数类样本的数目满足要求，达到均衡样本集的目的后结束算法。

扩展阅读：

Han H, Wang W Y, Mao B H. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[C]//International Conference on Intelligent Computing. Springer, Berlin, Heidelberg, 2005: 878-887.

这篇文章提出了Borderline-SMOTE算法。

2.3代价敏感学习(cost-sensitive learning)

(1)代价矩阵

采样算法从数据层面解决不平衡数据的学习问题；在算法层面上解决不平衡数据学习的方法主要是基于代价敏感学习算法（Cost-Sensitive Learning）。

在现实任务中常会遇到这样的情况：不同类型的错误所造成的后果不同。例如在医疗诊断中，错误地把患者诊断为健康人与错误地把健康人诊断为患者，看起来都是犯了“一次错误”，但是后者的影响是增加了进一步检查的麻烦，前者的后果却可能是丧失了拯救生命的最佳时机；再如，门禁系统错误地把可通行人员拦在门外，将使得用户体验不佳，但错误地把陌生人放进门内，则会造成严重的安全事故；在信用卡盗用检查中，将正常使用误认为是盗用，可能会使用户体验不佳，但是将盗用误认为是正常使用，会使用户承受巨大的损失。为了权衡不同类型错误所造成的不同损失，可为错误赋予“非均等代价”（unequal cost）。

代价敏感学习方法的核心要素是代价矩阵，如表1所示。其中 cost_{ij} 表示将第 i 类样本预测为第 j 类样本的代价。一般来说， cost_{ij}=0 ;若将第0类判别为第1类所造成的损失更大，则 cost_{01}>cost_{10} ;损失程度相差越大， cost_{01}与cost_{10} 的值差别越大。当 cost_{01}与cost_{10} 相等时为代价不敏感的学习问题。

(2)代价敏感学习方法

基于以上代价敏感矩阵的分析，代价敏感学习方法主要有以下三种实现方式，分别是：

1).从学习模型出发，对某一具体学习方法的改造，使之能适应不平衡数据下的学习，研究者们针对不同的学习模型如感知机、支持向量机、决策树、神经网络等分别提出了其代价敏感的版本。以代价敏感的决策树为例，可以从三个方面对其进行改造以适应不平衡数据的学习，这三个方面分别是决策阈值的选择方面、分裂标准的选择方面、剪枝方面，这三个方面都可以将代价矩阵引入。

2).从贝叶斯风险理论出发，把代价敏感学习看成是分类结果的一种后处理，按照传统方法学习到一个模型，以实现损失最小为目标对结果进行调整，优化公式如下所示。此方法的优点在于它可以不依赖所用的具体分类器，但是缺点也很明显，它要求分类器输出值为概率。

H\left( x \right)=argmin\left( \sum_{j\in\{-,+\}}^{}{p(j|x)C(i,j)} \right)

3).从预处理的角度出发，将代价用于权重调整，使得分类器满足代价敏感的特性，下面讲解一种基于Adaboost的权重更新策略AdaCost算法。

(3)AdaCost算法

要想了解AdaCost算法，我们得先知道Adaboost算法，如图6所示。Adaboost算法通过反复迭代，每一轮迭代学习到一个分类器，并根据当前分类器的表现更新样本的权重，如图中红框所示，其更新策略为正确分类样本权重降低，错误分类样本权重增大，最终的模型是多次迭代模型的一个加权线性组合。分类越准确的分类器将会获得越大的权重。

AdaCost算法修改了Adaboost算法的权重更新策略，其基本思想是对代价高的误分类样本大大地提高其权重，而对于代价高的正确分类样本适当地降低其权重，使其权重降低相对较小。总体思想是代价高样本权重增加得大降低的慢。其样本权重按照如下公式进行更新。其中 \beta_{-}和\beta_{+} 分别表示样本被正确和错误分类情况下的 \beta 的取值。

D_{t+1}(i)=\frac{D_{t}(i)exp(-\alpha_{t}h_{t}(x_{i})y_{i}\beta_{i})}{Z_{t}}

\beta_{+}=-0.5C_{i}+0.5

\beta_{-}=0.5C_{i}+0.5

2.4不平衡学习的评价方法

(1)F1度量

这一部分涉及到模型的评价方法，如果你还没有学习过，可以看我的公众号之前发的关于这部分文章。同时，我也把链接地址贴出来，供大家快速学习。

例如在癌症预测的场景中，假设没有患癌症的样本为正例，患癌症的样本为反例，反例占的比例很少（大概0.1%），如果直接把分类器设置为预测都是正例，那么精度和查准率的值都是99.9%。可见精度、错误率和查准率都不能表示不平衡数据下的模型表现。而F1值则同时考虑了少数类的查准率和召回率，因此能衡量不平衡数据下模型的表现。

Accuracy(精度)=\frac{(TP+TN)}{(TP+FN+FP+TN)}

ErrorRate(错误率)=1-accuracy

Precision(查准率)=\frac{TP}{TP+FP}

Recall(召回率)=\frac{TP}{TP+FN}

F_{1}=\frac{2\times TP}{样例总数+TP-TN}

(2)G-Mean

G-Mean是另外一个指标，也能评价不平衡数据的模型表现，其计算公式如下。

G-Mean=\sqrt{\frac{TP}{TP+FN}\times \frac{TN}{TN+FP}}

(3)ROC曲线和AUC面积

我的这篇文章把ROC曲线和AUC面积分析的全面。ROC曲线和AUC面积可以很好的评价不平衡数据的模型表现。