（计算机应用技术专业论文）基于svm的基因选择.pdf

摘要 摘要 基因芯片的出现为基因诊断和基因治疗提供了很好的前提和可能性，超高维 空间超小样本的基因选择问题是基因芯片技术的挑战性课题之一，对于解决维数 发难问题和获得诊断基因具有重要的理论和实际意义。本文针对d n a 微阵列数 据，进行了基因选择方面的研究。 本文主要做了以下四部分的工作：( 1 ) 提出了实现二病类样本有效分类的基 于s v m + l e a v e - o i l e - o u t 递增基因选择方法。( 2 ) 针对多病类情况的基因选择问题， 提出了在区分两两病类所选择基因的基础上的基于i v l p + l e a v e o n e o u t 、 m l p + l e a v e - 4 - o u t 的递减基因选择方法。( 3 ) 在前面工作的基础上，提出了一种用 对多个区分两病类对的贡献向量求合表示基因对区分所有病类样本的贡献，并根 据合向量进行基因选择的合贡献向量基因选择方法。( 4 ) 提出了一种直接进行基 因选择的贡献空间基因选择方法。该方法利用多个区分两病类对的贡献向量构造 贡献空间，然后在贡献空间中进行基因选择。 经过对真实的基因微阵列数据进行大量实验，从2 3 0 8 个基因中找出了6 个基 因即可以诊断对应的4 种疾病，从7 1 2 9 个基因中找出了1 1 个基因即可以诊断对 应的2 种疾病。从而可极大的降低芯片和诊断费用，但却不失对疾病的正确诊断 能力，表明了本文中提出的几种方法的有效性。， 关键词：基因选择支持向量机交叉验证合贡献向量贡献空间 a b s t r a c t a b s t r a c t t h ea d v e n to fd n a m i c r o a r r a ym a k ei tp o s s i b l et op e r f o r mg e n ed i a g n o s i sa n d g e n e t r e a t m e n tg e n es e l e c t i o ni so n eo f t h em a j o r c h a l l e n g eo f g e n e - c h i pt e c h n o l o g y ， f o rg e n ed i a g n o s i sw h e r eo n l yag e n es u b s e ti s e n o u g hf o rd i a g n o s i so fd i s e a s e s ，f o r r e s o l u t i o no fc u r s eo fd i m e n s i o n a l i t yw h i c ho c c u r s e s p e c i a l l yi nd n am i c r o a r r a y d a t a s e tw h e r et h e r ea r em o r et h a nt h o u s a n d so fg e n e sa n do n l yaf e wn u m b e ro f e x p e r i m e n t s ( s a m p l e ) t h i sp a p e rs t u d i e dt h em e t h o do fg e n es e l e c t i o na n df o u rp a r t s w o r ka r es t u d i e da s f o l l o w s ：0 ) p r e s e n tag e n es e l e c t i o nm e t h o db yt r a i n i n gl i n e a r s v m ( s u p p o r tv e c t o rm a c h i n e ) c l a s s i f i e r a n dt e s t i n gt h e mw i t hc r o s sv a l i d a t i o nf o r f i n d i n gg e n es u b s e tw h i c h i so p t i m a l s u b o p t i m a lf o rd i a g n o s i so f b i n a r yd i s e a s ec l a s s e s g e n e sa r es e l e c t e dw i t hl i n e a rs v m c l a s s i f i e ri n c r e m e n t a l l yf o rt h ed i a g n o s i so f b i n a r y d i s e a s e ( 2 ) p r e s e n t ag e n es e l e c t i o nm e t h o df o rm u l t i c l a s sd i s e a s e b yt r a i n i n g s v m m l pc l a s s i f i e rw i t hm e t h o d l , w eg e tm a n yg e n es u b s e t ，t h e nt h eu n i o no f t h e mi su s e da s i n i t i a l i z e d g e n e s u b s e tf o r d i a g n o s i s o fa l lr e l a t e dd i s e a s e c l a s s e s ( 3 ) p r e s e n tag e n es e l e c t i o nm e t h o df o rm u l t i - c l a s sd i s e a s eb a s e do nc o m b i n e d v e c t o r b a s e dt h em e t h o d sa b o v e ，g e tm a n yc o n t r i b u t ev e c t o r , t h ec o m b i n e dv e c t o ro f t h e mi su s e dt os e l e c t e dg e n es u b s e tf o rd i a g n o s i s ( 4 ) p r e s e n tag e n es e l e c t i o nm e t h o d b a s e do nc o n t r i b u t es p a c e c o n s t r u c tac o n t r i b u t es p a c ew i t hm a n yc o n t r i b u t ev e c t o r g o ta si nm e t h o d3 g e n e sa r es e l e c t e di nc o n t r i b u t es p a c e f o rr e a ld n am i c r o a r r a y d a t aw i t h2 3 0 8g e n e sa n do n l y6 4l a b e l e ds a m p l e sb e l o n g i n gt o4d i s e a s ec l a s s e s ，o n l y 6g e n e sa r es e l e c t e dt ob ed i a g n o s t i cg e n e s ；w i t h7 1 2 9g e n e sa n do n l y7 2l a b e l e d s a m p l e sb e l o n g i n g t o2d i s e a s ec l a s s e s ，o n l y11 g e n e sa r es e l e c t e d k e y w o r d ：g e n e s e l e c t i o n c o m b i n e dv e c t o r s v mc r o s s i d a t i o n c o n t r i b u t e s p a c e 创新性声明 y 5 8 3 3 8 5 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：鱼生硷日期皇坐 ! i 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：南审山奎 导师签名：歪聋爱垩 日期加辁? 日期型2 生f ：i ： 第一章绪论 第一章绪论 堪与“曼哈顿原子弹计划”、“阿波罗登月计划”相媲美的“人类基因组计 划( h g p ) ”自1 9 9 0 年启动以来，目前基因测序工作己基本完成。这一跨世纪工 程完成蛆后，有关人类生长、发育、衰老、遗传的秘密将被揭开。与此同时，基 因诊断、基因治疗和药物基因组学也应运而生，将成为2 1 世纪诊治疾病的主要手 段和方法。而基因选择作为基因诊断、治疗总体工程的首要子工程，更是倍受大 家的关注。本文主要针对基因微阵列数据，进行了基因选择方面的研究。 1 1 基因微阵列数据与基因选择 自从克隆羊“多莉”1 9 9 7 年成功问世以来，对于基因方面的研究逐渐升温。 基因研究给人们带来了前所未有的希望：克服病痛、彻底治愈癌症、保护濒危物 种、甚至可以令人们长生不老等等。国内外大量专家学者开始关注基因领域并进 行深入研究，并取得相当的进展。 基因芯片f 1 2 】技术是近年来分子生物学及医学诊断技术的重要进展，该技术是 通过把巨大数量的寡核营酸，肽核苷酸或c d n a 固定在一块面积很小的硅片、玻 片或尼龙膜上而构成基因芯片。该技术同时将大量的探针固定于支持物上，因此 可以一次性对大量序列进行检测和基因分析，得到高维的基因微阵列数据即基因 表达数据。附录中给出了d n a 微阵列数据的影像表示。 目前关于基因之间调控关系的研究才刚刚开始，从而造成癌症的分子生物原 因目前仍只能被认为是各基因独立行为的结果，即每个基因被视为是独立的一维， 因此d n a 芯片的高通量使一次实验可获得超高维基因空间的一个样本，其维数通 常达到几千维甚至上万维，并且随着基因芯片技术的进一步发展和芯片集成度的 进一步提高，这个空间的维数还将进一步提高。同时每个病人的d n a 基因表达数 据只是这个高维空间中的一个样本，我们无法也不可能采集到多于空间维数十倍 以上的样本数【2 3 】，这就造成了严重的维数发难( c u r s eo fd i m e n s i o n a l i t y ) 现象 ”j 4 j 。比如在1 2 0 0 0 维空间中只有2 4 个样本。因此需要就这样的数据进行病类发 现、聚类、特定癌症的基因模式发现、找出最有利于区分这2 4 个病人所属疾病的 基因个体或子集来等。这些过去从未有过的超高维空间超小样本数据分析问题是 基因学向数据处理方法提出的新的挑战。 基因表达数据有助于更好的理解疾病，比如说：癌症。如果细胞中某些基因 ( 比如说：控制细胞生命周期、a p o p t o s i s 、基因组完整性等的基因) 经过一系列 基于s v m 的基因选择 的突变，正常缅胞就会演化成恶性的癌细胞【2 “。基因表达数据，可以使得基因诊 断、基因治疗、基因药物的研制等工作更有针对性。 基因表达数据的一个主要难题是数据集中基因的数目巨大但是大部分都无法 为癌症与肿瘤的区分提供有用信息，并且在分类过程中会引入噪声。然而，从诊 断的角度来说，找到一小组能提供足够信息的基因来区分不同类型的细胞非常重 要。选择相对较小的基因子集能明显的提高性能。而且，这个选择过程能够把那 些跟肿瘤组成和病理机制有潜在关系的基因分离开来。此外，诊断研究的一个主 要目标是利用廉价的微阵列设计出一个诊断方法，这种微阵列拥有足够少的能够 探测出疾病的探针。鉴别出能够产生有效的学习分类器的基因组也可能会展现出 先前人们不知道的与疾病相关的基因，并且指导进一步的生物学研究。对于大量 基因的另一个问题是对结果的解释。能够保证我们的方法把肿瘤和正常组织区分 开的信号如果只是少数基因表达水平的编码，应该能够理解这些基因的重要性。 因此识别出一小部分基因能否满足很好的分类是至关重要。 在生物学家目前还不了解哪些基因的突变会引起哪些疾病的情况下，d n a 芯 片的高通量为通过数据分析和处理手段运用计算机获得这种基因突变与疾病的关 系提供了前提和可能性。接下来的就是通过数据分析手段从这些固化在d n a 芯 片上的基因中筛选出与特定疾病相关的基因或基因子集，这就是d n a 芯片技术 给工程和科学提出的新的挑战：基因选择。因为判断癌症的类型和阶段对进行正 确的治疗非常重要，所以基因表达数据分析的一个主要任务是通过基因表达的剖 析分析辨认出几组能够作为分类和诊断依据的基因。这就意味着基因选择是癌症 分类的前提。此外，由于和生物实验样本的数量相比，基因的数量巨大，所以如 果不进行基因选择将引起维数发难 1 2 , 2 0 l ，从而导致分类性能的严重下降。 实际上，基因选择的目的之一就是从成千上万个( 设为n 个) 基因中筛选出一 个基因子集，使其对不同病类样本的可分性最大，从而可以作为对这些病类的诊 断基因，用于这些疾病的临床诊断。对于找使不同病类样本的可分性最大的基因 子集而言，需要解决两个问题：( 1 ) 应选择多少个基因；( 2 ) 皮选择哪些基因。实 际上这些问题的解决都是n p 完全问题 5 j 7 】，从而人们转而研究获得近似最优基因 子集的方法。 基因选择作为超高维特征空间中的特征选择问题，相对通常特征选择具有如 下特点：( 1 ) 空间维数比空间中的样本数要大得多，如空间维数为2 0 0 0 1 0 0 0 0 维，而样本数仅有几十。而不象通常的特征选择问题，空间维数仅有几十，而空 间中的样本数却有几百或几千；( 2 ) 特征选择是从2 0 0 0 - i 0 0 0 0 个特征中选择出几 个或几十个特征( 基因) ，而不象通常的特征选择是从几十个特征中选出一部分( 如 从1 8 个中选出1 2 个【5 , 1 7 1 ) ；( 3 ) 由于疾病的误诊将带来沉重的代价，因此要求选 出这样的基因或基因子集，使数据在这样的基因子集上可分性最强，且实现数据 第一章绪论 分类的分类器的推广能力最强。这些特点给基因选择提出了新的挑战。 1 2目前基因微阵列数据方面的研究 最近许多文章讨论d n a 微阵列数据分析，如用层次增长神经网络进行基因数据 的聚类口j ，用概率主分量分析进行疾病的生物标识研究p o 用以及用支持向量机队 两类问题进行基因选择【9 1 等。目前专门针对超高维基因空间的d n a 微阵列数据研 究基因选择的文章还不多，在对基因数据进行分析前多数采用一些非常简单的基 因选择方法( 如s n r 方法【1 1 】) ，也有通过主分量分析实现降维后直接进行数据分 类的研究i ”1 ，文献【”】提出了基于基因敏感度的基因选择方法，而文献【“1 所给出的 不是d n a 数据的基因选择而是二值逻辑函数的特征选择。文献【6 】【7 】所给出的特征 选择方法还没有讨论到像d n h 微阵列数据的如此高维情况的特征选择问题( 仅从 1 8 个特征中选择出1 2 个特征) 。诸如分支定界法及其改进算法【1 5 】f 1 7 】也都无法适应 如此高维情况的特征选择问题。 1 3 支持向量机及其在d n a 微阵列数据处理方面的应用 支持向量机( s s u p p o r tv e c t o rm a c h i n e ) 是由v a p n i k 于1 9 9 8 年提出的 一种使结构风险最小的两类问题模式分类学习算法1 2 3 脚】，该算法通过核函数的选 择可实现线性和非线性分类，对于线性可分问题，该算法可以获得m a r g i n 最大的 决策边界，从而所学习出的分类器对已有的学习样本具有最好的推广能力。进行 模式识别时，支持向量学习算法可以尽量使得落在区分正向样本和负向样本的边 界区内的训练样本的数量最少( 由松弛因子决定) ；s v m 保证能够找到误差面的全 局极值，而不会陷入局部局小；高维空间中的数字优化将遇到维数灾难，这种计 算上的问题可以通过使用s v m 的内积核( 根据m e r c e r 理论定义) 的以及在输入空 间求解以公式表述的约束极值问题的对偶规划的方法避免。用s v m 进行分类的另 一个吸引人的特征是判别边界表达式的稀疏性。 特征选择问题在模式识别和机器学习中非常受到人们的重视。由于数据集中 包含大量的基因( 特征) ，因此基因表达数据集的问题很难解决，同时基于特征子 空间的搜索方法也是不可行的。而且，由于这些数据集中仅包含一小部分样本， 因此统计的不稳定性也会给基因不相关性的检测带来难度。 由前面s v m 本身的特点，我们认为s v m 特别适于两类问题的基因分类( 诊 断) 与基因选择。g u y o n 等人f 1 3 】提出了递归特征消除的s x q v l 方法并且将它应用 到基因选择上，并进行了基于两个不同的癌症数据库的实验，实验证明在基因选 基于s v m 的基因选择 择过程中如果考虑基因间的相互影响将对分类的性能造成影响。由s v m 找出来 的基因都和癌症有一定的关系。相比之下，目前其他的基因选择算法都只是与分 类有关，而与癌症诊断没有关系。 1 4 本论文的主要工作 本论文的工作得到了美国n a t i o n a lc a n c e ri n s t i t u t er e s e a r c h 基金 ( r 2 1 r 3 3 ( 5 r 2 1 c a 8 3 2 3 0 1 ) ) 和国家自然科学基金( n o 6 0 0 7 1 0 2 6 ) 的资助。本论文 的工作主要针对d n a 微阵列数据的基因选择展开。为了评价所选择基因子集的优 越性，本文不得不将整个过程的两个阶段结合起来认真评价，这两个过程是：基 因选择和分类。选择出一个基因子集后，同时在相应的基因子空间中进行分类， 并用分类结果以及推广能力来衡量所选基因子集的性能。本论文其余章节安排如 下： 第二章、简要介绍s v m 对两类问题进行分类的方法，然后根据对分类方法的 分析，给出了两病类问题的基于s v m 的基因选择方法。首先利用训练样本构造线 性分类器，得到最优分类超平面及其所带来的分类间隔；然后，将样本向基因子 空间投影同时分类间隔也进行投影。根据基因选择的目的，希望得到一个基因子 集，在该子集中可以实现子分类间隔最大，即对应着求某个基因子空间，在该子 空间中分类间隔的投影最大，同时保证能进行正确分类所有样本并且推广能力最 大。本方法中用s v m + l e a v e o n e o u t 交叉验证的方法来衡量所选基因子集的性能。 第三章、简要介绍了s v m 对多类问题进行分类的方法，给出了多病类情况下 的基于s v l v l m l p 交叉验证的基因选择方法。该方法中将多病类的基因选择问题 转化为多个两病类基因选择问题来处理。首先，在上一章的基础上根据一一区分 的分类方法，进行多个两病类的基因选择；然后将得到的多个基因子集求并集； 最后在新得到的基因子集中，利用s v i v i - r f e 的方法，进行递减搜索，得到最终 的基因子集。其中，采用m l p + l e a v e o n e o u t 交叉验证的方法衡量所选基因子集 的性能效果。本方法中实际上进行了多次的基因选择。 第四章、上一章的方法由于进行了多次的基因选择，所以带了很大的时间复 杂度与空间复杂度。因此希望能有一种方法可以一次性的选择出符合要求的基园 子集。本章中，给出了一种针对多类问题的合向量基因选择方法。该方法中，对 分类时得到的m a r g i n 向量，求取一个模值最大的合向量。利用该合向量代表基因 对区分所有样本的贡献，在一定程度上模拟了基因在区分不同病类时相互间的影 响。然后利用该合向量进行递增基因选择。利用该方法有效的降低了时间复杂度 和空间复杂度。 第一章绪论 第五章、上一章的方法，由于用比较简单的向量求合来模拟基因在区分不同 病类时相互间的相互影响这种复杂的关系，效果并不是特别理想。在本章中，针 对多病类情况，根据空间变化的想法，在变换空间中进行基因选择。在第一章的 基础上，对得到的m a r g i n 向量进行变换处理，得到相应的贡献向量，并利用得到 的一系列贡献向量构造贡献空间。该贡献空间中，以两两病类对为坐标轴，以基 因为空间中的点。基因点的每一个分量代表该基因对分某两类的贡献。称贡献空 间中每个分量值都最大的那个点为最大贡献点。我们希望得到贡献空间中，尽量 靠近最大贡献点的那些基因。据此，构造了基于贡献空间的基因选择方法，该方 法中同样采用m l p + l e a v e o l l e o u t 交叉验证的方法衡量所选基因子集的性能效 果。本章的方法，由于只进行了一次基因选择，相对第三章的方法，有效的降低了 时间复杂度和空间复杂度，同时考虑到了基因在区分不同病类时相互间的相互影 响，结果的性能也有所提高。 基于s v m 的基因选择 第二章两病类情况下的基因选择 2 1 引言 对高维空间中的d n a 微阵列数据进行基因选择是在整个基因处理、治疗过 程中非常重要的工作。注意到基因选择的目的是选择某个基因子集，不仅将两类 样本分类开来，而且保证有最强的推广能力。可以证明对于基因空间中的样本来 说，由于空间的超高维特性和超小样本特性，样本的线性无关性通常是可以保证 的，从而对于二类问题，总可以用线性分类器进行分类。另外，我们可以发现， 存在无穷多个可以将二类问题分开的线性分类器。那么在所有这无穷多个分类器 中，哪一个线性分类器最有利于基因选择呢? 由于支持向量机( s v i 订s u p p o r t v e c t o rm a c h i n e ) 可以找到以最大边界( m a r g i n ) 将二类样本分类开来的最优分类超 平面，因此我们认为s v m 特别适于两类问题的基因选择。本章，首先会给出高 维空间小样本数据线性可分的证明；然后，简单介绍统计学习理论以及支持向量 机；最后在深入分析支持向量机的基础上给出了对于两类问题的基于s v m 的基 因选择方法同时给出了相应的实验结果。 2 2 高维空间小样本数据线性可分的证明 对于甩维空间中仅有很少几个( 比如说胁个，且肌 m 。本章仅讨论k = 2 的情况。 由前面的分析知道，对于线性可分问题，用分类超平面进行分类所得到的 m a r g i n 来描述模式的可分性和分类器的推广能力是合理的。运用$ v m 总可以找到 基因空间g 中m a r g i n 最大的分类超平面设为，：( w r , b ) ，它所带来的m a r g i n 为三i l w l l ， m a r g i n 的方向( 从第一类样本到第二类样本) 为朋法向方向赫。故若将，所带来 m a r g i n 用向量表示，则，在g 空间的m a r g i n 向量为m 。2 丽2 。赢。将，投影到 任选的r 个基因所构成的r 维基因子空间g ，得到，在g 。的投影分类超平面为 z + ：( 扩，6 ) ，则 w ：= f ”0 霎萋星：蓑蓑老上r = ，a 玎 c z - ，：， ”r 2 1若基因f 没被选上污l ，厶玎 1 印 显然瑚黼方向矢量旆在6 t 的投影为赫故纯6 空间中的m a r g i n 髓 2 赢赫在g 的投影为m 。2 丽2 榆a 基因选择即是选择r 个粗使靴啦，所给出删满足= 跺最大。 由于对特定样本的二分类问题，s v m 可以得到唯一的w ，从而选择，个基因使m 最大，即是找使w 中分量绝对值最大的前，个分薰。因此在二分类情况下基于s v m 的基因选择步骤非常简单，如下：( 1 ) 用s v m 对样本数据进行二分类，得到m 7 ，6 ) ； ( 2 ) 选w 分最值最大的前，个分量对应的基因作为基因选择的结果。 图2 3 ( 曲，m 、分别示出了简单的从 ：2 的两个基因盔，p ，门：3 的三个基因 1 2基于s v m 的基因选择 g 。，占：，占，中选择1 个1 个和2 个时的m a r g i n 的情况示意图。其中 m ，( x ) m f ( x ) m 耻分别表示选择了基因晶毋，g ，g j ，g ，g 女时s v m 的m a r g i n ， 并且m a r g i n 大小为x 。显然对于图2 3 ( a ) ( 其中m ，是由对样本进行s v m 分类器 设计获得的) ，若从两个基因中选择一个基因，则应选择岛，因为它所带来的 m a r g i n 最大；同理，对于图23 ( b ) ( 其中m 。是由对样本进行s v m 分类器设计 获得的) ，若从三个基因中选择一个基因，则应选择晶，若从中选择两个基因， 则应选择g ：，晶。 显然，对于任意的，维基因子空间，总有m 。m 。由于这一基因选择方法 是针对空间维数大于样本数情况提出的，不适于通常的特征选择。 ( a ) c o ) 图2 3 基于s v m 的基因选择方法示意图，( a ) 从两个基因中选择1 个；( b ) 从三个基因 中选择1 个或2 个 本文中用s v m + l e a v e - k o u t ( 对二病类情况) 描述样本在所选，维基因子空间 中的推广能力。从个训练样本中任取一k 个作为训练样本，训练一个s v m 线性分类器s v m 。，并用剩余五个样本测试该分类器的推广能力。若将该分类器 的误识率记为点( r ) ，即 i 1 0 0 若训练样本中有误识别 嗔p ) 5 1 测试样本误识率；i 荔蒜；辛晃簇蟊茹 则4 ( ，) 描述了样本在所选r 维基因子空间中s v m ，从n k 推广出k 的推广能力。 这样对有个样本的数据总可设计c 吾个s v m 分类器，其用s v m 线性分类器进 行分类的从任一足个推广到足个的最差推广能力可用如下的分类器结构误识率 表示，为： d ( 7 ) = ，掰5 巧( 7 ) ( 2 - 1 3 ) 显然，8 ( r ) 描述了样本在这r 个所选基因的基因子空间上用s v m 分类器进行分类 的推广能力。当8 ( r ) = 0 时，在这r 个所选基因的基因子空间上c 舌个s v m 分类 器中的最小m a r g i n 0 。 一 直 怒a 前 ill，1；雷卜l上叶j 、l 第二章两病类情况下的基园选择 综上，在两病类情况下进行基因选择的步骤如下： 1 用分属于两类的样本训练线性s v m 分类器，得到分类器的权向量w ，w ( i ) 为 其第i 个分量； 2 依基因i 对分类的贡献1 w ( 叫的大小，按降序将基因排序，并将选择的基因数目 ，设为，= 1 ； 3 将基因排序中的前r 个基因作为所选择的基因子集，在此，维基因子空间中， 对训练样本用线性s v m 以及l e a v e o n e o u t 训练c ：= n 个s v m 分类器，并依 式( 2 1 3 ) 计算s v m 。( i = 1 , 2 ，) 所带来的最大误识率d ( r ) ； 4 若万( r ) 0 ，则，卜r + 1 ，转s t e p 3 ；否则记录所选择的基因子集为g ； 2 5 实验与结果 我们的实验数据主要是( n c i 数据) ，该数据由美国癌症研究院( n c i ) 提供的 来自n e u r o b l a s t o m a 神经细胞和非霍吉金氏淋巴细胞肿瘤这两类样本的源基因表 达数据【8 】，这是在4 种病类8 8 个人的人群中所采集的这些人的基因表达数据， 即其基因空间的维数为2 3 0 8 ，样本数为8 8 ，病类数为4 ，其中6 4 个样本的所属 类别已知，各病类中的样本数分别为：2 3 、8 、1 2 、2 1 。本章的实验数据还包括 m i t 数据【2 “，该数据是来自一种白血病的源基因表达数据，包括两种病类有7 2 个样本，其基因空间的维数为7 1 2 9 ，两个病类的样本数分别为：4 7 、2 5 。以下是 实验结果及对结果的分析，主要包括：( 1 ) 对n c i 中某两病类进行分类的递增基因 选择与结果；( 2 ) 对m i t 数据进行分类的递增基因选择与结果。 2 5 1对n c i 数据中的某两病类进行分类的基因选择 运用本章的方法，对n c i 数据中两两病类分类问题进行了基因选择，图2 4 分别给出了运用s v m + l e a v e o n e - o u t 进行基因选择的过程。由前面的方法知道， 按所训练出的s v m 权系数绝对值由大到小进行排序，并选择基因。在基因数从 小到大增长过程中第一个m a r g i n 为正值所对应的基因子集就是在l e a v e o n e o u t 推广能力意义下的基因选择结果。从图中可以知道，并不是基因选得越多越好。 图2 4 ( a ) 中，选5 个基因时最小m a r g i n 为正值，但是当选择3 0 个基因时最小m a r g i n 为负，并不具有l e a v e o n e o u t 的推广能力。由图中，知道分病类l 和病类2 ，只 需要5 个 1 4基于s v m 的基因选择 s m a i ；s tm a r g i no b i b i n “f r o mp ，mf orl h gi g sk i n 9d a t a 一? 杰 一 ，” - 川j s m l l ；e s l m ar g i no b l a i n e d f r o ms v m f o r l h e t l ；l i n bd a t a 、 p 卜 i k 一? r 。 ”。一品“。品。 1 ” ( a )( b ) 图2 4 区分两两病类样本的s v m 最小m a r g i n ( 1 e a v e - o n e o u t ) 与所选择基因数目的关系( 基因递 增搜索过程) ，( a ) 区分病类1 与病类2 的基园子集递增搜索过程；c o ) k 分病类1 与病类4 的 基因子集递增搜索过程 基因即可；但是分病类1 与病类4 ，却需要1 5 个基因才行，为了使所选的基因子 集不至于漏掉重要的基因，在分病类1 与病类4 的时候，我们会向生物学家提供 4 2 个基因，此时最小的m a r g i n 比较大。 2 5 2 对m l t 数据进行分类的基因选择 我们利用本章的方法，也对m i t 数据进行了基因选择。图2 5 给出了基因选 择过程中所选捧的基因数目与s v m + l e a v e o n c o u t 的最大误识率的关系。从图中 可以看出当选择i 1 个基因的时候可以保证l e a v e o n e - o u t 误识率为零，但是随着 基因数目的增长，误识率却在增长。也说明了基因之间是有相互影响的。表2 1 i ? 弋 l 厂 7| ： ； 0 ： ； 。 图2 5 利用s v m + l e a v e o n e o u t 得到的最大 误识率与所选基因的关系 也说明这个问题，即当有一个基因子集可以对病类样本实现很好的分类时，向该 基因子集中增加一些基因，也许整个基因子集的推广能力，分类效果等都会有所 叫 。 吣 3 e e帚若*_j量e 第二章两病类情况下的基因选择 下降 表2 1 对m i t 数据进行基因选择，得到的误事率和对应支撑向量的个数 所选基因数目训练误识率测试误识率支撑向量个数 全部基因( 7 1 2 9 ) o 0 1 3 90 0 2 7 83 3 4 0 0 00 0 2 7 80 0 2 7 83 4 2 0 0 000 1 3 9o 0 1 3 93 3 1 0 0 00o3 1 5 0 0o1 3 900 2 7 82 8 2 0 0o02 7 1 0 0002 4 5 0001 8 3 0001 5 2 0oo 0 1 3 91 6 1 10o1 2 800 1 3 90 0 4 1 78 500 2 7 800 5 5 66 400 2 7 80 0 8 3 3 7 表中的训练误识率、测识误识率以及支撑向量个数，都是进行l e a v e o n e o u t 实验 得到的平均数值。对每一个基因子集，都进行了l e a v e o n e o u t 实验，会有7 2 个 s v m 分类器，将每个分类器得到的以上三个量分别求和然后取平均值。从表2 1 中，可以看出选1 1 个基因时便可以实现了l e a v e o n e - o u t 误识率为0 。 表2 2 选取不同数目的基因子集所对应的最小m a r g i n 值 i 所选基因数目 1 12 43 05 01 0 02 0 01 0 0 0 【对应的最小m a r g i n 1 9 9 91 9 4 51 6 9 21 6 6 91 4 8 31 3 5 81 3 0 9 从表2 , 2 中，可以看出选取n 个基因比选2 4 个甚至1 0 0 0 个基因，更具有好的推 广能力。此结果与图2 4 得到的结论相同。 2 6 小结 本章提出了一种基于s v m + l e a v e o n e o u t 交叉验证的基因选择方法。该方法， 根据对一个最优分类面得到的m a r g i n 向量，在病类样本向基因子空间投影的同时 m a r g i n 也进行投影。进行基因选择即是寻找某一个基因子空间，在该子空间中 m a r g i n 的投影最大。文中给出了方法的证明，从中可以知道，实际上就是以训练 出的s v m 分类器的权系数作为基因对区分病类的贡献来进行基因选择的。通过 对实际的n c i 数据和m i t 数据进行基因选择，我们可以只选择6 个基因和1 1 个 基因，即可正确诊断相应的不同疾病。表明了本文方法的有效性。 1 6基于s v l 的基因选择 第三章基于s v m m l p 交叉验证的基因选择 在上一章中的，讨论了如何利用s v m 分类器实现两病类问题的基因选择 但是由于现实问题中，病类的数目常常会大于2 ，那么面对多病类问题，该如何 进行基因选择呢? 在上一章的基础上，利用多类s v m 分类器的方法，本章给出 了对于多病类问题的，基于s v m m l p 交叉验证的基因选择方法，并对实际d n a 微阵列数据进行实验，得到了较好的效果。 3 1 多类s v m 分类器简介 由于支持向量机方法是针对两类问题的分类而提出的，如何将两类别分类方 法扩展到多类别分类是支持向量机研究的重要内容之一假定多类别分类问题 ( ( x ，y a x ，尺”，y ，( o ，1 ，k 一1 ) ，j = 1 , 2 ，川) ，其中有历个样本 ( x ，j = 1 , 2 ，嘲，分属于世类y j = 七，k ( 0 ，l ，k 一1 ) ，并且有门 m 。现在实现 s v m 的多类别分类的方法【28 j 一般是将多类问题转化为若各个两类问题的组合。我们 主要简单介绍以下3 种方法。 ( i ) 逐一鉴别法。逐一鉴别法【2 9 l ( o n e a g a i n s t a l lm e t h o d ) 构造k 个s v m 分类器在构造第i 个s v m 子分类器时，用所有的样本来训练第f 个 s v m ，其中第i 类所有样本标记为+ 1 ，其余样本为一l 。测试时，对测试数 据分别计算各个子分类器的判别函数值，并选取判别函数值最大所对 应的类别为测试数据的类别 ( 2 )一一区分法。一一区分法【3 0 】( o n e a g a i n s t o n em e t h o d ) 分别选取2 个 不同类别构成一个s v m 子分类器，这样共有 k x 涨一1 ) 1 2 个s v m 子 分类器。在构造类别i 和类别，的s v m 子分类器时，样本数据集选取 属于类别i 、类别，的样本数据作为训练样本数据，并将属于类别f 的 数据标记为+ 1 ，将属于类别，的数据标记为一1 测试时，将测试数据 对【k ( k 一1 ) 】2 个s v m 子分类器分别进行测试，并累计各类别的得 票，选择得票最高者所对应的类别为测试数据的类别以3 个类别 1 ，2 ，3 ) 为例，构造【3 x ( 3 1 ) 2 = 3 个s v m 子分类器。对于第1 个 s v m 子分类器，类别l 、所对应的样本数据全标记为正，类别2 所对应 的样本数据全标记为负；同样分别用类别l 和类别3 对应的样本训练 第2 个s v m 子分类器；用类别