宋艷，白治江

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

0 引言

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

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

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

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

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

1.1 SMOTE算法

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

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

1.2 支持向量機(jī)

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

1.3 NCL（Neighborhood Cleaning Rule）

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

圖1 NCL原理

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

1.4 SMOTE_NCL算法

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

2 E_SMOTE算法

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

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

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

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

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

圖2 非安全集插樣示例

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

E_SMOTE算法的操作步驟如下：

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

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

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

評估標(biāo)準(zhǔn)是衡量分類器性能的準(zhǔn)則。為了客觀、公正地評價面向不平衡數(shù)據(jù)集的SVM分類器性能，結(jié)合實(shí)際需求，本文采用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計(jì)算公式如公式（3）所示：

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

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

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

實(shí)驗(yàn)中SMOTE和E_SMOTE算法的近鄰參數(shù)K都設(shè)置為5，并且E_SMOTE的擴(kuò)展近鄰參數(shù)M分別設(shè)置為3,4,5以便對比實(shí)驗(yàn)效果。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算法處理后，正負(fù)類樣本基本達(dá)到平衡，因此絕大部分?jǐn)?shù)據(jù)集的正類樣本的識別率提升了，即 Acc+顯著增大。在 6種數(shù)據(jù)集上SMOTE_NCL較SMOTE取得更高的 Acc+值，但同時Acc-的值卻有不同程度的下降，致使SMOTE_NCL的F-value和G-mean值要么沒有顯著提高，要么略有下降，原因是在SMOTE_NCL方法中，NCL作為一種清洗式的欠采樣方法，它只按照特定的近鄰規(guī)則簡單地刪除負(fù)類樣本，使得帶有重要信息的負(fù)類樣本也可能被刪除，降低了負(fù)類樣本訓(xùn)練分類器的能力。

整體上，SMOTE_NCL方法確實(shí)提升了數(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值，這是因?yàn)镋_SMOTE算法插值新樣本時綜合了擴(kuò)展近鄰的分布信息，不僅能有效抑制噪聲點(diǎn)的影響，同時也克服了類邊界模糊的問題。而由表6-表8可以觀察到SMOTE和E_SMOTE算法整體性能基本一樣或略小，通過多次交叉驗(yàn)證試驗(yàn)結(jié)果對比發(fā)現(xiàn)，本文并沒有對相似分布特征的樣本點(diǎn)采取抉擇策略，而是優(yōu)先選擇第一個滿足條件的近鄰樣本點(diǎn)，這種隨機(jī)選擇結(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-值有顯著提高。負(fù)類樣本分類精度之所以提高是因?yàn)镾MOTE_NCL清洗樣本時可能刪除重要的負(fù)類樣本，而E_SMOTE方法只是針對非安全集插入新樣本時進(jìn)一步考慮了擴(kuò)展近鄰的分布信息，并未刪除任何負(fù)類樣本。

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

4 結(jié)語

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

[1]李毅,姜天英,劉亞茹.基于不平衡樣本的互聯(lián)網(wǎng)個人信用評估研究[J].統(tǒng)計(jì)與信息論壇,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ì)算代價敏感算法分類精度的方法[J].中國計(jì)量學(xué)院學(xué)報,2017,28（1）:92-96.

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

[5]李村合,唐磊.基于欠采樣支持向量機(jī)不平衡的網(wǎng)頁分類系統(tǒng)[J].計(jì)算機(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].計(jì)算機(jī)應(yīng)用,2011,31（9）:2399-2401.

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