基于RBF的支持向量數據描述算法性能分析

阜 艷,余 君

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

關鍵詞:支持向量數據描述;核函數;高斯核函數;單值分類

中圖分類號:TP391文獻標識碼: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 引 言

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

1 支持向量數據描述算法

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

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

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)

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

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

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

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被判決為目標類;否則z被判決為非目標類。

2 核函數的性能

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

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

p階多項式核函數:

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

高斯(RBF)核函數:

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

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

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

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

下面再從理論上驗證高斯核函數在SVDD算法中的優點。

SVDD算法中優化問題的對偶形式中式(3)目標函數,對于高斯核函數K(xi,xi)=1,此目標函數轉化為:

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),要想得到目標函數的最大值,只要考慮式中的第二項就可以。

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

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

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

3 高斯核參數σ對SVDD的影響

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

3.1 實驗

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

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

圖1 小規模banana樣本

圖2 大規模banana樣本

圖3 小規模breast-cancer樣本

3.2 結果分析

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

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

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

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

4 結 語

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

參考文獻

[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].廣州:華南理工大學出版社,2006.

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

[8]吳今培,孫德山.現代數據分析[M].北京:機械工業出版社,2006.

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