改進(jìn)MAHAKIL 的過采樣技術(shù)

袁甜甜，李鳳蓮，左婷

（太原理工大學(xué)信息與計算機(jī)學(xué)院，山西榆次 030600）

在現(xiàn)實(shí)生活中，存在很多不平衡問題，如疾病診斷[1]、非法網(wǎng)絡(luò)入侵[2]等。腦卒中是嚴(yán)重威脅全國居民公共健康的疾病之一，是全球范圍內(nèi)致死、致殘的重要原因[3]。對腦卒中進(jìn)行輔助診斷也常面臨數(shù)據(jù)不平衡的問題。不平衡指的是不同類別中，一類（稱為多數(shù)類或負(fù)數(shù)）所包含的樣本數(shù)遠(yuǎn)多于其他類（稱為少數(shù)類或正類）。機(jī)器學(xué)習(xí)算法訓(xùn)練分類器時，容易導(dǎo)致對多數(shù)類的偏向，使得分類結(jié)果具有高準(zhǔn)確率，少數(shù)類樣本卻存在高誤分率。

近年來，學(xué)者們對類不平衡問題展開了深入研究，在不降低多數(shù)類樣本準(zhǔn)確率的前提下，提高機(jī)器學(xué)習(xí)預(yù)測正類樣本的準(zhǔn)確性。文獻(xiàn)[4]提出了SMOTE-LOF 算法，剔除合成少數(shù)類樣本的噪聲因子，通過添加局部利群因子(Local Outlier Factor,LOF)來改進(jìn)傳統(tǒng)的合成少數(shù)樣本過采樣技術(shù)(Synthetic Minority Oversampling Technique,SMOTE)；文獻(xiàn)[5]建立了一個分類器模型，結(jié)合遺傳算法與BP神經(jīng)網(wǎng)絡(luò)，取得了良好的分類效果，但沒有考慮算法的復(fù)雜度問題。文獻(xiàn)[6]基于遺傳算法提出MAHAKIL 過采樣算法，將兩個不同的少數(shù)類樣本當(dāng)作父母，繼承父母不同的特征合成新的樣本，該算法極大地提高了分類性能。但沒有考慮合成樣本的多樣性及其噪聲問題。以上研究證明，過采樣技術(shù)對解決類不平衡問題有了良好的效果，但還存在進(jìn)步空間。

為實(shí)現(xiàn)合成樣本的多樣性，該文提出了MARAIF算法(MAHAKIL Random and Isolation Forest)。首先，通過采用隨機(jī)數(shù)替換平均數(shù)的方法合成新樣本，提出了改進(jìn)的MAHAKIL 算法。同時，采用了孤立森林(Isolation Forest，ISF)算法[7]檢測離群樣本，提高了預(yù)測精度。

1 相關(guān)理論

1.1 MAHAKIL過采樣技術(shù)

1.1.1 馬氏距離

馬氏距離是由印度學(xué)者提出的[8]，用來度量數(shù)據(jù)之間的相似性，與常用歐幾里得距離不同的是，馬氏距離考慮了樣本數(shù)據(jù)特征之間的關(guān)系，消除了樣本之間的相關(guān)干擾；利用樣本數(shù)據(jù)之間的協(xié)方差，使得相似性不受樣本維度的干擾。對于兩個樣本x=[x1,x2,…,xm]T與y=[y1,y2,…,ym]T，馬氏距離計算公式如式（1）所示：

1.1.2 MAHAKIL算法原理

SMOTE 過采樣技術(shù)采用K 近鄰方法選取與樣本點(diǎn)相近的樣本[9]，與之結(jié)合生成新樣本。這種方法一方面容易拓寬少數(shù)類樣本的邊界，影響分類效果；另一方面若少數(shù)類樣本存在類內(nèi)不平衡問題，生成的新樣本只會增加子簇的大小，惡化類內(nèi)不平衡。針對該問題，文獻(xiàn)[6]提出了MAHAKIL 過采樣技術(shù)，利用初始種群中的樣本進(jìn)行連續(xù)交叉生成新的合成樣本，使得子代樣本與親代樣本之間保持一致性，又添加了新的特征。MAHAKIL 算法合成新樣本步驟如下：

Step 1：將數(shù)據(jù)集D分為多數(shù)類Dmaj與少數(shù)類Dmin，計算T=Dmaj-Dmin為需要合成的新樣本數(shù)目。計算D中每個樣本到中心點(diǎn)的馬氏距離，并進(jìn)行降序排列。

Step2：按照馬氏距離大小將樣本分為兩個部分，并依次為每個樣本分配唯一的標(biāo)簽。

Step3：從兩個分區(qū)中選擇兩個樣本（具有相同的唯一標(biāo)簽），求取平均值生成新的合成樣本。

Step4：子樣本與親代樣本交叉結(jié)合，直至滿足需要合成的樣本數(shù)。

1.2 孤立森林算法

在過采樣過程中，不可避免地會產(chǎn)生噪聲因子，合成的少數(shù)類樣本有時會成為多數(shù)類的一部分，影響了分類的效果。圖1 描述了噪聲樣本的情況[10]，其中，N 為噪聲樣本(Noisy Sample)；B 為邊界樣本(Borderline Sample)；S 為安全樣本(Safe Sample)，噪聲被定義為錯誤的標(biāo)簽或?qū)傩灾抵械脑肼暋?/p>

圖1 噪聲樣本

針對生成新樣本中的噪聲問題，可以采用異常值檢測技術(shù)。孤立森林是一種有效的無監(jiān)督異常值檢測算法[11]，孤立是指從整個數(shù)據(jù)集中分離出異常的數(shù)據(jù)，通常情況下，正常數(shù)據(jù)比異常數(shù)據(jù)要多。異常數(shù)據(jù)的特點(diǎn)如下：

1）異常樣本占數(shù)據(jù)集的很小部分。

2）與正常數(shù)據(jù)相比，異常數(shù)據(jù)具有不同的行為或特征。

不同于傳統(tǒng)的異常檢測算法（如LOF[12]、KNN[13]），ISF 不計算距離或密度，因此顯著減少了執(zhí)行時間和內(nèi)存需求；具有低而小的內(nèi)存需求[11]和線性執(zhí)行時間。

算法原理是遞歸地隨機(jī)切分?jǐn)?shù)據(jù)集，直至所有的樣本點(diǎn)被孤立，在這種切分策略下，異常值通常切分較少的次數(shù)就可以被孤立。如圖2 所示，密度較高的正常樣本Xi需要切分很多次才能被孤立，而異常值X0則很容易就被孤立。

圖2 數(shù)據(jù)集中樣本點(diǎn)的孤立

ISF 檢測異常值包括兩個步驟：訓(xùn)練階段與評估階段。

1）訓(xùn)練階段

孤立二叉樹建立對數(shù)據(jù)集D的遞歸分割，直至所有樣本點(diǎn)被孤立，或者達(dá)到了樹的指定高度。

2）評估階段

計算數(shù)據(jù)集中每個樣本的得分。該分?jǐn)?shù)是樣本與其他樣本之間的相似性程度。根據(jù)樣本的路徑長度h(d)，計算樣本d的異常分?jǐn)?shù)，如式（2）所示：

其中，n是數(shù)據(jù)集D的樣本總數(shù)，E(h(d))是樣本d的多顆樹的路徑長度平均值。C(n)用來對樣本d的路徑長度進(jìn)行標(biāo)準(zhǔn)化。H(i)=ln(i)+0.577 215 664 9為調(diào)和數(shù)。E(h(d))值越小，則樣本的異常分?jǐn)?shù)越接近于1，此時，樣本被認(rèn)定為異常樣本。

2 MARAIF算法實(shí)現(xiàn)

該文提出的MARAIF 算法的原理：首先，將不平衡數(shù)據(jù)集分為多數(shù)類與少數(shù)類，對少數(shù)類樣本，采用改進(jìn)的MAHAKIL 算法合成新樣本。將合成的新樣本采用孤立森林算法去除噪聲因子。最終重組多數(shù)類與少數(shù)類樣本。

MAHAKIL 算法在合成子代樣本時，取親代樣本二者的平均值，忽視了合成新樣本的多樣性問題。筆者認(rèn)為，使用隨機(jī)數(shù)替換單一取平均值的方法，繼承親代不同比例的特征，不僅使生成的樣本有更多的特性，又能夠保留親代的特點(diǎn)。改進(jìn)的MAHAKIL算法描述如算法1 所示。

過采樣技術(shù)合成的新樣本往往伴隨著生成噪聲樣本，以干擾分類性能。為避免噪聲的影響，提高合成樣本的有效率，該研究采用ISF 異常檢測技術(shù)，檢測出的異常值即噪聲因子。

算法1：MAHARA(MAHAKIL Random)

1）將數(shù)據(jù)集D分為多數(shù)類數(shù)組Dmaj和少數(shù)類數(shù)組Dmin，計算需要生成的樣本數(shù)T=Dmaj-Dmin；

2）Dnew：生成樣本數(shù)組，初始化為0；Dnewnum：統(tǒng)計生成樣本的數(shù)量；

3）計算Dmin中樣本的馬氏距離，按照順序遞減排列并保存到Dminmaha；

4）找到Dmin的中心點(diǎn)，即Dmid=T/2,將Dminmaha分為兩個部分：

Dpar1={d1,d2,…,dmid},Dpar2={dmid+1,dmid+2,…,dt}，其中di∈Dminmaha。對于da∈Dpar1,db∈Dpar2，分配唯一的標(biāo)簽li,i=1,2,…,mid；

5）fori=1,2,…,mid

從Dpar1、Dpar2分別選取樣本da、db，其 中，da(li)==db(li)

生成新的樣本：

將d添加到Dnew;Dnewnum+1

6）end for

7）如果Dnewnum＜T，則將Dnew中的樣本與Dpar中的樣本結(jié)合，并重復(fù)步驟5）-6）生成Dnew[j](j=1,2)；如果仍然Dnewnum＜T，將當(dāng)前Dnew與它的直系父代配對，然后與前任父代配對，并重復(fù)步驟5）-6）；

8）直至Dnewnum＞=T，Dnew中的所有樣本即為生成的少數(shù)類樣本。

被識別的噪聲僅來源于MAHARA 產(chǎn)生的合成少數(shù)類樣本，而不是原始樣本。剔除識別為噪聲的樣本，然后重組多數(shù)類與少數(shù)類樣本，使用機(jī)器學(xué)習(xí)分類器將最終所得的平衡數(shù)據(jù)集進(jìn)行分類。MARAIF 過采樣算法流程圖如圖3 所示。

圖3 MARAIF算法流程圖

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

3.1 評價指標(biāo)

傳統(tǒng)的二分類評價標(biāo)準(zhǔn)由表1 所示的混淆矩陣[14]元素組成。

表1 混淆矩陣元素

在不平衡數(shù)據(jù)集中，少數(shù)類樣本被稱為正類，多數(shù)類樣本被稱為負(fù)類。實(shí)驗(yàn)選取F1-measure、AUC（ROC 曲線下的面積）評估分類性能，計算公式如式（4）-（5）所示：

3.2 數(shù)據(jù)集

實(shí)驗(yàn)選用的公共數(shù)據(jù)集的信息如表2 所示，包括數(shù)據(jù)集(Datasets)、樣本數(shù)量(Amounts)、屬性個數(shù)(Attributes)以及數(shù)據(jù)集的不平衡率（Imbalance Rate,IR）。隨機(jī)選取數(shù)據(jù)集的80%作為訓(xùn)練集，20%作為測試集。

表2 公共數(shù)據(jù)集

該文采用的腦卒中發(fā)病風(fēng)險預(yù)測數(shù)據(jù)集從國內(nèi)某醫(yī)院神經(jīng)內(nèi)科腦卒中篩查病例數(shù)據(jù)庫中獲取，經(jīng)過數(shù)據(jù)清洗等預(yù)處理后，整理得到數(shù)據(jù)集Stroke。該數(shù)據(jù)集包含41 個屬性，診斷類別為八類。實(shí)驗(yàn)選取兩種類別：腦出血（251 例）和頸動脈狹窄或閉塞（33 例），不平衡率為7.61。

3.3 實(shí)驗(yàn)設(shè)計

為了比較MARAIF 算法的性能，實(shí)驗(yàn)采用了SMOTE[15]、MAHAKIL、ADASYN[16]進(jìn)行對比實(shí)驗(yàn)。另外，為了分析MARAIF 算法結(jié)合不同分類算法的分類效果，實(shí)驗(yàn)選擇了五種常用的分類算法：邏輯回歸(Logistic Regression,LR)、決策樹(Decision Tree,DT)、隨機(jī)森林(Random Forest,RF)、支持向量機(jī)(Support Vector Machine,SVM)以及K 近鄰(K-Nearest Neighbor,KNN)。實(shí)驗(yàn)采用了5-fold 交叉驗(yàn)證網(wǎng)格尋優(yōu)法搜索分類器的最優(yōu)參數(shù)，使用AUC 作為尋優(yōu)的目標(biāo)參數(shù)。

3.4 公共數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果與分析

表3 顯示了公共數(shù)據(jù)集在每種過采樣方法下AUC、F1-measure 評價指標(biāo)的實(shí)驗(yàn)結(jié)果。當(dāng)使用AUC 為評價指標(biāo)時，所提算法MARAIF 與其他方法的比較結(jié)果如表3 左側(cè)所示，可以看出除了數(shù)據(jù)集Churn_ prediction 外，MARAIF 算法可以在三個數(shù)據(jù)集上獲得更好的分類性能，其中Glass-1-2-7_vs_3取得的效果最為明顯，在決策樹分類器上，相較于SMOTE、ADASYN、MAHAKIL 分別提高了25.50%、21.74%、20.95%。而在Churn_ prediction 數(shù)據(jù)集上，MARAIF 算法相較于MAHAKIL，除了在決策樹分類器取得了相同的分類性能，在其他分類器上均表現(xiàn)更好，驗(yàn)證了MARAIF 算法提高不平衡樣本集分類能力的有效性。

表3 公共數(shù)據(jù)集MARAIF算法與已有過采樣技術(shù)AUC值、F1-measure結(jié)果對比

表3 右側(cè)呈現(xiàn)了MARAIF 算法與其他算法的F1-measure 結(jié)果，可以看出，在Glass-1-2-7_vs_3 數(shù)據(jù)集上，除了決策樹分類器，較之SMOTE 有0.1%的降低外，其他均有提高，且分類性能均優(yōu)于MAHAKIL 算法；此外，在Churn_ prediction 數(shù)據(jù)集上，該文所提出的MARAIF 算法在LR、DT、SVM、KNN 分類器的性能均低于SMOTE，但與MAHAKIL進(jìn)行比較，均優(yōu)于MAHAKIL 算法，驗(yàn)證了該文提出的基于MAHAKIL 的改進(jìn)算法的有效性。

從數(shù)據(jù)集層面分析，該文算法更適用于低失衡率的數(shù)據(jù)集，優(yōu)于其他對比的過采樣技術(shù)。在高失衡數(shù)據(jù)集（Churn_ prediction）中，MARAIF 算法性能較MAHAKIL 更為優(yōu)越。在F1-measure 評價指標(biāo)方面，與SMOTE 還有些許差距。

3.5 腦卒中數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果與分析

圖4、圖5 顯示了腦卒中篩查數(shù)據(jù)集與已有過采樣技術(shù)在AUC 值、F1-measure 值的實(shí)驗(yàn)對比結(jié)果。

圖4 算法在腦卒中篩查數(shù)據(jù)集中AUC結(jié)果對比

圖5 算法在腦卒中篩查數(shù)據(jù)集中F1-measure結(jié)果對比

由圖4 可以看出，MARAIF 算法在DT、RF、SVM分類器均取得了最好的結(jié)果，其中，決策樹分類器的效果最為明顯，較之SMOTE、ADASYN、MAHAKIL 過采樣技術(shù)，AUC 分別提高了32.61%、5.17%、6.64%。此外，在LR、KNN 分類器上，雖實(shí)驗(yàn)結(jié)果不是最好的，但性能均優(yōu)于MAHAKIL 算法。

從圖5結(jié)果可知，在決策樹分類器、KNN分類器上，MARAIF 算法均取得了最好的F1-measure 值；此外，除邏輯回歸分類器以外，MARAIF 算法的效果均優(yōu)于MAHAKIL算法，驗(yàn)證了該文所提出算法的有效性。

綜合結(jié)果表明，該文算法具有比SMOTE、ADASYN、MAHAKIL 三種過采樣技術(shù)更優(yōu)越的分類性能。MARAIF 算法適用于多種類型的分類器，特別是決策樹分類器，可獲得更好的分類性能。此外，對于較低失衡率的數(shù)據(jù)集[17-18]，該文所提出的算法更能體現(xiàn)其優(yōu)越性。

4 結(jié)論

為了解決腦卒中篩查數(shù)據(jù)集的類別不平衡問題，該文基于MAHAKIL 與孤立森林提出一種MARAIF 過采樣算法，該算法采用隨機(jī)數(shù)克服了MAHAKIL 合成新樣本單一的缺點(diǎn)。針對過采樣生成新樣本容易生成噪聲樣本，影響分類性能的缺陷，對新生成的樣本該文采用孤立森林算法對噪聲樣本進(jìn)行過濾，得到更具識別率的新樣本。通過在不同機(jī)器學(xué)習(xí)分類器進(jìn)行實(shí)驗(yàn)，與SMOTE、ADASYN、MAHAKIL 過采樣技術(shù)進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明，MARAIF 算法綜合表現(xiàn)優(yōu)于其他三種過采樣技術(shù)，且適用于多種類型的分類器。但是，對于高失衡的樣本數(shù)據(jù)集，分類效果略低于SMOTE，下一步將研究如何更有效地提高對高失衡數(shù)據(jù)集的分類性能。