（计算机应用技术专业论文）基于基因表达数据的样本分类研究.pdf

硕上学位论文 摘要 利用基因芯片技术可以同时对成千上万个基因的表达数据进行并行分析，从 而产生了海量的有用数据，使用机器学习对这些大量的复杂数据进行分析是目前 重要的研究领域之一。在这个研究领域里，基于基因表达数据的样本分类扮演着 很重要的角色，它一般具有两个关键步骤：基因选择和分类模型设计。本文在研 究样本分类过程的基础上，针对此种分类问题的特殊性以及已有方法存在的一些 问题，提出了一些改进的方法。 基因表达数据矩阵的最大特点是少量样本( 一般不超过l o o ) 对应着很多的特 征( 几千甚至上万个基因) ，这给样本分类研究带来了巨大挑战。为了剔除与样本 分类无关的基因以减少冗余、降低计算复杂度和提高分类准确度，基因选择是进 行样本分类前必不可少的一步。本文先按照相关性系数标准对样本所包含的全体 基因进行筛选，降低冗余的同时有利于缩小优化算法的搜索范围；然后在筛选结 果上采用蚁群优化策略进行分类相关基因子集的选择，并利用样本聚类效果作为 优化目标函数，保证分类准确度的同时大大降低了基因选择方法的计算复杂度。 实验结果表明，本文提出的基因选择方法能在相当短的时间内选出与分类相关的 基因子集。 基于基因表达数据的样本分类属于数据挖掘中的分类任务，它最重要的性能 指标就是它对样本分类的准确度。本文在属性识别理论的基础上，利用统计原理 设计了一个分类系统。同时，为了克服单分类器分类准确度相对不高等特点，把 这个分类系统与传统的k n n 分类器结合起来，形成一个新的样本分类方法。在 癌症数据集上的实验显示，新的方法具有较好的分类效果，并且时间复杂度较低。 关键词：样本分类；基因选择；蚁群优化算法；属性识别理论；准确度 i i 基于基因表达数据的样本分类研究 a b s t r a c t t h eg e n ec h i pt e c h n o l o g yc a ns i m u l t a n e o u s l ya n a l y s et h ee x p r e s s i o nd a t ao f t h o u s a n d so fg e n e s ，a n di th a sg e n e r a t e da1 a r g eq u a n t i t yo fa v a i l a b l ed a t a u s i n gt h e m a c h i n el e a m i n gt oc a r r yo nt h e 蛆a l y s i sf o rt h e s em a s s i v cc o m p l e xd a t ai so n eo f i m p o r t a n tr e s e a r c ha r e a sa tp r e s e n t i nt h e s er e s e a r c ha r e a s ， s a m p l ec l a s s i f i c a t i o n b a s e do ng e n ee x p r e s s i o nd a t ai sa c t i n gav e r yi m p o r t a n tr o l e ，i tg e n e r a l l yh a st w o p i v o t a ls t e p s ：g e n es e l e c t i o na n dc 1 a s s i f i e rd e s i g n t h i sa r t i c l e ，w h i c hb a s e do n r e s e a r c ho fs a m p l ec l a s s i f i c a t i o n sp r o c e s s ，i m p r o v e ds o m em e t h o d si nv i e wo ft h e p a r t i c u l a r i t yo fs a m p l e c l a s s i f i c a t i o nb a s e do n g e n ee x p r e s s i o n d a t aa n dt h e s h o r t c o m i n go ft h ee x i s t e n tm e t h o d s t h em o s tm a jo rc h a r a c t e r i s t i co ft h eg e n ee x p r e s s i o nd a t am a t r i xi st h a taf e w s a m p l e s ( g e n e r a l l yd o e sn o te x c e e d 10 0 )c o r r e s p o n dt oag r e a tm a n ya t t r i b u t e s ( s e v e r a lt h o u s a n de v e nu pt ot e nt h o u s a n dg e n e s ) ，w h i c hb r i n g sah u g ec h a l l e n g et o t h er e s e a r c h i no r d e rt or e l j e c tt h eg e n e sw h i c ha r ei n d e p e n d e n to ft h es 锄p l e c l a s s i f i c a t i o nt or e d u c et h er e d u n d a n c yo rc o m p u t a t i o nc o n l p l e x i t ya n de n h a n c e c l a s s i f i c a t i o na c c u r a c y ，g e n es e l e c t i o ni sa na b s o l u t e l yn e c e s s a f ys t e pb e f 0 r es a m p l e c l a s s i f i c a t i o n a tf i r s t ，t h i sa n i c l eu s e dt h er e l e v a n tc o e f f i c i e n ts t a n d a r dt of i l t e rt h e g e n e s ，w h i c hw a sa d v a n t a g e o u st or e d u c et h er e d u n d a n c ya n dt h eh u n t i n gz o n eo ft h e o p t i m i z e da l g o r i t h ma tt h es a m et i m e ；t h e ni tu s e dt h ea n tc o l o no p t i m i z a t i o ns t r a t e g y i nt h er e s u l tt os e l e c tt h es u b s e to fg e n e s ，i tt o o kt h ec l u s t e r i n ge f f e c ta st h e o p t i m i z a t i o no b j e c t i v e 如n c t i o n ，w h i c hg u a r a n t e e dt h ea c c u r a c yo fc l a s s i f i c a t i o na n d g r e a t l yr e d u c e dt h ec o n l p u t a t i o nc o m p l e x i t yo ft h e m e t h o ds y n c h r o n o u s l y t h e e x p e r i m e n t a lr e s u l ti n d i c a t e dt h a tt h eg e n es e l e c t i o nm e t h o dp r o p o s e di nt h ea r t i c l e c a ns e l e c tt h es u b s e to fr e l a t e dg e n e si nv e r ys h o r tt i m e t h es a m p l ec l a s s i f i c a t i o nb a s e do ng e n ee x p r e s s i o nd a t ap e r t a i n st oc l a s s i f i c a t i o n i nd a t am i n i n g ，i t sm o s ti m p o r t a n tp e r f o m a n c ei n d e xi st h ea c c u r a c y t h i sa n i c l eu s e d t h ep r o b a b i l i t ys t a t i s t i c st h e o r yt od e s i g nac l a s s i f i c a t i o ns y s t e mo nt h ef b u n d a t i o no f a t t r i b u t er e c o g n i t i o nt h e o r y a tt h es a m et i m e ，i no r d e rt oo v e r c o m et h ed e f e c to f l o w e ra c c u r a c yo fs i n g l ec l a s s i f i e r ，t h i sa r t i c l eu n i f i e dt h i sc l a s s i f i c a t i o ns y s t e ma n d t h et r a d i t i o n a lk n nc l a s s i f i e rt of o n nan e wm e t h o do fs a m p l ec l a s s i f i c a t i o n t h e r e s u l to fe x p e r i m e n t so nc a n c e rd a t ad e m o n s t r a t e dt h a tt h en e wm e t h o dh a sag o o d c l a s s i f i c a t i o ne f 佗c ta n dl o wt i m ec o m p l e x i t y i 硕士学位论文 ； k e yw o r d s ：s 锄p l ec l a s s i f i c a t i o n ；g e n es e l e c t i o n ；a n tc 0 1 0 no p t i m i z a t i o na l g o r i t h m ； a t t r i b u t er e c o g n i t i o nt h e o r y ；a c c u r a c y l v 基于基因表达数据的样本分类研究 插图索引 图1 1 基因芯片制作过程1 图1 2 学习系统结构示意图3 图2 1 基于基因表达数据的样本分类模型6 图2 2 欧氏距离失效示意图1 3 图2 3 分类线及分类间隔示意图1 4 图2 4 最优分类线示意图1 5 图3 1 蚁群寻找最短路径的原理2 2 v l i 硕七学位论文 附表索引 表3 1 万对基因规模的影响2 8 表3 2 万= 0 0 0 5 时w 与口取值对分类结果的影响。2 8 表3 3 万= 0 0 5 时w 与口取值对分类结果的影响2 9 表3 4 万= 0 3 时w 与口取值对分类结果的影响2 9 表3 5 本文方法( g s b f o ) 与p m b g a 的比较3 0 表4 1 在训练集上用l 0 0 c v 方法测得结果4 l 表4 2 在测试集上测得结果4 l v i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：日期：加矽年 ，月 i 砂日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 作者签名： 导师签名： 日期：9 ，年t 月 f 日 日期：d 晰年r 月，2 日 硕士学位论文 1 1 基因芯片 第1 章绪论 生物芯片技术是根据分子间特异性的相互作用原理，将生命科学领域中不连 续的分析过程集成于硅芯片或玻璃芯片表面的微型生物化学分析系统，以实现对 细胞、蛋白质、基因及其他生物组分的准确、快速、大信息量的检测，它的主要 特点是高通量、微型化和自动化。按照芯片上固化的生物材料不同，可以将生物 芯片划分为基因芯片、蛋白质芯片、细胞芯片和组织芯片。目前，最成功的生物 芯片形式是以基因序列为分析对象的“微阵列 ，也被称为基因芯片或d n a 芯片。 基因芯片就是将大量探针分子固定于支持物上，根据碱基互补配对原理，与 标记的样品分子进行杂交，通过检测杂交信号的强度及分布进而获取样品中靶分 子的数量和序列信息。它应用的基本原理是分子杂交，即先用荧光染料标记样本 d n a 或c d n a ，然后与基因芯片杂交，经激光共聚焦荧光显微镜检出杂交信号， 通过计算机处理、分析，即可得所需信息：用红绿荧光分别标记实验样本和对照 样本的c d n a ，混合后与基因芯片杂交，可显示实验样本和对照样本基因的表达 强度( 显示红色、绿色或黄色) ，由此可在同一基因芯片上同时检测两个样本的基 因差异表达。其制作过程如图1 1 所示。 删鼬 图1 1 基因芯片制作过程 甲 鼍乒 c o m p u t 何 a n a i 弘吐 基于基冈表达数据的样本分类研究 基因芯片的高通量特点包括其高度并行性和多样性。高度的并行性不仅可大 大提高实验的进程，并且有利于基因芯片技术所展示图谱的快速对照和阅读；多 样性是指在单个芯片中可以进行样品的多方面分析，从而提高分析的精确性，避 免因不同实验条件产生的误差；微型化是当前芯片制造中普遍的趋势，其好处是 可以减少试剂用量和减少反应液体积，从而提高样品浓度和反应速度；高度自动 化则可以减低制造芯片的成本和保证芯片的制造质量不易波动。另外，与计算机 相连的图象分析系统使研究结果更客观、准确。正因为基因芯片具有如上优势， 它在短短几年内便得到了非常广泛的应用，它的重要性可以与2 0 世纪5 0 年代把单 个晶体管组装成集成电路芯片相比，它将会对2 1 世纪生命科学和医学的发展产生 无法估量的影响【l ，2 j 。 1 2 机器学习 机器学习是继专家系统之后人工智能应用的又一重要研究领域，也是人工智 能和神经计算的核心研究课题之一。它是人工智能领域中较为年轻的分支，其发 展过程可分为4 个时期：2 0 世纪5 0 年代中期到6 0 年代中期属于热烈时期；6 0 年代中期至7 0 年代中期，被称为机器学习冷静时期；7 0 年代中期至8 0 年代中期， 称为复兴时期；1 9 8 6 年开始是机器学习的最新阶段。处于新阶段的机器学习具有 如下特点：它已成为新的边缘学科并在高校成为一门独立课程；融合了各种学习 方法，形式多样的集成学习系统研究正在兴起；机器学习与人工智能各种基础问 题的统一性观点正在形成；各种学习方法的应用范围不断扩大，一部分应用研究 成果已转化为商品；与机器学习有关的学术活动空前活跃。 一般认为，机器学习就是一个通过经验休整系统的过程。机器学习的核心是 学习，学习是人类智能的主要标志和获得智慧的基本手段，是人类具有的一种重 要智能行为。从特殊的训练样本中提炼出普遍适用的规律是学习的中心，提供一 组含有各种类型的训练和测试样本给学习机器，机器经过学习后，从中定义出假 设，对于一组确定的测试样本，机器必须具备通过对假设的逼近从而获得最佳假 设的能力。简言之，机器学习是使计算机能模拟人的学习行为，通过自动学习获 取知识和技能，不断改善性能，实现自我完善，它研究的是如果通过识别和利用 现有知识来获取新知识和新技能【3 j 。 1 2 1 学习系统的基本结构 为了使计算机系统具有某种程度的学习能力，使它能通过学习增长知识、改 善性能和提高智能水平，需要为它建立相应的学习系统。一个学习系统必须具有 适当的学习环境，一定的学习能力，并且能应用学到的知识求解问题，其目的是 提高系统的性能。它一般应该由环境、学习、知识库、执行与评价四个基本部分 2 硕士学位论文 组成，如图1 2 所示。 图1 2 学习系统结构示意图 图中箭头表示信息的流向；环境指外部信息来源，它将为系统的学习提供有 关信息；学习指系统的学习机构，它通过对环境的搜索取得外部信息，然后经过 分析、综合、类比、归纳等思维过程获得知识，在存储时要进行适当的组织，使 它既便于应用又便于维护；执行与评价由执行和评价两个环节组成，执行环节用 于处理系统面的现实问题，即应用学习到的知识求解问题，如定理证明、智能控 制、自然语言处理、机器人行动规划等；评价环节用于验证、评价执行环节的效 果，如结论的正确性等。另外，从执行到学习必须有反馈信息，学习将根据反馈 信息决定是否要从环境中索取进一步的信息进行学习，以修改、完善知识库中的 知识，这也是学习系统的一个重要特征。 1 2 2 学习的主要策略 机器学习的发展极为迅速，应用也日益广泛。有很多优秀的学习算法，基本 上可分为基于符号学习和基于非符号学习( 连接学习) 。其中符号学习比较好的有 机械学习、指导式学习、示例学习、类比学习、基于解释的学习。 随着人类智能研究的进展，人们逐渐发现研究人工智能的最好方法是向人们 自身学习，因而引入一些模拟进化的方法来解决复杂优化的问题，其中富有代表 性的是遗传算法。遗传算法的生物基础是人类生理的进化及发展，此方法被称为 进化主义：另一方面，神经网络的理论基于人脑的结构，其目的是揭示一个系统 如何向环境学习，此方法被称为连接主义。这两种方法与传统方法大相径庭，因 而近年来许多科学家致力于这两种方法的研究。 另外，统计学习理论的发展提出了支持向量机学习算法，由于其出色的学习 性能尤其是泛化能力，引起人们对这一领域的极大关注。该技术已成为机器学习 界研究的热点，并在很多领域都得到成功应用。 。 2 0 世纪8 0 年代，基于试错方法、动态规划和瞬时误差方法形成了强化学习 ( r e i n f o r c e m e n tl e a m i n g ) 理论，这是一种不同于传统机器学习理论的学习方法。 1 2 3 机器学习的分类 一般把机器学习分为有指导学习、无指导学习和半指导学习三种类别。有指 导的学习是指样本有结果度量的学习过程，我们希望根据一组特征对结果度量进 基于基因表达数据的样本分类研究 行预测。这里的结果度量一般有定量和定性两种，分别对应于统计学中的回归和 分类。在无指导学习中，只能观察特征，没有结果度量的。此时只能利用从总体 中给出的样本信息对总体作出某些推断以及描述数据是如何组织或聚类的。半指 导学习是近年来机器学习中一个备受瞩目的内容：已得的观察量中一部分是经由 指导者鉴认并加上了标识的数据，称之为已标识数据；另一部分观察量由于种种 原因未能标识，被称为未标识数据。需要解决的是如何利用这些观察量( 包括已标 识数据和未标识数据) 及相关的知识对未标识的观察量的标识做出适当合理的推 断。解决这类问题常用方法是采用归纳一演绎式的两步骤路径，即先利用已标识 数据去分析并指出适当的一般性的规律，再利用此规律去推断得出有关未标识数 据的标识。这里，前一步是从特殊得到一般结论的归纳步，后一步则是将一般规 律用于特殊情况的演绎步。 1 3 本文研究意义 随着2 0 0 3 年4 月人类基因组计划的所有目标全部实现，研究者接下来的任务 就是对这些基因表达数据进行分析，我们进入了后基因组时代。d n a 序列最初被 转录为m r n a 序列，这些m r n a 序列将被翻译成代表组织细胞功能的蛋白质相 对应的氨基酸序列。一个至关重要的方面是，基因表达数据的模式是组织细胞功 能的重要表征，不同的细胞类型表达不同的基因数据模式。测量m r n a 水平可以 让我们对在不同状态下的不同组织细胞类型的基因表达进行微观层面上的观察， 而微阵列技术使我们能同时测量成千上万个基因的这种水平。在不同状态下测量 基因的表达水平是研究者进一步了解基因功能、基因之间如何协作以及如何影响 组织细胞功能的重要手段【4 j 。当前的癌症分类技术高度依赖于病理学工作者对癌 症组织的主观判断，而基于基因表达数据的分析技术，即使一些组织在形态等方 面没有显著变化，也可以对其做出早期诊断，因此利用基因表达数据进行癌症的 分类和诊断是当今生物信息和医学等领域专家的共识。 通过基因表达数据对样本进行分类能帮助人类更好的认识癌症。正常的组织 细胞会由于控制细胞类型的一些基因的系列转变而进化成恶性癌细胞，虽然这只 是一个相对小的概率事件，但它毕竟还是一直在发生。准确的识别癌症类型或确 定其发展阶段对有针对性的治疗是j f 常关键的，因此，对组织样本进行分类并进 一步为癌症诊断进行服务，是分析基因表达数据的一个中心目标。研究者都确信 基因表达模式的分类能为人类进行癌症分类提供一个精确的、客观的、系统的方 法p q j ，我们可以通过基因表达模式的变化状态来判别癌症的类型，并且已经有很 多经典的分类算法被用到癌症分类上来，比如支持向量机、近邻方法、人工神经 网络等等【8 10 1 。 用基因表达数据对样本进行分类的另一个重要目的是更好的认识组织对药物 4 硕士学位论文 治疗的反应。我们可以通过观察组织在接受药物治疗前、治疗中以及治疗后的基 因表达模式的变化状况，来确定药物治疗的响应基因、指出药物治疗的效果、甚 至找到潜在的药物治疗标靶。更通俗的讲，完整的基因表达模式是对接受治疗的 组织样本进行分类，从而预测组织接受药物治疗后的反应的基础【4 】。 1 4 本文的主要工作及结构 本文对基于基因表达数据的样本分类进行了一个比较详细的叙述，为此方向 的研究提供了一个基本的模型和框架。针对框架内的两个主要步骤，分别提出了 基于筛选优化的基因选择算法和基于属性识别理论的样本分类方法，并先后在相 应数据集上利用v c 实现了这两个算法，具体工作如下： 1 ) 提出一个基于筛选优化的基因选择方法一一g s b f o ：先根据一个相似性 标准对全体基因进行一次筛选，然后在剩下的基因集上利用蚁群优化算法对特征 基因子集进行选择，其中的优化目标函数不采用与具体分类器相关的分类准确度， 而是用样本的聚类效果，从而得到一个速度快且更有利于分类的基因选择方法。 2 ) 提出一个新的样本分类方法一一基于属性识别理论的样本分类( a i b p ) ：借 鉴属性识别模型的思想，先利用高斯分布对每个属性基因进行单属性测度的计算， 然后采用加权的方法计算样本的属性测度。为了加强分类器对噪声的处理能力， 本方法还把属性测度与k n n 分类器结合起来，形成一个加权的组合分类器，提高 了分类性能。 本文分四章展开： 第一章为绪论部分，阐述了基因芯片技术和机器学习理论背景下的基因表达 数据分类( 即研究课题的来源) 及其意义； 第二章概述了基于基因表达数据的样本分类，为其研究提供了一个具体的模 型和框架，并对模型中各步骤进行了比较详细的说明。 第三章提出一个基于筛选优化的基因选择方法，并对其进行深入分析，除了 在一个数据集上进行方法参数的研究外，还在另一个数据集上与其它算法进行了 对比，然后给出实验结果。 第四章提出一个新的样本分类方法，对其理论基础，即属性识别理论进行了 比较详细的说明，并与其他的同类方法进行了分析和比较，然后给出实验结果。 最后，论文总结了全文的主要工作，并探讨了基于基因表达数据的样本分类 所面临的问题和发展方向。 基于基因表达数据的样本分类研究 第2 章基于基因表达数据的样本分类概述 2 1 基于基因表达数据的样本分类模型 基于基因表达数据的样本分类一般分为基因选择与分类器的构造两个主要步 骤。由于分类器的应用范围更广，各领域研究者投入的工作也相对较多，而基因 选择可以与具体的生物信息相关，它也正是分类器在遇到维数灾难而提出的，因 此它的研究要稍滞后于分类器的研究。一般认为，虽然主要目标是样本分类，但 基因选择和分类器的构造一样重要，并且把它当成是构造分类器之前一个必不可 少的预处理过程。图2 1 是基于基因表达数据的样本分类模型【l l 】，它包括了基因 数据处理的一些详细步骤，其中模型最主要的数据流是特征基因选择和参数设置 以及构造分类器之间的循环( 参数设置实质也是分类建模的一部分) ，由此也可以 看出特征基因选择与分类器的同等重要性。 图2 1 基于基因表达数据的样本分类模型 在以上样本分类模型中，基因表达数据和样本类别数据都被用到了，所以这 是一个有监督的学习模型。与有监督的学习相对应，无监督学习不存在训练集与 测试集的划分，也不存在特征基因的选择，因为这种类型的学习任务一般是发现 新的样本类别亚型。由于基因表达数据有样本数非常小的特点，把样本分为训练 集和测试集几乎是不可能的，所以在最后阶段，可以采用交叉检验的方式去进行 分类器的效果分析与评价。有时把基因选择也看做是数据预处理的一部分，这种 情况下把前面的处理看成是初级预处理，而基因选择被称为高级预处理。 6 硕士学位论文 2 2 基因数据预处理 从某种程度上说，基因表达数据的预处理与其他领域数据挖掘的数据预处理 是一样的，也就是把数据进行一下转换，以便处理后的基因数据更适合我们对其 进行分析及建立尽可能好的分类模型。然而基因表达数据独有的特征也给此阶段 带来了与其他数据挖掘不同的特性。 1 ) 阈值化。通过对同一样本多次测试所产生的误差进行研究，发现基因表达 谱的观察值在1 0 0 之上是可再生的，当观察值小于1 0 0 时则很难再生。因此，基 因表达谱值的左阈值通常设为l o o ，对于小于1 0 0 基因表达谱观察值，其为噪声 的可能性也越大。基因表达值的右阈值一般设置为1 6 0 0 0 ，因为高于此阈值的表 达谱观察值与真实的表达谱值趋向于未知的非线性相关的关系，应予以舍弃。 2 ) 标准化。分类一般可以直接使用基因表达的实际数据，但聚类时表达数据 的标准化是必要的，一般把基因表达标准化成均值为o 、标准方差为l 的数据。 3 ) 过滤。由于很多基因在某些样本下完全无表达或者在不同样本之间变化不 够大，通常在为数据集添加类别信息之前进行一次基因过滤操作。典型的过滤方 法是将在样本间表达值变化过小的基因排除掉，如： m a x v a l u e ( g ) m i n v a l u e ( g ) 5a n d m a x 、伍l u e ( g ) 一m i n v a l u e ( g ) 5 0 0 这里m a x v a l u e ( g ) 和m i n v a l u e ( g ) 分别为基因g 在所有样本下表达谱值的最 大值和最小值。 2 3 分类特征基因选择 基因表达数据的一个显著特点是样本维数过高，每个样本都记录了组织细胞 中所有可测基因的表达水平，但实际上只有少数基因才真正同样本类别相关，包 含了样本分类信息，这些基因被称为分类特征基因。如何在表达数据成千上万个 基因中有效的选出样本的分类特征，一直是基因表达数据分析的难点所在，仍有 待深入研究。分类特征基因选择实质上是模式识别中的特征选择，其方法一般分 为排列( 筛选) 法和特征子集评估( 包装) 法两种大类别。 2 3 1 排列法 排列法利用一个标准去评价每个基因的样本区分能力，然后选择那些区分能 力较强的基因作为构造分类模型的特征，这里所说的评价标准一般有信躁比、信 息增益、线性相关系数等。 1 ) g o l u b 等人【1 2 】采用信噪比( s i g n a lt on o i s er a t i o ) 指标来衡量某个基因 所含有的样本信息量，即： 7 基于基因表达数据的样本分类研究 册( g ) ：姓 ( 2 1 ) o | + 七o g 一 其中，跚瑷( g ) 为基因g 的信噪比，以+ 、f 一分别为基因g 在两种样本类别 中表达水平的均值，盯、吒一为相对应的标准差。由上式分析可以得出若两个类 别样本表达值的均值距离越大，并且每个类别样本表达值分布越集中，则该基因 含有的分类信息越多。 2 ) 信息增益( i n f o m a t i o ng a i n ) 【1 3 】最初是i d 3 算法里用于选择最有助于分类 实例的属性的一个定量标准，它是一个统计属性，用来衡量给定的特征区分训练 样本的能力的。为了精确的定义信息增益，必须先定义信息论中广泛使用的一个 度量标准，称为熵( e n t r o p y ) ，它刻画了任意样本集的纯度，给定包含正常与癌症 两个样本类别的集合s ，那么s 相对这个布尔型分类( 即只有两个类别的样本分类) 的熵为： 凸f ( s ) = 一nl 0 9 2n 一见l 0 9 2 卫( 2 2 ) 其中，n 是在s 中正例的比例，正是在s 中反例的比例。在有关熵的所有 计算中定义0 1 0 9 0 为0 。熵的一种解释是，熵确定了要编码集合s 中任意成员( 即 以均匀的概率随机抽出的一个成员) 的分类所需要的最少二进制位数。 简单的说，一个属性的信息增益就是由于使用这个属性分割样本而导致的期 望熵最低。更精确的讲，一个属性彳相对样本集合s 的信息增益g 口跏阻么) 被定 义为： ici 国伽( s ，彳) = 勘f ( s ) 一舒砌f ( 最) ( 2 3 ) v e 砌f t 船 ) l 。l 其中，砌缸酷翻) 是属性彳所有可能值的集合，s ，是s 中属性彳的值为y 的 子集( 也就是，鼠= p s ia ( s ) = v ) ) 。在上式中，第一项就是原集合s 的熵，第二 项是用彳分类s 后熵的期望值，当对s 的一个任意成员的目标值编码时，g 口伽( s ，彳) 的值是在知道属性彳的值后可以节省的二进制位数。 3 ) 线性相关系数( l i n e a rc o r r e l a t i o nc o e m c i e n t ) 【1 4 1 是基因表达( 自变量z ) 与样 本类别向量( 因变量) ，) 之间一种线性关系强弱的度量： ，= 一。) ( y 一) ( q + q ) ( 2 4 ) 这个，值刻画了属性与样本类别之间的依赖关系的强弱，它在区间 - 1 ，l 】上， 当为o 时，说明属性z 与样本分类之间毫无关系，绝对值接近l 时则说明属性x 与样本分类之间有非常强的线性关系。 2 - 3 2 包装法 前面的排列算法仅对每个单独的基因按照一定统计或可分性判断进行排队， 然后取排在前面的一些基因，这样虽然比较简单，但筛选基因的阈值难以确定， 8 硕十学位论文 当为了不损失分类准确率而尽可能把筛选阈值放宽时，又会存在非常大的冗余， 另外还忽略了基因相互结合所产生的分类效果，由于结合两个排在后面基因可能 具有比结合两个排在前面的基因更具分类能力，所以纯粹的筛选法所取得的结果 在大多数情况下不是最优基因子集，在仿真状况下甚至还有可能取到最差的基因 组。后来研究者提出了基因子集评估法，这类方法一般由搜索方法和评价标准两 部分组成。假设从d 个基因中选择出包含d 个的基因的最优子集，在d 和d 都 已经知道的情况下，所有可能的组合数为c ：，如果d = 1 0 0 ，咖1 0 ，则q 的数量 级已经是1 0 1 3 了，而实际上，基因数量d 一般是成千上万，并且最优基因子集的 规模是不确定的，也就是d 可能是1 到d 之间的任何整数，这样一来，所有可能 的组合数就是2 d 了，如果要把各种可能的基因组合都算出来再用评价标准进行比 较，计算量非常之大，是一个n p 完全难问题。因此一般只用一些搜索策略去取 得局部最优或接近全局最优，这些搜索策略一般分为全局最优搜索策略、随机搜 索策略和启发式搜索策略三类【l5 1 。 1 ) 在特征选择领域，唯一得到最优结果的全局最优搜索策略是“分支定界 ( b r 觚c h 粗db o u n d ) 算法，它的主要思路是：定义一个评价准则函数，该评价准则 函数必须满足单调性条件，即对两个子集s l 和s 2 ，如果s l 是s 2 的子集，那么s l 所对应的评价函数值必须小于s 2 所对应的评价函数值。在此条件下，对最终特 征子集的选择过程可以用一棵树来描述，树根是所有特征的集合，从树根往下， 在树的每级每枝都舍弃一个特征，然后根据可分性和事先定义的最佳特征子集的 规模，搜索满足要求的特征子集。 此搜索策略用于基因选择至少存在以下几个问题：它要求事先知道最优基因 子集的规模，这是非常难以确定的；单调性的评价准则函数设计困难，甚至不符 合基因选择的实际；基因选择属于高维数据处理问题，用全局搜索策略计算复杂 度高，运行效率低下。 2 ) 随机搜索策略带有一定智能，在计算过程中把特征选择问题与一些优化算 法结合，以概率推理和采样过程作为算法基础。在算法上增加一些启发式信息能 克服其子集规模难以确定，时间消耗大等问题。这种策略在基因选择领域用得比 较多，比如b i n 【l6 】等人先对基因进行排序筛选，然后使用遗传算法作为搜索策略 进行基因选择，e l o n 【1 。7 】等人则用粒子群优化算法进行基因选择。 3 ) 启发式搜索策略有很多种类型，它可以根据合理的启发式规则设计出非常 使用的次优搜索方法。用于特征选择时，它并不检查每个特征组合，但是可以估 计一组潜在、有用的特征组合，甚至可以根据所制定的启发式规则对所有特征进 行排序，在合理设计规则作用下，实际应用中这类算法甚至可以达到和前两种搜 索策略类似的效果，且具有运算速度快等特点。此类型搜索策略的缺点是当启发 式规则设置不当时，它的效果远不如前面两种方法，而启发式的设置恰恰是这类 9 基于基因表达数据的样本分类研究 方法的难点，因此如何找一个适合实际问题的启发式规则使得此搜索策略成为前 两种策略的最佳替代，是研究此类方法的努力方向。 除了搜索策略，包装法另一个主要方面是需要确定一个准则来评价所选特征 子集的性能，这个准则一般根据是否与具体分类器相关而分为两类：滤波策略和 嵌入式策略。前者在评价被选出的基因子集时不会用到分类器所使用的学习算法， 而后者一般以分类器采用子集对样本类别的预测效果来评价子集的优劣。在基因 选择领域，使用过的典型的滤波策略有互信息【18 1 、二次互信息【1 9 】等，而嵌入式策 略用的比较多的是基于s 功订分类效果的评价准则。 1 ) 互信息。令，( s ，f ) 表示基因子集s 与类别f 之间的互信息，那么有： ，( s ，f ) = 日( f ) 一( fs ) = 一p ( f ) - 1 0 9 2p ( f ) + p ( f ，s ) 1 0 9 2 比s ) ( 2 5 ) tt s 其中，日( f ) 是筛选法里介绍过的信息熵，它是关于类别f 的，而( f i s ) 是在 给定基因子集s 条件下，类别f 所具有的信息熵。这个互信息定义是单调性的评 价函数，也就是在基因子集s 上随意加一个基因不会减小，( s ，f ) 的值。，( s ，f ) 越大 说明子集s 与类别f 之间的关系越强，当它达到最大值时，说明s 能完全描述样 本类别f ，这个最大值可以简单的由，( f ，f ) 计算而来，也就是使用全局搜索策略对 侯选基因子集进行搜索时，一旦j ( s ，f ) = ，( f ，f ) ，就认为s 是最佳的基因子集。 2 ) 二次互信息。令训练样本集为g ，) ，) ，x 为连续的特征矢量，) ，为代表类别 的整数变量，p 为概率函数，则特征矢量x 与类别属性) ，之间的二次互信息为： ! ：p ( x ，y ) = 芝：i ( p ( 工，y ) 一尸( y ) p ( j ) ) c = 工以y ) 2 出+ p ( y ) 2 f p ( 工) 2 出一2 ( p ( j ，) 工p ( x ) p ( 训) p 川， yyy 实质上，二次互信息也是特征与类别之间相关性的一个度量，当x 关于) ，完 全独立时有最小值0 。用它进行特征选择的方法就是采用某种优化策略，搜索一 个特征变量子集x ，使该子集与类别属性y 之间的二次互信息最大。 另外，嵌入式策略一般是采用某种搜索方法得到基因子集，然后利用分类某 个分类器对用这些基因表示的样本进行分类，分类精确度越高，说明这个基因子 集越佳，当分类精确度达到预设的满意度时就可以停止算法。这种策略一般选出 的基因子集规模比较小，有利于关键基因的辨识和精简分类模型的结构，但它有 速度慢等缺陷。为了解决速度慢的问题，普遍的做法是利用评价结果在搜索策略 中加入启发式信息或把其转化为其他比较容易计算的问题。 2 4 几个经典的分类算法 基于基因表达数据的样本分类是一类典型的有监督的学习问题，即利用已经 知道类别标签的样本集( 训练集) ，通过某种算法建立一个分类预测模型，然后使 l o 硕士学位论文 用这个模型对未知类别的样本进行分类和预测。在有监督的学习算法中，最具代 表性的要数朴素贝叶斯( n a j f v eb a y e s ) 、k 近邻( k - n e a r e s tn e i g l l b o r ，k n n ) 和支持 向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 了，它们有不同的理论基础和实现形式， 因此在分类性能上也不尽相同，有各自的特性。这里重点介绍这三个经典的分类 算法。 2 4 1n a i v e b a v e s 贝叶斯推理提供了一种概率手段，基于如下的假定：待考察的量遵循某概率 分布，且可根据这些概率及已观察到的数据进行推理，以作出最优的决策，它为 衡量多个假设的置信度提供了定量的方法，也为直接操作概率的学习算法提供了 基础。朴素贝叶斯分类器就是直接操作概率型学习算法的一种。 n a i v eb a y e s 分类器应用的学习任务中，每个样本z 可由属性值的合取描述， 而目标函数f ( j ) 从某有限集合y 中取值，学习器被提供一系列关于目标函数的训 练样本以及新样本( 描述为属性值的元组) ，然后要求预测新样本 的类别标签。 贝叶斯方法的新样本分类目标是在给定描述样本的属性值 下， 得到最可能的目标值p 。 屹t p = a r g m a ) 【以y ，i ) 可使用贝叶斯公式将此表达式重写为： 2 鼍笋可瓦虿衰芍一 尺 1 1 ，) 以1 ，) 刮、“l “2 ，叫 = a r g m a ) 【尸( ，1 fs 刀，f 。换言之，z 被分到使其y 粕值最大的类。 理论上讲，与其他所有分类算法相比，贝叶斯分类具有最小的出错率，但实 践中并非总是如此。这是由于对其应用的假定( 如类条件独立性) 的不准确性，以 及缺乏可用的概率数据造成的。然而，种种实验研究表明，与判别树和神经网络 分类算法相比，在某些领域，该分类算法可以与之媲美。