不平衡數(shù)據(jù)中基于異類k距離的邊界混合采樣

于艷麗 江開忠 盛靜文

(上海工程技術大學數(shù)理與統(tǒng)計學院 上海 201620)

0 引 言

不平衡數(shù)據(jù)指的是數(shù)據(jù)集中存在不同類別樣本的數(shù)目相差很大。以二分類數(shù)據(jù)為例，征信領域中誠信與違約、醫(yī)療領域中健康與絕癥、郵箱里正常郵件與垃圾郵件，這些二分類數(shù)據(jù)中某一類數(shù)據(jù)數(shù)量遠多于另一類，這樣的數(shù)據(jù)就稱為不平衡數(shù)據(jù)[1-4]。將數(shù)量較少的類別稱為少數(shù)類，將數(shù)量較多的稱為多數(shù)類?，F(xiàn)實世界中，隨處都有不平衡數(shù)據(jù)，且錯分兩類數(shù)據(jù)的代價是不同的，通常對少數(shù)類的正確判斷更有意義[5]。傳統(tǒng)的分類方法對于平衡的樣本數(shù)據(jù)已經表現(xiàn)出很好的性能，但是對于不平衡數(shù)據(jù)，分類器的性能在下降。如何提升傳統(tǒng)分類方法對少數(shù)類的識別準確率成為機器學習中一個急需解決的問題[1,6]。目前，解決不平衡數(shù)據(jù)問題的方法可以分為如下兩類：

1) 改進分類算法以提高對少數(shù)類樣本的識別，如：代價敏感學習[7]、集成學習[8]和單類學習等。AdaBoost算法[9]就是其中比較經典的處理不平衡數(shù)據(jù)的集成算法，本身就具有代價敏感的特性，能夠給予誤判樣本更高的權重。一些算法通過更改AdaBoost算法中樣本更新權重來增加正確率，如AdaCost算法[10]和RareBoost算法[11]。還有些算法將采樣算法與集成算法相結合，例如NIBoost[12]、RSBoost[13]和PCBoost[14]。另外還有其他分類算法，如：SVM[2]、決策樹、神經網絡等，它們也經常被用來處理不平衡數(shù)據(jù)。

2) 通過處理原始數(shù)據(jù)來提高對少數(shù)類樣本的識別，即對數(shù)據(jù)進行欠采樣或者過采樣來達到數(shù)據(jù)平衡的目的。欠采樣是剔除多數(shù)類樣本數(shù)量，過采樣是增加少數(shù)類樣本數(shù)量。欠采樣算法有基于密度的欠采樣[1]、基于權重的欠采樣[15]等，其很容易造成有用信息的減少。過采樣算法中的SMOTE[16]算法是主流算法，其通過線性插值的方法增加少數(shù)類虛擬個體，使得分類結果得到改善，但具有如下缺點：① 參與合成的少數(shù)類可能是噪聲樣本，進而影響新樣本質量；② 沒有根據(jù)少數(shù)類樣本的重要性，進行區(qū)別化選擇；③ 生成新樣本時，正負類樣本混雜，從而導致邊界模糊問題；④ 合成樣本僅在2個點的連線上產生，分類器易過擬合等[17]。針對SMOTE算法存在的問題，學者提出了很多改進的SMOTE算法。董燕杰[18]研究了Random-SMOTE方法，把直線插點改成三角形內插點；袁銘[19]提出了R-SMOTE算法，在n維球體進行插點。這些方法對減少過擬合現(xiàn)象均有一定作用，但都是對全體少數(shù)類樣本進行過采樣，準確率提升有限。候貝貝等[20]用np-SMOTE方法在邊界少數(shù)類周圍合成少數(shù)類，使其從非安全樣本變成安全樣本，突破了原有的少數(shù)類樣本點的范圍，但易產生噪聲。Han等[21]用Borderline-SMOTE算法定義了邊界，解決了沒有區(qū)分少數(shù)類點重要性的問題，但對于邊界的定義僅依靠異類點的數(shù)量，不夠細致。古平等[5]提出了SD-ISMOTE算法，采用了不同的過采樣算法，能夠解決過擬合的問題，但是目標依舊是全體少數(shù)類樣本。Batista等[22]提出了SMOTE與Tome Link結合的算法，Last等[23]提出了一種基于k-means聚類的SMOTE過采樣方法，兩者都有效地解決了噪聲問題。上述過采樣方法的改進在處理不平衡數(shù)據(jù)上都有一定優(yōu)勢，但大部分沒有對參與新樣本合成的少數(shù)類樣本進行區(qū)別化對待，或者區(qū)分度不高，從而導致少數(shù)類的識別率不夠高。

本文提出一種不平衡數(shù)據(jù)中基于異類k距離的邊界混合采樣算法，主要目標是區(qū)分邊界樣本與非邊界樣本，對參與合成的邊界少數(shù)類樣本做精細區(qū)分，以便增加產生新樣本的質量，提高少數(shù)類樣本的分類正確性。首先，生成邊界集，只對其中的少數(shù)類樣本進行過采樣，從而對少數(shù)類樣本點進行區(qū)別選擇；其次，根據(jù)支持度對邊界集中的少數(shù)類樣本進行細分，能夠更加細致嚴謹?shù)亟o每一個少數(shù)類樣本定位，少數(shù)類樣本虛擬個體的產生根據(jù)類別的不同分別采用SMOTE、R-SMOTE、Random-SMOTE的過采樣方法，改善過擬合現(xiàn)象；最后，對非邊界集多數(shù)類樣本基于異類k距離進行剔除，保留有意義的樣本。

1 相關知識

1.1 分類問題

1.1.1二分類理論

假設在一個兩分類問題中，數(shù)據(jù)集C=C0∪C1，C0∩C1=?，其中C0為多數(shù)類樣本，C1為少數(shù)類樣本。標準化后的樣本觀測矩陣為：

當xi∈C1時，yi=1，稱個體xi為陽性個體；即少數(shù)類個體；否則，yi=0，稱個體xt為陰性個體，即多數(shù)類個體。

分類器超平面表示為：

w1x1+w2x2+…+wpxp=wTx=c

(1)

通常，超平面的系數(shù)和常數(shù)的估計可表示為下面優(yōu)化問題的解：

(2)

即分類器的超平面法向量和常數(shù)是使得F1取最大值時的(w1,w2,…,wp,c)，F(xiàn)1指分類評價指標中的F1分類(F-Score)。

1.1.2分類評價指標

通常來說混淆矩陣是評價一個算法分類效果的不二選擇，混淆矩陣如表1所示。

表1 混淆矩陣

將實際為正類的樣本分為預測為正類和預測為負類兩部分，將實際為負類的樣本分為預測為負類和預測為正類兩部分，它們的個數(shù)分別簡記為：TP、FN、TN和FP，則分類器的性能表示如下：

1.1.3最小距離分類法

已知類C及其中心μ，個體x到類C的距離定義為：

d(x,C)=d(x,μ)=(x-μ)T(x-μ)

最小距離判別準則為：已知兩類C0和C1，對任意x，若d(x,C0)

1.2 相關過采樣算法

1.2.1SMOTE算法[16]

SMOTE算法流程如下:

1) 對于少數(shù)類樣本中每一個個體x，以歐氏距離為標準計算它到少數(shù)類樣本集C1中所有樣本的距離，對所有距離排序，距離其最近的k個樣本便是其k近鄰。

2) 根據(jù)樣本不平衡比例設置一個采樣比例以確定采樣倍率N，對于每一個少數(shù)類樣本x，從其k近鄰中隨機選擇樣本yi。

3) 對于每一個隨機選出的近鄰yi，分別與原樣本按下式構建新的樣本：

xnew,i=x+rand(0,1)×|x-yi|

(3)

1.2.2R-SOMTE算法[19]

R-SMOTE算法在n維球體內插值，算法流程如下:

1) 根據(jù)數(shù)據(jù)集不平衡比例設置一個采樣倍率N，從少數(shù)類樣本C1中循環(huán)選擇樣本x。

2) 從x的k個同類最近鄰中隨機選擇樣本y，構建新樣本。

zi,j=xj-|yj-xj|

(4)

z2,j=xj+|yj-xj|

(5)

xnew,j=xj+rand(0,1)×|z2,j-z1,j|

(6)

式中：xj代表樣本x的第j個屬性。

3) 如果D(x,xnew)>D(x,y)，則廢棄xnew，重新生成xnew。

4)xnew加入C1，當C1的樣本數(shù)等于或相當于C0的樣本時，結束過采樣。

1.2.3Randmon-SOMTE算法[18]

Random-SMOTE算法在三角形內生成新的樣本點，算法流程如下：

1) 根據(jù)數(shù)據(jù)集不平衡比例設置一個采樣倍率N，從少數(shù)類樣本C1中循環(huán)選擇個體x。

2) 在x的k近鄰中隨機尋找兩個同類個體a、b，在兩點連線上隨機確定一點y，最后在個體x與y之間合成新的樣本點xnew：

xnew=x+rand(0,1)×(x-y)

(7)

2 邊界混合采樣的BHSK算法

2.1 算法思想

BHSK算法作為混合采樣算法，綜合過采樣與欠采樣算法于一體。主要思路是凸顯不同位置樣本不同的采樣重要性，所以采樣方法要因樣本位置而異，這樣能產生有助于提高分類精確度的新樣本，而如何區(qū)分樣本的重要性是本文算法的重點之一。對于過采樣部分，BHSK算法采用兩種方法實現(xiàn)了對少數(shù)類樣本遞進式區(qū)分，分別是基于異類k距離邊界集的識別、支持度的判定，從而篩選出不同層次的少數(shù)類邊界點。對于欠采樣部分，BHSK算法主要是通過異類k距離判別，從而刪除遠離邊界的多數(shù)類點。

另一個相關問題是如何尋找適合各種不同位置少數(shù)類樣本的采樣方法與采樣倍率。根據(jù)不同位置樣本的不同特點，本文算法采用了三種過采樣算法和倍率，有針對性地對不同樣本進行過采樣，產生更有意義的位于邊界的新樣本。

2.2 基于異類k距離的邊界集識別

從數(shù)據(jù)層面對數(shù)據(jù)集進行分類，為了使類之間的樣本數(shù)量均衡，實現(xiàn)較好的分類效果，基于支持向量機(SVM)的分類思想，超平面只與支持向量有關，而支持向量大都位于多數(shù)類樣本和少數(shù)類樣本的邊界，所以在處理不平衡數(shù)據(jù)時邊界集的識別是極其重要的[20]。BHSK算法的邊界集是基于異類k距離來定義的，本文通過改進文獻[24]中的k距離，提出一種異類k距離。

換言之，x的異類k距離是所有與x異類的點中，由近到遠第k個異類點到x的距離。異類k距離可以評價一個樣本點附近異類點的密度，異類k距離越大，說明附近異類點密度越小，反之則越大。

(8)

(9)

定義4邊界噪聲點。若x=A0或A1，且其k近鄰全是異類點，可以理解為深入異類點內部，則x為邊界噪聲點；由邊界噪聲點產生的新樣本，可能存在質量較差的問題，所以以下B0和B1表示已經刪除了噪聲點的邊界0類點與邊界1類點。

2.3 少數(shù)類邊界樣本集的細分

定義5支持度。設x∈B1，m(x)表示x的最近k個近鄰中屬于B1的個體數(shù)，則m(x)為x的支持度。

根據(jù)支持度將B1分為三類，具體情況如下：

(10)

在區(qū)分邊界集的基礎上再對邊界集進行細分，目的是為了更加細致地對每一個少數(shù)類樣本進行重要性評估，從而選擇出每一個類別少數(shù)類樣本適合的采樣方法。

2.4 邊界集的過采樣方法與數(shù)量

對于邊界集少數(shù)類樣本B1進行過采樣。對于過采樣方法，BHSK算法根據(jù)每個點對分類做出的貢獻不同對三類邊界點采用不同的過采樣方法和過采樣倍率，按照近邊界則優(yōu)的原則進行如下采樣?？偛蓸訑?shù)量是D=C0-C1，按照3∶2∶1的比例確定三個類別中新生成樣本的數(shù)量。

2.5 非邊界集的欠采樣

2.6 算法步驟

本文提出的BHSK算法具體如下：

輸入：訓練數(shù)據(jù)集C，近鄰參數(shù)k，插值數(shù)量D。

輸出：均衡數(shù)據(jù)集T。

2) 將B1根據(jù)支持度細分為B11、B12和B13。

5) 將train 1和train 2合并為train。

3 實 驗

3.1 數(shù)據(jù)集的選擇與分析

本文從UCI數(shù)據(jù)庫選取8個數(shù)據(jù)集Abalone、biodeg、Ecoli、Shuttle、pima、glass、yeast、spambase，其中有些數(shù)據(jù)集是二分類數(shù)據(jù)集，比如biodeg、spambase、pima；有些是多分類數(shù)據(jù)集，比如Abalone、Ecoli、shuttle、glass、yeast。將abalone中”F”定義為少數(shù)類，其余為多數(shù)類；Ecoli數(shù)據(jù)中的標簽為“pp，om”的樣本定義為少數(shù)類，其他為多數(shù)類；將shuttle數(shù)據(jù)集中標簽為“1”定義為多數(shù)類，其他為少數(shù)類；將glass標簽中“2”定義為少數(shù)類，其他為多數(shù)類；將yeast數(shù)據(jù)集標簽中“MIT”定義為少數(shù)類其他為多數(shù)類。數(shù)據(jù)集信息如表2所示。

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

3.2 實驗結果分析

表3 不同算法在8個數(shù)據(jù)集上Recall對比結果

表4 不同算法在8個數(shù)據(jù)集上的F1-score對比結果

(a) Abalone (b) biodeg (c) ecoli

從表3可以看出，BHSK算法在少數(shù)類的識別上是比較有優(yōu)勢的，大部分數(shù)據(jù)集在本文算法的處理后得到的Recall值都高于文中列舉的其他對比算法。因為本文在處理數(shù)據(jù)時，對少數(shù)類的邊界點做了相應處理，較好地降低了由邊界點分錯而帶來的不良影響，同時對非邊界的多數(shù)類基于異類k距離進行刪除，較好地保留了對分類有價值的樣本點。雖然在Yeast、Spambase數(shù)據(jù)集上沒有取得最優(yōu)值，但相差不大，說明BHSK算法能夠在一定程度上提高少數(shù)類的分類性能。

從表4可見，針對Yeast數(shù)據(jù)集，R-SMOTE算法的結果優(yōu)于本文，由于該數(shù)據(jù)集的不平衡比率較大，且邊界點重疊度較大，本文邊界集閾值的設定可能對該數(shù)據(jù)集的分類性能產生影響，使得球體插值更適合于這個數(shù)據(jù)集。但是從整體來看，BHSK算法經過一系列處理以后，能夠使少數(shù)類的準確性提高。

為了更加可視化本文算法與其他算法的比較情況，圖1列舉了本文算法與所有對比算法在不同數(shù)據(jù)集不同指標的得分情況，橫坐標都表示打分的指標Precision、Recall、F1-score和Accuracy。縱坐標是分類結果打分情況，其范圍在0～1之間。綜上所述，BHSK算法優(yōu)于SMOTE、R-SMOTE、Borderline-SMOTE和KOCDE算法，它可以更合理且有效地改善不均衡數(shù)據(jù)集中樣本分布的不均衡程度，從而提高分類器的性能。

4 結 語

本文針對非平衡數(shù)據(jù)分類問題，提出一種基于異類k距離邊界混合采樣分類算法。一方面能夠通過兩次判別：邊界判別與支持度判別，更加具體區(qū)分少數(shù)類樣本重要性，并對細分的不同類別少數(shù)類采取不同的分類方法和不同的采樣倍率，給距離邊界越近的少數(shù)類越高重視；另一方面對非邊界集的多數(shù)類點根據(jù)異類k距離閾值，刪除遠離邊界的一部分點，從而構造平衡數(shù)據(jù)。實驗結果表明，本文算法在一定程度上提高了數(shù)據(jù)集的分類性能，可將其應用于一系列評估和檢測問題。但本文算法也存在一些不足，如邊界集閾值與多數(shù)類非邊界集閾值的選取方面理論依據(jù)不足，未來將在閾值方面進行研究。