宋艷，白治江

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

不平衡數(shù)據(jù)集是指數(shù)據(jù)集中某類別樣本的數(shù)量在整個數(shù)據(jù)集中占主導(dǎo)優(yōu)勢。一般把數(shù)據(jù)集中數(shù)量較多的類標(biāo)記為多數(shù)類或負類，數(shù)量處于劣勢的類標(biāo)記為少數(shù)類或正類。這類數(shù)據(jù)在現(xiàn)實生活中普遍存在，如網(wǎng)站中用戶搜索行為，客戶的個人信譽評估[1]。然而使用傳統(tǒng)的支持向量機[2]已不足以在龐大的數(shù)據(jù)集中識別出正類樣本。因此，如何在信息時代正確地區(qū)分和預(yù)測正類樣本，成為眾多學(xué)者的研究重點。

目前，多數(shù)學(xué)者主要從算法和數(shù)據(jù)兩個層面對不平衡數(shù)據(jù)進行處理。算法層面一般通過改進分類算法提高正類樣本的識別精度，如代價敏感法[3]、集成學(xué)習(xí)[4]、主動學(xué)習(xí)等。算法改進的辦法一般只適用于某些特定分布特征的數(shù)據(jù)集，因為數(shù)據(jù)集的分布仍然保持原樣。數(shù)據(jù)層面主要以欠采樣（Under-Sampling）[5]與過采樣（Over-Sampling）[6]為原型，使原始數(shù)據(jù)集中兩類樣本數(shù)量上相近。欠采樣通過隨機刪減負類樣本使兩類樣本的數(shù)量相同，卻有可能將帶有重要信息的負類樣本舍棄，從而使分類器的學(xué)習(xí)能力下降；過采樣則以隨機復(fù)制正類樣本的方式平衡兩類樣本，但新增的樣本數(shù)據(jù)不僅需額外的計算代價并且會造成過度擬合。2002年，Chawla等人提出SMOTE算法[7]，極大地改善了過學(xué)習(xí)問題，但該算法新增樣本時不加區(qū)分地在正類樣本間線性插入新樣本，限制了新增樣本的生成位置，忽略了靠近分類邊界附近的樣本才影響分類邊界的位置。

鑒于SMOTE算法插值的局限性，眾多學(xué)者在此基礎(chǔ)上提出了改善策略。Han等人提出了Borderline-SMOTE方法[8]，其基本思想是在正類數(shù)據(jù)集的邊界樣本之間線性插值，使得平衡后的數(shù)據(jù)中更多的樣本出現(xiàn)在類邊界附近，致使分類邊界模糊。文獻[9]在正類樣本及其最近鄰正類樣本構(gòu)成的n維球體內(nèi)隨機插值，擴大了新樣本生成的區(qū)域，致使數(shù)據(jù)集邊界附近聚集過多新樣本。

基于上述分析,本文提出一種結(jié)合鄰域樣本分布特征的改進型SMOTE算法（簡稱E_SMOTE算法）,其要點是探察近鄰的近鄰，即用SMOTE算法插值時充分利用K近鄰候選點的M近鄰樣本分布特征,實現(xiàn)對新樣本分布區(qū)域的控制，克服新樣本引起的邊界模糊問題。通過實驗表明，與其他相關(guān)算法對比，本文算法確實提升了不平衡數(shù)據(jù)集的整體分類準(zhǔn)確性。

1 相關(guān)算法簡介

1.1 SMOTE算法

SMOTE是一種過采樣方法。具體操作如下：首先，根據(jù)不平衡度設(shè)置采樣倍率N；接著，對數(shù)據(jù)集的每個正類樣本x計算其k個同類最近鄰樣本，并在這k個樣本中隨機選擇N個，記為y1y2...yN，按公式（1）生成N個新樣本；最后，把每個正類樣本新增的N個樣本加入原始數(shù)據(jù)集中，構(gòu)成新的樣本數(shù)據(jù)集。

其中rand是（0,1）內(nèi)一個隨機數(shù)，NewMinority代表新合成的樣本。

1.2 支持向量機

支持向量機（Support Vector Machine,SVM）是Vap?ink等人提出的以統(tǒng)計學(xué)習(xí)理論原理為基礎(chǔ)的機器學(xué)習(xí)方法。在解決分類問題、非線性和高維模式識別中展現(xiàn)出獨特的優(yōu)勢，同時也具備抑制局部極值和過學(xué)習(xí)的特性，從而受到廣泛的關(guān)注。傳統(tǒng)的SVM分類器在處理樣本數(shù)量基本相同、分布均勻的數(shù)據(jù)集時，表現(xiàn)出極優(yōu)分類結(jié)果。然而實際應(yīng)用中更可能面向不平衡數(shù)據(jù)的分類問題，這使得SVM分類結(jié)果并不理想，其結(jié)果更可能偏向負類樣本，使得正類樣本分類精度下降。

1.3 NCL（Neighborhood Cleaning Rule）

NCL基本原理：對訓(xùn)練集中的每一個樣本x，計算x的3個最近鄰樣本。若x是正類樣本，且其3個最近鄰樣本中存在2或3個負類樣本，則刪除這些負類樣本，如圖1（a）所示；若x是負類樣本，且其3個最近鄰樣本中存在2或3個正類樣本，則刪除x。如圖1（b）所示。

圖1 NCL原理

（a）正類樣本x的3個近鄰中，有x1和x2兩個負類樣本，所以刪除x1和x2。（b）負類樣本x的3個近鄰樣本，有x2和x3兩個正類樣本，所以刪除x。

1.4 SMOTE_NCL算法

SMOTE_NCL方法先使用SMOTE對數(shù)據(jù)集過采樣處理，然后使用NCL方法對訓(xùn)練集進行欠采樣處理。該方法的缺點是當(dāng)NCL清洗了一定數(shù)量的負類樣本后，可能導(dǎo)致兩類樣本數(shù)量再度失衡。

2 E_SMOTE算法

靠近邊界附近的樣本帶有重要信息，且決定著決策界面的位置，尤其是正類樣本稀少且寶貴。E_SMOTE算法正是通過考察正類樣本的擴展近鄰，既突出了邊界樣本的重要性，又抑制了噪聲點的干擾。為了便于描述，定義如下概念：

根據(jù)正類樣本近鄰的分布特征，把正類樣本細分[10]為安全集和非安全集兩類，具體定義如下：

定義1（安全集）S1=｛x|x的k近鄰樣本全部是正類樣本｝。

定義2（非安全集）S2=｛x|x的k近鄰樣本不全是正類樣本｝。

E_SMOTE算法基本思想如下：SMOTE算法對非安全集中每一個樣本x與其正類近鄰樣本xi合成新樣本時，如果 xi的 M個最近鄰樣本存在ω（M/2≤ω≤M）個負類樣本，則不做任何處理，否則在x和xi之間插入一個新樣本，重復(fù)這一過程直到非安全集中所有樣本處理完畢。該算法中M2向上取整。該線性插值過程如圖2所示，正類樣本點x屬于非安全集，假設(shè)采樣倍率N=2。

圖2 非安全集插樣示例

圖2表示，從x的同類最近鄰樣本中隨機選擇2個樣本點，這里選擇x1和x2；x1的3個最鄰近樣本存在2個負類樣本點（x11和x12），則x與x1之間不合成新樣本；而x2的3個近鄰樣本全部為正類樣本，則在x與x2之間根據(jù)SMOTE算法合成一個新樣本。

E_SMOTE算法的操作步驟如下：

①設(shè)置采樣倍率N。

②根據(jù)正類樣本的k近鄰分布，把正類樣本分為安全集S1和非安全集S2。

③對S1直接應(yīng)用SMOTE算法插入新樣本。

④對S2在使用SMOTE算法合成新樣本前考慮擴展近鄰的分布特征，符合條件的才插入新樣本。

⑤用平衡后的數(shù)據(jù)集訓(xùn)練SVM分類器。

3 實驗設(shè)計和結(jié)果分析

3.1 數(shù)據(jù)集及評價標(biāo)準(zhǔn)

本文選取UCI庫的6種數(shù)據(jù)集完成實驗，數(shù)據(jù)集具體信息如表1所示。對多類別數(shù)據(jù)集，選擇其中樣本數(shù)目較少的一類作為正類樣本，其他類別樣本的集合作為負類樣本。例如，Wine數(shù)據(jù)集共有3個類別，本實驗把類別1標(biāo)記為少數(shù)類，其余2類合在一起作為負類。

評估標(biāo)準(zhǔn)是衡量分類器性能的準(zhǔn)則。為了客觀、公正地評價面向不平衡數(shù)據(jù)集的SVM分類器性能，結(jié)合實際需求，本文采用G-mean和F-value作為評價標(biāo)準(zhǔn)。

本文分類器性能的評價參數(shù)依據(jù)表2所示的混淆矩陣。

表1 數(shù)據(jù)集描述

表2 混淆矩陣

利用混淆矩陣，可得：

F-value標(biāo)準(zhǔn)是正類樣本的召回率（Recall）和準(zhǔn)確率（Precision）的調(diào)和值，其值靠近Recall和Precision中的較小者。只有當(dāng)兩者均較大時，F(xiàn)-value值才會變大。F-value計算公式如公式（3）所示：

G-mean是正、負類樣本的召回率的幾何均值。當(dāng)兩類的分類精度均較高時，G-mean的值才會增大。因此，采用F-value和G-mean作為衡量不平衡數(shù)據(jù)集的整體分類指標(biāo)是合理的。G-mean計算公式如公式（4）所示：

3.2 實驗數(shù)據(jù)分析

本文實驗在MATLAB R2012a平臺上運行。分類器是核函數(shù)為徑向基函數(shù)（Radial Basis Function，RBF）的標(biāo)準(zhǔn)SVM。訓(xùn)練分類器之前，對6個數(shù)據(jù)集分別做如下四種平衡處理進行實驗對比：①保持原樣，不做平衡處理；②用SMOTE算法過采樣；③用SMOTE_NCL算法過采樣；④用E_SMOTE算法過采樣。全部實驗對每個數(shù)據(jù)集均采用2次5折交叉驗證法，取10次分類結(jié)果的均值作為最終的分類結(jié)果，實驗結(jié)果如表3-表8所示。

實驗中SMOTE和E_SMOTE算法的近鄰參數(shù)K都設(shè)置為5，并且E_SMOTE的擴展近鄰參數(shù)M分別設(shè)置為3,4,5以便對比實驗效果。NCL數(shù)據(jù)清洗算法中近鄰參數(shù)C取3。

表3 Blood的分類情況

表4 Haberman的分類情況

表5 Diabetes的分類情況

表6 Wine的分類情況

表7 Breast的分類情況

表8 Balance的分類情況

由表3-表8可知，相比在原始數(shù)據(jù)集上直接訓(xùn)練SVM分類器，使用SMOTE、SMOTE_NCL和E_SMOTE算法對不平衡數(shù)據(jù)處理后提升了分類器的F-value和G-mean值。原因是對原始數(shù)據(jù)集采用SMOTE、SMOTE_NCL和E_SMOTE算法處理后，正負類樣本基本達到平衡，因此絕大部分?jǐn)?shù)據(jù)集的正類樣本的識別率提升了，即 Acc+顯著增大。在 6種數(shù)據(jù)集上SMOTE_NCL較SMOTE取得更高的 Acc+值，但同時Acc-的值卻有不同程度的下降，致使SMOTE_NCL的F-value和G-mean值要么沒有顯著提高，要么略有下降，原因是在SMOTE_NCL方法中，NCL作為一種清洗式的欠采樣方法，它只按照特定的近鄰規(guī)則簡單地刪除負類樣本，使得帶有重要信息的負類樣本也可能被刪除，降低了負類樣本訓(xùn)練分類器的能力。

整體上，SMOTE_NCL方法確實提升了數(shù)據(jù)集正類樣本的召回率，然而分類器的總體性能未顯著提高。當(dāng)然也有例外，比如Wine數(shù)據(jù)集使用SMOTE_NCL處理后，該算法較其他算法取得更高的F-value和G-mean值，說明NCL算法并無普遍適用性，只能在具有特定分布特征的數(shù)據(jù)集上才能體現(xiàn)其優(yōu)勢。由表3-表5可知，E_SMOTE算法比SMOTE算法獲得更高的F-value和G-mean值，這是因為E_SMOTE算法插值新樣本時綜合了擴展近鄰的分布信息，不僅能有效抑制噪聲點的影響，同時也克服了類邊界模糊的問題。而由表6-表8可以觀察到SMOTE和E_SMOTE算法整體性能基本一樣或略小，通過多次交叉驗證試驗結(jié)果對比發(fā)現(xiàn)，本文并沒有對相似分布特征的樣本點采取抉擇策略，而是優(yōu)先選擇第一個滿足條件的近鄰樣本點，這種隨機選擇結(jié)果的差異性在表6-表8上表現(xiàn)較為明顯，導(dǎo)致整體分類精度的平均值降低。最后，6種數(shù)據(jù)集上的E_SMOTE算法比SMOTE_NCL算法的F-value和G-mean值均有不同程度的提高（除表6和表8中E_SMOTE的整體性能有微小下降）。此外，E_SMOTE算法在確保Acc+與SMOTE_NCL基本持平的情況下，其Acc-值有顯著提高。負類樣本分類精度之所以提高是因為SMOTE_NCL清洗樣本時可能刪除重要的負類樣本，而E_SMOTE方法只是針對非安全集插入新樣本時進一步考慮了擴展近鄰的分布信息，并未刪除任何負類樣本。

全部實驗中E_SMOTE算法中擴展近鄰參數(shù)M的取值設(shè)置了3，4，5三個值，可以看出，除了表6和表8中當(dāng)M=3時取得最優(yōu)值F-value和G-mean外，其他4個數(shù)據(jù)集都在M=4時獲得這兩個度量的最大值，說明擴展近鄰中的樣本數(shù)量要適當(dāng)，既不能太多也不能太少，跟我們的直覺一致。

4 結(jié)語

平衡數(shù)據(jù)的算法是數(shù)據(jù)層面處理不平衡數(shù)據(jù)的關(guān)鍵，本文提出了一種稱作E_SMOTE的改進型過采樣算法。實驗結(jié)果表明考慮非安全集擴展近鄰的分布特征有效地提升了數(shù)據(jù)集的分類精度。本文算法的不足之處包括兩個方面，首先擴展近鄰參數(shù)M的取值只能根據(jù)實驗結(jié)果確定；其次本文使用rand函數(shù)選擇近鄰樣本，滿足M擴展近鄰即可。而沒有探察多個樣本點的M近鄰擴展分布，并引入合理的選擇機制。今后工作重點將對這兩個問題進行深入研究。

[1]李毅,姜天英,劉亞茹.基于不平衡樣本的互聯(lián)網(wǎng)個人信用評估研究[J].統(tǒng)計與信息論壇,2017,32（2）:84-90.

[2]Vapnik V N.The Nature of Statistical Learning Theory[M].New York:Springer，2000：138-167.

[3]楊磊,陸慧娟,嚴(yán)珂，等.一種計算代價敏感算法分類精度的方法[J].中國計量學(xué)院學(xué)報,2017,28（1）:92-96.

[4]李凱,高元,劉柏嵩.基于集成學(xué)習(xí)的標(biāo)題分類算法研究[J].計算機應(yīng)用研究,2017,34（4）:1004-1007.

[5]李村合,唐磊.基于欠采樣支持向量機不平衡的網(wǎng)頁分類系統(tǒng)[J].計算機系統(tǒng)應(yīng)用,2017,26（4）:230-235.

[6]Batuwita R,Palade V.Efficient Resampling Methods for Training Support Vector Machines with Imbalanced Datasets[C].International Joint Conference on Neural Networks.IEEE,2010:1-8.

[7]Chawla N V,Bowyer K W,Hall L O,et al.SMOTE:Synthetic Minority Over-Sampling Technique[J].Journal of Artificial Intelligence Research,2011,16（1）:321-357.

[8]Han H,Wang W Y,Mao B H.Borderline-SMOTE:A New Over-Sampling Method in Imbalanced Data Sets Learning[C].International Conference on Intelligent Computing,icic 2005.2005:878-887.

[9]許丹丹,王勇,蔡立軍.面向不均衡數(shù)據(jù)集的ISMOTE算法[J].計算機應(yīng)用,2011,31（9）:2399-2401.

[10]古平,楊煬.面向不均衡數(shù)據(jù)集中少數(shù)類細分的過采樣算法[J].計算機工程,2017,43（2）:241-247.