基于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.