姜新盈，江開忠，嚴 濤，王舒梵

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

0 引 言

各個類別樣本數(shù)量相差較大的數(shù)據(jù)集稱為不平衡數(shù)據(jù)，不平衡數(shù)據(jù)在各個領(lǐng)域中隨處可見，如工業(yè)故障檢測[1]、疾病診斷[2]、信貸欺詐[3]、石油儲層含油量識別[4]等，因為少數(shù)類樣本的存在，傳統(tǒng)分類方法為了確保得到較高的整體分類性能會向多數(shù)類傾斜，這也導(dǎo)致少數(shù)樣本分類錯誤[5]，但是，人們經(jīng)常關(guān)注分類錯誤成本較高的少數(shù)類樣本。因此，如何確保多數(shù)類樣本準確性的同時提高少數(shù)類樣本的識別精度是機器學(xué)習(xí)中需要解決的一大難題。

現(xiàn)有文獻中僅使用欠采樣或過采樣算法會產(chǎn)生過擬合問題或者誤刪重要樣本，而混合采樣算法的分類效果一般比單一的采樣方法好[6]。許多研究學(xué)者相繼提出混合采樣方法。侯貝貝等[7]提出的BMRM算法以及吳藝凡等[8]提出的SVM_HS算法雖然區(qū)分了不同類別樣本，但合成樣本質(zhì)量不佳，陸萬榮等[9]改進的MD-SMOTE算法雖然改善了少數(shù)類樣本分布邊緣化問題，但存在易產(chǎn)生冗余樣本的風(fēng)險。

以上算法大部分沒有區(qū)分少數(shù)類樣本的重要性，且沒有考慮類內(nèi)分布情況，針對以上問題，本文提出了BWBMS算法來更有效識別少數(shù)類樣本。一方面考慮類內(nèi)樣本分布情況，通過引入邊界因子將數(shù)據(jù)集劃分成邊界集和非邊界集，再設(shè)置采樣比重和總權(quán)重將邊界集少數(shù)類樣本進行劃分，考慮不同位置少數(shù)類樣本的重要性，分別采用不同的采樣算法和采樣倍率，使得在遠離邊界的密集區(qū)域的樣本合成較少，在靠近邊界的低密度區(qū)域的樣本合成較多。另一方面，考慮不同區(qū)域樣本的不同，對非邊界集中的多數(shù)類樣本采用NearMiss1算法[10]進行刪減，最終使類別樣本集相對平衡。

1 相關(guān)工作

1.1 不平衡數(shù)據(jù)分類問題

在當(dāng)前研究中，主要從以下3類研究非平衡數(shù)據(jù)分類：在特征層面，主要是篩選原始特征或構(gòu)造新特征來有效識別少數(shù)類；從算法層面來看，主要是利用代價敏感因子等對現(xiàn)有的算法改進，如使用單一樣本來訓(xùn)練的單類學(xué)習(xí)、把多個基分類器的分類結(jié)果進行集成的集成學(xué)習(xí)[11]、引入代價的代價敏感學(xué)習(xí)[12]等。在數(shù)據(jù)層面，主要是通過欠采樣、過采樣以及混合采樣來平衡數(shù)據(jù)集以提升分類性能。

欠采樣算法中較為典型的是隨機欠采樣，但是極易誤刪重要樣本，基于此，吳圓圓等[13]根據(jù)樣本間的歐氏距離和k近鄰規(guī)則來刪減多數(shù)類樣本。而過采樣算法中經(jīng)典的SMOTE算法[14]也有一些問題：容易受到噪聲樣本影響而造成合成樣本質(zhì)量不佳；沒有對少數(shù)類樣本區(qū)別對待，且容易導(dǎo)致兩類樣本邊界模糊；未注意到少數(shù)類樣本的分布情況，容易在密集區(qū)產(chǎn)生過多樣本；合成樣本僅進行線性插值，導(dǎo)致樣本分布區(qū)域小而使分類器易過擬合[6]。為了改善SMOTE的缺點，Wang等[15]使用Random-Smote算法，少數(shù)類樣本在三角形內(nèi)進行插值，使合成樣本的分布更加合理，但沒有對少數(shù)類樣本細分；古平等[16]對細分的少數(shù)類樣本采用不同的過采樣方法，但沒有注意到少數(shù)類樣本分布問題。趙清華等[17]使生成樣本接近于質(zhì)心，降低了合成樣本分布位于邊緣的可能性，也改善了樣本數(shù)據(jù)集分布問題，但沒有關(guān)注到少數(shù)類樣本的區(qū)別。這些算法僅對少數(shù)類進行處理，分類性能有所不足。

1.2 相關(guān)采樣算法

1.2.1 SMOTE算法

SMOTE算法[14]流程如下：

(1)計算少數(shù)類樣本集C(1)中每個個體x到C(1)中所有個體間的歐式距離，計算每個少數(shù)類個體x的k近鄰；

(2)循環(huán)選擇少數(shù)類樣本集C(1)中的個體x， 隨機選擇其k近鄰樣本點作為輔助樣本y；

(3)在根樣本x和輔助樣本y之間按照以下公式進行新樣本的合成

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

(1)

1.2.2 Random-SMOTE算法

Random-SMOTE[15]是在三角形區(qū)域內(nèi)進行線性插值以形成新的樣本，其算法流程如下：

(1)根據(jù)樣本的不平衡比例設(shè)置一個采樣倍率，從少數(shù)類樣本集C(1)中循環(huán)選取個體x， 在k個同類近鄰中選擇兩個樣本點y1、y2作為間接樣本。根據(jù)以下公式在y1、y2之間進行隨機線性插值，生成N個間接樣本pj，j=1,2,……,N

pj=y1+rand(0,1)×(y2-y1)

(2)

(2)在pj和x之間根據(jù)下列公式進行線性插值以構(gòu)造新的少數(shù)類樣本

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

(3)

2 BWBMS算法

BWBMS算法是把欠采樣和過采樣算法思想結(jié)合起來所提出的算法，主要創(chuàng)新點在于考慮了邊界集中少數(shù)類不同位置樣本的重要程度的不同，所使用的采樣方法和采樣倍率是依據(jù)樣本的位置及其所處位置的稀疏程度而定，另一方面考慮類內(nèi)樣本的稀疏程度，計算邊界集少數(shù)類樣本集中每個個體的支持度和密度，并賦予各個樣本相應(yīng)權(quán)重，對少數(shù)類樣本根據(jù)密度權(quán)重和支持度權(quán)重之和以及采樣比重進行細分，避免在密集區(qū)生成大量冗余樣本，稀疏區(qū)依舊樣本較少。最后在非邊界集采用NearMiss1欠采樣算法來處理多數(shù)類樣本，保留對分類起重要作用的樣本，以使類別樣本集相對平衡。

2.1 數(shù)據(jù)集邊界因子

根據(jù)支持向量機(SVM)的原理，樣本離類別邊界越近，其包含的重要信息就越多，直接刪除邊界上的樣本點有可能會誤刪含有重要信息的樣本[7]，因此有效識別出邊界點對于提高少數(shù)類分類精度是極其重要的。

為了有效識別出邊界點，文中引入k-離群度[9]來有效識別邊界點，將原樣本空間劃分為邊界集和非邊界集，具體定義如下：

定義1k距離：對于數(shù)據(jù)集M和任意正整數(shù)k， 對象x的k距離記為dk(x)， 其中對象x∈M且滿足：

(1)至少有k個對象y∈M-{x}， 使得

d(x,y)≤dk(x)

(2)至多有k-1個對象y∈M-{x}， 使得

d(x,y)

其中，d(x,y) 表示x與y之間的歐氏距離。

定義2k-離群度：對任意點x∈M，x的k距離與其ε鄰域內(nèi)所有點(包含x)的k距離的平均值之比，稱為x的k-離群度，記為

(4)

其中， |ε(x)| 為點x的ε鄰域內(nèi)樣本點的個數(shù)。(下同)特殊地，本文取ε=dk(x)，x的ε鄰域等于x的k近鄰鄰域。

定義3 邊界因子：數(shù)據(jù)集M中任意點x的k-離群度與1之差的絕對值記為點x的邊界因子σ(x)。 即

σ(x)=|1-τ(x)|

(5)

邊界因子的大小反映了該點周圍樣本的分布，根據(jù)以上定義，可以通過設(shè)置閾值σ0并與σ(x) 進行比較來判斷樣本點是否為邊界點。

2.2 基于邊界因子的邊界集識別

定義4 邊界點：對于任意x∈M， 當(dāng)σ(x)>σ0時，稱樣本點x為邊界點，否則為非邊界點。其中

(6)

2.3 對邊界集少數(shù)類樣本的處理

(7)

(8)

則樣本x的密度權(quán)重為

(9)

總權(quán)重公式為

w(x)=α*wρ(x)+β*wk(x)

(10)

2.4 非邊界集樣本的處理

為了提高算法整體運行速度，并使數(shù)據(jù)樣本的分布越來越合理化、均勻化，應(yīng)選擇適當(dāng)?shù)那凡蓸铀惴āＴ谌コ紨?shù)據(jù)集的噪聲之后，本文采用基于數(shù)據(jù)分布特征的NearMiss1算法[10]來處理非邊界集中的多數(shù)類樣本，計算每個多數(shù)類樣本點的k個異類最近鄰，保留到最近的這k個異類最近鄰平均距離小的點，以此降低算法復(fù)雜度并能保留含有重要信息的樣本點。

2.5 BWBMS算法描述

輸入：原始數(shù)據(jù)集C=C(0)∪C(1)且C(0)∩C(1)=? (C(0)： 多數(shù)類樣本集，C(1)： 少數(shù)類樣本集近鄰參數(shù)k， 邊界閾值σ0)

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

步驟1 對于數(shù)據(jù)集C中的每個個體x， 計算對應(yīng)的k近鄰，如果這k個近鄰樣本全部為異類樣本，就把個體x視為噪聲樣本，從C中剔除，得到C′， 其樣本量為 |C′|。

步驟2 fori=1 to |C′|， 計算C′中每個樣本x的邊界因子σ(x);

步驟2.1 計算樣本點x到其它樣本點的歐氏距離，得到對應(yīng)的k距離dk(x);

步驟2.2 計算每個樣本點的k-離群度τ(x);

步驟2.3 計算每個樣本點的邊界因子σ(x)。

3 實驗及結(jié)果分析

3.1 評價指標(biāo)

對于不平衡數(shù)據(jù)的研究，正確的區(qū)分出誤分代價更高的正類是當(dāng)前機器學(xué)習(xí)的目標(biāo)。但是僅使用準確性作為評估指標(biāo)是不公平的，研究學(xué)者常常根據(jù)混淆矩陣引入的概念來評估算法性能。表1是二分類問題的混淆矩陣。

表1 混淆矩陣

根據(jù)混淆矩陣，引入查全率、查準率和真負率3個定義。

查全率(Recall)是指數(shù)據(jù)集中正類樣本被預(yù)測正確的比率

(11)

查準率(Precision)是指所有預(yù)測為正類的樣本中，實際上也是正類的比率

(12)

真負率(TNR)是指所有真負類樣本中被預(yù)測為負類的比率

(13)

由于傳統(tǒng)評價指標(biāo)對少數(shù)類的不公平性，F(xiàn)-value作為新的評價指標(biāo)被提出，其既考慮了準確率，又考慮了召回率，公式如下

(14)

G-mean是另一種評價分類性能好壞的指標(biāo)，當(dāng)R值和TNR值同時變大時，G-mean值才會越高。公式如下

(15)

本文主要使用F-value、G-mean、Precision、Recall這幾個指標(biāo)來衡量算法的分類性能。

3.2 數(shù)據(jù)集描述

本文從國際機器學(xué)習(xí)標(biāo)準庫UCI中選取了Ionosphere、Abalone、Haberman、Vehicle、Ecoli、Yeast這6組不平衡數(shù)據(jù)集，來驗證所提算法的有效性。本文重在研究不平衡數(shù)據(jù)的二分類問題，將多數(shù)類數(shù)據(jù)集重構(gòu)為不平衡的二分類數(shù)據(jù)集。其中對于Abalone數(shù)據(jù)集中標(biāo)簽為“F”的樣本定義為少數(shù)類，其它類別合起來為多數(shù)類；Vehicle數(shù)據(jù)集中，將第一類視為少數(shù)類，其它均為多數(shù)類；Ecoli數(shù)據(jù)集中將“om”、”omL”和“pp”合并為少數(shù)類，其它類歸為多數(shù)類；Yeast數(shù)據(jù)集中將“MIT”視為少數(shù)類，其它為多數(shù)類。6組數(shù)據(jù)集的具體信息見表2。

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

3.3 實驗及分析

為了驗證本文所提算法BWBMS算法的有效性，選取SMOTE算法、Borderline-SMOTE算法(BSMOTE)、Random-SMOTE算法、NearMiss1算法、SMOTE+Tomek Links算法在8組數(shù)據(jù)集上做對比實驗，并選取SVM作為分類器，用F-value、G-mean、Precision和Recall作為評價指標(biāo)進行對比。實驗環(huán)境基于Anaconda 3.0中Jupyter Notebook軟件，所使用的對比算法除Random-SMOTE外均調(diào)用該軟件中imbalanced-learn程序包實現(xiàn)。經(jīng)過反復(fù)的大量實驗得出參數(shù)k=8， 其它參數(shù)通過接下來的參數(shù)敏感性分析進行選擇。

3.3.1 參數(shù)敏感性分析

本文所提的BWBMS算法需要確定采樣比重μ、 密度權(quán)重系數(shù)α和支持度權(quán)重系數(shù)β。 在此選取了6組公開數(shù)據(jù)集進行實驗，并以SVM為分類器，其中SVM的各參數(shù)均為Scikit-learn程序包的默認參數(shù)。此外用F-value、G-mean、Precision和Recall來評估各參數(shù)的影響。為了評估采樣比重μ的影響，對μ分別設(shè)置為0.5、0.6、0.7、0.8進行實驗，從表3可以看出，當(dāng)μ=0.7時，各指標(biāo)普遍表現(xiàn)較好。

密度權(quán)重系數(shù)α和支持度權(quán)重系數(shù)β分別表示密度權(quán)重和支持度權(quán)重在樣本選擇時的重要性，當(dāng)α和β越大時，說明稀疏區(qū)域且離邊界近的樣本更為重要，當(dāng)兩者相等時，認為密度權(quán)重和支持度權(quán)重一樣重要。下面設(shè)置了幾組對比實驗來評估不同權(quán)重系數(shù)值的影響。其中，設(shè)置μ=0.7， 且將 (α,β) 設(shè)置為(0.9,0.1)，(0.7,0.3)，(0.5,0.5)，(0.3,0.7)，(0.1,0.9)這5組分別進行實驗以選取更好的參數(shù)。實驗結(jié)果見表4，由此可知，當(dāng)α=β=0.5時，6組數(shù)據(jù)集上的各指標(biāo)整體性能表現(xiàn)較好。

表3 不同采樣比重μ下分類效果對比

3.3.2 實驗結(jié)果

根據(jù)前面的實驗對比，本文將實驗參數(shù)設(shè)置如下：k=8，μ=0.7,α=β=0.5， SVM分類器中的參數(shù)都是Scikit-learn程序包中的默認參數(shù)。表5和表6展示了6組數(shù)據(jù)集在本文采樣方法和其它采樣算法結(jié)合SVM分類器上的F-value值和G-mean值，實驗結(jié)果的最大值用黑色粗體表示。

從表5可以看出BWBMS算法在提高少數(shù)類分類精度上較為有效，大部分數(shù)據(jù)集在經(jīng)過本文所提出算法的處理再結(jié)合SVM分類器后，評價指標(biāo)值都高于文中其它采樣算法組合形式，這是因為BWBMS算法處理數(shù)據(jù)時，首先去除了噪聲樣本，能提高合成樣本質(zhì)量，再對邊界集中的少數(shù)類和多數(shù)類樣本作相應(yīng)的處理，賦予樣本支持度權(quán)重和密度權(quán)重，根據(jù)每個少數(shù)類樣本的重要程度采用不同的采樣方法和采樣倍率，在一定程度上降低了錯分邊界點而造成的不利影響，避免在樣本密集區(qū)繼續(xù)生成大量冗余樣本，雖然在Haberman數(shù)據(jù)集上的F-value值沒有取得最優(yōu)值，但較有些算法的F-value都有所提升。

從表6可以看出，BWBMS算法在Abalone和Vehicle數(shù)據(jù)集上的G-mean值沒有取得最優(yōu)值，但與其它算法相差不大。結(jié)合表5和表6來看，對Haberman數(shù)據(jù)集使用Random-SMOTE算法的結(jié)果優(yōu)于本文算法結(jié)果，這是由于Haberman數(shù)據(jù)集的邊界點重疊度較大，本文引入的邊界因子概念以及該算法設(shè)置的邊界閾值對于邊界點重疊較大的數(shù)據(jù)集可能有點不足，而使得三角形插值的Random-SMOTE算法更適合這個數(shù)據(jù)集。但是從整體上來看， BWBMS算法在提高少數(shù)類分類精度上優(yōu)于文中所提其它對比算法。

圖1繪制了6種算法在不同數(shù)據(jù)集上的打分情況變化曲線。其中，縱坐標(biāo)分別代表F-value、G-mean、Precision、Recall這4個評價指標(biāo)，表示分類得分情況，取值范圍為0-1，橫坐標(biāo)列舉了6種實驗對比算法。綜上可知，BWBMS算法優(yōu)于文中所對比的其它算法。

4 結(jié)束語

本文提出了不平衡數(shù)據(jù)中基于權(quán)重選擇的邊界混合采樣算法，既考慮了不同區(qū)域樣本重要性不同，又考慮了類內(nèi)樣本分布情況。將BWBMS算法與SVM分類器結(jié)合在一起，并與5種采樣算法進行實驗對比，該算法在大部分UCI公開數(shù)據(jù)集上表現(xiàn)較好，F(xiàn)-value、G-mean、Precision和Recall這4個評價指標(biāo)有所提升，驗證了該算法的有效性，可將該算法推廣至現(xiàn)實領(lǐng)域中來處理不平衡數(shù)據(jù)。未來，一方面研究更佳的邊界閾值的選取，另一方面本文僅結(jié)合了SVM分類器，將不同改進的分類算法與BWBMS相結(jié)合會產(chǎn)生什么樣的分類效果也是今后的研究方向。

表4 不同權(quán)重系數(shù)(α,β)下分類效果

表5 不同數(shù)據(jù)集在不同算法上的F-value性能對比

表6 不同數(shù)據(jù)集在不同算法上的G-mean性能對比

圖1 6種算法在不同數(shù)據(jù)集上的打分情況