欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:153 2730 2358
邮箱:910330594@QQ.COM

Q Q:
910330594
网址:http://www.17winner.com
工作时间:
9:00-24:00  

硕士论文
当前位置:首页 > 硕士论文
基于特征子集区分度与支持向量机的特征选择算法
来源:一起赢论文网     日期:2015-04-28     浏览数:1177     【 字体:

 摘   要   考虑特征之间的相关性对于其类间区分能力的影响, 提出了一种新的特征子集区分度衡量准则— — — D F S( D i s c e r n i b i l i t y   o f  F e a t u r e  S u b s e t s ) 准则 . 该准则考虑特征之间的相关性, 通过计算特征子集中全部特征对于分类的联合贡献来判断特征子集的类间辨别能力大小, 不再只考虑单个特征对于分类的贡献 . 结合顺序前向、 顺序后向、顺序前向浮动和顺序后向浮动4种特征搜索策略, 以支持向量机( S u p p o r t  V e c t o r  M a c h i n e s , S VM ) 为分类工具, 引导特征选择过程, 得到4种基于 D F S与 S VM 的特征选择算法. 其中在顺序前/后向浮动搜索策略中, 首先根据D F S 准则加入/去掉特征到特征子集中, 然后在浮动阶段根据所得临时 S VM 分类器的分类性能决定刚加入/去掉特征的去留 . U C I 机器学习数据库数据集的对比实验测试表明, 提出的 D F S 准则是一种很好的特征子集类间区分能力度量准则; 基于 D F S 与 S VM 的特征选择算法实现了有效的特征选择; 与其他同类算法相比, 基于 D F S 准则与S VM 的特征选择算法具有非常好的泛化性能, 但其所选特征子集的规模不一定是最好的 .

关键词   特征选择; 支持向量机; 相关性; 特征子集区分度; 特征区分度
   1  引   言
    特征选择是模式识别、 数据挖掘等领域的重要研究内容, 它通过选择原始特征集合中的重要特征构成特征子集, 达到降低数据维数, 同时保持或提高系统分类性能的目的 . 与特征提取不同, 特征选择保留的是原始物理特征, 因此, 可以真正地降低存储需要、 测量需求、 计算开销等; 而特征提取所保留的特征是原始特征的线性组合, 降维后的特征与原始每一个特征都相关, 因此特征提取保留下的特征没有任何物理意义, 这对癌症等疾病诊断研究没有任何意义 . 另外, 特征提取也不能降低存储需要、 测量需求、 计算开销等, 不具有特征选择的这些优点 [1 ]. 特征选择对于构建一个简洁、 高效的分类系统有重要作用 . 它不仅可以揭示系统所隐藏的潜在模式和规律, 并使分类结果的可视化成为可能 [1 ] .因此, 特征选择, 特别是基于最具有泛化能力和最小错分率的学习机— — —支持向量机(S u p p o r t  V e c t o r  M a c h i n e s ,S VM ) 的特征选择研究备受关注[ 2 - 9 ] .
    现有特征选择研究主要着眼于选择最优特征子集所需要的两个主要步骤 [1 0 ] : 特征子集搜索策略和特征子集性能评价准则. 经典的特征子集搜索策 略 包 括: 顺 序 前 向 搜 索 ( S e q u e n t i a l  F o r w a r dS e a r c h , S F S )[ 1 1 ] 、 顺序后向搜索(S e q u e n t i a l  B a c k w a r dS e a r c h , S B S )[ 1 2 ] 、 顺 序 前 向 浮 动 搜 索 (S e q u e n t i a lF o r w a r d  F l o a t i n g   S e a r c h ,S F F S )[ 1 3 ] 、 顺序后向浮动搜索( S e q u e n t i a l  B a c k w a r d  F l o a t i n g S e a r c h , S B F S )[ 1 3 ]4种. 
特征子集性能评价准则有独立于分类器的评价方法、 以分类器分类准确率评价的方法, 以及将两者相结合的评价方法.特征选择方法依据其与分类器的关系分为F i l t e r方法、 W r a p p e r方法和 E m b e d d e d 方法 3 类 [ 1 4 - 1 6 ] .F i l t e r[ 1 4 ] 方法根据每一个特征对分类贡献的大小,定义其重要度, 选择重要的特征构成特征子集. 该方法独立于学习过程, 时间效率较高, 但是该方法需要一个阈值作为特征选择的停止准则. F i l t e r方法选择的特征子集的分类性能不仅与特征重要性计算方法, 即特征排序准则有关; 而且与特征搜索策略, 以及特征选择过程的停止准则密切相关.W r a p p e r[ 1 5 ] 方法依赖于学习过程, 将训练样本分成训练子集和测试子集两部分 . W r a p p e r 方法中的学习算法完全是一个“ 黑匣子” , 仅以每一组特征子集训练所得分类器的分类准确率作为该组特征分类性 能 的 度 量 . 为 选 择出性能最好的特征子集,W r a p p e r 算法需要的计算量巨大; 而且该方法所选择的特征子集依赖于具体学习机; 容易产生“ 过适应” 问题, 推广性能较差 . 另外, 确定搜索策略以搜索所有可能的特征组合, 评价学习机的性能以引导或停止搜索, 以及选择具体的学习算法是 W r a p p e r 方法的关键.E m b e d d e d[ 1 6 ] 方法将特征选择集成在学习机训练过程中, 通过优化一个目标函数在训练分类器的过程中实现特征选择. 
    该方法不用将训练数据集分成训练集和测试集两部分, 避免了为评估每一个特征子集对学习机所进行的从头开始的训练, 可以快速地得到最佳特征子集, 是一种高效的特征选择方法, 但是构造一个合适的函数优化模型是该方法的难点.F i l t e r算法和 W r a p p e r算法相结合的混合特征选择方法集成了 F i l t e r 方法的高效与 W r a p p e r 方法的高准确率, 可得到更优的特征子集 [1 7 - 1 9 ] , 是目前特征选择方法研究的一个新趋势. 然而, 现有特征选择研究多集中于考虑单个特征对于分类的贡献, 以此来评价特征的重要性, 从而依次选择重要的特征构成特征子集. 这样进行特征选择忽略了特征之间的相关性对于分类的影响, 或者对特征之间的相关性考虑不足, 特征之间的联合作用对于分类的贡献经常被忽略.H a l l 的C F S ( C o r r e l a t i o n  b a s e d  F e a t u r e  S e l e c t o r ,C F S )[ 2 0 ] 特征选择方法基于特征之间的相关性考虑, 通过计算特征之间的相关性, 以及特征与类标的相关性, 来实现特征选择, 从而使得被选特征子集的特征之间尽可能不相关, 而与类标高度相关. 但是HA L L 的 C F S 计算特征相关性的方法只适用于离散型数据, 非离散的数据需要进行离散化预处理; 另外, 特征之间的相关性只注重了特征两两之间的相关性, 对于多个特征对于分类的联合贡献考虑不足.本文 基 于 特 征 之 间 相 关 性 的 考 虑, 提 出 D F S( D i s c e r n i b i l i t y o f  F e a t u r e  S u b s e t s , D F S ) 特征子集区分度衡量准则, 通过计算特征子集中特征的联合F - s c o r e 值 来 判 断 特 征 子 集 的 类 别 间 区 分 能 力大小, 以此作为特征子集对分类贡献大小的度量, 并结合 S F S 、 S B S 、 S F F S 和 S F B S  4 种特征搜索策略,以 S VM 为分类工具引导特征选择过程, 实现特征选择 . U C I 机器学习数据库数据集的实验测试表明, 本文提出的 D F S 准则是一种有效的特征子集类间区分能力度量准则; 基于 D F S 与 S VM 的特征算法实现了有效的特征选择, 具有很好的泛化性能; 但是 所 选 择 的 特 征 子 集 的 规 模 不 一 定 是 最好的 .
    2  特征子集评价准则
    现有特征选择研究中特征重要性的评价多是计算单个特征的类间区分能力, 选择对分类贡献大的特征构成特征子集, 而忽略了特征之间的相关性对于特征类间区分能力大小的影响, 或者对特征之间的相关性考虑不足. H a l l[ 2 0 ] 通过计算特征之间的相关性、 特征与类标的相关性提出 C F S特征子集评价准则, C F S计算整个特征子集的类间区分能力实现特征选择, 使得被选特征子集中的特征之间尽可能不相关, 而与类标高度相关. 但 C F S[ 2 0 ] 只适用于离散型数据; 另外, C F S 更注重了特征两两之间的相关性, 对于多个特征对于分类的联合贡献考虑不足.为此, 本文首先将 P e a r s o n 相关系数引入 C F S , 以计算特征两两之间的相关性, 使得 C F S可应用于实值特征; 然后将P e a r s o n相关系数所表达的正、 负相关性进行统一, 不区分正、 负相关, 只考虑相关, 从而得到 C F S P a b s ( C o r r e l a t i o n  b a s e d  F e a t u r e  S e l e c t o rb a s e d  o n  t h e  a b s o l u t e  o f  P e a r s o n ’ s  c o r r e l a t i o nc o e f f i c i e n t , C F S P a b s ) 特征子集评价准则 . 
    其次, 本文在文献[1 9 ] 对单个特征的类间区分能力, 即对分类的贡献的研究基础上, 考虑多个特征对于分类的联合贡献, 提出 D F S 特征子集评价准则, 并结合4种特征搜索策略 S F S 、 S B S 、 S F F S和 S F B S , 提出4种基于 D F S特征子集评价准则的特征选择算法.
    2 . 1 C F S特征子集评价准则C F S 特征子集评价准则[ 2 0 ] 的定义如式(1 ) 所示:M s =k rc fk + k ( k -1 ) r槡 f f(1 )式(1 ) 中的 M s 度量了包含 k 个特征的特征子集 S的类别辨识能力,rc f表示特征 f (f ∈ S ) 与类别 c 的相关系数的均值,rf f 是特征之间的相关系数均值 .式(1 ) 的分子表达了特征子集 S 的类预测能力; 分母表示了特征子集 S 中特征的冗余程度 . 因此分子越大表示特征子集 S 的类预测能力越强, 分母越小表示该特征子集的冗余性越小 . 特征选择, 就是选择一组特征构成特征子集, 该子集与类别高度相关, 但是子集中的特征之间高度不相关 [1 2 ] .由此可见 M s的值越大, 当前特征子集 S 对于分类的贡献越大,是优良的特征子集 . 我们使用 P e a r s o n 相关系数计算相应特征之间的相关性, 以便 C F S 准则可应用于任意类型的特征值 . P e a r s o n相关系数的计算公式如式(2 ) 所示 .r =∑ X Y -∑ X ∑YN∑ X2 - ∑ ( )X2烄烆烌烎N∑Y2 - ∑ ( )Y2烄烆烌烎槡 N(2 )其中, X ,Y 表示待求相关系数的两个向量, 可以是两列特征向量, 或者一列特征向量与一列类标向量,N 是样本个数.
    2 . 2 C F S P a b s特征子集评价准则由于P e a r s o n相关系数可能为正值, 也可能为负值, 也即待判断相关程度的两向量可能正相关, 也可能负相关. 而无论正相关还是负相关, 相关系数的绝对值越大, 也即相关系数越接近+1或-1 , 则相关性越强; 相关系数越接近于 0 , 则相关度越弱 . 因此, 我们将式(1 ) 所示 C F S准则中计算相关系数的P e a r s o n 相关系数进行改进, 取其绝对值, 得到特征子集评价准则 C F S P a b s . C F S P a b s准则中的相关系数计算公式如式(3) 所示.
    2 . 3 D F S特征子集评价准则设 m 维实空间 R m 中的两类分类问题, 训练集样本的规模为 n , 正类和负类的样本数分别为 n + 和n - . 即训练集是{ ( x k , y k ) | x k ∈ R m , m 0 , y k ∈ { 1 ,-1 } , k =1 , …, n } , ‖ { y k | y k =+1 , k =1 , …, n } ‖=n + , ‖ { y k | y k =-1 , k =1 , …, n } ‖= n - . 则含有 i ( i =1 , 2 , …, m ) 个特征的特征子集的区分度 D F S 的定义如式(4) 所示.D F S i =∑ij =1(x- ( + )j- x-j )2 + (x- ( - )j- x-j ) ( )21n + -1 ∑n +k =1∑ij =1(x( + )k , j - x- ( + )j)( )2+1n - -1 ∑n -k =1∑ij =1(x( - )k , j - x- ( - )j)( )2(4 )其中,x-j , x- ( + )j,x- ( - )j分别为第 j 个特征在整个数据集上的均值, 在正类数据集上的均值和在负类数据集上的均值;x( + )k , j为正类第 k 个样本点的第 j 个特征的值;x( - )k , j为第 k 个负类样本的第 j 个特征的值 .式(4 ) 可以简记为式( 5 ) .D F S i =‖ x-( + ) -x- ‖ 2 +‖x-( - ) -x- ‖ 21n + -1 ∑n +k =1‖ x( + )k- x-( + )‖2 + 1n - -1 ∑n -k =1‖ x( - )k- x-( - )‖2(5 )其中, ‖X-Y‖ 表示向 量X , Y 之 间 的 距 离; x- ,x-( + ) ,x-( - ) 分别为包含 i 个特征的特征子集在整个数据集上的均值向量, 在正类数据集上的均值向量和在负类数据集上的均值向量;x( + )k为正类第 k 个样本点对应于当前 i 个特征的特征值向量; x( - )k为第 k 个负类样本对应当前 i 个特征的特征值向量.
    分析式(4 ) 和( 5 ) 可知, 分子表示正类、 负类对应当前含有 i 个特征的特征子集的均值向量与整个样本集对应当前 i 个特征的特征子集的均值向量的距离平方之和; 分母表示正类、 负类对应当前 i 个特征的特征子集的方差之和; 分子值越大表示对应当前i 个特征的特征子集的类间越疏; 分母值越小表示对应当前 i 个特征的特征子集的类内越聚. 因此D F S i 值越大, 表明包含当前 i 个特征的特征子集的类间区分能力越强, 也即类别辨识能力越强.对于 l ( l 2 ) 类分类问题, 设训练样本集规模为n , 样本空间维数为 m . 即训练样本集为{ ( x k , y k ) |x k ∈ R m ( m 维实空间) , m 0 , y k ∈ { 1 , …, l } , l 2 ,k = 1 , …, n } . 其中, 第 j 类的样本数为 n j , 即 ‖ y k | y k =j , k = 1 , …, n ‖= n j , j =1 , …, l , 则含有 i ( i =1 , …,m ) 个特征的特征子集的区分度 D F S i 定义为式( 6 ) .D F S i =∑lj =1 ‖x-( j ) -x- ‖ 2∑jj =11n j -1 ∑njk =1 ‖x( j )k - x-( j )‖2(6 )其中 x- ,x-( j ) 分别为包含当前 i 个特征的特征子集在整个数据集上的均值向量, 在第 j 类数据集上的均值向量;x( j )k为第 j 类中第 k 个样本对应当前 i 个特征的特征值向量. 式(6 ) 的分子表示 l 个类别中各类别对应包含当前 i 个特征的特征子集的样本中心向量与整个样本集对应当前 i 个特征的中心向量的距离平方和, 其值越大, 类间越疏 . 式( 6 ) 的分母表示各个类别对应包含当前 i 个特征的特征子集的类内方差 . 方差越小, 类内越聚 . 因此, 式( 6 ) 定义的 D F Si表示了当前 i 个特征的特征子集的类间距离和与类内方差之比, 其值越大表明包含当前 i 个特征的特征子集的类别辨识力越强 .当 i =1 时, D F Si 蜕化为单个特征的类间区分能力度量准则— — —改进的 F - s c o r e 准则 [1 9 ] , 如式(7 )所示.F i =∑lj =1(x- ( j )i - x-i )2∑lj =11n j -1 ∑njk =1(x( j )k , i - x- ( j )i)2(7 )式(7 ) 中 x-i , x- ( j )i分别为第 i 个特征在整个数据集上的均值, 在第 j 类数据集上的均值; x( j )k , i 为第 j 类第k 个样本点的第 i 个特征的值 . 式( 7 ) 分子表示 l 个类中第 i 个特征的各类中心到整个样本集中心的距离平方和, 其值越大, 类间越疏. 式(7 ) 的分母表示各个类第 i 个特征的类内方差. 方差越小, 类内越聚.因此,F i 近似表示了第 i 个特征的类间距离与类内方差之比, 其值越大表明第 i 个特征的辨识力越强.
    3  基于 D F S 与 S VM的特征选择算法
    将本文提出的特征子集区分度衡量准则 D F S结合 S F S 、 S B S 、 S F F S 和 S F B S 特征搜索策略, 以S VM 为分类工具, 提出4种不同的特征选择算法.
    算法1. 基于 D F S与 S VM 的顺序前向混合特征选择算法.该算法采用S F S搜索策略, 以D F S度量相应特征子集的类间区分能力, 以 S VM 分类模型的分类正确率作为最终依据选择相应特征子集. 特征选择从空集开始, 第一次加入类间区分能力最强的一个特征, 然后依次迭代加入与已选择特征组合构成类间区分能力最大的特征子集对应的那个特征. 该过程一直进行, 直到所有特征都被加入 . 最后选择训练集分类正确率最高时对应的特征子集为被选择特征子集. 算法的伪代码描述如下.输入: 当前的训练集和测试集 .输出: 特征子集 C设 S = {f i | i =1 , …, m } 为全部特征构成的集合, C 为被选择特征构成的子集, 初始为空集, 即 C = ;根据式( 7 ) 计算训练集上每个特征的类间区分能力;选择最重要的特征 f m a x =m a x { F i , i =1 , …, m } ;令 S = S - {f m a x } ; C = C ∪ { f m a x } ;使用 C 中特征训练 S VM , 得到一个 S VM 分类模型;以该模型对训练集、 测试集进行分类, 记录相应的分类正确率;WH I L E   S ≠ D OB E G I N  m a x D F S = m i n ; m a x t e m p C = ;F O R  e a c h   f ∈ S D OB E G I N  t e m p C = C ∪ { f } ;  根据式( 6 ) 计算 D F S ( t e m p C ) ; I F   D F S ( t e m p C )  m a x D F S THE N B E G I N   m a x D F S = D F S ( t e m p C ) ;   m a x t e m p C = t e m p C ;   s e l e c t e d f e a t u r e = f ; E N D / / e n d  o f  i fE N D / / e n d  o f  f o rC = m a x t e m p C ;S = S - { s e l e c t e d f e a t u r e } ;使用 C 中特征训练 S VM , 得到一个 S VM 分类模型;以该模型对训练集、 测试集进行分类, 并记录相应的分类正确率;E N D / / e n d  o f  w h i l e
    算法2. 基于 D F S与 S VM 的顺序后向混合特征选择算法.该算法利用S B S搜索策略, 以D F S度量相应特征子集的类间区分能力,S VM 的分类准确率引导特征选择过程 . 算法从特征全集开始, 每次剔除当前余下特征中最差的一个, 即剔除该特征后的剩余特征构成最具有类间区分能力的特征子集. 以训练集分类正确率不再上升时对应的规模最小的特征子集为被选择特征子集. 算法的伪代码描述如下.输入: 当前的训练集 X t r a i n 和测试集 X t e s t输出: 特征子集 S设 S = {f i | i =1 , 2 , …, m } 为全部特征构成的集合;WH I L E   S ≠ D OB E G I N  以 S 中特征训练 X t r a i n , 得到一个 S VM 分类模型;以该模型分类 X t r a i n 和 X t e s t , 并记录分类正确率;m a x D F S = m i n ;f e a t u r e s u b s e t = S ;F O R  e a c h   f ∈ S D OB E G I N  t e m p s u b s e t = S - { f } ;  根据式( 6 ) 计算 D F S ( t e m p s u b s e t ) ;  t e m p D F S = D F S ( t e m p s u b s e t ) ; I F t e m p D F S > m a x D F S THE N B E G I N   d e l e t e f e a t u r e = f ;   f e a t u r e s u b s e t = t e m p s u b s e t ;   m a x D F S = t e mD F S ; E N D / / e n d  o f  i fE N D / / e n d  o f  f o rS = S - { d e l e t e f e a t u r e } ;E N D / / e n d  o f  w h i l e
    算法 3.   基于 D F S 与 S VM 的顺序前向浮动混合特征选择算法 .该算法将 D F S 特征评价准则与顺序前向浮动搜索策略 S F F S 结合, 以 S VM 为分类工具, 首先加入最具有类间区分能力的一个特征, 然后每次迭代加入与已选择特征组合最具有类间区分能力的相应特征, 之后浮动部分依据加入特征之后的特征子集对应S VM 分类器的分类正确率判定刚刚加入的特征是否保留. 若当前特征子集训练所得 S VM 分类模型的训练分类正确率上升, 则保留刚加入的特征,否则删除刚刚加入的特征. 该过程一直进行, 直到所有特征都被测试过. 最后留在特征子集中的特征构成最佳被选择特征子集. 算法伪代码描述如下.输入: 当前训练集和测试集输出: 特征子集 C设 S = {f i | i =1 , 2 , …, m } 为全部特征构成的集合, C 为被选择特征构成的子集, 初始为空集, 即 C = ;根据式( 7 ) 在训练集上计算每个特征的区分能力;选择最重要的特征 f m a x =m a x { F i , i =1 , 2 , …, m } ;令 S = S - {f m a x } ;令 C = C ∪ {f m a x } ;使用 C 中特征训练S VM , 得到一个S VM 分类模型;记录该模型对训练集、 测试集的分类正确率 a c c t r a i n和 a c c t e s t ;WH I L E   S ≠ D OB E G I N  m a x D F S = m i n ;m a x t e m p C = C ;F O R  e a c h   f ∈ S D OB E G I N  t e m p C = C ∪ { f } ;  根据式( 6 ) 计算 t e m p C 的 D F S 值 D F S ( t e m p C ) ; I F   D F S ( t e m p C ) > m a x D F S THE N B E G I N   m a x D F S = D F S ( t e m p C ) ;   m a x t e m p C = C ∪ { f } ;   s e l e c t e d f e a t u r e = f ; E N D / / e n d  o f  i fE N D / / e n d  o f  f o rC = m a x t e m p C ;S = S - { s e l e c t e d f e a t u r e } ;p r e a c c t r a i n = a c c t r a i n ;p r e a c c t e s t = a c c t e s t ;使用 C 中特征训练 S VM , 得到一个 S VM 分类模型;以该模型对训练集、 测试集进行分类, 记录相应的分类正确率 a c c t r a i n 和 a c c t e s t ;I F   a c c t r a i n p r e a c c t r a i n  THE NB E G I N  C = C - { s e l e c t e d f e a t u r e } ;E N D / / e n d  o f  i fE N D / / e n d  o f  w h i l e
    算法4. 基于 D F S与 S VM 的顺序后向浮动混合特征选择算法 .该算法将 D F S 特征子集区分度评价准则与S VM 结合, 以顺序后向浮动搜索策略S B F S进行特征搜索, 特征选择从全集开始, 根据 D F S值剔除当前余下特征中最差的一个特征, 即剔除该特征使得剩余特征构成的特征子集对应的 D F S值最大. 浮动部分以被选择特征子集的S VM 分类模型的分类正确率判断刚刚剔除的特征是否需要收回, 若剔除该最差特征后导致训练集的分类正确率下降, 则将刚剔除的最差特征召回; 否则剔除. 该过程一直迭代,直到所有特征都被测试过, 最后留下的特征构成被选特征子集. 算法的伪代码描述如下.输入: 当前训练集 X t r a i n 与测试集 X t e s t输出: 特征子集 C设 S = {f i | i =1 , 2 , …, m } 为包含全部特征的集合, C ={f i | i =1 , 2 , …, m } 为被选择特征构成的子集;WH I L E   S ≠ D OE G I N  以 C 中特征在 X t r a i n 训练得到一个S VM 分类模型;以该模型对 X t r a i n 和 X t e s t 进行分类, 记录相应的分类正确率 a c c t r a i n 和 a c c t e s t ;m a x D F S = m i n ; f e a t u r e s u b s e t = S ;F O R  e a c h   f ∈ S D OB E G I N  t e m p s u b s e t = S - { f } ;  根据式( 6 ) 计算 t e m p s u b s e t 的 D F S ( t e m p s u b s e t ) ;  t e m p D F S = D F S ( t e m p s u b s e t ) ; I F t e m p D F S > m a x D F S  THE N B E G I N   d e l e t e f e a t u r e = f ;   f e a t u r e s u b s e t = t e m p s u b s e t ;   m a x D F S = t e m p D F S ; E N D / / e n d  o f  i fE N D / / e n d  o f  f o rS = S - { d e l e t e f e a t u r e } ;p r e a c c t r a i n = a c c t r a i n ;p r e a c c t e s t = a c c t e s t ;使用 S 中特征训练 S VM , 得到一个 S VM 分类模型;以该模型对 X t a r i n 、 X t e s t 进行分类, 记录相应的分类正确率 a c c t r a i n 和 a c c t e s t ;I F   a c c t r a i n p r e a c c t r a i n  THE NB E G I N  C = C - { d e l e t e f e a t u r e } ;E N D / / e n d  o f  i fE N D / / e n d  o f  w h i l e
    4  实验结果与分析
    实验采用 U C I机器学习数据库 [2 1 ] 的1 0个数据集 ① i r i s , d e r m a t o l o g y , g l a s s , h a n d w r i t e , i o n o s p h e r e ,WD B C ( W i s c o n s i n  D i a g n o s t i c  B r e a s t  C a n c e r ) , W P B C( W i s c o n s i n  P r o g n o s t i c  B r e a s t  C a n c e r ) , w i n e ,t h y r o i d - d i s e a s e和h e a r t  d i s e a s e . 其中, d e r m a t o l o g y数据集, 删去了 8 个含有缺失数据的样本;g l a s s 数据集分成了 w i n d o w  g l a s s 和 n o n - w i n d o w  g l a s s 两类; h a n d w r i t e 数据集只选择了 s e m e i o n  h a n d w r i t t e nd i g i t数据集的前两类; WP B C数据集删去了4个含有缺失数据的样本;t h y r o i d - d i s e a s e数据集是其中的 n e w - t h y r o i d ,即 t h y r o i d  g l a n d  d a t a 数 据 集;h e a r t  d i s e a s e 数据集使用了其中的 p r o c e s s e d  c l e v e-l a n d数据集, 并删去了6个含有缺失数据的样本. 数据集详细信息如表1描述. 实验环境为 D e l l  V o s t r o4 5 0笔记本电脑,I n t e l  C o r e  i 5 - 2 4 5 0  2 . 5 0 GH z  C P U ,4G B 内 存, W i n 7  6 4 位 操 作 系 统,M a t l a b 应 用软件.  
为得到具有统计意义的实验结果, 采用 5 折交叉验证实验 . 
    同时, 为了得到随机的实验数据, 采用将样本顺序随机打乱, 每一类样本依次逐个加入到5 个初始为空的样本集合, 直到这一类的每一个样本都被加入, 实现将样本随机均匀划分为 5 份的目的 . 以 1 份样本为测试样本集, 其余 4 份为训练样本集, 并以每 1 份都做过测试集结束 5 折交叉验证实验 . 样本随机打乱的方法是: 随机生成一个 5 0 0 0×2的2维数组, 数组每一元素的值在1~ 数据集规模之间; 交换数组每一行两个元素值对应的两个样本 .实验采用林智仁教授等开发的S VM 工具箱 [2 2 ] , 核函数采用 R B F ( R a d i a l  B a s i s  F u n c t i o n ) 核函数[ 2 3 ] .为了更客观地比较基于不同特征子集评价准则的特征选择算法的性能, 对各特征子集评价准则进行性能比较, 本文各算法的核函数参数均采用默认值.为测试提出的 D F S特征子集评价准则的有效性, 将其与 C F S以及提出的 C F S P a b s特征子集评价准则进行实验比较. 
    3 种分别基于 D F S 、 C F S 和C F S P a b s 不同特征子集重要性( 区分度) 评价准则与S VM 的特征选择算法的实验结果如表2 ~ 表5所示.表中数值为各算法 5 折交叉验证实验对应实验结果的平均值, 加重和加下划线的被选择特征数、 测试集分类正确率、 运行时间( 以s为单位) 分别表示最小的特征子集规模、 最高的分类正确率、 最快的运行速度 .为了更清楚地展示特征依次被选入( 或依次被剔除) 时, 相应 S VM 的正确率变化情况, 以说明选择到多少个特征时才是最好的, 图 1、 图2 分别展示了基于 S F S 、 S B S 搜索策略, 并分别以 D F S 、 C F S 和C F S P a b s为特征子集重要性( 区分度) 评价准则, 以S VM 为分类工具的相应特征选择算法的训练正确率和测试正确率变化曲线 . 其中的训练正确率与测试正确率变化曲线是5折交叉验证实验的平均正确率曲线 .表 2 基于 S F S 搜索序策略的 5 折交叉验证实验结果显示, 提出的 D F S 特征子集评价准则在 i r i s ,d e r m a t o l o g y , h a n d w r i t e , WD B C ,t h y r o i d - d i s e a s e 和h e a r t  d i s e a s e  6 个数据集上选择的特征子集的分类正确率高于等于 C F S 、 C F S P a b s 准则选择的特征子集的分类正确率; C F S 准则在 g l a s s , WP B C 和 w i n e3 个数据集上的分类正确率超过 D F S 和 C F S P a b s准则; C F S P a b s准则只在i o n o s p h e r e一个数据集上的分类正确率超过 D F S和 C F S准则. 特征子集规模比较显示: C F S P a b s准则选择的特征子集规模优于 D F S和 C F S准则. 
其中, 在 d e r m a t o l o g y , g l a s s ,h a n d w r i t e和 w i n e     4个数聚集上优于 D F S和 C F S准则, 在i o n o s p h e r e和t h y r o i d - d i s e a s e数据集上等于C F S P a b s准则, 优于提出 D F S准则选择的特征子集规模; D F S准则只在i r i s数据集上与其他两个准则持平, 在其他9个数据集上都不如其他两个准则; C F S准则在 WD B C ,WP B C和h e a r t  d i s e a s e共3个数据集上优于其他两个准则 . 运行时间比较显示:提出的 D F S特征子集评价准则优于其他两个特征子集评价准则, 特别体现在 h a n d w r i t e这类较高维数据集的特征选择上, 基于 D F S特征子集评价准则的特征选择算法明显优于其他两个准则. 1 0个数据集的运行时间显示, D F S准则在5个数据集上运行时间优于 C F S 和 C F S P a b s 准则; 而 C F S p a b s 准则在 3 个数据集上较优; C F S 准则在 2 个数据集上较优 .以上对于表 2 实验结果的分析得出: 提出的D F S 特征子集评价准则无论运行时间还是所选择特征子集的分类性能都较优, 但所选择的特征子集规模不是最优的 . 然而从 h a n d w r i t e 这一较高维数据集的实验结果来看, 提出的 D F S特征子集评价准则优于 H a l l提出的C F S特征子集评价准则.表3基于S B S搜索策略的实验结果显示, 在所选特征子集的分类正确率、 相应特征选择算法的运行时间两个指标的平均值比较上, 提出的 D F S特征子集评价准则优于C F S和C F S P a b s准则; 另外,C F S和C F S P a b s准则相比, 后者优于前者. 从选择的特征子集规模来看, 虽然提出的 D F S特征子集评价准则只在h a n d w r i t e数据集上较优, 但是3个特征子集评价准则的比较可见, D F S准则在 h a n d w r i t e数据集上选择的特征数远远少于 C F S 和 C F S P a b s 准则选择的特征数. 虽然 C F S准则在7个数据集上选择的特征子集规模优于其他两准则, 但是特征子集的规模差别不像 D F S与 C F S 、 C F S P a b s在h a n d w r i t e数据集选择的特征子集规模差别那么突出.以上表2和表3 实验结果的分析得出: 提出的D F S特征子集区分度衡量准则最好. 其选择的特征子集不仅泛化性能好, 而且对于较高维数据集的降维效果特别突出; 另外, 基于 D F S特征子集评价准则与S VM 的特征选择算法的运行效率较高.表4基于 S F F S搜索策略的实验结果显示: 提出的 D F S特征子集区分度衡量准则在 3个数据集i r i s 、 h a n d w r i t e和t h y r o i d - d i s e a s e上选择的特征子集的分类正确率最高; C F S准则在 g l a s s 、 WP B C和w i n e  3 个数据集上选择的特征子集具有较高的分类正确率; 改进的 C F S P a b s准则在 D e r m a t o l o g y 、i o n o s p h e r e和 WD B C  3个数聚集上选择的特征子集分类正确率最好; 对于 h e a r t  d i s e a s e数据集, D F S 、C F S 和 C F S P a b s  3 个特征子集评价准则选择的特征子集具有相同的分类性能 . 
    特征子集规模分析可见, 改 进 的 C F S P a b s 准 则 在 d e r m a t o l o g y 、 g l a s s 、h a n d w r i t e 、 i o n o s p h e r e 、 WD B C 、 WP B C 、 w i n e 和 t h y -r o i d - d i s e a s e 共 8 个数聚集上选择的特征子集规模不超过 D F S 准则和 C F S 准则, 其中在 WD B C 和t h y r o i d - d i s e a s e两 个 数 据 集 上 与 C F S 准 则 相 同;C F S 准则只在 h e a r t  d i s e a s e 数据集上最优; 提出的D F S 准则只在 i r i s 数据集上选择的特征子集规模优于其他两准则 .表5基于 S B F S搜索策略的实验结果显示, 提出的 D F S 特征子集区分度评价准则性能最优, 因为基于 D F S 准则的顺序后向浮动特征选择算法的5 折交叉验证实验, 无论其选择的特征子集平均规模, 还是其选择的特征子集的平均分类正确率, 还是其平均运行时间都优于基于其他两个特征子集评价准则 C F S 与 C F S P a b 的特征选择算法 .表2~表5的实验结果还显示: 对于较高维数据集进行特征选择, S F S特征搜索策略的运行时间低于S B S , S F F S搜索策略需要的时间低于 S B F S.另外, 从h a n d w r i t e数据集的5折交叉验证实验的运行时间明显可见, 除了采用 S F F S搜索策略的特征选择算法外, 其他以 S F S 、 S B S 、 S B F S 为搜索策略的3个特征选择算法, D F S特征子集评价准则明显优于 C F S 和 C F S P a b s 准则 .所得分类器在该数据集的泛化性能, 无论采用那个搜索策略, D F S 特征子集评价准则选择的特征子集的分类性能都最好 .图1关于特征依次被选入时在1 0个 U C I数据集的5折交叉验证实验的平均训练和测试正确率比较显示, 提出的 D F S特征子集重要性评价准则选择的特征子集具有更好的泛化性能, C F S P a b s准则能选择到规模较小的特征子集 . 图1展示的详细实验结果与表2所示的实验结果一致.图 2 关于特征依次被剔除时的 5 折交叉验证实验的平均训练和测试正确率的详细结果与表 3 展示的实验结果一致 . 从图 2 实验结果的比较看出, 提出的 D F S特征子集评价准则选择的特征子集的泛化性能优于 C F S 和 C F S P a b s 准则 . 另外, 在 h a n d w r i t e这一较高维数据集, D F S 特征子集评价准则不仅选择的特征子集的泛化性能很好, 而且选择的特征子集的规模也小于 C F S和C F S P a b s准则.以上5折交叉验证实验的结果分析揭示: 本文提出的 D F S特征子集区分度衡量准则是一个很好的特征子集类间区分能力度量准则, 基于该准则的特征选择算法所选择的特征子集具有很好的泛化性能, 且对于较高维数据集, 该准则不仅大大降低数据维数, 还具有很高的运行效率, 需要的运行时间最少. 我们对 C F S准则改进得到的 C F S P a b s特征子集评价准则所选特征子集的泛化性能与 C F S准则选择的特征子集的泛化性能差别不大, 但是基于C F S P a b s 准则的特征选择算法运行时间效率较高,且选择的特征子集规模优于 C F S 准则选择的特征子集的规模 .
    5  结论与应用前景展望
    本文提出了 D F S特征子集区分度评价准则, 该准则充分考虑特征之间的相关性, 通过计算整个特征子集对于分类的联合贡献克服了单个特征区分度准则在衡量特征的类间辨别能力大小时, 没有考虑特征之间的相关性对于单个特征辨别能力大小影响的缺憾, 以及 H a l l提出的 C F S特征子集评价准则对于特征之间相关性考虑不足和不适于连续性数值的缺陷. 在此基础上, 以 D F S准则作为特征选择依据, 提出基于不同特征搜索策略与 S VM 的 4 种混合特征选择算法.U C I机器学习数据库的 1 0 个经典数据集的5折交叉验证实验表明: 提出的 D F S特征子集区分度评价准则是一种有效的特征子集辨识能力衡量准则, 基于该准则与 S VM 的混合特征选择算法选择的特征子集具有很好的分类效果, 其泛化性能优于分别基于C F S和C F S P a b s特征子集评价准则的特征选择算法, 达到了保持数据集辨识能力情况下进行维数压缩的目的, 特别是对较高维数据集, D F S特征子集评价准则特别有效. 实验结果同时显示: 我们改进的 C F S P a b s特征子集评价准则 优 于 C F S准则 .本文实验还揭示, 提出的 D F S特征子集区分度衡量准则选择出了分类红斑鳞状皮肤病等疾病的有效特征子集, 实现了对相应疾病的诊断.另外, 伴着计算机网络带来的文本大数据, 以及医疗诊断大数据和社会大数据, 还有随着分子生物技术发展产生的癌症基因大数据, 特征选择是对这些大数据进行分类分析的首要和关键步骤. 本文提出的特征选择方法及其变种将在这些蓬勃兴起的大数据领域发挥重要作用 . 继本文之后, 我们已经开展了关于癌症基因数据集的特征选择方法研究, 并取得了很好的实验结果.
    参 考 文 献[ 1 ] G u y o n  I , E l i s s e e f f  A. A n  i n t r o d u c t i o n  t o  v a r i a b l e  a n d  f e a t u r es e l e c t i o n. T h e  J o u r n a l  o f  M a c h i n e  L e a r n i n g   R e s e a r c h , 2 0 0 3 ,3 : 1 1 5 7 - 1 1 8 2[ 2 ] G u y o n  I , W e s t o n  J , B a r n h i l l  S , e t  a l .G e n e  s e l e c t i o n  f o rc a n c e r  c l a s s i f i c a t i o n  u s i n g   s u p p o r t  v e c t o r  m a c h i n e s .M a c h i n eL e a r n i n g , 2 0 0 2 , 4 6 ( 1 - 3 ) : 3 8 9 - 4 2 2[ 3 ] R a k o t o m a m o n j y   A. V a r i a b l e  s e l e c t i o n  u s i n g   s v m  b a s e d  c r i t e r i a .T h e  J o u r n a l  o f  M a c h i n e  L e a r n i n g   R e s e a r c h , 2 0 0 3 , 3 : 1 3 5 7 -1 3 7 0[ 4 ] D u a n  K  B , R a j a p a k s e  J  C , W a n g   H , e t  a l .M u l t i p l e  S VM -R F E  f o r  g e n e  s e l e c t i o n  i n  c a n c e r  c l a s s i f i c a t i o n  w i t h  e x p r e s s i o nd a t a . I E E E  T r a n s a c t i o n s  o n  N a n o B i o s c i e n c e , 2 0 0 5 , 4 ( 3 ) :2 2 8 - 2 3 4[ 5 ] X i a  H , H u  B  Q. F e a t u r e  s e l e c t i o n  u s i n g   f u z z y   s u p p o r t  v e c t o rm a c h i n e s . F u z z y   O p t i m i z a t i o n  a n d  D e c i s i o n  M a k i n g , 2 0 0 6 ,5 ( 2 ) : 1 8 7 - 1 9 2[ 6 ] Z h o u  X , T u c k  D  P.M S VM - R F E : E x t e n s i o n s  o f  S VM - R F Ef o r  m u l t i c l a s s  g e n e  s e l e c t i o n  o n  D NA m i c r o a r r a y   d a t a .B i o i n f o r m a t i c s , 2 0 0 7 , 2 3 ( 9 ) : 1 1 0 6 - 1 1 1 4[ 7 ] M a l d o n a d o  S , W e b e r  R. A w r a p p e r  m e t h o d  f o r  f e a t u r es e l e c t i o n  u s i n g   s u p p o r t  v e c t o r  m a c h i n e s . I n f o r m a t i o nS c i e n c e s , 2 0 0 9 , 1 7 9 ( 1 3 ) : 2 2 0 8 - 2 2 1 7[ 8 ] S o m o l  P , N o v o v i c o v a  J .E v a l u a t i n g   s t a b i l i t y   a n d  c o m p a r i n go u t p u t  o f  f e a t u r e  s e l e c t o r s  t h a t  o p t i m i z e  f e a t u r e  s u b s e tc a r d i n a l i t y .I E E E  T r a n s a c t i o n s  o n  P a t t e r n  A n a l y s i s  a n dM a c h i n e  I n t e l l i g e n c e , 2 0 1 0 , 3 2 ( 1 1 ) : 1 9 2 1 - 1 9 3 9[ 9 ] T a p i a  E , B u l a c i o  P , A n g e l o n e  L.S p a r s e  a n d  s t a b l e  g e n es e l e c t i o n  w i t h  c o n s e n s u s  S VM - R F E.P a t t e r n  R e c o g n i t i o nL e t t e r s , 2 0 1 2 , 3 3 ( 2 ) : 1 6 4 - 1 7 2[ 1 0 ] M a o  Y o n g , Z h o u  X i a o - B o , X i a  Z h e n g , e t  a l .A  s u r v e y   f o rs t u d y   o f  f e a t u r e  s e l e c t i o n  a l g o r i t h m s .C h i n e s e  J o u r n a l  o fP a t t e r n  R e c o g n i t i o n  a n d  A r t i f i c i a l  I n t e l l i g e n c e , 2 0 0 7 , 2 0 ( 2 ) :2 1 1 - 2 1 8 ( i n  C h i n e s e )( 毛勇,周晓波,夏铮等 . 特征选择算法研究综述 . 模式识别与人工智能, 2 0 0 7 , 2 0 (2 ) : 2 1 1 - 2 1 8 )[ 1 1 ] Wh i t n e y   A W.A  d i r e c t  m e t h o d  o f  n o n p a r a m e t r i c  m e a s u r e -m e n t  s e l e c t i o n.I E E E  T r a n s a c t i o n s  o n  C o m p u t e r s , 1 9 7 1 ,1 0 0 ( 9 ) : 1 1 0 0 - 1 1 0 3[ 1 2 ] M a r i l l  T , G r e e n  D M.O n  t h e  e f f e c t i v e n e s s  o f  r e c e p t o r s  i nr e c o g n i t i o n  s y s t e m s .I E E E  T r a n s a c t i o n s  o n  I n f o r m a t i o nT h e o r y , 1 9 6 3 , 9 ( 1 ) : 1 1 - 1 7[ 1 3 ] P u d i l  P , N o v o v i ˇc o v J , K i t t l e r  J . F l o a t i n g   s e a r c h  m e t h o d s  i nf e a t u r e  s e l e c t i o n . P a t t e r n  R e c o g n i t i o n  L e t t e r s , 1 9 9 4 , 1 5 ( 1 1 ) :1 1 1 9 - 1 1 2 5[ 1 4 ] B l u m A  L , L a n g l e y   P.S e l e c t i o n  o f  r e l e v a n t  f e a t u r e s  a n de x a m p l e s  i n  m a c h i n e  l e a r n i n g .A r t i f i c i a l  I n t e l l i g e n c e , 1 9 9 7 ,9 7 ( 1 ) : 2 4 5 - 2 7 1[ 1 5 ] K o h a v i  R , J o h n  G H.W r a p p e r s  f o r  f e a t u r e  s u b s e t  s e l e c t i o n.A r t i f i c i a l  I n t e l l i g e n c e , 1 9 9 7 , 9 7 ( 1 ) : 2 7 3 - 3 2 4[ 1 6 ] L a l  T N , C h a p e l l e  O , W e s t o n  J , e t  a l . E m b e d d e d  m e t h o d s / /G u y o n  I , N i k r a v e s h  M , G u n n  S , Z a d e h  L  A  e d s .F e a t u r ee x t r a c t i o n. B e r l i n  H e i d e l b e r g : S p r i n g e r - V e r l a g , 2 0 0 6 : 1 3 7 -1 6 5[ 1 7 ] U n c u , T ü r k 爧 e n  I  B.A  n o v e l  f e a t u r e  s e l e c t i o n  a p p r o a c h :C o m b i n i n g   f e a t u r e  w r a p p e r s  a n d  f i l t e r s . I n f o r m a t i o nS c i e n c e s , 2 0 0 7 , 1 7 7 ( 2 ) : 4 4 9 - 4 6 6[ 1 8 ] H u  Q , P e d r y c z  W , Y u  D , e t  a l .S e l e c t i n g   d i s c r e t e  a n dc o n t i n u o u s  f e a t u r e s  b a s e d  o n  n e i g h b o r h o o d  d e c i s i o n  e r r o rm i n i m i z a t i o n.I E E E  T r a n s a c t i o n s  o n  S y s t e m s , M a n , a n dC y b e r n e t i c s , P a r t  B : C y b e r n e t i c s , 2 0 1 0 , 4 0 ( 1 ) : 1 3 7 - 1 5 0[ 1 9 ] X i e  J , W a n g   C.U s i n g   s u p p o r t  v e c t o r  m a c h i n e s  w i t h  a  n o v e lh y b r i d  f e a t u r e  s e l e c t i o n  m e t h o d  f o r  d i a g n o s i s  o f  e r y t h e m a t o -s q u a m o u s  d i s e a s e s . E x p e r t  S y s t e m s  w i t h  A p p l i c a t i o n s ,2 0 1 1 , 3 8 ( 5 ) : 5 8 0 9 - 5 8 1 5[ 2 0 ] H a l l  M A.C o r r e l a t i o n - b a s e d  f e a t u r e  s e l e c t i o n  f o r  m a c h i n el e a r n i n g [ P h. D. d i s s e r t a t i o n ] .T h e  U n i v e r s i t y o f  W a i k a t o ,H a m i l t o n , N e w  Z e a l a n d , 1 9 9 9[ 2 1 ] F r a n k  A , A s u n c i o n  A.U C I  m a c h i n e  l e a r n i n g   r e p o s i t o r y[ E B / O L ] . h t t p : / / www. i c s . u c i . e d u / ~m l e a r n / ML R e p o s i -t o r y . h t m l . I r v i n e , C A : U n i v e r s i t y   o f  C a l i f o r n i a , S c h o o l  o fI n f o r m a t i o n  a n d  C o m p u t e r  S c i e n c e , 2 0 1 0[ 2 2 ] C h a n g   C  C , L i n  C  J . L I B S VM : A  l i b r a r y   f o r  s u p p o r t  v e c t o rm a c h i n e s .A CM T r a n s a c t i o n s  o n  I n t e l l i g e n t  S y s t e m s  a n dT e c h n o l o g y ( T I S T ) , 2 0 1 1 , 2 ( 3 ) : 1 - 2 7[ 2 3 ] H s u  C W , C h a n g   C  C , L i n  C  J . A  p r a c t i c a l  g u i d e  t o  s u p p o r tv e c t o r  c l a s s i f i c a t i o n. D e p a r t m e n t  o f  C o m p u t e r  S c i e n c e ,N a t i o n a l  T a i w a n  U n i v e r s i t y , T e c h n i c a l  R e p o r t . T a i p e i ,C h i n a , 2 0 0 3
 
[返回]
上一篇:基于后验 HOG 特征的多姿态行人检测
下一篇:无线传感器网络通信负载状态识别方法的研究