1、一种改进支持向量域数据描述方法及其应用讲解第48卷 第5期2009年9月厦门大学学报(自然科学版)JournalofXiamenUniversity(NaturalScience)Vol.48 No.5Sep.2009一种改进支持向量域数据描述方法及其应用罗 键,庄进发,李 波,吴长庆,黄春庆(厦门大学信息科学与技术学院,福建厦门361005)摘要:针对支持向量域数据描述中的核参数选择及其决策边界规整问题,提出一种新的改进算法.该算法根据支持向量域数据描述本身的特点,利用非高斯性来测量核空间样本接近球形区域分布的程度,并根据此测量结果来优化核参数.当核参数选定之后,核空间样本可能存在分布不均匀
2、的现象,对此,该算法应用核主元分析来进行规整,即通过尺度变换来调整各主轴的长度,以获得一个更合理的球形分界面.最后通过标准数据集和TEP故障诊断仿真以验证该算法,仿真实验结果表明了该算法的有效性.关键词:支持向量域描述;核主元分析;非高斯性中图分类号:TP311 文献标识码:A 文章编号:0438 0479(2009)05 0656 06 支持向量域数据描述(Supportvectordatade scription,SVDD)是在支持向量机(Supportvectormachine,SVM)的基础上提出的一种数据描述算法.它的主要思想是在核特征空间中寻找一个最小超球分界面,该分界面应尽可能把
3、所有训练样本包围起来,并以该分界面对数据进行分类和描述.SVDD的性能受核参数和最小超球分界面的影响很大,当核参数选择不当,SVDD描述数据的分类效果就不理想;当核参数选定后,如果样本在核特征空间中分布不够均匀,用球面去包围训练样本就不一定使得SVDD决策边界线紧凑.针对这两方面的问题,本文提出了一种基于非高斯性测量与核主元分析的改进方法.文献3指出选择不同的核函数或设置不同的核参数,特征样本映射到核空间的维数以及数据集在核空间分布形状就有很大的不同.在SVDD算法中,主要通过高斯核函数将特征样本进行映射,并寻找一个最小超球分界面来尽可能把所有训练样本包围起来1.本文认为一个理想的SVDD高斯
4、核参数 ,应使得核空间样本的空间分布形状尽量地趋近于球形区域.这样求解SVDD最优核参数问题就转化为测量核空间中样本趋近于超球体的程度.文献5介绍了应用蒙特卡罗法(Simplemontecarloalgorithm)、交叉坐标法(Coordinatebycoordinatestrategy)和高斯分布转动不变性法6-7(Basedontherotationinvari收稿日期:2008 12 30基金项目:国家自然科学基金(60704043),国家 211 工程(王艺之)项目 立体通信和信息集成技术 资助edu.421ancethenormaldistribution),来产生一个属于N维球形
5、面的随机变量,并在理论上对这3种算法进行了比较,得出高斯分布转动不变性法是一种较高效的产生球形面数据集的方法.在文献5的基础上,本文提出一法则,即若多维随机变量中各维服从同均值且同方差的独立高斯分布,则该变量的空间分别趋近于球形区域.这样就可通过测量核空间样本的非高斯性质来优化SVDD的核参数值.当核参数确定之后,如果核空间的样本分布是不均匀的,那么应用球形面去包围所有的训练样本,就显得不紧凑,如图1所示.在图中,椭圆决策分界面比圆形决策分界面更紧凑地包围样本.针对这个问题,本文通过核主元分析(Kernelprincipalcomponentanal ysis,KPCA)来对球形面进行规整,即
6、利用KPCA获得p个主元方向,并计算p个方向上的主轴长度,然后通过尺度变换使得各主轴的长度相等,从而获取一个更合理的球形界面.对于KPCA核参数选择,文献9指出在KPCA分析中,最优核参数应该是使核空间特征样本的分布趋于高斯分布,这也与前述求取核参数的方法一致,因此前述求解得到的核参数可作8图1 用椭圆球面覆盖训练样本第5期罗 键等:一种改进支持向量域数据描述方法及其应用 657为KPCA分析中的核参数.1 SVDD简介设X=xii=1为R空间中的一个样本集,其中n表示样本的数目.通过一个非线性映射 将样本映射到特征空间F中,即 :x X Rd (x) F(称 (x)为x对应的核样本).SVD
7、D的基本思想是:在F中寻求一个体积最小的超球 =(a,R),使得核样本集X= (xi)i=1中的数据全部或尽可能多的包容在 中.其中a表示球心,R表示半径.最小化超球体的体积是一个二次规划问题,即min(R+C i)R,a,i2 基于非高斯测度的核参数优化dn2.1 产生球形区域的数据集文献7指出,如果X1,X2, ,Xn为独立且服从平均值为0,方差为1的高斯分布,那么X1,X2, ,Xn位于一个单位球形面上,即(X1/r,X2/r, ,Xn/r)其中r=1+X2+ +Xn.(6)n若要使点位于N维球形的球内,只要把X1,X2, ,(1)Xn乘以一个正交矩阵U即可获得.定理1 如果多维变量y中
8、的各维变量服从独立且平均值相等的同方差高斯分布,则y的空间分布趋(2)于一个N维球形区域.由文献7可知,N维球形表面上的点是服从独立且平均值相等的同方差高斯分布.现只需证明球形内的点也是服从独立且平均值相等的同方差高斯分布即可.若有一随机变量服从N(0,1)的高斯分布,则其密度函数为2-x(7)2同样如果有一多维变量中的各维变量服从N(0,1)独ni=1约束条件为(xi)-a 2 R2+ i,i=1,2, ,n其中 i 0表示松弛变量,以便把奇异点排除在超球体外.C是一个指定的常数,起到控制对错分样本惩罚程度的作用,以实现错分样本比例与算法复杂程度之间的折中.该优化问题的解可由下面的拉格朗日(
9、La grange)泛函的鞍点给出:2L(R,a, i,ai, i)=R+Cni=1n-i2i=1f(x)=i=1a(Ri+ i- (xi)-a )-iin立且平均值相等的同方差高斯分布,那么其密度函数(3)为1-2e(8)d(2 )现设有一正交矩阵U Rd d,则球形内的点为Y其中,ai 0, i 0.求式(3)的最小值可变成求其Wolf对偶问题的最大值W(a)=i=1nnnf(x)=ak(x,x)- aak(x,x)iiiijiji=1j=1=UX.证明P(Y A)=P(X UA)=-x,xUtAe=d(2 )-xxAe=d(2 )-Ae.d(2 )因此,不论是球形面,还是球形内部的点都服
10、从独立且t(4)其中a=(a1,a2, ,an),a的约束是i=1ani=1和0ai C.K(xi,xj)表示核函数,用它替代内积运算,即k(xi,xj)=.对于一个新样本x如果满足下列条件,则接受它属于目标样本,否则拒绝.f(x)=k(x,x)-2 aik(xi,x)+i=1n平均值相等的同方差高斯分布.定理1得到证明.(5)i=1j=1aak(x,xijinnj) R2.2 特征子空间的数据分布在特征空间F中,无法直接分析数据集X= (xi)i=1的分布情况.因此,考虑yi在一组标准正交基 (x1), , (xr)生成的子空间F投影分布情况,从几,yii1nrn在实际计算中,多数ai=0,
11、只有少数ai 0,称ai0对应的样本为支持向量,只有这些支持向量才决658 厦门大学学报(自然科学版)2009年构,即它们的分布相同.设子空间F的一组基为xb1, ,xbr,则F的一组标准正交基为( 1, , r)=( (xb1), , (xbr)V其中V=(u1/1, ,ur/(9)r),u1, ,ur为核矩阵SVDD是通过求解覆盖所有训练样本的最小超球面来实现基于单类训练样本的判别方法.但是如果样本分布得不够均匀,用球面去覆盖训练样本就未必合理.如在图1的情形下,用超球面去覆盖训练样本就要承担相当大的风险.如果不用球面,而是用椭球面去覆盖这些点,结果就会更合理.设核函数k(x,y)导出的特
12、征映射为: :R F,x (x).由于主成分分析都是将数据中心化后进行的,因此可设ni=1i=1Nrr3 基于KPCA的超球形圆整Krr=(k(xbi,xbj)1 i,j r的一组标准正交特征向量, 1,r为对应的特征值. ,则 (xi)(1 i n)在标准正交基 1, , r的投影向量为yi=( 1, , r) (xi)=TV(k(xb1,xi), ,k(xbr,xi)TT(10)2.3 核参数优化评价数据集X= (xi)ni=1的分布逼近超球形区域的程度,可以转化为考察Y=yi逼近超球形区域的程度.由前面定理知,当一个多维变量y的各个分量独立且服从同方差的高斯分布,则y的分布是一个近似超球
13、形区域.因此趋近于球形区域的测量,可以转化为对多维变量y的各个分量的高斯性进行测量.对于非高斯性测度,文献10介绍了一种基于最大熵原则的非高斯性测度,用来测量一维随机变量的非高斯性,并证明了比传统的基于累计量的测度精确得多11.其定义如下:J(z)=Eg(z)-Eg(v)2(x)=ijn0并计算协方差矩阵TC=mj=1(xM) (xj)(14)特征值分解C,则可以得到C的非零特征值 0及相应的特征向量V,满足CV= V(15)C对应于特征向量V的特征值大小等于映射样本在该V方向上投影的方差.注意到任何一个不为0的特征值所对应的特征向量V都在 (x1), , (xn)张成的空间中,所以存在系数a
14、i(i=1, ,n)使得:V=i=1(11)a (x)iinM(16)其中v是标准的高斯变量,随机变量z假定具有零均值、单位方差.g是非二次函数,具体选取方法见文献10.由于式(11)只是针对一维随机变量的非高斯性测度,因此本文在式(11)的基础上拓展为一种多维的非高斯性测度.假定v是N维的高斯随机变量,即每一维服从零均值,单位方差的高斯分布.z假定为一个N维随机变量,每维具有零均值,单位方差.定义测度如下:J(Z)_n=i=1将式(15)两端同时与 (xk)做内积,有 =,k=1, ,n再将式(16)代入,得ai=ni=1 故有n Ka=Ka求解与式(17)等价特征值问题:2j=1ni=1a
15、i (xk),(xnj)(),k=1, ,n.(17)Eg(Z)-iini=1nEg(v)2(12)最优化核参数算法如下:1)求解X= (x)对应的所有数据集Y=Y1, ,Ym.其中m为标准正交基的个数.2)将数据yi(i=1,2, ,n)按如下方式处理:zi=(yi-y)/ .其中y是Y =yini=1( =1, ,m)的均值, 是每维向量方差的均值.3)用式(12)分布测量Y 的非高斯度J(Z)_n.4)按下式确定最优的核参数 =m inJ(Z)_n=min 2i=1n a=Ka(18)最后得到特征空间中的p个主方向为Vk(k=1, ,p).对任意的测试样本x,其在各个主方向上的投影为=k
16、i=1ak(x,x)kiin(19)利用KPCA方法得到的p个主方向就是待求的椭球的主轴.各主轴的长度可以通过计算样本点在该主轴方向的投影的最大间隔距离近似得到.然后根据主轴的长度进行变换,使得各主轴的长度相等.算法描述如下:1)训练样本X= (xi)i=1在第二节求得最优核nEg(Z)-in(第5期罗 键等:一种改进支持向量域数据描述方法及其应用 6592)对映射后的点施行中心变换,即将坐标平移到ni=1处.in3)通过旋转和投影变换,根据式(18)获得p个主方向.4)计算训练样本在各个主轴上的投影,得到椭球各主轴长度,从而得到各主轴方向的收缩比例因子,然后对样本点施行收缩尺度变换.4 实验
17、验证图2 测试样本本文实验主要采用的是Matlab7.4语言以及在dd_tools工具包(http:/www ict.ewi.tudelft.nl/davidt/dd_tools.html#download)和SVM KM工具包(http:/asi.insa rouen.fr/enseignants/arako tom/toolbox/index.html)的基础上来编写本文的算法.的性能没有优于SVDD3,如图3所示.当SVDD经过这两阶段的改进之后,其性能有一定的提高. Fig.2 Testingsamples4.2 基于TEP的实验验证TEP故障诊断问题是由美国伊斯曼化学公司创建的,其目
18、的是为评价过程控制和监控方法提供的一个现实的工业过程.TEP作为比较各种方法的数据源,已在过程监控领域得到了广泛的应用12.TEP主要包含有22类故障,55个监控变量,960个样本数(每3min采集一次,总共运行48h).根据文献13的研究建议只选取2448h时间段的480个数据(ht tp:/brahms.scs.uiuc.edu)中具有典型代表的1、4、5、11共4类故障.在本实验中,依次把4类故障中的一类作为未知新故障,其它的3类作为已知故障,其中把480个数据样本同样的分为两部分,一部分作为训练,一部分作为测试,然后利用已知故障来进行SVDD的建模,总共进行了4 5=20次实验,实验结
19、果如表2所示.表2显示,基于改进的SVDD能够有效对已知故障进行识别达到85%左右,同时对新故障也能够较好地识别,达到72%左右.4.1 基于标准数据集的实验验证本实验主要采用的banana标准数据集(www.first.gmd.de/raetsch)来验证.该数据集含有200个样本,2维输入,输出维数是1.把200个banana数据集平均分成两部分,一部分用于SVDD的训练建模,另一部分数据集用于测试SVDD的准确率.由于SVDD是单分类器,本文人为地引入100个非banana数据样本(界外样本)并加入测试样本集中,如图2所示.训练SVDD模型的实验结果如图3所示,图3显示不同的核参数和在是
20、否圆整球面条件下产生的不同分界球面.其中图3(a)显示数据集的分界面过于宽松,有可能包含了较大一部份的界外样本,这说明在数据集分布为 弧形或椭圆 时,采用SVDD表述数据边界的效果很差;图3(b)数据集的分界面比较合适,但是不够平滑;图3(c)显示分界面比较合适,且分界比较平滑;图3(d)中数据集的分界面出现 过拟合 的现象,可能导致把大量的训练样本(目标样本)排除在外.表1显示不同的核参数以及是否对球形面进行圆整的测试样本的准确率结果.SVDD1对目标样本的识别准确率较高达89.32%,对界外样本的识别准确率较低为70.10%,这是由于其分界面过于 宽松 导致,这也可以从图4的ROC(Rec
21、eiver operatorcharacteristiccurve)曲线上可以看出;SVDD4对于目标样本的识别准确率较低为37.86%,对于界外样本的识别准确率较高达97.57%,这是由于其分界面 过适应 导致,如图4所示.SVDD2与SVDD3相对于前面两个模型,分界面比较适中,对于目标样本和界外样本准确率都比较高,5 结 语针对SVDD中的核参数选择及其决策边界规整问题,提出一种新的改进算法.SVDD是在SVM的基础上提出的一种基于KPCA方法的单一分类器.针对SVDD核参数的优化和样本在核空间的分布不均匀这两个问题,本文提出并证明应用非高斯性准则来优化核参数的可行性;当样本在特征空间的
22、分布不均匀时,利用球面去作为分界面就存在一定的宽松,提出应用KPCA方法来对最小球形面进行圆整,最终获得一个球数验及660 厦门大学学报(自然科学版)2009年图3 不同的核参数和圆整球面获得的SVDD模型(a)数据集的分界面过于宽松;(b)数据集的分界面比较合适,但是不够平滑;(c)显示分界面比较合适,且分界比较平滑;(d)数据集的分界面出现 过拟合 的现象Fig.3 TheSVDDmodelscreatedbydifferentkernelparametersandroundedsphericalsurface表1 识别率与核参数、是否圆整球面的关系Tab.1 Therelationshi
23、pbetweentherecognitionrateandthekernelparametersaswellaswhetherornotroundthespherical名称J8330.95圆整球面否否是否目标准确率/%89.3285.4491.2637.86界外准确率/%70.1098.9794.8597.57SVDD10.36SVDD20.03SVDD30.03SVDD40.45图4 ROC曲线 Fig.4 ROCcurves表2 TEP故障检测结果Tab.2 TheresultsofTEPfaultdetection已知故障1、4、51、4、111、5、11新故障1154J0.1020.
24、0890.765 3.512.131.56圆整球面是是是已知故障识别率/%87.686.483.2新故障识别率/%73.471.270.7第5期罗 键等:一种改进支持向量域数据描述方法及其应用1969.661TEP故障诊断实验验证本文算法,实验结果证明了该方法的有效性,即通过核参数优化和球形面的圆整之后,SVDD的性能有较大的提高.尽管本文从上述两方面对SVDD进行改进,但是对于参数C的选择还是没有一个有效的方法,本文的下一步工作就是利用核小波分析来优化参数C的选择.7 EdwinFBeckenbach,ArthurErd lyi,MagnusRHestenes.Modernmathemati
25、csfortheengineerM.NewYork:McGraw Hill,1961.8 ScholkopfB,SmolaA,MullerKR.NonlinearcomponentanalysisaskerneleigenvalueproblemJ.NeuralCompu tation,1998,10(6):1299-1319.9 MikeS,ScholkopfB,SmolaA.KernelPCAandde noisinginfeaturespaceJ.AdvancesinNeuralInformationProcessingSystems,1999,11(1):524-536.10 Hyva
26、rinenA.NewapproximationsofdifferentialentropyforindependentcomponentanalysisandprojectionpursuitC/TheProceedingofAdvancesinNeuralIn formationProcessingSystems.Cambridge:MITPress,1998,10:273-293.11 AmariA,CichockiA,YangHH.AnewlearningalgorithmforblindsourceseparationC/ProceedingsofAdvancesinNeuralInf
27、ormationProcessingSystem.Cambridge:MITPress,1996,8:757-763.12 ChenGT,McavoyJ.Predictiveon linemonitoringofcontinuousprocessJ.JournalofProcessControl,1999,8:409-420.13 DownsJJ,VogelEF.Aplant wideindustrial processcontrolproblemJ.Computers&ChemicalEngineer ing,1993,17:245-255.参考文献:1 DavidT,RobertD.Sup
28、portvectordatadescriptionJ.PatternRecognitionLetters,1999,20(11):1191-1199.2 TaxD.One classclassificationD.Netherlands:DelftUniversityofTechnology,2001.3 BaudatG,AnouarF.GeneralizeddiscriminantanalysisusingakernelapproachJ.NeuralComputation,2000,12(1):2385-2404.4 赵峰,张军英,刘敬.一种改善支撑向量域描述性能的核优化算法J.自动化学报
29、,2008,34(9):12-19.5 JanPoland.ThreedifferentalgorithmsforgeneratinguniformlydistributedrandompointsontheN sphereEB/OL.(2000 10 24)2008 12 30http:/www.alg.ist.hokudai.ac.jp/jan/randsphere.pdf.6 KnuthDE.Theartofcomputerprogramming,Vol.2:seminumericalalgorithmsM.USA:Addison Wesley,AnImprovedSupportVect
30、orDataDescriptionMethodandItsApplicationLUOJian,ZHUANGJin fa,LIBo,WUChang qing,HUANGChun qing(SchoolofInformationScienceandTechnology,XiamenUniversity,Xiamen361005,China)Abstract:Toaddresstheproblemofkernelparameterselectionandregulatingdecisionboundaryinsupportvectordatadescription(SVDD),thispaperproposesanewalgorithm.AccordingtothecharacteristicofSVDD,theproposedalgorithmutilizesthenon Gaussiantomeasurehowkernelsamplesapproximatetoasphericalarea,andthen
