计算机科学2007V01．34 N0．6 基于二进制PSO算法的特征选择及SVM参数同步优化*) 任江涛赵少东许盛灿印鉴 (中山大学计算机科学系广州510275) 摘要特征选择及分类器参数优化是提高分类器性能的两个重要方面，传统上这两个问题是分开解决的。近年来， 随着进化优化计算技术在模式识别领域的广泛应用，编码上的灵活性使得特征选择及参数的同步优化成为一种可能 和趋势。为了解决此问题，本文研究采用二进制PSO算法同步进行特征选择及SVM参数的同步优化，提出了一种 PSO-SVM算法。实验表明，该方法可有效地找出合适的特征子集及SVM参数，并取得较好的分类效果；且与文I-4] 所提出的GA-SXqVI算法相比具有特征精简幅度较大、运行效率较高等优点。 关键词特征选择，支持向量机，同步优化，粒子群算法 Simultaneous Feature Selection and SVM Parameters Optimization Algorithm Based on Binary PSO REN Jiang-Tao ZHAO Shao-Dong XU Shen-ChanⅥN Jian (Department of Computer Science，Zhongshan University，Guangzhou 510275) Feature selection and classifier parameter optimization are two important aspects for improving classifier per— Abstract formance and are solved separately traditionally．Recently，with the wide applications of evolutionary computation in pattern recognition area，simultaneous feature selection and parameter optimization become possible and tendency．To solve the problem，we propose a simultaneous feature selection and SVM parameter optimization algorithm based on bi— nary PSO algorithm called PSO-SVM The experiments show that the algorithm can efficiently find the suitable feature subsets and SVM parameters．which result in good classification performance．Compared with GA-SVIVI[“，PSO-SVM can get a more compact feature subset and run more efficiently． Keywords Feature selection，SVM，Simultaneous optimization，PSO 1 引言 分类问题是模式识别领域的核心问题，主要包括分类器 模型的选择、特征选择及分类器参数优化等子问题。近年来， 随着模式识别研究的深入，研究对象越来越复杂，对象的特征 维数越来越高。大量高维数据对象的特征空间中含有许多冗 余特征甚至噪声特征，这些特征一方面可能降低分类或聚类 分类问题[1…。 针对特征选择及SVM参数同步优化问题，本文提出了 一种基于二进制PSO算法同步进行特征选择及SVM参数同 步优化的PSO-SVM算法。论文的第2部分首先介绍了PSO 算法的基本原理，第3部分介绍了SVM算法，第4部分讨论 了所提出的基于PSO同步进行特征选择及SVM参数优化的 PSO-SVM算法，第5部分给出了实验研究结果，最后是对本 的精度，另一方面会大大增加学习及训练的时间及空间复杂 文的总结。 度。因此，在面对高维数据进行分类或聚类时，通常需要运用 特征选择算法找到具有较好可分性的特征子空间，从而实现 降维，降低机器学习的时间及空间复杂度[1“]。因此，模式识 别领域研究出了大量的特征选择算法。另外，合适的参数设 置对于提高分类器模型的分类精度非常重要，错误的参数设 置往往会大幅降低分类器的性能，因此分类器参数优化也是 模式识别领域重要的研究方向之一。 2 PSO算法 粒子群优化算法(PSO)是一种进化计算技术，源于对鸟 群捕食的行为模拟，由Eberhart和Kennedy提出。系统初始 化为一组随机解，通过迭代搜寻最优值。但是并不同于遗传 算法使用的交叉以及变异，而是粒子在解空间追随当前最优 的粒子进行搜索。同遗传算法相比，PSO的优势在于简单易 传统上，特征选择与分类器参数优化问题一般是分别研 究的，但近年来出现了一种趋势，将这两个问题融合起来同步 实现并且没有许多参数需要调整。目前已经广泛应用于函数 优化，神经网络训练，模糊系统控制以及其他遗传算法的应用 研究。文f4]提出了一种应用遗传算法(GA)同步进行特征选 择及SVM参数优化的方法。文[5]提出了一种应用遗传规 划(GP)同步进行特征选择及分类器参数优化的方法，都取得 了不错的效果。 领域。 PSO中，将每个粒子也就是优化问题的解看作是搜索空 间中的一点。所有的粒子都有一个表示当前在解空间中位置 的属性X一(黝，勋，…，X。)，并由评价函数计算其适应度， PSO算法是一种新兴的优化技术，其思想来源于人工生 命及演化计算理论。PSO通过粒子追随自己找到的最优解 核整个粒子群的最优解来进行优化[6’7]。近年来，粒子群算 每个粒子还有一个速度Ⅵ=(让。，viz，…，V／D)决定它们运动 的方向和距离。粒子之间通过共享当前最优粒子的信息，在 解空间中搜索。 法(PSO)在模式识别与数据挖掘领域得到了许多应用，如二 进制PSO算法用于特征选择[8’9]，PSO算法还被应用于解决 首先粒子群初始化为一群随机粒子(随机解)，然后通过 迭代来寻找最优解。在每一轮的迭代中，粒子通过速度更新 *)本文研究得到国家自然科学基金资助(60573097)、广东省自然科学基金资助(04300462、05200302)。任江涛博士，讲师，主要研究方向：数 据挖掘与知识发现、生物信息学、商务智能。 万方数据 ·179· 

当前位置，并通过适应值函数计算出其适应值，然后粒子根据 本属于第一类，标记为1，如果属于第二类，则标记为一1，数 以下的速度更新公式进行计算，更新其当前速度。 学定义如下： rid—rid+C1×rand×(Pd--X“)+C2×rand×(声耐--X“) (1) 32d一37／d 4-％ 式(1)是粒子的速度更新公式，P。一(夕n，P一…，加)表 示粒子i的局部最优值，即粒子i目前为止在搜索空间中到 过的最佳点，Pg一(户小P92，…，细)表示整个粒子群的全局 最优值，即整个粒子群到目前为止在搜索空间中到过的最佳 点。Ct和cz是两个正的常数，称为学习因子。rand表示0到 (2) 1之间的随机数。公式(2)是粒子的位置更新公式。 为了适应PSO算法在离散问题中的应用，Kennedy和 Eberhart于1997年提出了二进制PSO算法。在二进制PSO 算法中，每个粒子被编码为一个二进制向量。在二进制粒子 中，速度定义了粒子的每个位置赋值为1的概率，因此要通过 转换函数将速度转换到区间Eo．0，1．ol。本研究中采用sig— moid函数。二进制的粒子更新公式如下： f1，rand()≤S(vi》) 岛一1 o。otherwise 为了获得更好的优化效率和效果，本研究对PSO算法进 … q’ 行了一些改进，在每轮迭代中将适应度最差的10％粒子进行 变异。实验证明这10％的粒子浪费计算资源，而进行变异后 粒子群能够更快地找到最优值，并且避免了容易聚集于局部 最优的情况。 3支持向量机 传统的统计模式识别方法都是在样本数目足够多的前提 下进行研究，所提出的方法只有在样本数趋于无穷大时其性 能才有理论上的保证。而实际上，样本数目通常是有限的。 而近年来迅速发展起来的统计学习理论是一种专门研究小样 本学习的模式识别理论，为研究有限样本情况下的统计模式 识别和更广泛的机器学习问题建立了一个较好的理论框架， 同时也发展了一种新的模式识别方法——支持向量机，能够 较好地解决小样本学习问题。 支持向量机在解决小样本、非线性及高维模式识别问题中 表现出许多特有的优势，决定使用它进行学习和分类。下面对 支持向量机进行模式学习和分类的原理进行简要介绍[11|。 假设输入模式集D有M个n维样本，分为两类，如果样 D一』‘zt，yi)li∈{1，2，…，M}，l J lXi∈R”，Y。∈{4-1，一1) (4) 假定输入模式集D中的样本可以被下式所描述的一个 超平面正确分类， (叫·z)一6—0 这个问题可表达为， (叫·Xi)一6≥1 (硼·Xi)一《一1 上式可以简化为 ifyi一1 if yi一一1 y。[(叫·五)-51≥1 iE{1，2，…，M) (5) … (7) 可以很容易得出结论，求解满足条件(4)的最优超平面问 题可以表达为 Minimize西(硼)一ll W||2 该问题还可转化为如下形式， ，(z)=sign(∑akykK(xk，z)4-6) (8) (9) 其中，K(x，y)为核函数，b是根据训练样本确定的阈值，m 由二次规划确定。在支持向量机中，其决策面的特性是由核 函数确定的，而支持向量机正是通过决策面来实现样本分类 的。核函数有很多种，如线性核函数、多项式核函数、径向基 核函数等。 4 PSOm SVM特征选择及参数优化同步算法 下面从粒子设计、适应度函数及算法流程等方面分别进 行介绍。 4．1粒子设计 粒子用一个二进制位串表示，其结构应该根据所采用的 核函数来确定。本研究采用RBF函数作为SVM的核函数， RBF核函数的定义如式(10)所示。 K(x，y)=exp(--y||z—y{l 2)，7>0 针对采用RBF核函数的SVM，需要优化的参数有两个： 核参数7>0和惩罚参数(penalty parameter)C>0，另外，还要 同步进行特征选择。因此，粒子应该包含三个部分，即参数 (10) C、参数y和特征掩码，如图1所示。粒子的前托位代表参数 C，中间n，位表示参数y，最后n，位代表特征掩码。nc和n， 根据精度要求来确定，nF由数据集的特征数决定。 图1粒子结构示意图 粒子中代表参数c和y的位串可以通过式(11)转换为十 由于该算法目标为同步优化特征子集SVM参数以提高 进制表示的实际参数。式(11)中P表示参数的十进制值， minp表示参数的最小值，maxp表示参数的最大值，z表示参 SVM算法的分类正确率，同时尽可能降低所选择的特征数， 即一个粒子能够使分类器产生的分类精度越高，同时选出的 数的二进制位串长度(对应于参数C和y分别为nc和n，)，d 特征数目越少，它的适应值就应该越高。因此，本研究采用如 表示参数的二进制位串的十进制值。参数的精度(由代表该 参数的位串的长度l决定)和范围(由参数的最小值和最大值 确定)都可以根据需要设定。对于特征掩码部分，每一个二进 制位对应特征集合中的一个特征，该位为1则表示对应的特 征入选特征子集，而该位为0则表示对应的特征不在选出的 特征子集中。 p=minp q．max。／,，--m，mp×d Z。一l 4．2适应度函数 万方数据 · 180· (11) 式(12)所示的粒子适应度函数定义。 厅￡埘ss一让k×szgrLaccuracy+wf×(∑．^)-1 (12) 叩 其中，毗表示分类精度的权重；svlTLaccuracy表示SVM的 分类精度；wf表示特征数目倒数的权重；^表示第i个特征 在特征掩码中的对应位，1表示特征被选中，0表示未选中； 砒和Wr根据实际需要确定。 4．3算法流程 算法1：PSOSVM(D，C1，C2，PN，m溉，max．，m畸， 

ma琦，7／c，珥，nf，砒,wf，N) 时，也采用文I-1]所提出的GA_sVM的实验结果进行对比。 输入：数据集D，学习因子C，、Cz，粒子数目PN，参数C、y 上述两种方法分别简记为SVM和GA-SVM，其实验也采用 的最小最大值m毗，max：，mint，ma毡及二进制位串长度，zc 交叉验证法进行评价。 和以，，特征二进制位串长度行，、权重参数Wa，wf、最大迭代次 下面描述粒子适应度函数中分类精度指标svnLaccura— 数N cy的定义。 输出：优化的特征子集、SVM参数C、y及相应的分类精 度 步骤： 1)初始化粒子群； 2)根据粒子编码方案及式(11)，将每个粒子的二进制表 对于二类数据集(即数据集中的样本只有两类，分别称为 正例和反例)，本文先定义三个命中率：正命中率、反命中率和 总体命中率，见式(13)。 f珞一咒甜mp Nump <“一咒“碥：／Nurn。 (13) 达转化为SVM的参数C、7及所选择的特征子集，然后调用 【％一(nump+num．)／(N“mp+N“％) LIBSvIⅥ算法进行学习和训练，测试并记录分类精度，根据式 (12)计算粒子适应度； 其中如为正命中率；rn为反命中率；k为总体命中率；hump 表示被分类器正确分类的正例样本数目；nurn。表示被分类器 3)根据粒子适应度，更新只及P。； 4)根据式(1)，更新粒子的速度； 5)根据式(3)，更新粒子的二进制位； 6)判断是否达到最大迭代次数N，若达到则输出当前最 优的特征子集、参数c、y及分类精度，否则返回步骤2)继续 迭代。 5实验研究 正确分类的反例样本数目；Nump表示数据集中正例样本总 数；N“％表示数据集中反例样本总数。 对于类别数为2的数据集，采用rp×rn而不是心来度量 分类精度。因为一个好的分类器，不但总体的命中率要高，而 且表现要均匀，即对于不同的类，其分类精度不能相差很大。 这一点对二类数据集尤为重要。所以，采用bד代表 svm_accuracy更加科学。而对于多类数据集，则用总体命中 率心代表其svHL accuracy。 5．1实验数据及实验环境 5．3实验参数设置 为了评估算法的有效性，采用多个UCI数据集进行实验 研究，数据集的名称及相关信息如表i所示。本研究的所有 实验在采用Intel奔腾4 3．0G CPU、内存为512M的计算机 上进行，算法用Matlab编程实现，SVM采用LIBSVME”]。 表1实验中用到的UCI数据集 NO．of NO．of Nominal Numeric Total Names 实验中算法的参数设置如下：Ct—Cz一2，粒子速度的初 始值范围是[一5，5]。粒子数目随着数据集维数的不同而不 同，具体见表2。这是因为当数据集的维数较高时，搜索空间 大，所以需要较多的粒子数目；反之，则可以采用较少的粒子 数目。当迭代次数达到300或者连续100次迭代全局最佳适 应值没有改变时，PSO算法停止。实验中用到的其它参数如 classes instances features features features 下：Wa一0．8，wf一0．2，7／R一咒s一20。C∈[2，500]，y∈ Pima-Indian diabetes 2 Heart disease 227 Ionosphere Sonar Iris Vehicle 2 2 3 4 768 O 351 208 150 990 O 7 0 O O O 8 6 34 60 4 18 8 13 34 60 4 18 5．2实验评价方法及指标 实验采用交叉验证法(Cross Validation)进行评价。数据 集被随机分成忌个子集，PSO-SVM算法在每个数据集上运 行k次，每次取一个子集作为测试集，其余尼一1个子集合并 为训练集，然后取k次实验结果的均值作为该数据集的分类 结果，本研究中取k一10。 另外，为了与PSO-SVM算法进行对比，还采用既未进行 特征选择，也未进行参数优化的SVM进行训练和测试。同 r215，1]。 表2各个数据集采用的粒子数目 Names Total features Particle No． Pima-Indian diabetes Heart disease Ionosphere Sonar Iris Vehicle 8 13 34 60 4 18 100 100 200 300 50 150 5．4实验结果 表3所示是SVM算法、GA-SVM算法和PsosVM算 法在各个数据集上的实验结果，分类精度，其中平均值是算法 在某一数据集上运行10次所得结果的平均值。 表3 SVM、PSO-SVM和GA-SVM三种方法在实验数据集上的性能比较 SVM PSo—SvM GA—SVM Average Average Average Average Average Average Average Average Average negative overall posmve negative hit rate hit rate hit rate hit rate 0．7440 0．8067 0．9377 0．7433 0．9417 0．9923 0．7920 0．9267 1．0000 overall hit rate 0．7748 0．9333 0．9971 pomtlve negative overall hit rate hit rate hit rate 0．7835 0．9447 0．9963 0．8704 0．9511 0．9876 O．8150 0．9480 0．9856 Datasets Diabetes posmve hit rate 0．7318 Heart disease 0．8000 Ionosphere 0．9532 Sonar Iris Vehicle 0．9477 0．6722 NA NA NA NA 万方数据 0．7396 0．8037 0．9431 O．8187 0．9667 0．7634 1．0000 I．0000 1．0000 0．9863 0．9842 0．9800 NA NA NA NA 0．9800 0．9256 NA NA NA NA 1．0000 0．8406 · 181 · 

表4是GA-SVM方法和PSO-SVM方法在特征选择方 选特征数目的平均值。第一列括号中的数字是该数据集原有 面的比较，其中给出了两种算法在相同数据集上运行10次所 的特征数目。 表4 P盼SVM方法和GA-SVM方法在实验数据集上的平均特征选择数目比较 PS(>SVM GA—SVM Average number of selected features Average number of selected features 1．4 4．1 3．9 5．8 1．0 9．7 3．7 5．4 6．0 15．O 1．0 9．2 Datasets Diabetes(8) Heart disease(13) Ionosphere(34) Sonar(60) Iris(4) Vchicle(18) 5．5实验结果分析 下面将根据实验结果，从分类精度、特征选择能力和算法 运行效率等三个方面对上述三种方法进行比较分析。 从表3可以看出，P盼SVM方法的分类精度比起SVM 方法有了很大的提高。在每个实验数据集上，前者的分类精 度都高于后者。l：L女tl对于二类数据集Heart，SVM方法的正 命中率、负命中率和总体命中率分别只有0．8000、0．8067和 0．8037；而P盼SVM方法的三个命中率分别达到0．9417、 0．9267和0．9333，比SVM方法分别提高了17．71％、14．88％ 和16．13％。对于多类数据集Vehicle，SVM方法的平均命中 率为0．7634；而PSO-SVM方法达到0．9256，比前者提高了 21．25％。此外，由P盼SVM方法得到的分类器更为均衡， 也就是说对于不同的类，其命中率相差不大。这一点在二类 数据集Sonar上表现最为明显。在该数据集上，SVM方法的 负命中率和正命中率分别为0．6722和0．9477，相差40． 98％；而P盼SVM方法的正负命中率都是1．0000，相差0． oo％。上述结果充分说明，在运用SVM分类器时，特征选择 和参数优化的重要性，也证明了本文提出的Psos、n，I方法 的有效性。对于PSDSⅥⅥ和G介sVM而言，从总体上看， 无论是分类器精度还是均衡性，两种方法都非常接近，都是较 为有效的方法。 从表4可以看出，平均来说，PSpSVM方法在大多数数 据集上所选出的特征数目要少于GA-SVM方法，而且这种差 别比较明显。以特征数目最多的Ionosphere(特征数目为34) 和Sonar(特征数目为60)数据集为例，Ps口s、M选出的特征 数目的均值只有3．9和5．8，而GA-SVM方法选出的特征数 目均值分别为6．0和15．0，分别是前者的1．54倍和2．57倍。 考虑到两种方法的分类精度很接近，可以得出结论说PSO- SVM方法比GA_SVM方法具有更好的特征选择效果。 在实际应用中，分类器有训练和使用两个阶段。在训练 上，SVM方法是最快的，因为不像其它两种方法需要使用优 化算法(PSO或GA)进行特征选择和参数优化。但是，训练 阶段特征选择的缺失，将降低使用阶段SVM的分类精度；且 过多的特征数目将使得SVM运行变慢。而一个分类器的使 用阶段要长于训练阶段，所以从长远看，SVM方法的效率较 差。从训练阶段看，在相同的数据集上达到类似的分类精度， GA-SVM方法需要进行600次迭代而PspsVM方法只需进 行300次迭代。而且，GA-SVM方法对于每个数据集都采用 了500个染色体，而P鼢SVM方法则根据数据集的特征数 选择粒子数目，最多300，最少50。上述结果表明，P盼SVM 算法的运行效率优于GA-SVM算法。 综上所述，从分类精度、特征选择能力及算法运行效率等 方面综合比较分析，P盼SVM算法要优于另外两种算法。 结论本研究受到文[4]所提出的GA-SⅥⅥ算法启发， 提出了一种基于PSO同步进行特征选择及SVM参数同步优 化的PSO-SVIVl算法。实验表明，该方法可有效地找出合适 的特征子集及SVM参数，并取得较好的分类效果；且与GA_ SVIVl算法相比具有特征精简幅度较大、运行效率较高等 优点。 参考文献 1 2 3 4 5 6 7 8 9 John G H，Kohavi R，Pfleger K．Irrelevant Features and the Sub— set Selection Problem[A]．In：Proceedings of the Eleventh Inter— national Conference on Machine Learning[El，New Brurlswick， NJ，USA，Morgan Kaufmann，1994．121～129 Kohavi R，John G H．Wrappers for feature subset selection口]． Artificial Intelligence，1997，97(1—2)：273～324 Liu Huan，Yu Lei．Toward Integrating Feature Selection Algo— rithms for Classification and Clustering[J]．IEEE Transactions on Knowledge and Data Engineering，2005，17(5)：491～502 Huang C-L，Wang C-J．A GA-based feature selection and param— eters optimization for support vector machines．Expert Systems with Applications，2006，31(2)：231～240 Muni D P，Pal N R，Das J．Genetic Programming for Simultane— OUS Feature Selection and Classifier Design．IEEE Transactions on Systems，Man，and Cybernetics-Part B，2006，36(1)：106～ 117 Kennedy J，Eberhart R C Particle swarlTl optimization．In：Pro— ceedings of IEEE International Conference on Neural Networks． Piscataway，NJ，1995．1942～1948 Kennedy J，Eberhart R C A discrete binary version of the parti— cle swarm algorithm．In：Proceedings of the World Multiconfer— ence on Systemics，Cybernetics and Informatics 1997，Piscat— away，NJ，1997．4104～4109 Liu Yu，Qin Zheng，Xu Zenglin，He Xingshi．Feature Selection with Particle Swarms，Computational and Information Seience． In：First International Symposium，CIS 2004，Shanghai，China， December Proceedings，LNCS3314，2004．425～430 Wang Ling，Yu Jinshou．Fault Feature Selection Based on Modi— fled Binary PSo with Mutation and Its Application in Chemical Process Fault Diagnosis，ICNC 2005，LNCS3612．832～840 10 De Falco I，Della Cioppa A，Tarantino E Facing classification problems with Particle Swarm Optimization．Applied Soft Compu— ting，In Press，Available online 3 February 2006 Cristianini N，Shawe-Taylor J．An Introduction To Support Vec— tor Machines And Other Kernel—Based Learning Methods．Cam— briage University Press，2000 11 12 Chang C-C，Lin C-J．UBSVM：a library for support vector ma— chines 万方数据 · 182 · 

基于二进制PSO算法的特征选择及SVM参数同步优化 作者： 任江涛， 赵少东， 许盛灿， 印鉴， REN Jiang-Tao， ZHAO Shao-Dong， XU Shen-Chan 作者单位： 刊名： ， YIN Jian 中山大学计算机科学系,广州,510275 计算机科学 英文刊名： COMPUTER SCIENCE 年，卷(期)： 2007,34(6) 3次 被引用次数： 参考文献(12条) 1.Muni D P;Pal N R;Das J Genetic Programming for Simultaneous Feature Selection and Classifier Design[外文期刊] 2006(01) 2.Huang C-L;Wang C-J A GA-based feature selection and parameters optimization for support vector machines[外文期刊] 2006(02) 3.Liu Huan;Yu Lei Toward Integrating Feature Selection Algorithms for Classification and Clustering [外文期刊] 2005(05) 4.Kohavi R;John G H Wrappers for feature subset selection 1997(1-2) 5.Chang C-C;Lin C-J LIBSVM:a library for support vector machines 6.Cristianini N;Shawe-Taylor J An Introduction To Support Vector Machines And Other Kernel-Based Learning Methods 2000 7.De Falco I;Della Cioppa A;Tarantino E Facing classification problems with Particle Swarm Optimization 2006 8.Wang Ling;Yu Jinshou Fault Feature Selection Based on Modified Binary PSO with Mutation and Its Application in Chemical Process Fault Diagnosis 9.Liu Yu;Qin Zheng;Xu Zenglin;He Xingshi Feature Selection with Particle Swarms,Computational and Information Science 2004 10.Kennedy J;Eberhart R C A discrete binary version of the particle swarm algorithm 1997 11.Kennedy J;Eberhart R C Particle swarm optimization[外文会议] 1995 12.John G H;Kohavi R;Pfleger K Irrelevant Features and the Subset Selection Problem 1994 引证文献(3条) 1.申宇皓.孟晨.张磊.傅振华.石纯 基于同步优化的支持向量机模拟电路故障诊断方法研究[期刊论文]-太原理工大 学学报 2010(4) 2.张宏达.王晓丹.徐海龙 用于RBF-SVM参数搜索的伪梯度动态步长算法[期刊论文]-电子科技大学学报 2010(4) 3.李雪.刘弘 结合二进制PSO的SVM在园林评价中的应用[期刊论文]-计算机工程与应用 2009(6) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjkx200706049.aspx