針對非平衡數據分類的新型模糊SVM模型

蔡艷艷,宋曉東

(北京航空航天大學經濟管理學院,北京 100191)

針對非平衡數據分類的新型模糊SVM模型

蔡艷艷,宋曉東

(北京航空航天大學經濟管理學院,北京 100191)

提出了一種新的模糊支持向量機模型——非平衡數據分類的支持向量機模型,通過改進懲罰函數,降低模型對于含有噪聲點的非平衡樣本數據的敏感性,并采用網格搜索算法來確定各個支持向量機模型中參數的優化取值.研究結果表明,非平衡數據分類的支持向量機模型對非平衡樣本數據進行分類的效果優于其他方法,不僅總體判別精度較高,也提高了少數類樣本的判別精度,取得了較好的改進效果.

支持向量機;分類;非平衡數據集;噪聲;懲罰函數

支持向量機(Support Vector Machine,SVM)實質上是一種基于統計學習理論的新型機器學習方法,最早由Vapnik等[1]提出,具有嚴格的數學基礎和良好的泛化能力.目前,支持向量機已經被廣泛地應用到人臉識別[2]、故障檢測[3]、信用評價[4]和文本分類[5]等諸多領域,并且在解決平衡樣本數據分類問題方面的性能優越.然而,傳統支持向量機存在過度擬合的問題,對噪聲樣本點十分敏感.此外,在二分類問題中,傳統支持向量機將每個樣本點絕對視為某一類,沒有考慮到樣本點可能存在的雙重屬性,也導致模型判別精度下降[6-7].

Lin等[8]構建了模糊支持向量機(Fuzzy Support Vector Machine,FSVM)模型,根據樣本點對所在類的不同重要性分配給每個樣本點不同的權重值,來降低支持向量機對于噪聲點的敏感性.進一步,考慮到樣本點可能同時隸屬于兩類樣本,Wang等[9]構建了雙隸屬支持向量機(Bilateral-weighted Fuzzy Support Vector Machine,B-FSVM)模型,通過采用隸屬度函數對每個樣本點隸屬于兩類樣本的程度進行刻畫.然而,模糊支持向量機和雙隸屬支持向量機模型與傳統支持向量機類似,仍然沒有消除樣本數據非平衡對于分類精度的影響.非平衡數據集是指至少存在一個類別的樣本數相對其他類別更少的數據集.在非平衡的數據集下,傳統支持向量機和各種形式的模糊支持向量機對兩類樣本的分類效果會不同,即樣本數量較少的一類(負類)判別精度較差,而樣本數量較多的一類(正類)判別精度較高.這不僅影響整體的分類性能,而且由于對樣本數量較少的一類的判別精度有時更為重要,導致分類模型的應用價值下降.例如,醫療領域的疾病識別,患病的樣本數通常比未患病樣本數少得多,但對于患病類樣本(少類)的正確判別無疑更為重要.

為了降低支持向量機對于樣本數據非平衡的敏感性,提高支持向量機的判別精度,特別是提高對于樣本數量較少一類的判別精度,國內外學者進行了相關的研究,并取得了一定的成果.總體來說,這些方法可以分為構建平衡樣本和修正支持向量機模型兩大類.其中,構建平衡樣本主要是采用一定的方法使得兩類樣本重新平衡,包括減少多數樣本采樣[10]與增加少數樣本采樣[11]兩種;修正支持向量機模型主要是通過修正算法本身,降低算法對于樣本非平衡的敏感程度,包括SMOTE模型[12-13]和z-SVM模型[14]等.關于處理樣本數據非平衡的各種方法及其優缺點,在文獻[15-16]中都有著較為詳細的綜述.

1 支持向量機與雙隸屬支持向量機

1.1 支持向量機的基本模型

支持向量機的核心思想是在兩類樣本之間尋找一個最優分類面,這個最優分類面要保證分類精度高且分類間隔最大.

假設樣本集z={(xi,yi),i=1,…,l},其中,輸入向量代表不同指標;yi代表樣本類別.對于二分類問題,所有樣本被分為A、B兩類,以yi∈{-1,+1},i=1,…,l來表示,每一個樣本xi只對應一個yi.若yi=+1,則將xi劃為A類;若yi=-1,則將xi劃為B類.

假設最優分類面方程為ωTφ(x)+b=0,則對于yi=+1,ωTφ(xi)+b≥1;對于yi=-1, ωTφ(xi)+b≤-1.因此,可以得到

其中,φ(*):Rn→Rd,表示映射函數,可將低維不可分的樣本集非線性地映射到高維空間,從而能夠線性可分.式中,使等號成立的樣本點xi被稱為支持向量.

由最優分類面ωTφ(x)+b=0,可以計算出兩類樣本的分類間隔為因此,要保證分類間隔最大,就等價于使最小.另外,考慮到一些噪音樣本點會導致這些樣本即使在映射后的高維空間也會被判別錯誤,因此,支持向量機模型在優化問題約束條件中增加一個松弛變量ξi,ξi＞0.最終,支持向量機模型變為

其中,C＞0,代表樣本點被錯誤分類時的懲罰系數.C數值越大,表明對錯誤的懲罰越嚴重.

1.2 雙隸屬模糊支持向量機模型

在傳統支持向量機模型中,每一個樣本點被絕對地劃分到A類或者B類.但在很多實際問題中,樣本點往往不是絕對地隸屬于某一類,而是存在雙重屬性.此外,在傳統支持向量機中,不同樣本點被錯誤分類的懲罰參數是相同的,使得傳統支持向量機存在過度擬合問題,對于數據集中的噪聲點十分敏感.文獻[9]中構建的新的雙隸屬度模糊支持向量機模型使得每個訓練樣本同時依隸屬度屬于兩個類別,有效地解決了上述兩個問題.

在雙隸屬支持向量機中,樣本集形式可以表示為

每個樣本分別依隸屬度屬于兩類,即樣本xi屬于A類(yi=1)的隸屬度為,屬于B類(yi=-1)的隸屬度為

雙隸屬度模糊支持向量機的基本模型為

其中,ξi,ηi分別是樣本點xi隸屬于A類和B類的松弛變量.

2 非平衡數據分類的支持向量機模型

傳統的支持向量機沒有考慮可能存在的樣本重疊情況,對于噪聲樣本點和樣本非平衡也比較敏感.已有的針對樣本非平衡的支持向量機改進模型仍然沒有考慮樣本重疊的情況,且依然對于噪聲樣本點比較敏感;而模糊支持向量機模型盡管可以克服噪聲樣本點問題,雙隸屬度支持向量機甚至考慮了樣本重疊的情況,但這些模型卻沒有考慮樣本數據集非平衡時對支持向量機分類效果的影響.筆者改進了Wang等[9]的模型,構建了一種新的支持向量機模型,既兼顧到樣本的雙重屬性,同時也能夠克服樣本非平衡、噪聲樣本點對支持向量機分類性能的影響.

筆者建立的改進支持向量機模型結構為

對比已有的支持向量機和雙隸屬支持向量機模型,筆者構建的非平衡數據分類的支持向量機模型(Class Imbalance Fuzzy Support Vector Machine,CI-FSVM)具有以下優點:

(1)在非平衡數據分類的支持向量機模型中,每個樣本點具有雙隸屬度和),雙隸屬度能夠體現出不同樣本點的重要性.因此,非平衡數據分類的支持向量機模型能夠降低噪聲樣本點在訓練階段的重要性,從而緩解模型對于噪聲樣本點的“過擬合”問題.

(2)rA、rB參數能夠調節非平衡數據分類的支持向量機模型的錯誤分類懲罰體現兩類樣本數量的不平衡,減少兩類樣本的非平衡所帶來的影響.

因此,對于非平衡數據分類的支持向量機模型來說,需要正確地設定隸屬度和以及非平衡調整參數rA和rB.

對于樣本非平衡調整參數rA和rB的設定,假定A類為多類,B類為少類,參考Akbani等[17]的思路,令

其中,r為A類(多類)與B類(少類)樣本數量的比值(r＞1).

3 仿真實驗

為了檢驗上文構建的非平衡數據分類的支持向量機模型的效果,通過對比實驗,比較了非平衡數據分類的支持向量機模型和其他已有方法對樣本數據的分類效果.

仿真實驗的數據取自加利福尼亞大學UCI機器學習樣本庫中廣泛應用的Pima-Indians數據庫.Pima-Indians數據庫包含樣本768個,共兩類,其中多類(正類)包含500個樣本,少類(負類)包含268個樣本.在進行仿真實驗時,筆者隨機選取多類樣本500個和少類樣本200個,兩類樣本的非平衡比例為5∶2.為了確保實驗結果的穩健性,側重對各方法泛化能力的對比,采用5組交叉驗證方法,具體做法為:將樣本集分為數量相等的5組,即每組各含多類樣本點100個和少類樣本點40個;取其中4組樣本點作為訓練集,剩下1組作為測試集,仿真得到分類精度.如此重復5次,得到5個分類精度.計算上述5個分類精度的簡單平均值,作為算法的最終分類精度.

(1)數據的歸一化處理.數據的歸一化能夠使得各個指標在分類時具有相同的作用,避免由于某個指標的數值范圍大而產生較大判別誤差.因此,為了將原始數據歸一化處理至區間[0,1],筆者采用的歸一化公式為

(2)核函數和參數選取.求解支持向量機模型需要計算高維空間的內積φ(xi)Tφ(xj),為避免維度災難,支持向量機模型采用核函數K(xi,xj)來代替φ(xi)Tφ(xj).筆者選取高斯核函數,即

對于具有高斯核函數的支持向量機模型,主要的參數包括C和σ2,參數的選取對模型的效果影響較大.參考相關文獻,筆者采用網格參數搜索算法[18]來確定C和σ2的最優值.假定C的取值范圍是{2-8,2-7,…, 28},σ2的取值范圍是{2-8,2-7,…,28},分別組合形成參數對(C,σ2).然后,采用5組交叉驗證的方法計算每一對(C,σ2)下支持向量機模型的分類精度,取分類精度最高時對應的參數組合(C*,σ2*)作為模型的最優取值.

此外,對于非平衡數據分類的支持向量機模型中的樣本非平衡調整參數(rA,rB),根據式(7),取rA=1, rB=r=500/200=2.5.

(3)仿真結果分析.為了客觀地評價筆者提出的非平衡數據分類的支持向量機模型效果,需要將其與其他現有模型的判別精度進行橫向比較.筆者將模糊支持向量機[8]、雙隸屬支持向量機[9]、Undersampling[10]、Over-sampling[11]、SMOTE[12-13]和z-SVM[14]這6個模型進行對比,以相同的樣本集作為數據來源,判別結果如表1所示.其中,L表示靈敏度,即多類樣本劃分正確的數量占所有多類樣本的比例;T表示特異度,即少類樣本劃分正確的數量占所有少類樣本的比例.總精度G為L和T的幾何平均值,即

表1 相同樣本集下各模型的判別精度對比

如表1所示,在相同樣本集下,非平衡數據分類的支持向量機模型的靈敏度為96.48%,特異度為94.55%,總精度高達95.51%.雖然非平衡數據分類的支持向量機模型的靈敏度低于模糊支持向量機(97.33%)和z-SVM(96.84%)模型,但是特異度和總精度顯著高于其他方法.特異度最高,說明非平衡數據分類的支持向量機模型對于少類樣本的判別精度顯著優于其他方法;總精度最高,說明非平衡數據分類的支持向量機模型的總體分類效果最優.因此,筆者建立的非平衡數據分類的支持向量機模型達到了預期的效果,即一方面通過雙隸屬度降低了模型對于噪聲樣本點的敏感性,另一方面有效地解決了樣本非平衡給模型判別帶來的困擾.

為了進一步比較筆者提出的非平衡數據分類的支持向量機模型和其他模型的分類性能,采用ROC[19](Receiver Operating Characteristic curve)來評價各個算法的判別能力.ROC曲線依據一系列二分類結果(分界值或決定閾),以1-特異度作為橫坐標,以靈敏度L作為縱坐標繪制而成.ROC曲線對樣本分布和類別先驗概率不具有敏感性,是一類相對有效的分類器性能評估工具.ROC曲線通常采用AUC(Area Under Curve)指標來衡量分類器性能,AUC越大,則分類性能越好.

如圖1所示,在相同樣本集下,繪制了非平衡數據分類的支持向量機模型、模糊支持向量機、雙隸屬支持向量機、Undersampling、Over-sampling、SMOTE和z-SVM模型的ROC曲線.可以看出,非平衡數據分類的支持向量機模型對應的ROC曲線AUC值最大,從而證明了非平衡數據分類的支持向量機模型的判別性能優于其他模型.

圖1 各模型的ROC曲線對比

4 總 結

針對樣本數據非平衡問題建立了一種新的模糊支持向量機模型,可以有效地降低模型對于樣本集中的噪聲點的敏感性,提高分類精度,還能顯著提高少類樣本的判別精度,有效地降低樣本的非平衡導致模型分類效果不佳的影響,應用前景更好.仿真實驗結果也支持了上述觀點,證明筆者構建的非平衡數據分類的支持向量機模型的判別精度的確要高于其他方法,而且模型對于樣本非平衡問題的解決也最為有力.將上述的二分類非平衡數據分類的支持向量機模型擴展到多分類問題中,將是下一步研究的重點.

[1]Vapnik V N.The Nature of Statistical Learning Theory[M].New York:Springer,1995.

[2]Luo Y,Wu C M,Zhang Y.Facial Expression Recognition Based on Fusion Feature of PCA and LBP with SVM[J]. Optik-International Journal for Light and Electron Optics,2013,124(9):2767-2770.

[3]Xiao Y C,Wang H G,Zhang L,et al.Two Methods of Selecting Gaussian Kernel Parameters for One-class SVM and Their Application to Fault Detection[J].Knowledge-Based Systems,2014,59(3):75-84.

[4]Zhong H M,Miao C Y,Shen Z Q,et al.Comparing the Learning Effectiveness of BP,ELM,I-ELM,and SVM for Corporate Credit Ratings[J].Neurocomputing,2014,128(3):285-295.

[5]Marseguerra M.Early Detection of Gradual Concept Drifts by Text Categorization and Support Vector Machine Techniques:the Trio Algorithm[J].Reliability Engineering&System Safety,2014,129(9):1-9.

[6]Guyon I,Matic N,Vapnik V N.Discovering Information Patterns And Data Cleaning[M].Cambridge:MIT Press, 1996.

[7]Debruyne M.An Outlier Map for Support Vector Machine Classification[J].The Annals of Applied Statistics,2009,3 (4):1566-1580.

[8]Lin C F,Wang S D.Fuzzy Support Vector Machines[J].IEEE Transactions on Neural Networks,2002,13(2):464-471.

[9]Wang Y Q,Wang S Y,Lai K K.A New Fuzzy Support Vector Machine to Evaluate Credit Risk[J].IEEE Transactions on Fuzzy Systems,2005,13(6):820-831.

[10]Weiss G M.Mining with Rarity:a Unifying Framework[J].ACM SIGKDD Explorations Newsletter,2004,6(1):7-19.

[11]He H,Garcia E.Learning from Imbalanced Data[J].IEEE Transactions on Knowledge and Data Engineering,2009,21 (9):1263-1284.

[12]Han H,Wang W Y,Mao B H.Borderline-SMOTE:a New Over-Sampling Method in Imbalanced Data Sets Learning [C]//Proceedings of International Conference on Intelligent Computing.Berlin:Springer-Verlag,2005:878-887.

[13]王超學,潘正茂,董麗麗,等.基于改進SMOTE的非平衡數據集分類研究[J].計算機工程與應用,2013,49(2):184-187. Wang Chaoxue,Pan Zhengmao,Dong Lili,et al.Research on Classification for Imbalanced Dataset Based on Improved SMOTE[J].Computer Engineering and Applications,2013,49(2):184-187.

[14]Imam T,Ting K,Kamruzzaman J.z-SVM:an SVM for Improved Classification of Imbalanced Data[C]//Proceedings of the 19th Australian Joint Conference on AI.Berlin:Springer-Verlag,2006:264-273.

[15]劉進軍.基于懲罰的SVM和集成學習的非平衡數據分類算法研究[J].計算機應用與軟件,2014,31(1):186-190. Liu Jinjun.Research on Classifying Unbalanced Data Based on Penalty-based SVM and Ensemble Learning[J].Computer Applications and Software,2014,31(1):186-190.

[16]孫全尚.不平衡數據集分類方法研究[J].科教文匯,2013(9):92-93. Sun Quanshang.Research on Imbalanced Data Sets Classification Method[J].The Science Education Article Collects, 2013(9):92-93.

[17]Akbani R,Kwek S,Japkowicz N.Applying Support Vector Machines to Imbalanced Datasets[C]//Proceedings of the 15th European Conference on Machine Learning.Berlin:Springer-Verlag,2004:39-50.

[18]Hsu C W,Lin C L.A Comparison of Methods for Multiclass Support Vector Machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.

[19]Choi S W,Park J Y.Nonparametric Additive Model with Grouped Lasso and Maximizing Area under the ROC Curve [J].Computational Statistics and Data Analysis,2014,77(9):313-325.

(編輯:郭 華)

New fuzzy SVM model used in imbalanced datasets

CAI Yanyan,SONG Xiaodong
(School of Economics and Management,Beihang Univ.,Beijing 100191,China)

The paper proposes a new fuzzy SVM,called CI-FSVM(Class Imbalance Fuzzy Support Vector Machine)short for which is based on imbalanced datasets classification.By improving penalty functions,we reduce the sensitivity of the model for imbalanced datasets with“overlap”.In addition,the parameters in SVM models are optimized by the grid-parameter-search algorithm.The results show that the CI-FSVM has a better effect in imbalanced datasets classification compared with other models.It not only has a higher overall accuracy,but also improves are judgment accuracy when dealing with the minority classifications.

support vector machine;classification;imbalanced datasets;noise samples;penalty function

TP181

A

1001-2400(2015)05-0120-05

2014-09-29< class="emphasis_bold">網絡出版時間:

時間:2014-12-23

國家自然科學基金重點資助項目(70821061)

蔡艷艷(1976-),女,北京航空航天大學博士研究生,E-mail:caiyanyan@buaa.edu.cn.

宋曉東(1984-),男,講師,博士,E-mail:song5120@126.com

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.021.html

10.3969/j.issn.1001-2400.2015.05.021