概率密度函數(shù)的自適應(yīng)過采樣算法研究

張忠林，傅添翼，閆光輝

(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070)

1 引 言

在現(xiàn)實(shí)世界中的眾多數(shù)據(jù)通常是不均衡的，其表現(xiàn)為類與類之間樣本數(shù)量較大的差異，當(dāng)常規(guī)分類器對(duì)這些不均衡的數(shù)據(jù)集進(jìn)行分類時(shí)，會(huì)導(dǎo)致分類器偏向多數(shù)類的樣本，從而產(chǎn)生誤分類的情況，而這些情況也會(huì)使我們付出較大的代價(jià).在進(jìn)行分類的過程中，比較經(jīng)典的分類算法有支持向量機(jī)[1]、樸素貝葉斯[2]、最近鄰分類算法[3]等等.但是在現(xiàn)實(shí)世界中存在著大量的不均衡數(shù)據(jù)，對(duì)于不均衡數(shù)據(jù)的分類問題，在我們身邊的諸多領(lǐng)域有著重要的應(yīng)用，例如信用卡欺詐[4]、異常檢測(cè)[5]、醫(yī)療健康預(yù)測(cè)[6]等等.在運(yùn)用傳統(tǒng)的分類方法處理不均衡數(shù)據(jù)時(shí)，少數(shù)類具有比較大的錯(cuò)分代價(jià)，同時(shí)我們也更加關(guān)注少數(shù)類的分類準(zhǔn)確率，這是因?yàn)樯贁?shù)類樣本通常具有較高的價(jià)值，是數(shù)據(jù)分析與挖掘中的重要目標(biāo).因此，很多研究學(xué)者將自己的研究方向放在了對(duì)于不均衡數(shù)據(jù)集的分類研究.

近年來，國內(nèi)外的學(xué)者在不均衡數(shù)據(jù)分類問題的研究中已經(jīng)取得了大量的成果，這些成果大致在數(shù)據(jù)層面和算法層面兩方面.在數(shù)據(jù)層面，主要采用的是抽樣方法來平衡各類別的樣本數(shù)，包括過采樣[7]、欠采樣[8]、混合采樣[9]、SMOTE[10](Synthetic Minority Oversampling technique)以及改進(jìn)算法Borderline-SMOTE[11]等等.在算法層面，主要是對(duì)傳統(tǒng)的分類器進(jìn)行改進(jìn)，使得分類器能夠適應(yīng)不均衡數(shù)據(jù)集，其目的就是要減少分類器對(duì)于多數(shù)類的偏重，在這里代價(jià)敏感與集成算法取得了較好的結(jié)果.代價(jià)敏感實(shí)質(zhì)上是為實(shí)際屬于少數(shù)類但是被錯(cuò)分為多數(shù)類的實(shí)例賦予更大的錯(cuò)分代價(jià)，避免生成過多的錯(cuò)誤.集成學(xué)習(xí)則能夠顯著的提高單個(gè)分類器的性能，使用最為廣泛的就是Yoav[12]提出的Boosting算法，其被運(yùn)用在了諸多算法當(dāng)中，例如SMOTEBoost[13]、RUSBoost[14]、EasyEnsemble[15]、EUSboost[16]等等.

學(xué)者們對(duì)于不均衡數(shù)據(jù)的分類問題進(jìn)行了大量的研究，也取得了豐碩的成果.但是仍然存在一些不足，傳統(tǒng)的欠采樣方法可能會(huì)刪除一些多數(shù)類樣本中的重要樣本點(diǎn)，丟失一部分的重要信息；隨機(jī)過采樣只是簡單的復(fù)制了少數(shù)類樣本，增大了產(chǎn)生過擬合的幾率；SMOTE算法雖然通過對(duì)少數(shù)類進(jìn)行分析，k個(gè)樣本之間線性插值合成了新的樣本，使得對(duì)少數(shù)類的預(yù)測(cè)精度有所提升，但是在合成新樣本時(shí)沒有考慮到樣本的分布，比較容易合成噪聲樣本以及冗余樣本.本文針對(duì)以上在不均衡數(shù)據(jù)分類中存在的問題，設(shè)計(jì)了一種基于ADASYN的改進(jìn)方法.

2 算 法

自適應(yīng)過采樣算法通過自身優(yōu)點(diǎn)解決了SMOTE會(huì)因樣本自身分布而產(chǎn)生噪聲樣本.本文中通過對(duì)自適應(yīng)過采樣的改進(jìn)算法對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)均衡化操作.最后采用隨機(jī)森林對(duì)數(shù)據(jù)進(jìn)行分類，同時(shí)采用網(wǎng)格搜索進(jìn)行參數(shù)尋優(yōu).

2.1 ADASYN算法

自適應(yīng)過采樣算法[17](Adaptive Synthetic sampling approach，ADASYN)是一種自適應(yīng)的數(shù)據(jù)合成方法，該方法可以根據(jù)少數(shù)類樣本的分布自適應(yīng)的合成新樣本.ADASYN算法中的每個(gè)少數(shù)類樣本根據(jù)其學(xué)習(xí)的復(fù)雜程度來確定需要合成的新樣本的個(gè)數(shù)，即在越難分類的地方生成更多的樣本.

ADASYN算法合成新樣本點(diǎn)步驟如下：

輸入：數(shù)據(jù)集Xtrain={(xi，yi)|x∈X，y∈Y}； X={x1，x2，…，xn}，Y={1，-1}；

輸出：新的樣本集Xnew；

1. Mmin←Count_min(Xtrain)；#樣本中少數(shù)類數(shù)目#

2. Mmaj←Count_maj(Xtrain)；#樣本中多數(shù)類數(shù)目#

3. Xmin←Search_min(Xtrain)；

4. d←div(Mmaj，Mmin)；#數(shù)據(jù)集不均衡因子#

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

#計(jì)算少數(shù)類樣本數(shù)量β∈[0，1]#

6. R←?；#少數(shù)類比例集合#

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)；

#計(jì)算每個(gè)少數(shù)類樣本周圍多數(shù)類的情況#

15. gi←mult(ri，G)；

#計(jì)算出各個(gè)少數(shù)類樣本xi需要合成的樣本數(shù)目#

由表1計(jì)算可以得到單樁承載力極限平均值為10 635 kN，極差與平均值的比為6.4%(<30%)，故單樁承載力極限為10 635 kN，遠(yuǎn)超過設(shè)計(jì)單樁承載力極限值8 000 kN。

16. end for

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

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

#合成新的少數(shù)類樣本#

19. Xnew←add(sj)；

20. end for

21. return Xnew

2.2 瑞利分布

(1)

圖1 σ=2時(shí)瑞利分布的概率密度函數(shù)圖Fig.1 Graph of the probability density function of the Rayleigh distribution at sigma=2

如圖1所示，是瑞利分布在σ=2時(shí)的概率密度函數(shù)圖，圖中在x=2時(shí)取得極值點(diǎn)，在極值點(diǎn)的左邊，f(x)隨著x的增大而迅速的增大，相反，在極值點(diǎn)的右邊，f(x)隨著x的增大而逐漸緩慢減小.

根據(jù)上文中給出的式(1)，我們可以控制圖1中的極值點(diǎn)的位置.因而在式(1)中由f(x)對(duì)x求導(dǎo)可得：

(2)

2.3 ADASYN算法改進(jìn)

雖然ADASYN算法相比于其他幾種傳統(tǒng)算法對(duì)分類器的性能有一定程度的提升，考慮到了樣本分布，但是其本身仍然有一定程度上的不足，受到噪聲點(diǎn)的較大影響，會(huì)在具有大量多數(shù)類實(shí)例的鄰域中生成更多的新樣本.蔣華[19]等人將K近鄰均為多數(shù)類的少數(shù)類樣本直接刪除，這種欠采樣操作雖然一定程度上降低了噪聲樣本點(diǎn)的影響，但同時(shí)也可能丟失重要信息.Han等人在Borderline-SMOTE算法中提出：在距離決策邊界較近的樣本中進(jìn)行采樣操作，這樣可以提高分類器的性能.ADASYN算法雖然考慮到了樣本點(diǎn)的分布造成的影響，同時(shí)也受到了離群噪聲點(diǎn)的影響.ADASYN算法中以少數(shù)類樣本點(diǎn)的K個(gè)近鄰中包含多數(shù)類樣本點(diǎn)個(gè)數(shù)作為標(biāo)準(zhǔn)，當(dāng)少數(shù)類樣本點(diǎn)的K個(gè)近鄰中的多數(shù)類樣本點(diǎn)越多，表明對(duì)于該樣本點(diǎn)的學(xué)習(xí)就會(huì)越困難，就需要在該樣本點(diǎn)周圍更多的合成新的樣本點(diǎn).同時(shí)，當(dāng)一個(gè)少數(shù)類樣本點(diǎn)的K個(gè)近鄰中多數(shù)是多數(shù)類樣本點(diǎn)，該少數(shù)類樣本點(diǎn)是噪聲的可能性也會(huì)隨之增大，此時(shí)分類器的性能就會(huì)隨著噪聲樣本點(diǎn)的增多而下降.

對(duì)于以上問題，本文引入了瑞利分布來對(duì)ADASYN算法來加以改進(jìn).對(duì)于其中新樣本的密度分布，使用瑞利分布的概率密度函數(shù)來進(jìn)行構(gòu)造.在本算法中對(duì)少數(shù)類樣本進(jìn)行劃分，以少數(shù)類樣本的K近鄰中包含多數(shù)類的樣本個(gè)數(shù)Δ為依據(jù)，將Δ作為閾值標(biāo)準(zhǔn)，把少數(shù)類劃分為3類：安全樣本，邊界樣本，危險(xiǎn)樣本.通過瑞利分布的概率密度函數(shù)我們可以更好的對(duì)安全樣本和邊界樣本進(jìn)行采樣.當(dāng)Δ小于我們閾值時(shí)，該樣本屬于安全樣本；當(dāng)Δ等于閾值時(shí)，該樣本屬于邊界樣本；當(dāng)Δ大于閾值時(shí)，該樣本屬于危險(xiǎn)樣本.在劃分出的3類中，當(dāng)由邊界樣本合成的新樣本越多，密度越大，此時(shí)就有利于增強(qiáng)決策邊界.對(duì)于上文中提到的瑞利分布，在極值點(diǎn)左右兩側(cè)的斜率不同，設(shè)置圖1中的極值為Δ等于閾值時(shí)合成的新樣本的密度，這樣就可以使得新樣本集中的合成在邊界樣本附近，增強(qiáng)決策邊界.

對(duì)于Δ的值，考慮到樣本的K近鄰中存在的多數(shù)類樣本數(shù)，設(shè)置Δ=k/2，判斷此時(shí)的樣本點(diǎn)屬于邊界樣本，同時(shí)又要瑞利分布的極值點(diǎn)處的新樣本密度最大，此時(shí)我們令σ=x=Δ=k/2.

1)數(shù)據(jù)預(yù)處理階段ADASYN改進(jìn)

在之前的ADASYN算法中少數(shù)類樣本的比率ri是通過公式ri=Δ/k計(jì)算得到，本文中應(yīng)用瑞利分布的概率密度函數(shù)來計(jì)算比率ri.即對(duì)于每個(gè)少數(shù)類樣本xi，在其K個(gè)近鄰中多數(shù)類樣本的個(gè)數(shù)記為Δi，則ri的計(jì)算公式如公式(3)所示.算法的具體步驟如算法1所示.

(3)

算法1.ADASYN(X)：

輸入：數(shù)據(jù)集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)；#進(jìn)行樣本擬合和近鄰尋找#

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作為隨機(jī)森林的輸入，通過Bootstraping(有放回抽樣)采樣方式，為每棵樹構(gòu)造訓(xùn)練集，其大小為N.

Step3.遞歸生成決策樹

Step4.通過公式(4)來計(jì)算未分類樣本x分類為C的概率:

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

(4)

Step5.采用多數(shù)投票法確定類別C←argmaxP(C|x)，同時(shí)計(jì)算分類誤差.

Step6.采用Gridsearch算法選擇合適的參數(shù)，通過不斷的調(diào)整搜索范圍找到較優(yōu)的參數(shù)

Step7.在測(cè)試集中測(cè)試分類模型的分類效果，并進(jìn)行評(píng)價(jià)

輸出：參數(shù)調(diào)優(yōu)后的隨機(jī)森林分類器模型以及分類結(jié)果

算法整體流程圖如圖2所示.

圖2 整體算法流程圖Fig.2 Overall algorithm flow chart

為將本文改進(jìn)算法與ADASYN，SMOTE的采樣效果可視化，圖3展示了3種算法在ecoli0147vs56和yeast6兩個(gè)數(shù)據(jù)集中的采樣效果，其中數(shù)據(jù)集ecoli0147vs56的不均衡比率為10.59，yeast6數(shù)據(jù)集的不均衡比率為41.4.

圖3(a)為原始數(shù)據(jù)集分布；圖3(b)為ADASYN算法的采樣結(jié)果，可以看到算法受離群點(diǎn)樣本影響較為明顯，使得合成的新樣本落在了多數(shù)類樣本點(diǎn)附近，模糊了決策邊界，增加了分類難度；圖3(c)為SMOTE算法的采樣結(jié)果，可以看出算法同樣在一定程度上都到了離群點(diǎn)的影響，導(dǎo)致分類器對(duì)樣本的誤判；圖3(d)是本文改進(jìn)的ADARSYN算法，對(duì)安全樣本和邊界樣本均進(jìn)行了采樣，同時(shí)在邊界樣本的附近合成樣本較多，增強(qiáng)了決策邊界的同時(shí)降低了噪聲樣本的影響.

圖4 3種算法在數(shù)據(jù)集yeast6上的效果對(duì)比圖Fig.4 Effect comparison diagram of the three algorithms on data set yeast6

圖4(a)為原始數(shù)據(jù)集分布；圖4(b)為ADASYN算法的采樣結(jié)果；圖4(c)為SMOTE算法的采樣結(jié)果；圖4(d)是本文改進(jìn)的ADARSYN算法；可以看出本文改進(jìn)算法在與ADASYN以及SMOTE算法的采樣效果的對(duì)比中，較好的增強(qiáng)了決策邊界，降低了離群樣本點(diǎn)的影響.同時(shí)在不均衡比率不同的兩個(gè)數(shù)據(jù)集中的實(shí)驗(yàn)表明，改進(jìn)后的算法不均衡比率不同的數(shù)據(jù)集同樣具有普適性.

3 評(píng)價(jià)指標(biāo)

在不平衡數(shù)據(jù)中分類的困難不僅僅表現(xiàn)在對(duì)于算法以及分類模型的提升中，同時(shí)還在于對(duì)評(píng)價(jià)標(biāo)準(zhǔn)的選取，傳統(tǒng)總體精度已經(jīng)不能較為客觀的評(píng)價(jià)不均衡分類模型的性能.因?yàn)樵诓痪鈹?shù)據(jù)中多數(shù)類樣本與少數(shù)類樣本的分布以及其具有的不同的重要性.如果對(duì)少數(shù)類樣本錯(cuò)誤分類，可能導(dǎo)致付出較大的代價(jià).在不均衡比率較大的數(shù)據(jù)集中，如果將少數(shù)類都錯(cuò)誤的分為多數(shù)類，依舊可以得到較高的總體精度，但是不能有效的反應(yīng)模型在不均衡數(shù)據(jù)上的性能.本文中選用幾個(gè)常見的不均衡數(shù)據(jù)分類問題評(píng)價(jià)指標(biāo)：F-measure、召回率(recall)、準(zhǔn)確率(Accuracy，Acc)、馬修斯相關(guān)系數(shù)(Matthews Correlation Coefficient，MCC).

表1 二分類混淆矩陣Table 1 Two-class confusion matrix

在不均衡數(shù)據(jù)中，分類模型的評(píng)價(jià)指標(biāo)主要都是基于混淆矩陣，其二分類混淆矩陣如表1所示.其中TP表示正確預(yù)測(cè)到的正類樣本個(gè)數(shù)，TN表示正確預(yù)測(cè)到的負(fù)類樣本個(gè)數(shù)，F(xiàn)N表示正類樣本預(yù)測(cè)為負(fù)類樣本的個(gè)數(shù)，F(xiàn)P表示負(fù)類樣本預(yù)測(cè)為正類樣本的個(gè)數(shù).

評(píng)價(jià)指標(biāo)F-measure計(jì)算公式如下：

(5)

當(dāng)參數(shù)β=1時(shí)，就是常見的F1.其中，

準(zhǔn)確率是最為常見的性能指標(biāo)，其定義為：

(6)

MCC計(jì)算公式如下：

(7)

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用KEEL機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的10個(gè)數(shù)據(jù)集和UCI數(shù)據(jù)庫中的4個(gè)數(shù)據(jù)集wine，yeast，habermam，abalone，共14個(gè)數(shù)據(jù)集進(jìn)行測(cè)試.在KEEL數(shù)據(jù)庫中的8個(gè)數(shù)據(jù)集中用于二分類問題.在UCI數(shù)據(jù)集中的4個(gè)數(shù)據(jù)集也用于多分類，將其中的幾類樣本合并，形成二分類數(shù)據(jù)集.其中habermam數(shù)據(jù)集的類別1為多數(shù)類，類別2為少數(shù)類；abalone數(shù)據(jù)集中I類別為少數(shù)類，其他類別合并為多數(shù)類；wine數(shù)據(jù)集中3類別為少數(shù)類，其他類別合并為多數(shù)類；yeast數(shù)據(jù)集中ME3類別為少數(shù)類，其他類合并為多數(shù)類.數(shù)據(jù)集的不平衡度IR定義為多數(shù)類樣本mmaj與少數(shù)類樣本mmin的數(shù)量的比值.文中的不平衡比率IR從2.71-41.4不等，其中較大的IR值表示了少數(shù)類樣本集和多數(shù)類樣本集之間的不平衡程度越大.數(shù)據(jù)集的詳細(xì)描述見表2.

表2 數(shù)據(jù)集信息Table 2 Datasets information

4.2 實(shí)驗(yàn)及結(jié)果分析

4.2.1 實(shí)驗(yàn)方法

為驗(yàn)證本文中改進(jìn)算法ADARSYN算法的性能，將本文中算法與ADASYN算法、SMOTE算法、SVMSMOTE算法、Borderline-SMOTE算法的效果進(jìn)行對(duì)比.SMOTE算法是通過對(duì)少數(shù)類樣本的K近鄰進(jìn)行線性插值來合成新的樣本；SVMSMOTE算法是基于支持向量的過采樣，在支持向量近似的分類邊界附近，根據(jù)決策機(jī)制生成少數(shù)類樣本，把少數(shù)類樣本擴(kuò)大到多數(shù)類樣本相對(duì)密度不高的區(qū)域，以提高分類模型的性能；Borderline-SMOTE算法是在邊界樣本中進(jìn)行過采樣.在數(shù)據(jù)集均衡化之后，在分類中采用隨機(jī)森林的分類模型.

4.2.2 參數(shù)設(shè)置

在實(shí)驗(yàn)中算法SMOTE，SVMSMOTE，Borderline-SMOTE的最近鄰k值，是提高隨機(jī)森林模型分類效果的重要參數(shù)，在眾多學(xué)者的多年研究中表明，在多數(shù)情況下當(dāng)k值等于5時(shí)，采樣會(huì)有較好的效果，因此k近鄰值設(shè)置為k=5.同時(shí)實(shí)驗(yàn)中均采用5折交叉驗(yàn)證.

4.2.3 實(shí)驗(yàn)結(jié)果分析

從表3中可以看出，在特征數(shù)，不平衡比率以及樣本個(gè)數(shù)均不同的數(shù)據(jù)集中，本文中改進(jìn)的算法都能取得較好的效果，在能夠提高模型整體分類效果的同時(shí)還具有不錯(cuò)的普適性，可以在較多的數(shù)據(jù)集上應(yīng)用.

表3 ADARSYN與ADASYN，SMOTE，SVMSMOTE，BorderLineSMOTE采樣方法對(duì)比結(jié)果Table 3 Comparison of ADARSYN with the methods of ADASYN、SMOTE、SVMSMOTE、BorderLineSMOTE

在實(shí)驗(yàn)中分析得出：SMOTE算法在近鄰選擇時(shí)具有一定的盲目性，容易產(chǎn)生分布邊緣化問題，從而導(dǎo)致決策邊界模糊，雖然使得數(shù)據(jù)集不均衡程度降低，但也增大了分類模型難度；BorderLineSMOTE和SVMSMOTE算法在采樣時(shí)只是對(duì)邊界樣本進(jìn)行采樣操作，雖然在一定程度上解決了SMOTE算法帶來的問題，但是也因?yàn)椴蓸臃绞綄?dǎo)致生成的新樣本過于聚集，造成了樣本的重疊；提出的ADARSYN算法在ADASYN算法考慮到樣本數(shù)據(jù)分布的情況下，依據(jù)瑞利分布模型，在極值點(diǎn)增強(qiáng)了決策邊界的同時(shí)，也以較小的概率密度對(duì)安全樣本進(jìn)行采樣.

本文在KEEL數(shù)據(jù)庫中選取了3個(gè)噪音與邊界樣本的數(shù)據(jù)集：03subcl5-600-5-50-BI、Paw02a-800-7-70-BI、04clover5z-800-7-70-BI.由表3中實(shí)驗(yàn)數(shù)據(jù)可以看出改進(jìn)算法整體上相對(duì)有較大的提升.

為更加清晰直觀的表示，5種方法在12個(gè)數(shù)據(jù)集上的F-measure如圖5所示，數(shù)據(jù)集按照表1中的順序分別從1-10進(jìn)行標(biāo)號(hào).

圖5 5種方法在不同的12個(gè)數(shù)據(jù)集上F-measure對(duì)比Fig.5 Five methods compared F-measures on different 12 data sets

5 總 結(jié)

針對(duì)不均衡數(shù)據(jù)中的問題，以及成熟算法的存在的部分缺點(diǎn)，對(duì)ADASYN進(jìn)行了改進(jìn).本文ADARSYN算法結(jié)合瑞利分布對(duì)新樣本進(jìn)行生成，在考慮到安全樣本與噪音樣本的同時(shí)增強(qiáng)了決策邊界.通過在不同的多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)，與其他幾種算法進(jìn)行比較，本文算法能夠在一定程度上提升分類模型在不均衡數(shù)據(jù)集上的分類性能，具有較好的普適性.如何使得參數(shù)自動(dòng)化，避免人為因素對(duì)算法的影響，進(jìn)一步提升算法性能，將是今后的研究方向.