傾斜數(shù)據(jù)集的分界修剪支持向量機

周華平 張貝貝 劉光宗

摘 要：傾斜數(shù)據(jù)集在實際應用中具有很高的價值，同時也是數(shù)據(jù)挖掘中的難點和熱點，因而得到越來越多的研究者的關注。通過給出的一種改進的支持向量機—DP-SVM，首先對數(shù)據(jù)集進行預處理、分類，再對它們采取相應的操作；然后根據(jù)混疊數(shù)據(jù)集中樣本的k個最近鄰的類別，并結(jié)合波動大小與其相應類限定值的關系，對該樣本點做相應的處理；最后根據(jù)副類支持向量與主類樣本數(shù)量之間的關系，決定對副類支持向量采取何種修剪策略，訓練得到其分類器。提出的分界修剪支持向量機由消除分類邊界混疊與支持向量修剪兩個主要處理部件構(gòu)成，并通過這兩個處理部件實現(xiàn)對分類邊界混疊數(shù)據(jù)的判別及兩類支持向量的修剪。實驗結(jié)果表明，DP-SVM是一種能夠較好地解決傾斜數(shù)據(jù)集分類邊界混疊問題的有效方法。

關鍵詞：傾斜數(shù)據(jù)集；混疊現(xiàn)象；支持向量；分界修剪支持向量機

中圖分類號： TP391 文獻標志碼：A

文章編號：1672-1098（2017）06-0008-07

Abstract：This paper was to present an improved Support Vector Machine-DP-SVM. Firstly data sets were preprocessed and classified， and then the corresponding operation were taken on them. Secondly， according to the category of the k nearest neighbors in aliasing data set and the relationship between the fluctuation and the corresponding category limited values， the sample point was processed correspondingly. Lastly， based on the relationship between the support vectors in negative category and the number of samples in major category， the pruning strategy was determined on the support vectors in negative category，as a result， the classifier was trained to be obtained. The proposed DP-SVM in this paper was composed of two main processing components， with one eliminating aliasing data at the classifying boundary and the other supporting the vectors pruning； and the two components could be used to realize the judgement of the aliasing data at the classifying boundary and support the vectors prunning of the two categories. The results show that DP-SVM is an effective method that can better solve the aliasing problem of skewed data sets.

Key words：skewed data sets； aliasing phenomenon； support vector； demarcation pruning-support vector machine

傾斜數(shù)據(jù)集在實際應用中具有很高的價值，同時也是數(shù)據(jù)挖掘中的難點和熱點，因而得到越來越多的研究者的關注。對傾斜數(shù)據(jù)集的處理，文獻[1-2]提出了許多處理效果較好的理論方法，但其主要是對分類邊界混疊數(shù)據(jù)做了簡單的刪除或?qū)χС窒蛄孔隽撕唵涡藜?，而未考慮這些數(shù)據(jù)對數(shù)據(jù)集分類正確率及主類分類精度的影響；因此對存在傾斜的數(shù)據(jù)集的分類正確率及主類的分類精度的處理效率尚有進一步提升的空間。為了降低數(shù)據(jù)集尤其是傾斜數(shù)據(jù)集分類邊界混疊數(shù)據(jù)對分類正確率以及主類分類精度的影響，本文提出分界修剪支持向量機（Demarcation Pruning-Support Vector Machine， DP-SVM）。

DP-SVM的工作過程：首先，對分類邊界混疊數(shù)據(jù)進行處理。計算每個分類邊界混疊數(shù)據(jù)的k個最近鄰，并判斷該樣本所屬類型：（1）k個最近鄰均屬同一類，若為大類，判斷其標準差與副類對應的邊界限定值關系，然后對其采取相應的操作；反之，則判斷其標準差與主類對應邊界限定值關系，并對其進行相應的處理。（2）k個最近鄰屬異類，若屬于副類樣本數(shù)量大于屬于主類樣本數(shù)量，舍棄該測試樣本；反之，對該測試樣本做加權(quán)操作，使其脫離分類邊界混疊區(qū)，進入主類區(qū)，使得主類樣本數(shù)量得以增多。其次，判斷分類邊界線性關系，如果非線性可分，選擇相應的核函數(shù)將其轉(zhuǎn)換到高維線性空間；反之，則無需轉(zhuǎn)換。最后，對支持向量進行修剪。計算副類的支持向量并判斷其代價敏感程度，同時根據(jù)其與主類樣本數(shù)量的關系分別進行操作：（1）主類樣本數(shù)量與副類支持向量數(shù)目基本均衡，求出這兩部分數(shù)據(jù)的最優(yōu)超平面，即該數(shù)據(jù)集的較適合的分類器；（2）主類樣本數(shù)量與副類支持向量數(shù)目相差較多，則需根據(jù)兩類樣本數(shù)量的大小情況分別進行處理，最后通過支持向量機訓練出合適的分類器。

1 相關工作

支持向量機（Support Vector Machine， SVM）由Boser，Guyon和Vapnik在COLT-92上首次提出，是統(tǒng)計學習理論中提出較晚的內(nèi)容，也是最實用的部分之一，目前仍處于不斷發(fā)展階段。

為了提高傾斜數(shù)據(jù)集的分類正確率，已提出了許多優(yōu)秀的相關研究方法。又因SVM主要用于二分類問題，且SVM可通過邊界寬度保證其泛化能力，故有許多研究方法依據(jù)于此。KE Hai-xin等提出ESVM數(shù)據(jù)集的重采樣方法，使用SVM算法在數(shù)據(jù)集上訓練得到?jīng)Q策邊界，并根據(jù)SVM的決策邊界刪除數(shù)據(jù)集中數(shù)據(jù)混疊部分和被錯誤分類的抽樣樣本，但該方法直接對決策邊界的混疊數(shù)據(jù)進行了刪除。文獻[3]提出的NN-SVM方法，根據(jù)測試樣本與其最近鄰的類別標識的異同，決定該測試樣本的取舍，但對邊界混疊數(shù)據(jù)類別標識只做了簡單的處理。文獻[4]在NN-SVM基礎上提出了KCNN-SVM，判斷測試樣本與其最近的訓練樣本的類別的異同，同類不做處理，反之則分別對其k個近鄰做均值比較，并刪除均值大者對應的樣本點，該方法忽略了邊界點對主類分類精度的影響。文獻[5]在其論文中提出通過軟間隔支持向量機與Boosting算法相結(jié)合的方式對傾斜數(shù)據(jù)集進行處理，該方法在平衡支持向量的同時，又防止了過擬合的產(chǎn)生，但未考慮到分類邊界混疊數(shù)據(jù)對分類正確率以及主類分類精度的影響。

SVM的構(gòu)建主要從兩個方面：最優(yōu)超平面和核函數(shù)。最優(yōu)超平面作為SVM分類時的最優(yōu)決策面，根據(jù)決策面是否線性可分，又分為線性最優(yōu)超平面和非線性最優(yōu)超平面，且可通過將非線性最優(yōu)超平面轉(zhuǎn)化為線性最優(yōu)超平面來求出其最優(yōu)決策面；核函數(shù)主要是解決低維空間向量難分的問題，通過將低維空間向量映射到高維空間的方式來解決[6-11]。

上述方法對分類邊界混疊數(shù)據(jù)只進行了簡單處理或只考慮到對分類器的修正，而忽視了該數(shù)據(jù)點與分類器的共同作用對分類正確率的影響，尤其是對傾斜數(shù)據(jù)集中主類分類精度的影響。鑒于此，本文針對傾斜數(shù)據(jù)集，提出了一種改進的支持向量機——分界修剪支持向量機。該方法通過將對分類邊界混疊數(shù)據(jù)的處理與對支持向量的修剪相結(jié)合的方式，來實現(xiàn)對傾斜數(shù)據(jù)集的處理，從而進一步提升分類正確率以及主類的分類精度。

2 DP-SVM

SVM在對數(shù)據(jù)集分類時會受到類間樣本分布不均衡的影響，造成分類決策面的偏移，導致最優(yōu)分類超平面向主類傾斜，從而使得主類的分類誤差率增加。然而，主類的分類精度對一些實際應用的影響又比較大，如醫(yī)療診斷、信用卡入侵檢測、電信客戶流失、垃圾郵件過濾及設備故障預測[12-18]等研究領域，因此不斷地提高傾斜數(shù)據(jù)集的分類正確率以及主類的分類精度就顯得尤為迫切。鑒于此，本文結(jié)合數(shù)據(jù)處理與支持向量數(shù)目修剪，提出了DP-SVM方法。

3）上述策略的實現(xiàn)算法

（4）實際分類中，尤其是傾斜數(shù)據(jù)集分類時兩類之間樣本數(shù)量的極大差異，必然會導致兩類支持向量數(shù)目的不平衡，而給分類正確率帶來極大的影響，為降低其負面作用，特通過引入松弛變量ξi與懲罰因子C來允許實際分類中存在一定的不準確性以及放棄一些重要的數(shù)據(jù)來減小分類器分類正確率的損失；

（5）為減少兩類之間的傾斜程度，比較NS支持向量數(shù)目與MS中樣本數(shù)量的關系，從而決定對NS的支持向量是否修剪。

本文基于（4）、（5）兩點，通過對NS使用支持向量修剪策略以及對MS采取相應操作方式來訓練分類器。

1）MS樣本數(shù)量與NS支持向量數(shù)目均衡

MS樣本數(shù)量與NS支持向量數(shù)目相差較小，故而MS支持向量數(shù)目稀少，因此引入軟間隔來允許MS中一些點到分類平面的距離可以不滿足必須大于某個值的要求，尋求出的這兩部分數(shù)據(jù)集的最優(yōu)超平面即是整個數(shù)據(jù)集的最優(yōu)超平面。本文使用的數(shù)據(jù)集屬此類情況，由抽取的隨機樣本組合而成。

2）MS樣本數(shù)量與NS支持向量數(shù)目相差較多

① MS樣本數(shù)量遠小于NS支持向量數(shù)目（此種情形多出現(xiàn)于MS樣本數(shù)量絕對稀少或數(shù)據(jù)集較?。擃惽闆r根據(jù)具體實驗數(shù)據(jù)，從以下兩種方法中選擇一個較適合的方法，對數(shù)據(jù)集進行處理。

a. 在MS數(shù)據(jù)集上使用SMOTE算法[20]，以增加MS樣本數(shù)量。但此過程中，需即刻驗證新生成點是否可被正確分類，若不可，刪除該點，反之則保留，直至MS樣本數(shù)量與NS支持向量數(shù)目大致均衡為止，再求出這兩部分數(shù)據(jù)的最優(yōu)分類器。

b. 仿照主成分分析方法，通過構(gòu)建NS分類器來判斷NS每個支持向量的重要程度，并為其賦予相應的權(quán)值，從中抽取權(quán)值較大者，并保持其數(shù)目與MS樣本數(shù)量大致相同，然后再根據(jù)兩者求出其最優(yōu)超平面。

② MS樣本數(shù)量多于NS支持向量數(shù)目且MS支持向量數(shù)目遠少于NS支持向量數(shù)目，此情形較常出現(xiàn)于大型或超大型傾斜數(shù)據(jù)集（傾斜比相對較?。Ｏ葘S中除其支持向量外的數(shù)據(jù)判斷其權(quán)重，再根據(jù)NS支持向量的數(shù)目，從MS中抽取出其支持向量及權(quán)重較大的樣本，并使之與NS支持向量數(shù)目盡量達到平衡，然后再根據(jù)這兩個修剪后的數(shù)據(jù)集求出最優(yōu)超平面。

本部分內(nèi)容主要是先對數(shù)據(jù)集進行初步分類，利用最遠距離，找出AS，并利用最近鄰、標準差、類限定值對AS進行訓練，得到處理后的訓練集TA。然后對其進行分類邊界判定并對非線性邊界進行轉(zhuǎn)換；最后再對支持向量進行修剪，最大程度上保證NS分類正確率的同時又提高了MS的分類精度。上述獲得分類器的方法稱為DP-SVM。

相對于SVM，DP-SVM具有以下優(yōu)點：

（1）分類正確率的提高

應用SVM之前對數(shù)據(jù)集A處理，得到訓練集TA，再對訓練集TA進行分類，從而使分類邊界的混疊現(xiàn)象得到很大的改觀；其次，將非線性可分的邊界通過核函數(shù)轉(zhuǎn)換為高維線性可分情況；最后，先對NS的支持向量加權(quán)，再根據(jù)MS樣本數(shù)量與NS支持向量數(shù)目的關系，分情況構(gòu)建相應的支持向量機，從而得到最優(yōu)超平面。DP-SVM使分類邊界得以簡化，泛化能力得到提升，同時分類正確率也得到提高，第四部分對此做了驗證。由實驗結(jié)果可知，DP-SVM是一種能夠解決傾斜數(shù)據(jù)集分類邊界混疊問題較為有效的方法。

（2）主類分類精度的提高

MS分類的精度與該類樣本數(shù)量及新增樣本數(shù)量有很大關系，一定程度上受到NS支持向量數(shù)目的影響。數(shù)據(jù)集A處理后，一定程度上增加了MS的樣本數(shù)量，使MS中樣本信息得到豐富。MS精度的提升幅度大于分類正確率的提升幅度。傾斜比越大，混疊現(xiàn)象越嚴重，MS精度提升的越多，因此有較高的應用參考價值。

當然，DP-SVM的上述優(yōu)點是以增加額外修剪處理時間為代價的，而此代價與分類正確率及MS分類精度的提高相比是可以接受的。當前計算機的處理速度很快，即使面對較大的傾斜數(shù)據(jù)集也能夠快速地對其做出處理。

3 實驗與分析

3.1 實驗環(huán)境

選擇使用的是HP型號機（Intel 340G，40G內(nèi)存），使用的軟件是Matlab71版本以及自己編制的數(shù)據(jù)集處理及支持向量修剪程序。數(shù)據(jù)集是Stat log（德國信用數(shù)據(jù)）1 000個、Stat log（澳大利亞信用批準）690個、信用篩選數(shù)據(jù)集690個，數(shù)據(jù)集來自數(shù)據(jù)堂，所用五維數(shù)據(jù)均已經(jīng)過脫敏處理。本文實驗數(shù)據(jù)是由數(shù)據(jù)集中的數(shù)據(jù)處理后組合而成。且本文的對比實驗，未考慮維度的這一因素，是鑒于維度在Boosting-SVM、DP-SVM、KCNN-SVM方法中更多的是增加了計算的復雜度，而對分類準確率、MS分類精度影響相對較小的原因。

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

θ-、θ+是實驗時推導出來的修訂值，隨著樣本集以及樣本數(shù)量的不同，θ-、θ+取值也會不同。實驗結(jié)果如圖4～圖5。由于所采用樣本集樣本數(shù)量有限，故實驗結(jié)果難免會有一定的偏差。圖4是在傾斜比、混疊程度一定時，樣本量對分類正確率及MS分類精度的影響。一定程度上樣本量越多，可獲取的樣本信息越豐富，分類的正確率也會越高，根據(jù)其趨勢圖可預測當樣本量達到一定程度時，其對分類正確率及MS分類精度的影響將趨于平緩。由圖4左圖可知，樣本量對分類正確率及MS分類精度在三種方法下，均有提高；但當樣本量不足（小于300）時，DP-SVM方法的分類正確率略優(yōu)于其他兩種方法，樣本量稍多（300～600）時，Boosting-SVM的分類正確率高于DP-SVM方法，主要受到DP-SVM中參數(shù)對混疊邊界的處理時的影響，以及支持向量在修剪時對其數(shù)目的影響，隨著樣本數(shù)量的增加，這一影響逐漸減小，DP-SVM方法分類正確率的優(yōu)勢逐漸凸顯。圖4右圖所示，是在樣本量不足（小于300）時，KCNN方法的分類精度高于其他兩種方法，源于其對樣本的簡單的k近鄰處理，隨著樣本量的增加，其優(yōu)勢逐漸減弱，同時DP-SVM對MS分類精度的提升明顯優(yōu)于該方法，在一定范圍內(nèi)Boosting-SVM方法對MS分類精度的提升優(yōu)于DP-SVM，但隨樣本量的增多，樣本信息的豐富，DP-SVM對MS分類精度的提升幅度更為顯著。圖5呈現(xiàn)出在樣本量、傾斜比一定時，混疊程度對分類正確率、MS分類精度的影響。假設無混疊時，樣本的分類正確率及MS分類精度均是最優(yōu)的?；殳B程度較小時，Boosting-SVM方法較DP-SVM方法優(yōu)良，主要是可處理的邊界混疊數(shù)據(jù)的數(shù)量有限，無法呈現(xiàn)出DP-SVM方法的優(yōu)勢。隨著混疊程度的加深，三種方法的分類正確率及MS分類精度均有所下降，但DP-SVM曲線較平穩(wěn)，對混疊狀況表現(xiàn)出較強的健壯性，在分類正確率及MS分類精度的下降程度上明顯低于另外兩種方法。

圖4 樣本數(shù)量對分類正確率及主類分類精度影響

圖5 混疊程度對分類正確率及主類分類精度影響

4 結(jié)論

DP-SVM是一種能夠解決傾斜數(shù)據(jù)集分類邊界混疊問題較為有效的方法，一定程度上解決了SVM由于類間數(shù)據(jù)分布不均衡造成的過學習和泛化能力弱的問題。

隨著數(shù)據(jù)量的增多，當傾斜比、混疊情況一定時，分類正確率提升緩慢，本文提到的方法略顯不足。鑒于分類正確率與抽樣方法關系更為密切，后續(xù)工作是探索選取何種抽樣方法，以便可以更有效地提高分類正確率以及MS的分類精度。

參考文獻：

[1] KE HAI-XIN，ZHANG XUE-GONG. Editing support vector machines[C]//Neural Networks， 2001 Proceedings， IJCNN01， International Joint Conference on IEEE，2001：

1 464-1 467.

[2] 黃久玲. 面向失衡數(shù)據(jù)集的集成學習分類方法及其應用研究[D].哈爾濱：哈爾濱理工大學，2015.

[3] 李紅蓮，王春花，袁保宗.一種改進的支持向量機NN-SVM[J].計算機學報，2003，26（8）：1 015-1 020.

[4] ZHANG SHI-RONG，ZHOU KUAN-JIU，TIAN YUAN.An improved NN-SVM based on k congener nearest neighbors classification Algorithm[C]//Knowledge Science， Engineering and Management. Springer Berlin Heidelberg，2007：550-555.

[5] BENJAMIN X WANG，NATHALIE JAPKOWICZ.Boosting support vector machines for imbalanced data sets[J]. Knowledge and Information Systems，2010，25（1）：1-20.

[6] 張學工.關于統(tǒng)計學習理論與支持向量機[J].自動化學報，2000，26（1）： 32-42.

[7] BURGES C J C.A tutorial on support vector machines for pattern recognition[J]. Data Mining and Knowledge Discovery，1998，2（2）：121-167.

[8] VAPNIK V N.An overview of statistical learning theory[J]. IEEE Transactions on Neural Networks，1999，10（5）： 988-999.

[9] Vapnik V N. Statistical learning theory[M]. New York： Wiley-Interscience，1998：2-200.

[10] KLAUS-ROBERT MULLER，SEBASTIAN MIKA，GUNNAR RTSCH，et al. An introduction to kernel-based learning algorithms[J]. IEEE Transaction on Neural Networks，2001，12（2）：181-201.

[11] XU JIE，TANG YUAN-YAN，ZOU BIN，et al. The generalization ability of SVM classification based on Markov sampling[J]. IEEE Trans. Cybem.，2015，45（6）：1 169-1 179.

[12] 吳慶忠，車峰遠，薛付忠.基于非平衡數(shù)據(jù)的癲癇發(fā)作預警模型研究[J].山東大學學報（醫(yī)學版），2012， 50（2）：141-148.

[13] MAJID A， ALIS S， IQBAL M. Prediction of human breast and colon cancers from imbalanced data using nearest neighbor and support vector machines[J]. Computer methods and programs in biomedicine， 2014， 113（2）：792-808.

[14] CHEN WEI-MIN，MA CHAO-QUN，MA LIN.Mining the customer credit using hybrid support vector machine technique[J]. Expert Systems with Applications，2009，36（4）：7 611-7 616.

[15] WEI WEI，LI JIN-JIU，CAO LONG-BING. Effective detection of sophisticated online banking fraud on extremely imbalanced data[J]. World Wide Web，2013，16（4）：449-475.

[16] 王春玉.非平衡數(shù)據(jù)集分類方法研究及其在電信行業(yè)中的應用[D].杭州：浙江大學，2011.

[17] DIAO LI-LI，YANG CHENG-ZHONG，WANG HAO. Training SVM email classifiers using very large imbalanced dataset[J]. Journal of experimental and theoretical artificial intelligence， 2012，24（2）：193-210.

[18] LIAO T Warren1. Classification of weld flaws with imbalanced class data[J]. Expert Systems with Applications，2008，35（3）：1 041-1 052.

[19] CHEN XUE-WEN，BYRON GERLACH，DAVID CASA-SENT.Pruning support vectors for imbalanced data classification[C]//2005 IEEE International Joint Conference on Neural Networks. Montreal，Quebec，Canada， 2005：1 883-1 888.

[20] JOSEY MATHEW，LUO MING，CHEE KHIANG PANG，et al. Kernel-based SMOTE for SVM classification of imbalanced datasets[C]// Industrial Electronics Society， IECON 2015-41st Annual Conference of the IEEE. Yokohama， 2015：001 127-001 132.

（責任編輯：李 麗）