（计算机应用技术专业论文）基于支持向量机的特征选择及其分类算法研究.pdf

中山大学硕士学位论文 摘要 论文题目：基于支持向量机的特征选择及其分类算法研究 专业：计算机应用技术 姓名：曾霖 导师：任江涛 摘要 特征选择是数据挖掘领域中一个重要的研究课题，特征选择可以剔除学习过 程中冗余的、无关的和有噪声的特征，从而得到一个维数最少而判别能力更强的 信息特征子集。可以有助于提高模式识别的识别率，机器学习算法的精度及其泛 化能力。随着大规模数据的不断增长，不仅样本数很大，而且样本的特征维数也 很高。在此情况下，分类算法的时间复杂度会随着不相关特征或噪声数据成指数 增长，不仅会造成维数灾难( c u r s eo f d i m e n s i o n a l i t y ) ，也会造成降低分类算法的效 果，因此有必要进行特征选择。一个特征选择的过程在原理上可以看成是一个组 合优化过程，在原有的特征中选择其中的一部分，使某个特定的评价函数最优。 但传统基于支持向量机的特征选择算法精度低并且时间复杂度高，本文重点研究 了基于支持向量机的特征选择及其分类算法的基本概念和相关理论基础，提出了 3 个s v m r f e 特征选择算法的改进算法。为了避免s v m r f e 特征选择算法在 特征空间搜索过程效率较低的缺陷，在基于s v m r f e 的特征选择算法中结合了 模式识别领域的两种重要的特征选择方法过滤( f i l t e r ) 和封装( w r a p p e r ) 的优点，得 到s v m r f e 的特征选择改进算法( a s v m r f e ) ，并且利用相关的数学知识和原 理分析了s v m r f e 特征选择算法不能剔除线性冗余特征的情况，利用相关系数 的方法剔除冗余特征进一步改进了s v m r f e 算法( a d s v m r f e ) 。受到w e s t o n 等人在特征选择算法中利用梯度下降法来优化特征搜索策略的启发，本文也在 s v m r f e 特征选择算法中应用了梯度下降法的方法( g a d s v m r f e ) 来求解最 优的信息特征子集。上述的3 个特征选择改进算法都分别进行了实验和效果的分 析，实验结果表明这3 个特征选择改进算法在急性白血病数据集、u c i 数据集和 w e s t o n 数据集等中搜索出的信息特征子集都获得较高的分类准确率和优越的时 间性能，取得了较好的实验效果。最后用改进算法( o a d s v m r f e ) 在真实的肿 瘤数据集应用，实验结果和分析表明其具有一定的实用价值和应用前景。 关键词：支持向量机；特征选择；高维数据；生物基因芯片分析 中山大学硕士学位论文 t i t l e ：f e a t u r es e l e c t i o na n dc l a s s i f i c a t i o na l g o r i t h mb a s e do ns u p p o r tv e c t o rm a c h i n e s m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：l i nz e n g s u p e r v i s o r ：j i a n g t a or e n a b s t r a c t f e a t u r es e l e c t i o ni sa ni m p o r t a n tf i e l do fd a t am i n i n gr e s e a r c ht o p i c ，f e a t u r e s e l e c t i o nc a l le l i m i n a t et h el e a r n i n gp r o c e s sr e d u n d a n t ，i r r e l e v a n ta n dn o i s yf e a t u r e s ， w h i c hh a v ead i m e n s i o no fa tl e a s tt h ea b i l i t yt od e t e r m i n em o l ei n f o r m a t i o no n f e a t u r es u b s e t c a nh e l pt oi m p r o v et h er e c o g n i t i o nr a t eo fp a a e r nr e c o g n i t i o n , m a c h i n el e a r n i n ga l g o r i t h ma c c u r a c ya n dg e n e r a l i z a t i o na b i l i t y w i t ht h eg r o w i n g m a s so fd a t a , n o to n l yl a r g es a m p l es i z e ，a n df e a t u r e so ft h es a m p l ed i m e n s i o ni sa l s o v e r yh i g l l i nt h i sc a s e ，t h ec l a s s i f i c a t i o na l g o r i t h mo ft i m ec o m p l e x i t yw i l lb e 勰 i r r e l e v a n to rn o i s ef e a t u r e so ft h ee x p o n e n t i a lg r o w t ho fd a t a , n o to n l yw i l lc a u s et h e c u r s eo fd i m e n s i o n a l i t y ( c u r s eo fd i m e n s i o n a l i t y ) ，a l s ow i l lr e s u l ti nl o w e r c l a s s i f i c a t i o na l g o r i t h mr e s u l t s t h e r e f o r e ，t h en e e df o rf e a t u r es e l e c t i o n af e a t u r e s e l e c t i o np r o c e s si np r i n c i p l ec a l lb ev i e w e da sac o m b i n a t o r i a lo p t i m i z a t i o np r o c e s s ， t h ef e a t u r e so ft h eo r i g i n a ls e l e c to n ep a r to ft h ee v a l u a t i o nf u n c t i o nt oap a r t i c u l a r o p t i m a l h o w e v e r , t h et r a d i t i o n a lf e a t u r es e l e c t i o nb a s e do ns u p p o r tv e c t o rm a c h i n e s a l g o r i t h mt ol o wa c c u r a c ya n dh i 曲t i m ec o m p l e x i t y , t h i sa r t i c l ef o c u s e so nf e a t u r e s e l e c t i o nb a s e do ns u p p o r tv e c t o rm a c h i n e sa n dc l a s s i f i c a t i o na l g o r i t h m sb a s e do n f u n d a m e n t a lc o n c e p t sa n dt h e o r i e s ，t h e np u tf o r w a r dt h r e es v m r f ef e a t u r es e l e c t i o n a l g o r i t h ma l g o r i t h m i no r d e rt oa v o i dt h es v m - r f ef e a t u r es e l e c t i o na l g o r i t h mi n f e a t u r es p a c es e a r c hp r o c e s sl e s se f f i c i e n td e f e c t , s v m r f e b a s e df e a t u r es e l e c t i o n a l g o r i t h m ，c o m b i n e dw i t hp a t t e r nr e c o g n i t i o no ft w oi m p o r t a n tf e a t u r e ss e l e c t i o n m e t h o d sa d v a n t a g eo ff i l t e ra n dw r a p p e r , t h e no b t a i n e ds v m r f ef e a t u r es e l e c t i o n i m p r o v e da l g o r i t h m ( a - s v m r f e ) ，a n du s eo fr e l e v a n tk n o w l e d g ea n dp r i n c i p l e so f m a t h e m a t i c a la n a l y s i ss v m r f ef e a t u r es e l e c t i o na l g o r i t h mc a r ln o te x c l u d et h ec a s e 1 1 1 中山大学硕士学位论文 a b s t m c t o fl i n e a rr e d u n d a n tf e a t u r e s ，u s i n gc o r r e l a t i o nc o e f f i c i e n tm e t h o dt oe l i m i n a t e r e d u n d a n tf e a t u r e sf u r t h e ri m p r o v et h es v m - r f ea l g o r i t h m ( g o - s v m r f e ) b y w e s t o na n do t h e r si nt h ef e a t u r es e l e c t i o na l g o r i t h mu s i n gg r a d i e n td e s c e n tt o o p t i m i z et h ef e a t u r e so fs e a r c hs t r a t e g yi n s p i r e d ，t h e nt h i s a r t i c l ea r es v m - r f e f e a t u r es e l e c t i o na l g o r i t h mi nt h ea p p l i c a t i o no ft h eg r a d i e n td e s c e n tm e t h o dt of m d t h e o p t i m a lf e a t u r e s u b s e to fi n f o r m a t i o n t h ea b o v et h r e ef e a t u r es e l e c t i o n a l g o r i t h m sw e r ec a r r i e do u tt oi m p r o v ee x p e r i m e n t a la n da n a l y t i c a lr e s u l t s ，t h e r e s u l t ss h o wt h a tt h et h r e ef e a t u r es e l e c t i o na l g o r i t h m st oi m p r o v ed a t ac o l l e c t i o ni n a c u t el e u k e m i a , u c id a t as e t sa n dw e s t o nd a t as e t st os e a r c ho u ti n f o r m a t i o ns u c ha s f e a t u r es u b s e ta r e g i v e nah i g h e r c l a s s i f i c a t i o n a c c u r a c y a n d s u p e r i o rt i m e p e r f o r m a n c e ，a c h i e v e dg o o de x p e r i m e n t a le f f e c t f i n a l l y , t h ei m p r o v e df e a t u r e s e l e c t i o na l g o r i t h m ( g a d s v m r f e ) w a sa p p l i e dt or e a lt u m o rd a t as e t s ， e x p e r i m e n tr e s u l t sa n da n a l y s i ss h o wt h a ti th a sc e r t a i np r a c t i c a lv a l u ea n da p p l i c a t i o n p r o s p e c t s k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e s ；f e a t u r es e l e c t i o n ；h j 【g hd i m e n s i o n a ld a t a ； m i c r o a r r a ya n a l y s i so fb i o l o g i c a l i v 中山 学砸士学位论文 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指寸h 立进行研究工作所取得的成果。除本文已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：、髫霖 日期：】口l d 年占月彳日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于菲赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可咀采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：嗜嘛 日期：扣f 牟占月f 日 导师签名： 日期：汕 第一章绪论弟一早殖记 本章将介绍本文的研究背景及其意义，并对国内外相关的研究进行概述，最 后将介绍本文的研究工作和内容安排。 1 1 研究背景 数据挖掘是从数据库、数据仓库、万维网或者其它信息存储库大量数据中提 取有用知识的过程，它是统计学、机器学习、并行算法、人工智能、模式识别、 神经网络、数据库及数据仓库技术等学科的交叉集成。近年来随着生物医学和信 息技术地不断发展，出现了成千上万维的数据集，这些领域包括因特网文档处理、 基因表达阵列及其组合化学，引起越来越多的国内外学者关注( g u y o n ，2 0 0 3 ) t 1 1 。 这就要求能对大量冗余或不相关的特征而训练样本数量相对较少数据进行处理 的新技术。因此需要进行有效的特征选择以利于数据的可视化和理解，缩短训练 和预测时间，减少在线运算的资源，提高系统的可解释性，增强学习算法的性能 ( b u n k e ，2 0 0 4 ；s a o n & p a d m a n a b h a n ，2 0 0 1 ) t 2 1 t 3 1 。特征选择方法的研究在统计学、 机器学习、数据挖掘及其模式识别等领域成为研究热点，特别是当需要处理数据 的属性( 变量、特征) 数目达到成千上万时，尤其需要进行特征选择。其主要思 想是去除无关的或冗余的特征来选择相应的输入属性子集用来提高预测性能，提 高机器学习速度，从而只需要利用极少数的特征就可以达到最佳分类性能的效 果。 1 2 国内外研究现状 特征选择在现实应用中无处不在，可以应用于声音辨别、图像处理、文本分 类、医疗、数据挖掘、多媒体、网络搜索等方面的处理，可以提高分类器预测能 力，提供更快、更高效率的数据分析处理，更好理解数据产生的基本过程，达到 数据最小的冗余性和最大的相关性。特征选择是数据挖掘领域的研究主要课题之 一，也是模式识别系统步骤的主要组成部分，在设计和选择特征过程中希望能得 到有效区分模型中不同类别的特征集。早在1 9 9 7 年人们就开始出现对变量和特 中山大学硕士学位论文 征选择的研究( k o h a v i & j o h n ，1 9 9 7 ；b l u m & l a n g l e y , 1 9 9 7 ) 1 】【4 】，当时大多数研究 领域由于数据获取能力限制仅仅局限于对几十维特征数据的探索。近年来在信息 科学研究中涌现出海量指数级增长的复杂数据，如何从这些众多不相关、冗余的 而又相对少得多训练样本的复杂数据中提取有用的信息是当前信息数据处理领 域研究热点之一，也是收集、存储、分析这些数据的最终目的。特征选择有助于 降低测量和存储数据的要求，有利于数据的可视化和理解，缩短训练和预测数据 的时间并且能避免数据维数灾难以提高模型的分类预测性能。特征选择在数据挖 掘领域中的监督学习方面已经得到很好的研究，其主要目的是找到能够提高分类 预测性能的特征子集。近年来一些学者( d y & b r o d l e y ，2 0 0 0 b ；l i u & y u ，2 0 0 5 ) 5 】【6 】 通过单一的或统一标准将特征选择与聚类结合起来进行研究；在无监督学习的特 征选择中，学习算法是为了找到样本在特征空间上的自然分组。因此特征选择是 在无监督学习中的目标是在给定簇数目情况下能找到形成高质量簇的特征子集。 模式识别、数据挖掘中特征选择算法有f i l t e r ( 过滤) 和w r a p p e r ( 封装) 两种主 要框架，f i l t e r 是在预处理过程中完全与学习过程不相关，根据独立于分类器的 度量指标j 来评价所选择的特征子集s ，在所有可能的特征子集中搜索出使得j 最大的特征子集作为最优特征子集。如一些排列标准( f o r m a n ，2 0 0 3 ；w e s t o ne ta 1 ， 2 0 0 3 ) 【刀【8 1 利用距离度量( 如欧式距离) ，互信息度量( 如信息增益) ，一致性度量 ( 如不一致性率) 或单变量分类器的性能来给每个特征进行评分。而w r a p p e r 是根据学习机预测性能来决定特征子集的相关性( k o h a v i & j o h n ，1 9 9 7 ) t 。两者 主要的区别在于特征变量选择和学习算法是否是独立过程。嵌入式( e m b e d d e d ) 方法是在训练过程中进行特征选择的如决策树( b r e i m a n ，2 0 0 1 ) 9 】和最近研究成果 的稀疏执行惩罚方法。f r i e d m a n ( 2 0 0 7 ) 1 0 】提出将惩罚定义为l 1 n o r m 和把错误等 于残差平方和的算法即最小绝对收缩和选择算子算法，用来找到相应的极小目标 函数。许多特征选择算法力求解决搜索问题，经典算法有分支定界法( 最优搜索) 、 次优搜索( 单独最优特征组合法、顺序前进法、顺序后退法) 、其他组合优化方 法( 模拟退火法、t a b u 搜索法、遗传算法) 。文献( d e s t r e r o ，2 0 0 9 ；z o u & h a s t i e ， 2 0 0 5 ) 【1 1 】【1 2 1 提出了结合弹性网策略和迭代软阈值算法( d a u b e c h i e se ta 1 ，2 0 0 4 ) t 1 3 】 解决生物计算和计算机视觉两种不同领域特征选择最小平方问题稀疏限制的正 规化特征选择方法。不同的特征选择可以进一步分类成两类即特征权重算法和子 2 第一章绪论 集搜索算法，通过个体特征或特征子集来评估其特征好坏特征权重算法通过它 们与目标函数给每个特征赋予权重并排列特征相关性有不同的定义例如文献 ( k o h a v i & j o h n ，1 9 9 7 ；b l u m & l a n g l e y ，1 9 9 7 ) j 1 4 ，比较著名的相关性评估算 法是r e l i e f 算法( k i r a & r e n d e l l ，1 9 9 2 ) t 1 4 】，其重要思想是特征相关性根据它们的 值能够有效地区分不同类别的样本。但是r e l i e f 算法并不能消除特征的冗余性， 只要认为特征跟目标类概念相关，即使是特征互相之间有很强的关联，也会将其 选中( k i r a & r e n d e l l ，1 9 9 2 ) ! 。从特征选择文献的经验事实表明不相关的、冗余 的、有噪声的特征也会影响到学习算法的速度和性能，有必要消除这些特征 ( x i n p i n g c u i le ta 1 ，2 0 1 1 5 】。因此本课题具有较高应用前景和实际研究价值。 1 3 本文研究内容和工作 本文的研究内容和工作有以下几个方面： 主要研究基于支持向量机的特征选择及其分类算法，从研究统计学理论的原 理出发，引入支持向量机的分类模型，然后利用错误概率期望上界来构建最佳的 分类模型，从而达到特征选择的目的；并且利用梯度下降法解决传统特征搜索算 法时间复杂度过高的问题。 本文针对经典的基于支持向量机s v m r f e 特征选择算法在处理高维特征数 据集时搜索速度过慢的情况，结合模式识别中的两种主要特征选择方法f i l t e r 和 w r a p p e r 各自的优点来改进其搜索策略，并且针对其在处理不相关的特征具有很 好的效果，但是不能考虑到特征的冗余特征的缺陷，本文在基于支持向量机的特 征选择算法中尝试结合相关系数、互信息理论来进行特征选择，进一步提高其分 类性能，从而达到所选特征子集的最大关联和最小冗余。实验数据集表明这种方 法不仅可以减少特征数、提高分类性能，并且具有优越的时间性能。 提高支持向量机分类回归性能关键因素是选择合适的核函数，本文研究了核 函数统一框架的基础上利用缩放可变参数进行特征选择的算法原理，并且分析了 各种特征选择算法的分类性能，在相关数据集的实验表明利用梯度下降法的 s v m r f e 的特征选择改进算法( g a d s v m r f e ) 具有优越的分类性能。 最后将改进算法( g a d s v m r f e ) 应用于真实医疗数据( 鼻咽癌、淋巴瘤数 据，由中山医学院肿瘤防治中心提供) 上，达到预期的效果。各项实验结果显示 3 中山大学硕士学位论文 表明本文所使用的算法具有一定的实用价值和应用前景。 1 4 本文内容安排 本文的主体主要分为以下六个部分： 第一部分为绪论，介绍了特征选择算法的研究背景和意义，综述了特征选择 算法国内外研究现状和各个特征选择算法的分支特点；最后列出了本文的主要研 究内容、工作及全文的组织结构。 第二部分为数据挖掘相关的概念及理论，介绍了数据挖掘的基本定义、过程 及其功能，并概述了特征选择方法；然后研究了统计学习相关理论知识；最后重 点分析和总结了支持向量机怎样在基于统计学习理论中应用结构最小化的原则 得到泛化能力较强的分类超平面的过程。 第三部分为基于s v m r f e 的特征选择算法的研究，讨论了基于s v m r f e 的特征选择算法工作机制和在高维训练集中s v m r f e 时间复杂度偏高效率低下 及不能剔除冗余特征的缺陷。然后提出相关解决策略和方法，最后用实验进行不 同的数据集分析和比较。 第四部分为基于s v m r y e 的特征选择改进算法研究，先介绍了w e s t o n 特 征选择算法d 6 的原理并因此利用类似的思路改进s v m r f e 的特征选择算法，并 利用w e s t o n 文献中的数据集分别对其进行实验比较和分析；得到利用梯度下降 法的s v m r f e 的特征选择改进算法( g a d s v m r f e ) 口- i 以作为特征选择中的 w r a p p e r 方法，从而挑选出更具有重要意义的特征并优越的时间性能。 第五部分为改进的特征选择算法( g a d s v m r f e ) 在生物医学中的应用研 究，在生物医学基因数据的分析和处理中，挑选出能判别分析肿瘤疾病的信息基 因组。然后进一步进行定量实时p c r 实验分析，最后将得到的实验效果进行相 应文献研究成果的比较。证明本文利用的特征选择算法( g a d s v m r f e ) 在生物 医学上的应用价值。 第六部分为结论及进一步研究方向，总结了本文的研究思路、工作及其相关 实验效果。并进一步展望了基于s v m 的特征选择算法研究方向。 4 第二章数据挖掘相关的概念及理论 数据挖掘( d a t a m i n i n g ) ，又称为数据库中的知识发现( k n o w l e d g e d i s c o v e r y i nd a t a b a s e ，k d d ) ，就是从大量数据中获取有效的、新颖的、潜在有用的、最 终可理解的模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取寅挖 掘”知识。知识发现过程由以下步骤的迭代序列组成u i a w e ih a n m i e h e l i n e k a m b e r ，d a t a m i n i n g c o n c e p t sa n d t e c h n i q u e s ，s e c o n d e d i t i o n ) 1 7 1 ： 豆 * # 目示，岔矗。 数据挖* ( l 、， 圉2 - 1 数据挖掘在知识发现过程中的步骤 现代信息社会中存在海量模糊数据和大量不确定性问题，促使数据挖掘的理 论、方法和技术的不断发展，传统的数据分析技术往往无法满足对大量地指数级 规模不断增长复杂数据的处理，这就引发了数据挖掘的研宄。数据挖掘涉及多学 科的交叉集成，包括模式识别、人工智能、机器学习、神经网络、信息检索、统 计学、图像与信号处理、数据库及其数据仓库技术。 数据挖掘是从数据库、数据仓库、万维网或其它信息存储库中提取或发现有 趣数据模型或有用知识并将其以人们能够理解的方式展示的过程，即： 中山大学硕士学位论文 ( 1 ) 特征化和区分一汇总目标类数据的一般特征或特性 ( 2 ) 分类预测一通过训练集建立数据类或概念的分类模型，并能使用这个 模型对未知标号的样本进行分类和预测。 ( 3 ) 关联和相关一挖掘频繁模式，从而发现数据中有趣的关系和联系。 ( 4 ) 聚类分析一根据相似性度量将数据对象聚成相似对象的类的过程，使 得最大化簇内对象的相似性，而最小化簇间对象的相似性。 ( 5 ) 演变分析一描述数据对象随时间变化的趋势或规律，并对其进行建模 处理。 2 1 特征选择方法概述 本节主要是介绍了特征选择方法的定义、步骤及其相关的基本要素，并进一 步介绍了特征选择方法和学习算法的结合方式。 2 1 1 特征选择方法定义 特征选择在机器学习、统计学或者数据挖掘中又称之为属性选择，特征减少， 变量选择或者变量子集选择，是为了构建更好学习模型而进行选择与分类或任务 相关特征子集的技术：应用于包括分类、回归、聚类和时间序列预测的监督或无 监督学习任务中，能够减少不相关或冗余的特征数，从而很有效地降低学习算法 的时间复杂度和提高其泛化性能，并且有助于现实分类模型的理解。但数据降维 中的特征提取与特征选择的术语是有区别，其主要区别如下( 边肇祺和张学工， 2 0 0 0 ) t 1 8 】： 特征提取高维空间中的样本，通过某种形式的变换( 或映射) 将原测量空 间映射到低维空间中的特征空间的过程就叫做特征提取，其中映射后的特征叫二 次特征，它们是原始特征的某些组合( 通常是线性组合) ，这种映射方法的一个 缺点是没有舍弃任何一个原始输入特征。所谓特征提取在广义上又是一种变换。 若a 是测量空间，b 是特征空间，则变换f ：a - b 就叫特征提取器。这些用于从 高维空间的样本映射到低维空间的降维技术包括主成分分析( p r i n c i p a l c o m p o n e n t sa n a l y s i s ) ，独立成分分析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ) ，非线性降 6 第二章数据挖掘相关的概念及理论 维( n o n l i n e a rd i m e n s i o n a l i t yr e d u c t i o n ) ，多因素降维( m u l t i f a c t o rd i m e n s i o n a l i t y r e d u c t i o n ) 等等。 特征选择从原始特征中挑选出符合某种评价准则的最优特征子集以达到 降低特征空间维数的目的，这过程就叫做特征选择。 2 1 2 特征选择方法的步骤及基本要素 从数据集d 中的n 个不同特征中选择p 个特征，穷尽列举全部特征子集， 其所有的组合方式可以用以下公式计算：言睇= 言瓦若当数据集。中 的维数( 即特征数目) 过于庞大时，会引起计算和存储数据依赖于维数呈指数增 长趋势导致所谓维数灾难( c u r s eo f d i m e n s i o n a l i t y ) 等问题，并且当训练样本固 定数目时，分类模型的性能通常会由于大量特征数目而降低。通常特征选择算法 由以下四个步骤组成：特征子集产生，特征子集评估，停止准则，结果验i 正( d a s h & l i u ，1 9 9 7 ) t 1 9 1 。 图2 - 2 典型特征选择算法的四个步骤 特征子集产生过程与搜索方向： 特征子集产生首先产生搜索起点，其中有两种完全相反的搜索方向。第一种 是从自下而上的前进搜索方法，搜索的起始点是为空集的特征子集，基于某种评 估准则每次从未选取的特征集中挑选出最好的特征加入，直到特征子集包含所有 的特征或者达到停止准则；另一种恰好相反，是一种自上而下的后退搜索方法。 其搜索的起始点是所有的特征，基于某种评估准则去除最无关的特征，直到特征 7 中山大学硕士学位论文 子集只剩下一个特征或者达到停止准则。另外还有一种是随机产生搜索的起始 点，然后随机加入或剔除特征的方法以避免产生局部最优情况的发生。 1 1 。一 一一刊 图2 3 包含4 个特征的二进制搜索空同的偏序状态图 ( 黑方体代表选中的特征，从左到右表示特征选择搜索过程) 搜索策略： 特征选择算法确认了搜索方向后就开始执行对应的搜索策略，一般认为有三 种不同的搜索策略即：完全式搜索、启发式搜索和随机( 非确定性) 搜索。 完全式搜索是穷尽所有可能的最优特征子集，在小规模特征数时是可行的， 算法的时间复杂度随着特征数的增加呈指数级增长而不切实际。但是在某些条件 下比如假设评估准则函数满足单调性以( 4 ) 以( 4 ，4 ) 厶( 4 ，a 。) ，其中 ( a i ，彳一) 是原始特征集为了获得最优子集数而剔除的特征，这样就可以根据 这个性质评估准则函数不需要对所有的特征子集进行分支限界法的计算 ( n a r e n d r a & f u k u n a g a ，1 9 7 7 ) 。但在现实应用中，评估准则函数往往不具备单 调性，而且这种算法的时间复杂度仍然很高o ( 2 甩) 难以实现。 启发式搜索是用启发式进行搜索的算法，以避免盲目穷举所有的特征子集但 同时可能失去最优的特征子集；启发式搜索算法时间复杂度为o ( n 2 ) ，因此运行 速度快并且容易实现。常用的启发式搜索算法有单独最优特征组合、顺序前进法 ( s e q u e n t i a lf o r w a r ds e l e c t i o n ，s f s ) 、顺序后退法( s e q u e n t i a lb a c k w a r ds e l e c t i o n ， s b s ) 、增l 减r 法( 1 - r 法) 、t a b u 搜索算法等。 随机( 非确定性) 搜索与前面的两种搜索方法不同，完全随机或者基于概率 3 第二章数据挖掘相关的概念及理论 地进行下一步的搜索并且可以通过设置最大迭代次数减少搜索空间。这类算法有 模拟退火算法、遗传算法、拉斯维加斯过滤器( l 弱v e g a sf i l t e r ) 等，这类算法通 过设置适当参数来得到最优特征子集。因此如何产生出有效参数是引起人们的关 注。 2 1 3 特征选择方法和学习算法的结合方式 根据相关的评价准则最优的特征子集跟评价标准是密切相关的，不同的评价 标准往往导致不同的最优特征子集。根据在选择最优的特征子集上采用学习算法 和评价准则的依赖关系，可以将特征选择方法分为f i l t e r ( 过滤) 、w r a p p e r ( 封 装) 和e m b e d d e d ( 嵌入) 三种方法( g u y o n & e l i s s e e f f , 2 0 0 3 ；n e u m a n ne ta 1 ， 2 0 0 5 ) 1 1 1 【2 1 】。其中第一种方法过滤是在评价选择最优特征子集的处理过程中不涉 及学习算法，这种独立与学习算法的评价标准有距离度量( d i s t a n c em e a s u r e s ) 、 信息度量( i n f o r m a t i o nm e a s u r e s ) 、相关度量( c o r r e l a t i o nm e a s u r e s ) 、一致性度量 ( c o n s i s t e n c ym e a s u r e s ) 等；第二种方法封装是最优特征子集的选择取决于其作为 候选特征子集在后续分类器性能作为评价标准，一般这种算法准确率高但计算量 较大；而嵌入式方法是指特征选择的过程中完全结合在分类学习算法具体结构 中，一般地相比过滤式和封装式方法，嵌入式方法在特征选择上具有较好地优越 性能但计算量较大( g u y o ne ta 1 ，2 0 0 6 b ) 1 2 2 1 。 过滤式方法在学习算法之前作为解决特征空间维数和过分拟合问题的预处 理，可应用于生物医学的基因微阵列数据样本相对于基因少的情况；相对而言比 封装式方法运行算法要快得多。但过滤式方法主要的缺点是没有考虑后续的学习 算法对己选定的特征子集的评价，因此相对于封装式方法分类精度要差。比较有 名的过滤方法有皮尔森相关系数( p e a r s o nc o r r e l a t i o nc o e f f i c i e n t s ) 方法。 距离度量( d i s t a n c em e a s u r e s ) 的4 种形式： ( 1 ) 欧氏( e u c l i d e 锄) 距离 d c z ，少) ：i i x - y l y l = ( 喜c 一一乃，z ) 必 ( 2 )d ( ”) = = i ( 一一乃) 2i ( 2 - 1 ) j i l 9 中山大学硕士学位论文 曼哈顿( m a n h a t t a n ) 疆离 d ( x ，们= yx , 一y | ( 3 ) 闵可夫斯基( m i n k o w s k i ) 距离 d c x ，y ，：( 喜i x ，一j ，i ， ( 4 ) 相关( c o r r e l a t i o n ) 系数度量 ( 2 2 ) ( 2 3 ) ( 薯一乃( 乃一乃 烈而力2 蓐丽 q q 其中i 是x 的平均值，万是y 的平均值；d ( x ，y ) 的值在1 和1 之间，如果x 和y 完全相关，则d ( x ，力的值等于l 或1 ，反正完全不相关，则等于0 。 蛤、a 】目口肚：c l 特征选择搜索算法 已选特征子舅暮 l o 学习算法i l i 训练集 候选特征子集j r 性能评估 特征评估模块 图2 - 4 过滤式( f i l t e r ) 特征选择方法 w r a p p e rm e t h o d s 是通过学习算法评价待选的特征子集的准确性来进行特征 选择，因此常常跟特定的学习算法结合起来，算法的准确性往往比f i l t e rm e t h o d s 要高( k o h a v i ，1 9 9 5 ) t 2 3 1 ，但计算开销也比较大。根据最终的评判标准选择最好的 特征子集，每个待候选的特征用于尝试解决的问题。 l o 第二章数据挖掘相关的概念及理论 2 2 统计学习理论 图2 - 5w r a p p e r 特征选择方法 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 有归纳推理和转导推理两种不同类 型的推理，传统的推理方法一般是归纳一演绎，即解决某个具体的问题时首先得 到有关问题更一般的规则，再从这个更普遍的规则推理出这个具体实际问题，也 就是说解决思路是首先特殊到一般，然后再从一般到特殊这样的过程。v a p n i k 根据o c c a m 剃刀原则的哲理思想在统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ) 2 4 1 中提出支持向量机可以利用选择推理的方法直接从特殊到特殊的求解过程，解决 了推理求解过程中的不适定问题。 根据给定的独立同分布( i i d ，i n d e p e n d e n t l yd r a w na n di d e n t i c a l l yd i s t r i b u t e d ) 训练集为t = ( 两，y 3 ，( 屯，) ，( 而，乃) ) i x y y ，其中输入对象t 彤，输出标 签y j r ，f = 1 ，2 ，。假设这些数据中存在未知概率分布e ( x ，y ) ，对于每个输 入毛，希望能够利用训练样本得到一个映射五h 咒，也即得到一个分类器：决 策函数y = 八工，口) ) - 1 ，1 ) 其中决策函数厂用参数a 来进行调整，可以从中 一组超平面中选择需要的分类模型：f ( x ， w ，6 ) ) = s i g n ( w x + b ) 。而参数口的调 整是通过以下分类模型厂在训练集中分类效果很好的函数得出的。 中山大学硕士学位论文 预测输出y 图2 - 6 机器学习识别过程 因此从分类模型可以得到期望风险函数： r ( 口) = ，丢l 少一( x ，口) l 卯( 墨y ) ( 2 - 5 ) 其中尸( x ，j ，) 为x 和y 联合概率分布函数，联合概率分布函数尸( 工，y ) 可以表 示成类先验概率密度和类条件概率密度之积：尸( x ，y ) = p ( x ) p ( ylx ) ，当概率密 度p ( x ，y ) 存在时，d p ( x , y ) = p ( x ，y ) a x d y 。但是期望风险函数计算依赖于联合概 率分布函数p ( x ，y ) ，而实际机器学习应用过程中只知有限训练样本丁的存在， 因此期望风险函数r ) 也就不能直接计算。所以寻求这样一个函数 ) ：当 ，个训练样本趋向于无穷大时，函数 ) 与期望风险函数尺 ) 都依概率收敛 于其真实风险的下确界尺+ ) ，即所谓的经验风险学习过程的一致性( c o n s i s t e n c ” 是满足如下条件的： r 唧( 口) 。专r ( a 。) ( 2 - 6 ) ，_ r ( a ) r ( 口。) ( 2 7 ) i - - 其中尺他。) = 瓣r + ) ，口q 可以用来表示任意的函数集。 1 2 第二章数据挖掘相关的概念及理论 。) 根据概率论与数理统计的相关大数定理，可以用下列公式替代期望风险函 经验风险( 班蔫盯( 咄咒) ( 2 8 ) z ( y ，多) ： 1 矿yy，、(29) 【0 ， fy = y 其中为0 1 损失函数，即对类别标号y 进行预测时所造成的损失( 代价) ， 依实际情况具有不同的损失函数。 给定一个参数刁( 0 叩1 ) ，( v a p n i k & c h e r v o n e n k i s ，1 9 9 5 ) t 2 5 】证明了最小化 经验风险泛函灭 ) 依1 - 1 7 满足下列不等式： r ( a ) 墨唧( a ) + 其中不等式右边的 ) 为经验风险，西( 三) ： ，l ( 2 - l o ) 为置 信范围( c o n f i d e n e ei n t e r v a l ) ，两者之间的关系可如下面图2 - 8 形象地表示( e t h e m a l p a y d i n ，2 0 0 4 ) 1 2 6 1 ，h 为函数集 厂( 五口) ) 的v c 维( v a p n i k - c h e r v o n e n k i s 中山大学硕士学位论文 d i m e n s i o n ) ，是