（计算机软件与理论专业论文）基于粒子群算法的特征选择与支持向量机参数同步优化.pdf

中山大学硕士学位论文摹于粒子群算法的特征选择与支持向量机参数同步优化 基于粒子群算法的特征选择与支持向量机参数同步优化 专业：计算机软件与理论 硕士生：赵少东 指导教师：印鉴教授 摘要 s v i 是一种新的模式分类技术，已经在许多领域得到广泛的应用。特征选 择和分类器参数优化是提高s v m 性能的两个重要方面，传统上这两个问题是分 开解决的。然而这两个问题是相互影响的，获取最佳特征子集和获取最优参数应 该同步进行。随着进化优化计算技术在模式识别领域的广泛应用，编码上的灵活 性使得特征选择及参数的同步优化成为一种可能和趋势。 为解决s 的特征选择和参数优化问题，本文提出了一种基于连续p s o 算 法的特征选择和s v m 参数同步优化算法( c p s o s v m ) ，其目标是在尽可能提 高s v m 分类精度的同时，选择尽可能少的特征数目。在真实数据集上的实验研 究表明，c p s o s v m 算法具有原始s 算法所不具备的特征选择能力，能显著 提高s v m 的分类能力( 包括更高的分类精度和更好的均衡性) ，而且从分类器 的整个生命周期来看，具有更高的效率。与h 啪gc l 等【1 2 】所提出的基于g a 的 算法相比，c p s o s 订算法在分类能力和特征性选择能力上毫不逊色，而且效 率更高。因此，c p s o s v m 算法具有较好的分类能力、特征选择能力和效率， 是一种有效的算法。 鉴于特征选择在s 分类问题上的重要性，以及离散p s o 算法比连续p s o 算法更适合处理特征选择这种组合优化问题，本文在c p s o s v m 算法的基础上， 提出了一种基于离散p s o 算法的特征选择和s v m 参数同步优化算法 ( d p s o s 垤) ，旨在提高c p s o s v m 算法的特征选择能力。在真实数据集上的 实验研究表明，d p s o s v m 算法在分类能力( 指分类器精度和均衡性) 和算法 效率方面不亚于c p s o s v m 算法，并且具有更强的特征选择能力，能够在不影 中山大学硕士学位论文基于粒予群算法的特征选择与支持向量机参数同步优化 响分类效果的前提下，选出更少的特征数目。 总的来说，本文运用p s o 算法同步解决s v m 的特征选择和参数优化问题， 取得了良好的效果。在作者所掌握的文献范围内，这方面的工作还比较缺乏。而 且，与已有的算法相比，本文所提出的算法具有更强的特征选择能力和更高的效 率。 关键字：特征选择，支持向量机，同步优化，粒子群算法 i i 中山人学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 s i m u l t a n e o u sf e a t l l r es e l e c t i o na n ds v mp a r a m e t e r so p t i n 血a t i o n a l g o r i t h m b a s e do np s o m 勾o r ：c o m p u t e rs o f l w a r e 柚dt h e o 巧 n 锄e ：z h a os h a o d o n g s u p e r v i s o r ：p r o f e s s o ry i nj i a j l a b s t r a c t s u p p o r tv r e c t o rm a c i l i n e s ，o n eo fm en e wt e e h n i q u e sf o rp a t t 锄c l a s s i 丘c a t i o n ， h a v eb e e i lw i d e l yu s e di nm 锄ya p p l i c a t i o na r e 嬲f e 以鹏s e l e c t i o n 锄dc l a s s m e r p 蹦l i i l e t e ro p t i m i z a t i o na r e 觚oi m p o r t a l l t 嬲p e c t sf o ri m p r o v i n gs v mp e r l b m a i l c e a l l da r es 0 1 v e ds 印鲫l t e l y 仃a d i t i o n a l l y h o w e v t h 懿e 觚op r o b l e m si n n u e l l c ee a c h o m e r ，s oo b t a i n i n gm eo p t i m a lf e a t u r es u b s e ta n ds v mp a r 锄e t e r sm u s to c c l l r s i m u l t a n e o u s l y r e c e n n y ，w i t ht h ew i d ea p p l i c a t i o n so fe v o l u t i o n a r yc o m p u t 撕o ni n p a 钍锄r e c o g n i t i o n 撇，s i m u l t a i l e o u sf - c a t u r es e l e c t i o na n dp 眦吼e t e r0 p t i m i z a t i o n b e c o m ep o s s i b l e 柚dt e i l d e n c y 1 os o l v et h ea b o v ep r o b l e m ，as i m u l t a l l e o u sf e a t i l r es e l e c t i o n锄ds v m p 龇l l l l e t e r so p t i i i l i z a t i o na l g o f i m 1 l b a s e do nc o i l t i n u o u sp s oa l g o r i t h mc a l l e d c p s o s v mi sp r o p o s e di nt 1 1 i sp a p 既e x p 甜m e 鹏w i n lr e a l w o d dd a 协s e t ss h o wt l l a t t h ec p s o s v ma l g o r i t l l mc a i le m c i e i l t l y 丘n dm es u i t a b l ef e 锄j r e ：s u b s e t s 粕ds v m p a r 锄e t e r s ，w h i c hs i 鲥f i c a n t l yi m p r o v em ec l a s s i 6 c a t i o np e r f i o m a l l c eo f t h eo r i 昏n a l s a l g o r i 缸n c o m p a f e dw i mt h eg a - b a s e da l g o r i l i n 【12 1 ，c p s o s v mh 硒勰 g o o dc l a s s i f i c 撕o na b i l 时锄df e a t u r es e l e 以o na b i l i t y 嬲i t b u tn 1 i l sm o r ee f f i c i e n t l y c o n s i d 甜n gm a td i s c r e t ep s oa 1 9 0 r i t h mi sm o r eo q u a l t os 0 1 v i n gc o n l b i n a t i o n o p t i m i z a t i o np r o b l 锄s s i l c ha sf e a 饥鹏s e l e 以o nw l l i c hh 豁b e e i lp r o v e dv e 叮 i m p o r t a n t f o rs v mc l a s s i f i c a t i o n ，as i m u l t 锄e o u s 矗暑a t u r es e l e c t i o n 柚ds v m p 锄哑e t e r so p t i i i i i z a t i o na l g o 删姗 b 硒e do nd i s c r e t ep s oa l g o r i t l l i i lc a l l e d i l i 中山大学硕士学位论文基于粒子群算法的特征选择与支持向量机参数问步优化 d p s o s v mi sp r o p o s e d t h eo b j e c t i v eo fd p s o - s v mi st oi m p r 0 v et h ef e a t i l r c s e l e c t i o na b i l i t yo fc p s o s v mw i t h o u td e 黟a d i n gt h ec l a s s i 丘c a t i o np e r f o m a n c ea n d e m c i e i l c y e x p 甜m e i l t sw i t hr e a l w o d dd a t a s e t ss h o wt h a td p s o - s v m h a sa c h i e v e d t h eg o a la i l dc 觚g e r a t eam o r ec o m p a c tf e a n l r es u b s e t k e y w o r d s ： f e a m r es e l e c t i o n ，s v m ，s i i i l u l t 姗e o u so p t i m i z a t i o n ，p s o 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：爱羔少孑、 日期：2 - ，年多月日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 日期：2 p ，矿年莎月石 匙乡香、 导师签名： 日 日期：矽f 月彦日 中山大学硕上学位论文 皋于粒子群算法的特征选择与支持向量机参数同步优化 第1 章引言 传统的统计模式识别方法都是在样本数目足够多的前提下进行研究，所提出 的方法只有在样本数趋于无穷大时其性能才有理论上的保证。而实际上，样本数 目通常是有限的。近年来迅速发展起来的统计学习理论是一种专门研究小样本学 习的模式识别理论，为研究有限样本情况下的统计模式识别和更广泛的机器学习 问题建立了一个较好的理论框架，同时也发展了一种新的模式识别方法支持 向量机( s u p p o r tv e c t o rm a c h i n e ，s v l ) ，能够较好地解决小样本学习问题。s v l 已经表现出很多优于现有方法的性能。它已经成为继神经网络研究之后新的研究 热点，并将有力地推动机器学习理论和技术的发展。 随着模式识别研究的深入，研究对象越来越复杂，对象的特征维数越来越高。 大量高维数据对象的特征空间中含有许多冗余特征甚至噪声特征，这些特征一方 面可能降低分类的精度，另一方面会大大增加分类算法的时间及空间复杂度。因 此，在对高维数据进行分类时，通常需要运用特征选择算法找到具有较好可分性 的特征子空问，从而实现降维，降低机器学习的时间及空间复杂度，提高机器学 习的效果【卜引。 另外，合适的参数设置对于提高分类器模型的分类精度非常重要，错误的参 数设置往往会大幅降低分类器的性能，因此分类器参数优化也是模式识别领域重 要的研究方向之一。 s 作为一种分类算法，在实际应用中同样面临上述两个问题：一是如何 选择最佳的特征子集；二是如何设置最佳的s v m 参数。特征选择在很大程度上 影响到分类器的分类精度和学习时间等。选择适当的s v m 参数，可以改善s v m 的分类精度。 传统上，特征选择与分类器参数优化问题一般是分别研究的。在s 的特 征选择方面，已经有了一些研究工作【4 - 8 】。在s v m 参数优化方面，g 订d 算法是 一种常用的算法，但是该算法的比较费时而且效果也不能令人满意【9 ，1 0 】。 然而，特征选择和参数优化这两个问题是互相影响的：特征子集的选择将影 响到参数选择，因为对不同的特征子集而言，最优的参数是不同的；反之亦然【1 1 1 。 所以，获取最佳特征子集与获取最优参数必须同时进行。 中山人学硕十学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 随着进化优化计算技术在模式识别领域的广泛应用，编码上的灵活性使得特 征选择及参数的同步优化成为一种可能和趋势。目前已有少量工作将特征选择和 参数优化这两个问题融合起来同步研究：h u a l l gc l 掣1 2 】提出了一种应用遗传算 法 ( g e n e t i ca l g o r i t h m ，g a )同步进行特征选择及s v m 参数优化的方法， m u n i 等【1 3 1 提出了一种应用遗传规划( g e n e t i cp r o 鲈锄m i n g ，g p ) 同步进行特征 选择及分类器参数优化的方法，都取得了不错的效果。 粒子群优化算法( p a n i c l es w a mo p t i m i z a t i o n ，p s o ) 是一种新兴的优化技 术，其思想来源于人工生命及演化计算理论。p s o 算法通过粒子追随自己找到的 最优解和整个粒子群的最优解来进行优化。近年来，p s o 算法在模式识别与数据 挖掘领域得到了许多应用，并表现出了良好的性能，例如p s o 算法用于特征选 择【1 4 - 16 1 。 本文将p s o 算法运用到s 的特征选择和参数同步优化问题上，提出了一 种基于连续p s o 算法的特征选择和s v m 参数同步优化算法( c p s o s v m ) 。为 改进c p s o s v m 算法的特征选择能力，本文在其基础上又提出了一种基于离散 p s o 算法的特征选择和s v m 参数同步优化算法( d p s o s v m ) 。 本文其余部分的组织如下：第二章简述了支持向量机的基本思想和原理；第 三章介绍了特征选择的相关知识，包括特征选择的定义、特征选择的一般过程以 及特征选择方法的分类；第四章概述了p s o 算法的基本原理，在此基础上给出 了连续p s o 算法和离散p s o 算法的形式化描述，最后讨论了本文研究中p s o 算 法的参数设置等实现细节：第五章提出了基于连续p s o 算法的特征选择和s v m 参数同步优化算法，并在真实数据集上进行了实验，将实验结果与现有算法进行 了对比，以验证所提出算法的有效性；第六章提出了基于离散p s o 算法的特征 选择和s v m 参数同步优化算法，在同样的真实数据集上进行了实验，以验证该 算法达到了设计时预期的目的；最后一章对本文的研究工作进行了总结，并展望 进一步的工作。 2 中山大学硕_ 上学位论文基于粒了群算法的特征选择与支持向量机参数i 列步优化 第2 章支持向量机 基于数据的机器学习是现代智能技术中的重要方面，它研究如何从观测数据 ( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。 现有机器学习方法的重要基础是传统的统计学，其前提是有足够多的样本，当样 本数目有限时难以取得理想的效果。但在实际问题中，样本数目往往是有限的， 因此一些理论上很优秀的学习方法在实际中的表现却可能不尽人意【1 7 1 。 统计学习理论( s t a t i s t i c a ll e 锄i n gt h e o r y ，s l t ) 是由、r a p l l i k 等人提出的一 种小样本统计理论，着重研究在小样本情况下的统计规律以及学习方法性质。 s l t 为解决有限样本学习问题提供了一个统一的框架。在这一理论的基础上发展 了一种新的通用学习算法支持向量机( s u p p o r tv e c t o rm a c l l i n e ，s v m ) ，能 够较好的解决小样本学习问题。如今s l t 和s v m 已成为国内外机器学习领域新 的研究热点。 下面对支持向量机学习和分类的基本思想和原理进行简单介绍。以下内容主 要参考了张学工【1 7 】和c r i s t i a i l i n i 等【1 8 】的相关文献。 2 1 支持向量机 支持向量机是统计学习理论中最年轻的内容，也是最实用的部分，其核心内 容是在1 9 9 2 到1 9 9 5 年之间提出的，目前仍处在不断发展阶段。 概括地说，支持向量机就是首先通过用核函数定义的非线性变换将输入空间 变换到一个高维空间，然后在这个空间中求( 广义) 最优分类面。 2 1 1 广义最优分类面 s v m 是从线性可分情况下的最优分类面发展而来的，其基本思想可用图2 一l 中的两维情形来说明。图2 1 中，黑点和白点分别代表两类样本，日为分类线， q 为过黑类中离分类线最近的样本点且平行于分类线的直线，为过白类中离 分类线最近的样本点且平行于分类线的直线，它们之间的距离叫做分类间隔 中山大学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 ( m a r g i n ) 。所谓最优分类线就是要求分类线不但能将两类正确分开( 训练错误 率为o ) ，而且使得分类间隔最大。分类线方程为w x + 6 = o ，可以对它进行归一 化，使得对线性可分的样本集( x ，此) ，扣1 ，2 ，咒，x ，r 4 ，咒 + 1 ，一1 ) ，满足式2 - 1 。 此时分类间隔等于2 1 1 w 0 ，使分类间隔最大等价于使0 w i l 2 最小。满足式2 1 并且 使0 w i l 2 2 最小的分类面就是最优分类面。h 。和凰上的样本点称为支持向量。 日l 咒( w x f + 6 ) 一1 o ，f = 1 ，2 ，z ( 2 一1 ) 图2 1 线性可分情况下的最优分类线 刀= 2 | 1 w 0 利用l a g r a n g e 优化方法可以把上述最优分类问题转化为其对偶问题，即在约 束条件以q = o ，江l ，2 ，刀和q o ，江1 ，2 ，疗下，对a = ( 口i ，一，口。) 求式2 2 所示函数的最大值，其中哆是与每个样本点对应的l a 蓼a l l g e 乘子。这是一个不 等式约束下二次函数寻优问题，存在唯一解。容易证明，解中只有支持向量所对 应的那部分不为o 。求解上述问题之后得到的最优分类函数如式2 - 3 所示。式 2 3 中的求和实际上只对支持向量进行。矿是分类阈值，可以用任何一个支持向 量( 满足式2 1 中的等号) 求得，或通过两类中任何任意一对支持向量取中值求 4 中山大学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 得。 q ( a ) = q 一寺呸吁儿乃( x ，x ，) ( 2 2 ) f = l f = l ，；l 厂( x ) = s 印( w x + 6 ) = s 鳃 西乃( x ，x ，) + 6 ) ( 2 3 ) f = l 在线性不可分的情况下，可以在式2 - 1 中增加一个松弛项毒o ，如式2 4 所 示。再将目标改为求扣w 0 2 + c ( 喜缶) 最小，即折衷考虑最小错分样本和最大分类 间隔，就得到广义最优分类面。其中c 0 是一个常数，称为惩罚参数( p e l l a l t y p a r a m e t e r ) ，用于控制对错分样本的惩罚程度。广义最优分类面的对偶问题与线 性可分情况下几乎相同，唯一不同之处在于约束条件啦o ，b 1 ，2 ，刀修改为 o q c ，f _ l ，2 ，刀。 2 1 2 核函数 只( w x f + 6 ) 一l + 点0 ，f = 1 ，2 ，拧 ( 2 4 ) 对于非线性问题，s v m 先通过非线性变换将原特征空间中的非线性问题转 化为某个高维空间中的线性问题，然后在高维空间中求最优分类面。一般情况下， 这种变换可能比较复杂，不容易实现。但是，如前所述，在将求最优分类面的问 题转换成其对偶问题之后，可以发现不论是寻优函数( 式2 2 ) 还是分类函数( 式 2 3 ) ，都只涉及到训练样本之间的内积运算。因此，并不需要计算原空间中的样 本点在高维空间中的像，也就是说不需要知道变换的形式，而只需要一个原空间 中的函数，能够根据原空间的样本点计算出它们在高维空间中的像的内积即可。 这种函数称为核函数。根据泛函的有关理论，只要一种核函数k ( x ，x ，) 满足 m e r c e r 条件，它就对应某变换空间中的内积。 所以，采用适当的核函数k ( x ，x ，) 就可以实现某一非线性变换后的线性分 类，而不增加计算复杂度。在采用核函数的情况下，目标函数如式2 5 所示，而 相应的分类函数如式2 6 所示。这就是支持向量机。 5 中山大学硕+ 学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 q ( a ) = 口，一寺q 口，咒乃k ( x ，x ，) ( 2 5 ) f = i ，f = l ，= i 厂( x ) = s 印匹口 k ( x ，x ) + 6 ) ( 2 - 6 ) s 订中使用不同的核函数将形成不同的算法，目前研究最多的核函数主要 有三类。一是多项式核函数，二是径向基函数( r b f ) ，三是s i 舯o i d 函数，分 别如式2 8 、式2 9 和式2 1 0 所示。本文的研究中采用的是r b f 核函数。 k ( x ，y ) = ( x y + r ) 9 ( 2 8 ) k ( x ，y ) = e x p ( 7 i l x y i l 2 ) ，y o ( 2 9 ) 2 2 本章小结 k ( x ，y ) = t 锄h y ( x y ) + c ) ( 2 1 0 ) 本章简述了支持向量机的基本思想和原理。概括地说，支持向量机就是首先 通过核函数定义的非线性变换将输入空间变换到一个高维空间，然后在高维空间 中求( 广义) 最优分类面。 6 中山大学硕十学位论文基于粒了群算法的特征选择与支持向量机参数同步优化 第3 章特征选择 特征选择是模式识别与数据挖掘领域的重要数据处理方法之一。随着模式识 别与数据挖掘研究的深入，研究对象越来越复杂，对象的特征维数越来越高。大 量高维数据对象的特征空间中含有许多冗余特征甚至噪声特征，这些特征一方面 可能降低分类的精度，另一方面会大大增加学习及预测的空问及时问复杂度。因 此，在面对高维数据进行分析时，通常需要运用特征选择方法找到具有较好可分 性的特征子空间，从而实现降维，降低机器学习的时间及空间复杂度【i 捌。 3 1 特征选择的定义 有很多学者从不同的角度对特征选择进行了定义。j o l h l 等【1 】从提高预测精度 角度定义特征选择为选择特征子集来增加分类精度，或者在不降低分类器精度的 条件下降低特征空间维数的过程：k o l l e r 等【1 9 】从类分布的角度定义特征选择，即 在保证结果类分布尽可能与原始数据类分布相似的条件下，选择尽可能小的特征 子集；d a s h 等【2 0 】认为选择尽量小规模的特征子集，同时不会显著降低分类精度 和不会显著改变类分布。 特征选择可以包括特征提取和特征筛选两方面：特征提取广义上指的是一种 变换，将处于高维空间的样本通过映射或变换的方式转换到低维空间，以达到降 维的目的；特征筛选指从一组特征中去除冗余或不相关的特征来降维。二者常常 联合使用，例如通过变换将高维特征空间映射到低维特征空间，然后再去除冗余 的和不相关的特征来进一步降低维数。 3 2 特征选择的一般过程 特征选择的一般过程如图3 1 所示。它包括以下四个方面【2 0 】：( 1 ) 搜索策略； ( 2 ) 特征评价标准；( 3 ) 终止条件；( 4 ) 结果评价。 搜索策略是指特征子集的形成方式，即如何产生特征子集。特征评价标准是 指建立一种评价标准来区分哪些特征组合有助于分类，哪些特征组合存在冗余 性、部分或者完全无关。终止条件主要用于控制特征选择过程的完成并且停止。 7 中山人学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 结果评价是指对特征选择的结果进行评价，最直观的评价方法是应用一种数据挖 掘算法，分别观察原始数据集和进行特征选择后的数据集在该算法下运行结果的 变化。 图3 1 特征选择的一般过程 3 3 特征选择方法的分类 3 3 1 根据搜索策略分类 按照搜索策略的不同，特征选择方法可以分为如下三类：穷举法、启发法和 随机法【2 0 】。 穷举法指遍历特征空间中所有的特征组合，选取最优特征组合子集的方法。 假设特征数目为时，计算复杂度为d ( 2 ) 。常用的方法有回溯法及其变体等， 其优点在于一定能得到最优子集，但实际情况下由于特征空间过于庞大，时间代 价和计算复杂度太大，因此实用性并不强。 启发式方法是一种近似算法，具有较强的主观倾向。实际应用中通过采用 期望的人工机器调度规则，重复迭代产生递增的特征子集。特征个数为时， 复杂度一般小于或等于d ( 2 ) 。这种方法实现过程比较简单且快速，在实际中应 r 中山大学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 用的较为广泛，如前向( 后向) 选择、决策树方法、r e l i e f 方法等，不过一般能够 获得的是近似最优解。 随机方法是一种相对较新的方法，细分为完全随机方法和概率随机方法两 种。完全随机方法是指“纯”随机产生特征子集，概率随机方法是指特征子集的 产生依照给定的概率进行。虽然计算复杂度仍为d ( 2 ) ，但通过设置最大迭代次 数可以限制复杂度小于d ( 2 1 ) 。常用的方法有遗传算法、模拟退火和集束搜索 ( b e 锄s e a r c h ) 等【2 l 】。本文研究中采用的粒子群算法也属于随机方法，它已经 被一些研究应用到特征选择上【1 舢1 6 1 ，并显示出良好的性能。 3 3 2 根据评价函数与分类器的关系分类 前面已经提到，特征选择需要建立一种评价标准来区分哪些特征组合有助于 分类，哪些特征组合存在冗余性、部分或者完全无关。不同的评价函数可能会给 出不同的结果。根据评价函数与分类算法的关系，特征选择方法分成过滤式 ( f i l t e rm o d e l ) 和封装式( w r a l ) p e rm o d e l ) 两种。过滤式特征选择的评价函数 与分类算法无关，而封装式特征选择一般采用分类算法的错误率作为评价函数。 过滤式特征选择算法的流程如图3 2 所示。过滤式特征选择算法的评价函数 独立于分类算法，直接由数据集求得。通常是选择和目标函数相关度大的特征或 者特征子集，一般认为相关度较大的特征或者特征子集会得到后续学习算法较高 的准确率。过滤式特征选择的评价函数很多，有距离度量、信息熵、相关性度量 和一致性度量等等。 封装式特征选择算法最早由j o l l i l 等在1 9 9 4 年提出【1 1 ，算法流程如图3 3 所 示。封装式特征选择算法与过滤式特征选择算法的最大不同之处在于，其特征子 集的形成过程与学习算法密切相关。不同的学习算法偏好不同的特征子集，既然 特征选择后的特征子集最终将用于后续的学习算法，那么该学习算法的性能就是 最好的评估标准。因此在封装式特征选择中将学习算法的性能作为特征选择的评 估标准，例如分类错误率。封装式特征选择算法中用以评估特征的学习算法是没 有限制的。 9 中山大学硕 ：学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 算法：过滤式特征选择算法 输入：维训练数据集d ( 互，e ，目) ，初始搜索子集瓯，停止条件艿。 输出：最优特征子集。 步骤：( 1 ) 初始化特征子集，= 瓯； ( 2 ) 用独立的评价标准m 来判别氐的好坏：= e ，( 瓯，d ，m ) ； ( 3 ) 如果停止条件万没有得到满足，进行如下计算： 1 搜索候选特征子集s = 舻疗伽纪( d ) ； 2 用独立的评价标准m 来判别s 的好坏：厂= 咖，( s ，d ，m ) ； 3 如果7 ，那么k = y ，= s ； ( 4 ) 输出最优特征子集，算法结束。 图3 2 过滤式特征选择算法流程 图3 3 封装式特征选择算法流程 1 0 中山大学硕上学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 过滤式特征选择算法通常运行效率较高因而适用于大规模数据集。与之相 比，封装式特征选择算法的准确率较高，但是算法效率较低。为了得到更高的准 确率，并考虑到s v m 通常用于小样本学习，本文的研究采用封装式的特征选择 算法。 3 4 本章小结 本章介绍了特征选择的理论，包括特征选择的定义、特征选择的一般过程以 及特征选择方法的分类。按照搜索策略的不同，特征选择方法可以分为穷举法、 启发法和随机法三类；根据评价函数与分类器的关系，特征选择方法分成过滤式 和封装式两种。本文研究中采用的粒子群算法是随机法的一种，采用的特征选择 方法是封装式的。 中山大学硕上学位论文基于粒子群算法的特征选择与支持向量机参数列步优化 第4 章粒子群算法 粒子群优化算法( p a r t i c l es w 姗o p t i m i z a t i o n ，p s o ) 是一种基于种群的随 机优化技术，由e b e f h 积和k e l l i l e d y 于1 9 9 5 年提出【2 2 ，2 3 1 。p s o 算法模拟昆虫、 兽群、鸟群和鱼群等的群集行为，这些群体按照一种合作的方式寻找食物，群体 中的每个成员通过学习它自身的经验和其它成员的经验来不断改变其搜索模式。 4 1 p s o 算法基本原理 自然界中一些生物的行为特征呈现群体特征，可以用简单的几条规则将这种 群体行为( s w a n n b e h a v i o r ) 在计算机中建模，实际上就是在计算机中用简单的 几条规则来建立个体的运动模型，但这个群体的行为可能很复杂。例如，r e v l l o l d s 使用了下列三个规则作为简单的行为规则： ( 1 ) 向背离最近的同伴的方向运动； ( 2 ) 向目的运动； ( 3 ) 向群体的中心运动。 这即是著名的b o i d ( b i r d o i d ) 模型。在这个群体中每个个体的运动都遵循 这三条规则，通过这个模型来模拟整个群体的运动。p s o 算法的基本概念也是如 此，每个粒子的运动可以用几条规则来描述，因此p s o 算法简单，容易实现， 越来越多地引起人们的注意。 设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物， 所有的鸟都不知道食物在哪里，但是它们知道当前的位置距离食物还有多远。那 么找到食物的最优策略是什么呢? 最简单有效的就是搜寻目前距离食物最近的 鸟的周围区域。p s o 算法就从这种生物种群行为特性中得到启发并用于求解优化 问题。 在p s o 算法中，优化问题的每个潜在解都可以想象成d 维搜索空间里的一个 点，称之为“粒子”。粒子当前位置的好坏由目标函数进行评估，目标函数根据粒 子的位置计算出相应的适应值( f i t n e s sv a l u e ) 。每个粒子都知道自己到目前为止 所发现的最好位置，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子 中山人学硕士学位论文基于粒子群算法的特征选择与支持向量机参数i f d 步优化 还知道到目前为止整个群体中所有粒子发现的最好位置，这个可以看作是粒子的 同伴的飞行经验。粒子在搜索空问中以一定的速度飞行，这个速度根据它本身的 飞行经验和同伴的飞行经验来动态调整，继而被用来计算粒子的新位置。优化搜 索正是在由一群随机初始化形成的粒子所组成的种群中，以迭代的方式进行的， 直到满足一定的终止条件，例如达到指定的迭代次数。p s o 算法的流程如图4 1 所示。 图4 1p s o 算法的流程图 4 2 连续p s o 算法 以下给出连续p s o 算法的形式化描述。 在连续空间坐标系中，设粒子种群规模为，每个粒子在d 维空间中的坐标 位置向量表示为z = ( 玉，薯：，) ，速度向量表示为巧= ( v p h ：，) ，粒子个 1 3 中山大学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 体历史最优位置( 即该粒子经历过的最优位置) 记为虿= ( 只。，b ：，砌) ，群体 历史最优位置( 即该粒子群中任意个体经历过的最优位置) 记为 弓= ( 砍t ，岛z ，翰) 。 不失一般性，以最小化问题为例，设目标函数为厂，个体历史最优位置的迭 代公式如式4 1 所示，其中f 表示迭代次数。群体历史最优位置通过计算个体历 史最优位置中最好的位置得到。 _ f “：j i ；，如果厂( 叉：州) ( 万) ( 4 1 ) i 万， 其它 粒子的速度更新公式如式4 2 所示，其中国、c l 和c 2 是常数，具体含义将在 下文解释；m 以d 表示均匀分布在【o ，l 】区间上的随机数。粒子的位置更新公式如 式4 3 所示。粒子移动的原理如图4 2 所示。 矿；“= 缈木_ f + c l 木凇咒d 事( 万一牙；) + q 事朋以d ( 砖一z ) ( 4 2 ) 矿f= 缈木y ，+ c l 木凇咒d 事( 只一x f ) + g 事朋以d ( 尸窖一x f ) ( 4 2 ) 叉；+ l ：叉；+ 彰引 ( 4 3 ) 从社会学的角度看速度迭代公式，其中第一部分为粒子先前的速度的影响， 表示粒子对自身当前运动状态的信任，依据自身的速度进行惯性运动，因此参数 缈称为惯性权重( i n e n i aw 萌咖) ；第二部分取决于粒子当前位置与自身历史最 优位置之间的距离，为“认知( c o 印i t i o n ) ”部分，表示粒子本身的思考，即粒 子的运动来源于自己经验的部分，因此参数c i 称为认知学习因子( 也可称为认知 加速因子) ；第三部分取决于粒子当前位置与群体历史最优位置的距离，为“社 会( s o c i a l ) ”部分，表示粒子间的信息共享和相互合作，即粒子的运动来源于群 体中其它粒子经验的部分，它通过认知模拟了较好同伴的运动，因此参数c ，称为 社会学习因子( 也可称为社会加速因子) 。 1 4 中山人学硕士学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 、| | 4 3 离散p s o 算法 一f + 1 x i f xi 图4 2 粒子移动原理图 p s o 算法最初是用来对连续函数进行优化的，而实际中许多问题是组合优化 向题，因此k e 衄e d y 和e b e d l a n 在连续p s o 算法的基础上发展了离散p s o 算法 来解决这一类问题【2 4 】。与连续p s o 算法不同，在离散p s o 算法中，粒子是长度 为d 的二进制向量，每一维的取值为o 或l 。因此，连续p s o 算法中的粒子位置 更新公式不再适用。为解决这一问题，用一个速度转换函数将粒子速度转换到区 间【o 1 】上，转换后速度的某一维的值表示粒子的对应维取值为1 的概率。s i 肿o i d 函数是常用的转换函数，如式4 4 所示。新的粒子位置更新公式如式4 5 所示。 除此以外，个体历史最优位置和群体历史最优位置的计算方法，以及粒子速度的 更新公式都与连续p s o 算法相同。 s 辔( 功2 寿 4 _ 4 ) l + p 6 弘怯凳翮以啦吖令 5 ， 在此基础上，s h e l lq i 等【硎提出了一个改进的离散p s o 版本。在该版本中， 粒子位置的更新公式如式伯所示。式中口是一个大于o 小于l 的随机值，称为 1 5 中山大学硕十学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 静态概率( s t a t i cp r o b a b i l 埘) 。它在平衡局部搜索和全局搜索中扮演了重要角色。 口值越大，则粒子群跳出局部最优点的能力越强；而口值越小，则粒子群收敛越 快。 i 带1 = 弓，矿( o 哼1 口) 譬1 = 西，矿缸 o 和 误差项的惩罚参数( p 肌a l t yp a r 锄e t e r ) c 0 。粒子中应当包含这两个参数。此 外，还要同步进行特征选择，所以粒子中还应当包含特征选择信息。 粒子有两个分量用于编码上述两个参数。假定用粒子的某一分量五来编码参 中山大学硕上学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 数p ，薯的取值范围是 一k 。，k 。】，p 的取值范围是【p 面。，】，那么薯所代 表的参数的真实值由式5 2 确定。 p 2 + 等c 一， 6 乏， 为实现对特征选择信息的编码，本章采取了类似l i uy u 等的方法，具体 如下：假设用粒子的某一分量薯来编码特征f 的选择信息，五的取值范围是 卜k 。，k 。】，那么当薯 o 时表明特征f 被选中，而当玉o 时表明特征f 不被 选中。 综上，粒子的结构如图5 - 1 所示。玉，而，用于编码特征选择信息，+ 。 编码参数c ，吒川编码参数厂。咋表示特征数目，不同的分类问题有不同的特 征数目，因此粒子的维数也不同。 特征选择信息参数c参数7 五屯x q 。 f + l吒，+ 2 图5 1 粒子结构示意图 5 1 2 适应度函数的设计 c p s o s 订算法的目标是同步优化特征子集和s v m 参数以提高s v m 的分 类精度，同时尽可能减少所选择的特征数目。分类精度和所选择的特征数目是设 计适应度函数的两个标准。一个粒子能够使分类器产生的分类精度越高，同时选 出的特征数目越少，它的适应度就应该越高。基于上述考虑，本章设计的适应度 函数如式5 3 所示。 伽鲫= 删一口例阳钞+ w ，知砌坨一以甜m - 1 ( 5 - 3 ) 式5 3 中，s 瑚一口c 伽m 秒表示s 订的分类精度，而伽舭一万“m 表示所选 择的特征数目。分类精度和所选择的特征数目这两个因素都在适应度函数中得到 了体现，并且分类精度越高，所选择的特征数目越少，适应度函数的值越大。比 1 9 中山大学硕士学位论文 基于粒子群算法的特征选择与支持向量机参数同步优化 和w ，分别是上述两个因素的权重，满足心+ w ，= 1 。用户可以根据实际需要来调 节这两个权重。例如，如果用户认为分类精度是最重要的，而不考虑所选择的特 征数目，那么可以设置w 口= l 。一般来说，比可以设置的范围是o 7 5 到1 o 。 5 1 3c p s o s v m 算法 图5 2 给出了所提出的c p s o s v m 算法，图5 3 是该算法的流程图。 中山人学硕士学位论文摹于粒子群算法的特征选择与支持向量机参数同步优化 输入：数据集d ，特征数目咋，参数c 的最小值c m i 。和最大值l ，参数7 的最小值 。和最大值，适应度函数的权重参数心和1 吁，粒子数目怖，最火迭代次数。 输出：优化的特征子集邢，优化的参数c 和y 。 步骤：( 1 ) 对数据集d 进行最小最人规范化处理，将全部特征值都变换剑【o ，1 】区间上， 并将数据集d 划分为训练集d i 和测试集砬。 ( 2 ) 由特征数目确定粒子维数d ，根据维数d 和粒子数目拧p 初始化粒子群p 。 ( 3 ) 计算出粒子群p 中每个粒子的适应度：对于粒子p ，根据特征选择信息的编 码方案得到选中的特征子集耶口，根据式5 - 2 以及c m i 。、g 。和i 。、。，得到s 垤 的参数q 和以。根据特征子集晖对训练集q 和测试集砬进行特征选择，得到约简 的训练集d l p 和测试集d 2 p 。以q p 为训练集，q 和砟为参数构建s v m 分类模型m 。 在测试集d 2 p 上测试分类模型m ，得到分类精度s 啪一口“朋钞，再根据式5 3 和权 重参数w 4 和w ，计算出粒子p 的适应度。 ( 4 ) 根据粒子适应度，更新每个粒子的个体历史最优位置，以及整个粒子群的群 体历史最优位置。 ( 5 ) 根据连续p s o 算法的速度和位置更新公式，更新粒子的速度和位置。 ( 6 ) 判断是否达到最大迭代次数：如果已经达到，则根据群体历史最优位置输 出优化的特征子集殿以及优化的参数c 和7 ；如果还没达到，则返同步骤( 3 ) 继续迭 代。 图5 2c p s o s 算法 2 l 中山大学硕j ：学位论文基于粒子群算法的特征选择与支持向量机参数同步优化 图5 3c p s o s v m 算法流程图 中山大学硕士学位论文摹于粒子群算法的特征选择与支持向量机参数同步优化 5 2 实验研究 5 2 1 实验数据和实验环境 为了评估c p s o s v m 算法的性能，本章从u c l 数据库中选取了若干真实数 据集进行实验研究。这些数据集经常被用来比较各种分类算法的性能。表5 一l 说 明了实验中用到的数据集。这些数据集中既有二类数据集，也有多类数据集；既 含有数字属性( n u m 甜cf e a t l l r e ) ，也含有标称属性( n o m i n a lf e a t l l r e ) 。 表5 1