基于样本密度峰值的不平衡数据欠抽样方法

苏俊宁，叶东毅

(福州大学 数学与计算机科学学院，福州 350108)

0 引言

在许多模式分类的应用问题中，不同类别的数据分布往往是不平衡的[1-3]，即某些类别样本的数量远远小于其他类别样本的数量，其中样本数少的类称为少数类，样本数大的类称为多数类[4]。如果不考虑不平衡性因素的影响，传统的机器学习算法对于不平衡数据的分类学习结果往往会倾向满足多数类样本的分类正确性而造成少数类样本的误分，也即容易产生分类决策边界偏移[5]，降低了分类模型(特别是对少数类样本正确分类)的泛化能力[6-7]，因此，研究如何有效处理不平衡数据的分类问题具有重要的理论和实际意义。

近年来，人们针对不平衡数据的分类问题提出了许多方法，这些方法大致分为三类[8]。

一是数据层面的方法[9-12]，即通过对不平衡数据集进行重抽样而得到平衡的数据集，应用已有的学习算法对平衡处理后的数据集进行学习和建模。常用的抽样方法包括对少数类样本的过抽样[9-10]和对多数类样本的欠抽样[11-12]，其中，SMOTE(Synthetic Minority Over-sampling TEchnique)[9]是一种经典的过抽样方法，它通过插值扩充少数类样本集使样本数目达到均衡。一般来说，过抽样容易产生过拟合，而欠抽样可能丢失与分类相关的信息[5,13]。

二是算法层面的方法，即通过在学习算法中考虑不平衡的因素来改进现有的学习算法，使之适合于处理不平衡数据的分类问题[14-16]，如代价敏感支持向量机[14]，该算法通过对不同类型的错分引入不同的惩罚代价，以保证分类器总体错分代价最小。该类方法能有效地提高少数类的识别率，但在多数情况下，真实的错分代价很难被准确估计[17]，且对于一些不能直接使用代价敏感学习的分类器，只能通过调整正负样本比例或者决策阈值间接地实现代价敏感学习[18]，不能保证代价敏感学习的效果。

第三类融合了数据层面方法和算法层面方法[19-22]，通过对不平衡数据集进行多次重抽样获得多个不同的平衡训练集，并训练相应的分类器，最后对这些分类器进行集成[23]。该类方法已成为目前处理不平衡数据分类问题的一个主要方法，得到研究者的广泛关注。例如：文献[19]中提出的结合欠抽样和bagging技术的RBBag(Roughly Balanced Bagging)算法，文献[20]中提出的基于权重抽样的uNBBag(under-sampling NeighBorhood Bagging)算法，文献[21]中提出的基于样本聚类的KAcBag(K-means Adacost Bagging)算法和文献[22]中提出的同样基于聚类和欠抽样的CbUs(Clustering-based Under-sampling)算法。

尽管上述第三类型算法有效地提升了不平衡数据的分类性能，但是它们采用的欠抽样方法在数据分布一致性保持和噪声处理方面还存在不足，因而分类准确性有待进一步提高。具体而言，RBBag算法主要是随机抽取多数类样本获得平衡数据集，并未考虑多数类样本的分布特点，导致可能丢失多数类中与分类相关的有用信息，降低分类的质量；uNBBag算法同样未考虑多数类数据的整体分布特点，也未考虑噪声的处理；KAcBag算法根据K-means聚类算法对形成的不同类簇赋予不同的权重进行欠抽样，虽然考虑了多数类数据分布的因素，但由于同一类簇的样本被赋予相同的权重，因而不能充分体现同一类簇中的样本分布信息；CbUs算法则采用一种基于聚类代表点的欠抽样策略，该策略在一定程度上考虑了多数类数据分布的因素，但由于只考虑类簇中心作为抽样代表点容易忽视边界区域样本的选择，导致与决策面相关的有用信息丢失，进而影响分类特别是多数类的正确率。

针对上述方法存在的不足，本文提出一种基于样本密度峰值的不平衡数据欠抽样方法以及基于该欠抽样方法的集成分类学习算法——DPBag(Density Peaks Bagging)，其欠抽样的思路是通过考量样本密度分布信息来尽量保持抽取样本与多数类样本数据分布的一致性。具体而言，该方法通过密度峰值聚类算法[22]完成多数类数据的聚类，并利用样本局部密度和密度峰值的分布来赋予每个样本权重，使得对于每个类簇而言，越靠近类簇中心区域的样本权重越大，越接近边界区域的样本权重越小，尽可能使抽取的样本集合能较好地反映多数类样本的分布情况。实验结果表明，与上述欠抽样方法相比，在同样采用集成学习方法对重抽样得到的训练集进行分类模型学习的情况下，本文的欠抽样方法有效提高了分类的性能，取得了良好的改进效果。

1 基于样本密度峰值的欠抽样方法

1.1 密度峰值聚类算法

为便于描述本文提出的DPBag算法，首先简要回顾一下算法抽样权重计算中将要使用到的密度峰值聚类算法——DPC(Clustering by fast search and find of Density Peaks)[24]。该算法的基本思路是通过计算样本点的局部密度并寻找密度峰值点，从而形成类簇。对于每个样本点xi，DPC算法需计算两个量：样本点xi的局部密度ρi和该点到具有更高局部密度的点的最小距离δi，其定义如下：

(1)

其中：dij为样本i，j间的欧氏距离；dc为截断距离(由用户设置的距离)。

(2)

DPC算法将具有高δ值和相对较高ρ值的点作为类簇中心，而具有高δ值和较低ρ值的点往往是离群点或噪声点。在类簇中心找到后，剩余点被归属到具有更高密度的最近邻点所属类簇。一般来说，DPC算法具有较好的区分类簇中心、边界样本和离群点(含噪声)的能力。

1.2 本文提出的DPBag算法

DPBag算法的核心在于对多数类欠抽样的样本权重计算方法。

1.2.1 样本权重的计算

样本权重计算的基本思想是使得抽样后的样本与原始样本的分布尽量保持一致。注意到，DPC聚类算法中的δ值和ρ值可以较好地反映样本点在相应类簇中所处的位置，即对于任意一个样本点xi而言：

①若xi具有较高δ值和较高ρ值时，则该点被判定为类簇中心；

②若xi具有较高δ值和较低ρ值时，则该点被判定为噪声点或小类簇点；

③若xi具有较低δ值和较高ρ值时，则该点被判定为类簇中心周边点；

④若xi具有较低δ值和较低ρ值时，则该点被判定为边界点。

由此依据样本点xi的δ值和ρ值，本文提出如下的多数类样本欠抽样权重计算方法。

首先对δ值进行归一化处理使之属于0到1之间，其次，根据ρ值和归一化后的δ值初始化多数类样本的权重，对于样本xi，令其权值为：

wi=(ρi+1)eδi

(3)

式(3)所得初始化结果使得各类簇中心具有最大的权值，其他点的权值较小。在初始化权重的基础上，根据DPC算法对多数类样本的聚类结果进行权值更新，具体规则如下。

(4)

由于wk-wi>0，则：

因此可得：

1)当样本点xi为类簇中心周边点时，因为其ρi值与类簇中心的ρk值相近，故权值更新后类簇中心周边样本的权值得到了提高。

2)当样本点xi为边界点或噪声点时，由于边界点和噪声点的ρ值较小，即ρi≪ρk，由式(4)可知样本点xi更新后的权值近似不变。

由上述分析可知，经过权重更新后，对于多数类的每一个类簇，样本权重值尽可能由类簇中心区域向边界区域呈现逐渐递减的趋势，因而以此权重抽样的样本与该类簇样本的分布较为近似，并能一定程度上抑制噪声数据。

1.2.2 基于加权Bagging的分类器集成

前述RBBag、uNBBag、KAcBag等算法使用的分类器学习均采用基于Bagging的集成学习方法。为便于算法性能比较，本文同样采用这种集成学习的方法构建分类器。Bagging方法[15]是由多个子分类器投票返回预测的类标签，可以提高基分类器的准确率。考虑到抽样的不确定性将导致每个子分类器的性能不同，因此，一般采用加权的方法赋予每个子分类器不同的权重以反映其对最终预测结果的贡献程度[17,19],其中对于子分类器hi权重αi定义如下：

(5)

其中，少数类样本权重的计算方法与多数类样本相同，由于处于少数类边界样本对分类性能影响更大[10]，因此对少数类样本权重wj-minority进行求倒数运算，即：

wj-minority′=1/wj-minority

error(hi)为子分类器hi的错分率，即hi误分训练样本子集Di的样本权重和，计算公式为：

若样本xd被误分，则err(xd)为1；否则err(xd)为0。

1.2.3 DPBag算法具体过程

考虑到对于一些小规模或高度不平衡(不平衡比率大于等于9的数据集[25])的不平衡数据集，单独采用欠抽样会使训练集样本过小而导致整体分类性能下降，因此针对这种情况，本文加入过抽样策略来处理单纯的欠抽样所带来的缺陷。

给定一个分类器学习算法WeakLearn，DPBag算法步骤如下,其具体框架如图1所示。

输入：训练集D，参数dc的百分比，迭代次数T。

输出：集成分类模型H。

步骤2 对每个多数类样本点xi，按照权重大小计算其被抽取概率，即：

步骤3 若N/M≥9，则对少数类样本进行过抽样，且过抽样率为「N/(5*M)⎤*100%；

步骤4 样本抽取以及子分类器的训练

fort=1 toT

/*可并行执行*/

1)依照赌轮原则[26]对多数类样本进行欠抽样，得到与少数类样本数量相同的多数类样本集，与所有少数类样本构成一个平衡训练集Dt；

2)应用Weaklearn对Dt进行学习，获得子分类器ht，计算子分类器权重αt(式(5))。

步骤5 生成集成模型：

其中符号函数sign定义为：

图1 DPBag算法框架Fig. 1 Framework of DPBag algorithm

由上述算法流程可以得出DPBag算法由三部分构成：权重的计算、按照权重对训练集进行重采样以及基于加权baggin的分类器集成。首先，权重的计算方法利用了DPC聚类算法中的δ值和ρ值可以较好地反映样本点在相应类簇中所处位置的特性，赋予样本点权重，使得对于多数类的每一个类簇，样本权重值尽可能由类簇中心区域向边界区域呈现逐渐递减的趋势；然后按照该权重对多数类进行欠抽样，使得抽取的样本既能平衡训练集，又尽可能地与原始样本的分布保持一致，提高少数类的分类性能；最后，利用集成学习提高不平衡数据整体分类性能的特点，考虑了抽样的不确定性给子分类器带来的影响，赋予了子分类器权重，使得集成分类器能更好地提高不平衡数据集的整体分类性能。

1.2.4 DPBag算法复杂度分析

DPBag算法复杂度主要包括两个方面，如下所示。

1)样本权重的计算，即应用DPC算法分别计算多数类和少数类样本权重，由于多数类样本数远多于少数类样本数，因此该部分复杂度量级上等于计算多数类样本权重的复杂度：

a)计算样本间的距离O(N2)；

b)计算多数类样本的密度ρ值O(N2)；

c)计算多数类样本的δ值O(N2)；

d)初始化多数类样本权重O(N)；

e)依据聚类结果对多数类样本权重更新O(N)。

因此，权重计算的总复杂度为O(N2)。

2)T轮分类器的训练。设基分类器训练为CART(Classification And Regression Tree)算法，其时间复杂度与抽样获得的平衡训练集Dt大小成线性关系，为O(|Dt|)，|Dt|=2M，故T轮分类器的训练时间为O(2TM)。

因此，DPBag算法的复杂度为O(N2)+O(2TM)。

针对在引言中叙述的其他欠抽样方法RBBag、uNBBag、KAcBag和CbUs四种算法，其时间复杂度如表1所示。

表1 4种算法的时间复杂度对比 Tab. 1 Time complexity comparison of four algorithms

通过对比可以得出本文算法与其他欠抽样算法的时间复杂度差别主要在于样本抽取的过程，虽然本文时间花费稍大，但其所抽取的样本与原始数据集的分布较为近似，并能一定程度上抑制噪声数据。

2 实验结果与分析

2.1 分类的评价方法

不平衡数据分类问题的常用标准有：查全率(Recall)、查准率(Precision)、F1-measure以及G-mean[27]。其计算方法均建立在表2混淆矩阵的基础上，其中正类和负类分别表示少数类和多数类。Recall、Precision、F1-measure、G-mean值计算方法如下：

表2 二类问题的混淆矩阵 Tab. 2 Confusion matrix for two-class problem

F1-measure是一种反映分类器对少数类样本识别率的评价指标，它是Recall和Precision的组合，仅当少数类的Recall值和Precision值都较大时，它的F1-measure值才较大。此外G-mean是一种度量单个数据集整体分类性能的评价指标，仅当分类器对多数类和少数类的分类精度都较大时，才能获得较大的G-mean值。本实验采用F1-measure和G-mean来衡量算法的分类性能。

由于F1-measure和G-mean是从单个数据集上衡量不同分类算法性能的指标，因此为了从整体上比较各种分类算法优劣，本文引入Friedman检验[28]和Wilcoxon符号秩检验[28]来衡量各重抽样方法整体性能上的差异。其中，Friedman检验是利用秩判断不同算法是否存在显著性差异的非参数检验方法；而Wilcoxon符号秩检验是通过分析两配对样本，推断样本来自的两个算法是否存在显著性差异。

2.2 实验设置

本文选择12个少数类和多数类样本不平衡且具有不同实际应用背景的UCI数据集[29]进行实验。各数据集的基本信息如表3所示，其中，对于有多个类别属性的数据，将数量最少的若干类别作为少数类，将其他类合并为一个多数类；最后一列表示数据集不平衡比率(Imbalanced Ratio, IR)，即多数类样本数与少数类样本数的比值。

表3 UCI数据集的基本信息 Tab. 3 Information of UCI datasets

本实验将DPBag算法与OvBag(Over-Bagging)[30]、SmBag(SMOTE-Bagging)[30]、oNBBag(over-sampling Neighborhood Bagging)[20]三种过抽样算法以及RBBag[19]、uNBBag[20]、KAcBag[21]和CbUs[22]四种欠抽样算法在F1-measure和G-mean两个指标上的结果进行对比分析，如表4所示。

实验中，对DPBag算法设置如下：按照DPC算法的推荐做法，将数据集中两两样本之间的距离按照由小到大的方式排序，处于第2%位置的值作为截断距离dc的值；针对不平衡比率大于9的数据集，使用随机过抽样方法，过抽样率设为「IR/5⎤。对CbUs算法设置如下：选择其中实验效果更好的策略2，即用K-means聚类算法对多数类样本进行聚类，将聚类中心的最近邻真实样本作为多数类代表点与所有少数类样本组成平衡数据集用于分类器的训练；聚类个数K设为少数类样本数。将weka软件[31]的J48决策树算法(C4.5)作为基分类器，算法参数使用weka中的默认参数设置。

2.3 结果分析

为了使实验更具客观性，采用十折交叉验证的方法对分类效果进行验证，将均值作为最终结果。表4为8种算法在12个UCI数据集上的F1-measure值和G-mean值，表中的每行表示数据集在对应算法上的实验结果，每一行中的最高值以加粗下划线表示，第二高值以加粗表示；表格最后一行为每种算法在所有数据集上的平均秩，其值越小说明算法性能越好。表5为不同算法两两比较的Wilcoxon符号秩检验结果。为了更直观体现算法对比的结果，图2给出8种算法在12个数据集上F1-measure值和G-mean值的平均值的图形表示。

由表4可知，对于F1-measure和G-mean两个评价指标而言，本文的DPBag算法在12个数据集上的平均秩分别为1.92和2.17，排名均为第1，说明它在8种算法中的平均性能最优。此外，相对G-mean指标而言，DPBag算法在F1-measure指标上的优势更为明显，由图2可以看出，它在12个数据集上的平均F1-measure值明显高于其他7种算法的对应值，而且比它们中取得最高值的KAcBag算法高出2.36%。对于abalone和yeast数据集，可以看出过抽样算法OvBag、SmBag和oNBBag得到的F1-measure值明显优于欠抽样算法uNBBag、RBBag、KAcBag和CbUS。这是因为这些数据集中少数类样本过少且数据集的不平衡程度较高，使得欠抽样算法得到的平衡数据集丢失过多的多数类样本，造成分类性能降低，但本文增加的过抽样策略能较为有效地处理该问题，如对yeast数据集，DPBag算法与欠抽样算法相比，与F1-measure值的最高值之差为+15.89%，与G-mean值的最高值之差为-6.16%；同时DPBag算法与过抽样算法相比，其F1-measure值为最高，并且G-mean值也高于过抽样算法中的最高值+6.06%。

从Friedman统计检验的角度看，F1-measure上的Friedman检验结果为0.009(p<0.05)，G-mean上的Friedman检验结果小于0.001(p<0.05)，说明8种算法F1-measure和G-mean指标在整体上均有显著性差异。

由表5的Wilcoxon符号秩检验结果以及图2所展示的8种方法在12个数据集上的平均F1-measure值可以得出DPBag算法在F1-measure指标上显著优于其他7种算法；在G-mean指标上，DPBag算法与KAcBag算法无显著性差异，但均优于其他6种算法。

表4 DPBag算法与其他抽样算法的F1-measure值、G-mean值对比 单位：% Tab. 4 F1-measure and G-mean comparison of DPBag and other sampling algorithms unit:%

表5 DPBag算法与其他抽样算法两两比较的Wilcoxon符号秩检验 Tab. 5 Wilcoxon sign rank test for DPBag and other sampling algorithms

图2 12个数据集上F1-measure值和G-mean值的平均值Fig. 2 Average F1-measure and G-mean on 12 datasets

综合以上分析，在12个不平衡的数据集上，DPBag算法取得了良好的改进效果，说明本文提出的DPBag算法通过尽量保持欠抽样样本与原始样本分布的一致性对于提高不平衡数据的分类精度是一个合理、有效的途径；并且针对欠抽样算法在少数类样本过少且不平衡程度较高的不平衡数据集下F1-measure值较低的问题，DPBag算法增加的过抽样策略有效地处理了该情况，在对整体分类性能影响较小的情况下，提升了分类器对少数类的识别率。

为了观察参数dc值对DPBag算法的影响，图3和图4分别给出DPBag算法在取不同dc值[1%，2%，3%，4%，5%]的情况下F1-measure值和G-mean值的变化。

由图3和图4可得，从整体上看dc值的选取对DPBag算法的影响较小，当dc值取2%、3%时，两个评价指标均可以取得较好的结果。

由于Yeast是典型的不平衡数据集，其不平衡比率较大且样本数较多，因此本文主要针对该数据集观察不同的过抽样率[100%,1 000%]对DPBag算法的影响。图5给出dc=2%时不同过抽样率对DPBag算法的F1-measure值和G-mean值的影响。

由图5可得，当过抽样率达到500%以上(接近「IR/5⎤，即「28.1/5⎤)时，F1-measure值逐渐达到峰值，而G-mean值呈下降趋势，这是由于当过抽样率过大时，分类器对训练集产生了过拟合现象，因此，选择合适的过抽样率，少数类的F1-measure值和整体性能的G-mean值均能取得较好的结果。

图3 不同dc值对F1-measure值的影响Fig. 3 Effect of different dc values on F1-measure

图4 不同dc值对G-mean值的影响Fig. 4 Effect of different dc values on G-mean

图5 不同过抽样率的实验结果(dc=2%)Fig. 5 Experimental results of different oversampling rates(dc=2%)

3 结语

本文研究了不平衡数据分类问题中的数据重抽样方法。针对现有欠抽样方法在样本分布一致性保持和噪声数据处理方面存在的不足，提出一种基于样本密度峰值的不平衡数据欠抽样方法。该方法应用密度峰值聚类算法中的样本密度峰值和局部密度来初始化多数类样本权重，通过计算样本与类簇中心密度差异来更新多数类权重信息，按照权重大小对多数类样本进行欠抽样，使得所抽取的多数类样本尽可能由类簇中心区域向边界区域逐步递减，既能较好地反映原始数据集的分布又可有效抑制噪声数据，减小决策面的偏倚程度。在UCI数据集上的实验结果表明，与近期的重抽样方法相比，在同样采用集成学习方法对重抽样得到的训练集进行分类模型学习的情况下，本文方法取得了较为明显的改进效果，达到了相对最佳的总体泛化性能。这表明尽量保持欠抽样样本与原始样本分布的一致性对于提高不平衡数据的最终集成分类精度是一个合理可行的途径。当然，本文方法还存在一些需要改进的地方，在权重计算方面，噪声数据和边界样本的权重都较小，不易被区分，因此如何进一步地区分边界样本和噪声数据将成为下一阶段的研究重点。