一种改进型的不平衡数据欠采样算法

魏 力,张育平

(南京航空航天大学 计算机科学与技术学院,南京 211100)

1 引 言

在机器学习中,不平衡数据集是指不同类别的样本分布不均衡,即会出现某一类别的样本远远多于另一类别的样本[1].这在各个研究领域也是很常见的,比如信用欺诈检验[2],信用不合格的客户往往是占少数的；又如医院疾病检测,生病的人较正常人也是少数的.然而,如果直接使用这种数据集进行分类研究,会因为类别不平衡问题对算法的学习过程造成干扰,使得分类结果不尽如人意[3].

Wessi[4]的研究表明,不平衡数据集分类困难的主要原因有如下几点：1.传统的分类器性能评价标准失效.在很多情况下,我们会将精度(Accuracy)作为评价分类器好坏的依据,但有些时候精度并不能很好的反映模型的好坏.例如,100个人中有10个人生病,分类器即使将所有个例都预测为正常人也能获得90%的精度.但这不是我们想要的预测模型,能将患者预测出来才是研究的目标.因此,在不平衡数据集中,以精度为评价标准的分类学习会使分类器更偏向于预测为多数类.2.少数类样本过于少.从Wessi的文献[5]可以知道,在一些应用下,多类样本与少类样本比例过高时就会使分类变得困难.说明分类器的性能与样本类别比例有关.3.数据碎片问题.不少分类算法采用了分治思想,即将原来的大规模数据空间划分成若干个小规模子空间,而这些子空间会包含更少的少数类样本,导致少数类信息的匮乏,那么预测模型也较难建立.4.归纳偏置问题.在预测任务中,未知样本可以是任意的,而如果没有额外假设来约束的话,任务完成不了.这些假设约束条件就称为归纳偏置.为了获得更好的性能并能避免过度拟合,很多学习算法不利于少数类样本的预测,即这类算法会更偏向于将样本预测为多数类.

2 相关技术

对于处理不平衡数据集给学习任务造成的困扰,目前研究主要从两方面着手：从算法设计层面改进算法；从数据层面改变样本分布.

为了解决上文提到的不平衡数据集对传统分类算法性能的影响,从算法设计着手是一种思路,主要包括：

代价敏感学习.代价敏感学习主要考虑在分类任务中,不同类别错分时如何通过此时的“错误代价”来调整分类器.比如在疾病诊断一例中,将正常人误分为病人和将病人误分为正常人的“代价”是不同的.很明显,将病人误分为正常人很可能会让患者错过最佳治疗时机而导致比较严重的后果.那么在代价敏感学习中,会先设计一个C×C的Cost代价矩阵,用以表明将某一类别错分时的代价.所以代价敏感学习任务追求的不是总体的错误率最低,而是完成分类后的总“代价”最小.

单分类方法.与二分类或多分类任务不同,单分类方法是去确定唯一类别的边界条件.这样做的结果就是,该方法只能识别一个类别,而不包含在边界内的都属于“其它”.刘敬[19]等人对基于单分类支持向量机和主动学习的异常检测进行了研究,利用原始数据采用无监督方式建立单分类支持向量机模型,然后结合主动学习找出能够提高异常检测性能的样本并标记,所提方法能够利用少量标记数据获取性能提升.常用的单分类SVM在处理不平衡数据问题是有较好的效果,文献[6]也证明,因为只要训练某一类别的数据,这无论是在时间开销还是空间开销上都节省了很多.

重划分.重划分就是将多数类通过聚类算法划分为若干个与少数类均衡的子类,以此来达到类别平衡.邬长安[18]等人提出了基于 k-mean的数据预处理的逻辑回归学习方法ILKL提高逻辑回归在不平衡类中的分类性能.不同于传统的逻辑回归方法,该方法采用k-means聚类进行了数据预处理,将多数类实例划分为一个个子簇,然后用ILKL学习到的模型在重平衡的数据集上进行分类.

其它诸如改进集成学习算法Adaboost的Ada-Cost[8],基于核函数的学习方法[9],主动学习[10],遗传算法[11]等等.

从根本上说,导致不平衡数据集学习问题的原因还是不同类别的样本分布不均.那么,减少多类样本数目,增加少类样本数目,也就是从数据层面入手自然成为另一种思路.通过增加少数类样本来降低不平衡度的方法叫做过采样(over-sampling),减少多数类样本的方法叫做欠采样(under-s-ampling).迄今为止,不少学者在这两个方法上已有建树.

过采样方面,最基础的方法就是复制已经存在的少数类样本个例,这样做的好处是简单,但是复制操作在没有给出额外信息的情况下,不仅会增加训练器学习的时间,更会导致过拟合问题.Chawa-la[12]等人提出的SMOTE算法简单高效地模拟产生相似的少数类样本数据.算法为每一个少数类样本根据K-Nearest算法选择与其近邻的其它样本,然后在与这些样本的连线上随机产生人造样本.尽管在一些实验中,SMOTE算法有较优异的表现,但它存在着两个很明显的问题,由于该算法在每个少数类样本上都产生若干个近邻相似样本,所以在扩展少数类样本方面只能是成倍的,另外也不可避免的会产生过于重叠的样本.针对这些问题,后人提出了一些改进算法.比如Han[13]等人提出的Bordline-SMOTE算法,该算法首先在整个样本空间中为每个少数类样本生成K-Nearest近邻样本集Si,如果Si中属于多数类的大于属于少数类的,则将这个Si放入Danger集中,之后只在Danger集中根据SMOTE算法产生新样本.Bordline-SMOTE算法只为那些处于边界的少数类样本产生新样本会有更好的效果.王超学等人[16]提出了一种改进的SMOTE算法GA-SM-OTE.该算法在传统的SMOTE算法中引入遗传算法的三个基本算子,利用选择算子实现对少数类样本有区别的选择,使用交叉、变异算子实现对合成样本质量的控制.最后结合SVM算法来处理不平衡数据的分类问题.

欠采样方面,很容易想到随机去掉若干个多数类样本,但这样做会去除掉富有信息量的样本,不利于后面的学习过程.针对这一缺陷,熊冰研等人[15]提出了一种基于样本权重的欠抽样方法KAcBag(K-means AdaCost bagging),该方法通过样本权重来刻画多数类样本所处的区域,在多次聚类后确定各样本的权重,然后根据权重从多数类中抽取样本以平衡数据集.最后结合集成学习思想,通过投票集成提升分类效果.杨杰明等人[17]提出一种基于数据密度分布的欠采样方法US-DD.该算法通过某个数据样本点在一定半径内包含的样本个数来定义数据密度概念,并以此来区分高密度数据和低密度数据,再通过阈值参数来提出低密度数据样本.Mani[14]等人根据数据分布特征,给出了4种基于KNN(K Nearest Neighbour)欠采样方案.分别是NearMiss-1,NearMiss-2,NearMiss-3和Most Distant.其中NearMiss-1选择到最近的三个少数类样本平均距离最小的那些多数类样本,属于局部最近.NearMiss-2选择到最远的三个少数类样本平均距离最小的那些多数类样本,属于全局最近.而NearMiss-3让每个少数类样本都选择给定数量的最近多数类样本,使得每一个少数类样本附近都有足够多的多数类样本,这会使得模型的精确度高、召回率低.Most Distant选择那些与最近的三个少数类样本平均距离最远的多数类样本,这可以用作比较.实验结果表明,NearMiss-2拥有较好的不平衡数据学习能力.然而,在论文中Mani也提到即使是NearMiss-2与随机欠抽样相比提升也比较有限.

本文利用聚类簇中心的信息概括能力结合Ne-arMiss-2在欠抽样过程中的优先权重,提出了一种基于K-Means聚类的欠抽样方法——CCNM.

3 算法设计

K-Means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大.由K-Means算法聚类得出的簇中心点可以认为是各个簇内样本点的信息概括.以簇中心点作为代表,根据Near-Miss距离去赋予各个簇选择权重,让权重最高的簇按照距离中心点近优先原则选择K个样本,权重次之的选择样本数目递减.

CCNM算法的步骤如下：

记多数类样本集为S,样本数目为M,少数类样本集为T,样本数目为N.

1)按照公式(1),根据少数类样本数目N确定K值；

K=⎣(2N+0.25)1/2-0.5」

(1)

2)对少数类样本进行确定后K值的聚类,得出K个簇及其中心点；

3)按照NearMiss距离(NearMiss-1,NearMi-ss-2,NearMiss-3)对K个簇中心点进行排序,并赋予权重,权重最高的簇即选择K个,接下来的选择K-1个；

4)在各个簇内依照权重选择那些离簇中心点最近的样本,如果当前簇的样本点少于应该选择点的数目,则将不够的选择数目交予权重次之的簇；

5)整理各簇选择的样本,构建欠采样后的多数类样本S′.

图1 不同类型的NearMiss算法示例Fig.1 Examples of different types of NearMiss algorithm

聚类采样可以保证在以距离为相似性的评价标准下,比较多的保留样本信息.从步骤3)可以看到,在不同簇内的采样个数是根据当前簇的权重递减的,呈等差数列态,那么为了平衡样本数的差异,公式(1)就通过确立K值,并约定最高权重簇的采样个数为K,来完成最终采样数约等于少数类样本个数的目的.应用NearMiss距离也可以在纵观整个数据空间下,选出那些易于分类的数据.图1给出三种NearMiss的典型示例.

4 实验结果

4.1 评价标准

传统的学习任务采用精度作为分类器性能好坏的评价标准,但由于不平衡数据集的特殊性,分类器更偏向将结果预测为多数类从而获得较高的精确度.但是在一些情况下,不能识别少数类的分类并不是我们想要的,所以将精度作为不平衡数据集中分类器的评价标准是不合适的.为此,一些学者提出了更完善的解决方案,如F-Measure[9],G-Mean[10].这些指标都基于分类评价中常用的混淆矩阵(confusion matrix),根据分类器预测结果与实际情况划别4类组合,真正例(true positive),假正例(false positive),真反例(true negative),假反例(false negative).混淆矩阵如表1所示.

表1 混淆矩阵Table 1 Confusion matrix

在此基础上,查准率precision如公式(2)所示,查全率recall定义如公式(3)所示.

(2)

(3)

F-Measure是不平衡数据分类评价中最为常见的标准,其定义如下：

(4)

基于调和平均定义的F度量标准的一般形式取β为1,本文也按此进行试验.综合考虑查全率和查准率的F-Measure只有当precision和recall都较高时才会有比较出色的表现,更适合不平衡数据分类评价.

当考虑有多少正例被成功预测出来(Positive-Accuracy),多少负例被成功预测出来(NegativeA-ccuracy)时,就有了G-Mean的定义：

(5)

(6)

(7)

G-Mean的定义同时考虑正、负类的预测结果,在那些偏向预测为多数类的情况下,G-Mean不会有好的分数,能够完成不平衡数据分类评价的任务.

表2 数据集Table 2 Data set

4.2 数据集

本文从UCI上选取10个数据集,如表2所示.以少数类与样本总数的比例作为数据集的稀有度,先将前6个数据集用作在本文中三类NearMiss距离效果的比较,确定最佳的一种NearMiss距离,后续补充4个数据集与其它方法比较.

4.3 实验结果与分析

实验先要将多数类样本和少数类样本按照一定比例归入训练集和测试集,为了让实验结果更加客观,在采用不同欠采样策略时,都使用“10折交叉验证”.即将数据集划分为10个互斥子集,然后将9个子集的并集作为训练集,剩下的作为测试集,从而可以进行10次训练和预测.欠采样后的训练集分别调用朴素贝叶斯(NaiveBayes)和支持向量机算法(SVM)完成对测试集的预测.预测结果对比实际情况,得出F-Measure和G-Mean的值,评估模型好坏.

首先比较在6个训练集上应用三类不同Near-Miss距离后CCNM的表现,分别称之为CCNM-1、CCNM-2和CCNM-3.

表3 应用不同NearMiss距离CCNM在SVM上的F-Measure(G-Mean)Table 3 SVM′s F-Measure(G-Mean)applied with different NearMiss distance CCNM

从表3可以看出,应用NearMiss-2后的CCNM有着更为出色的表现,从选择策略上也可以发现,NearMiss-2会从全局角度考虑多数类与少数类的距离,通过这种方式选出的多数类会均匀的分布在少数类的周围,从而更容易找出分类界限.NearMiss-1从局部着手,只考虑最近的那么三个,选出的多数类不会均匀分布在少数类周围.会出现某些少数类周围有大量多数类,而某些周围几乎没有.那么,大量多数类环绕着少数类就会导致很低的查全率(recall),相反则会导致很低的查准率(pre-cision).NearMiss-3虽然会“刻意”使少数类周围有一定量的多数类,但局部仍然会出现某一类样本密集,导致少数类预测(PositiveAccuracy)、多数类预测(NegativeAccuracy)都不够理想.

表4 各欠采样方法在SVM上的F-Measure(G-Mean)表现Table 4 Different under-sampling methods′F-Measure(G-Mean)using SVM

表5 各欠采样方法在NaiveBayes上的F-Measure(G-Mean)表现Table 5 Different under-sampling methods′F-Measure(G-Mean)using NaiveBayes

表4和表5可以看到应用NearMiss-2后的CCNM算法与其它算法在10个数据集上F-Measure和G-Mean的表现.随机欠采样是最简单的方法,但如上表展示一样,由于随机性会去除大量的有用信息,R-andom算法无论在F-Measure还是G-Mean上都有着较低的分数.但值得注意的是,随机欠采样在le-tter、wine和balance数据集上有着尚可的表现,原因是这两个数据集是多类别的,将稀有类别作为少数类而其他类别作为多数类时,随机欠采样后的多数类样本在各个类别的分布可能是比较均匀的,利于后面的分类学习.CCNM算法首先利用聚类将多数类样本进行归类,再利用NearMiss-2对各个簇周围少数类样本个数进行分析,这样选出的多数类样本不仅具有更丰富的信息,在样本空间分布上也能围绕着少数类.因此,CCNM在不平衡数据分类任务中有更好的性能,尤其在不平衡度较高的yeast和glass数据集上提升明显,聚类在此处起到了很明显的去噪声的作用,同时保留了信息量高的多数类.

5 总 结

在各行业应用领域中,不平衡数据问题是较为常见的,数据类别分布不均会直接影响学习过程,给最后的预测造成困扰.本文提出一种结合KMea-ns聚类和NearMiss距离的欠采样算法CCNM,在应用UCI数据集后,验证了该算法在处理不平衡数据集问题的有效性,提高了学习器的分类性能.CCNM欠采样后的多数类样本数目约等于少数类样本数目,如何使得采样后的数目更加接近或者等于少数类样本,以及结合聚类和NearMiss距离的过采样方法是今后工作的下一个目标.