孟東霞，李玉鑑

1.河北金融學(xué)院 信息管理與工程系，河北 保定 071051

2.北京工業(yè)大學(xué) 信息學(xué)部 計(jì)算機(jī)學(xué)院，北京 100124

1 引言

不平衡數(shù)據(jù)集指各類別數(shù)據(jù)采樣數(shù)量差異較大，在分布上不平衡的集合，其在疾病的識(shí)別診斷、信用風(fēng)險(xiǎn)識(shí)別、異常天氣預(yù)報(bào)、攻擊檢測等領(lǐng)域中廣泛存在。其中，樣本數(shù)量較少的類別被稱為少數(shù)類，樣本數(shù)量較多的類別是多數(shù)類。在現(xiàn)實(shí)的信用評(píng)估問題中，客戶數(shù)據(jù)的類別分布都很不平衡，即信用差的客戶樣本往往要比信用好的樣本少很多。在這種情況下，傳統(tǒng)的分類模型例如神經(jīng)網(wǎng)絡(luò)、貝葉斯網(wǎng)絡(luò)、K-近鄰、支持向量機(jī)等對(duì)信用差的少數(shù)類客戶的錯(cuò)誤分類率要比信用好的多數(shù)類客戶高很多，將導(dǎo)致企業(yè)極大的損失。因此在不平衡數(shù)據(jù)集中，提高少數(shù)類樣本的分類性能是一個(gè)有意義的研究課題。

目前，主要從算法和數(shù)據(jù)兩個(gè)層面解決不平衡數(shù)據(jù)集的分類問題：在算法設(shè)計(jì)上，通過改變現(xiàn)有算法使其分類更偏向于少數(shù)類，代價(jià)敏感學(xué)習(xí)方法[1]、提升算法[2]和集成算法；在數(shù)據(jù)層面上，通過某些策略增加少數(shù)類樣本（過采樣）和減少多數(shù)類樣本（欠采樣）以達(dá)到平衡樣本分布的目的。本文采用從數(shù)據(jù)層面上增加少數(shù)類樣本數(shù)量的方法平衡數(shù)據(jù)分布。

最簡單的過采樣方法是隨機(jī)復(fù)制少數(shù)類樣本，雖能從數(shù)量上達(dá)到快速增加樣本數(shù)量的目的，但實(shí)際效果不夠理想[3]。SMOTE算法（Synthetic Minority Over-sampling Technique）基于K近鄰確定少數(shù)類樣本的K個(gè)近鄰，通過對(duì)少數(shù)類樣本和K個(gè)近鄰插值合成新的少數(shù)類樣本，以增加少數(shù)類樣本的數(shù)量，是目前最為典型的過采樣方法[4]。SMOTE算法雖然能在一定程度上改善少數(shù)類樣本的分類性能，但是由于未考慮鄰近樣本點(diǎn)的分布，容易引入噪聲和引起過擬合。趙等人將產(chǎn)生的新樣本限制在一定區(qū)域內(nèi)，使得樣本集分布趨于中心化，用更少的正類樣本點(diǎn)人為構(gòu)造樣本，提出了基于SMOTE的改進(jìn)算法TSMOTE（Triangle SMOTE）和MDSMOTE（Max Distance SMOTE）[5]。Borderline-SMOTE（Borderline Synthetic Minority Over-sampling Technology）強(qiáng)化了邊界點(diǎn)在插值中的影響，根據(jù)少數(shù)類樣本點(diǎn)周邊的近鄰分布，將其分為safe（近鄰均為少數(shù)類樣本）、danger（近鄰中包含少數(shù)類和多屬類樣本）和noise（近鄰均為多屬類樣本）三種類型，只選取danger樣本利用smote算法合成新樣本[6]。楊等人提出了精化Borderline-SMOTE方法（RB-SMOTE），其加強(qiáng)了對(duì)邊界樣本的進(jìn)一步區(qū)分，不同的邊界樣本合成不同數(shù)量的新樣本[7]。為有效避免新合成樣本的重疊問題，帶多數(shù)類權(quán)重的少數(shù)類過采樣法被提出，其核心思路是根據(jù)少數(shù)類和多數(shù)類樣本的距離信息，識(shí)別出難以學(xué)習(xí)的信息豐富的少數(shù)類樣本，使用聚類方法從加權(quán)信息量大的少數(shù)類樣本中合成新樣本[8]。夏等人在利用層次聚類算法對(duì)少數(shù)類聚類后，根據(jù)類簇的密度因子和少數(shù)樣本到多數(shù)類邊界的距離確定少數(shù)樣本的采樣權(quán)重，提出一種加權(quán)過采樣方法[9]?？紤]到支持向量對(duì)分類間隔決策邊界的影響，一種基于支持向量的過采樣方法被提出，該方法在利用支持向量機(jī)對(duì)訓(xùn)練集進(jìn)行學(xué)習(xí)后，根據(jù)統(tǒng)計(jì)特性對(duì)少數(shù)類樣本中的支持向量添加一定數(shù)量的噪聲來平衡數(shù)據(jù)集[10]。算法L-SMOTE將SMOTE與SVM有機(jī)結(jié)合起來進(jìn)行迭代，對(duì)SVM的錯(cuò)分樣本進(jìn)行循環(huán)采樣，有效解決了SMOTE和SVM在處理不平衡數(shù)據(jù)集分類問題時(shí)的不足[11]。改進(jìn)的FTL-SMOTE算法借助混合核SVM分類器對(duì)數(shù)據(jù)集分類后，針對(duì)噪聲樣本首次提出了噪聲樣本識(shí)別三原則，克服了L-SMOTE算法產(chǎn)生大量噪聲點(diǎn)的問題，有效提高了分類模型的整體性能[12]。

考慮到大多數(shù)數(shù)據(jù)集為非線性可分的情況，本文基于文獻(xiàn)[13]在定義最優(yōu)非線性分類邊界時(shí)提出的特征邊界點(diǎn)的概念，設(shè)計(jì)了一種融合特征邊界的幾何分布信息的過采樣技術(shù)。所提方法首先采用K近鄰方法去掉少數(shù)類樣本中的噪聲點(diǎn)，然后基于少數(shù)類樣本點(diǎn)的多類近鄰集合，根據(jù)特征邊界點(diǎn)的計(jì)算過程識(shí)別出少數(shù)類樣本中有利于定義最優(yōu)非線性分類邊界的樣本點(diǎn)，通過其與少數(shù)類聚簇的結(jié)合生成新樣本。

2 特征邊界點(diǎn)

特征邊界點(diǎn)的概念由Pujol O和Masip D提出，它實(shí)現(xiàn)了在數(shù)據(jù)集原始空間內(nèi)準(zhǔn)確地定義最佳非線性分類面的目標(biāo)，是在分片線性分類器——優(yōu)化幾何集成模型中構(gòu)造局部最優(yōu)線性分類器的基礎(chǔ)[13]。從幾何角度來說，每個(gè)樣本點(diǎn)周圍都有一個(gè)“影響區(qū)”，即以樣本點(diǎn)為中心構(gòu)造的超球面。樣本點(diǎn)對(duì)影響區(qū)內(nèi)的噪聲點(diǎn)具有魯棒性，也就是位于這個(gè)超球面內(nèi)的任意噪聲點(diǎn)都被判定為與此樣本點(diǎn)同類。如果兩個(gè)樣本點(diǎn)不屬于同一類，則其影響區(qū)發(fā)生相互碰撞的位置就被稱為邊界二分點(diǎn)。位于最佳非線性分類邊界上的邊界二分點(diǎn)就是特征邊界點(diǎn)，確定特征邊界點(diǎn)的不同類樣本參與了最佳非線性分類邊界的構(gòu)造，在各自類中蘊(yùn)含的幾何邊界信息較強(qiáng)，若基于其合成新樣本，有利于保留數(shù)據(jù)集中的邊界信息。

如圖1所示，假設(shè)空心點(diǎn)是正類樣本點(diǎn)，三角形是負(fù)類樣本點(diǎn)，樣本點(diǎn)周圍的虛線型圓圈表示該樣本點(diǎn)的影響區(qū)，不同類樣本點(diǎn)的影響區(qū)在圖中實(shí)心點(diǎn)位置發(fā)生碰撞后，將分別被實(shí)心點(diǎn)以最大間隔分離開。因此，實(shí)心點(diǎn)是位于最佳分類邊界上的特征邊界點(diǎn)，在其基礎(chǔ)上構(gòu)造局部最優(yōu)線性分類器并計(jì)算相應(yīng)權(quán)重后，即可集成為優(yōu)化幾何集成模型，從而得到最佳非線性分類面。圖中的不同類樣本點(diǎn)A和B是確定特征邊界點(diǎn)的點(diǎn)對(duì)，位于各自類中的邊界位置。

圖1 圖中的實(shí)心點(diǎn)是特征邊界點(diǎn)

已知訓(xùn)練集s={( xi,li)}包含M個(gè)樣本點(diǎn)，其中xi=根據(jù)定義，特征邊界點(diǎn)可由符合下列條件的不同類樣本點(diǎn)對(duì)(x ,x)構(gòu)造得ij到，快速算法可參考文獻(xiàn)[14]：

（1）使特征邊界點(diǎn)位于最佳非線性分類邊界上。根據(jù)歐式距離計(jì)算，xi,xj比其他任意樣本點(diǎn)xk接近，即：

其中，構(gòu)造特征邊界點(diǎn)的少數(shù)類樣本可用來合成新樣本，在上述條件的判定過程中可對(duì)其進(jìn)行標(biāo)記。

3 融合邊界信息的過采樣方法

根據(jù)特征邊界點(diǎn)的定義，參與構(gòu)造最佳非線性分類邊界的少數(shù)類樣本點(diǎn)位于樣本分布的邊界位置，若挑選其結(jié)合所屬類簇中的樣本點(diǎn)合成新樣本，將使少數(shù)類樣本的分布更加合理，有利于保留樣本分布的邊界信息，提高識(shí)別少數(shù)類樣本的準(zhǔn)確率。算法的具體流程如下：

輸入：S為不平衡數(shù)據(jù)集；K1為用于篩選少數(shù)類噪聲點(diǎn)的近鄰樣本數(shù)；K2為識(shí)別邊界位置附近的少數(shù)類樣本時(shí)，用于構(gòu)造少數(shù)類樣本的多數(shù)類鄰居數(shù)量。

輸出：過采樣生成的少數(shù)類樣本集合Sgen。

步驟1將原始數(shù)據(jù)集S分為訓(xùn)練集T和交叉驗(yàn)證集V。

步驟2利用K-近鄰計(jì)算T中所有少數(shù)類樣本的近鄰集合(K=K1)，過濾掉近鄰全為相反類別的樣本（認(rèn)定為噪聲點(diǎn)），得到新的訓(xùn)練集T′。

步驟3根據(jù)特征邊界點(diǎn)的定義，識(shí)別出T′中帶有明顯邊界信息的少數(shù)類樣本，加入集合,初始化為空集：

步驟3.1利用步驟2中計(jì)算得到的樣本間距離，利用K近鄰獲得T′中所有少數(shù)類樣本xi的多數(shù)類近鄰集合

步驟3.2將少數(shù)類樣本xi與近鄰集合中的多類樣本xj依次構(gòu)造點(diǎn)對(duì)，檢驗(yàn)其能否構(gòu)造特征樣本點(diǎn)，能參與構(gòu)造特征邊界點(diǎn)的xi具有明顯的邊界信息，將其加入集合。

步驟4對(duì)T′中的少數(shù)類進(jìn)行聚類，得到N個(gè)類簇，C1,C2,…,CN。

步驟5初始化Sgen為空集，基于集合和所屬類簇合成新樣本：

步驟5.1根據(jù)距離信息，將T'cp中的樣本點(diǎn)xi劃分到對(duì)應(yīng)的類簇Ck中，1≤k≤N。

將集合Sgen和T′一起構(gòu)成新的訓(xùn)練集，獲得分布較為平衡的數(shù)據(jù)集。用分類器對(duì)其進(jìn)行訓(xùn)練后，可通過交叉驗(yàn)證集V評(píng)估其性能。

圖2直觀地展示了算法合成少數(shù)類樣本的基本原理：（a）中給出了訓(xùn)練集的原始分布情況，其中空心圓為少數(shù)類，X形為多數(shù)類，根據(jù)步驟2去掉其中的噪聲點(diǎn)。（b）在新訓(xùn)練集T′，基于少數(shù)類樣本的多數(shù)類近鄰集合構(gòu)造特征邊界點(diǎn)，能定義特征邊界點(diǎn)的少數(shù)類樣本加入集合T'cp。圖中實(shí)心點(diǎn)是特征邊界點(diǎn)，假設(shè)實(shí)線型曲線是在其基礎(chǔ)上定義的最佳非線性分類邊界，經(jīng)過實(shí)心點(diǎn)虛線一端的空心圓是帶有顯著邊界信息的少數(shù)類樣本，可參與樣本的合成。（c）對(duì)少數(shù)類樣本聚類，得到T'cp中樣本點(diǎn)所屬的類簇。（d）根據(jù)步驟5.2合成新樣本，即圖中的三角形。從圖中可以看到，此方法減少了噪聲點(diǎn)的引入，極大程度地保留了分類邊界信息。

圖2 融合特征邊界信息的過采樣方法圖

4 實(shí)驗(yàn)

4.1 人工數(shù)據(jù)集

為了驗(yàn)證融合特征邊界信息過采樣方法的有效性，構(gòu)造人工數(shù)據(jù)集對(duì)比表現(xiàn)不同方法新合成樣本的分布情況。假設(shè)所構(gòu)造的數(shù)據(jù)樣本點(diǎn)為( )xi,yi，其中 xi是二維特征，其在兩個(gè)維度上均服從均勻分布，yi是類別信息，在樣本點(diǎn)特征信息平方根的基礎(chǔ)上隨機(jī)判定為+1或者－1。在實(shí)驗(yàn)中，實(shí)心點(diǎn)是多數(shù)類，X形是少數(shù)類，方塊形是算法合成的少數(shù)類樣本，其數(shù)量由多數(shù)類樣本和少數(shù)類樣本的差值確定。實(shí)驗(yàn)使用Python語言編寫，SMOTE和Borderline-SMOTE方法使用的是Python庫imbalance-learn package中的程序。

圖3給出了采用不同過采樣方法合成新樣本的分布圖。（a）中是數(shù)據(jù)的原始分布情況；（b）和（c）分別是采用SMOTE和Borderline-SMOTE方法合成的樣本分布情況；（d）展示了本文方法所合成的新樣本分布情況。從圖中可以看到，本文方法較其他兩種，引入了較少的噪聲合成點(diǎn)，新樣本的分布與原始分布較為一致，較大程度地保留了原始分類邊界信息。

圖3 不同方式下合成樣本的分布圖

4.2 UCI數(shù)據(jù)集

為了進(jìn)一步驗(yàn)證所提方法的有效性，選擇8組UCI[15]數(shù)據(jù)集進(jìn)行測試，數(shù)據(jù)集信息如表1所示，不平衡率由少數(shù)類樣本數(shù)量/多屬類樣本數(shù)量計(jì)算得到。對(duì)多類數(shù)據(jù)集，將其中一類設(shè)置為少數(shù)類，其余類合并為多屬類。所有數(shù)據(jù)集均采用五折交叉驗(yàn)證的方法分成訓(xùn)練集和測試集，每種方法執(zhí)行五次，取平均值作為實(shí)驗(yàn)結(jié)果。在實(shí)驗(yàn)前，所有樣本點(diǎn)的特征值都被縮放到[0，1]之間。本文所提方法使用Python語言編寫，SMOTE、Borderline-SMOTE和SVM過采樣方法使用的是Python庫imbalance-learn package中的代碼，分類器選用支持向量機(jī)，核函數(shù)采用高斯核，使用Python庫svm中SVC代碼實(shí)現(xiàn)。

表1 實(shí)驗(yàn)所用數(shù)據(jù)集

目前，評(píng)價(jià)不平衡數(shù)據(jù)分類問題的標(biāo)準(zhǔn)有F-value和G-mean等，其計(jì)算過程均由混淆矩陣構(gòu)造得到。混淆矩陣的定義如表2所示。

F-value：

表2 混淆矩陣

G-mean同時(shí)考慮了多數(shù)類和少數(shù)類的分類準(zhǔn)確率，可用于衡量整體分類效果。

表3給出了不同過采樣方法處理后使用支持向量機(jī)分類得到的F-value值和G-mean值。

表3粗體部分給出了同組數(shù)據(jù)集中F-value和G-mean值相對(duì)較高的采樣方法。通過對(duì)比可以看出，本文所提方法在不平衡率較高的數(shù)據(jù)集中，F(xiàn)-value值相對(duì)較高，表示其對(duì)少數(shù)類的分類效果較好，在不平衡率較低的數(shù)據(jù)集中，F(xiàn)-value值與其他方法差異較小甚至基本持平?？傮w來看，所提方法能有效提高少數(shù)類分類準(zhǔn)確率。從所有數(shù)據(jù)集的G-mean結(jié)果來看，本文所提方法提高了不平衡數(shù)據(jù)的整體分類性能。

5 結(jié)束語

本文提出了一種融合數(shù)據(jù)集特征邊界幾何信息的過采樣方法。該方法在檢測得到可構(gòu)造特征邊界點(diǎn)的少數(shù)類樣本后，結(jié)合其所屬少數(shù)類聚簇合成新樣本，在保留分類邊界信息的同時(shí)，減少了噪聲點(diǎn)的引入。在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上開展的實(shí)驗(yàn)證明所提方法有效改善了不平衡數(shù)據(jù)的整體分類性能，提高了少數(shù)類樣本的分類準(zhǔn)確性。本文方法在個(gè)別數(shù)據(jù)集上對(duì)少數(shù)類樣本分類的一般表現(xiàn)可能與可構(gòu)造的特征邊界點(diǎn)數(shù)量較少有關(guān)，導(dǎo)致參與合成新樣本的少數(shù)類樣本點(diǎn)數(shù)量減少。在今后的工作中，將對(duì)此問題進(jìn)一步深入研究，使算法更全面地融合特征邊界信息。

表3 不同過采樣方法下的分類性能比較