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

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

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

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

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

1 SVM算法

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

給定樣本(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為松弛變量，反映樣本被錯分的程度；C為懲罰常數(shù)，控制對錯分樣本的懲罰程度。

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

(3)

式中，αi、βi為Lagrange算子，式(3)分別對W、b、ξi求偏導，并置零，得到式(2)的對偶問題

(4)

根據(jù)KTT條件，得

(5)

求得判別函數(shù)為

(6)

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

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

(7)

2 NNDSVM算法

2.1 問題分析

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

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

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

2.2 樣本近鄰密度

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

(8)

(9)

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

2.3 本文算法流程

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

NNDSVM算法的流程：

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

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

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

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

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

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

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

(10)

3 實驗分析

3.1 評價指標

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

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

FN：實際為正類被預測為負類的樣本個數(shù)；

FP：實際為負類被預測為正類的樣本個數(shù)；

TN：實際為負類被預測為負類的樣本個數(shù)。

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

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

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

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

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

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

3.2 各算法實驗結(jié)果比較

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

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

表1 實驗數(shù)據(jù)集信息

表2 實驗結(jié)果比較

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

(a)Dataset

(b)Glass Identification

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

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

4 結(jié)論

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