摘 要: 支持向量机兼顾训练误差和推广性能,已受到机器学习领域的高度重视,而核函数的性能是支持向量机研究中的关键问题。研究了几种常见核函数对支持向量机推广性能的影响,并利用全局核函数和局部核函数的性质,提出了一种新的分段核函数的支持向量机。数据集上的仿真结果表明,该核函数对应的支持向量机泛化能力优于传统核函数对应的支持向量机,具有较好的预测性能。
关键词: 支持向量机; 分段核函数; 全局核; 局部核
中图分类号: TN911⁃34 文献标识码: A 文章编号: 1004⁃373X(2013)16⁃0005⁃04
支持向量机(SVM)是一种以统计学习理论为基础的优化算法,对于未知测试数据具有良好的推广性能,它在文本分类、车牌识别、身份验证、生物科学等领域已经有了较好的应用。V.N.Vapnik等人在20世纪60年代就开始研究小样本情况下机器学习问题,并在1995年首先提出支持向量机。近年来,支持向量机理论逐渐成熟,主要有以下几个特点:
(1)SVM解决的是小样本条件下的最优解,不需要训练过程中有充足的训练样本。
(2)SVM利用内积核函数实现从低维空间到高维空间的非线性映射,从而将非线性分类问题变为线性分类问题。SVM决策函数由支持向量确定,支持向量的数目决定计算的复杂度,与样本空间维数无关,因而它克服了传统模式识别中由于样本空间的维数过高导致的 “维数灾难”。
(3)SVM引入错误代价系数,可以在约束错误率的情况下找出最佳分类超平面,具有很好的推广性能,避免了人工神经网络方法中容易过度拟合训练样本的问题。然而,支持向量机在应用过程中也存在一些问题,分类过程中,不同核函数对应的分类结果、准确率都不同,如何根据不同的训练样本采用相应的核函数亟待解决。目前,国内外一些学者正在从事这方面的研究,并取得了一些进展。袁小艳等人提出了组合核函数支持向量机,充分利用了全局核函数和局部核函数的特性,提高了分类准确率[1]。丁子春在自适应算法的基础上提出了自适应核函数,通过实验证明此核函数有较好的学习能力和泛化能力[2]。OLIVIER CHAPELLE等人提出用梯度下降法选择核函数参数进行训练,得到了理想的结果[3]。因此,针对支持向量机现有的问题,本文将根据核函数类型以及核函数中的参数对数据集进行研究讨论。
1 支持向量机简介
支持向量机主要有线性可分、非线性可分以及带有核函数映射三类分类问题。由于线性分类器分类性能较差,非线性分类器在保证推广能力的前提下错误率较高,因此可以通过低维空间到高维空间的非线性映射,将问题转换为在高维空间求得最佳线性分类超平面。
1.1 非线性映射
为了使样本在特征空间可分,将[ℓ]维空间中样本映射到高维的空间中去,通过一个非线性映射[ϕ]:[Rℓ]→[RD],训练样本集我们得到[D]维空间里的分割超平面。分类样本通过映射[ϕ]变换到[RD]中,直接在[RD]中进行分类,不用映射回原空间。
1.2 优化求解
非线性可分数据集{([x1],[y1]),([x2],[y2]),…,([xℓ],[yℓ])},经过非线性映射,数据集转化为线性可分数据集{([ϕ(x1)],[y1])),([ϕ(x2)],[y2]),…,([ϕ(xℓ)],[yℓ])},它被超平面[w,x+b=0]分开,样本点离此平面越远,支持向量机推广性能越好。同时考虑到样本分类的正确率,得到如下优化问题:
[min 12w2+Ci=1ℓξi]
[s.t. yi(w,ϕ(xi)+b)≥1-ξi, ξi≥0, i=1,2,…,ℓ]
式中样本向量[xi∈Rℓ];[ℓ]是训练样本数;[w]是权矢量;[b]是阈值;[yi]为样本标记。
通过推导得到优化目标函数:
[L(a)=i=1lai-12i=1lj=1laiajyiyjκ(xi⋅xj)]
式中核函数[κ(xi,xj)=ϕ(xi),ϕ(xj)],原问题转化为如下最优化问题:在如下约束条件下,[i=1ℓaiyi=0,][0≤ai≤C,][i=1,2,…,ℓ]。最大化目标函数[L(a)]。
因为有[w=][iℓaiyiϕ(xi)],故最终的决策函数为:
[h(x)=sgn(w,ϕ(xi)+b)=sgniℓaiyiϕ(xi),ϕ(xj)+b]
由上式可知,最终的决策函数取决于核函数,核函数的性能决定最终的判别结果。
2 核函数研究
核函数是支持向量机的关键部分,核函数引入后,不用再进行庞大的内积运算,从而使高维空间的线性分类成为可能。
2.1 常见核函数
根据泛函理论,任何一种核函数只要满足Mercer条件,他就可以等价为变换空间中的内积。常见的核函数有4种:
(1)线性核函数:
[κ(x,y)=x⋅y]
(2)多项式核函数:
[κ(x,y)=(x⋅y+1)d, d=1,2,…]
(3)径向基核函数:
[κ(x,y)=exp(-rx-y2)]
(4)Sigmoid核函数:
[κ(x,y)=tanh(b(x⋅y)-c)]
式中:[b],[c]都是实常数;[r=1p2],[p2]为方差。在实际应用时,根据不同的样本集以及具体情况选择不同的核函数。
2.2 分段核函数
由于全局核函数推广性能好,每个测试点对所有训练样本都有影响。而局部核函数学习能力强,测试点只对其附近的训练样本有较大影响。如图1,图2所示,测试点在0.5处,选用线性核函数作为全局核函数,rbf核函数作为局部核函数,测试点在0.5处。
图1 线性核函数映射特性
图2 RBF核函数映射特征
由图1知,测试点对应整个训练集都有较大的核函数值。由图2知,测试点只对应其附近训练集有较大的核函数值,随着训练集离测试点距离变远,核函数值很快衰减。为了充分利用每一个训练数据,本文选择分段核函数,如图3所示,任意选择参数[p]=0.2对应的rbf核函数,在rbf核函数对称轴左右一定距离阈值内使用此核函数,而在此距离阈值外使用线性核函数,这样可以充分利用全局核函数以及局部核函数的性能。
图3 分段核函数映射特性
分段核函数满足:
[κ(x,y)=x⋅y, x-y>q-x⋅y, x-y<-qC⋅exp(-rx-y2), x-y 式中:[x]是测试点;[y]是训练点;[q]是阈值。 下面证明分段核函数满足成为核函数的条件: 文献[4]中已证明核函数有零置换的性质,即设[κ(x,y)]是[x][×][x]上的核函数,[s⊂x],则: [κ(x,y)"=κ(x,y), x,y∈s0, otherwise] [κ(xi,xj)"]是[x][×][x]上的核函数,称为[κ(x,y)]的零置换。 因此: [κ(x,y)=x⋅y, x-y>q0, otherwise] [κ(x,y)=-x⋅y, x-y [κ(x,y)=exp(-rx-y2), x-y 也是核函数。 又由核函数的封闭性:若[κ1],[κ2]是核函数,则[κ1]+[κ2]也是核函数,[aκ1]也是核函数,[a][≥]0。 故有: [κ(x,y)=x⋅y, x-y>q-x⋅y, x-y 满足核函数条件,得证。 3 实验结果与分析 为了验证分段核函数有较好的分类能力,选取UCI数据集heart,训练集数目为30,测试集数目为60,分段核函数中常数C取10,由于恰当的阈值对应高的分类正确率,故用文献[1]中的交叉检验法选取阈值的大概范围,本次实验对应阈值选为3,其他参数为libsvm工具箱中默认参数,训练集和测试集无相同数据。用组合核函数[1]对训练集建模,用分段核函数预测,预测结果见表1。 表1到表4表明,测试数据集的增加不影响分段核函数的性能,分段核函数对应支持向量机预测正确率依然高于其他核函数对应正确率。 接下来在训练集数目为30,测试集数目为240的条件下,改变阈值大小,测试分段核函数预测能力,预测结果如表5所示。 表5 阈值对准确率的影响 % 由以上实验结果可以看出,本文使用的分段核函数对应支持向量机分类效果优于单一的核函数以及组合核函数对应的支持向量机,对于分段核函数,阈值大小的选择直接影响分类结果。由分段核函数的构成知,只要距离阈值选择恰当,它的分类准确率的下线为使用其他几种核函数对应分类准确率的上限。分段核函数通过对距离阈值的调节可以适应不同的样本数据集,但由于本文选取阈值利用交叉检验法,根据预测正确率选取阈值大小,采用的是穷举思想,只能人为确定阈值的大概范围,精确得到最优阈值需要编程对阈值所在区间逐一计算,因此,阈值精度要求越高,要的时间越长。但支持向量机更重视的是学习能力以及对未知数据的预测能力,如何根据已有样本集选择对应核函数才是关键问题。 4 结 语 本文通过研究分析全局核函数以及局部核函数的性能,在线性核函数和RBF核函数的基础上提出了一种分段核函数,通过对UCI数据集heart的实验并与传统核函数分类正确率进行对比,验证了这种分段核函数比较理想的学习能力和推广能力,提升了支持向量机分类器的性能。但随着对分段核函数性能要求的提高,需要提高阈值的精度,这将会以牺牲时间作为代价。下一步工作,将在阈值选取和新型核函数的选取上,有了合适的阈值,对性能更好的新型核函数的分段组合将使支持向量机有更好的性能和更大的应用空间。 参考文献 [1] 袁小艳,刘爱伦.组合核函数支持向量机的研究与应用[M].上海:华东理工大学自动化研究所,2011. [2] 丁子春.支持向量机中核函数研究[M].武汉:武汉理工大学,2008. [3] CHAPELLE Olivier, VAPNIK Vladimir, BOUSQUET Olivier, et al. Choosing multiple parameters for support machine [J]. Machine Learing, 2002, 46(1/3): 131⁃159. [4]王国胜.核函数的性质及其构造方法[J].计算机科学,2006,33(6):172⁃174. [5] CHANG Chih⁃Chung, LIN Chih⁃Jen. LIBSVM: a library for support vector machines [EB/OL]. [2013⁃03⁃04]. http://.cn/qkpdf/moet/moet201316/moet20131602-1.pdf" style="color:red" target="_blank">原版全文