一種新的近鄰密度SVM不平衡數(shù)據(jù)集分類算法

劉悅婷，孫偉剛，張發(fā)菊

(蘭州文理學(xué)院 傳媒工程學(xué)院，甘肅 蘭州 730000)

分類是對(duì)輸入訓(xùn)練樣本分析、學(xué)習(xí)后得到?jīng)Q策模型，然后預(yù)測(cè)未知樣本，它已成為機(jī)器學(xué)習(xí)領(lǐng)域的重要研究方向。目前，已有眾多經(jīng)典算法可以實(shí)現(xiàn)平衡數(shù)據(jù)的良好分類效果，如支持向量機(jī)法、模糊分類算法、代價(jià)敏感學(xué)習(xí)法和決策樹(shù)算法等[1]。但是，現(xiàn)實(shí)中許多應(yīng)用領(lǐng)域存在明顯的不均衡數(shù)據(jù)，如網(wǎng)絡(luò)入侵、商業(yè)欺詐、文本分類等數(shù)據(jù)集[2-3]，人們很重視少數(shù)類的信息。在分類判決時(shí)，傳統(tǒng)分類器總會(huì)偏向多數(shù)類，把少數(shù)類分到多數(shù)類，導(dǎo)致錯(cuò)分率很高，分類器性能不理想[4]。因此，如何提高不平衡數(shù)據(jù)的分類性能已成為眾多學(xué)者研究的熱點(diǎn)[5]。

目前，不平衡數(shù)據(jù)分類的方法主要從數(shù)據(jù)層面和算法層面實(shí)現(xiàn)。數(shù)據(jù)層面完成數(shù)據(jù)預(yù)處理，包括欠采樣、過(guò)采樣和混合采樣。欠采樣是通過(guò)減少多數(shù)類樣本使數(shù)據(jù)集均衡，可能造成信息丟失，降低分類器的性能[6-7]。過(guò)采樣是通過(guò)復(fù)制、插值增加少數(shù)類樣本使數(shù)據(jù)集均衡，但會(huì)造成過(guò)擬合，增加分類器的空間和時(shí)間消耗[8-9]?；旌喜蓸邮菍⑶凡蓸雍瓦^(guò)采樣有效結(jié)合從而平衡數(shù)據(jù)集的分布。

算法層面是對(duì)分類算法本身進(jìn)行操作，包括對(duì)傳統(tǒng)算法的改進(jìn)、眾多算法的集成等。改進(jìn)算法主要通過(guò)調(diào)整分類邊界、改變概率密度等措施修改算法在數(shù)據(jù)集上的偏置，使得決策面偏向于少數(shù)類，提高少數(shù)類的分類性能[10]。文獻(xiàn)[11]提出先由支持向量機(jī)(Support Vector Machine，SVM)確定近鄰數(shù)目，再由K最近鄰分類算法(k-Nearest Neighbor，KNN)完成分類；文獻(xiàn)[12]提出加權(quán)支持向量機(jī)(Weighted Support Vector Machine，WSVM)算法，按照聚類權(quán)重定性選擇出對(duì)分類決策面起作用大小的多數(shù)類樣本，將選取的多數(shù)類樣本與少數(shù)類完成SVM組織訓(xùn)練。文獻(xiàn)[12-13]提出不平衡數(shù)據(jù)集的特點(diǎn)：兩類數(shù)據(jù)數(shù)量差別很大，類分布比較均勻；兩類數(shù)據(jù)數(shù)量相當(dāng)，但類分布差別較大，如一類比較集中，一類比較分散；兩類數(shù)據(jù)數(shù)量和類分布差別都很大。傳統(tǒng)分類方法都是基于第一種情況的研究，對(duì)后面兩種情況不適用。文獻(xiàn)[14]提出基于實(shí)例重要性的方法解決不平衡數(shù)據(jù)分類問(wèn)題，但忽略了類內(nèi)不均勻?qū)Ψ诸惥鹊挠绊?。本文綜合文獻(xiàn)[13-15]的思想，提出基于近鄰密度的平衡法，新的近鄰密度支持向量機(jī)算法(New Neighbor Density Support Vector Machine，NNDSVM)，按照多數(shù)類每個(gè)樣本K鄰域范圍內(nèi)的密度值選擇出對(duì)分類決策面起作用的樣本，將訓(xùn)練集按照樣本作用大小分別與相同數(shù)目的少數(shù)類結(jié)合進(jìn)行重新組織訓(xùn)練。

1 SVM算法

基于統(tǒng)計(jì)學(xué)習(xí)理論的SVM是建立在結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理上，尋求最優(yōu)分類面。對(duì)于原始特征空間中不可分的問(wèn)題，通過(guò)核函數(shù)映射到更高維的特征空間中，轉(zhuǎn)化為求解線性約束的二次規(guī)劃問(wèn)題。

給定樣本(xi,yi)，i=1,2,…,n，xi∈Rn，yi∈{-1,+1}，基本SVM利用最大間隔尋找決策分類超平面，決策判別函數(shù)為

f(x)=WTx+b。

(1)

式中，W∈Rn為權(quán)向量，b∈R為閾值。

構(gòu)造SVM優(yōu)化模型

s·t·yi(WTxi+b)≥1-ξi，

ξi≥0，i=1,2,…,n。

(2)

式中，ξi為松弛變量，反映樣本被錯(cuò)分的程度；C為懲罰常數(shù)，控制對(duì)錯(cuò)分樣本的懲罰程度。

為求解式(2)二次規(guī)劃問(wèn)題，構(gòu)造Lagrange函數(shù)

(3)

式中，αi、βi為L(zhǎng)agrange算子，式(3)分別對(duì)W、b、ξi求偏導(dǎo)，并置零，得到式(2)的對(duì)偶問(wèn)題

(4)

根據(jù)KTT條件，得

(5)

求得判別函數(shù)為

(6)

式中，K(x,xi)為核函數(shù)，將高維特征空間兩個(gè)訓(xùn)練樣本的內(nèi)積(x·xi)用輸入空間樣本的核函數(shù)代替，即

K(x,xi)=(x·xi)

(7)

2 NNDSVM算法

2.1 問(wèn)題分析

現(xiàn)實(shí)中許多不平衡數(shù)據(jù)集具有分布不均勻，類間邊界模糊等特點(diǎn)，或者在數(shù)據(jù)空間不同區(qū)域具有不同的密度，導(dǎo)致傳統(tǒng)分類算法難以實(shí)現(xiàn)理想的結(jié)果。通過(guò)圖1數(shù)據(jù)集說(shuō)明密度不均勻問(wèn)題，數(shù)據(jù)集中，a、b、c分別代表3個(gè)簇所在的范圍，由圖知密度關(guān)系a>b>c，傳統(tǒng)的分類算法很難找到統(tǒng)一的鄰域半徑來(lái)發(fā)現(xiàn)3個(gè)類別a、b、c。若鄰域半徑取值較大，a和b容易被認(rèn)定為一個(gè)類；反之c被視為噪聲。要解決該問(wèn)題，簡(jiǎn)單方法是人為設(shè)定鄰域半徑值，然而在數(shù)據(jù)集密度分布情況未知的情況下，人為設(shè)定鄰域半徑值有很大的難度，因此對(duì)分布不均勻數(shù)據(jù)集的正確分類造成很大困難。

一般來(lái)說(shuō)，想得到整個(gè)數(shù)據(jù)集密度分布情況十分困難，所以本文算法考慮通過(guò)樣本的K鄰域密度值確定樣本所在的區(qū)域。而樣本的密度值可通過(guò)樣本到K鄰域內(nèi)所有樣本的平均距離的倒數(shù)來(lái)計(jì)算；平均距離越小，密度越大，說(shuō)明樣本間越密集，樣本所在區(qū)域接近簇類中心；反之，平均距離越大，密度越小，樣本間越稀疏，樣本所在區(qū)域接近類邊界。邊界區(qū)域密度值最小，很容易發(fā)生錯(cuò)分，嚴(yán)重影響分類精度，因而對(duì)分類結(jié)果“作用最大”?？拷吔绲臉颖臼菃卫龜?shù)據(jù)或有助于克服噪聲數(shù)據(jù)的影響，因而對(duì)分類結(jié)果“作用較大”，其余區(qū)域的樣本對(duì)分類結(jié)果“作用較小”。因此采用平均距離的倒數(shù)標(biāo)識(shí)樣本的密度信息，從而判定樣本在類的區(qū)域。

圖1 不均勻分布數(shù)據(jù)集Fig.1 The uneven distribution datase

2.2 樣本近鄰密度

定義：樣本近鄰密度。給定包含m維、q個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集Z，對(duì)任意zi(zi∈Z，1≤i≤q)有K個(gè)近鄰為zi(k)，zi與zi(k)的歐氏距離定義為式(8)，樣本zi的K近鄰密度定義為式(9)。

(8)

(9)

由式(9)知，zi的近鄰密度為zi到K個(gè)近鄰歐氏距離和的平均值的倒數(shù)。ρi越大，說(shuō)明對(duì)象zi的近鄰越密集；反之，ρi越小，對(duì)象zi的近鄰越稀疏。

2.3 本文算法流程

本文提出一種新的近鄰密度SVM不平衡數(shù)據(jù)集分類算法。該算法先計(jì)算多數(shù)類中每個(gè)樣本K近鄰范圍內(nèi)的密度值，再根據(jù)該密度值的大小分別選出多數(shù)類邊界區(qū)域、靠近邊界區(qū)域的樣本，并且所選樣本數(shù)目與少數(shù)類數(shù)目相同，保證樣本的均衡性。對(duì)分類結(jié)果“作用最大”的是多數(shù)類的邊界區(qū)域的樣本，對(duì)分類結(jié)果“作用較大”的是靠近邊界區(qū)域的樣本，對(duì)分類結(jié)果“作用較小”的是剩余區(qū)域的樣本。因此先從多數(shù)類樣本中選取與少數(shù)類數(shù)目相等的密度值最小、次最小的兩部分樣本，再將選取樣本分別與少數(shù)類樣本完成SVM初始分類，從而保證訓(xùn)練樣本數(shù)量的平衡性，最后用所得的支持向量機(jī)和剩余的多數(shù)類樣本對(duì)初始分類器迭代優(yōu)化。

NNDSVM算法的流程：

Step1：初始化變量。P為少數(shù)類樣本集合，p為少數(shù)類樣本總數(shù)；N為多數(shù)類樣本集合，n為多數(shù)類樣本總數(shù)；Norder為多數(shù)類樣本按密度值降序排列的集合；Norder_behind為Norder集合中最后p個(gè)樣本組成的集合；Norder_behindf為Norder集合中次最后p個(gè)樣本組成的集合；Norder_other為Norder集合中剩余樣本組成的集合。

Step2：對(duì)于訓(xùn)練樣本，分離出多數(shù)類樣本集合N。

Step3：從集合N中任選樣本ni，用式(8)計(jì)算子集半徑r。以ni為中心，r為半徑的子集為SC(ni)，統(tǒng)計(jì)SC(ni)子集中每個(gè)樣本的局部密度。依次類推，統(tǒng)計(jì)集合N中所有樣本的局部密度，以密度值降序排列集合N中的所有樣本，得到集合Norder。

Step4：判斷p、n的關(guān)系。若p2p，則認(rèn)為訓(xùn)練樣本是不平衡樣本，轉(zhuǎn)入Step5。

Step5：集合P和Norder_behind組成的兩類平衡集合MPN1，用MPN1訓(xùn)練SVM，得到支持向量機(jī)SPN1，多數(shù)類支持向量個(gè)數(shù)nneg1，少數(shù)類支持向量個(gè)數(shù)npos1。

Step6：集合P和Norder_behindf組成的兩類平衡集合MPN2，用MPN2訓(xùn)練SVM，得到支持向量機(jī)SPN2，多數(shù)類支持向量個(gè)數(shù)nneg2，少數(shù)類支持向量個(gè)數(shù)npos2。

Step7：在不影響分類精度的同時(shí)，使用支持向量集取代訓(xùn)練樣本集進(jìn)行訓(xùn)練可以降低訓(xùn)練時(shí)間。由支持向量機(jī)SPN1、SPN2和Norder_other組成集合MPN3，從MPN3中提取全部支持向量(npos1+npos2+nneg1+nneg2)個(gè)，提取與支持向量相同數(shù)目的多數(shù)類，完成SVM分類器迭代訓(xùn)練，并完成支持向量的更新。當(dāng)滿足T<0.9時(shí)，返回到 Step4執(zhí)行；當(dāng)滿足T≥0.9時(shí)，迭代訓(xùn)練停止，輸出分類結(jié)果。

(10)

3 實(shí)驗(yàn)分析

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

針對(duì)不均衡數(shù)據(jù)集的特點(diǎn)，傳統(tǒng)分類器的性能指標(biāo)存在嚴(yán)重的缺陷。經(jīng)研究，學(xué)者們提出以下指標(biāo)：不均衡數(shù)據(jù)集中少數(shù)類別的樣本為正類P，多數(shù)類別的樣本為負(fù)類N。其中，

TP：實(shí)際為正類被預(yù)測(cè)為正類的樣本個(gè)數(shù)；

FN：實(shí)際為正類被預(yù)測(cè)為負(fù)類的樣本個(gè)數(shù)；

FP：實(shí)際為負(fù)類被預(yù)測(cè)為正類的樣本個(gè)數(shù)；

TN：實(shí)際為負(fù)類被預(yù)測(cè)為負(fù)類的樣本個(gè)數(shù)。

(1)查全率：少數(shù)類樣本的正確率。

(2)特異度：多數(shù)類樣本的正確率。

(3)查準(zhǔn)率：被正確分類的正類樣本占被分為正類的全部樣本比值。

(4)G-mean：綜合考慮少數(shù)類和多數(shù)類兩類樣本的分類性能，若分類器分類偏向于某一類，則會(huì)影響另一類的分類正確率。

(5)F-measure：是查全率和查準(zhǔn)率兩個(gè)評(píng)價(jià)方式的結(jié)合，能有效反應(yīng)分類器對(duì)少數(shù)類樣本分類性能的敏感程度。

(6)ROC曲線下與坐標(biāo)軸圍成的面積(Area Under Curve，AUC)：計(jì)算接收者操作特征(Receiver Operating Characteristic， ROC)曲線下的面積作為不平衡數(shù)據(jù)的評(píng)價(jià)方式，它能全面地描述分類器在不同判決閾值時(shí)的性能。

3.2 各算法實(shí)驗(yàn)結(jié)果比較

為驗(yàn)證本文算法的可行性，用Matlab2014a編寫程序，選人工數(shù)據(jù)集Dataset和UCI數(shù)據(jù)集為實(shí)驗(yàn)對(duì)象，將測(cè)試結(jié)果與文獻(xiàn)[9]主動(dòng)學(xué)習(xí)SMOTE的非均衡數(shù)據(jù)分類(Active learning SMOTE Support Vector Machine，ALSMOTE-SVM)算法、文獻(xiàn)[12]中WSVM算法和SVM算法比較。圖2所示Dataset是密度不均勻的人工數(shù)據(jù)集，包含1018個(gè)數(shù)據(jù)點(diǎn)。從UCI庫(kù)中選取不平衡率較輕Iris、Glass Identification數(shù)據(jù)集和不平衡率較高Spectf Heart、Ecoli數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，如表1所示。SVM分類器參數(shù)設(shè)置：選取高斯函數(shù)為核函數(shù)，核寬度=1，懲罰因子C= 1000，初始α=0.2，實(shí)驗(yàn)迭代運(yùn)行20次，4種算法在5個(gè)數(shù)據(jù)集上運(yùn)行得到G-mean、F-measure結(jié)果如表2所示。在人工數(shù)據(jù)集Dataset、Glass Identification和Spectf Heart上運(yùn)行4種算法，得AUC變化曲線如圖3所示。

圖2 人工數(shù)據(jù)集DatasetFig.2 Artificial dataset

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

表2 實(shí)驗(yàn)結(jié)果比較

由表2可知對(duì)于不平衡率較輕的Glass Identification、Iris數(shù)據(jù)集，每個(gè)樣本成為支持向量的可能性較大，故本文算法較ALSMOTE-SVM、WSVM算法在F-measure、G-mean性能值提高得較小。對(duì)于不平衡率較高的人工數(shù)據(jù)集Dataset、Spectf Heart和Ecoli數(shù)據(jù)集，SVM分類器較易忽略少數(shù)類，因而分類性能較差。ALSMOTE-SVM和WSVM算法針對(duì)不平衡數(shù)據(jù)集適用性良好，但是較本文算法差，因?yàn)楸疚乃惴ㄍㄟ^(guò)局部密度將多數(shù)類進(jìn)行劃分排序，保證每次參與分類器訓(xùn)練的多數(shù)類與少數(shù)類個(gè)數(shù)平衡，而且充分考慮類邊界的樣本信息，因此本文改進(jìn)策略使分類器的精度有較大提高。

(a)Dataset

(b)Glass Identification

(c)Spectf Heart圖3 4種算法在不同數(shù)據(jù)集上運(yùn)行對(duì)應(yīng)的AUC值Fig.3 AUC curves of 4 algorithms on the different artificial dataset

AUC值，即ROC曲線與橫軸圍成區(qū)域的面積值，AUC大小可以反應(yīng)分類器的性能。曲線越接近(0，1)點(diǎn)，且與橫軸圍成面積越大，分類器效果越好。由圖3可以看出：對(duì)于均勻性較差的人工數(shù)據(jù)集Dataset，NNDSVM算法得到AUC值為0.960，與SVM模型獲得AUC值0.765要高出很多；對(duì)于不平衡性較輕的Glass Identification數(shù)據(jù)集，SVM算法的AUC值為0.878，其余3種改進(jìn)SVM算法的AUC值都較高，說(shuō)明改進(jìn)SVM算法分類器性能良好，但NNDSVM算法性能更好，從而證明基于局部密度劃分多數(shù)類與相同數(shù)目的少數(shù)類完成SVM分類器訓(xùn)練的可行性；對(duì)于不平衡性較重的Spectf Heart數(shù)據(jù)集，SVM算法的AUC值為0.797，其余3種改進(jìn)SVM算法的AUC值相差較大，NNDSVM算法得到AUC值為0.967，說(shuō)明用基于局部密度劃分多數(shù)類，將邊界區(qū)域的樣本定義為對(duì)分類器“作用最大”，將靠近邊界的樣本定義為對(duì)分類結(jié)果“作用較大”的策略對(duì)于不均勻平衡數(shù)據(jù)集的分類效果良好。當(dāng)4條不同曲線不相互交錯(cuò)的時(shí)候，位于上方ROC曲線對(duì)應(yīng)分類器的性能優(yōu)于位于下方分類器的性能，從曲線分布可知對(duì)于每個(gè)數(shù)據(jù)集，NNDSVM建立的分類器性能優(yōu)于其他算法模型分類器的性能，驗(yàn)證NNDSVM算法的可行性。

4 結(jié)論

傳統(tǒng)分類方法對(duì)不均勻分布、邊界信息模糊的不平衡數(shù)據(jù)集識(shí)別性能較低，本文提出一種改進(jìn)的SVM算法，即NNDSVM。該算法先依據(jù)子集半徑將多數(shù)類劃分成多個(gè)子類，再根據(jù)子類內(nèi)每一個(gè)樣本的局部密度值的大小分別選出多數(shù)類邊界區(qū)域、靠近邊界區(qū)域的樣本，且所選樣本數(shù)目與少數(shù)類數(shù)目相同，保證訓(xùn)練樣本的平衡性。將選取樣本分別與少數(shù)類樣本完成SVM初始分類，最后用所得的支持向量機(jī)和剩余的多數(shù)類樣本對(duì)初始分類器迭代優(yōu)化。實(shí)驗(yàn)結(jié)果表明NNDSVM對(duì)不平衡數(shù)據(jù)集分類性能良好，證明了該算法的可行性和有效性。如何更好地協(xié)調(diào)相關(guān)參數(shù)的取值及降低時(shí)間復(fù)雜度是今后需要進(jìn)一步研究的目標(biāo)。