不均衡数据的分类问题是一个巨大的挑战,因为我们没有足够的数据来实现generalization。如何充分地利用手头的数据,尽可能把不同类别的数据分开呢?

下面我们来将这个问题简化(事实上也是极端化):

给定一个数据集,其中有10个正样本,1个负样本,怎么找一个决策边界,使得两类最好地分开?

假设样本的维度是2,负样本为$(a_1,b_1)$,正样本为$(a_2, b_2),(a_3,b_3),...(a_{11}, b_{11})$。比如像这样:

又或者是这样:

只有一个负样本,这个问题真是棘手。我想,我们可以从如下几个常规思路上来处理这个问题:

让样本的分布均匀起来

很多处理不均衡数据的方法,是通过resampling的方式,把数据处理地均衡了,再跑常规的分类算法。

undersampling

其中一种方式undersampling,换到上面的例子,就是将正样本进行采样,把数据量减少到和负样本一样多。但是这里貌似不是很可取,最后剩下正负样本个一个还分个什么类?

oversampling

另外一种方式就是过采样,也就是复制少数类的样本,使之与多数类的样本一样多。但其实这样存在一个问题,那就是实际的知识并没有增加。可能效果也不会特别明显。

合成新的数据

oversampling一个改进的方式是,不要纯粹地复制那个负样本,而是把那个负样本增加一些变化。

如果将负样本增加一些噪声(得到新的一些样本),我们可以有比较大的把握认为这些新的样本仍然属于负样本。这样,正负样本的不均衡问题也可以一定程度上的解决。至于噪声的选择,就选择自然界中最普遍的高斯白噪声,这样也符合科学规律。

另外一种合成新数据的思路是从概率角度出发,我们可以使用常规的概率密度估计的方法,从样本出发,得到数据的概率模型,然后通过概率模型生成新的数据(有一些generative model的意思)。当然,这里负样本实在太少了,进行概率估计应该是一件不靠谱的事情。

从cost function出发

因为正样本的数量众多,通常的分类器的决策都会偏向多数类,这样就无法满足“将两类尽量分开”的要求。如果要想把负样本找出来的话,就要强调它们的地位。

现在如果先不考虑将低维向高维的映射,只看线性分类器:最简单的线性分类器就是perceptron,考虑的是0-1 loss,也就是统计分类错误的个数,正负样本分错的loss是一样的。为了强调负样本,我们可以增大负样本损失权重,也就是:

其中C就是我们给负样本分错提升的权重,可以调整这个参数寻找一个很好的决策平面(注:perceptron只有在线性可分的情形下work,对于不可分的情形则要上高维映射或者贪婪的pocket算法)。

既然perceptron可以这样调整,那么其它分类器也可以如法炮制。比如SVM,一般SVM(带松弛变量)的问题可以写成:

要强调负样本的作用,就可以调整正负样本的正则化的参数$C$,也就是写成:

我们自己调节$C^+$与$C^-$的大小,达到强调负样本的效果(负样本的正则化参数小一些)。

下面就是调整这个权重的结果:

权重比例调整前:

权重比例调整后:

进一步讲,因为SVM得到的最有决策平面仅仅与一部分的数据又关(support vectors),我们甚至可以针对每一个样本点单独设置一个正则化的参数。当然,这样做的话,变量就变得更多,进行最优化的时候难度也相应地增大。

不仅如此,决策树(比如cart)也可以自己定义cost matrix,其方法也就是修改cost function。印象中R里面的rpart可以以参数形式传入:

ClaimsTree = rpart(y~x, data=train, method="class", cp=someSmallNumber, parms=list(loss=PenaltyMatrix))

负样本太少,是不是一个异常点?

现在,既然负样本只有一个,它会不会是一个异常点呢?

正常情况下,数据点都是正样本,但是在一些“异常”的情况下,也会出现负样本。异常点的检测,在我的印象中还是聚类算法应用的比较多一些。通过将相似的正样本数据点聚在一起,而那些不相似的点则为负样本了。至于聚类算法就有很多了,可以根据需要进行选择。

但是这里的问题是要求找到正负样本的决策平面(直线/曲线),一个比较直观的方法是利用GMM估计分布的概率密度,然后通过计算后验概率的大小得到决策边界。

此外,前些年南京大学周志华团队开发的isolation forest也是一个很好的异常点检测的算法。单类的SVM也是一个异常点检测的办法。

目前已有的机器学习算法自带不均衡处理的解决方案

实际上,现在一些比较成熟的机器学习算法也或多或少存在对不均衡数据的处理。正如前面提到的SVM,就可以采用调整正负样本的正则化的权重缓解不均衡的问题。

此外,集成的分类器也天然有处理不均衡数据的能力。像random forest,处理不均衡数据比较稳健,当然与之bootstrap的抽样过程也是离不开的。此外像AdaBoost,通过改变抽样的权重,也能一定程度上解决这个问题。至于GBDT则是通过残差的学习,最终也能较好的解决不均衡这一问题。

当然,目前成熟的机器学习包可能将前面提到的方法进行了融合。比如最近最流行的xgboost(真是大杀器,比其他分类器的效果都好),就集成了正负比例不同比例抽样的方法,再加上boosting的天然优势。

再开一个脑洞

既然数据点这么少,我们是不是可以联系到推荐系统中的预测用户电影评分的问题?因为往往评分数据是很稀疏的,跟这里的问题有点像。

那么,我们不妨将训练的这11个样本在空间上进行划分,得到一个单元格总数为为$n \times m$的矩形,每一个小单元格都存在一个或者零个样本。这样我们就得到一个$n \times m$的矩阵,其中有正样本的那个位置我们将值置为1,负样本的则置为-1,其余位置则为空缺值。现在的问题就是要预测这些空缺值。这时候就是常规思路了:利用矩阵分解,来拟合这样一个矩阵。当矩阵拟合完毕之后,我们就可以通过矩阵位置处值的正负号来判定正负样本了,这样可能也能得到一个很不规则的决策平面。至于矩形之外的区域,我们可以利用KNN这样的工具。

当然了。这个脑洞开得有点大,实际效果可能不会很好~~

提防overfitting!

回顾一下,overfitting发生的原因:

  • 模型的复杂度越高,越容易overfitting
  • 数据的噪声越大,越容易overfitting
  • 数据量越少,越容易overfitting

这里我们讨论的10个正样本和一个负样本,真的很难达到一个很好的泛化的效果。在这里,我们连cross validation都不好做!因此,无论我们怎样花式调参,或者怎样修改模型,都难以弥补数据量少的缺憾(当然,前面使用人工合成的数据可能可以一定程度上解决这一问题)。

小结一下

前面废话那么多,这里简单地小结一下(可能)有效的解决10个正样本一个负样本的分类的问题的方法:

  1. 得到更多的数据,使得正负样本均衡(oversampling,人工合成新数据)
  2. 增大少数类分错的损失权重
  3. 当成异常点检测来做

但是,无论采用什么方法,都要小心overfitting的风险。毕竟,数据量还是太少了~~