張?zhí)煲?丁立新

(武漢大學計算機學院 湖北 武漢 430072)

0 引 言

現(xiàn)實中的數(shù)據(jù)集通常是不平衡的，不平衡數(shù)據(jù)集中的實例分布十分不均衡。當基于不平衡數(shù)據(jù)集構(gòu)造分類器時，分類器的預測結(jié)果可能會偏向多數(shù)類，這些分類器很容易將少數(shù)樣本誤分類為多數(shù)類。但是有時少數(shù)類樣本才是問題的主要研究對象，在這種情況下，少數(shù)類樣本的錯誤分類可能會帶來嚴重的問題和風險。例如，在醫(yī)學數(shù)據(jù)集中，健康人的樣本通常遠遠多于患者樣本，如果基于此數(shù)據(jù)集構(gòu)建分類器，那么輸入一個測試樣本，分類器大概率會將輸入樣本預測為健康人，但是將患者誤分類為健康人的風險遠高于將健康人誤分類為患者的風險。數(shù)據(jù)失衡不僅出現(xiàn)在醫(yī)學檢測中，而且也出現(xiàn)在許多其他實際應(yīng)用中，例如海上雷達圖像中油污泄露區(qū)域檢測[1]、電信欺詐檢測[2]等。

研究者們已經(jīng)開發(fā)出了許多方法來消除數(shù)據(jù)不平衡所帶來的影響，這些方法大都在算法層面或數(shù)據(jù)層面來解決不平衡問題。算法層面的方法主要包括集成學習法和成本敏感型學習法。傳統(tǒng)分類算法的目標是平衡的數(shù)據(jù)集，因此數(shù)據(jù)集中的所有樣本都具有相同的重要性，并且將A誤分類為B和將B誤分類為A的代價是相同的。但是在不平衡的數(shù)據(jù)集中，對于少數(shù)類而言，擁有與多數(shù)類樣本相等的誤分類成本并不公平。因為在一些問題中，少數(shù)類相比于其他類具有更大的研究價值。成本敏感型學習方法則修改了各類錯誤的懲罰因子，分類器將少數(shù)類樣本誤分類為多數(shù)類樣本會受到更大的懲罰，在迭代過程中會逐漸減少這類錯誤，因此可以弱化或消除分類器的錯誤偏差。AdaCost[3]是一種典型的成本敏感型學習方法。AdaCost在迭代學習過程中為少數(shù)樣本的錯誤分類提供了更大的懲罰因素，這使得少數(shù)樣本在總體成本函數(shù)中占主導地位。

集成學習方法從數(shù)據(jù)集中生成多個獨立的預測模型作為弱分類器，然后將這些模型組合為強分類器。當每個弱分類器具有相對較低的錯誤率時，組合的強分類器將具有比任何弱分類器低得多的錯誤率。研究人員已經(jīng)開發(fā)了基于提升算法的改進方法來解決數(shù)據(jù)不平衡問題，例如文獻[4]提出少數(shù)類合成提升算法(SMOTEBoost)、文獻[5]提出隨機欠采樣提升算法(RUSBoost)、文獻[6]提出干擾修正提升算法(PCBoost)、文獻[7]提出基于模型的樣本合成提升算法(MBSBoost)、文獻[8]提出基于過采樣的不平衡數(shù)據(jù)集成分類算法(SDPDBoost)。SMOTEBoost使用SMOTE進行樣本合成，并且把新樣本加入到數(shù)據(jù)集中。這些新樣本可以給弱分類器帶來更多有關(guān)少數(shù)群體分類的信息，經(jīng)過多次迭代，最終的強分類器可以得到針對少數(shù)類樣本分類的提升。RUSBoost則采用欠采樣方法，隨機刪除一些多數(shù)類樣本，然后使用處理后的數(shù)據(jù)構(gòu)造弱分類器。PCBoost算法首先對少數(shù)類進行隨機過采樣，然后使用信息增益率構(gòu)造弱分類器。錯誤分類的過采樣樣本在最后階段會被刪除。除了基于提升算法的方法，還有其他的方法，如文獻[9]提出的概率閾值袋裝法，利用袋裝法首先獲得校準良好的后驗估計，然后根據(jù)性能指標選取適當?shù)拈撝?，以使其最大化?/p>

數(shù)據(jù)層面的方法采用的主要策略是合成新樣本和重采樣。這些方法會重塑數(shù)據(jù)集，因此可以通過重塑每個類別中的樣本數(shù)來消除數(shù)據(jù)不平衡。主要有三種重采樣方式：多數(shù)類樣本欠采樣、少數(shù)類樣本過采樣和混合方法。欠采樣方法會丟棄多數(shù)類中的某些內(nèi)部樣本，或?qū)⒛承颖咎鎿Q為合成樣本，然后通過某種標準選擇丟棄的樣本或替換后的樣本，以便剩余的多數(shù)樣本可以保留盡可能多的原始數(shù)據(jù)信息。欠采樣后，兩種類型的采樣數(shù)近似相等，數(shù)據(jù)集達到平衡。過采樣方法通過生成新的少數(shù)類樣本來消除偏斜分布的危害，生成的新樣本加入數(shù)據(jù)集后，應(yīng)使數(shù)據(jù)集達到平衡，并且基于這些數(shù)據(jù)集訓練的分類器可以是無偏的?；旌戏椒ㄊ巧鲜龇椒ǖ幕旌?，它同時使用欠采樣和過采樣來使數(shù)據(jù)集平衡，經(jīng)由數(shù)據(jù)層面的方法處理后的數(shù)據(jù)集是平衡的，因此基本分類器可以發(fā)揮其原始作用。

在以上不同類型的方法中，過采樣是研究人員在解決數(shù)據(jù)不平衡問題中的一種流行策略[10]，而使用較多的方法之一是少數(shù)類樣本合成過采樣技術(shù)(SMOTE)算法[11]。該方法根據(jù)少數(shù)樣本的k個最近鄰樣本生成新的合成樣本，合成樣本是端點為兩個最近鄰少數(shù)類樣本對應(yīng)的線段上的隨機點。由于缺乏多樣性，已經(jīng)有許多其他改進的算法被提出，例如文獻[12]提出的邊界線少數(shù)類樣本合成技術(shù)(Borderline SMOTE)、文獻[13]提出的自適應(yīng)綜合過采樣(ADASYN)、文獻[14]提出的基于類聚集程度的少數(shù)類樣本合成(DB-SMOTE)、文獻[15]提出的基于周圍鄰域的SMOTE和文獻[16]提出的隨機游走過采樣(RWO)。針對多分類不平衡問題，文獻[17]提出了基于馬氏距離的適應(yīng)性過采樣方法(AMDO)。為了使合成的樣本更具多樣性，本文提出了一種改進的合成技術(shù)。與其選擇兩個點來構(gòu)建一條線，不如在合成過程中涉及更多樣本來構(gòu)建平面或空間。除了過采樣策略，還有許多欠采樣的方法被用來解決不平衡問題，如文獻[18]提出的去噪欠采樣(Noise-filtered Under-sampling Scheme)。

1 背景知識

1.1 少數(shù)類樣本合成過采樣技術(shù)

解決數(shù)據(jù)不平衡問題的一種典型的過采樣方法是SMOTE算法，該方法旨在彌補少數(shù)類隨機過采樣的缺陷。對少數(shù)類樣本進行隨機過采樣不會使得少數(shù)類樣本更具識別性，因為過采樣過程其實是對樣本進行復制，這種復制會使樣本的決策判定越來越嚴格，越來越具體，導致分類過擬合。例如，如果原始決策為[0,10]，則在隨機過采樣后，由于復制了多個少數(shù)樣本，這使分類器確信少數(shù)類在較窄的范圍內(nèi)，分類器將給出更具體的決策區(qū)域，例如[3,6]。SMOTE算法則采用了合成新樣本的方法來增加少數(shù)類樣本的數(shù)量，其基本步驟如下：

Step1從少數(shù)類樣本A的K最近鄰少數(shù)類中隨機選取一個B，A和B的樣本特征的差向量為(B-A)。

Step2從區(qū)間(0，1)中隨機選取一個實數(shù)i作為權(quán)值。將權(quán)值i與差向量相乘得到i(B-A)。

Step3把Step 2的結(jié)果與樣本A的特征向量相加得到合成樣本A+i(B-A)。

該技術(shù)通過生成人工樣本來拓寬決策區(qū)域，因為添加到數(shù)據(jù)集中的樣本位于原始樣本的附近的合成樣本，而不是樣本本身。與帶有替換的隨機過采樣相比，決策區(qū)域更為通用。實驗表明，SMOTE算法可以提高少數(shù)類的分類器準確性，并且SMOTE算法和欠采樣的組合比單純使用欠采樣效果更好。SMOTE算法在低維不平衡數(shù)據(jù)集中運行良好，但在一些實驗中能觀察到，SMOTE在高維上的性能不如在低維上的性能[19]。SMOTE包含一個參數(shù)k，代表了取最近鄰的個數(shù)，文獻[20]介紹了如何選取合適的k值。

1.2 已有的SMOTE算法改進

盡管SMOTE算法是解決數(shù)據(jù)不平衡問題的有效工具，但它仍有一些局限性。其沒有考慮多數(shù)類別即可生成合成樣本，由于新樣本的生成過程是隨機的，因此新生成的樣本可能會出現(xiàn)在多數(shù)類的決策區(qū)域中。隨機生成的結(jié)果是兩種類別的決策區(qū)域的重疊的概率會增加，這使得兩個類別更難以區(qū)分[11]。前人已經(jīng)提出了SMOTE算法的一些改進版本，大多數(shù)的改進算法都在尋找一個合適的生成區(qū)域生成新樣本并盡量避免重疊的增大。文獻[12]提出的Borderline SMOTE將少數(shù)樣本劃分為噪聲點、危險點和安全點，首先刪除噪聲點，僅使用危險點進行樣本合成。Borderline SMOTE在生成過程中不僅使用少數(shù)樣本，還使用多數(shù)樣本，通過此方法可以加強類之間的邊界。自適應(yīng)SMOTE考慮了最近鄰居和被選取的少數(shù)樣本的距離[13]，設(shè)置了最近鄰距離的閾值，避免了樣本到合成樣本之間的距離過長，并根據(jù)不同樣本集的內(nèi)部分布特征調(diào)整閾值?；谥車徲虻腟MOTE算法使用了最近鄰的不同定義[14]，該方法使用了最近的質(zhì)心鄰域和Graph鄰域，以確保最近的鄰域距離不太遠?；诰植烤€性嵌入的SMOTE算法將局部線性嵌入算法部署到少數(shù)樣本[15]。隨機游走過采樣(RWO)引入了基于中心極限定理的過采樣方法[16]，它以新生成的少數(shù)樣本均值遵循原始分布的方式創(chuàng)建樣本。當使用帶有SVM的SMOTE算法作為分類器時，合成采樣方法會影響SVM的內(nèi)核歸納特征空間的性能，基于內(nèi)核的SMOTE算法直接在SVM的特征空間中生成合成樣本[23]。文獻[24]結(jié)合了K-means聚類和SMOTE算法來創(chuàng)建新樣本，避免了噪聲的產(chǎn)生，有效地克服了類之間和類內(nèi)部的不平衡。

2 改進算法

2.1 SMOTE算法的局限性

SMOTE算法首先找出每個少數(shù)類的k個最近鄰樣本，然后隨機選擇一個最近鄰樣本和一個實數(shù)來合成新樣本。根據(jù)算法的描述，對于單個合成樣本，只有兩個真實的少數(shù)樣本參與合成，并且合成樣本選自兩個真實樣本所對應(yīng)的線段上。換言之，合成樣本的特征向量是兩個真實樣本特征向量的線性組合。整個少數(shù)類中新樣本的潛在出現(xiàn)范圍是每個少數(shù)類樣本對之間的一組線段上。在低維特征空間中，這種方法足以描述潛在的少數(shù)類樣本分布特點。但當特征空間維度較高時，線性關(guān)系太單調(diào)以致不足以描述潛在的少數(shù)樣本的分布。因為在低維度空間中可能的真實樣本落在一條線段上的概率較高，但是隨著維度的增大，潛在的真實樣本落入在兩個樣本之間線段上的可能性則會越來越小。

另外，原有的合成策略不足以改變某些分類器的偏差。例如，支持向量機分類器使用支持向量來找出分隔不同類的邊界，支持向量是靠近邊界的樣本向量，是分類算法的核心，如果將SVM應(yīng)用于通過SMOTE算法進行過采樣的數(shù)據(jù)集，參與單個樣本合成的真實樣本存在三種可能性，即兩個都是支持向量、兩個都不是支持向量、一個是支持向量且一個是非支持向量，后兩種可能性的合成樣本幾乎不能成為支持向量，因此新樣本對邊界的計算沒有幫助。對于第一種情況，新樣本不會顯著改變原始邊界，因為它們位于支持向量的直線上，并且這些直線與邊界線段趨近平行?？傮w而言，SMOTE算法在高維度上缺乏多樣性，并且可能不會大大改變某些分類器的偏差。

2.2 改進SMOTE算法設(shè)計

基于以上分析，SMOTE算法的缺點實際上有著相同的原因，即合成方法太單調(diào)，并且線段關(guān)系太簡單以致無法適應(yīng)潛在的少數(shù)類特征。為合成樣本添加一些垂直偏移可以增加多樣性，一種有效的方法是在生成過程中涉及更多的少數(shù)類樣本。

因此，本文提出了一種改進的SMOTE算法，與原始的SMOTE算法相比，本文使用D個少數(shù)類樣本創(chuàng)建了人工樣本，這里D是特征空間的維數(shù)。首先，對于所有少數(shù)樣本，計算它們的k個相同類別的最近鄰樣本集，然后對于每個少數(shù)樣本，選擇D個鄰居和0到1/D的實數(shù)以創(chuàng)建新樣本。該方法將合成樣本空間從一維空間擴展到D維空間，從而使新樣本更加多樣化。改進的SMOTE算法描述如算法1所示。

算法1改進的SMOTE算法

輸入：訓練集中的正類樣本集合(少數(shù)類集合)P={P1,P2,…,Pmin};正類樣本的個數(shù)min;每一個正類需合成樣本的數(shù)量N;近鄰個數(shù)k;參與合成的近鄰個數(shù)D(D

輸出:一個合成樣本集合Syntheticsamples。

使用少數(shù)類集合P構(gòu)建Kd樹；

fori=1 tomindo

找出Pi的k近鄰集合：

knni={knni1,knni2,…,knnik}；

fora=1 toNdo

從knni中隨機選擇D個緊鄰樣本：

da={da1,da2,…,daD}；

計算被選取的近鄰與樣本Pa的向量差：

計算合成樣本的向量：

將生成的新樣本計入集合；

Endfor

Endfor

這里，失衡率是多數(shù)類樣本個數(shù)與少數(shù)類樣本個數(shù)的比值，N=INT(maj/min-1)，maj是多數(shù)樣本的數(shù)量。

上述的改進算法中有兩個參數(shù)k和D，其中k表示最近鄰樣本的數(shù)量，D表示生成新樣本過程中涉及的樣本數(shù)量。原始SMOTE算法始終將參數(shù)D設(shè)置為1，這使得樣本出現(xiàn)的范圍在真實的少數(shù)類樣本的線段上。如果將D設(shè)置為2，則合成樣本將在平面上而不是在線段上。如果將D設(shè)置為特征向量的大小，則合成樣本的可能范圍將擴展到整個特征空間。在一些特殊情況下，合成樣本的可能范圍會小于預期，如選取的最近鄰中存在某個樣本是其他樣本的線性組合，此時依然能夠生成足夠多樣的合成樣本。

新算法會輸出min×D個合成樣本，這些樣本分布在整個特征空間而不是線段中。因此，本文改進的SMOTE算法的結(jié)果會更加多樣化，并且能夠表示潛在分布特征。與RWO算法相比，本文改進的SMOTE算法生成的人工樣本具有更多的局部分布特征。

3 實 驗

準確率是衡量分類器性能的通用指標，但是當數(shù)據(jù)集不平衡時，準確率并不能很好地體現(xiàn)分類器對于少數(shù)類樣本的分類性能。由于數(shù)據(jù)集中包含大量多數(shù)類樣本，因此多數(shù)類的準確率主導了整體準確率。為了評估分類器的整體性能，研究者們使用了許多其他指標，例如AUC和F-measure。AUC是ROC(接收器工作特性曲線)曲線下的面積，ROC曲線是表示在不同分類標準下真陽率和假陽率變化的曲線。根據(jù)不同的分類器，標準也有所不同。由于ROC曲線下的面積是不同標準的積分結(jié)果，針對分類器的整體度量，因此該度量僅與分類器和數(shù)據(jù)集有關(guān)。ROC曲線如圖1所示，其中：曲線最左邊點的坐標為(0，0)，最右邊點的坐標為(1，1)。AUC則是ROC曲線下的的面積，即ROC在[0,1]區(qū)間的定積分。

圖1 ROC曲線示例

F-measure是精度和召回率的加權(quán)諧波平均值。由于多數(shù)類的權(quán)重更多地取決于準確性，因此手動為少數(shù)類設(shè)置適當?shù)臋?quán)重可以對分類器進行公平的評估。F測度的公式為：

(1)

式中：recall為召回率，recall=TP/(TP+FN)；precision為準確率，precision=TP/(TP+FP)；β為諧波系數(shù)，設(shè)置β=1；F-measure為F1-measure，本文實驗中也使用了F1-measure作為衡量指標之一。實驗中選擇AUC、少數(shù)類召回率、少數(shù)類準確率及F1量度作為度量標準，因為這些衡量指標更多地集中于分類器的整體表現(xiàn)。

本文使用的數(shù)據(jù)集來自UCI機器學習數(shù)據(jù)庫。數(shù)據(jù)集包括Adults、Forest、Phoneme和Pima。在這些數(shù)據(jù)集中Adults、Phoneme和Pima是二分類集，F(xiàn)orest是多分類集。由于Forest數(shù)據(jù)集具有兩個以上的類別，所以手動選擇一個類作為少數(shù)類，并將其余的類合并為一個類作為多數(shù)類。某些數(shù)據(jù)集包含名義屬性，SMOTE算法是為數(shù)字屬性設(shè)計的，不能用于名詞性屬性。為了方便起見，將這些名詞性屬性刪除。改進算法中的參數(shù)D則會根據(jù)數(shù)據(jù)集的屬性數(shù)有所改變。Adult、Forest、Phoneme和Pima的參數(shù)D分別為14、12、5和8。表1展示了每個數(shù)據(jù)集的詳細信息。

表1 數(shù)據(jù)集信息

實驗中應(yīng)用了不同的機器學習算法作為過采樣數(shù)據(jù)集的分類器，包括KNN、CART、樸素貝葉斯分類器(Bayes)和支持向量機(SVM)。這些分類器是基于scikit-learn(https://scikit-learn.org/)構(gòu)建。

實驗測試了三種過采樣方法，分別為SMOTE算法、本文改進的SMOTE算法和RWO算法。SMOTE算法是本文中改進算法的原算法。RWO算法是一種基于中心極限定理的過采樣算法，在合成新樣本的過程中首先會計算出所有少數(shù)類樣本的正態(tài)分布，再根據(jù)這個分布產(chǎn)生新樣本。所以新樣本是根據(jù)所有少數(shù)類樣本產(chǎn)生的，并且在所有屬性上都具有多樣性。本文算法是針對原算法在合成樣本多樣性上的改進，因此選用SMOTE算法和RWO算法作為對照比較。由于所有這些方法均包含隨機因素，因此單次實驗無法有效反映算法的性能。針對每種過采樣方法和分類器進行了30次重復實驗，最終結(jié)果是所有結(jié)果的平均值。每種過采樣算法和分類算法的實驗結(jié)果如表3-表5所示。4個指標通過十折交叉驗證進行評估，每個指標的評估將產(chǎn)生10個實驗結(jié)果，并且表中顯示的結(jié)果是所有驗證結(jié)果的均值。

表2 Adult數(shù)據(jù)集實驗結(jié)果

表3 Forest數(shù)據(jù)集實驗結(jié)果

表4 Phoneme數(shù)據(jù)集實驗結(jié)果

表5 Pima數(shù)據(jù)集實驗結(jié)果

續(xù)表5

為了更加直觀地比較三種方法的綜合性能，本文特別比較了三種方法在不同數(shù)據(jù)集和分類算法下的ROC-AUC指數(shù)，如圖2-圖5所示。

圖2 Adult數(shù)據(jù)集ROC-AUC比較

圖3 Forest數(shù)據(jù)集ROC-AUC比較

圖4 Phoneme數(shù)據(jù)集ROC-AUC比較

圖5 Pima數(shù)據(jù)集ROC-AUC比較

根據(jù)Adult數(shù)據(jù)集的實驗結(jié)果，本文方法具有比原始SMOTE算法更好的總體性能，尤其是在使用SVM分類器的Forest和Pima數(shù)據(jù)集的結(jié)果上，本文方法在這些數(shù)據(jù)集上實現(xiàn)了更高的ROC-AUC。至于其他指標和測試，結(jié)果提升了1%～2%。當使用CART分類器對過采樣的數(shù)據(jù)集進行分類時，SMOTE算法的性能要優(yōu)于本文方法，SMOTE算法在召回率、F1和ROC-AUC方面表現(xiàn)更好。在高失衡率數(shù)據(jù)集中，本文方法的性能不如RWO算法。但是在低失衡率數(shù)據(jù)集(如Pima)中，本文方法具有與RWO算法類似的結(jié)果。綜合結(jié)果表明本文方法優(yōu)于其他兩種方法，特別是在使用SVM時，而RWO算法在使用樸素貝葉斯分類器時具有更好表現(xiàn)。

4 結(jié) 語

數(shù)據(jù)不平衡會影響基本分類器的分類結(jié)果，使它們很難對少數(shù)類進行公平的分類。為了解決這個問題，SMOTE算法被提出以通過生成少數(shù)樣本的合成來達到平衡。本文提出了一種SMOTE方法的改進，使算法產(chǎn)生的合成樣本更具多樣性。實驗表明，該方法在召回率、F1和ROC-AUC方面比原始SMOTE算法具有更好的性能，并且在使用SVM分類器的低失衡率數(shù)據(jù)集上特別有效。本文算法比原始SMOTE算法在綜合性能上也有一定的提升，在使用不同的分類算法時，本文方法和RWO算法也會有不同的表現(xiàn)。在使用樸素貝葉斯分類器時，RWO算法優(yōu)于本文方法；使用支持向量機時，本文方法則會有更好的綜合性能。盡管在整體實驗結(jié)果上，本文方法優(yōu)于SMOTE算法，但是當數(shù)據(jù)集的不平衡率較高時，RWO算法會比本文方法更好。因此，當數(shù)據(jù)集高度不平衡時，還需要探索更有效的改進策略。

本文方法比原始SMOTE算法多一個設(shè)定參數(shù)。對于不同的數(shù)據(jù)集，最佳參數(shù)是不同的，如何設(shè)置適當?shù)膮?shù)是有待解決的問題。未來可嘗試將其他的一些改進版本的SMOTE上使用的策略移植到本文方法上，多種策略融合或許是處理非平衡數(shù)據(jù)集分類問題的可選途徑。