改進MAHAKIL 的過采樣技術

袁甜甜，李鳳蓮，左婷

（太原理工大學信息與計算機學院，山西榆次 030600）

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

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

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

1 相關理論

1.1 MAHAKIL過采樣技術

1.1.1 馬氏距離

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

1.1.2 MAHAKIL算法原理

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

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

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

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

Step4：子樣本與親代樣本交叉結合，直至滿足需要合成的樣本數。

1.2 孤立森林算法

在過采樣過程中，不可避免地會產生噪聲因子，合成的少數類樣本有時會成為多數類的一部分，影響了分類的效果。圖1 描述了噪聲樣本的情況[10]，其中，N 為噪聲樣本(Noisy Sample)；B 為邊界樣本(Borderline Sample)；S 為安全樣本(Safe Sample)，噪聲被定義為錯誤的標簽或屬性值中的噪聲。

圖1 噪聲樣本

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

1）異常樣本占數據集的很小部分。

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

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

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

圖2 數據集中樣本點的孤立

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

1）訓練階段

孤立二叉樹建立對數據集D的遞歸分割，直至所有樣本點被孤立，或者達到了樹的指定高度。

2）評估階段

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

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

2 MARAIF算法實現

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

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

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

算法1：MAHARA(MAHAKIL Random)

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

2）Dnew：生成樣本數組，初始化為0；Dnewnum：統計生成樣本的數量；

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

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

Dpar1={d1,d2,…,dmid},Dpar2={dmid+1,dmid+2,…,dt}，其中di∈Dminmaha。對于da∈Dpar1,db∈Dpar2，分配唯一的標簽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中的樣本結合，并重復步驟5）-6）生成Dnew[j](j=1,2)；如果仍然Dnewnum＜T，將當前Dnew與它的直系父代配對，然后與前任父代配對，并重復步驟5）-6）；

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

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

圖3 MARAIF算法流程圖

3 實驗及結果分析

3.1 評價指標

傳統的二分類評價標準由表1 所示的混淆矩陣[14]元素組成。

表1 混淆矩陣元素

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

3.2 數據集

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

表2 公共數據集

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

3.3 實驗設計

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

3.4 公共數據集的實驗結果與分析

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

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

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

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

3.5 腦卒中數據集的實驗結果與分析

圖4、圖5 顯示了腦卒中篩查數據集與已有過采樣技術在AUC 值、F1-measure 值的實驗對比結果。

圖4 算法在腦卒中篩查數據集中AUC結果對比

圖5 算法在腦卒中篩查數據集中F1-measure結果對比

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

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

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

4 結論

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