基于相對密度的加權一分類支持向量機

鄭 瑋

(金陵科技學院 計算機工程學院, 江蘇 南京 211169)

?

基于相對密度的加權一分類支持向量機

鄭 瑋

(金陵科技學院 計算機工程學院, 江蘇 南京 211169)

提出了以相對密度的方式給訓練集樣本賦予權值．位于數(shù)據(jù)分布邊緣的樣本具有較低的相對密度,而位于數(shù)據(jù)分布內部的樣本具有較高的密度．對于位于數(shù)據(jù)分布內部的樣本賦予較大權值,位于數(shù)據(jù)分布邊緣的樣本賦予較小的權值．由于噪聲通常位于數(shù)據(jù)分布外部,因此本文的方法可以賦予噪聲較小的權值,從而使算法對于噪聲更加魯棒．人工數(shù)據(jù)集和UCI標準數(shù)據(jù)集的實驗結果表明,該法優(yōu)于用libsvm實現(xiàn)的一分類支持向量機方法．

加權一分類支持向量機; 相對密度; 一分類

0 引言

支持向量機由Vladimir Vapnik等于20世紀90年代提出[1]．原始的支持向量機算法主要用于二分類問題．當數(shù)據(jù)集不同類別樣本分布不均衡時,二分類支持向量機性能會有所下降．一種處理不均衡數(shù)據(jù)集的方法是用一分類來代替二分類．一分類支持向量機首先由Scholkopf提出[2],后來被成功用于多種問題[3-9]．傳統(tǒng)的一分類支持向量機同等的對待訓練集中每一個樣本,對于訓練集中的噪聲數(shù)據(jù)不夠魯棒,學習結果容易受到噪聲影響．一種降低噪聲的影響的方式是對處于訓練集分布邊緣的樣本賦予低的權值,而對于位于數(shù)據(jù)集內部的樣本賦予高的權值．通常,對于一分類支持向量機學習結果有影響的噪聲位于數(shù)據(jù)集分布的邊緣部分．一分類支持向量機同樣實現(xiàn)了結構風險最小化,對于未知樣本又更好的泛化性;同時一分類支持向量機具有全局最優(yōu)解,并且解只由少量支持向量決定．然而,傳統(tǒng)支持向量機具有的一些局限在一分類支持向量機中也仍然存在.如:沒有考慮先驗知識對學習的作用;需要一個好的核函數(shù)將訓練數(shù)據(jù)映射到高維線性可分空間;需要求解一個時間和空間消耗都很大的二次規(guī)劃等．

本文僅針對第一種問題，一種利用先驗知識的方式是根據(jù)數(shù)據(jù)本身賦予不同樣本不同權值，位于數(shù)據(jù)分布邊緣與內部的樣本對于一分類學習的作用不同,提出通過相對密度的方式給訓練數(shù)據(jù)賦權值．位于數(shù)據(jù)分布邊緣的樣本相對密度較大,而位于數(shù)據(jù)分布內部的樣本相對密度較?。谌斯?shù)據(jù)集和UCI標準數(shù)據(jù)集上的實驗表明加權一分類支持向量機優(yōu)于libsvm實現(xiàn)的算法．

1 相關工作介紹

如何在支持向量機中引入先驗知識一直是機器學習與模式識別里的一個熱門話題．一種方式是賦予不同數(shù)據(jù)不同權值,這樣賦給噪聲低的權值來降低噪聲對于學習影響,提高算法的魯棒性．但是,以前的工作大多關注的是二分類問題,而不是一分類問題[10-12]．

加權一分類支持向量機首先由Manuele Bicego & Mario A.T. Figueiredo提出[13],并被用用于模糊聚類．在文獻[14]中,作者用核概率c均值聚類算法(KPCM)給SVDD算法中樣本加權．由于SVDD算法可以包含少量負類樣本,KPCM算法中的聚類數(shù)設為2即可．而一分類支持向量機不包含負類樣本,因此KPCM算法加權的策略不適合于一分類支持向量機．在文獻[15],作者提出集成加權一分類支持向量機,在集成加權一分類支持向量機理樣本權重仍然由聚類方式獲得．然而,對于一個由M個一分類支持向量機組成的集成需要選擇2*M的參數(shù),因此選擇一組適合的參數(shù)需要耗費大量時間．本文提出了一種非聚類方式的加權策略,且提出的策略不需要調整過多參數(shù)．

2 基于相對密度的加權一分類支持向量機

在一分類問題中,只有大量目標數(shù)據(jù)和非常少量的奇異數(shù)據(jù)可以利用．一分類問題的目的就是找到一個可以包含所有目標數(shù)據(jù)而排出所有奇異數(shù)據(jù)的數(shù)據(jù)描述．用X 表示訓練數(shù)據(jù)集,數(shù)據(jù)集包含l目標{xi,i=1,…,l},xi∈Rn(n是xi的維數(shù))．x是一未知樣本,一分類問題就是找到函數(shù)f(x),當x是目標數(shù)據(jù)時,f(x)返回1;否則,f(x)返回-1．

(1)

引入優(yōu)化約束wTΦ(xi)-ρ+ξi≥0和ξi≥0的拉格朗日乘子αi,βi≥0,可以寫出式(1)對應的拉格朗日函數(shù):

(2)

對上式求關于w,ξ 和ρ的偏導,并令偏導數(shù)為0,可得:

(3)

(4)

將式(3)(4)帶入式(1),可以得到式(1)的對偶形式:

(5)

其中,α=(α1,α2,…,αl)為拉格朗日乘子的向量形式;Q為核矩陣,Q(i,j)=K(xi,xj)．顯然,式(5)與一分類支持向量機的惟一區(qū)別是拉格朗日乘子約束上界,而加權一分類支持向量機與原一分類支持向量機的決策函數(shù)形式相同．當v→0,加權一分勒支持向量機等同于一分類支持向量機．

在加權一分類支持向量機中,可以通過在訓練前賦予噪聲較小權值來降低噪聲對于學習結果的影響．

3 基于相對密度的加權方法

位于數(shù)據(jù)分布外圍的噪聲會引起一分類支持向量機的學習結果的偏移,因此希望賦予靠近數(shù)據(jù)分布邊緣的樣本低的權值,而賦予位于數(shù)據(jù)分布內部的樣本高的權值,以降低噪聲對學習結果的影響．而樣本在數(shù)據(jù)分布中的位置與自身的相對密度有關．在文獻[15]中,作者提出了樣本的相對密度．樣本的相對密度反映了樣本周圍的稠密情況．通常位于數(shù)據(jù)分布內部的樣本相對密度較大,反之位于數(shù)據(jù)分布邊緣的樣本相對密度較小．圖1顯示了Iris數(shù)據(jù)集中不同位置樣本的相對密度情況．

(6)

圖2比較了傳統(tǒng)一分類支持向量機與加權支持向量機在香蕉分布數(shù)據(jù)集上學習到的結果．其中訓練集包含10%的高斯分布噪聲．其中方框為訓練樣本,菱形◇為訓練數(shù)據(jù)中的噪聲,實現(xiàn)為學習到的一分類數(shù)據(jù)描述．由圖2可以發(fā)現(xiàn)當訓練集中混入10%高斯分布的噪聲時傳統(tǒng)的一分類支持向量機學習結果發(fā)生了嚴重的偏移,而加權一分類支持向量機仍然可以獲得一個較好的學習結果．

(a) 樣本位于數(shù)據(jù)分布的內部 (b) 樣本位于數(shù)據(jù)分布的邊緣

(a) 傳統(tǒng)一分類支持向量機(OC-SVM) (b) 加權一分類支持向量機(WOC-SVM)

4 實驗仿真

表1 無噪聲時AUC值比較

表2 加入高斯噪聲AUC值比較

對加權一分類支持向量機與傳統(tǒng)一分類支持向量機作一比較．其中加權一分類支持向量機與傳統(tǒng)一分類支持向量機均由libsvm實現(xiàn)[17]．作為使用最廣泛的支持向量機工具箱具有更高的效率,因此基于libsvm的改進也更有意義．求解樣本相對密度的算法由Matlab環(huán)境下的mex接口實現(xiàn),并且由VC2010編譯．實驗在Intel CoreTMi5-4690 CPU @3.50GHz,8GB DRAM的Windows 7機器上運行．

對于一分類問題由于只有目標可以利用(即正類樣本),而奇異數(shù)據(jù)(負類數(shù)據(jù))幾乎沒有．對于學習效果的評價第二類錯誤無法計算,本文中的實驗在一分類效果上采用了ROC(Receiver Operating Characteristic) 曲線[18]和AUC(the Area Under the ROC curve) 值[19]作為評價標準．而本文的程序由Matlab實現(xiàn)．

首先比較了算法在人工數(shù)據(jù)集上的效果,然后比較了在UCI標準數(shù)據(jù)集[20]上的效果．與其他一分類研究類似,本節(jié)的實驗結果主要比較了ROC curve和AUC值這兩個指標．AUC值越大說明該一分類分類器的性能越好．

表3 加入均勻分布噪聲AUC值比較

表4 UCI標準數(shù)據(jù)集

4.1 人工合成數(shù)據(jù)集

實驗比較了對于Sine問題加權一分類支持向量機的效果．Sine問題中目標數(shù)據(jù)由以下方式產生:

其中，t是步長0.01在[0, 2π]范圍的序列;N是均值[0, 0]T，方差0.04I(I是2*2的單位矩陣)的高斯噪聲.奇異數(shù)據(jù)為均勻分布.實驗中分別50，100和200個訓練數(shù)據(jù).為了驗證算法對噪聲的有效性，分別添加了10%，20%和30%的高斯分布噪聲和均勻分布噪聲. 測試數(shù)據(jù)集包含獨立生成的1 000個目標數(shù)據(jù)和1 000個奇異數(shù)據(jù). 實驗重復執(zhí)行50次，統(tǒng)計了50次實驗結果AUC值的均值和標準差. 表1～表3分別表示在不加噪聲以及分別加入高斯噪聲、均勻分布噪聲的實驗結果. 算法中的參數(shù)σ和υ分別選自2-10,2-9,2-8,2-7,2-6,2-5}和{0.01,0.06,0.11,0.16,0.21}中使得AUC最大的參數(shù)組. 相對密度中近鄰的取值為10.

4.2 UCI標準數(shù)據(jù)集

本文實驗驗證算法在UCI標準數(shù)據(jù)集:Yeast,Pima Indians Diabetes,Blood Transfusion和Satimage上的效果,如表4所示,其中括號里的數(shù)字是每一類包含的樣本數(shù)．

每個數(shù)據(jù)集中包含樣本數(shù)最多的類被作為目標類,其余類作為奇異數(shù)據(jù)類．沒有獨立測試集的數(shù)據(jù)集中目標數(shù)據(jù)被平均分為2份,一份用作訓練,另一份連同奇異數(shù)據(jù)一起用作側試．對于Satimage數(shù)據(jù)集,訓練集中的目標數(shù)據(jù)用作訓練,訓練集中的奇異數(shù)據(jù)和測試集一起用作測試．圖3～圖6比較了算法的在Yeast, Pima Indians Diabetes, Blood Transfusion和Satimage的ROC value曲線．

圖3 Yeast數(shù)據(jù)集ROC曲線 圖4 Pima Indians Diabetes數(shù)據(jù)集ROC曲線

圖中點線表示加權一分類支持向量機,虛實線表示原始支持向量機．ROC曲線面積越接近左上角算法性能也越好．可以發(fā)現(xiàn)在這4個數(shù)據(jù)集上加權一分類支持向量機均好于傳統(tǒng)一分類支持向量機．

圖5 Blood Transfusion數(shù)據(jù)集ROC曲線 圖6 Satimage數(shù)據(jù)集ROC曲線

5 結論

提出了一種基于相對密度的加權一分類支持向量機算法．傳統(tǒng)的一份類支持向量機由于同等的對待訓練集中的所有樣本,因此位于靠近數(shù)據(jù)分布邊緣的噪聲會對一分類支持向量機的學習結果產生偏差．由于位于數(shù)據(jù)分布邊緣的訓練樣本通常相對密度也較小,而位于數(shù)據(jù)分布內部的訓練樣本相對密度較大,因此可以用樣本的相對密度賦予訓練樣本權值．這樣訓練集中的噪聲可以被賦予較小的權值,從而降低噪聲對于學習結果的影響．在人工合成數(shù)據(jù)集和UCI標準數(shù)據(jù)上的實驗結果均表明利用相對密度加權的一分類支持向量機均好于原一分類支持向量機．人工數(shù)據(jù)集上分別增加高斯噪聲、均勻分布噪聲的實驗結果表明本文的加權方式可以使算法對于噪聲更加魯棒．

[1] Vapnik V. The nature of statistical learning theory[M]. New York:Springer-Verlag, Inc, 1995.

[2] Scholkopf B, Platt J C, Shawe-Taylor J, et al. Estimating the support of a high-dimensional distribution[J]. Neural computation, 2001, 13(7): 1443-1471.

[3] Guerbai Y, Chibani Y, Hadjadji B. The effective use of the one-class SVM classifier for handwritten signature verification based on writer-independent parameters[J]. Pattern Recognition, 2015, 48(1): 103-113.

[4] Lipka N, Stein B, Anderka M. Cluster-based one-class ensemble for classification problems in information retrieval[C]. Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval. ACM, 2012: 1041-1042.

[5] Cabral G G, de Oliveira A L I. One-class Classification for heart disease diagnosis[C]. Systems, Man and Cybernetics (SMC), 2014 IEEE International Conference on. IEEE, 2014: 2551-2556.

[6] Guo L, Zhao L, Wu Y, et al. Tumor detection in MR images using one-class immune feature weighted SVMs[J]. Magnetics, IEEE Transactions on, 2011, 47(10): 3849-3852.

[7] Li W, Guo Q, Elkan C. A positive and unlabeled learning algorithm for one-class classification of remote-sensing data[J]. Geoscience and Remote Sensing IEEE Transactions on, 2011, 49(2): 717-725.

[8] Cyganek B. Image segmentation with a hybrid ensemble of one-class support vector machines[M]. Springer Berlin Heidelberg: Hybrid Artificial Intelligence Systems, 2010: 254-261.

[9] Cyganek B. One-class support vector ensembles for image segmentation and classification[J]. Journal of Mathematical Imaging and Vision, 2012, 42(2-3): 103-117.

[10] Wu X, Srihari R. Incorporating prior knowledge with weighted margin support vector machines[C]. Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 326-333.

[11] Yang X, Song Q, Wang Y. A weighted support vector machine for data classification[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2007, 21(5): 961-976.

[12] Karasuyama M, Harada N, Sugiyama M, et al. Multi-parametric solution-path algorithm for instance-weighted support vector machines[J]. Machine learning, 2012, 88(3): 297-330.

[13] Bicego M, Figueiredo M A T. Soft clustering using weighted one-class support vector machines[J]. Pattern Recognition, 2009, 42(1): 27-32.

[14] Zhang Y, Liu X D, Xie F D, et al. Fault classifier of rotating machinery based on weighted support vector data description[J]. Expert Systems with Applications, 2009, 36(4): 7928-7932.

[15] Krawczyk B, Wozniak M, Cyganek B. Clustering-based ensembles for one-class classification[J]. Information Sciences, 2014, 264: 182-195.

[16] Lee K Y, Kim D W, Lee D, et al. Improving support vector data description using local density degree[J]. Pattern Recognition, 2005, 38(10): 1768-1771.

[17] Chang C C, Lin C J. LIBSVM: A library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2(3): 27.

[18] Metz C E. Basic principles of ROC analysis[C]. Seminars in nuclear medicine. WB Saunders, 1978, 8(4): 283-298.

[19] Bradley A P. The use of the area under the ROC curve in the evaluation of machine learning algorithms[J]. Pattern recognition, 1997, 30(7): 1145-1159.

[20] Lichman, M. UCI Machine Learning Repository[M].Irvine CA: University of California, School of Information and Computer Science, 2013.

[責任編輯：蔣海龍]

A Weighted One-class Support Vector Machine based on Relative Density Degree

ZHENG Wei

(School of Computer Engineering, Jinling Institute of Technology, Nanjing Jiangsru 211169, China)

In this paper, an instance-weighted strategy was proposed based on relative density degree. The closer to the boundary of the training set the sample was, the higher the relative density degree was. The samples locating in the exterior of the data distribution are assigned with larger weights, while the samples locating near the boundary of the data distribution are assigned with lower weights. In general, the noises locate in the external of the data distribution. Therefore, the proposed method can assign the noises with lower weights. The weighted one-class support vector machine could be robust to the noises. The results of the experiments, performed on artificial synthetic datasets and UCI benchmark datasets, demonstrate that weighted one-class support vector machine performs better than one-class support vector machine, which was implemented by libsvm the most popular SVM toolbox.

weighted one-class support vector machine; relative density degree; one-class classification

2016-09-09

江蘇省高校自然科學基金資助項目(16KJB520012)

鄭瑋(1981-),女,江蘇泗洪人,講師,博士生,主要研究方向為數(shù)據(jù)挖掘與模式識別. E-mail: vividzheng@163.com

TP391

A

1671-6876(2016)04-0317-06