[转载]不平衡数据下的机器学习方法简介

出处

Xubao blog: 不平衡数据下的机器学习方法简介 http://baogege.info/2015/11/16/learning-from-imbalanced-data/

引言

不平衡数据的场景有, 搜索引擎的点击预测,电子商务领域的商品推荐,信用卡欺诈,网络攻击识别等等.

问题定义

顾名思义,数据集样本类别极不平衡. 以二分类为例,假设数据集为S, 多数类和少数类的样本比例达到100:1, 1000:1甚至10000:1. 这种情况下是不平衡数据,不平衡数据的学习就是需要在如此分布不平衡的数据集中学习有用的信息.

为什么不平衡学习

传统的学习方法以降低总体分类精度为目标, 将所有样本一视同仁, 同等对待,造成分类器在多数类的分类精度较高,而在少数类的分类精度很低.比如二分类, 数据比例为499:1, 那么只要将学习器全部预测为负类,准确率(精度)可以达到非常高,但很显然这并不是一个很好的学习效果, 因此传统的学习算法在不平衡数据集中具有较大的局限性.

)

不平衡学习的方法

解决方法主要分为两个方面:

  1. 从数据的角度出发, 主要方法为抽样. 通过某种策略进行抽样,进而样我们的数据相对均衡一点;
  2. 从算法的角度出发,考虑不同误分类情况代价的差异性对算法进行优化,使得算法在不平衡数据下也能有较好的效果.

采样

采样算法通过某一种策略改变样本的类别分布, 以达到将不平衡分布的样本转换为相对平衡分布的样本的目的.

随机采样

随机采样算法是采样算法中最简单也最直观易懂的一种方法. 随机采样主要分为两种类型, 分别为随机欠采样和随机过采样.随机欠采样顾名思义即从多数类中随机选择少量样本E再合并原有少数类样本作为新的训练数据集, 新的数据集为$S_{min} + E$. 随机欠采样有两种类型分别为有放回和无放回两种. 无放回欠采样在对多数类某样本采样后不会再被重复采样, 有放回采样则有可能. 随机过采样则正好相反, 通过多次有放回随机过采样从少数类中抽取数据集E, 采样的数量大于原有少数类的数量,最终训练集为$S_{maj} + E$.

随机采样通过改变多数类或少数类样本比例以达到修改样本分布的目的,从而让样本分布较为均衡,但是他们也存在一些问题。对于随机欠采样,由于采样的样本要少于原样本集合,因此会造成一些信息缺失,未被采样的样本往往带有很重要的信息。对于随机过采样,由于需要对少数类样本进行复制因此扩大了数据集,造成模型训练复杂度加大,另一方面也容易造成模型的过拟合问题。针对这些问题提出了几种其它的采样算法。

SMOTE采样

Synthetic Minority Oversampling Technique即合成少数类过采样技术. 它是基于随机过采样算法的一种改进方案,由于随机过采样采取简单复制样本的策略来增加少数类样本,这样容易产生模型过拟合的问题,即使得模型学习到的信息过于特别(Specific)而不够泛化(General),SMOTE算法的基本思想是对少数类样本进行分析并根据少数类样本人工合成新样本添加到数据集中,算法流程如下。

  1. 对于少数类中每一个样本x,以欧氏距离为标准计算它到少数类样本集$S_{min}$中所有样本的距离,得到其k近邻;
  2. 根据样本不平衡比例设置一个采样比例以确定采样倍率N,对于每一个少数类样本x,从其k近邻中随机选择若干个样本, 假设选择的近邻为$\hat x$;
  3. 对于每一个随机选出的近邻$\hatx$,分别与原样本按照如下公式构建新的样本. $x_{new} = x + rand(0,1) * (\hatx- x)$

过采样, 每个样本, k近邻, 随机性—> 新的少数类样本.

该算法主要存在两方面的问题:一是在近邻选择时,存在一定的盲目性。从上面的算法流程可以看出,在算法执行过程中,需要确定k值,即选择多少个近邻样本,这需要用户自行解决。从k值的定义可以看出,k值的下限是sampling_rate(sampling_rate为从k个近邻中随机挑选出的近邻样本的个数,且有 sampling_rate < k ), sampling_rate的大小可以根据负类样本数量、正类样本数量和数据集最后需要达到的平衡率决定。但k值的上限没有办法确定,只能根据具体的数据集去反复测试。因此如何确定k值,才能使算法达到最优这是未知的。

另外,该算法无法克服非平衡数据集的数据分布问题,容易产生分布边缘化问题。由于正类样本(少数类样本)的分布决定了其可选择的近邻,如果一个正类样本处在正类样本集的分布边缘,则由此正类样本和相邻样本产生的“人造”样本也会处在这个边缘,且会越来越边缘化,从而模糊了正类样本和负类样本的边界,而且使边界变得越来越模糊。这种边界模糊性,虽然使数据集的平衡性得到了改善,但加大了分类算法进行分类的难度。

SMOTE算法摒弃了随机过采样复制样本的方法, 可以防止随机过采样易过拟合的问题,实践证明此方法可以提高分类器的性能. 但是由于对每个少数类样本都生成新样本,因此容易发生生成样本重叠overlapping的问题, 为了解决smote算法的这一缺点提出一些改进算法,其中之一是一种Borderline-SMOTE算法.

在Borderline-SMOTE中,若少数类样本的每个样本xi求k近邻,记作Si-knn, 且Si-knn属于真个样本集合S而不再是少数类样本, 若满足 $\frac{k}{2} < |S_{i-knn} \cap S_{maj}| < k$ 则将样本xi加入DANGER集合,显然DANGER集合代表了接近分类边界的样本,将DANGER当做SMOTE种子样本的输入生成新样本. 特别地,当上述条件取右边界,即k近邻中全部样本都是多数类时,此样本不会被选择为种样本生成新样本,此情况下的样本为噪音.

Borderline-SMOTE与原始SMOTE不同的地方在于,原始的SMOTE是对所有少数类样本生成新样本。而改进的方法则是先根据规则判断出少数类的边界样本,再对这些样本生成新样本。

判断边界的一个简单的规则为:K近邻中有一半以上多数类样本的少数类为边界样本。直观地讲,只为那些周围大部分是多数类样本的少数类样本生成新样本。

假设a为少数类中的一个样本,此时少数类的样本分为三类,如下图所示:

(i) 噪音样本(noise), 该少数类的所有最近邻样本都来自于不同于样本a的其他类别:

(ii) 危险样本(in danger), 至少一半的最近邻样本来自于同一类(不同于a的类别);

(iii) 安全样本(safe), 所有的最近邻样本都来自于同一个类。

Informed Undersampling

既然SMOTE可以解决随机过采样容易发生的模型过拟合问题,对应地也有一些采样方法,可以解决随机欠采样造成的数据信息丢失问题,答案是informed undersampling采样技术, informed undersampling采样技术主要有两种方法分别是easyensemble算法和balanceCascade算法.

EasyEnsemble算法如下图所示, 此算法类似于随机森林的bagging方法, 它把数据划分为两部分,分别是多数类样本和少数类样本, 对于多数类样本$S_{maj}$, 通过n次有放回抽样生成n份子集(有放回, 防止抽样数据不同,导致的问题),少数类样本分别和这n份样本合并训练一个模型,这样可以得到n个模型,最终的模型是这n个模型预测结果的平均值.

BalanceCascade算法是一种级联算法,利用增量训练的思想(Boosting). BalanceCascade从多数类$S_{maj}$中下采样生成训练集,训练一个分类器,对于那些分类正确的对偶舒蕾样本不放回, 然后对这个更小的多数类样本下采样产生数据集,训练第二个分类器,以此类推,最终组合所有分类器的结果得到最终结果.

代价敏感学习

代价矩阵

在算法层面上解决不平衡数据学习的方法主要是基于代价敏感学习算法(cost-sensitive-learning), 代价敏感学习方法的核心要素是代价矩阵,在实际应用中不同类型的误分类情况导致的代价是不一样的,例如在医疗中,”将病人误诊为健康人”和”将健康人误诊为病人”的代价不同…

代价矩阵学习方法

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

  1. 从学习模型出发,着眼于对某一具体学习方法的改造,使之能使用不平衡数据下的学习,研究者们针对不同的学习模型如感知机,支持向量机,决策树等分别提出了其代价敏感的版本. 以代价敏感的决策树为例,可从三个方面对其进行改进以适应不平衡数据的学习,这三个方面分别是:决策阈值的选择,分裂标准的选择方面,剪枝方面. 这三个方面中都可以将带将矩阵引入.
  2. 从贝叶斯理论出发,把代价敏感学习看成是分类结果的一种后处理,按照传统方法学习到一个模型,以实现损失最小的目标对结果进行调整,优化公式如下. 此方法的优点在于它可以不依赖所用具体的分类器,但是缺点也能明显它要求分类器输出值为概率.
  3. 从预处理的角度出发, 将代价用于权重的调整, 使得分类器满足代价敏感的特性. 比如,基于AdaBoost的权重更新策略.

AdaCost算法

AdaBoost权重更新方法, 正确分类样本权重降低,错误分类样本权重加大, 最终模型是多次迭代模型的一个加权线性组合,分类越准确的分类器将会获得越大的权重.

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

不平衡学习的评价方法

正确率和F值

正确值和F值都是基于混淆矩阵的.每行代表预测情况,每列代表实际类别.

正确率和F值的计算公式如下.正确率和错误率不能表示不平衡数据下模型的表现,对于不平衡数据即使全部预测为多数类也可以达到较高的正确率较低的错误率, 而F值同时考虑到了少数类的准确率和召回率,因此能衡量不平衡数据下模型的表现,其中beta通常取1.

G-mean

G-Mean是另一个指标,能评价不平衡数据的模型表现.考虑了真阳率和假阳率,

ROC曲线和AUC

真阳率和假阳率, 假阳率又表示为1-负类召回率, 真阳率又表示为正类召回率, 模型最好的时候FP_rate=0,TP_rate=1, 以假阳率为横坐标,真阳率为纵坐标,位置在左上角. ROC曲线越靠近A表示模型表现越好, 曲线下面积越大,表现也越好.

总结

https://www.cnblogs.com/kamekin/p/9824294.html

您的支持就是我更新的最大动力!谢谢!