不均衡数据集的分类模型学习方法

简介

不均衡数据集指的是在分类问题中,数据集的两个类别之间的数量差别到达100:1,1000:1甚至10000:1的情况。当然,有些时候在多分类问题(multiclass classification)中也会出现。

如何在不均衡的数据集(imbalanced data)下进行学习,是一个很重要的问题,原因是这样的数据集会很大程度上限制我们的分类模型的准确性,正如文章所说——

“大部分标准的分类算法都期待一个均衡的类别分布,以及相近的误分类损失”。

在不均衡数据集的研究中,主要的领域有医疗分析、欺诈检测、网络入侵识别、溢油检测等。一个非常经典的数据集是乳腺摄影数据集(Mammography Data Set),在这个数据集中,有若干医学摄影图片以及其对应的二分类标签「健康」,「癌性」。

Image result for mammography data set
Mammography Data Set

在这个数据集中,有10923例阴性以及260例阳性。使用传统分类算法,非常容易出现的情况就是,阴性以几乎100%的正确率被成功分类,但是阳性的分类正确性却低至10%以下,在这个情境下,就是多达234例阳性样本被误诊。

在这一类数据集下,我们的目标就变成了在不严重损害大类(major class)的准确性的基础上,尽量让小类(minor class)的分类准确性提高。

不均衡问题的特性

内在不均衡和外在不均衡

数据集不均衡的成因可能是内在的(intrinsic)或者外在的(extrinsic),如之前所述的肿瘤识别,由于样本在真实世界的分布本身就是不均匀的,所以是内在不均衡。

另一方面,还会有一些情况,原本均匀分布的样本数据,由于采样偏差,导致最终进入数据集的时候样本不均匀了,这种情况则被称之为外在不均衡。这个情况最为著名的就是“欺诈检测”数据集。因为真实世界中,那些欺诈者,基本在申请阶段就已经被拒贷了,而我们无法获取到“如果他们借了钱,会不会逾期”,进而无法进入我们的训练数据集。

类间不均衡和类中不均衡

类间不均衡与类中不均衡同样值得注意,正如下图所示,在一些比较复杂的数据上,不仅不同的类别个数相差巨大,同一类样本之间,也会有不同的概念。对于小类别中间的小样本,样本数极少(underrepresented),分类器非常难以学习到完整的分类函数。

图a)只包含了类间不均衡,即五角星表示的“小类”样本个数远小于“圆圈”代表的“大类”,
图b)则同时包含了类间不均衡、类中不均衡、重叠、噪音等等……

小样本问题(small sample size problem)是传统不均衡问题之外的新兴研究方向,讲的是数据的维度和样本的个数显著不均衡。比较有代表性的有人脸识别、基因序列分析等。对于单纯的小样本问题,传统的做法有数据降维等措施。但是倘若小样本问题和类别不均衡同时存在,不仅小类中的样本数量过于稀缺,而且也会导致传统的解决算法无法归纳出有效的分类函数。是以后的研究重点。

不均衡数据集学习的state-of-art算法

当标准的学习算法遇上不均衡数据时,归纳出来的用于描述小类的规则通常比描述大类的规则要少要弱。这既是由于标签数量上的差别,又是由于小类的样本由于数量少本身可信度就较低。

基于采样的算法

Random Sampling

分为随机过采样(random oversampling)和随机欠采样(random undersampling),随机过采样的思路是从小类里面,随机复制若干样本点,加到原来的集合中,使数据集均衡。而随机欠采样则是从大类里面,随机删除若干样本点,使得数据集分布均衡。

随机欠采样可能导致遗失某些重要的信息,而随机过采样则有过拟合风险。

Informed Undersampling

首先讲讲Easy Ensemble算法,这个算法很简单,使用多次随机欠采样,每次都训练一个分类器,然后再将每次欠采样训练出来的分类器组合到一起,形成最终的分类器。

接着是Balance Cascade算法,这个算法是一个迭代算法。

  1. 在大类样本集合S_{maj}中选择一个子集E满足|E| = |S_{min}|
  2. 使用N = {E \cup S_{min}}进行训练,得到分类器
  3. 过滤出N中所有被正确归类的大类中的样本N_{maj}^*
  4. N_{maj}^*中的样本点剔除S_{maj},回到第1步

还有基于KNN的采样算法,该算法使用的四个规则来筛选出比较重要的大类样本点,用这些重要的样本点进行模型的训练。

  • NearMiss-1方法选择与“三个最接近的小类样本”的平均距离最小的大类样本点;
  • NearMiss-2方法选择与“三个最远的少数类样本”的平均距离最小的大类样本点;
  • NearMiss-3方法为每个小类样本选择给定数量的最接近的大类样本点,以确保每个小类样本点都被一些大类样本点包围;
  • “最大距离”方法选择了大多数类的样本点,这些样本点与“平均距离是最近的三个少数类”距离最大。

研究发现,其中NearMiss-2获得的结果较好。

Synthetic Sampling With Data Generation

合成少数子过采样技术(the synthetic minority oversampling technique, SMOTE)对于每个小类样本,寻找同为小类的K近邻,并使用插值法随机选取其连线中间的一个点最为一个新的过采样点。

(1)   \begin{equation*}x_{new} = x_i + (\hat{x_i} - x_i) \times \delta\end{equation*}

具体来说,上式中x_i为小类中的一个样本点,\hat{x_i}x_i的位于小类集合中的K近邻之一,\delta是一个随机[0,1]区间内实数。

Adaptive Synthetic Sampling

先介绍Borderline-SMOTE算法,和普通SMOTE算法不同的是,Borderline-SMOTE算法对于每一个小类样本点,都统计了其最近邻居中大类和小类的样本点个数。

  • 如果小类邻居多于一半,则该点是内部点,记为SAFE
  • 如果小类邻居少于一半,则该点是边界点,记为DANGER
  • 如果小类邻居为0,则该点为噪声,记为NOISE

统计完成后,使用DANGER集合点进行SMOTE的过采样算法。

ADASYN算法在此基础上又做了优化,去掉了“一半”这个人为的常数。使得过采样更加的自然。

(2)   \begin{equation*}G = (|S_{maj}| - |S_{min}|) \times \beta\end{equation*}

这里面\beta \in [0,1]是一个人为设计的常数,G是描述了“究竟小类需要补充多少个样本点?”

接下来,对于每一个小类样本点计算

(3)   \begin{equation*}\Gamma_i = \frac{\Delta_i / K}{Z}\end{equation*}

其中\Delta_i表示样本点的K近邻中有多少属于大类S_{maj}KZ用于归一化,使得\sum_{\Gamma_i} = 1

最终,每一个点按照下面式子,计算需要生成的点的个数,并使用SMOTE算法的方式进行过采样

(4)   \begin{equation*}g_i = \Gamma_i \times G\end{equation*}

Sampling With Data Clean Technique

Tomek link是一个基于数据清洗的技术,适用于一个经过过采样之后的数据集。其目的是为了解决“由于过采样导致的类别存在边界覆盖,进而影响分类器训练”这个问题。

其核心思想是找到两个离的很近的x_i \in  S_{maj}x_j \in S_{min},令d(x_i, x_j)表示x_ix_j的距离,那么(x_i, x_j)被称为Tomek link当且仅当不存在x_k,满足d(x_i, x_k) < d(x_i, x_j)d(x_j, x_k) < d(x_i, x_j)

Tomek link的出现意味着x_ix_j要不然有一个是噪音,要不然就是他们两个位于分类的交界处。将他们同时删除(或删除大类的那一个),可以有效的防止出现类别边界模糊,有利于提高分类器效果。

Cluster-Based Sampling Method

基于聚类的采样算法可以保证类间的不均衡也被关注。

具体来说,该算法首先使用迭代的方式,找到不同的团,这里使用了经典的KNN算法——

  1. 在两个类别中,分别随机选择K个团中心;
  2. 对于每个样本点,都被归类到最近的团中心;
  3. 团中心进行重新计算,用当前所有归类到该团的样本的坐标均值作为新一轮迭代的团中心;
  4. 跳至第2步

接着,将不同的团使用过采样的方式放大到同等规模。如下图所示——

Integration of Sampling and Boosting

SMOTEBoost 算法分为若干轮,每一轮都涉及到重新采样,使用递增的方式建立模型。每一轮,都着重采样哪些不能被上一轮模型所解释的样本。这样,分类器会逐渐习惯去拟合哪些少数的样本,因为他们更大概率会不能被上一轮的模型分类。

对于DataBoost-IM算法来说,则依照一定的比例来采样那些不容易被学习的样本。

基于修改成本函数的算法

一些对于成本敏感的学习算法,使用成本(cost)函数来量化误分类的程度。与其像基于采样的算法构造均衡的数据分布,不如直接设计一个不同的算是度量,使之能够适应不均衡的数据。

Cost-Sensitive Learning Framework

我们定义C(Min, Maj)表示将大类样本误分类为小类的成本,C(Maj, Min)则相反。那么成本敏感(cost-sensitive)学习的目标就是最小化训练集的总体成本,也就是所谓的贝叶斯条件风险(Bayes Conditional Risk)。

这个函数也可以非常容易的扩充到多标签的分类中,具体C矩阵定义如下——

此时,条件风险被定义为

(5)   \begin{equation*}R(i|x) = \sum_i{P(j|x)C(i,j)}\end{equation*}

这里P(j|x)被定义为给定样本x,实际上为类别j的概率。

通常的分类器,都默认分类错误有1的代价,而分类正确没有代价——

(6)   \begin{equation*} C(i,j) = \left\{ \begin{aligned} 1 & (i \neq j) \\ 0 & (i=j) \end{aligned} \right.\end{equation*}

而在非均衡学习中,我们需要保证有C(Maj, Min) > C(Min, Maj),以使得分类器能够更好地分辨大类小类。而接下来的算法,一大特点就是都使用了不同的办法,来讲我们认为定义的成本矩阵放到具体算法实现中——

  • 第一类技术将误分类成本作为数据空间权重应用于数据集;
  • 第二类将成本最小化成本的技巧运用在模型组合上;
  • 最后一类技术将对成本敏感的函数或特性直接纳入分类模型中,以便将对成本敏感的框架拟合到这些分类器的结果中。

Cost-Sensitive Dataspace Weighting with Adaptive Boosting

这里涉及了AdaBoost系列算法,包括AdaBoost.M1,AdaC1,AdaC2,AdaCost,CSB1,CSB2。以AdaBoost.M1为例讲解这类算法的核心思路——

对于数据集迭代,每一轮拥有不同的权值D_{t}(i)

(7)   \begin{equation*}D_{t+1}(i) = D_t(i) exp(-\alpha_t h_t(x_i) y_i) / Z_t\end{equation*}

其中\alpha_t = \frac{1}{2} ln(\frac{1-\epsilon_t}{\epsilon_t})。这个式子的粗略理解是如果一个样本被误分类,那么下一轮迭代将拥有更大的权值。

Cost-Sensitive Decision Trees

决策树的叶子节点是类别,非叶子节点是规则。建立决策树的过程是从上到下,逐层挑选一个最有分类性的规则,并将样本按照这个规则递归到两个子树处理。

Contact-lens decision tree
决策树

决策树有两个步骤,第一个是从上到下的分裂,第二个是从下到上的修建。

决策树的分裂使用了不纯度函数(impurity function),这个函数是否超过特定阈值决定了一个节点的分裂与否。不同的不纯度函数对于不均衡数据有不同的敏感度,比如传统的准确率函数就非常敏感,而Gini函数、熵函数(Entropy)、DKM函数就不那么敏感。其中,DKM函数生成的未修剪决策树相对较小。

决策树的修剪有利于增加其普遍性,但是对于不均衡数据,决策树的修剪可能会减掉小类的样本,降低模型准确度。类似于Laplace修剪技术也被提出用于让决策树的修剪不那么糟糕。

Cost-Sensitive Neural Networks

一个神经网络,会构造基于模型输出与目标距离的损失函数

(8)   \begin{equation*}E(\omega) = \frac{1}{2} \sum(t_k - o_k)^2\end{equation*}

其中\omega是模型权值,t_k,o_k分别是模型的目标与输出。在每一轮迭代,神经网络都会计算每个权值对于损失函数的梯度,用这个梯度更新权值,使得网络误差函数更小。

(9)   \begin{equation*}\Delta \omega_n = -\eta \nabla_{\omega} E(\omega_n)\end{equation*}

其中\eta是学习速率,\nabla_{\omega}是梯度算子。

成本敏感学习可以以下面四种方式引入模型——

  1. 成本敏感可以体现在对最终估计概率的修正上面
  2. 模型输出o_k可以被修正为成本敏感
  3. 学习速率可以被修正为成本敏感
  4. 误差函数最小化中的误差可以是成本敏感的

这四种方式都各有非常多的研究成果,这里就略去不谈。

基于核函数的算法和主动学习

Kernel-Based Learning Framework

这里讨论支持向量机(SVM)在不均衡数据集下的研究。由于支持向量机试图最小化总误差,因此它们天生就有优化大类样本的偏好。在一个理想模型里面,大类小类通过一条直线分隔,SVM分类的界限将远远偏离实际的界限。

Integration of Kernel Methods with Sampling Methods

大量研究都尝试将采样算法与SVM结合,其中比较有代表性的是GSVM-RU,将GSVM与欠采样算法结合。通过迭代的算法,每一轮迭代,都将大类中被定为支持向量的样本点移出。实现欠采样的目标。

位于最大间隔超平面边界上的点被称为支持向量

Kernel Modification Methods for Imbalanced Learning

直接修改核函数也是很多研究者研究的方向,这些研究的共同点是尝试向原来的SVM添加一个模块或替换一个模块,实现对不平衡数据的支持。包括了LOO-AUC、PSVM、P2PKNNC等等算法

Active Learning Methods for Imbalanced Learning

主动学习通过某种策略找到未进行类别标注的样本数据中最有价值的数据,交由专家进行人工标注后,将标注数据及其类别标签纳入到训练集中迭代优化分类模型,改进模型的处理效果。

在主动学习领域,文章指出,主动学习和基于核函数的学习算法有共通之处,所以有必要放在一起讨论。比如说,一个在SVM算法中靠近超平面的样本点就是比较有意义的。当然,如果遇到了数据不均衡,主动学习也会有很多需要研究的问题。

Additional Methods for Imbalanced Learning

不均衡数据的处理方式还有很多无法被分类到之前类别的算法。比如所有的多标签算法、小样本数量的处理算法、基于单个标签的学习算法等等。

评价指标

使用下表来定义正/负样本被模型正确/错误分类的个数,是后续统计指标的基本依赖变量——

True positives(TP):  被正确地划分为正例的个数,即实际为正例且被分类器划分为正例的实例数;
False positives(FP): 被错误地划分为正例的个数,即实际为负例但被分类器划分为正例的实例数;
False negatives(FN):被错误地划分为负例的个数,即实际为正例但被分类器划分为负例的实例数;
True negatives(TN): 被正确地划分为负例的个数,即实际为负例且被分类器划分为负例的实例数。 

单数值指标

这里假设小类为正类(positive),大类为负类(negative),有准确率(accuracy)和错误率(error rate)

(10)   \begin{equation*}Accuracy = \frac{TP+TN}{P_C+N_C}\end{equation*}

(11)   \begin{equation*}ErrorRate = 1 - Accuracy\end{equation*}

(12)   \begin{equation*}Precesion = \frac{TP}{TP+FP}\end{equation*}

(13)   \begin{equation*}Recall = \frac{TP}{TP+FN}\end{equation*}

(14)   \begin{equation*}F\_{Measure} = \frac{(1+\beta)^2 \cdot Recall \cdot Precesion}{\beta^2 \cdot Recall + Precesion}\end{equation*}

(15)   \begin{equation*}G\_{Mean} = \sqrt{\frac{TP}{TP+FN} \times \frac{TN}{TN+FP}}\end{equation*}

对于(1)(2)来说,虽然比较符合常理,但是容易被欺骗,比如对于5%正类,95%负类的数据,全部分类为负类可以达到95%正确率。这类“对于分布敏感”的指标不是用于不均衡数据集的算法效果评估。

对于精准率(3)来说,描述了“对于所有被分类器预测为正的样本,有多少预测对了?”
对于召回率(4)来说,描述了“有多少真正是正的类别,被正确预测了?”
通过观察公式,可以发现,精准率(3)是数据分布敏感的,而召回率(4)是数据分布不敏感的。
如果使用恰当的话,精准率和召回率已经足以描述用以评价分类器好坏的所有信息了。

F-Measures(5)是精准率率和召回率的合并,并用参数\beta调整双方的权重

G-Mean(6)则使用了正类准确率和负类准确率的比例来刻画分类器的偏好。

上面这些单变量指标虽然已经足够好了,但是还是没法解决一个问题“如何比较两个分类器孰好孰坏?”

ROC曲线

定义真阳性率(TPRate)和假阳性率(FPRate)

(16)   \begin{equation*}TP\_Rate = \frac{TP}{P_C}; FP\_Rate = \frac{FP}{N_C}\end{equation*}

ROC曲线的空间是一个二维平面,横坐标为假阳性率,纵坐标为真阳性率。

对于硬标签分类器(hard-type classifier),输出是类别标签,其效率可以用一个坐标点(FPR, TPR)画在ROC空间上。我们知道完美分类是A(0,1),也就是说越靠近A,分类器的效果越好,而灰色部分则是表示分类器没有随机分类好。

一个软标签分类器(soft-type classifier),输出是类别属于“正类”的概率,这种情况下,我们可以画出一条ROC曲线,在这种情况下,我们可以用曲线下方的面积来衡量分类器的效果。

PR曲线

研究发现ROC曲线有些时候会把模型的结果看的过于乐观,而PR曲线(Precession-Recall Curve)则是为了弥补这一缺憾的。

曲线和ROC曲线的唯一区别在于,ROC曲线使用(FPR, TPR)刻画分类器的效果,而PR曲线则用(Precesion, Recall)来刻画分类器效果。

比较两个曲线的公式,我们会发现FP_Rate在N_C非常大的时候,无法捕捉到FP的数量变化。

代价曲线

代价曲线(Cost Curve)尝试解释的问题是“一个分类器在处理先验概率不同样本表现如何?”。在ROC曲线中的每一个点都对应了代价曲线里面的一条线。

在ROC曲线中的坐标(FP, TP),都可以计算出期望的代价

(17)   \begin{equation*}E(C) = (1-TP-FT)\times PCF(+)+FP\end{equation*}

其中E(C)是期望代价,PCF(+)是样本为正的先验概率。

我们可以将手中若干可用的分类器的代价直线下方区域求交,获得的面积就是代价曲线,该曲线的含义是在“已知先验概率的条件下选择分类器,能够达到的最小期望代价是多少?”

多分类问题的拓展指标

上述的很多指标都可以拓展到多标签分类问题中,包括多标签ROC,M-Measures,Misclassification Cost……

未来我们该怎么做?

了解不均衡分类算法的本质

现在的很多研究都是偏技术的,为某个问题设计了一个巧妙地算法,能够优化某一个评价指标。但是这些算法究竟如何优化了模型表现,并没有人能够说清楚。

  1. 与从原始分布学习相比,什么样的假设会使不平衡学习算法更好地工作?
  2. 应该在多大程度上平衡原始数据集?
  3. 不平衡的数据分布如何影响学习算法的计算复杂度?
  4. 在数据分布不平衡的情况下,普遍的误差范围是多少?
  5. 对于特定的算法和应用领域,是否有一种通用的理论方法可以减轻学习不平衡数据集的障碍?

需要一个标准化的评价体系

上面讲的那些基于曲线的评价指标非常重要,需要行业能够有意识的将其纳入评价指标,这样才能有助于模型的迭代比较。

增量数据上的不均衡学习

在网络监控,流媒体,网络挖掘领域,数据往往是增量到达的,在增量学习如果存在不平衡该怎么办,有以下几个问题需要思考:

  1. 如果在学习期间的中间引入不平衡,我们如何自主调整学习算法?
  2. 我们是否应该考虑在增量学习期间重新平衡数据集?如果是这样,我们怎么能做到这一点呢?
  3. 我们如何积累经验并利用这些知识自适应地改进从新数据中的学习?
  4. 当新引入的概念也不平衡时(即概念漂移的不平衡问题),我们如何处理这种情况?

半监督学习与不均衡数据集

半监督学习中,同时存在带标注和不带标注的数据,这个时候,如果存在不平衡又改如何处理,思考如下问题:

  1. 如何识别未标记的数据示例是来自平衡的还是不平衡的底层分布?
  2. 给定一个带有标签的不平衡训练数据,有哪些有效的方法来恢复未标记的数据示例?
  3. 在给定不平衡标记数据的恢复过程中(通过传统的半监督学习技术),可能会引入什么样的偏差?

参考资料

原始论文:He, H., & Garcia, E. A. (2009). Learning from imbalanced data. IEEE Transactions on knowledge and data engineering21(9), 1263-1284.

机器学习模型性能评估二:代价曲线与性能评估方法总结:https://zhuanlan.zhihu.com/p/53781144

机器学习基础(1)- ROC曲线理解:https://www.jianshu.com/p/2ca96fce7e81

adaboost.M1与adaboost.M2差别比较:https://blog.csdn.net/tyh70537/article/details/76675098

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据