融合特征邊界信息的不平衡數(shù)據(jù)過采樣方法

孟東霞，李玉鑑

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

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

1 引言

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

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

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

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

2 特征邊界點

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

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

圖1 圖中的實心點是特征邊界點

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗

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

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

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

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

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

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

表1 實驗所用數(shù)據(jù)集

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

F-value：

表2 混淆矩陣

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

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

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

5 結(jié)束語

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

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