[一种基于DGMF与PSO的多核SVM]下列哪种情况细胞不会出现多核现象

　　摘要:目前常用的支持向量机采用传统的单一高斯核函数，或者传统高斯核函数与多项式核函数的组合，但是存在着分类器泛化推广能力不强，容易出现数据偏斜等问题。鉴于此，提出了基于DGMF的多核支持向量机、并采用粒子群算法优化其参数。最后构造了文本倾向性分类实验，实验结果表明改进算法在正确率、准确率、召回率、F1值上具有更好的性能。
　　关键词:双高斯合成函数；多核支持向量机；组合核函数；粒子群算法；文本倾向性分类
　　中图分类号：TP181文献标识码：A文章编号：1009-3044(2012)13-3171-08
　　A kind of Multiple Kernel Support Vector Machines Based on Double Gaussian Kernel Mixed-function and Particle Swarm Optimization
　　TIAN Dong-yang
　　（Wulumuqi Central Sub-branch of the People’s Bank of China，Wulumuqi 830002,China）
　　Abstract：At present, the majority of text sentiment classification algorithms based on support vector machines using a single traditional Gaussian kernel function, or a combination of Gaussian kernel function and polynomial kernel function. But there are some problems: generalization abilities of these classifiers are not strong, the effects of fine-tune are not obvious .In view of this, experimental results show that the algorithm has better performances based on multiple kernel support vector machines of double Gaussian kernel mixed-function and par? ticle swarm optimization algorithm.
　　Key words：double gaussian kernel mixed-function; multiple kernel support vector machines; combination of nuclear function; particle swarm optimization; text sentiment classification
　　支持向量机（Support Vector Machines，SVM）是Vapnik等人根据结构风险最小化原则提出来的。在有限样本前提下，能尽量提高学习机的泛化能力。另外，它还是凸二次优化问题，能够保证找到的极值就是全局最优解。
　　核函数是SVM的核心，目前分类算法大多是以传统高斯核函数为基础，存在文本倾向性数据集在高维空间不平坦的问题(No-Flat Problem，NFP)，即测试点在低维特征空间比较密集，映射到高维空间后却相当稀疏[1]。目前，常将传统高斯核函数与多项式核函数组合使用，但该方法较为依赖数据集自身的特征，容易出现数据偏斜现象[3-4]。
　　分类器参数是影响分类效果的重要因素。目前常用的优化算法有交叉验证法、网格搜索算法，遗传算法等，但它们分别存在最优划分问题，经验选取问题，计算复杂、速度较慢、容易陷入局部最优化等问题。
　　为克服上述问题，改进分类性能，研究提出基于DGMF的多核SVM，并采用PSO求解参数。该文探讨了该算法的原理，通过实验与传统算法进行了比较。
　　1支持向量机
　　对于训练集：(xi,yi)，i∈N，xi∈Rd,yi∈{+1,-1}，判别函数为f(x)=ω?x+b，分类面为ω?x+b=0。归一化后使离分类面最近的样本f(x)=1，其它样本满足：|| f(x)≥1,yi(ω?x+b)-1≥0，i∈N。这样分类间隔为
　　α*iyixi，b*可由αi[yi(ω?xi+b)-1]=0求出。根据泛函理论，将满足Mercer条件的对称核函数K(xi,xj)代替xi
　　2双高斯合成函数
　　在支持向量机中，核函数的作用就是把低维空间中非线性的数据映射到高维空间，然后构造最优分类超平面进行线性分类。它的优点就在于代替了高维空间中的内积运算，不需要映射后的样本在高维空间进行运算，可以避免维数灾难。在支持向量机中，核函数有两种类型：全局核函数和局部核函数[2]。全局核函数的特点是能够提取样本的全局特征，能够对数据集中相距较远的数据之间产生影响，善于提取样本的全局特征。局部核函数的特点刚好相反，善于提取样本的局部特征。在满足了Mercer条件下，我们可以使用多种不同类型的核函数，并且选用不同的核函数可以构造不同的支持向量机。
　　局部核函数的典型代表是高斯核函数K(x,y)=exp(
　　)。当σ越大，核函数的幅度越宽；相反当σ越小，核函数的幅度越窄。下图是高斯核函数的图形，测试点y取5，σ分别取0.5，1，2，3，4的曲线图。从图中可以看出来，局部核函数只是对测试点C＝0.5的小范围内的数据有较大影响，同时随着不同的σ有不同的影响范围。
　　对于高斯核函数K(x,y)=e-
　　2/(2σ2)，如果σ较小，虽然可以使得样本在高维空间中线性可分，但是幅度窄、造成了过拟合的现象，导致泛化推广能力不强，并且在测试点0.5附近衰减地很快。因此高斯核函数插值能力较强，善于提取样本的局部特征[2-4]。 x-y的核函数，存在数据集在高维空间不平坦的问题(No-Flat Problem，NFP)，测试点在低维特征空间比较密集，但是映射到高维空间后却相当稀疏。为了解决这个问题，我们必须要让核函数在测试点附近的距离有较快的衰减，同时还要让核函数在远处有一定的衰减[2-4]。
　　为此，我们提出了双高斯合成函数（Double Gaussian kernel Mixed-function，DGMF）：
　　(4)
　　其中x是输入向量，ic和jc是分属于类i C和类jC的训练向量，||
　　图4不同高斯核函数远离测试点处对比
　　如图3、图4所示，改进后的高斯核函数在测试点附近具有较快的衰减，而传统的高斯核函数在测试点附近衰减较慢；在远离测试点的区域，传统核函数衰减几乎停滞了，而改进的高斯核函数还可以缓慢衰减。根据统计学习理论，这就可解决数据集映射到高
　　维空间后稀疏的缺点，提高了SVM的泛化能力[1,3-4]。
　　3基于DGMF的多核函数
　　SVM性能是由核函数决定的：局部核函数学习能力强、泛化能力弱；全局核函数刚好相反[2]。因此，可将这两类核函数组合，这样既有较好的学习能力又有较强的泛化能力。目前常将高斯径向基函数与多项式函数组合构造SVM，但该方法较依赖数据集自身的特性，容易出现数据偏斜现象[3-4]。
　　按照这种思路，以上组合核函数的泛化推广能力是否可以提高呢？就着这个疑问，该文尝试将DGMF、sigmoid、多项式核函数进行了加权组合构造了新的核函数
　　λi=1,λi>0
　　通过图3，我们可以看出，该核函数在同一个测试点附近的不同区域中，有着多个波峰和波谷，这表明了新核函数对数据集的适应性强；同时波峰和波谷的幅度狭窄，具有良好的局部性特征，学习能力强；在远离测试点区域有着较为缓慢的衰减，该新核函数推广泛化能力强。这就提高了核函数对数据集的适应性，同时学习能力、泛化推广能力也获得了提高[1,3-4]。
　　4 PSO优化基于DGMF的多核SVM参数
　　交叉验证法、网格搜索法、遗传算法是优化SVM参数的常用算法。但交叉验证法在训练集划分成子集的过程中没有理论指导，很难获得最优划分；网格搜索法的搜索步长和范围的设定没有理论指导，靠的是经验选取；遗传算法计算复杂、速度较慢、容易陷入局部极值[4-5]。
　　粒子群优化算法( Particle Swarm Optimization，PSO )是由Eberhart等发明的基于迭代的全局进化算法，具有进化计算、群智能、计算简单速度快、不易陷入局部极值等特点，这对求解基于DGMF的多核SVM参数提供了良好的工具。
　　5基于PGMSVM的文本倾向性分类算法
　　本文提出一种PSO优化参数，基于DGMF的多核SVM（Particle Swarm Optimization and Multi-Core Support Vector Machine of Im? proved Gaussian Kernel Function，PGMSVM）。将其运用在实验中与传统算法进行对比。
　　该算法主要思想如下：
　　通过DGMF，使核函数在测试点附近的距离有较快的衰减，在远处有缓慢的衰减，从而解决传统算法中依赖数据集特征、容易出现数据偏斜的问题。
　　将DGMF与Sigma、多项式核函数组合，使其在同一个测试点附近的不同区域有多个波峰波谷，提高对数据集的适应性；由于波峰波谷的幅度狭窄，具有良好的局部性特征，提高了学习能力；在远离测试点区域有着较为缓慢的衰减，提高了泛化能力。
　　利用PSO进化计算、群智能、算法简单、计算速度快、不容易陷入局部极值等特点求解SVM参数，提高了自动寻优性能。
　　实验系统架构如图6所示：图6基于PGMSVM的文本倾向性分类实验系统架构
　　实验系统流程如下：
　　将训练文本及待分类文本输入中科院计算所汉语词法分析系统ICTCLAS，进行单词、命名实体识别，分词、词性标注等工作；采用TF-IDF表示文本，：
　　其中tfij是第i个文本特征项在文本dj中出现的次数，N为文本集合中所有文本的数量，Ni为出现的第i个文本特征项的文本数量。
　　将向量化特征和类别数据输入PSO：通过循环迭代，对速度、种群、自适应粒子、适应度、个体最优和群体最优更新，代入下式：
　　计算公式（8）中的αi和b、并且与待测试文本向量化特征和类别数据代入公式(9)：
　　f(x)=sgn?
　　è??
　　6实验与分析
　　6.1实验数据集
　　实验使用美国加州大学尔湾分校提供的机器学习数据库Most Popular Data Sets (hits since 2007)中的三个数据集：Abalone、Iris、Wine。在每一次试验中随机挑选其中的两个类别作为正负类实验数据，随机取数据量的4/5为训练集、1/5为测试集。6.2实验1：DGMF与传统高斯核函数的对比
　　为了有效地测试我们提出的基于DGMF的算法是否能提高分类效果，我们首先设计了如下2个基准算法以作对比：1）基于核函数K1(x,y)=exp(
　　)2)的SVM分类算法。
　　为了方便起见，称这2种基准算法分别为分类算法I、分类算法II。我们对每一组实验，采取多次实验后的平均值作为最终的结果。
　　从图7、图8中我们可以看出，基于“Abalone”数据集、“Iris”数据集和“Wine”数据集的实验，不论是准确率还是召回率还是F1值，算法II都一致地高于算法I，分别有了4.43%、4.94%、4.69%、2.11%、1.34%、1.73%、3.93%、1.03%、2.47%的提高。而宏平均准确率、宏平均召回率、微平均准确率、微平均召回率，算法II也一致地高于算法I，分别有了1.00%、1.95%、3.16%、1.50%的提高，这说明我们提出的基于DGMF的支持向量机确实能有效的提高分类的效果。图8 DGMF与传统高斯核函数的宏平均值、微平均值对比
　　6.3实验2：基于DGMF的多核SVM与传统组合核函数SVM对比
　　为了有效地测试本章提出的基于DGMF的多核SVM的算法是否能提高分类效果，我们还另外设计了如下2个基准算法以作对比：
　　1）基于常用的传统组合核函数的SVM分类算法：
　　λi=1并且λi>0。
　　为了方便起见，称这2种基准算法分别为分类算法III、分类算法IV。我们对每一组实验，采取多次实验后的平均值作为最终的结果。
　　上面我们引入了三个参数λ1、λ2、λ3，用来调整改进的高斯核函数、多项式核函数、sigma核函数分别占的权重，下面我们通过实验来确定这三个参数值。首先通过网格法，得出λ1＝0.4。后面利用校验集，我们得到当λ2和λ3变化时，算法IV的F1值和准确率Precision分别如表1和表2所示。
　　F1值通常是首先被用来衡量分类效果的评价标准，因为它反映的是分类的整体效果，综合了准确率和召回率两方面的信息。而在保证了F1值的情况下，人们往往又对准确率有着更高的要求。所以我们从表1中选择F1值居于前五位的 1-λ1值在表2中哪个准确率最高。这样在我们的系统中可以求出λ1＝0.4、λ2＝0.27、λ3＝0.33。
　　从图9、图10中我们可以看出，基于“Abalone”数据集、“Iris”数据集和“Wine”数据集的实验，不论是准确率还是召回率还是F1值，算法IV都一致地高于算法III，分别有了1.15%、1.44%、1.30%、0.31%、0.83%、0.57%、0.72%、0.99%、0.86%的提高。而宏平均准确率、宏平均召回率、微平均准确率、微平均召回率，算法IV也一致地高于算法III，分别有了1.76%、1.19%、0.72%、2.17%的提高，这说明我们提出的基于DGMF的多核SVM确实能有效的提高分类的效果。
　　图10分类算法3、4对比实验（宏平均值、微平均值）
　　6.4实验3：基于DGMF的单核与多核SVM对比
　　本节实验对比的是分类算法II和分类算法IV，看到底是基于DGMF的多核函数SVM效率高，还是基于DGMF的单核函数SVM效率高。我们对每一组实验，采取多次实验后的平均值作为最终的结果。对于分类算法IV中的参数，按照实验2所得来设置，即λ1＝0.4、λ2＝0.27、λ3＝0.33。
　　从中我们可以看出，基于“Abalone”数据集、“Iris”数据集和“Wine”数据集的实验，不论是准确率还是召回率还是F1值，算法IV都一致地高于算法II，分别有了1.50%、2.00%、1.76%、1.07%、1.59%、1.32%、1.53%、2.86%、2.20%的提高。而宏平均准确率、宏平均召回率、微平均准确率、微平均召回率，算法IV也一致地高于算法II，分别有了2.30%、1.41%、2.01%、2.54%的提高，这说明基于DGMF的多核函数SVM效率比基于DGMF的单核函数SVM效率高。
　　图12分类算法2、4对比实验（宏平均值、微平均值）
　　6.5实验4：不同优化算法对基于DGMF的多核SVM进行优化对比
　　在本章的实验部分，为了能确认哪一种优化算法能够最大限度地将基于DGMF的多核SVM的分类性能最高。我们还设计了以人工设定参数、交叉验证法、网格搜索算法、遗传算法、PSO算法为基础的五个基准算法以作对比：
　　λi=1并且λi>0。
　　1）基于核函数(12)的SVM且采用人工设定参数的分类算法；2）基于核函数(12)的SVM且采用交叉验证优化的分类算法；3）基于核函数(12)的SVM且采用网格搜索优化的分类算法；4）基于核函数(12)的SVM且采用遗传算法优化的分类算法；5）基于核函数(12)的SVM且采用PSO优化的分类算法；
　　在本章的剩余部分，为了方便起见，称这五种基准算法分别为分类算法V、算法VI、算法VII、算法VIII、算法IX。我们对每一组实验，采取多次实验后的平均值作为最终的结果。对于算法V中的参数λ1、λ2和λ3，根据3.5.4小节中的校验集法，可以得出λ1＝0.4、λ2＝0.27、λ3＝0.33。
　　从图13中我们可以看出，基于“Abalone”数据集、“Iris”数据集和“Wine”数据集的实验，其中分类算法V的效果比不上分类算法VI、算法VII、算法VIII、算法IX，这说明采用人工的办法对基于DGMF的多核SVM的参数进行设置，分类效果是最差的；同时分类算法VI、算法VII的效果互有优劣，根据不同的数据集，有时候是分类算法VI的效果好一些，有时候是分类算法VII的效果好一些。另外，分类算法IX的效果好于分类算法VIII，说明我们采用的PSO优化基于DGMF的多核SVM的参数，优于遗传算法来优化基于DGMF的多核SVM的参数。因此，不论是准确率还是召回率还是F1值，算法IX都一致的高于算法V、算法VI、算法VII、算法VII。
　　从图14中我们可以看出，宏平均准确率、宏平均召回率、微平均准确率、微平均召回率，算法IX都一致的高于算法V、算法VI、算法VII、算法VII。
　　宏平均准确率分别有了6.09%、3.83%、4.06%、1.75%的提高；宏平均召回率分别有了8.07%、0.81%、0.46%、0.27%的提高；微平均准确率分别有了5.87%、3.35%、1.66%、0.75%的提高；微平均召回率分别有了5.74%、4.11%、3.24%、2.14%的提高。这说明我们采用的PSO优化基于DBMF的多核SVM的参数，确实能有效的提高分类效果。
　　7结论
　　本文研究了基于改进高斯核函数的多核SVM，其一是对传统的高斯核函数进行了研究，分析其优缺点。在此基础之上，提出了双高斯合成函数（DGMF）。该函数既能够在测试点附近的距离有较快的衰减，同时还能够在远离测试点的区域有一定的衰减。解决了测试点在低维特征空间比较密集，但是映射到高维空间后却稀疏的缺点，提高了支持向量机的泛化推广能力。
　　其二，将DGMF、sigmoid核函数、多项式核函数进行了加权组合构造了新的核函数，并且以美国加州大学尔湾分校（UCI，University of California,Irvine）提供的机器学习数据集――Abalone、Iris和Wine数据集为基础，进行了相关的实验，证明了该核函数获得了比单一核函数、含传统高斯函数的组合核函数有更加优异的性能。
　　其三，将PSO对基于DGMF的多核SVM参数进行优化的算法，与传统的人工优化、交叉验证优化、遗传算法优化进行了对比。实验证明，采用PSO对基于DGMF的多核SVM参数进行优化的算法，要比人工优化、交叉验证优化、遗传算法优化基于DGMF的多核SVM算法要优越，实验取得了较好的预期目标。
　　参考文献：
　　[1] Keerthi S S,Lin C J.Asymptotic behaviors of support vector machines with Gaussian kernel[J].Neural Computation 2003,15(7):1667-1689.
　　[2] Smits C F,Jordaan E M.Improved SVM Regression using Mixtures of Kernels [C].Proceedings of the 2002 International Joint Conference on Neural Networks.Hawaii:IEEE,2002:2785-2790.
　　[3]吴涛.核函数的性质方法及其在检测中的应用[D].长沙:国防科技大学,2003.
　　[4]田冬阳.一种基于改进支持向量机的文本倾向性分类算法[D].上海:上海交通大学,2011.
　　[5]田冬阳.一种基于改进支持向量机的文本倾向性分类算法[J].微型电脑应用,2011,27(3):34-31.
　　[6] Read J. A pruned problem transformation method for multi-label classification[C].Proc. 2008 New Zealand Computer Science Research Student Conference (NZCSRS 2008). 2008:143–150.
　　[7] Tsoumakas G., Vlahavas I..Random k-labelsets: An ensemble method for multilabel classification[C]. Proceedings of the 18th European Conference on Machine Learning (ECML 2007), Warsaw, Poland 2007:406–417.
　　[8] Zhang M L,Zhou Z H..Multi-label learning by instance differentiation[C].Proceedings of the Twenty-Second AAAI Conference on Artifi? cial Intelligence,Vancouver, Britiths Columbia,Canada, AAAI Press,2007:669–674.
　　[9] Brinker K,H¨ullermeier E:Case-based multilabel ranking[C].Proceedings of the 20th International Conference on Artificial Intelligence(IJCAI’07), Hyderabad, India,2007:702–707.
　　[10] Zhang M L,Zhou Z H:Ml-knn: A lazy learning approach to multi-label learning[J].Pattern Recognition 40,2007:2038–2048.