基于一种混合核函数的支持向量机聚类

摘要：在支持向量聚类中，采用单个核函数的支持向量机具有很大局限性，为了得到学习能力和泛化能力都很强的核函数，采用了一种新的混合核函数。将该混合核函数应用于支持向量聚类运算中，并且与普通核函数构造的支持向量机的实验结果进行了对比。结果表明了该方法的有效性。

关键词：SVM; 混合核函数; 加权多宽度高斯核; 支持向量聚类

中图分类号：TN911.734文献标识码：A文章编号：1004373X(2011)23005504

Support Vector Clustering Algorithm Based on Mixed Kernel Function

LI Xipeng， ZHAO Lifeng

(Department of Electronics Engineering, Ocean University of China, College of Information Science and Engineering, Qingdao 266100, China)

Abstract： The method that using a single kernel has great limitations in support vector clustering, in order to get an improved generalization performance and learning ability kernel function, a new mixed kernel function is proposed, and the data clustering experiment shows that the SVM performance in support vector clustering is much more efficient than the ones using only single traditional kernel.

Keywords： SVM; mixed kernel funtion; weighted Gaussian kernel with multiple widths; support vector clustering

收稿日期：20110621

基金项目：863计划项目:基于ROV的黄色物质水下原位探测系统(2008AA09Z105)0引言

支持向量机(Support Vector Machines,SVM)是在统计学理论基础上发展起来的一种分类和回归工具［1］。SVM通过核函数定义的非线性特征映射，将待分类数据映射到一个高维的特征空间中，从而能够线性可分，形成样本分类的决策规则［2］。目前它已被广泛应用到机器学习、模式识别和新知识检测等领域。近年来，又被应用到聚类分析中。核方法是支持向量机的基础。支持向量机的许多特性是由所选核函数来决定的［3］。

目前常用的核函数有很多种，例如：多项式核函数、高斯核函数和sigmoid核函数。使用单核函数的支持向量机有一定的局限性，为了得到性能更好的支持向量机，常用的方法是将两个或者多个核函数组合成混合核函数，由混合核函数构成的支持向量机兼顾各个单核函数的优点［4］。本文提出采用加权多宽度高斯核(Weighted Gaussian Kernel with Multiple Widths,WGKMW)函数［5］与多项式核函数组合起来，形成一种新的混合核函数。

1基于混合核函数的支持向量机

1.1核方法

核方法的基本思想就是通过非线性变换把输入模式空间映射到一个高维特征空间，再在高维特征空间中设计线性学习算法。若算法中各个模式矢量间的相互作用仅限于内积运算，则不需要知道非线性变换的具体形式，只要用满足Mercer条件的核函数代替线性算法中的内积，就能得到原输入空间中对应的非线性算法，即用核函数来简化计算。高斯核函数是支持向量聚类中普遍采用的［6］。

目前研究较多的核函数主要有以下几类：

(1) 多项式核函数K(x,y)=((x•y)+1)d(1)(2) Sigmoid函数K(x,y)=tanh(g(x,y)+h)(2)(3) 高斯核函数K(x,y)=exp(-x-y2/2σ2)(3)以上各式中d,σ,h,等参数都是实常数，在实际运用中，通常要根据问题的具体情况选择合适的核函数以及相应的参数。

加权多宽度高斯核函数(WGKMW)形式如下：K(x,y)=\[exp(-x-y2/2σ2)+R\]d(4)通过二项式定理(Binomial Theorem)将式(4)展开如下：K(x,y)=∑ds=0d

sRd-sexp-sx-y22σ2

=Rd+∑ds=1Rd-sexp-x-y22σ2/s(5)由式(5)可以看出，d个不同宽度的高斯核线性组合成加权多宽度高斯核。Rd-s是分别分配在d个不同宽度高斯核上的权重系数，控制不同高斯核的相对权重；d个高斯核由统一的宽度σ2变为可调宽度σ2/s；常量因子Rd使数据点之间距离的线性平移放大，在其特征空间扩大了样本点之间的差异，从而能更好地实现对差别微弱的样本类之间的聚类。

1.2混合核函数

核函数有两种主要类型：局部性核函数和全局性核函数。因为局部性核函数学习能力强，泛化性能较弱，而全局性核函数泛化能力强，学习能力较弱，因此考虑把这两类核函数混合起来［7］。下面函数可作为混合核函数的一种，并且满足Mercer条件。Kmix=λKpaly+(1-λ)Kwgkmw(6)这里还要确定最优混合系数λ∈(0,1)，通过仿真实验得出λ的值一般在0.55~0.99之间时更能体现该混合核函数的性能。

2基于混合核函数的支持向量机聚类

设数据空间XRd，数据集{Xi}X包含N个数据点，通过混合核函数定义的非线性映射Φ：XH；xΦ(x)，将样本从输入空间映射到高维特征空间中，在特征空间构造包含全部或大部分数据点的超球，最小包络超球体半径通过下面的优化问题［8］实现：min L=r2+C∑Nt=1ξi

s.t.Φ(xi)-a2≤r2+ξi,ξi≥0(7)式中:a是超球球心;ξi是允许部分数据在球外引入的松弛变量;C是惩罚因子，其为常数，在球的最小体积和非正常数据的个数之间取折中，引入式(7)的Lagrangian形式：L(r,a,ξ)=r2+C∑Ni=1ξi-∑Ni=1(r2+

ξi-Φ(xi)-α2)•βi-∑Ni=1ξiμi(8)式中:βi≥0和μi≥0都是Lagrangian乘子。求L对r，a，ξi的偏导数，并令它们等于0，得:∑Ni=1=1

a=∑Ni=1βiΦ(xi)

βi=C-μi(9)根据Fletcher提出的KKT互补条件［8］可得：ξiμi=0

(r2+ξi-Φ(xi)-a2)βi=0(10)分析KKT条件可知，若一个样本点对应的松弛变量ξi

将式(9)代入式(8)，并消去r，a和μi得到Lagrangian的Wolf对偶形式：max W(β)=∑Ni=1(Φ(xi))2βi-∑Ni=1∑Nj=1βiβjΦ(xi)Φ(xj)

s.t.∑Ni=1βi=1,i=1,2,…,N;0≤βi≤C(11)本文采用由多项式核函数与加权多宽度高斯核组成的混合核函数，将式(6)代入式(11)得：max W(β)=∑Ni=1Kmix(xi,xi)βi-∑Ni=1∑Nj=1βiβjKmix(xi,xj)

s.t.∑Ni=1βi=1,i=1,2,…,N;0≤βi≤C(12)求解(11)式的二次型可得到{βi}。则任一样本点在特征空间中的像到球心的距离为:d2(x)=Φ(x)-a2

=Kmix(x,x)-2∑Ni=1βiKmix(xi,x)+

∑Ni=1∑Nj=1βiβjKmix(xi,xj)(13)超球体的半径r可以用任一支持向量到球心的距离表示：r=d(xi)(14)式中xi为支持向量。

SVC可由数据空间中满足{x|d(x)=r}条件的样本点来形成聚类的边界。在特征空间中，数据点的像落入球内或者球面的数据，用+1指示；数据点的像落入球外的数据，用-1指示。这对应着决策函数：f(x)=sgn(r2-φ(x)-α2)

=sgn(r2-∑Ni=1∑Nj=1βiβjK(xi,xj)+

2∑Ni=1βiK(xi,x)-1)(15)然而由于聚类描述算法对样本点所属的类不做区分，为了在输入空间形成不同的类，利用距离d(x)来划分［9］。如果两个样本点属于不同的类，则在特征空间这对样本点之间的路径连线上必然存在点y且有d(y)>r。根据路径连线，若xi和xj在特征空间中的像落在球内或球面上，定义一个n×n邻接矩阵A：

(1) 如果xi和xj之间路径连线上的所有y都有d(y)≤r，则Aij=1；

(2) 否则，Aij=0。

由邻接矩阵可将聚类定义为邻近元素的元素。所以，SVC这样形成：SV在边界上，Outlier在边界外，其他数据点在边界内。

3模型选择和仿真实验

为了评价基于WGKMW支持向量聚类的性能，对3个数据集进行聚类试验，并与RBF支持向量聚类结果进行比较。试验采用的数据集描述如表1所示。

表1数据集描述

数据集类特征样本来源Data12283文献［10］krkonose32200文献［11］

试验1二维空间的数据集Data1［10］。由83个样本组成，分别隶属于两个不同的类别。分别用单独的多项式核函数与混合核函数对数据进行聚类实验，通过多次参数模型和多次实验比较，选择出聚类效果较好的参数，选取RBF核参数σ=2.1;WGKMW核参数σ=2.1,R=1,d=2，混合核函数中，聚类效果如图1所示。

试验2实验数据集krkonose［11］，取自Vojtech Franc和Vaclav Hlavac编写的stprtool工具包，由200个样本组成，分别隶属于3个不同的类别。实验中分别采用单独的高斯加权多宽度核函数与混合核函数进行聚类实验，两种核函数选取相同的σ=0.6，混合到核函数中。聚类实验结果如图2所示。

通过聚类误差率评价聚类效果:

聚类误差率=(有界支持向量(Outliers)/

数据样本总数)×100%

聚类误差率如表2所示。

图1两种核对Data1的聚类结果图2两种核对krkonose的聚类结果表2几种核函数时的聚类误差率

数据集RBFWGKMWMIXTURE

(RBF & WGKMW) /%Data117.6%NA5.3krkonoseNA5.5%0.97

实验表明，由多项式核函数与加权多宽度高斯核组成的混合核函数在其他参数相同的情况下，通过调节混合系数，可以提高支持向量机的泛化能力，获得更好的聚类效果。

4结论

本文提出将加权多宽度高斯核与多项式核函数组成混合核函数，使得新的核函数同时具备两个单核的优点，基于此混合核函数的支持向量机具有更好的学习能力和推广性。通过仿真实验验证，该方法不但方便可行，而且具有理想的聚类性能。对聚类过程中如何选取理想的核函数以及相应的参数，还需要进一步研究。

参考文献

［1］张芬.基于混合核函数的SVM及应用［D］.合肥:安徽大学,2006.

［2］邓乃扬,田英杰.数据挖掘中的新方法:支持向量机［M］.北京：科学出版社,2004.

［3］Vapnik.The nature of statistical learning theory \[M\]. 2nd edition. New York: SpringerVerlag, 2000.

［4］SMITS G F, JORDAAN E M. Improved SVM regression using mixture of kernels \[C\]// Processing of the 2002 International Joint Conference on Neural Networks. Washington DC: IEEE, 2002,3:27852790.

［5］田径，赵犁丰,赵宇倩.一种基于WGKMW的网络结构核函数框架［J］.中国海洋大学学报：自然科学版，2009(z1)：6869.

［6］［英］SHAWETAYLOR J,［美］CRISTIANINI N.模式分析的核方法［M］.赵玲玲,翁苏明,曾华军，等译.北京:机械工业出版社,2006.

［7］ZHANG Sheng, LIU Jian, TIAN Jinwen. An SVM based small target segmentation and clustering approach \[C\]//Proceedings of the Third International Conference on Machine Learning and Cybernetics.Shanghai: IEEE, 2004: 33183323.

［8］BENHUR A, HORN D, SIEGELMANN H T, et al. Support vector clustering \[J\].Journal of Machine Learning Research, 2001(2) :125137.

［9］GOLDBERG D E. Genetic algorithms in search,optimization,and machine learning \[M\]. \[S.l.\]: AddisonWesley Pub.,1989.

［10］BALASKO Balazs, ABONYI Janos, FEIL Balazs. Fuzzy clustering and data analysis toolbox. \[DB/OL\] \[20091011\]. www.fmt.vein.hu/softcomp/fclusttoolbox/.

［11］FRANC Vojtech，HLAVAC Vaclav. Statistical pattern recognition toolbox for Matlab \[EB/OL\]. \[20080816\]. /user/jung_dalglish/article/2326032.

作者简介： 李希鹏男，1987年出生，山东日照人，硕士研究生。主要研究方向为通信信号处理。

赵犁丰男，1957年出生，教授，山东青岛人。主要研究方向为通信信号处理。