基于新改進的SVM不平衡數(shù)據(jù)集分類算法

劉悅婷，李曉霞，李思璇，朱旭博

（蘭州文理學院傳媒工程學院，甘肅 蘭州 730000）

分類是對輸入訓練樣本分析、學習后得到?jīng)Q策模型，然后預測未知樣本，它已成為機器學習領域的重要研究方向。目前，已有眾多經(jīng)典算法可以實現(xiàn)平衡數(shù)據(jù)的良好分類效果，如支持向量機法、模糊分類算法、代價敏感學習法和決策樹算法等[1]。但是，現(xiàn)實中許多應用領域存在明顯的不均衡數(shù)據(jù)，如網(wǎng)絡入侵、商業(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]。混合采樣是將欠采樣和過采樣有效結合從而平衡數(shù)據(jù)集的分布。

算法層面是對分類算法本身進行操作，包括對傳統(tǒng)算法的改進、眾多算法的集成等。改進算法主要通過調整分類邊界、改變概率密度等措施修改算法在數(shù)據(jù)集上的偏置，使得決策面偏向于少數(shù)類，提高少數(shù)類的分類性能[10]。Wang Chinheng等[11]提出先由 SVM（Support Vector Machines）確定近鄰數(shù)目，再由 KNN（K-Nearest Neighbors）算法完成分類；王超學等[12]提出 WSVM（WeightTechnologyandbasedgrading Support Vector Machines）算法，按照聚類權重定性選擇出對分類決策面起作用大小的多數(shù)樣本，將選取的多數(shù)類樣本與少數(shù)類完成SVM組織訓練。文獻[12-13]提出不平衡數(shù)據(jù)集的特點：兩類數(shù)據(jù)數(shù)量差別很大，類分布比較均勻；兩類數(shù)據(jù)數(shù)量相當，但類分布差別較大，如一類比較集中，一類比較分散；兩類數(shù)據(jù)數(shù)量和類分布差別都很大。傳統(tǒng)分類方法都是基于第一種情況的研究，對后面兩種情況不適用。楊揚、李善平[14]提出基于實例重要性的方法解決不平衡數(shù)據(jù)分類問題，但忽略了類內不均勻對分類精度的影響。

受文獻[13-14]的啟發(fā)，本文提出基于樣本密度的平衡法，依據(jù)多數(shù)類每個樣本在距離臨界區(qū)域內的密度值思選擇出對分類決策面起作用大小的樣本，將訓練集按照樣本作用大小分別與相同數(shù)目的少數(shù)類結合進行重新組織訓練，通過實驗將本文方法與 ALSMOTE-SVM、WSVM算法和 SVM算法完成了比較，驗證了本文算法的優(yōu)越性。

1 SVM算法

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

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

為求解式（2）二次規(guī)劃問題，構造lagrange函數(shù)

式（3）分別對 求偏導，并置零，得到式（2）的對偶問題

求得判別函數(shù)為

2 基于新改進的SVM算法（IMSVM）

2.1 問題分析

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

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

圖1 不平衡數(shù)據(jù)集Fig.1 Imbalanced dataset

2.2 樣本的密度值

給定包含 維、 個樣本的數(shù)據(jù)集 ，樣本 到樣本 （ ∈ 、∈ ）的歐氏距離為式（8）。

定義：樣本距離臨界區(qū)域的密度值。樣本 距離臨界區(qū)域的密度值 義為

的距離小于等于 的樣本個數(shù)，即以 為中心，到 的距離小于等于 的樣本數(shù)目。

2.3 本文算法流程

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

IMSVM算法的流程為：

Step1：初始化變量。 少數(shù)類樣本集合， 少數(shù)類樣本總數(shù)； 多數(shù)類樣本集合，多數(shù)類樣本總數(shù)；order多數(shù)類樣本按密度值降序排列的集合；order_behind是order集合中最后 個樣本組成的集合；order_behindf是order集合中次最后 個樣本組成的集合；order_other是order集合中剩余樣本組成的集合。

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

Step3：從集合 中任選樣本 ，用式（9）計算樣本距離臨界區(qū)域的密度值。依次類推，計算集合N中所有樣本的密度值，以密度值降序排列集合 中的所有樣本，得到集合order。

Step4：判斷 的關系。若 ＜ ≤2 ，可認為訓練樣本是平衡樣本，用傳統(tǒng)SVM訓練樣本，得到分類結果；若 ＞2 ，可認為是不平衡樣本，轉入Step5。

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

Step6：集合P和order_behindf組成的兩類平衡集合PN2，用PN2訓練 SVM，得到支持向量機PN2，多數(shù)類支持向量個數(shù)neg2，少數(shù)類支持向量個數(shù)pos2。

Step7：在不影響分類精度的同時，使用支持向量集取代訓練樣本集進行訓練可以降低訓練時間。由支持向量機PN1、PN2和order_other組成集合 MPN3，從

PN3中提取全部支持向量（pos1+pos2+neg1+neg2）個，提取與支持向量相同數(shù)目的多數(shù)類，完成SVM分類器迭代訓練，并完成支持向量的更新。當滿足式（10）的 <0.9時，返回到 Step4執(zhí)行；當滿足 ≥0.9時，迭代訓練停止，輸出分類結果。

3 實驗分析

3.1 評價指標

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

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

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

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

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

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

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

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

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

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

（6）AUC：計算 ROC（Receiver Operating Characteristic）曲線下的面積作為不平衡數(shù)據(jù)的評價方式，它能全面地描述分類器在不同判決閾值時的性能。

3.2 各算法實驗結果比較

為驗證本文算法的可行性，用Matlab2014a編寫程序，選人工數(shù)據(jù)集Dataset和UCI數(shù)據(jù)集為實驗對象，將測試結果與文獻[9]ALSMOTE-SVM（Active Learning Smote Support Vector Machines）、文獻[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ù)取值如表2所示，實驗迭代運行20次，4種算法在5個數(shù)據(jù)集上運行得到G-mean、F-measure和CPU運行時間（表 3）。

在人工數(shù)據(jù)集 Dataset、GlassIdentification和Spectf Heart上運行4種算法，得AUC變化曲線分別如圖3-5所示。

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

表1 實驗數(shù)據(jù)集Tab.1 Experimental dataset

表2 參數(shù)取值Tab.2 Parameter value

表3 實驗結果比較Tab.3 Comparison of experimental results

由表3可知：

（1）對于不平衡性較輕的 Glass Identification、Iris數(shù)據(jù)集，每個樣本成為支持向量的可能性較大，故本文算法較 ALSMOTE-SVM、WSVM算法在 F-measure、G-mean性能值提高地較小，CPU運行時間相差較小。

（2）對于不平衡率較高的人工數(shù)據(jù)集、Spectf Heart和Ecoli數(shù)據(jù)集，SVM分類器較易忽略少數(shù)類，因而分類性能較差。ALSMOTE-SVM和WSVM算法針對不平衡數(shù)據(jù)集適用性良好，但是較本文算法差，因為本文算法通過樣本密度將多數(shù)類進行劃分排序，保證每次參與分類器訓練的多數(shù)類與少數(shù)類個數(shù)平衡，而且充分考慮類邊界的樣本信息。

（3）對于 Spectf Heart數(shù)據(jù)集，本文算法較其他算法的 G-mean提高了 5.59%，F(xiàn)-measure提高了6.43%，CPU運行時間降低了13%，表明本文改進策略使分類器的精度有較大的提高。

圖3 4種算法在Dataset人工數(shù)據(jù)集上運行對應的AUC曲線Fig.3 The AUC curves of the four algorithms on the artificial dataset

圖4 4種算法在Glass Identification數(shù)據(jù)集上運行對應的AUC曲線Fig.4 The AUC curves of the four algorithms on the Glass Identification dataset

圖5 4種算法在Spectf Heart數(shù)據(jù)集上運行對應的AUC曲線Fig.5 The AUC curves of the four algorithms on the Spectf Heart dataset

AUC值，即ROC曲線與橫軸圍成區(qū)域的面積值，AUC大小可以反應分類器的性能。曲線越接近（0，1）點，且與橫軸圍成面積越大，分類器效果越好。由圖3-5可以看出：

（1）對于均勻性較差的人工數(shù)據(jù)集Dataset，IMSVM算法得到AUC值為0.968，與SVM模型獲得AUC值0.77要高出很多。

（2）對于不平衡性較輕的Glass Identification數(shù)據(jù)集，SVM算法的AUC值為0.877，其余3種改進SVM算法的AUC值都較高，說明改進SVM算法分類器性能良好，但IMSVM算法性能更好，從而證明在距離臨界區(qū)域內的樣本密度值劃分多數(shù)類與相同數(shù)目的少數(shù)類完成SVM分類器訓練的可行性。

（3）對于不平衡性較重的Spectf Heart數(shù)據(jù)集，SVM算法的AUC值為0.80，其余3種改進SVM算法的AUC值相差較大，IMSVM算法得到AUC值為0.971，說明用基于密度劃分多數(shù)類，將邊界區(qū)域的樣本定義為對分類器“作用最大”，將靠近邊界的樣本定義為對分類結果“作用較大”的策略對于不均勻平衡數(shù)據(jù)集的分類效果良好。

（4）當4條不同曲線不相互交錯的時候，位于上方ROC曲線對應分類器的性能優(yōu)于位于下方分類器的性能，從曲線分布可知對于每個數(shù)據(jù)集，IMSVM建立的分類器性能優(yōu)于其他算法模型分類器的性能，驗證IMSVM算法的可行性。

3.3 對算法結果的影響

的選擇決定樣本局部密度的大小，如果取得太大或太小，都會降低 的區(qū)分度，嚴重影響分類精度。為證明 的大小對實驗結果的影響，本文采用不同大小的 在不同的數(shù)據(jù)集Dataset、Glass Identification和Spectf Heart上實驗，結果如圖6-8所示。

圖6 在人工數(shù)據(jù)集Dataset上，F(xiàn)-measure隨 變化曲線Fig.6 F-measure variation curve with dcon the artificial dataset

圖7 在Glass Identification數(shù)據(jù)集上，F(xiàn)-measure隨變化曲線Fig.7 F-measure variation curve with dcon the Glass Identification dataset

圖8 在Spectf Heart數(shù)據(jù)集上，F(xiàn)-measure隨 變化曲線Fig.8 F-measure variation curve with on the Spectf Heart dataset

從圖6-8可知：不同數(shù)據(jù)集下 對分類結果的影響不一樣。人工數(shù)據(jù)集Dataset和Spectf Heart數(shù)據(jù)集都有最優(yōu)的 ，人工數(shù)據(jù)集Dataset比Spectf Heart數(shù)據(jù)集不均勻性高，因此所得F-measure曲線變化幅度更大些。Glass Identification數(shù)據(jù)集不均勻性較輕，分類結果F-measure為0.985，基本不受 的影響。所以針對不同的問題應選擇合適的 參數(shù)。

4 小結

（1）本文針對傳統(tǒng)分類方法對不均勻分布、邊界信息模糊的不平衡數(shù)據(jù)集識別性能較低，提出基于新改進的SVM算法，即IMSVM。該算法先計算每個樣本在距離臨界區(qū)域內的密度值，再根據(jù)密度值的大小分別選出多數(shù)類邊界區(qū)域、靠近邊界區(qū)域的樣本，且所選樣本數(shù)目與少數(shù)類數(shù)目相同，保證訓練樣本的平衡性。將選取樣本分別與少數(shù)類樣本完成SVM初始分類，最后用所得的支持向量機和剩余的多數(shù)類樣本對初始分類器迭代優(yōu)化。

（2）實驗結果表明IMSVM對不平衡數(shù)據(jù)集分類性能良好，證明了該算法的可行性和有效性。如何更好地協(xié)調相關參數(shù)的取值和降低時間復雜度是今后需要進一步研究的目標。