不平衡數據的下采樣方法研究?

周建偉

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

近二十年來，不平衡學習（Imbalanced Data Learning）問題作為機器學習中的一個分支得到了產業界、學術界、和政府基金機構的密切關注，成為了業界各大會議研討的重要主題之一［1～2］。現實生活中，數據不平衡問題廣泛存在于各個不同領域，如網絡入侵檢測、圖像識別、信息檢索、金融欺詐檢測、風險管理、生物醫學應用和石油溢出檢測等［3～4］。對于這些問題，相比較于多數類，少數類樣本往往包含著重要的信息，且常常具有更高的錯判代價，因此我們更關注少數類樣本的分類準確性。比方說，信用卡欺詐檢測的案例，欺詐行為在全部交易記錄中往往占非常小的比例，將一個正常交易行為誤判成欺詐行為，也許會失去一個信用良好的客戶，帶來一定的損失。可是將一個欺詐行為歸類為了正常交易行為所帶來的損害則更為嚴重。

對于不平衡學習。其根本問題是數據分布不均衡導致很多傳統機器學習的分類算法性能大大減弱。因為大多數分類算法事先假設訓練集具有相等的誤分類代價或平衡的數據分布［5］，所以這些算法在面對相對復雜的不平衡數據集時便不能有效地反應出數據的分布特征。如此一來，當這些傳統分類算法在樣本不平衡的數據集上訓練時，經常會出現分類面偏倚的現象，使得最終無法獲得令人滿意的分類效果，甚至會出現模型完全失效的糟糕情況［6～7］。

不平衡學習因其重大研究意義而在機器學習和數據挖掘領域備受矚目，多個業內主流的期刊和會議都專門針對此問題舉辦過專刊或研討會［8］。例如 AAAI'2000［9］、ICML'2003［10］、ACM SIGKDD Exploration'2004［11］和 PAKDD'2009［12］。

2 基于高斯混合模型的下采樣

處理類不平衡問題的方法通常可以分為數據、算法和集成這三個層面，其中從數據層面的解決方法一般有上采樣、下采樣和混合采樣。而下采樣技術的關鍵就是如何通過減少多數類樣本使得兩類數據達到相對平衡狀態，并且保持多數類樣本的整體分布。概率論中的中心極限定理證明了大量相互獨立的隨機變量，其均值（或者和）的分布的極限是正態分布，即高斯分布。我們由高斯混合模型（Gaussian Mixture Model，GMM）的定義可知，它實質上就是單高斯分布模型的一種擴展，可以有效地近似模擬各種復雜的數據分布。基于以上思考，論文提出了一種基于高斯混合模型的下采樣算法（Gaussian Under-Sampling，GUS）。首先利用高斯混合模型對負類數據進行擬合，然后再依據每個子模型上數據的分布情況，即概率區間按比例進行下采樣。

2.1 高斯混合模型

高斯混合模型其實就是由K個單高斯模型組合而成的，這K個子模型就是混合模型的隱變量（Hidden Variable）。其概率分布密度函數為

其中，x表示服從GMM分布的隨機變量，K表示GMM中的子模型的個數，μk和∑k則分別表示第k個子模型的均值與方差，表示第k個子模型的概率密度函數，αk是觀測數據屬于第k個子模型的概率，即第k個子模型的權重，并且滿足以下條件:

高斯混合模型假定所有的樣本點都是由有限個單高斯模型生成的，對于此模型的求解就是對其概率密度函數的參數求解，通常我們利用最大期望算法（Expectation Maximization，EM）對高斯混合模型的參數進行求解。

2.2 決策樹與隨機森林

決策樹（decision tree）是一種基于樹的結構進行決策的分類方法，它的構建過程就是選擇特征和確定決策規則的過程［13］。

ID3，C4.5和CART算法都是經典的決策樹算法。

隨機森林（Random Forest，RF），簡單來說，就是建立很多決策樹，構建一個決策樹的“森林”，通過各個決策樹的投票來進行決策［14］。隨機森林算法的基本步驟為

1）通過自舉重采樣的方式從N個原始的樣本中有放回地隨機抽取N個樣本，從而產生多個樣本集；

2）利用每次重采樣產生的樣本集作為訓練樣本構建一棵決策樹。并且在構建決策樹的過程中先從該結點的候選特征中隨機選擇一個包含k個特征的子集，作為當前結點的備選特征，然后再從這些備選特征中選擇一個最優屬性用于劃分；

3）構建了指定數目的決策樹后，RF對這些決策樹的輸出進行匯總，得票最多的類就作為RF的輸出。

2.3 GUS算法

GUS算法的主要思想是利用高斯混合模型對負類數據進行擬合，得到多數類樣本對應的高斯混合模型，然后根據每個單高斯模型上數據的分布情況，按照概率區間內樣本的的比例進行下采樣，從而使得多數類樣本數與少數類樣本數達到相對平衡的狀態。

高斯混合模型能夠有效地描述數據的分布情況，但同時高斯混合模型對參數具有一定敏感性，例如高斯分量的個數。為了更好地觀察高斯分量的個數對描述數據分布的影響，我們選擇了常常用來做聚類分析的二維數據集TwoMoons來進行測試。實驗結果如圖1所示，可以發現高斯分量的個數選擇對數據的擬合是有一定影響。所以在我們正式利用高斯混合模型對多數類數據進行擬合之前，需要對數據有一定的了解。查詢數據集的來源和應用背景、了解數據的屬性特征以及利用相關算法進行參數尋優，都有利于我們對參數進行更好的選擇。目前，對于高斯分量個數確定的方法中最常用的兩種方法就是利用赤池信息準則（Akaike information criterion，AIC，又稱最小信息準則）和貝葉斯信息準則（Bayesian Information Criterion，BIC）來進行參數尋優。本次實驗中，我們采用了赤池信息準則來確定混合高斯模型中高斯分量的個數。

記原始訓練集S=S+∪S-，其中S+和S-分別表示少數類樣本集和多數類樣本集。

GUS算法的主要步驟為

第一步:置新的多數類樣本集Snew為空，并利用赤池信息準則AIC進行參數尋優，確定高斯分量的個數K。

圖1 不同高斯分量下的TwoMoons數據集的數據分布等高線圖，第一行從左到右高斯分量的個數分別為1、2、3，第二行從左到右高斯分量的個數分別為4、5、6

第二步:利用高斯混合模型對多數類S-進行擬合，建立一個高斯混合模型。

第三步:依照各個高斯分量中的數據分布以及每個高斯分量里概率區間中的數據分布情況，然后根據各個概率區間內的樣本所占比例進行隨機下采樣，得到第i個高斯分量上的采樣數據集Ci, i=1:K。

第四步:將從每個高斯分量中采樣獲得的樣本納入新的多數類樣本集合Snew。

第五步:輸出下采樣后新的訓練集S'=S+∪Snew。

2.4 評估指標

在機器學習的二分類問題中，通常將多數類記為負類（Negative），而將具有高識別重要性的少數類記為正類（Positive）。二分類問題的混淆矩陣（Confusionmatrix）如表1所示。

表1 混淆矩陣

從表1我們可以看出，TP和TN分別表示樣本本身就是正類/負類，然后被正確預測為正類/負類的樣本數，FP和FN則表示樣本實際標簽是負類/正類，但是卻被錯誤地預測為正類/負類的樣本數［15］。根據混淆矩陣的定義:

查全率:Recall=TP/（TP+FN）

查準率:Precision=TP/（TP+FP）

F-measure是查全率和查準率的調和均值，其定義如下:

其中，β是用于調節Recall和Precision的相對重要度的參數，通常取1，此時F-measure的實質是Recall和Precision的調和平均數，即有:

評估指標G-mean則是計算了正類和負類樣本分類準確度的幾何均值，其定義如下:

不平衡學習中另一個重要的評估指標就是馬氏 相 關 系 數（Matthew's correlation coefficient，MCC），其定義如下:

可以看出，以上幾個指標都是基于閾值的，所以我們還選取了另一種評估指標AUC（Area Under ROCCurve），即 ROC（Receiver Operating Characteristic Curve）曲線下方的面積。AUC值與閾值的選取無關，是一個衡量分類器的整體性能重要指標。

因為MCC綜合考慮了各方面的評估指數，可以作為分類模型總體性能的衡量標準。本文我們則是選擇MCC最大時的其他各項指標值作為實驗的評估結果。

3 實驗結果與分析

3.1 采樣前后的數據分布比較

統計學中，可以從數據分布的集中趨勢、離散程度以及形狀這三個方面對數據集的分布特征進行描述。

本文就從這三個方面分析利用高斯混合模型進行下采樣后樣本集的數據分布，分別選擇均值和方差作為描述指標，并繪制數據在采樣前后的分布形狀。與此同時利用高斯混合模型做聚類分析，并繪制聚類后的結果圖。為了方便我們觀察數據分布的形狀，選擇二維的數據集進行驗證。數據均值與方差的統計結果如表2所示，樣本集在采樣前后的數據分布的形狀如圖2、圖3、圖4和圖5所示。分析發現，兩組數據在采樣前后的均值和方差非常接近，并且采樣后數據集的分布形狀保持得很好。并且，我們針對三個高斯分布合成的數據在采樣前后分別進行了聚類分析，得到聚類的結果分別如圖6和圖7所示，從最后的聚類結果來看，采樣前后數據的聚類結果基本保持不變。所以，可以看出我們提出的GUS算法在減少負類樣本數目的同時也很好地保持了數據的整體分布。

表2 兩組數據集采樣前后均值與方差對比

圖2 TwoMooms數據集采樣前的數據分布圖

圖3 TwoMoons數據集采樣后的數據分布圖

圖4 三個高斯分布合成的數據集采樣前的數據分布圖

圖5 三個高斯分布合成的數據集采樣后的數據分布圖

圖6 三個高斯分布合成的數據集采樣前的聚類結果

圖7 三個高斯分布合成的數據集采樣后的聚類結果

3.2 UCI數據集上的結果

本次我們選取了6組具有不同應用背景的不平衡數據集來進行實驗。數據集的詳細信息如表3所示。

為了方便和文獻［16］中的其他方法進行實驗結果的比較，實驗選擇隨機森林作為分類器。與GUS算法進行比較的有:Random Forest（簡稱RF），表示的是對數據沒有采取任何重采樣技術的情況下直接使用隨機森林進行分類的結果，隨機下采樣（簡稱 Under）、BalanceCascade（簡稱 Cascade）和EasyEnsemble（簡稱Easy），這三種方法都是經典的下采樣方法。表4～表6詳細地描述了使用GUS方法與其他方法進行分類的結果。

表3 數據集信息

表4 GUS方法與其他方法在AUC值上的比較

表5 GUS方法與其他方法在F-measure值上的比較

表6 GUS方法與其他方法在G-mean值上的比較

從第一個性能評估指標AUC值上觀察，GUS方法在pima這組不平衡數據集上的AUC值高于其他方法。在剩下六組數據集上的值雖然不是最高的，但是結果相差不大，基本保持平均水平。

對于F-measure的考察，從表5可以明顯看出，GUS方法的結果在6組實驗數據上都是最優的，特別是在balance、mf-zernike和housing這三組數據上的值遠遠高于其他方法。說明GUS算法在處理不平衡數據的分類問題上的查全率和查準率都非常高。

從表6觀察G-mean值，不難發現除了在mf-zernike數據集上的結果略低于EasyEnsemble方法，在剩下的5組不平衡數據集上的結果都高于別的方法。

通過與其他方法在三個評估指標上的比較，可以看出GUS算法在F-measure和G-mean上的值普遍高于其他方法，在AUC上的值也不低。整體上而言，GUS算法在研究不平衡學習的問題上取得了可觀的結果。

4 結語

對于二分類不平衡學習，本文提出了一種新的下采樣算法，通過高斯混合模型對多數類樣本進行擬合，得到多數類樣本的數據分布模型，利用各個子模型中數據的概率分布區間，按照樣本所占比例在每個區間內進行隨機下采樣，從而獲得新的多數類樣本集，以達到平衡整個數據集分布的目的。通過在6組具有不同應用背景的不平衡數據集上進行實驗，并與其他幾種常用的方法進行比較，以AUC、F-measure和G-mean值作為評價指標。從實驗結果上看，GUS算法取得了可觀的結果，說明了GUS算法在處理不平衡數據問題上具有很大的優勢。