阜 艷,余 君

摘 要:核函數(shù)的選擇對支持向量數(shù)據(jù)描述算法(SVDD)的性能有重要的影響,是SVDD研究的一個核心問題。通過對SVDD算法中常用核函數(shù)進行分析,驗證了高斯核函數(shù)在單值分類問題上具有一定的優(yōu)越性,并分別探討相同樣本數(shù)據(jù)集不同規(guī)模樣本和不同樣本數(shù)據(jù)集相似規(guī)模樣本中,高斯核參數(shù)對SVDD分類器的影響。實驗表明,基于高斯核函數(shù)的支持,向量數(shù)據(jù)描述算法適合于小規(guī)模樣本的單值分類問題。

關(guān)鍵詞:支持向量數(shù)據(jù)描述;核函數(shù);高斯核函數(shù);單值分類

中圖分類號:TP391文獻標(biāo)識碼:A

文章編號:1004-373X(2009)20-140-03

Analysis of Support Vector Data Description Performance Based on RBF

FU Yan1,YU Jun2

(1.Guangdong Institute of Science and Technology,Zhuhai,519090,China;

2.The Third Branch of Guangdong Planning and Designing Institute of Telecommunications Co.Ltd.,Jiangmen,529030,China)

Abstract:The selection of kernel technology has an important impact on the performance of Support Vector Data Description(SVDD),so it is the core of SVDD.By the analysis of common kernel functions on SVDD,Gauss-kernel that possessed certain superiority to the problem of one-class classification is verified.It is investigated respectively that Gauss-kernel-parameter has the influence on SVDD,from different-scale sample of the same sample data set and similar-scale sample of different sample data set.Experiments show that SVDD method based on Gauss-kernel is adaptive to one-class classification of small-scale sample.

Keywords:support vector data description;kernel function;Gauss-kernel function;one-class dassification

0 引 言

支持向量數(shù)據(jù)描述(Support Vector Data Description,SVDD)是Tax[1]等人在支持向量機SVM基礎(chǔ)上提出的一種單值分類數(shù)據(jù)描述算法。在該算法中,如果存在一個超球面能夠正確分類訓(xùn)練數(shù)據(jù),并且這個程序保證收斂,這種情況稱為線性可分。如果這樣的超球面不存在,則數(shù)據(jù)稱為線性不可分?？赏ㄟ^核函數(shù)方法將原始訓(xùn)練數(shù)據(jù)從低維空間映射到高維空間中,從而使低維空間中線性不可分的情況變成在高維空間中線性可分的。如何選擇核函數(shù)才能使支持向量數(shù)據(jù)描述分類器的分類效果達到最佳是值得研究的一個重要問題。在此,對多項式、高斯和多層感知器核函數(shù)進行研究,并探討了高斯核參數(shù)對SVDD的影響。

1 支持向量數(shù)據(jù)描述算法

支持向量數(shù)據(jù)描述算法的基本思想是通過在特征空間中找出一個包圍目標(biāo)樣本點的超球體,并通過最小化該超球體所包圍的體積,使目標(biāo)樣本點盡可能地被包圍在超球體中,而非目標(biāo)樣本點盡可能地不被包含在超球體中。從而實現(xiàn)兩類之間的劃分。超球體內(nèi)的點被認為是目標(biāo)類數(shù)據(jù),超球體外的點被認為是非目標(biāo)類數(shù)據(jù)[2-4]。

設(shè)一個目標(biāo)樣本集為:{xi,i=1,2,…,l},設(shè)法找一個以a為中心,以R為半徑,能夠包含所有樣本點的最小球體。如果直接進行優(yōu)化處理,所得到的優(yōu)化區(qū)域就是一個超球體。為了使優(yōu)化區(qū)域更緊湊,可以采用核映射的思想,首先將低維的輸入空間通過非線性映射函數(shù)映射到高維屬性空間;然后在高維特征空間中求解包含所有樣本點的最小超球體。這里也可引入松弛變量ξi來允許一些數(shù)據(jù)點存在誤差,可用滿足mercer條件的核函數(shù)來代替高維空間中的內(nèi)積運算,即找一個核函數(shù)Κ(x,y),使得Κ(x,y)=[φ(x),φ(y)],這樣優(yōu)化問題轉(zhuǎn)換為:

min F(R,a,ξi)=R2+C∑li=1ξi (1)

s.t.[φ(xi)-a][φ(xi)-a]Τ≤R2+ξi(2)

ξi≥0,i=1,2,…,l

該問題的對偶形式為:

max∑li=1αiK(xi,xi)-∑li=1∑lj=1αiαjK(xi,xj)(3)

s.t. ∑li=1αi=1, 0≤αi≤C,i=1,2,…,l(4)

解該優(yōu)化問題可得αi的值,一般情況下,大部分αi將為0,不為0的αi所對應(yīng)的樣本被稱為支持向量。根據(jù)KKT條件,對應(yīng)于0≤αi≤C,i=1,…,l的樣本有:

R2-[K(xi,xi)-2∑lj=1αjK(xj,xi)+a2]=0(5)

式中:a=∑li=1αiφ(xi)。用任意一個支持向量,根據(jù)上式可求出R的值。對于新樣本z,設(shè):

f(z)=[φ(z)-a][φ(z)-a]Τ=K(z,z)-

2∑li=1αiK(z,xi)+∑li=1∑lj=1αiαjK(xi,xj)(6)

若f(z)≤R2,則z被判決為目標(biāo)類;否則z被判決為非目標(biāo)類。

2 核函數(shù)的性能

核函數(shù)本身是一種特征映射,反映了樣本在特征空間中彼此的相似程度。然而樣本之間的相似程度一旦給定,樣本間的分類其實也就基本上給定了。一個好的核函數(shù),應(yīng)該能夠真實反映樣本間的遠近關(guān)系。因此,核函數(shù)的選擇對SVDD分類器的分類效果有重要的影響。

目前,核函數(shù)類型的選擇基本上還是憑經(jīng)驗選定的。選定核函數(shù)后,再進行相關(guān)參數(shù)的確定。在實際應(yīng)用中被廣泛使用的核函數(shù)有下面三種[5]:

p階多項式核函數(shù):

K(x,y)=[(x?y)+1]p(7)

高斯(RBF)核函數(shù):

K(x,y)=exp[-‖x-y‖2/(2σ2)](8)

多層感知器(MLP)核函數(shù):

K(x,y)=tanh[v(x?y)+c](9)

其中,RBF核函數(shù)使用得最廣。無論是在低維、高維、小樣本、大樣本等情況,RBF核函數(shù)均適用,具有較寬的收斂域,是較為理想的分類依據(jù)函數(shù)。

下面再從理論上驗證高斯核函數(shù)在SVDD算法中的優(yōu)點。

SVDD算法中優(yōu)化問題的對偶形式中式(3)目標(biāo)函數(shù),對于高斯核函數(shù)K(xi,xi)=1,此目標(biāo)函數(shù)轉(zhuǎn)化為:

max[∑li=1αi-∑li=1∑lj=1αiαjK(xi,xj)](10)

由對偶形式中的約束條件可以得到:

max[1-∑li=1∑lj=1αiαjK(xi,xj)](11)

因0≤αi≤C,高斯核K(xi,xj)>0,則對于式(11),要想得到目標(biāo)函數(shù)的最大值,只要考慮式中的第二項就可以。

對于核函數(shù)取p階多項式核函數(shù)或者多層感知器核函數(shù)K(xi,xi),其不是常數(shù)而是變值,要隨著選定參數(shù)的不斷變化,SVDD算法中優(yōu)化問題的對偶形式的式(3)目標(biāo)函數(shù)的兩項都變化。特別是多項式核函數(shù),第二項的變化小于第一項的變化,以致于隨著參數(shù)的增大,半徑逐漸變大,而分類區(qū)域變得很寬松,使得映射效果不很理想。

由上理論研究知,高斯核函數(shù)具有如下優(yōu)點:表示形式簡單,即使對于多變量輸入也不會增加太多的復(fù)雜性;光滑性好,任意階導(dǎo)數(shù)均存在;解析性好,便于理論性分析。

所以,在后面本文采用的都是高斯核函數(shù)。

3 高斯核參數(shù)σ對SVDD的影響

有關(guān)實驗[6-8]已驗證了高斯核參數(shù)σ值與SVDD模型區(qū)域邊界的關(guān)系。SVDD的分類邊界是由位于分類邊界上支持向量決定的。當(dāng)σ很小時,所有的訓(xùn)練樣本都是支持向量,它們被緊致的界線包圍著,數(shù)據(jù)在圖中只表現(xiàn)為一個個孤立點。此時的區(qū)域邊界只能識別出這些訓(xùn)練樣本,測試樣本中不同的樣本都將被判為非目標(biāo)樣本。隨著核參數(shù)σ值的增加,支持向量數(shù)目在逐漸減少,SVDD模型的邊界區(qū)域有很多獨立的界線,變得連通且寬松,直至σ值使得所有的樣本點全部包括在一個獨立的區(qū)域界線內(nèi)和邊界上,再增加σ值時,區(qū)域邊界只變得寬松,圖形的變化不大明顯,此時的分類效果是不理想的。

3.1 實驗

調(diào)節(jié)高斯核參數(shù)σ觀察下超球體半徑R、支持向量數(shù)目SV、非目標(biāo)樣本被判為目標(biāo)樣本、目標(biāo)樣本判為非目標(biāo)樣本以及正確識別率的變化。一般地,把非目標(biāo)樣本判為目標(biāo)樣本的稱為漏判,把目標(biāo)樣本判為非目標(biāo)樣本的稱為誤判。兩者所帶來的損失是不同的,一般漏判損失是遠大于誤判損失的。

實驗數(shù)據(jù)采用二維banana數(shù)據(jù)集中第一組訓(xùn)練數(shù)據(jù)和第一組測試數(shù)據(jù)和九維breast-cancer數(shù)據(jù)集中第一組訓(xùn)練數(shù)據(jù)和第一組測試數(shù)據(jù),其中banana數(shù)據(jù)集中選擇正類樣本作為目標(biāo)樣本,breast-cancer數(shù)據(jù)集中選擇負類樣本作為目標(biāo)樣本。令實驗中的懲罰參數(shù)C=1。分別采用banana數(shù)據(jù)集中的部分目標(biāo)樣本和部分測試樣本、全部目標(biāo)樣本和測試樣本,以及breast-cancer數(shù)據(jù)集中全部目標(biāo)樣本和測試樣本,觀察參數(shù)σ的大小對小規(guī)模樣本和大規(guī)模樣本的影響。其中圖1是采用小規(guī)模的banana數(shù)據(jù)樣本,100個訓(xùn)練樣本,200個測試樣本(150個目標(biāo)樣本,50個非目標(biāo)樣本);圖2是采用大規(guī)模的banana數(shù)據(jù)樣本,4 900個訓(xùn)練樣本,200個測試樣本(2 159個目標(biāo)樣本,2 741個非目標(biāo)樣本);圖3是采用小規(guī)模的breast-cancer數(shù)據(jù)樣本,138個訓(xùn)練樣本,77個測試樣本(58個目標(biāo)樣本,19個非目標(biāo)樣本)。圖1~圖3是參數(shù)σ的大小和R,SV、漏判、誤判和正確識別率之間的關(guān)系圖。

圖1 小規(guī)模banana樣本

圖2 大規(guī)模banana樣本

圖3 小規(guī)模breast-cancer樣本

3.2 結(jié)果分析

從圖1～圖3可以看出,當(dāng)核參數(shù)σ取值相對過小時,SVDD的全部訓(xùn)練樣本全是支持向量,和訓(xùn)練樣本不同的測試樣本將不會被識別出來,其中包括一些目標(biāo)樣本被誤判為非目標(biāo)樣本,非目標(biāo)樣本也很小會被漏判。隨著σ值的增加,支持向量數(shù)目在不斷減少,超球體半徑隨之緩慢減少(圖3減少的坡度比較大,是因為選取的σ變化的幅度較大),漏判的非目標(biāo)樣本數(shù)目不斷增加,而誤判的目標(biāo)樣本數(shù)目在不斷的減少,支持向量數(shù)目、漏判樣本數(shù)目和誤判樣本數(shù)目增加或減少隨著σ值增大到一定值,其基本上趨于平緩狀態(tài),變化不是很明顯。

對于測試樣本的正確識別率,先是隨著σ值的增大,正確識別率逐漸增加,增加到一定值后,又緩慢的下降,減少的坡度要看測試樣本中目標(biāo)樣本和非目標(biāo)樣本的比例。圖1和圖3中σ-正確識別率關(guān)的系圖相似,而圖2在正確識別率出現(xiàn)最高位置后下降的坡度較大,是因為測試樣本中的非目標(biāo)樣本占的比例比較大,在50%以上,漏判的樣本數(shù)目較多,最終使得正確識別率比較低。

觀察圖中每組樣本對應(yīng)的σ-正確識別率關(guān)系圖和σ-漏判、σ-誤判的關(guān)系圖可以發(fā)現(xiàn),正確識別率最高的位置和σ-漏判、σ-誤判相交的位置對應(yīng)的σ比較接近。這樣在實驗中選擇參數(shù)σ值時,可以縮小其選擇范圍,減少一定的訓(xùn)練運算時間,必然大大降低核參數(shù)選擇上的工作量。不過,有時要結(jié)合實際情況,不是正確識別率高就能說明這組數(shù)據(jù)樣本好,要結(jié)合漏判和誤判的實際影響來選擇合理的核參數(shù)。

圖1和圖2所選用的目標(biāo)類訓(xùn)練數(shù)據(jù)樣本規(guī)模不一樣,對于關(guān)系圖具有相似性,不過對于獲得的最佳參數(shù)σ值是不同的,大規(guī)模目標(biāo)類訓(xùn)練樣本的σ值與小規(guī)模目標(biāo)類訓(xùn)練樣本的σ值相比要小些,小規(guī)模數(shù)據(jù)樣本的離散程度大些,得到的最佳參數(shù)σ值相對要大一些。由此可以看出,對于大規(guī)模的數(shù)據(jù)樣本采用SVDD算法,得到的最佳參數(shù)σ值相對比較小,若過于太小,獲得的區(qū)域邊界就會比較緊致,甚至有些訓(xùn)練樣本點在圖中表現(xiàn)為一個孤立點,這樣獲得的SVDD區(qū)域邊界會不理想。

4 結(jié) 語

在基于SVDD算法的基礎(chǔ)上,對SVDD算法中常用的核函數(shù)進行研究,驗證了高斯核函數(shù)用于理論分析具有一定的優(yōu)越性,并探討高斯核參數(shù)與SVDD模型區(qū)域邊界、超球體半徑、支持向量數(shù)目、漏判和誤判以及測試樣本的正確識別率之間的關(guān)系。實驗表明,基于高斯核函數(shù)的支持向量數(shù)據(jù)描述算法適合于小規(guī)模樣本的單值分類問題。實驗中用固定懲罰參數(shù),改變核參數(shù)σ來驗證σ的影響,對于C和σ參數(shù),可以通過交叉驗證、遺傳算法、網(wǎng)格搜索法和雙線性搜索法等來找到最好的一組參數(shù),這些都有待于進一步研究。

參考文獻

[1]Tax D M J,Duin R P W.Support Vector Data Description[J].Machine Learning,2004(54):45-66.

[2]Scholkopf B,Williamson R,Smola A,et al.Support Vector Method for Novelty Detection[J].Advances in Neural Information Processing Systems,2000(12):582-588.

[3]Tao Xinmin,Liu Furong,Zhou Tingxian.A NovelApproach to Intrusion Detection Based on Support Vector Data Description[A].The 30th Annual Conference of the IEEE Industrial Electronics Society[C].Harbin,2004,3(3):2 016-2 021.

[4]Xin Dong,Wu Zhaohui,Zhang Wanfeng.Support Vector Data Description for Speaker Recognition[A].Proceedings of the 2001 IEEE Signal Processing Society Workshop on Neural Networks for Signal Processing XI[C].North Falmouth,2001:481-488.

[5]張小云,劉允才.高斯核支撐向量機的性能分析[J].計算機工程,2003,29(8):22-25.

[6]肖健華.智能模式識別方法[M].廣州:華南理工大學(xué)出版社,2006.

[7]鄭曉星,吳今培.基于支持向量數(shù)據(jù)描述的數(shù)據(jù)約簡[J].現(xiàn)代電子技術(shù),2007,30(2):74-76.

[8]吳今培,孫德山.現(xiàn)代數(shù)據(jù)分析[M].北京:機械工業(yè)出版社,2006.

[9]Stephen J Chapman.Matlab Programming for Engineers[M].2版.北京:科學(xué)出版社,2003.