概率密度函数的自适应过采样算法研究

张忠林，傅添翼，闫光辉

(兰州交通大学 电子与信息工程学院，兰州 730070)

1 引 言

在现实世界中的众多数据通常是不均衡的，其表现为类与类之间样本数量较大的差异，当常规分类器对这些不均衡的数据集进行分类时，会导致分类器偏向多数类的样本，从而产生误分类的情况，而这些情况也会使我们付出较大的代价.在进行分类的过程中，比较经典的分类算法有支持向量机[1]、朴素贝叶斯[2]、最近邻分类算法[3]等等.但是在现实世界中存在着大量的不均衡数据，对于不均衡数据的分类问题，在我们身边的诸多领域有着重要的应用，例如信用卡欺诈[4]、异常检测[5]、医疗健康预测[6]等等.在运用传统的分类方法处理不均衡数据时，少数类具有比较大的错分代价，同时我们也更加关注少数类的分类准确率，这是因为少数类样本通常具有较高的价值，是数据分析与挖掘中的重要目标.因此，很多研究学者将自己的研究方向放在了对于不均衡数据集的分类研究.

近年来，国内外的学者在不均衡数据分类问题的研究中已经取得了大量的成果，这些成果大致在数据层面和算法层面两方面.在数据层面，主要采用的是抽样方法来平衡各类别的样本数，包括过采样[7]、欠采样[8]、混合采样[9]、SMOTE[10](Synthetic Minority Oversampling technique)以及改进算法Borderline-SMOTE[11]等等.在算法层面，主要是对传统的分类器进行改进，使得分类器能够适应不均衡数据集，其目的就是要减少分类器对于多数类的偏重，在这里代价敏感与集成算法取得了较好的结果.代价敏感实质上是为实际属于少数类但是被错分为多数类的实例赋予更大的错分代价，避免生成过多的错误.集成学习则能够显著的提高单个分类器的性能，使用最为广泛的就是Yoav[12]提出的Boosting算法，其被运用在了诸多算法当中，例如SMOTEBoost[13]、RUSBoost[14]、EasyEnsemble[15]、EUSboost[16]等等.

学者们对于不均衡数据的分类问题进行了大量的研究，也取得了丰硕的成果.但是仍然存在一些不足，传统的欠采样方法可能会删除一些多数类样本中的重要样本点，丢失一部分的重要信息；随机过采样只是简单的复制了少数类样本，增大了产生过拟合的几率；SMOTE算法虽然通过对少数类进行分析，k个样本之间线性插值合成了新的样本，使得对少数类的预测精度有所提升，但是在合成新样本时没有考虑到样本的分布，比较容易合成噪声样本以及冗余样本.本文针对以上在不均衡数据分类中存在的问题，设计了一种基于ADASYN的改进方法.

2 算 法

自适应过采样算法通过自身优点解决了SMOTE会因样本自身分布而产生噪声样本.本文中通过对自适应过采样的改进算法对数据集进行数据均衡化操作.最后采用随机森林对数据进行分类，同时采用网格搜索进行参数寻优.

2.1 ADASYN算法

自适应过采样算法[17](Adaptive Synthetic sampling approach，ADASYN)是一种自适应的数据合成方法，该方法可以根据少数类样本的分布自适应的合成新样本.ADASYN算法中的每个少数类样本根据其学习的复杂程度来确定需要合成的新样本的个数，即在越难分类的地方生成更多的样本.

ADASYN算法合成新样本点步骤如下：

输入：数据集Xtrain={(xi，yi)|x∈X，y∈Y}； X={x1，x2，…，xn}，Y={1，-1}；

输出：新的样本集Xnew；

1. Mmin←Count_min(Xtrain)；#样本中少数类数目#

2. Mmaj←Count_maj(Xtrain)；#样本中多数类数目#

3. Xmin←Search_min(Xtrain)；

4. d←div(Mmaj，Mmin)；#数据集不均衡因子#

5. G←Mmin_Count(Mmaj，Mmin，β)；

#计算少数类样本数量β∈[0，1]#

6. R←∅；#少数类比例集合#

7. for each_object in Xmin

8. k←KNN_min(each_object)；

10. R←add(r)；

11. end for

12. H←∅；

13. for r in R

14. ri←Mmaj_count(R)；

#计算每个少数类样本周围多数类的情况#

15. gi←mult(ri，G)；

#计算出各个少数类样本xi需要合成的样本数目#

由表1计算可以得到单桩承载力极限平均值为10 635 kN，极差与平均值的比为6.4%(<30%)，故单桩承载力极限为10 635 kN，远超过设计单桩承载力极限值8 000 kN。

16. end for

17. for i=1 to len(H) do

18. sj←Gen(Xi，Xzi，λ)；

#合成新的少数类样本#

19. Xnew←add(sj)；

20. end for

21. return Xnew

2.2 瑞利分布

(1)

图1 σ=2时瑞利分布的概率密度函数图Fig.1 Graph of the probability density function of the Rayleigh distribution at sigma=2

如图1所示，是瑞利分布在σ=2时的概率密度函数图，图中在x=2时取得极值点，在极值点的左边，f(x)随着x的增大而迅速的增大，相反，在极值点的右边，f(x)随着x的增大而逐渐缓慢减小.

根据上文中给出的式(1)，我们可以控制图1中的极值点的位置.因而在式(1)中由f(x)对x求导可得：

(2)

2.3 ADASYN算法改进

虽然ADASYN算法相比于其他几种传统算法对分类器的性能有一定程度的提升，考虑到了样本分布，但是其本身仍然有一定程度上的不足，受到噪声点的较大影响，会在具有大量多数类实例的邻域中生成更多的新样本.蒋华[19]等人将K近邻均为多数类的少数类样本直接删除，这种欠采样操作虽然一定程度上降低了噪声样本点的影响，但同时也可能丢失重要信息.Han等人在Borderline-SMOTE算法中提出：在距离决策边界较近的样本中进行采样操作，这样可以提高分类器的性能.ADASYN算法虽然考虑到了样本点的分布造成的影响，同时也受到了离群噪声点的影响.ADASYN算法中以少数类样本点的K个近邻中包含多数类样本点个数作为标准，当少数类样本点的K个近邻中的多数类样本点越多，表明对于该样本点的学习就会越困难，就需要在该样本点周围更多的合成新的样本点.同时，当一个少数类样本点的K个近邻中多数是多数类样本点，该少数类样本点是噪声的可能性也会随之增大，此时分类器的性能就会随着噪声样本点的增多而下降.

对于以上问题，本文引入了瑞利分布来对ADASYN算法来加以改进.对于其中新样本的密度分布，使用瑞利分布的概率密度函数来进行构造.在本算法中对少数类样本进行划分，以少数类样本的K近邻中包含多数类的样本个数Δ为依据，将Δ作为阈值标准，把少数类划分为3类：安全样本，边界样本，危险样本.通过瑞利分布的概率密度函数我们可以更好的对安全样本和边界样本进行采样.当Δ小于我们阈值时，该样本属于安全样本；当Δ等于阈值时，该样本属于边界样本；当Δ大于阈值时，该样本属于危险样本.在划分出的3类中，当由边界样本合成的新样本越多，密度越大，此时就有利于增强决策边界.对于上文中提到的瑞利分布，在极值点左右两侧的斜率不同，设置图1中的极值为Δ等于阈值时合成的新样本的密度，这样就可以使得新样本集中的合成在边界样本附近，增强决策边界.

对于Δ的值，考虑到样本的K近邻中存在的多数类样本数，设置Δ=k/2，判断此时的样本点属于边界样本，同时又要瑞利分布的极值点处的新样本密度最大，此时我们令σ=x=Δ=k/2.

1)数据预处理阶段ADASYN改进

在之前的ADASYN算法中少数类样本的比率ri是通过公式ri=Δ/k计算得到，本文中应用瑞利分布的概率密度函数来计算比率ri.即对于每个少数类样本xi，在其K个近邻中多数类样本的个数记为Δi，则ri的计算公式如公式(3)所示.算法的具体步骤如算法1所示.

(3)

算法1.ADASYN(X)：

输入：数据集X={x1，x2，…，xn}，X={xi|xi∈Rd}，(i=0，1，2，…，n)

输出：样本值X_res，样本值y_res

1.neighbors←5；

2.jobs←∅；

3.random_state←∅；

4.neighbors_set←∅；

5.improve_neighbors_set←∅；

6.X_res←∅；

7.y_res←∅；

8.Object←create_adasyn_object(neighbors，jobs)；

9.random_state←random(α)；

10.for class_samples，n_samples in S

11. class_sample←nonzero(class_sample)；

#剔除类样本中无效样本#

12. class_sample←index(X，class_sample)；

13. neighbors_set←find_knn(class_sample)；

14. neighbors←neighbors-1；

class_sample←train(class_sample)；

15. improve_neighbors_set←ratio_model(neighbor- s_set)；#引入瑞利分布#

16. improve_neighbors_set←fit_model(class_sam- ple)；

17. improve_neighbors_set←refind_knn(class_sam- ple)；#进行样本拟合和近邻寻找#

18.end for

19.for X_new，y_new in class_sample，improve_neigh- bors_set

20. if improve_neighbors_set≠∅

21. X_res←X_new；

22. y_res←y_new；

23. end if

24.end for

25.Return X_res，y_res

2)分类阶段

输入：样本集D

Step1.通过算法1，生成新的平衡样本集Dnew.

Step2.将Dnew作为随机森林的输入，通过Bootstraping(有放回抽样)采样方式，为每棵树构造训练集，其大小为N.

Step3.递归生成决策树

Step4.通过公式(4)来计算未分类样本x分类为C的概率:

P(C|x)=(1/NTree)∑hj(C|x)

(4)

Step5.采用多数投票法确定类别C←argmaxP(C|x)，同时计算分类误差.

Step6.采用Gridsearch算法选择合适的参数，通过不断的调整搜索范围找到较优的参数

Step7.在测试集中测试分类模型的分类效果，并进行评价

输出：参数调优后的随机森林分类器模型以及分类结果

算法整体流程图如图2所示.

图2 整体算法流程图Fig.2 Overall algorithm flow chart

为将本文改进算法与ADASYN，SMOTE的采样效果可视化，图3展示了3种算法在ecoli0147vs56和yeast6两个数据集中的采样效果，其中数据集ecoli0147vs56的不均衡比率为10.59，yeast6数据集的不均衡比率为41.4.

图3(a)为原始数据集分布；图3(b)为ADASYN算法的采样结果，可以看到算法受离群点样本影响较为明显，使得合成的新样本落在了多数类样本点附近，模糊了决策边界，增加了分类难度；图3(c)为SMOTE算法的采样结果，可以看出算法同样在一定程度上都到了离群点的影响，导致分类器对样本的误判；图3(d)是本文改进的ADARSYN算法，对安全样本和边界样本均进行了采样，同时在边界样本的附近合成样本较多，增强了决策边界的同时降低了噪声样本的影响.

图4 3种算法在数据集yeast6上的效果对比图Fig.4 Effect comparison diagram of the three algorithms on data set yeast6

图4(a)为原始数据集分布；图4(b)为ADASYN算法的采样结果；图4(c)为SMOTE算法的采样结果；图4(d)是本文改进的ADARSYN算法；可以看出本文改进算法在与ADASYN以及SMOTE算法的采样效果的对比中，较好的增强了决策边界，降低了离群样本点的影响.同时在不均衡比率不同的两个数据集中的实验表明，改进后的算法不均衡比率不同的数据集同样具有普适性.

3 评价指标

在不平衡数据中分类的困难不仅仅表现在对于算法以及分类模型的提升中，同时还在于对评价标准的选取，传统总体精度已经不能较为客观的评价不均衡分类模型的性能.因为在不均衡数据中多数类样本与少数类样本的分布以及其具有的不同的重要性.如果对少数类样本错误分类，可能导致付出较大的代价.在不均衡比率较大的数据集中，如果将少数类都错误的分为多数类，依旧可以得到较高的总体精度，但是不能有效的反应模型在不均衡数据上的性能.本文中选用几个常见的不均衡数据分类问题评价指标：F-measure、召回率(recall)、准确率(Accuracy，Acc)、马修斯相关系数(Matthews Correlation Coefficient，MCC).

表1 二分类混淆矩阵Table 1 Two-class confusion matrix

在不均衡数据中，分类模型的评价指标主要都是基于混淆矩阵，其二分类混淆矩阵如表1所示.其中TP表示正确预测到的正类样本个数，TN表示正确预测到的负类样本个数，FN表示正类样本预测为负类样本的个数，FP表示负类样本预测为正类样本的个数.

评价指标F-measure计算公式如下：

(5)

当参数β=1时，就是常见的F1.其中，

准确率是最为常见的性能指标，其定义为：

(6)

MCC计算公式如下：

(7)

4 实验与结果分析

4.1 实验数据集

本文采用KEEL机器学习数据库中的10个数据集和UCI数据库中的4个数据集wine，yeast，habermam，abalone，共14个数据集进行测试.在KEEL数据库中的8个数据集中用于二分类问题.在UCI数据集中的4个数据集也用于多分类，将其中的几类样本合并，形成二分类数据集.其中habermam数据集的类别1为多数类，类别2为少数类；abalone数据集中I类别为少数类，其他类别合并为多数类；wine数据集中3类别为少数类，其他类别合并为多数类；yeast数据集中ME3类别为少数类，其他类合并为多数类.数据集的不平衡度IR定义为多数类样本mmaj与少数类样本mmin的数量的比值.文中的不平衡比率IR从2.71-41.4不等，其中较大的IR值表示了少数类样本集和多数类样本集之间的不平衡程度越大.数据集的详细描述见表2.

表2 数据集信息Table 2 Datasets information

4.2 实验及结果分析

4.2.1 实验方法

为验证本文中改进算法ADARSYN算法的性能，将本文中算法与ADASYN算法、SMOTE算法、SVMSMOTE算法、Borderline-SMOTE算法的效果进行对比.SMOTE算法是通过对少数类样本的K近邻进行线性插值来合成新的样本；SVMSMOTE算法是基于支持向量的过采样，在支持向量近似的分类边界附近，根据决策机制生成少数类样本，把少数类样本扩大到多数类样本相对密度不高的区域，以提高分类模型的性能；Borderline-SMOTE算法是在边界样本中进行过采样.在数据集均衡化之后，在分类中采用随机森林的分类模型.

4.2.2 参数设置

在实验中算法SMOTE，SVMSMOTE，Borderline-SMOTE的最近邻k值，是提高随机森林模型分类效果的重要参数，在众多学者的多年研究中表明，在多数情况下当k值等于5时，采样会有较好的效果，因此k近邻值设置为k=5.同时实验中均采用5折交叉验证.

4.2.3 实验结果分析

从表3中可以看出，在特征数，不平衡比率以及样本个数均不同的数据集中，本文中改进的算法都能取得较好的效果，在能够提高模型整体分类效果的同时还具有不错的普适性，可以在较多的数据集上应用.

表3 ADARSYN与ADASYN，SMOTE，SVMSMOTE，BorderLineSMOTE采样方法对比结果Table 3 Comparison of ADARSYN with the methods of ADASYN、SMOTE、SVMSMOTE、BorderLineSMOTE

在实验中分析得出：SMOTE算法在近邻选择时具有一定的盲目性，容易产生分布边缘化问题，从而导致决策边界模糊，虽然使得数据集不均衡程度降低，但也增大了分类模型难度；BorderLineSMOTE和SVMSMOTE算法在采样时只是对边界样本进行采样操作，虽然在一定程度上解决了SMOTE算法带来的问题，但是也因为采样方式导致生成的新样本过于聚集，造成了样本的重叠；提出的ADARSYN算法在ADASYN算法考虑到样本数据分布的情况下，依据瑞利分布模型，在极值点增强了决策边界的同时，也以较小的概率密度对安全样本进行采样.

本文在KEEL数据库中选取了3个噪音与边界样本的数据集：03subcl5-600-5-50-BI、Paw02a-800-7-70-BI、04clover5z-800-7-70-BI.由表3中实验数据可以看出改进算法整体上相对有较大的提升.

为更加清晰直观的表示，5种方法在12个数据集上的F-measure如图5所示，数据集按照表1中的顺序分别从1-10进行标号.

图5 5种方法在不同的12个数据集上F-measure对比Fig.5 Five methods compared F-measures on different 12 data sets

5 总 结

针对不均衡数据中的问题，以及成熟算法的存在的部分缺点，对ADASYN进行了改进.本文ADARSYN算法结合瑞利分布对新样本进行生成，在考虑到安全样本与噪音样本的同时增强了决策边界.通过在不同的多个数据集上的实验，与其他几种算法进行比较，本文算法能够在一定程度上提升分类模型在不均衡数据集上的分类性能，具有较好的普适性.如何使得参数自动化，避免人为因素对算法的影响，进一步提升算法性能，将是今后的研究方向.