基于PSO的支持向量机改进算法研究

邱宁佳，贺金彪，赵建平，李岩芳

（长春理工大学 计算机科学技术学院，长春 130022）

支持向量机算法是通过寻求结构最小化来实现风险最小化的机器学习算法，以期待在有限条件的情况下得到最优结构。非线性和维数灾难问题以及局部极小问题等问题都可以通过支持向量机在一定程度上得到解决。此外，支持向量机分类的精度与其本身的参数和多分类模型的选择有很大的关系。为了解决以上问题，相关学者提出了不同的方法进行尝试，以提高支持向量机的分类精确度。

崔建明等针对文本分类器的性能容易受到核函数和参数的影响问题，将优化的粒子群算法引入SVM分类算法中，利用粒子群优化算法寻找最佳参数并用SVM算法进行分类，实验表明优化后的SVM分类器的准确性更高［1］；单黎黎等引入动量因子来缓解粒子群算法极易陷入局部极小值的问题，然后采用改进的粒子群算法实现对由径向基函数和多项式函数组合而成的混合核函数的参数寻优，实验表明基于粒子群改进的混合函数支持向量机分类器具有较好的分类精度［2］；Sun等针对数据挖掘中的大尺度和多维度导致的时间浪费和精度降低问题，提出了一种基于多准则排序和C-SVM的特征选择方法m CRC，通过互信息和类距离计算特征和标签之间的依赖关系，删除无关的和完全冗余的属性［3］；Zhang等为了解决SVM处理大规模多类样本时的低学习效率问题，提出了一种基于多聚类的多分类SVM快速学习方法，保证了较高的分类精确率并减少样本数量，有效提高学习效率［4］；梁钰针对SVM分类算法处理数据时未考虑语义的相似性度量问题，利用LDA主题模型进行建模和特征选择确定主题数和隐主题，在此特征空间下使用SVM分类器进行分类［5］；王道明等利用自变异的PSO聚类算法在每一个决策点自动寻找最优或最近分类决策，将数据集划分为两类，直至叶子节点位置，最终根据最优决策树构建SVM多分类结构，实验表明改进的多分类结构在分类精度和时间上得到明显改善［6］；朱庆生等重新定义遗传算法中的适应度函数，提出了一种基于累积适用度遗传算法的支持向量机多分类算法，改善基于遗传算法的支持向量机多分类决策树算法中存在的全局优化缺陷问题，使其分类精确度有所提高［7］；衣治安采用二叉树结构与多个支持向量机子分类器组合进行Web文本信息分类，提出了一种新的支持向量机的多类分类方法提高了分类精度，体现了将遗传算法与二叉树支持向量机结合的优越性［8］；王鹏等人提出了一种基于边分类的SVM模型对分类函数的参数进行估计进而对真实网络进行社区分类，实验得到了较高的整体准确度［9］；黄刚等针对SVM算法和朴素贝叶斯算法的缺点，对朴素贝叶斯算法进行分析和改进，提出了SVM-WNB分类算法并验证改进的算法在准确性方面有明显提升［10］。王振武等考虑传统粒子群算法后期震荡严重的缺陷，引入混沌序列来初始化粒子群的位置，并在简化的粒子群数学模型上对其改进用于优化支持向量机的模型参数，实验结果表明具有较高的分类准确率［11］。

上述支持向量机模型均在不同程度上提升了分类的精确度，但这些算法都只是针对核函数或多分类单方面做了改进，并没有同时考虑两种情况，然而本文涉及的是多分类问题，要同时考虑以上两种情况。因此提出一种改进的PSO-SVM算法来提升多分类性能。

1 文本预处理

在文本分类中，特征选择方法能从高维的特征空间中选取对分类有效的特征，降低特征的冗余度，提高分类准确度。Li等针对多标签学习算法性能很大程度取决于输入特征，提出了一种基于互信息的多标签学习的粒度特征加权KNN算法以避免标签组合爆炸问题，有效地提高了其分类性能［12］；陶永才提出了一种基于MapReduce的互信息文本特征选择机制，利用其能够处理大规模数据的优势，缩短文本训练和分类的过程从而提高文本分类的精度［13］；余璇利用互信息能够表达变量间相关性的特点，使用特征权重改进主题分类算法特征贡献度进而提高分类的准确率［14］；董露露提出了一种改进的互信息特征选择方法，引入平均词频和绝对值最大因子，提高了文本分类性能［15］；Luo为了解决微博情感分析忽略情感符号和网络词的问题，提出了一种扩展语义定向的逐点互信息算法来构造动态情感语料库，提高了对语料库进行分类的效率［16］；Wu提出了一种基于互信息的术语加权朴素贝叶斯文本分类方法，根据文本互信息的理论部分消除了其属性独立性等于其属性重要性的假设对分类的影响［17］；Nguyen等采用改进粒子群优化算法PSOMIE的波滤器特征选择算法代替传统的互信息算法，利用一种新的适应度函数提高了分类性能同时解决了过度拟合问题［18］；基于上述互信息理论，本文提出一种改进的特征评价函数，提高文本分类的准确性。

1.1 互信息算法的改进

互信息算法是文本分类常用的特征选择方法之一，但其在理论以及现实应用中分类精度比较低。传统的互信息算法按照特征词和类别一起出现的概率来衡量特征词与类别的相关性，特征词t和类别ci的互信息公式如（1）所示：

式中，p(t,)表示在训练集中类别为且包含特征词t的文本的概率；p(t)表示在训练集中包含特征t的文本的概率，p()表示训练集中属于类别的文本的概率。

由于计算各个概率时使用的频数都是包含特征词的文本数量，并没有考虑到特征词在各个文本中出现的词频因素。当类别C中包含特征词ti和tj的文本数目一致，并且两个特征词在其他类别中都甚少出现，那么由MI公式计算出的两个特征词与类别之间的互信息值基本接近。

然而事实上，当文本中包含的特征词ti的频数远大于tj时（如特征词ti在文本出现的平均频数为10，而特征词tj在文本中出现的频数为1，那么显然，特征词ti更具有代表性，分类能力也越好），利用MI公式计算的互信息值仍相近。因此可以得出特征在某类别各个文本中出现的频数是体现特征词分类能力的重要因素，根据上述因素引入权重因子、类间和类内离散因子三个定义，具体的描述如下。

定义1.设特征集T={t1,t2,…,}tm，训练集类别集C={c1,c2,…,}cn，记fij为特征词tj在类别ci出现的总频数，Fj为特征词tj在训练集中出现的总频数。特征tj在类别ci中的权重因子，定义如式（2）所示：

一个特征词的权重因子就是该特征词在某一类别中出现的频率。特征的权重因子越大，分类性能就越强。在互信息公式中引入权重因子，削弱互信息中对低词频的倚重，增强高词频属性的影响力，提高分类准确性。

定义2.设特征集T={t1,t2,…,}tm，训练集类别集C={c1,c2,…,}cn，记fij为特征tj在属于类别ci的文本中出现的总频数，为特征词tj在所有类别文本中出现的平均频数。特征tj的类间离散因子定义如式（3）所示：

一个特征词的类间离散因子能够量化该特征词在各个类间的差异分布状况。类间分布差异越大，特征词就越具有类别代表性，其分类性能也就越强。将类间离散因子引入互信息公式，就能剔除在各个类中出现频率相当的，没有分类能力的冗余属性，进而降低计算复杂度，提高分类精确度。

定义3.设特征集T={t1,t2,…,}tm，训练集类别集C={c1,c2,…,}cn，记Di为类别ci中文档总数，fik(tj)为特征词tj在属于类别ci的文本dik中出现的次数，为特征词tj在类别ci中的文本中出现的平均频数。特征tj的类内离散因子定义如式（4）所示：

一个特征词的类内离散因子能够量化该特征在某一个类中的差异分布状况。

类内差异分布越小，特征词就越有类别代表性，分类性能也就越好。将类内离散因子引入互信息方法中，就能够筛选出在某一类别各个文档中均匀出现的特征词，提高分类性能。

1.2 改进的CDMI特征评价函数

本文着重考虑互信息方法中对低频词的影响，可能导致冗余属性成为特征词，而有用的条件属性会漏选的不足之处，引入上文所定义的权重因子、类间离散因子和类内离散因子，提出一种改进的CDMI特征选择算法，其公式如（5）所示：

其中，t为特征词，训练集类别集C={c1,c2,…,}cn，α表示为特征t的类间离散因子，βi表示为特征t在ci类内的类内离散因子，ωi表示为特征t的权重因子，p(t)表示为训练集中包含特征t的文档数和总文档数的比值，是训练文本集中含有特征t的ci类文档数与ci类文档数的比值。使用CDMI算法进行属性约简，获得彼此相对相互独立的核心属性，为支持向量机优化模型分类做准备。

2 支持向量机优化算法

核函数的选取是支持向量机理论的核心问题，而核函数的选取却常常决定了特征空间的结构。径向基核函数只有一个需要调整的参数σ，因此只需要适当的调整参数便可应用于任意分布的样本。多项式核函数推广能力强且随着阶数的减小而增强。

综合考虑，径向基核函数学习能力强、泛化能力弱的特点和多项式核函数学习能力弱、泛化能力强的特点，考虑了采用径向基核Krbf和多项式核Kpoly相结合构造混合核函数Kmix，如公式（6）所示：

其中，λ∈],1。

本文采用类似于哈夫曼树的结构构造二叉树多分类器。对于给的n个权值ω={ω1,ω2,…,ωi,…,ωn}构成n棵二叉树初始集合T，其中每个二叉树都只有一个权值为ωi根节点，其左右子树均为空，并按权值大小对集合T中的二叉树按升序排列；在二叉树集合T中选取权值最小的两棵树作为新构造的二叉树的左右子树，新的二叉树根节点的权值为左右子树根节点的权值之和；从二叉树集合T中删除选中的两棵树，并将新的二叉树同样以升序加入集合T中；直至集合T上只有一棵二叉树。

哈夫曼树中的每个非叶子节点相当于决策树中的每一个SVM分类器，而叶结点就相当于决策树中的类别。依据哈夫曼树构造原理，将用户类别样本集两两分类，取两类之间距离最小的两个用户类别作为底层的叶节点，同时将上述两个类别合成一个新的用户类别重新与其他类别进行两两分类，直至只剩下一个用户类别为止。

距离函数是用于计算类别之间的距离值，距离值越小就越说明两个类别越相近，也越难分离，具体的距离函数计算公式如（7）所示：

其中，fi,fj分别代表类别i,j中距离最近样本的分类函数，分别代表类别中所有样本分类函数的平均值。

2.1 PSO优化算法

在支持向量机分类器中引入权值的概念，创造了加权向量机模型，由于权值的选取直接影响分类的效果，为了提高分类的准确性引入PSO优化算法对初始权值进行全局寻优，获取最优权值。

在PSO优化算法中依照速度与位置公式来调整微粒的速度与位置，求得全局最优解。由于在PSO优化算法中设定了合适的初始权值，其大小只需微调，因此在迭代寻优中速度不宜过大，以免得不到精确解。为避免这种情况发生，在速度更新中，对速度设定了最低速度和最高速度，保证其收敛性，改善局部最优的状况。其速度公式和位置公式分别如（8）、（9）所示：

式中，ω表示惯性因子，φ1和φ2为学习因子，vis表示第s次更新时微粒i的速度，xis表示第s次更新时微粒i的位置，rand()为随机函数。

式中，vis+1为第s+1次更新时微粒i的速度，xis为第s次更新时微粒i的位置。根据PSO优化算法的思想，具体的算法描述如算法1所示：

算法1 PSO优化算法输入：微粒群体的规模N，迭代次数max，最高速度vmax，最低速度vmin输出：最优解初始化位置集合x=( )v1,v2,···,vi,···,vN 和 速 度 集 合v=( )v1,v2,···,vi,···,vN for each xi∈x初始位置xi作为局部最优解pbesti微粒自适应度计算fitness(xi)end for gbest=min{ }pbesti while max＞0 for i=1 to N更新vi,xi if fitness(xi)＜fitness(pbesti)当前位置xi设为局部最优解if fitness(pbesti)＜fitness(gbest)gbest=pbesti end for max=max-1 end while输出最优解gbest

针对支持向量机加权模型中权值的选取问题，本文以特征词的词频比率为初始权值并以此权值作为PSO优化算法中的初始位置，迭代寻找全局最优解。

2.2 PSO-SVM算法

SVM的分类能力受参数影响力较大，好的参数能够使SVM发挥较好的分类作用，反之则对分类性有较大影响。故而，寻找合适的参数对SVM的分类性能起着决定性的作用。由上文分析可知支持向量机的惩罚参数C、径向基核函数σ以及混合函数中权重λ对SVM的分类性能有影响，因此本文使用粒子群优化算法对于混合核函数的SVM参数组合(C,σ,λ)进行优化，之后结合哈夫曼最优二叉树原理构造支持向量机多分类器，完整的算法结构如图1所示。

图1 PSO-SVM算法结构

在特征选择过程中，针对原有互信息计算中忽略词频因素的不足之处，引入权重因子，放大高词频的影响；引入类内离散因子和类间离散因子筛选出具有类别代表性的特征词，其具体的算法描述如算法2所示：

算法2特征提取算法输入：数据集，类别集C={ }c1,c2,…,ci,…,cn输出：特征集t'文本预处理得到初始特征集t={ }t1,t2,…,tj,…，t'=∅for eachtj∈t计算 ωij，αj，βij end for for each tj∈t计算CDMI()tj ifCDMI()tj＞ε t'=t'⋃tj end for输出特征集t'

在使用PSO优化算法进行求解最优参数组合之前，首先设定了参数的最大以及最小取值，并结合以往实验经验设定了初始参数值。然后，就是要设定优化时所需要的适应度函数。由于是多分类，所以在参数求取时，将正常用户作为正类，其他用户都作为负类，进行二分类求解。记准确值为γ，测量值为γi，那么具体的公式可描述如（10）、（11）所示：

那么目标函数f(x)可表示如公式（12）所示：

适应度函数确定之后可以利用PSO优化算法对参数组合进行寻优求解，其优化过程大致流程为首先是初始化粒子群速度和位置并设定核函数参数组合(C,σ,λ)的初始参数值以及计算粒子群的初始适应度，然后通过粒子速度和位置更新求粒子最优解pbest和种群最优解gbest，最后得到的gbest就是需要的最优参数组合。

在求解出最优参数之后还需要确定多分类模型，具体的算法描述如算法3所示：

算法3 PSO-SVM算法输入：训练样本类别集C={ }c1,c2,…,ci,…,cn，n棵二叉树集合T={ }t1,t2…,ti,…,tn，类间距离 dij；输出：多分类器模型哈夫曼树T for each tn∈T计算dij，end for while n＞1 for each tn∈T计算PSO(tn)best=dij for eachci∈C if PSO(tn)＜best m=i⋃j，m∈T deli j，end for end for输出哈夫曼树T

3 实验及结果分析

本文针对支持向量机模型的改进主要分为两个部分。第一部分是对特征选择方法中的互信息方法进行改进，去除冗余特征词，降低维度，减少算法计算的复杂度，同时也改善了算法的分类精度，为了验证改进前后算法的性能，以分类效果作为标准，设计实验对其进行验证。第二部分是采用PSO优化算法对混合核函数中的参数进行优化，并以混合核函数结合哈夫曼最优二叉树优化分类器的性能。为了验证参数优化前后算法的能力，设计实验将PSO-SVM算法与传统SVM算法以及其它改进算法的性能进行对比。

实验采用Reuters-21578中的10个类别新闻组作为数据文本集，对算法进行了实验测评，使用五折交叉验证法，将样本集随机的分割成大小相等但互不相交的5份，对样本训练和验证分别进行5次，计算得出每次分类的召回率与精确率，为了使分类的结果更具科学性，防止实验的随机性和偶然性，采取5次实验结果的平均值作为最终的衡量标准。

3.1 互信息参数和粒子群参数的选取

本文称引入权重因子的MI算法为WMI算法，引入类间离散因子和类内离散因子的MI算法为CMI算法，然后将改进的CDMI算法与WMI算法、CMI算法以及MI算法进行实验对比，确定要筛选的特征词个数。下面做的对比主要是在不限定总的单词个数的情况下，四种算法能达到的分类结果的最高精确率，以及在相同的单词个数下四种算法的精确率和特征词个数。

四种算法最高精确率对比结果如表1所示。

表1 算法最高精确率对比

相同单词总数情况下，四种算法的精确率和特征词数对比如图2、3所示。

图2 精确率对比

可以看出，在数据集单词由10000下降到5000时，MI特征选择算法的分类结果呈现急速下降的趋势，而MI和CMI算法皆有小幅度的波动，而改进后的CDMI算法一直趋于稳定在0.9之上并且CDMI算法的精确率一直优于其他算法，这就体现了改进后的CDMI算法的分类性能比较稳定且在数据记单词总量变化的状态下不会发生较大的波动。结合图2和图3看出，当数据集单词数目相同情况下改进的CDMI算法所选取的特征词数量明显少于其它算法，而分类精度却明显优于其它算法，这就说明改进后的CDMI算法可以降低属性冗余，筛选出具有高分类能力的计算复杂度。因此可以得出，改进的CDMI算法无论在分类精确度还是分类性能上面都明显优于其它算法。

图3 特征词数对比

对于CDMI算法而言，在数据集的总单词数为7000的时候，分类结果的精确率是最高的，为了更加直观的说明这一因素，分别对5次实验得到的精确率平均值进行了描述，如图4所示。

图4 CDMI算法准确率对比

对于CDMI算法，在数据集的总单词数变化的过程中，特征词的数量变化如表2所示。

由表2可知，在数据集的单词总数为7000的时候，特征词的个数为140，因此将特征词的个数设置为140。将PSO-SVM算法中粒子的规模设为n=140，粒子群其它参数的选取分别为φ1=2.05，φ2=2.05，ω=0.729，rand()为（0，1）区间上均匀分布的随机数，最大迭代次数为500。

3.2 PSO-SVM算法验证

通过结合以往实验经验，基于混合核函数的PSO-SVM算法中，设置PSO参数φ1=2.05，φ2=2.05，设计实验验证，在不同迭代次数下，参数组合的取值以及取得的分类精确率。粒子群算法参数寻优中，分类精确度的变化如图5所示。

图5 PSO-SVM算法

由图可以看出，在参数组合寻优过程中，在粒子更新到150次时，分类的精确度已经达到最大值，故设定最高迭代为200次。在迭代最优的情况下参数组合分别取值：C=1.54,σ=0.41,λ=0.14。

为了验证本文所提出的PSO-SVM算法的效果，设计实验分别测试PSO-SVM和传统的SVM以及文献中提及的SVM-WNB和IPSO-SVM这四种不同的算法，为避免实验的随机性和偶然性，选取互不相交的5个测试集进行5次实验，取5次结果的平均值为最终结果，得到3种分类模型的召回率、精确率以及F-Measure的值，进而分析分类器的分类性能，其结果对比如表3所示。

表3 实验结果对比

由表3可以看出，PSO-SVM算法的召回率和精确率均高于其他三个算法。其中SVM-WNB算法使用不同的加权方法来评估特征词的重要程度，同时采用WNB算法弥补最优超平面附近分错的情况，以提高分类性能；IPSO-SVM算法利用混沌搜索的便利性初始化粒子群算法使其均匀分布于整个解空间，从而加快粒子群算法的收敛速度，从而提高分类准确率；PSO-SVM算法首先使用改进的PSO优化算法对核函数参数组合迭代求取最优核参数组合，然后利用哈夫曼最优二叉树原理构建多分类支持向量机模型，因此精确率更高，大大降低了文本类别误判的概率。

4 结束语

本文针对测试文本集中有过多的属性冗余以及支持向量机算法受参数影响力而引起的分类性能降低问题，提出了一种改进的PSO-SVM算法。首先利用改进的CDMI方法进行属性约简；然后以特征词的词频比率作为初始权值，使用绝对误差方法确定目标函数，结合粒子群优化算法求解最优的混合核函数参数组合；最后使用改进的决策树多分类模型构造支持向量机多分类器。采用召回率、F-Measure和精确率作为PSO-SVM算法的评价标准，通过与其它算法在Reuters语料集上的实验对比，可得本文改进的算法具有更高的分类精度以及更低的计算复杂度。