改進SVM不平衡數(shù)據(jù)分類的IGWOSMOTE方法*

馬漢達，朱 敏

(江蘇大學(xué)計算機科學(xué)與通信工程學(xué)院,江蘇 鎮(zhèn)江 212013)

1 引言

由Vapnik[1]提出的傳統(tǒng)分類器支持向量機SVM(Support Vector Machine)，具有堅實的統(tǒng)計學(xué)理論基礎(chǔ)、簡易的實現(xiàn)方式以及優(yōu)秀的泛化能力和分類性能，目前在信用評估[2]、文本分類[3]和人臉識別[4]等領(lǐng)域中應(yīng)用非常廣泛。SVM在處理多分類[5]問題時，往往因誤分及不可分的問題導(dǎo)致最終分類精度不樂觀，其中誤分的根本原因是少數(shù)類和多數(shù)類樣本分布失衡，少數(shù)類即某個類樣本規(guī)模遠小于其他類的樣本規(guī)模，反之，樣本規(guī)模較大的則稱為多數(shù)類，學(xué)術(shù)界普遍將少數(shù)類和多數(shù)類也分別叫做正類和負類。不對稱的數(shù)據(jù)量造成了分類超平面對負類的傾斜，而待測樣本被所有子分類器都判為負類則是導(dǎo)致不可分的原因。因此，如何提高SVM對于不平衡數(shù)據(jù)的識別率及整體分類準(zhǔn)確率是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的一大難點。

少數(shù)類合成過采樣技術(shù)SMOTE(Synthetic Minority Over-sampling TEchnique)[6]從數(shù)據(jù)層角度出發(fā)，通過數(shù)據(jù)集重構(gòu)的方式來均衡少數(shù)類和多數(shù)類的樣本數(shù)量，以線性插值為原則隨機復(fù)制少數(shù)類樣本，這樣可以避免算法過擬合，從而更有利于SVM分類器的學(xué)習(xí)。眾多學(xué)者的研究表明，SMOTE算法在不平衡數(shù)據(jù)分類問題上能取得良好的分類效果。Chen等[7]使用SMOTE改進SVM算法以適用于混合類型和不平衡數(shù)據(jù)，實驗表明使用了SMOTE方法的SVM分類器在平均準(zhǔn)確率、查準(zhǔn)率和查全率上均能取得不錯的分類結(jié)果。Prachuabsupakij等[8]提出的KSMOTE(K Synthetic Minority Over-sampling TEchnique)方法將數(shù)據(jù)集分為2個子集，并分別對這2個子集使用過采樣和欠采樣方法，構(gòu)建SVM的“一對一”和“一對多”分類模型進行預(yù)測實驗，最終在ROC曲線下的面積AUC和F_measure這2個指標(biāo)上體現(xiàn)了該方法的有效性。古平等[9]將SVM作為元分類器，基于錯分原理提出新的混合采樣方法，將樣本劃分為危險樣本和安全樣本，并分別進行樣本約除和SMOTE過采樣，對比實驗表明新方法在提高少數(shù)類識別率上具有較好的性能。然而，在實際中對少數(shù)類樣本的識別率往往易受到噪聲樣本[10]的干擾。這些噪聲可能是原數(shù)據(jù)集中的噪聲樣本，也可能是基于噪聲樣本再次生成的新噪聲樣本，都會使少數(shù)類更不易被識別到，從而造成分類精度更低的局面。另外，SMOTE算法對每一個少數(shù)類樣本均采用了相同的合成方式及采樣倍率，因此可能會產(chǎn)生偏離或者遠離決策域的無效樣本[10]，這樣既無益于分類器學(xué)習(xí)也加重了算法運行負擔(dān)。目前已有很多學(xué)者基于這2點對SMOTE算法進行改進,Han等[11]提出的Borderline-SMOTE方法只對處于決策域的正類樣本進行過采樣，主要是對當(dāng)前正類樣本和與其相鄰的正類與負類樣本的個數(shù)進行比較，若相鄰正類樣本數(shù)多則表明該樣本處于決策域內(nèi)，反之則視為無效樣本予以摒棄。劉雨康等[12]引入分區(qū)的理念把樣本空間劃分為密集區(qū)(即多數(shù)類)與稀疏區(qū)(即少數(shù)類)，先后將傳統(tǒng)SVM算法和K-最近鄰算法用于密集區(qū)和稀疏區(qū)的分類，使得各SVM子分類器中的噪聲樣本數(shù)明顯減少，這樣不僅分類更準(zhǔn)確，而且算法運行時間更短。霍玉丹等[13]提出了GASMOTE(Genetic Algorithm Synthetic Minority Over-sampling TEchnique)過采樣方法，利用GA循環(huán)優(yōu)化輸出最優(yōu)的采樣倍率取值組合進行樣本過采樣，使SMOTE采樣倍率取值具備一定的靈活性。以上研究均對SMOTE的局限性和盲目性做出了相應(yīng)改進，但仍存在以下缺陷：

(1)當(dāng)樣本規(guī)模較大時，忽略了特征維度對樣本識別的貢獻能力[14]。通常情況下少數(shù)特征對樣本的識別率貢獻較大，存在冗余特征時則對樣本識別貢獻較小。

(2)忽略了SVM中有關(guān)參數(shù)的取值在參與采樣過程中的相關(guān)性和重要性，一般可以為少數(shù)類和多數(shù)類分配不同的懲罰權(quán)重C，例如當(dāng)少數(shù)類樣本遠少于多數(shù)類樣本時，可為少數(shù)類樣本賦予較大的C值，但是這種操作可能使初始數(shù)據(jù)的概率分布發(fā)生偏離。

本文針對以上問題做出相應(yīng)改進。首先，使用改進的灰狼優(yōu)化算法IGWO(Improved Gray Wolf Algorithm)[15]進行SVM的參數(shù)尋優(yōu)及特征選擇，將二者作為構(gòu)成灰狼初始種群的因素之一，并為其設(shè)計適應(yīng)度函數(shù)，通過灰狼優(yōu)化過程獲得達到最佳分類準(zhǔn)確率的最優(yōu)參數(shù)組合及特征向量子集，為少數(shù)類樣本和多數(shù)類樣本分別賦予較大和較小的懲罰權(quán)重，從而避免原始數(shù)據(jù)分布出現(xiàn)嚴(yán)重偏差。其次，引入隨機的采樣倍率組合參與灰狼種群的初始化過程，利用IGWO的自適應(yīng)搜索能力輸出最佳采樣倍率組合。本文提出的基于改進灰狼算法的過采樣方法——IGWOSMOTE(Improved Gray Wolf Optimization Synthetic Minority Over-sampling TEchnique)，旨在緩解因初始數(shù)據(jù)中存在的冗余特征使得少數(shù)類樣本易被誤判為噪聲樣本，造成負類樣本規(guī)模更小的現(xiàn)象，以及改善因人為定義采樣系數(shù)而導(dǎo)致SMOTE算法生成無效樣本的問題。最終減小傳統(tǒng)SVM多分類問題受不平衡數(shù)據(jù)的影響，提升對少數(shù)類數(shù)據(jù)的識別率及SVM的整體分類準(zhǔn)確率。

2 相關(guān)方法

2.1 支持向量機

s.t.yi(ωxi+b)≥1-ξi,i=1，2，…，l

(1)

其中,ω為超平面的法向量;b為超平面的偏置;ξi為松弛變量;C為懲罰因子。

以徑向基核函數(shù)為例，在數(shù)學(xué)模型中可通過式(2)和式(3)所示的目標(biāo)函數(shù)和決策函數(shù)的優(yōu)化來描述尋找最優(yōu)分類超平面的過程[5]，式(4)給出了其約束條件。

目標(biāo)函數(shù)：

(2)

決策函數(shù)：

(3)

約束條件：

(4)

2.2 SMOTE算法

為了解決不平衡數(shù)據(jù)的分類問題，Chawla等[6]從合成少數(shù)類樣本的角度出發(fā),設(shè)計了一種過采樣算法。SMOTE算法的思想是，采用線性插值的方式在近鄰少數(shù)類樣本之間手動增加新的少數(shù)類樣本個數(shù)，從而盡可能達到數(shù)據(jù)平衡的狀態(tài)，算法步驟如下：

(1)對于每個少數(shù)類樣本S，利用歐幾里得距離計算出S與其他少數(shù)類樣本間的距離，正序排列得到前k個近鄰樣本，k值一般設(shè)為5。

(2)根據(jù)采樣倍率N，從k個近鄰中隨機選取一個樣本S′,在S與S′之間插入采用式(5)所示的線性插值公式合成的新樣本Snew。

Snew=S+(S′-S)×rand(0，1)

(5)

其中，rand(0，1)為0到1之間的隨機數(shù)。

(3)將新增的樣本加入到原訓(xùn)練集中再次進行分類器學(xué)習(xí)。

2.3 灰狼優(yōu)化算法

Mirjalili等[15]受灰狼群體活動中的領(lǐng)導(dǎo)階層和捕食體制啟示，將狼群分為4種階層，其中以α狼為首領(lǐng)，β狼次之，δ狼又次之，其余底層狼群為Ω，由4種灰狼共同完成狩獵過程。在灰狼優(yōu)化算法的數(shù)學(xué)模型中，由稱為第1優(yōu)解、第2優(yōu)解、第3優(yōu)解的α,β,δ來鎖定目標(biāo)解向量，剩余解向量稱為Ω，并根據(jù)前3者所在位置進行移動，最終完成獵物的攻擊。狩獵過程的數(shù)學(xué)表達[16]如下所示：

(1)包圍。

包圍行為的數(shù)學(xué)表達如式(6)～式(7)所示：

D=|G·Xp(t)-X(t)|

(6)

X(t+1)=Xp(t)-A·D

(7)

其中，D表示灰狼和獵物的距離;t表示當(dāng)前迭代次數(shù);A和G表示參數(shù)向量，A=2a·r1-a，G=2×r2;向量r1和r2是大小在[0,1]的隨機數(shù);Xp表示獵物的位置向量;X表示某個灰狼個體的位置向量;a為收斂因子，其值在每一次迭代中從2到0線性遞減。

(2)捕獲。

當(dāng)狼群成功包圍獵物后，狩獵通常由α狼帶領(lǐng)，β狼和δ狼則跟隨并更新位置，輔助α狼追捕獵物。為了從數(shù)學(xué)模型上模擬這種活動，可以假設(shè)α(第1優(yōu)解)狼、β(第2優(yōu)解)狼和δ(第3優(yōu)解)狼均對獵物的潛在位置(全局最優(yōu)解)有更好的了解，因此整個狼群中每個灰狼個體的位置更新可由式(8)確定：

(8)

X1=Xα-A1·Dα

(9)

X2=Xβ-A2·Dβ

(10)

X3=Xδ-A3·Dδ

(11)

Dα=|G1·Xα-X(t)|

(12)

Dβ=|G2·Xβ-X(t)|

(13)

Dδ=|G3·Xδ-X(t)|

(14)

其中，Xα，Xβ和Xδ為第t次迭代時排列前3的最優(yōu)候選解,A1，A2和A3表示參數(shù)向量,G1，G2和G3也表示參數(shù)向量。

在基本灰狼優(yōu)化算法中，灰狼位置向量的各維取值是連續(xù)型的，而在特征選擇方法中灰狼取值必須為0或1，所以需要使灰狼的位置二元化[17]。在IGWOSMOTE方法中，各灰狼位置向量的組成是特征子集和SVM參數(shù)，長度為二者之和，因此當(dāng)灰狼改變位置時，則使用式(15)二元化位置：

(15)

其中，Xi,j是指狼群中第i只狼的位置向量的第j維的值。此時灰狼位置向量的二元化設(shè)置已完成，可用于特征選擇方法中。

3 IGWOSMOTE+SVM分類方法

3.1 IGWOSMOTE方法

首先，基本灰狼算法易受局部與全局尋優(yōu)性能不均衡的影響，其中參數(shù)a呈線性收斂，這并不符合非線性問題中的優(yōu)化搜索過程。郭振洲等[18]引入了非線性收斂因數(shù)策略，降低a前期的衰減水平，則有利于算法發(fā)現(xiàn)全局最優(yōu)解，提高后期衰減水平，此時a能跳出全局并精準(zhǔn)找到局部最優(yōu)解。邢尹等[19]指出GWO搜索性能也受a的衰減程度影響，為了在均衡全局和局部性能的同時加快收斂速度，引入了衰減階數(shù)，本文將引用前者的理論基礎(chǔ)，其收斂因子a的計算方法如(16)所示：

(16)

其中,t是當(dāng)前迭代次數(shù);tmax是最大迭代次數(shù);p是取值在[0,10]的整數(shù)衰減階數(shù);e是自然底數(shù)。衰減階數(shù)越大,則a的收斂速度越快。

其次,本文研究的是利用灰狼算法進行SVM參數(shù)(即懲罰因子和核函數(shù)參數(shù))優(yōu)化和特征選擇，即為SVM不同類別樣本分配不同權(quán)重和對樣本進行降維處理，同時引入隨機采樣倍率的取值子集生成新樣本。獲取相應(yīng)最優(yōu)參數(shù)的問題可以轉(zhuǎn)化成IGWO求解函數(shù)最大值的優(yōu)化問題，其定義如式(17)所示：

max:y=f(X)

s.t.Rmin≤Ri≤Rmax,i=1，2，…，M,

X=(Ci，γi，f1，f2，…，fN，R1，R2，…，RM)

(17)

其中，X為決策向量，即灰狼初始種群的組成形式;N為特征總數(shù);f(·)為適應(yīng)度函數(shù)，即少數(shù)類樣本的最終預(yù)測精度;Rmin和Rmax分別為少數(shù)類樣本的采樣倍率Ri的最小取值和最大取值[20];M為決策空間的維度，即少數(shù)類樣本的個數(shù)。SVM參數(shù)組Ci和γi的定義如式(18)和式(19)所示：

Ci=(Cmax-Cmin)×r+Cmin，i=1，2，…，M

(18)

γi=(γmax-γmin)×r+γmin，i=1，2，…，M

(19)

其中，r為[0,1]的隨機數(shù);Cmax和Cmin分別表示懲罰權(quán)重C的最大值和最小值;γmax和γmin分別表示核函數(shù)參數(shù)γ的最大值和最小值。特征向量子集的構(gòu)成為(f1，f2，…，fN)，每一個元素為0或者1，若為0則代表該特征沒有被選擇，若為1則代表該特征被選擇。采樣倍率子集[13]由采樣倍率上下界之間的隨機整數(shù)值組成，采樣倍率Ri的定義如式(20)所示：

Ri=round(Rmin+(Rmax-Rmin)×

rand(0，1))

(20)

其中，灰狼個體在Ri的最小取值和最大取值之間取隨機整數(shù)，并由round(·)函數(shù)進行四舍五入操作。

3.2 IGWOSMOTE+SVM分類方法具體步驟

IGWO算法把本文所述相關(guān)參數(shù)作為SVM模型輸入并進行一系列的優(yōu)化訓(xùn)練，輸出結(jié)果為最優(yōu)的采樣后訓(xùn)練集。

步驟1生成初始灰狼種群，灰狼個體位置由C、γ、fi及Ri組合構(gòu)成，定義種群規(guī)模及最大迭代次數(shù)。

步驟2SVM根據(jù)灰狼個體位置對訓(xùn)練集進行學(xué)習(xí)，以分類準(zhǔn)確率作為灰狼個體位置的適應(yīng)度值。

步驟3利用IGWO算法計算適應(yīng)度值并降序排列，為狼群劃分等級。

步驟4更新參數(shù)a、A和G，重新計算所有灰狼個體位置。

步驟5判斷當(dāng)前是否達到最大迭代次數(shù)，若是則返回IGWO算法的全局最優(yōu)解，即C、γ、fi及Ri組合，否則跳轉(zhuǎn)至步驟2繼續(xù)優(yōu)化。

步驟6將利用最優(yōu)的C、γ、fi及Ri組合重新采樣獲得的訓(xùn)練集加載到SVM模型。

3.3 適應(yīng)度函數(shù)設(shè)計

IGWO需要根據(jù)每次迭代中的各灰狼位置計算對應(yīng)的適應(yīng)度值，該函數(shù)值是反映IGWO算法中灰狼個體優(yōu)劣性的重要評價指標(biāo)，是銜接IGWO算法與本文要解決的具體優(yōu)化問題的關(guān)鍵步驟。在IGWOSMOTE分類方法中，灰狼個體位置中有多種參數(shù)組合參與，其中包括特征向量參數(shù)，因此本文采用分類精度和所選特征數(shù)來構(gòu)造適應(yīng)度函數(shù)，如式(21)和式(22)所示：

(21)

(22)

其中，A表示分類精度;N是特征總數(shù);L表示選中特征的數(shù)量,L≤N;權(quán)重參數(shù)α0和β0用來協(xié)調(diào)A與N縮減，α0∈[0，1]，β0=1-α0;right表示被正確分類的樣本數(shù);total表示總樣本數(shù)。fitness值越大對應(yīng)的灰狼個體越優(yōu)秀，在劃分灰狼種群的過程中，適應(yīng)度函數(shù)值排列前3的優(yōu)解(灰狼個體)將在下一次迭代中起到種群位置更新的導(dǎo)向作用。

4 實驗與結(jié)果分析

4.1 實驗環(huán)境

本文實驗平臺是Windows 10操作系統(tǒng)，Intel Core CPU i5-8265U，8 GB RAM；開發(fā)環(huán)境是Matlab 2016b，LibSVM(3.24)，選用的是徑向基核函數(shù)。

4.2 數(shù)據(jù)集準(zhǔn)備

為了驗證IGWOSMOTE分類方法的有效性，本文基于UCI中6個標(biāo)準(zhǔn)不平衡數(shù)據(jù)集進行實驗分類，表1列出了各數(shù)據(jù)集的特征字段。

Table 1 Dataset feature fields

4.3 評價方法

傳統(tǒng)的SVM模型使用分類準(zhǔn)確率[21]作為模型分類結(jié)果的評價指標(biāo)。準(zhǔn)確率主要涉及正確分類樣本個數(shù)和總樣本數(shù)2個部分，所以更適用于評估平衡數(shù)據(jù)集。在不平衡數(shù)據(jù)集的分類結(jié)果評估中，可能出現(xiàn)多數(shù)類樣本的準(zhǔn)確率偏高，少數(shù)類樣本的準(zhǔn)確率偏低甚至為0的情況，導(dǎo)致對少數(shù)類的分類性能考察不到位。本文采用F_measure[22]和G_mean[23]作為評價指標(biāo)，兩者均需要基于混淆矩陣進行計算，混淆矩陣如表2所示。

Table 2 Confusion matrix

根據(jù)表2可得到以下常見的評價指標(biāo)：

(23)

(24)

(25)

(26)

(27)

查準(zhǔn)率(precision)對應(yīng)于實際正類被正確預(yù)測的樣本數(shù)(TP)與所有被預(yù)測為正類的樣本數(shù)的比值，查全率(recall)對應(yīng)于正確預(yù)測的正類樣本數(shù)與正確預(yù)測的每一類樣本數(shù)的比值。由式(26)可知，F(xiàn)_measure由precision和recall共同參與評價，且后者兩個比值需同時增大才能保證前者指標(biāo)值也增大，避免了2個比值發(fā)生偏向。G_mean是一個幾何平均值，根據(jù)少數(shù)類樣本和多數(shù)類樣本的分類精度計算得到，同樣需要2種樣本的分類正確率都高才能保證分類器實現(xiàn)公平度量。因此，F(xiàn)_measure可以較好地評價少數(shù)類的分類精度，G_mean可以用于評價整體數(shù)據(jù)集的分類效果。

4.4 實驗結(jié)果與分析

實現(xiàn)SVM算法并比較SMOTE+SVM方法、GASMOTE+SVM方法和IGWOSMOTE+SVM方法的分類性能。實驗基于Matlab平臺，實驗結(jié)果經(jīng)五折交叉驗證獲得。初始灰狼種群規(guī)模設(shè)置為30，C和γ取值上限均為10，下限均為0.001，迭代次數(shù)最大設(shè)為100。表3和表4分別列出了SVM算法、SMOTE+SVM方法、GASMOTE+SVM方法和IGWOSMOTE+SVM方法在6個數(shù)據(jù)集上的F_measure和G_mean結(jié)果。

表3和表4的實驗結(jié)果顯示，IGWOSMOTE+SVM方法較其他3種方法的少數(shù)類分類性能更佳。由F_measure值可以看出，IGWOSMOTE+SVM能有效提高少數(shù)類的分類精度，在6個數(shù)據(jù)集上的預(yù)測平均值比SMOTE+SVM提高了6.3個百分點，比GASMOTE+SVM提高了1.27個百分點。由G_mean值可以看出，IGWOSMOTE+SVM分別在Glass6、Haberman、Pima這3個數(shù)據(jù)集上取得最優(yōu)的整體分類效果，其平均G_mean值為83.79%，較SMOTE+SVM和GASMOTE+SVM分別增長了2.07個百分點和1.55個百分點。

Table 3 F_measure values of

Figure 1 Fitness curves of three methods and SVM algorithm on Yeast3 dataset圖1 3種方法和SVM算法在Yeast3數(shù)據(jù)集上的適應(yīng)度值曲線

Table 4 G_mean values of different methods based on SVM

IGWOSMOTE+SVM方法采取IGWO自適應(yīng)搜索策略能獲取最優(yōu)的懲罰參數(shù)、核函數(shù)參數(shù)、特征子集和采樣倍率組合，本文根據(jù)2種樣本的不平衡率對最優(yōu)懲罰參數(shù)進行權(quán)重分配，其中以不平衡率為倍率隨機增大對少數(shù)類的懲罰權(quán)重，權(quán)重越接近不平衡率，IGWOSMOTE+SVM方法越能達到較優(yōu)的訓(xùn)練效果。從整體實驗數(shù)據(jù)來看，新方法降低了人為設(shè)置采樣倍率對分類性能的影響，通過最優(yōu)特征子集和采樣倍率子集對訓(xùn)練集的篩選及重構(gòu)，可以在一定程度上緩解后期新樣本合成之前產(chǎn)生無效樣本的現(xiàn)象。另外，灰狼算法自身的局限性可能是導(dǎo)致IGWOSMOTE+SVM方法在其中3個數(shù)據(jù)集上的G_mean值沒有達到最大值的因素。

為了觀察和研究IGWOSMOTE+SVM、GASMOTE+SVM、GWOSMOTE+SVM及SVM在6個UCI數(shù)據(jù)集上的算法優(yōu)化過程，還在實驗過程中繪制了相應(yīng)的適應(yīng)度值曲線圖，根據(jù)6個數(shù)據(jù)集的優(yōu)化過程可知，IGWOSMOTE+SVM相較其他方法收斂速度更快，同時也能獲得較優(yōu)的適應(yīng)度值。由于篇幅限制，本文以Yeast3數(shù)據(jù)集為例，圖1記錄了上述3種方法和SVM算法的適應(yīng)度值迭代過程，從上到下依次為IGWOSMOTE+SVM、GASMOTE+SVM、GWOSMOTE及SVM的適應(yīng)度值曲線。從圖1中可以看出，IGWOSMOTE+SVM的適應(yīng)度值曲線在第100次迭代后達到完全收斂，最優(yōu)適應(yīng)度值為98.09%，通過比較可知，IGWOSMOTE+SVM方法明顯具有更快速的收斂速度和最優(yōu)的適應(yīng)度值。所以，IGWOSMOTE+SVM方法較其他算法來說更有效，也更有利于在自適應(yīng)搜索空間中尋得最優(yōu)解決方案，進而增強最終預(yù)測能力。

5 結(jié)束語

本文結(jié)合灰狼優(yōu)化算法與SMOTE算法，提出了基于灰狼特征選擇和智能設(shè)置采樣倍率的IGWOSMOTE方法，實驗結(jié)果表明了IGWOSMOTE+SVM方法的可行性。利用IGWOSMOTE方法訓(xùn)練得到的SVM模型分類器在提高少數(shù)類數(shù)據(jù)的分類精度上有了比較大的改觀，且在整體數(shù)據(jù)集上也獲得了較穩(wěn)定的分類性能，改善了SVM對不平衡本身的敏感度，有利于解決失衡數(shù)據(jù)的分類問題。然而，對于分類器參數(shù)及采樣過擬合的問題，IGWOSMOTE方法仍有縮短算法運行時間及提高分類精度的需求，未來將針對灰狼算法易陷入局部最優(yōu)解、影響過采樣方法的問題作進一步研究。