（管理科学与工程专业论文）一种数据挖掘中的特征子集选取模型研究和应用.pdf

硕士学位论文 m a s t e r st i i e s i s f l r il li rlili r lli i i iiif 18 9 7 9 6 6 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：袭淆 日期：砂“年岁月2 - 7 日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：获铱 日期：护1 1 年罗月日 导师张c i 寞磊等 日期：加1 1 年，月。) 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程 中的 规定享受相关权益。回童途塞握銮卮溢唇! 旦堂生；旦二生；旦三生蕉查! 作者签名：劢。钎 日期：刈年f 月叩日 导师签名 日期：珈 辱叼 吨1 7 磊朋 乞干 门年 硕士学位论文 m a s t e r st h e s i s 摘要 特征提取是模式识别中的一个重要过程，如今，也在数据挖掘领域也有着广泛 的应用。对于高维数据的数据挖掘，特征提取可以有效地对数据进行降维处理，从 而降低算法的运算规模。相对于主成分分析，粗糙集等数据降维方法，特征提取更 加系统化，也更加依赖与问题的具体应用领域，提出针对性的特征提取模型，得到 的结果也更加具有参考价值。将支持向量机应用于特征提取中，可以结合两者的长 处，优化特征提取的过程，是对特征提取方法的一种探索。 本文针对最优特征子集选取的问题，进行了相关的探索研究。借鉴经典统计理 论中的分位数的概念，将其引入特征选取模型，建立了分位数特征选取模型。另外， 参考信息学中关于信息相对熵的概念和定义，建立了相对熵特征选取模型。在对特 征候选集进行最优特征子集选取的过程中，本文依照分位数特征选取模型和相对熵 特征选取模型分别建立了样本属性的可分性判别函数，并运用浮动序列前进算法找 出不同属性个数下的最佳特征候选子集。最后，本文又借助于支持向量机的方法， 将包含不同属性个数的特征候选子集对应的数据放入支持向量机，学习后进行判 断，根据最后识别的错误率来判断该特征候选子集的优劣程度，从而得到最优特征 子集。另外，通过在结肠癌患病和正常样本基因表达水平数据集上进行实验，来对 上述特征提取模型进行了验证。 本文将特征提取应用于数据挖掘领域中，所建立的特征提取模型依据样本的统 计学特性以及信息学特性，这些模型的建立脱离了系统的具体应用领域，使其更具 有普遍意义。 关键词：分位数模型；相对熵模型；支持向量机：特征提取；数据挖掘 硕士学位论文 m a s t e r st h e s i s a b s t r a c t f e a t u r ee x t r a c t i o ni sa ni m p o r t a n tp r o c e s si np a t t e r nr e c o g n i t i o n ，a n dn o w ，i ta l s o h a saw i d er a n g eo fa p p l i c a t i o n si nt h ef i e l do fd a t am i n i n g f o rt h eh i g h d i m e n s i o nd a t a ， f e a t u r ee x t r a c t i o nc a ne f f e c t i v e l yr e d u c et h ed i m e n s i o n so ft h ed a t aa n dt h es i z eo ft h e a l g o r i t h m c o m p a r e t ot h e p r i n c i p a lc o m p o n e n ta n a l y s i s ，r o u g h s e t sa n do t h e r d a t a d i m e n s i o nr e d u c t i o nm e t h o d s ，f e a t u r ee x t r a c t i o ni sm o r es y s t e m a t i c , a n da l s om o r e d e p e n d e n to ns p e c i f i ca p p l i c a t i o n s ，b a s e do na b o v e ，t h er e s u l t sh a v em o r er e f e r e n c ev a l u e s u p p o r tv e c t o rm a c h i n eh a sa p p l i e dt of e a t u r ee x t r a c t i o n ，y o uc a nc o m b i n et h es t r e n g t h s o fb o t ht oo p t i m i z et h ep r o c e s so ff e a t u r ee x t r a c t i o n ，a n di ti sa ne x p l o r a t i o ni nf e a t u r e e x t r a c t i o nf i e l d i nt h i sp a p e r , w ea r em a k i n gs o m ee x p l o r a t i o na n dr e s e a r c ho nt h ep r o b l e mo fm o s t o p t i m a lf e a t u r es u b s e ts e l e c t i o n r e f e r e n c et h ec o n c e p to ft h eq u a r t i l ei nt h ec l a s s i c a l s t a t i s t i c a lt h e o r y ，w ei n t r o d u c ei n t ot h ef e a t u r es e l e c t i o nm o d e le s t a b l i s h e d w h a t sm o r e ， w ee s t a b l i s h e da n o t h e rf e a t u r es e l e c t i o nm o d e lb a s e do nt h ec o n c e p to fr e l a t i v ee n t r o p y i nt h ei n f o r m a t i o nt h e o r y i nt h ep r o c e s so fs e l e c t i n gt h em o s to p t i m a lc a n d i d a t es e to f f e a t u r e s ，t h i sf e a t u r es e l e c t i o nw a si na c c o r d a n c ew i t hq u a r t i l e sm o d e la n dt h er e l a t i v e e n t r o p yf e a t u r es e l e c t i o nm o d e l ，a n de s t a b l i s h e dt h ed i s c r i m i n a n tf u n c t i o n t ot h en e x t ， t of i n ds e q u e n c en u m b e ro fa t t r i b u t e su n d e rd i f f e r e n tc a n d i d a t es u b s e to ft h eb e s tf e a t u r e s m a k i n gu s eo ff l o a t i n gf o r w a r da l g o r i t h m f i n a l l y ，s u p p o r tv e c t o rm a c h i n em e t h o d w a s u s e dt om a k es u r et h en u m b e ro fd i f f e r e n tp r o p e r t i e sw h i c hi n c l u d i n gi nt h e c h a r a c t e r i s t i c so ft h ec a n d i d a t es u b s e t b yl e a r n i n gt om a k et h ej u d g m e n t ，a c c o r d i n gt o t h ee r r o rr e c o g n i t i o nr a t ew ed e t e r m i n et h es u b s e to ft h ef e a t u r e so fc a n d i d a t e i na d d i t i o n ， t a k ea ne x p e r i m e n to ni l l n e s sa n dn o r m a ls a m p l e si nc o l o nc a n c e rg e n ee x p r e s s i o nd a t a s e t st om a k es u r et h a tt h ef e a t u r ee x t r a c t i o nm o d e li sv a l i d a t e d t h i sp a p e rb r i n g st h ef e a t u r ee x t r a c t i o ni n t ot h ef i e l do fd a t am i n i n g f e a t u r e e x t r a c t i o nm o d e li se s t a b l i s h e db a s e do nt h es t a t i s t i c a lp r o p e r t i e so ft h es a m p l ea n d i n f o r m a t i o ns c i e n c e t h em o d e li sf a ra w a yf r o mt h ef i e l do fs p e c i f i ca p p l i c a t i o n s ，a n d m a k i n gi tm o r e u n i v e r s a l k e yw o r d s ：q u a r t i l em o d e l ；r e l a t i v e e n t r o p ym o d e l ；s u p p o r tv e c t o rm a c h i n e ； f e a t u r ee x t r a c t i o n ；d a t am i n i n g 1 1 _ ： 硕士学位论丈 m a s t e r st h e s i s 摘要 目录 i a b s t r a c t ” 1 绪论”“ l 1 1 课题的研究背景1 1 2 研究意义2 1 3 国内外研究现状3 1 4 本文的工作及组织结构5 2 基础理论概述 7 2 1 数据挖掘7 2 2 特征提取7 2 3 统计学习理论8 2 3 1 经验风险最小化8 2 3 2 结构风险最小化9 2 4 支持向量机理论“1 0 2 4 1 支持向量机基础1 0 2 4 2 线性分类器1 1 2 4 3 非线性分类器1 3 2 4 4 核函数1 3 2 5 本章小结”：1 5 3 分位数及相对熵特征提取模型及应用” 1 6 3 1 分位数特征提取模型1 6 3 1 1 分位数的概念1 6 3 1 2 分位数特征提取模型1 7 3 2 相对熵特征提取模型1 9 3 2 1 相对熵的概念1 9 3 2 2 相对熵特征提取模型”2 0 3 3 特征提取模型的应用2 1 硕士学位论文 m a s t e r st h e s i s 3 3 1 数据采集2 1 3 3 2 数据预处理一2 1 3 3 3 分位数及相对熵特征提取模型2 3 3 3 4 模型求解”2 5 3 4 本章小结“2 7 4 支持向量机特征提取优化模型及应用2 8 4 1 支持向量机特征提取优化模型2 8 4 1 1 模型总体思路2 8 4 1 2 确定判别函数2 9 4 2 浮动序列前进算法3 0 4 3 支持向量机优化3 l 4 4 模型的应用”3 2 4 5 本章小结一3 5 5 总结和展望 “”“3 6 5 1 本文的总结- 3 6 5 2 下一步的研究工作3 7 参考文献 参考文献 致 “”3 9 3 9 4 l 硕士学位论文 m a s t e r st h e s i s 1 1 课题的研究背景 1 绪论 人类从实践中进行总结和学习的能力是人类智慧的一个集中体现。人们通过对 已有事实的总结和分析，得到关于该事实进行判断和解决问题的规律，从而为以后 类似的事实进行预测提供参考。将人工智能转化为机器智能，利用计算机来模拟人 类的这种学习能力，使计算机也可以具有不同程度的智能判断，而不仅仅是靠人工 输入计算指令进行计算的工具。机器学习是现今计算机领域的一个重要研究方面。 机器学习的实现主要可以分为这样三种：以经典的统计理论为基础的机器学 习，基于经验风险最小化理论的神经网络的方法以及基于统计学习理论的机器学习 的方法。 以经典的统计理论为基础的机器学习，借鉴了经典统计理论中参数估计的思 想，其参数形式是预先定义好的，然后利用训练样本来对参数值进行估计，从而得 到确定的函数形式，再对测试样本进行测试。这种方法虽然理论基础比较完备，但 是对样本的要求较为严格，它需要预先知道样本的分布形式，参数形式也需要预先 设定。另外，经典的统计理论中的参数估计是以大数定律为理论基础的。经典的统 计分析要求样本点的数目足够多，而且要求先假设样本服从某一具体的分布函数， 然后依据大数定律，利用样本数据的统计特性对分布中的参数进行估计，从而达到 定量分析的目的。但是，这种参数估计的方法随着数据维数的增加，对样本点数目 的要求呈指数增长。对于样本数量小的数据集，基于大样本点的传统的统计分析无 法直接发挥作用。而小样本数据集上的数据挖掘，也使得很多机器学习方法不具备 显著意义。 人工神经网络的方法以经验风险最小化为目标，这会导致过学习的情况出现。 由于其经验风险最小化的要求，会得到在训练样本上的错误识别率很低，但是在测 试样本上的错误识别率却较高。过学习的出现使得该方法在推广能力上受到限制。 统计学习理论是从传统的统计理论发展而来，它集中研究在有限样本下的机器 学习，并建立了一套适用于有限样本统计学习问题的理论体系。统计学习理论提出 了与经验风险最小化不同的结构风险最小化理论，并以此为基础，提出了支持向量 机的方法理论。 。元吕安，邓松，李文敬等数据挖掘原理与s p s sc l e m e n t i n e 应用宝典【m 1 北京：电子工业出版社，2 0 0 9 ：3 1 1 3 3 1 1 彳7 、 硕士学位论文 m a s t e r st h e s i s 结构风险最小化“旨在针对经验风险和置信范围这两项最小化风险泛函。”它 有效地解决了经验风险最小化下的过学习问题。支持向量机理论以结构风险最小化 为目标，在解决小样本，高维度以及非线性等复杂数据的数据挖掘以及模式识别领 域具有着突出的优势。 支持向量机针对小样本数据，依据结构风险最小化，得n d , 样本下的最有解， 而不是假设样本数目趋于无穷大时的最优解。该方法在解决非线性的问题上，通过 核函数的概念，将输入空间中的低维数据转换至高维空间中，并且可以直接在低维 空间中进行计算，无需关注函数的具体转换形式，巧妙地解决了维数灾难的问题。 该方法最终将分类问题转换为一个优化问题进行求解，理论上说，得到的将是全局 最优解，解决了在神经网络方法中无法避免的局部极值问题。 虽然统计学习理论和支持向量机方法中尚有很多问题需要进一步研究，但很多 学者认为，它们正在成为继模式识别和神经网络研究之后机器学习领域新的研究热 点，并将推动机器学习理论和技术取得重大地发展。 特征提取是模式识别中的一个重要过程，如今，也在数据挖掘领域也有着广泛 的应用。对于高维数据的数据挖掘，特征提取可以有效地对数据进行降维处理，从 而降低算法的运算规模。相对于主成分分析，粗糙集等数据降维方法，特征提取更 加系统化，也更加依赖与问题的具体应用领域，提出针对性的特征提取模型，得到 的结果也更加具有参考价值。将支持向量机应用于特征提取中，可以结合两者的长 处，优化特征提取的过程，是对特征提取方法的一种探索。 1 2 研究意义 本文针对最优特征子集选取的问题，进行了相关的探索研究。借鉴经典统计理 论中的分位数的概念，将其引入特征选取模型，建立了分位数特征选取模型。另外， 参考信息学中关于信息相对熵的概念和定义，建立了相对熵特征选取模型。这两个 特征模型的建立，丰富了特征提取的方法，拓宽了特征提取方法的思考角度。 在对特征候选集进行最优特征子集选取的过程中，本文依照分位数特征选取模 型和相对熵特征选取模型分别建立了样本属性的可分性判别函数，并运用浮动序列 前进算法找出不同属性个数下的最佳特征候选子集。最后，本文又借助于支持向量 机的方法，将包含不同属性个数的特征候选子集对应的数据放入支持向量机，学习 后进行判断，根据最后识别的错误率来判断该特征候选子集的优劣程度，从而得到 。v l a d i m i rn v a p n i k 著张学t 译统计学习理论的本质 m i 北京：清华大学 n 版社，2 0 0 8 ：6 4 2 硕士学位论文 m a s t e r st h e s i s 最优特征子集。 在对候选特征子集优化方面，本文应用了支持向量机的方法。支持向量机的方 法最初用于样本分类，后来也被应用于回归和预测。支持向量机在样本分类方面有 着独特的优势，它作为一种有监督的学习过程，在对复杂的非线性分类问题方面有 着出色的表现能力。该方法的核心思想是将原始数据通过特定的函数转换至高维空 间，从而实现在高维空间中的线性可分，巧妙地将非线性的分类问题转换位线性的 分类问题，并且由于核函数的引入，使得可以不必关心具体的函数映射关系，所有 的计算都将直接在原始的低维输入空间上进行，这就避免了经典统计理论面对复杂 数据上可能遇到的维数灾难的问题。 特征提取是模式识别中的重要步骤，面对复杂系统的特征提取，往往特征提取 的方法以及模型建立都与系统的具体领域有关。本文将特征提取应用于数据挖掘领 域中，所建立的特征提取模型依据样本的统计学特性以及信息学特性，这些模型的 建立脱离了系统的具体应用领域，使其更具有普遍意义。 本文应用支持向量机的方法对候选特征子集进行优化，对支持向量机的研究和 应用有着以下作用和意义： 对于具有高维属性的样本分类问题，传统的聚类方法在解决实际问题中显得过 于粗糙。本文针对该类数据的特点( 样本属性数目多) ，提出分步进行特征提取的 办法，首先对属性进行初步的筛选，对包含分类信息量少，分类能力弱的属性进行 剔除，建立特征候选集。接下来对特征候选集中的属性进行组合，找出不同属性个 数下的特征候选子集，最后再从这些特征候选子集中找出最优特征集合。这些步骤 提高了特征选取的科学性，对特征选取以及后续的分类工作具有实际指导意义。 结肠癌患病特征基因识别，不但为结肠癌的患病诊断提供了依据，简化了诊断 的实验分析，也为结肠癌的患病病理研究以及抗癌药物的研制提供了参考价值。同 时，也为生物医学研究人员提供了致癌基因的参考知识，便于据此进行有针对性的 生物学实验，结合生物学的背景知识，发现基因之间的关联模式以及相互影响。 1 3 国内外研究现状 数据挖掘技术是从数据库技术发展演变而来，2 0 世纪8 0 年代后期以来，数据 库技术的快速发展以及当今社会数据丰富，信息贫乏的状况，直接推动了数据挖掘 技术的发展。 韩家炜在其著作数据挖掘：概念与技术一书中指出：“数据挖掘是从存放 3 硕士学位论文 m a s t e r st h e s i s 在数据库，数据仓库或其他信息库中的大量数据中发现有趣知识的过程。数据 挖掘的研究及应用主要分为以下几个方面： ( 1 ) 数据仓库与o l a p 。这一领域主要研究数据仓库以及o l a p 系统的架构 和实现。当前的研究重点主要包括数据仓库中多维数据模型，数据立方体的构建， 数据在数据仓库中的泛化，以及o l a p 中索引的建立等方面。 ( 2 ) 数据挖掘与知识发现。这一领域是数据挖掘的热门领域，主要研究数据 挖掘技术的基础理论和方法。例如泛化，分类，关联，聚类，频繁模式和结构化模 式分析，离群点分析，趋势和偏差分析等都是数据挖掘中常用的技术和方法。它们 是数据挖掘系统中数据挖掘引擎所关注的内容。 ( 3 ) 数据挖掘在各领域的应用研究，主要研究数据挖掘在具体领域里的应用。 例如流数据挖掘，主要研究流数据以及时间序列数据的数据挖掘：生物信息数据挖 掘，主要关注生物基因表达里的数据挖掘；文本挖掘，主要研究大规模文本中的知 识挖掘；w e b 挖掘，是当今数据挖掘应用中的热点，研究w e b 上的页面结构，页面 间的链接结构，w e b 上的多媒体数据挖掘以及w e b 文档的自动分类等方面；入侵检 测，主要研究数据挖掘在信息安全方面的应用。 特征提取是模式识别中的一个重要过程，也常常用于数据挖掘中的数据处理过 程中。特征提取通常用于特征空间维数过高的数据，通过特征提取以降低特征空间 的维数。特征提取的研究始于2 0 世纪6 0 年代，进入2 0 世纪9 0 年代以来，随着大 规模，高维度复杂数据的大量出现，特征提取的研究进入了一个新的阶段。 目前主要的特征提取算法包括最优化方法，启发式算法以及随机搜索方法等。 其中，最优化方法也称暴力搜索算法，采用穷尽的方式寻找全局最优解。启发式算 法包括序列前进算法以及序列后退算法。序列前进算法的主要思路是从一个空集或 者包含一个或两个特征的属性集合开始，依据评价标准从特征候选集中选择一个分 类能力最强的特征加入该初始属性集，直到满足预先设定的停止条件。序列后退算 法与序列前进算法相反，其初始特征集合即为特征候选集，然后依据评价标准从中 删除一个分类能力最弱的特征，直到满足预先设定的停止条件圆。本文中即采用序 列前进算法。随机搜索算法通常采用概率或者抽样处理的方法，遗传算法是其典型 代表。 特征提取中的子集评价方法也是特征提取的一个重要研究方面。目前常用的评 价方法有基于距离的方法，基于信息的方法以及基于独立性的方法等。其中，基于 。j i a w e ih a n ，m i c h e l i n ek a m b e r 著范明，孟小峰译数据挖掘：概念与技术( 第二版) 【m 】北京：机械工业出版 社，2 0 0 8 ：5 。卜华龙，夏静，韩俊波特征选择算法综述及进展研究【j 】巢湖学院学报，2 0 0 8 ，1 0 卷6 舅j 1 ：4 1 - 4 4 4 ，f = 、 一， 硕士学位论文 m a s t e r st h e s i s 距离的方法主要采用欧氏距离，马氏距离以及巴氏距离等，基于信息的方法主要应 用信息学中信息熵的方法，而基于独立性的方法则主要通过验证两个特征之间的相 关程度来实现。本文采用了前两种方法。 支持向量机是一类新型机器学习方法，由于其出色的学习性能和良好的泛化能 力，该技术己经成为机器学习的研究热点，并在众多领域如模式识别、数据挖掘、 回归估计和金融，生物，通信等领域得到很好的应用。 支持向量机最初用于样本分类，后来也用于回归和预测领域。将支持向量机与 其他方法相结合，是支持向量机研究的一个重要方面。主要的有支持向量机与小波 变换，粗糙集理论，模糊理论以及决策树等理论相结合以提高其判断和预测的准确 程度。另外，支持向量机中核函数的构造和参数的优化也是一个重要研究领域。 由于支持向量机在解决小样本、非线性、高维模式问题中具有突出的优势，支 持向量机在生物信息学等领域中也得到了广泛的应用，主要体现在特征提取和分类 识别两个方面： 特征提取主要是为了构造分类器的需要，由于高维数据的存在增加了问题的复 杂性，可能导致在高维空间构造的分类函数比在低维空间中构造的函数复杂的多， 而分类准确性并不一定能提高，而且有些特征之间具有较强的相关性，或者有的特 征与样本的分类是不相关，此外数据集中含有噪声数据，它的存在也影响着分类器 的分类性能。而支持向量机可以很好地解决数据的维数问题，并能同时不增加算法 的复杂度，这对于生物医学数据的小样本，高维数特性来说是个很好的解决办法。 支持向量机在某些疾病的亚型分类以及疾病预测方面也有着很好的应用。该方 法在两分类问题中的应用中，取得了较高的分类准确性。通过对特征基因的提取， 应用支持向量机方法对癌症的患病预测提供了较为准确的判断参考。 1 4 本文的工作及组织结构 本文针对最优特征子集选取的问题，建立了相关特征提取模型以及特征子集优 化模型。借鉴经典统计理论中的分位数的概念，将其引入特征选取模型，建立了分 位数特征选取模型。另外，参考信息学中关于信息相对熵的概念和定义，建立了相 对熵特征选取模型。在对特征候选集进行最优特征子集选取的过程中，本文依照分 位数特征选取模型和相对熵特征选取模型分别建立了样本属性的可分性判别函数， 。蒋琳基于支持向量机的特征提取方法及应用【d 】湖南大学，2 0 0 6 李泽，包雷，黄英武基于基渊表达谱的肿瘤分型和特征基因选取【j 1 生物物理学报，1 8 卷4 期：4 1 3 - 4 1 7 ，2 0 0 2 5 并运用浮动序列前进算法找出不同属性个数下的最佳特征候选子集。最后，本文又 借助于支持向量机的方法，将包含不同属性个数的特征候选子集对应的数据放入支 持向量机，学习后进行判断，根据最后识别的错误率来判断该特征候选子集的优劣 程度，从而得到最优特征子集。 在模型的应用方面，本文选取了一个公开的标准数据集一结肠癌患病样本和正常 样本的基因表达数据集来进行实验。应用文中建立的模型，对2 0 0 0 个基因进行筛 选，最终得到致癌基因集合。 本文的组织结构如下： 第一章：绪论。主要介绍本文的研究背景，研究意义，国内外研究现状以及本 文的工作。、 第二章：基础理论概述，主要介绍本文中所使用的基础理论，介绍了特征提取， 统计学习理论以及支持向量机理论。 第三章：分位数及相对熵特征提取模型及应用，主要介绍文中所建立的两种特 征提取模型：分位数模型以及相对熵模型，并在结肠癌患病与正常样本数据集上进 行了实验，利用上述两个模型从2 0 0 0 个基因中筛选出特征候选基因集。 第四章：支持向量机特征提取优化模型及应用，利用浮动序列前进算法和支持 向量机的方法对特征候选集中的特征进行组合筛选，最终得到最优特征子集。在选 取的数据集中进行实验，首先确定包含不同属性数的最优特征候选子集，然后利用 支持向量机的方法来确定最终的致癌基因集合。 第五章：总结与展望。对全文进行总结，并提出了下一步的研究方向和研究思 路。 6 一， 硕士学位论文 m a s t e r st h e s i s 2 1 数据挖掘 2 基础理论概述 数据挖掘从广义上来讲，是从存放在数据库，数据仓库或其他信息库中的大量 数据中发现有趣知识的过程，也可以认为是一个知识发现的过程。一个完整的数据 挖掘过程应当包括以下步骤： ( 1 ) 数据清理：消除噪声和不一致数据： ( 2 ) 数据集成：使得多种数据源可以组合在一起； ( 3 ) 数据选择：从数据库中提取与分析任务相关的数据； ( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作； ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式； ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 一般而言，数据挖掘任务可以分为描述性任务和预测性任务。描述性数据挖掘 任务描述数据库中数据的一般性质，而预测性数据挖掘任务对当前数据进行推断， 以做出预测。数据挖掘主要可以挖掘的模式类型：概念和类描述，关联规则以及频 繁模式挖掘，分类和预测，聚类分析，离群点分析以及演变分析等。而在数据挖掘 过程前期的数据预处理过程，主要包括数据清理，数据集成和变换，数据规约以及 数据离散化和数据的概念分层。 2 2 特征提取 特征选取是一项复杂的复合性工作，同时又与实际问题具有很高的相关性。特 征选择的任务是从一组数量为m 的特征中选择出数量为n ( n m ) 的一组最优特征， 以使这组最优特征在样本数据上具有最大的分类鉴别能力。为此需要进行两方面的 工作：一方面是选择标准的确立，即如何确定相关的特征可分性评价标准，从而依 据此标准选出可分性最大的特征组来。另一方面是要找个适当的算法，以便在允 。j i a w e ih a n ，m i c h e l i n ek a m b e r 著范明，孟小峰译数据挖掘：概念与技术( 第_ 二版) 【m 】| e 京：机械工业出版 社，2 0 0 8 ：3 5 ，3 0 3 3 7 硕士学位论文 m a s t e r st h e s i s 许的时间内找出最优的一组特征。特征选择的方法可分为筛选器和封装器方法。筛 选器技术在实际筛选之前预先估计互不相关的特征向量。 在实际应用中，筛选的方法是在已知训练数据的统计特性的情况下选取相关特征， 与学习算法无关，以可分性判据作为评价标准。封装器技术对于特征子集的选取标 准是与采用的学习算法相关，以学习得到的分类器性能作为对特征子集的评价标 准。学习算法往往需要在程序中反复执行，必然其时间复杂度会有所增加，但是得 到的最优特征子集在特定的学习算法上有较优的性能。 2 3 统计学习理论 统计学习理论是从传统的统计理论发展而来，它集中研究在有限样本下的机器 学习，并建立了一套适用于有限样本统计学习问题的理论体系。经典统计理论研究 的是样本数目趋于无穷大时的其统计特性的表现以及对统计参数的估计。但在实际 中，往往面临小样本数据的问题。这些小样本数据使得以大数定律为理论基础的经 典统计理论中的方法表现不尽如人意。而统计学习理论是针对小样本情况下的机器 学习理论，它依据经验风险以及置信度推测它的实际风险，称之为结构风险，以结 构风险最小化为目标建立算法，获得了较好的泛化能力。统计学习理论包括4 个部 分：学习过程一致性的理论，学习过程收敛速度的理论，控制学习过程泛化能力的 理论以及构造学习算法的理论。 2 3 1 经验风险最小化 实际系统是一个响应系统，其中存在一个未知形式的映射函数，机器学习的目 标就是通过模型训练求得一映射函数，使得其与实际系统映射的差别最小。可以定 义损失函数来描述学习机器产生的映射函数和实际系统映射之间的差别。称损失函 数在总体样本集上的数学期望为期望风险泛函，而损失函数在实际样本上的期望即 是经验风险。传统的机器学习方法直观地将经验风险作为期望风险的估计值，以经 验风险最小化( e r m ) 来近似期望风险泛函最小化。对于模式识别问题的损失函数 来说，训练样本错误率就是经验风险；对于函数逼近问题的损失函数来说，平方训 练误差就是经验风险；对于概率密度估计问题的损失函数来说，经验风险最小化准 则等价于最大似然法。但实际上，用e r m 原则代替最小化期望风险泛函，理论依 据并不充分，只是直观上合理的想当然做法而已，容易“过学习”( o v e r f i t t i n g ) ，如图 。卜华龙，夏静，韩俊波特征选择算法综述及进展研究川巢湖学院学报，2 0 0 8 ，1 0 卷6 ：4 1 - 4 4 8 硕士学位论文 m a s t e r st h e s i s 2 1 所示。 图2 1 a 欠学习 图2 1 b 适度学习 图2 1 c 过学习 2 3 2 结构风险最小化 经验风险最小化原则失败的一个典型例子就是神经网络的过学习问题，为解决 经验风险最小化的弊端，发展了机器学习的v c 理论。一般来说，学习机器能够产 生一个指示函数集，来实现对样本集合的分类。称样本集能够被指示函数集“打散”， 若指示函数集能够区分样本集合的所有可能分类情况。而指示函数集的v c 维即是 该指示函数集能够打散的最大样本数目。比如，已经证明n 维线性分类器的v c 维 就是n + l 。v c 维代表了学习机器的学习能力，然而，要具备较大的v c 维，即较高 的学习能力，必然要求学习机器足够复杂。如图2 2 所示，已经证明真实风险的界 由训练误差和置信区间两部分构成，e m r 法则就是片面追求较低的训练误差从而 o 导致过学习的。结构风险最小化就是通过适当降低学习机器的v c 维来简化学习机 器，同时在e r m 准则下进行学习的机制。而结构风险最小化原则( s r m ) 就是衡 量如何在训练误差和置信区间之间取得折中的法则。如图2 2 所示。 笾 区 函数集子集：s 1cs2 cs 3 v c 维：h 1 s h 2sh 3 图2 - 2 风险结构理论示意图 2 4 支持向量机理论 2 4 1 支持向量机基础 学习机器的构造方法直接决定了其遵循怎样的学习法则，支持向量机( s u p p o r t v e c t o rm a c h i n e ，s v m ) 就很好地实现了结构风险最小化原则。支持向量机首先构造出 一个函数集，使得其任意一个子集都能够取得最小的经验风险，然后再从中挑选出 适当的子集使得置信区间最小。 支持向量机早在1 9 6 3 年就被v a p n i k 领导的a t & t b e l l 实验室研究小组提出来 了，然而由于各方面的原因，知道九十年代由于统计学习理论的发展，才被广泛地 函元吕安，邓松，李文敬等数据挖掘原理与s p s s c l e m e n t i n e 应用宝典【m 】f l l , - q , , ：电子工业出版社，2 0 0 9 ：3 1 1 3 3 1 1 0 硕士学位论文 m a s t e r st h e s f s 重视起来。其良好的泛化能力使得在如手写字符识别、生物进化链分析、图像分类 等若干实际应用中提供了最佳的学习能力，并且几乎成为了在机器学习和数据挖掘 中的一种标准工具。 支持向量机通过寻找支持向量实现学习能力，结合各种技术发展出了线性分类 器、非线性分类器、支持向量分类机、支持向量回归机等众多有力的工具。下面， 简要介绍支持向量机在分类学习中的应用。 2 4 2 线性分类器 设给定的训练集为 k ，y ，) ，k ，y ： ，y ，h ，其 gx e r “，y e 一1 ，1 】。再假设该 训练集可被一个超平面线性划分，该超平面记为工) + 6 ；0 。其中，离超平面最 近的样本点( 支持向量) 满足 f ，w z f ) + 厶= 1 ，若y = l ，w x f ) + b 一- 1 ，若y _ 一1 公式2 - 1 以二维平面上的样本集为例，如图2 3 所示。 图2 - 3 线性分类器示意图 所有样本点分为两类，直线l 即为划分面( 二维情况下即为直线) ，距离直线l 最近的点位于l 1 和l 2 上，即为支持向量。 为更加明显地将两类样本点用超平面分开，很明显要求支持向量到超平面的距 离达到最大化。支持向量到超平面的距离为l ( w 五) 一6 f l w 0 - 1 i i i l ，支持向量之间 的距离为2 川w | l 即为分类间隔，因此构造最优超平面使分类间隔最大化的问题就 转化为如下的最优化问题： m i n i m i z e 中，6 ) = 导1 w l l 2 s t y f ( w x j + 6 ) 一1 乏0i 一1 ，z ，z 公式2 - 2 目标函数是严格上凸的二次型，约束函数是下凹的，这是一个严格凸规划。按 照最优化理论中凸二次规划的解法，可以把它转化为w o l f e 对偶问题来求解。 构造l a g r a n g e 函数： 工c 邺一；i w 1 2 一扣y ，( x ，- w + b ) + 塞口t ， a ，20 ，i 一1 ，乏，i 公式2 - 3 式中，q 是l a 伊a n g e 乘子。它满足条件v ，l ( w ，口，易，) 口o 去可w ，6 ，) o ( k u h n - t u c k e r ) ，即w ；罗口f y ，工，和罗y f 一0 。将这两式代回l a g r a n g e 函数中，消 _ 去w 和b ，经运算得到最优化问题的w o l f e 对偶问题，即 m a x m 协 f ，口) 2 荟口，一专荟a ，口，y ，y ，x ；z ， s f 善q n 。o 公式2 - 4 【a j 之0 i = 】，弘。，l 其解是最优化问题的整体最优解。解出口后利用，一口，y ，x ，确定最优超平 面，应该注意只有支持向量所对应的l a g r a n g e 乘子a ；才不是0 。 基于最优超平面的分类规则就是下面的判别函数： f ( x ) f f i 叫支船以一叫 公枷 式中，b 作为偏移值，取值如下： 西= 1 耋a i y i x i x , r 1 ，+ 套口，y ，z ，z r 一1 ，】 公式2 - 6 式中，x f ，1 ) 表示属于第一类的某个( 任一个) 支持向量：z f ，一1j 表示属于第 1 2 二类的某个支持向量。 2 4 3 非线性分类器 实际上，大量数据挖掘实例中，样本点都是线性不可分的，即不存在一个线性 的超平面将两类样本点完全分开，如图2 4 所示。 口 。 图2 4 非线性分类器示意图 。 此时，一个非常巧妙的方法就是把低维空间映射到某一高维空间去，使得样本 点在高维空间中是线性可分的。这样做，可以利用已经建立起来的线性分类器的相 关理论。同时，高维空间中相互关联的坐标对样本点分类也是没有本质性影响的。 但是，这种方法面临着两个问题。一是如何找到该映射关系使得样本点在高维空间 中是线性可分的，很明显，映射的形式决定于样本空间的固有性质，是未知的知识， 从而无法决定具体的映射形式。另外一个问题是，支持向量机最后会转化为二次规 划问题，问题规模决定于样本点数目和空间维数，在映射到高维空间后，问题规模 可能急剧增大，造成“维数灾难 。 核函数有效地解决了这两个问题。 2 4 4 核函数 线性分类器中基本的计算量存在于空间中向量内积的计算