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

于艷麗 江開忠 盛靜文

(上海工程技術大學數理與統計學院 上海 201620)

0 引 言

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

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

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

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

1 相關知識

1.1 分類問題

1.1.1二分類理論

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

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

分類器超平面表示為：

w1x1+w2x2+…+wpxp=wTx=c

(1)

通常，超平面的系數和常數的估計可表示為下面優化問題的解：

(2)

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

1.1.2分類評價指標

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

表1 混淆矩陣

將實際為正類的樣本分為預測為正類和預測為負類兩部分，將實際為負類的樣本分為預測為負類和預測為正類兩部分，它們的個數分別簡記為：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) 對于少數類樣本中每一個個體x，以歐氏距離為標準計算它到少數類樣本集C1中所有樣本的距離，對所有距離排序，距離其最近的k個樣本便是其k近鄰。

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

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

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

(3)

1.2.2R-SOMTE算法[19]

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

1) 根據數據集不平衡比例設置一個采樣倍率N，從少數類樣本C1中循環選擇樣本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的樣本數等于或相當于C0的樣本時，結束過采樣。

1.2.3Randmon-SOMTE算法[18]

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

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

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

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

(7)

2 邊界混合采樣的BHSK算法

2.1 算法思想

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

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

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

從數據層面對數據集進行分類，為了使類之間的樣本數量均衡，實現較好的分類效果，基于支持向量機(SVM)的分類思想，超平面只與支持向量有關，而支持向量大都位于多數類樣本和少數類樣本的邊界，所以在處理不平衡數據時邊界集的識別是極其重要的[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 少數類邊界樣本集的細分

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

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

(10)

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

2.4 邊界集的過采樣方法與數量

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

2.5 非邊界集的欠采樣

2.6 算法步驟

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

輸入：訓練數據集C，近鄰參數k，插值數量D。

輸出：均衡數據集T。

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

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

3 實 驗

3.1 數據集的選擇與分析

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

表2 數據集信息

3.2 實驗結果分析

表3 不同算法在8個數據集上Recall對比結果

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

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

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

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

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

4 結 語

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