不平衡數(shù)據(jù)中基于權(quán)重的邊界混合采樣

姜新盈，江開(kāi)忠，嚴(yán) 濤，王舒梵

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

0 引 言

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

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

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

1 相關(guān)工作

1.1 不平衡數(shù)據(jù)分類(lèi)問(wèn)題

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

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

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

1.2.1 SMOTE算法

SMOTE算法[14]流程如下：

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

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

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

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

(1)

1.2.2 Random-SMOTE算法

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

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

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

(2)

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

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

(3)

2 BWBMS算法

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

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

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

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

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

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

d(x,y)≤dk(x)

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

d(x,y)

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

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

(4)

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

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

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

(5)

邊界因子的大小反映了該點(diǎn)周?chē)鷺颖镜姆植迹鶕?jù)以上定義，可以通過(guò)設(shè)置閾值σ0并與σ(x) 進(jìn)行比較來(lái)判斷樣本點(diǎn)是否為邊界點(diǎn)。

2.2 基于邊界因子的邊界集識(shí)別

定義4 邊界點(diǎn)：對(duì)于任意x∈M， 當(dāng)σ(x)>σ0時(shí)，稱(chēng)樣本點(diǎn)x為邊界點(diǎn)，否則為非邊界點(diǎn)。其中

(6)

2.3 對(duì)邊界集少數(shù)類(lèi)樣本的處理

(7)

(8)

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

(9)

總權(quán)重公式為

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

(10)

2.4 非邊界集樣本的處理

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

2.5 BWBMS算法描述

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

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

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

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

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

步驟2.2 計(jì)算每個(gè)樣本點(diǎn)的k-離群度τ(x);

步驟2.3 計(jì)算每個(gè)樣本點(diǎn)的邊界因子σ(x)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 評(píng)價(jià)指標(biāo)

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

表1 混淆矩陣

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

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

(11)

查準(zhǔn)率(Precision)是指所有預(yù)測(cè)為正類(lèi)的樣本中，實(shí)際上也是正類(lèi)的比率

(12)

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

(13)

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

(14)

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

(15)

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

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

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

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

3.3 實(shí)驗(yàn)及分析

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

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

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

密度權(quán)重系數(shù)α和支持度權(quán)重系數(shù)β分別表示密度權(quán)重和支持度權(quán)重在樣本選擇時(shí)的重要性，當(dāng)α和β越大時(shí)，說(shuō)明稀疏區(qū)域且離邊界近的樣本更為重要，當(dāng)兩者相等時(shí)，認(rèn)為密度權(quán)重和支持度權(quán)重一樣重要。下面設(shè)置了幾組對(duì)比實(shí)驗(yàn)來(lái)評(píng)估不同權(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組分別進(jìn)行實(shí)驗(yàn)以選取更好的參數(shù)。實(shí)驗(yàn)結(jié)果見(jiàn)表4，由此可知，當(dāng)α=β=0.5時(shí)，6組數(shù)據(jù)集上的各指標(biāo)整體性能表現(xiàn)較好。

表3 不同采樣比重μ下分類(lèi)效果對(duì)比

3.3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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