阜 艷,余 君

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

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

中圖分類(lèi)號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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]等人在支持向量機(jī)SVM基礎(chǔ)上提出的一種單值分類(lèi)數(shù)據(jù)描述算法。在該算法中,如果存在一個(gè)超球面能夠正確分類(lèi)訓(xùn)練數(shù)據(jù),并且這個(gè)程序保證收斂,這種情況稱為線性可分。如果這樣的超球面不存在,則數(shù)據(jù)稱為線性不可分?？赏ㄟ^(guò)核函數(shù)方法將原始訓(xùn)練數(shù)據(jù)從低維空間映射到高維空間中,從而使低維空間中線性不可分的情況變成在高維空間中線性可分的。如何選擇核函數(shù)才能使支持向量數(shù)據(jù)描述分類(lèi)器的分類(lèi)效果達(dá)到最佳是值得研究的一個(gè)重要問(wèn)題。在此,對(duì)多項(xiàng)式、高斯和多層感知器核函數(shù)進(jìn)行研究,并探討了高斯核參數(shù)對(duì)SVDD的影響。

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

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

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

該問(wèn)題的對(duì)偶形式為:

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)化問(wèn)題可得αi的值,一般情況下,大部分αi將為0,不為0的αi所對(duì)應(yīng)的樣本被稱為支持向量。根據(jù)KKT條件,對(duì)應(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)。用任意一個(gè)支持向量,根據(jù)上式可求出R的值。對(duì)于新樣本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)類(lèi);否則z被判決為非目標(biāo)類(lèi)。

2 核函數(shù)的性能

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

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

p階多項(xiàng)式核函數(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ù)使用得最廣。無(wú)論是在低維、高維、小樣本、大樣本等情況,RBF核函數(shù)均適用,具有較寬的收斂域,是較為理想的分類(lèi)依據(jù)函數(shù)。

下面再?gòu)睦碚撋向?yàn)證高斯核函數(shù)在SVDD算法中的優(yōu)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)

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

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[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ī)的性能分析[J].計(jì)算機(jī)工程,2003,29(8):22-25.

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

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

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

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