（系统工程专业论文）基于多分类器组合的蛋白质结构预测研究.pdf

西北工业大学硕：l 学位论文摘要 摘要 随着人类基因组计划的顺利进展，越来越多的蛋白质序列被测定出来，利 用理论计算方法来研究蛋白质的结构和功能从而指导实验是一项非常有意义的 工作。本文从蛋白质的一级序列出发使用多分类器组合的一些算法对蛋白质结 构进行分类研究，论文主要工作如下： l 、首先对蛋白质相关知识作了简要介绍，在研究蛋白质结构预测问题的过 程中提出了使用多分类器组合算法对蛋白质结构进行分类研究。并在研究支持 向量机等分类器和多分类器组合的基础上，对其类型、算法等进行了分析。 2 、对蛋白子折叠子预测现状进行了研究，提出以支持向量机为基础的多分 类器级联算法来解决折叠子分类问题，实验结果比直接分类提高了近四个百分 点，证明了这种思路的有效性。 3 、分析了多分类器融合算法的理论框架，并采用决策模板算法对蛋白质结 构类的预测问题进行了研究。在此基础上对这种算法进行了三种改进，并设计 了不同的实验来验证算法。实验结果均有不同程度的提高，这说明了算法改进 的有效性，也表明将融合算法用于蛋白质结构类分类研究是一种比较可行的思 路。 4 、分析了多分类器选择算法的理论框架，对基于局部类精度的动态选择算 法和聚类选择算法进行了说明，并将其运用到蛋白质同源寡聚体分类问题中。 实验结果和使用支持向量机进行了比较，表明基于选择算法来预测蛋白质同源 寡聚体，其精度和可靠性都优于后者。 本论文受到西北工业大学研究生创业种子基金资助，基金编号：z 2 0 0 3 0 0 4 8 。 关键词：多分类器组合，蛋白质结构，决策模板算法，折叠子，支持向量机 a b s t r a c 丁 a b s t r a c t t h es u c c e s so fh u m a n g e n o m ep r o j e c tm a k e s t h en u m b e ro f p r o t e i ns e q u e n c e s e n t e r i n gi n t od a t a b a n k r a p i d l yi n c r e a s i n g t h e o r e t i c a lm e t h o dc o m p u t i n g f o rp r e d i c t i n g t h es t r u c t u r ea n df u n c t i o no fp r o t e i na n dg u i d i n gt h e e x p e r i m e n t si sv e r y s i g n i f i c a t i v e w o r k i nt h i st h e s i s ，w en s es e v e r a lm e t h o d so fm u l t i p l ec l a s s i f i e r s c o m b i n a t i o nt oc l a s s i f yp r o t e i ns t r u c t u r e sb a s e do nt h ep r o t e i np r i m a r ys e q u e n c e s t h em a i nw o r ki ss u m m a r i z e da sf o l l o w ： 1 t h ek n o w l e d g ea b o u tp r o t e i ni si n t r o d u c e df i r s t l y d u r i n gr e s e a r c h i n ga b o u t t h e p r e d i c t i n g t h es t r u c t u r eo f p r o t e i n ，t h e m e t h o d so f m u l t i p l e c l a s s i f i e r s c o m b i n a t i o na r ea p p l i e dt 0c l a s s i f yt h es t r u c t u r eo f p r o t e i n a n dw e s u m m a r i z e dt h e m e t h o d sa b o u tm u l t i p l ec l a s s i f i e r sc o m b i n a t i o na n dt h ec l a s s i f i e r ss u c ha ss u p p o r t v e c t o rm a c h i n eb a s e do nt h er e s e a r c h e so f l o t so f s c h o l a r s 2 r e s e a r c h i n ga b o u tm u l t i c l a s sp r o t e i nf o l dr e c o g n i t i o n ，w eu s et h ec a s c a d e a l g o r i t h m sb a s e do ns u p p o r tv e c t o rm a c h i n et oc l a s s i f yt h ef o l d s t h et o t a la c c u r a c y i sn e a r l y4p e r c e n t i l eh i g h e rt h a n d i r e c t c l a s s i l y i n g t h i sr e s u l ts u g g e s t st h et h o u g h t i sf e a s i b l e 3w e i n v e s t i g a t et h et h e o r e t i c a lf r a m e w o r ko fm u l t i p l ec l a s s i f i e r sf u s i o n ，a n d a p p l yt h ed e c i s i o nt e m p l a t ea l g o r i t h m st oc l a s s i f yt h ep r o t e i ns e c o n d a r ys t r u c t u r a l c l a s s e s t h e nt h r e ek i n d so f i m p r o v i n ga l g o r i t h m sa r ep r o p o s e d w e u s et h ed i f f e r e n t e x p e r i m e n t st ov a l i d a t et h e m t h er e s u l t so f t h ee x p e r i m e n t sa r eb e t t e r i ts h o w st h a t t h e a l g o r i t h m s a n dt h e t h o u g h t o f u s i n gm u l t i p l e c l a s s i f i e r sf u s i o nt os o l v e c l a s s i l y i n gt h ep r o t e i ns t r u c t u r a ic l a s s e sa r ee f f e c t i v e 4 r e s e a r c h i n gt h et h e o r e t i c a lf r a m e w o r k f o rc l a s s i f i e rs e l e c t i o n ，w ee x p l a i nt h e a l g o r i t h m so fd y n a m i cc l a s s i f i e rs e l e c t i o nu s i n gl o c a lc l a s sa c c u r a c ye s t i m a t e sa n d t h a to f c l u s t e r i n g a n d - s e l e c t i o na n da p p l yt h e m t oc l a s s i f yt h eh o m o o l i g o m e r i co f t h ep r o t e i n ，w ec o m p a r e 、i mt h ep r e d i c t i o nu s i n gs u p p o r tv e c t o rm a c h i n e t h e r e s u l to ft h ee x p e r i m e n t ss u g g e s t st h a tt h ep r e c i s i o na n dt h er e l i a b i l i t y u s i n gt h e s e l e c t i o na l g o r i t h m sa r eb e t t e rt h a nt h o s e o f u s i n gs u p p o r tv e c t o rm a c h i n e t h i st h e s i si se n d o w e db yt h e p o s t g r a d u a t ec a r v i n go u ts e e df o u n d a t i o no f n o r t h w e s t e r n p o l y t e c h n i c a lu n i v e r s i t y ，n o ，z 2 0 0 3 0 0 4 9 k e yw o r d s ：m u l t i p l ec l a s s i f i e r sc o m b i n a t i o n ，t h es t r u c t u r eo f p r o t e i n ，t h ed e c i s i o n t e m p l a t ea l g o r i t h m s ，f o l d s ，s u p p o gv e c t o rm a c h i n e 两北 i 业人学硕i 学位论文 第一帝绪沦 第一章绪论 随着人类基因组计划( h g p ) 在世界范围内的顺利展开，有关核酸、蛋白 质的序列和结构数据呈指数增长。面对巨大而复杂的数据，运用计算机管理数 据、控制误差、加速分析过程势在必行。从2 0 世纪8 0 年代末开始，生物信息 学( b i o i n f o r m a t i c s ) 逐渐兴起并蓬勃发展。近年来，随着计算机和因特网技术的 广泛应用，更是为生物信息的传递提供了硬件基础和便利条件i 0 2 2 。 1 1 研究背景 生物信息学是在生命科学的研究中，以计算机为工具对生物信息进行储 存、检索和分析的科学。它是当今生命科学和自然科学的重大前沿领域之一， 同时也将是2 l 世纪自然科学的核心领域之一。生物信息学是以生物大分子 ( d a n 序列和蛋白质) 为分析对象，运用信息科学、计算机科学、生物计算数 学、物理科学、比较生物学科学等学科的观点和方法对其进行分析，研究生物 大分子所含的各种信息，特别是d n a 序列中的遗传及调控信息，研究蛋白质 序列与结构及功能之间的关系。生物信息学研究的目的在于通过这样的分析逐 步认识生命的起源、进化、遗传和发育的本质，破译隐藏在d n a 序列中的遗 传语言，揭示人体生理和病理过程的分子基础，为人类疾病的诊断、预防和治 疗提供最合理的和有效的方法或途径。t 0 2 j 。 在这个生物信息学的快速发展时期，引人注目的是结构生物学的发展。近 几年来，测出级序列与解析出空间结构的蛋白质数量呈指数增长。人们对蛋 白质结构和功能的认识曰益加深，尤其是近1 0 年来，无论对蛋白质结构了解的 广度和深度，还是在蛋白质结构研究的方法和手段方面，都有了很大的飞跃。 从信息学角度来看，生物分子是生物信息的载体，如d n a 核苷酸序列对蛋 白质氨基酸序列进行编码，蛋白质序列决定蛋白质结构( 这是目前基本公认的 假设) ，而蛋白质结构又决定了蛋白质功能。归根到底，d a n 序列包含了基本的 生物信息，也就是说，生命的信息存储在d n a 四种字符( atgc ) 组成的序列 中。生物大分子蛋白质则执行着有机体内各项重要的任务，如生化反应的催化、 营养的运输、信号的识别与传递等。 两北工业大学硕_ 二学位论文第一章绪论 蛋白质是生命科学的重要研究对象，基因是生物细胞中的遗传物质，基因 必须以蛋白质形式表达出来，才能显示出生物的各种遗传性状。因此，蛋白质 的研究在生命科学中是至关重要的。从细胞分裂到细胞运动，从代谢到免疫， 已知的生物功能没有个是离开蛋白质能实现的。一个典型的细胞可能含有l o 万种左右不同的蛋白质，在细胞的生命中每一种蛋白质都有其自己的使命。研 究蛋白质的功能需要深入了解他们的结构，特别是空间结构( 三维结构) ，因 为结构决定功能。生命的功能和它的结构是同一的。有什么样的结构必定有什 么样的功能，反之亦然。只有了解了蛋白质的结构，才能对现有蛋白质进行结 构改造，从而有目的地改变其功能，例如设计艾滋病病毒转蛋白酶抑制剂，就 必须对该酶蛋白质的结构有相当的了解。当今，如果没有蛋白质三维结构的确 切知识，很难对生物学很多领域进行深入的研究。蛋白质空间结构已经成为生 物学家迫切要求了解和掌握的知识了“”“。 1 2 蛋白质结构预测主要方法 目前，研究蛋白质空间结构的试验方法主要有x 射线晶体学方法、多维核磁 共振( n m r ) 等方法“。x 射线晶体学方法是迄今为止研究蛋白质结构最有效的 方法，但是所需的蛋白质晶体难以培养，且晶体结构测定台勺周期较长。多维核 磁共振方法可以直接测定蛋白质在溶液中的构想，但由于对样品的需要量大、 纯度高，被测定的蛋白质的分子量一般不超过2 万等，因而也受到很大限制。虽 然x 射线晶体学和n m r 技术大规模的应用，使得蛋白质结构测定方面有了显著的 进步，但蛋白质结构测定的数目是远远不能与所确定的序列数目相比拟的。例 如截止2 0 0 3 年l o 月蛋白质序列数据库s w i s s p r o t 已存储了大约1 3 5 ，8 5 0 个记录 ( 冗余度较低) ，蛋白质结构数据库p d b 中测定的蛋白质结构大约为2 2 。8 l o 个， 而且p d b 数据库中存在大量的冗余。与此相似的是，由于缺乏高度自动化地确定 蛋白质功能的技术，蛋白质功能所能确定的数目与序列之间的差距亦越来越大。 所有蛋白质的空间结构和功能都通过实验测定是不现实的，因而有必要发展一 种可靠的理论预测方法，借助于计算的手段来得到某种程度的解决。也就是从 蛋白质的一级序列出发预测蛋白质的空间结构和功能；分析预测基因在翻译表 达方面的调控机制；以及建立细胞水平的新陈代谢模型等等。 西北丁业大学硕士学位论文 第一章绪论 1 9 6 1 年，a n f i h e n 等人通过实验证明蛋白质的氨基酸序列决定其三维结构 这是分子生物学的一个中心定理：序列规定构想。而且随着人类基因组计划在 世界范围内的顺利展开，人类已获得大量以测定氨基酸序列的蛋白质，其增长 速度异常迅速，因而利用蛋白质的一级结构所提供的氨基酸序列信息来进行高 级结构预测是目前比较流行和经济的方法。比对数据库中已知结构的序列和线 串法是两种主要方法，前者通常假定两段被比较的蛋白质序列的氨基酸残基接 近水环境的情形下是保守的，且在蛋白质结构相似而序列相似程度较低时不理 想：后者则把残基环境中的疏水作用相加，因而效果较好，但对于多结构域的 蛋白质序列目前很难得到有意义的结果“”1 。 c h r i sh q d i n g “等应用支持向量机和神经网络等方法对多类蛋白质折 叠进行了较成功的预测( 测试蛋白质序列与训练蛋白质序列的相似性小于3 5 9 6 ) ， 但他们仅考虑了每一氨基酸的成分、预测的蛋白质二级结构和一些物理、化学 特性，而没有考虑氨基酸的领域成分的影响：k l e i ne 刚雨 c h o u ”1 邮等考虑了氨基 酸的相互作用，迸一步改善了预测精度。秦红珊“等又运用协方差规划法对蛋 白质结构类进行了预测，得到了较好的结果。 1 3 常用的蛋白质结构与序列数据库简介 数据库是一切生物数据库工作的出发点，大量的数据库集中在些国家或 国家的生物信息中心，例如，欧洲生物信息学研究所( e u r o p e a n b i o i n f o r m a t i c s l n s t i t a r e ，e b i ) 所维护的e m b i 数据库( h t t p ：w w w e b i a c u k e m h ) ，美国 国家生物技术信息中心( n a t i o n a lc e n t r a lf o rb i o t e c h n o l o g yi n f o r m a t i o n ， n c s i ) 的o e n b a n k 数据库( h t t p ：w w w n c b i n l m n i h g o v ) 等。 生物信息学数据库主要分为两大类：基本数据库和二级数据库。基本数据 库主要包括原始数据库，例如d n a 序列、蛋白质序列和蛋白质结构等信息。 二级数据库则主要是对基本数据库进行分析、提炼加工后而形成，旨在使得基 本数据库更便于生物学家使用。 在这里我们首先对数据库做一简单介绍，文中用到时，我们会详细说明。 两北t 业大学硕【学位论文第审绪论 1 p d b ( h t t p ：w wr c s bo r g p d b ) 蛋白质结构数据库( t h ep r o t e i nd a t ab a n k ，p d b ) 由美国新泽西州立大学、 加州大学圣迭戈超级计算中心和国家标准技术研究所等三家单位合作建立的结 构生物信息学联合研究实验室( t h er e s e a r c hc o ll a b o r a t o r yf o rs t r u c t u r a l b i o i n f o r m a t i t s ，r c s b ) 维护，是收集蛋白质3 d 结构最为著名的数据库。它提 供蛋白质除氢原子之外的所有原子的坐标，此外还给出蛋白质的结构注释、图 像、氨基酸序列、二级结构等信息。许多蛋白质结构数据库都是依据p d b 的数 据来构建的。 2 s c o p ( h t t p ：s c o p m r c l m b c a m a cu k s c o p ) 蛋白结构分类数据库( s t r u c t u r a lc l a s s i f i c a t i o no fp r o t e i n s s c o p ) 是英国医学研究委员会( m e d i c a lr e s e a r c hc o u n c i l ，m r c ) 属下的m r c 分子生物 学实验室和蛋白质工程研究中心( m r cl a b o r a t o r yo fm o l e c u l a rb i o l o g ya n d c e n t r ef o rp r o t e i ne n g i n e e r i n g ) 开发维护的，它是通过手工比较辅以自动计 算方法，对已知结构的蛋白质进行相似性分析和进化同源性分析而建立的蛋白 质结构分类数据库。 3 c a l h ( h t t p ：v a m b i o c h e m u c l a c u k b s m c a t h ) 蛋白质结构与功能关系分类数据库。这是个把蛋白质结构域按四个层次进 行分类的数据库。这四个层次是“类别”( c l a s s 即c ) ，“构架”( a r c h i t e c t u r e 即a ) ，拓扑( t o p o l o g y 即t ) ，以及同源超家族( h o m o l o g o u ss u p e r f a m i l y 即 h ) 。库名即来自这四个字母。 4 p i r ( h t t p ：w w w - n b r f g e o r g e t o w n e d u p i r ) 蛋自质信怠源( p r o t e i ni n f o r m a t i o nr e s o u r c e ，p i r ) 数据库是美国乔治敦 大学医学中心的国家生物医学研究基金会( n a t i o n a lb i o m e d i c a lr e s e a r c h f o u n d a t i o n ，g e o r g e t o w nu n i v e r s i t ym e d i c a lc e n t e r ) 建立的蛋白质序列数据 库，主要用于研究蛋白质的进化。数据库对序列的注释被分为4 个层次：p i r i p i r 4 。p i r i 为注释详尽的已验证的蛋白质序列：p i r 2 为含有未定的冗余序列： p i r 3 中的序列既未注释，也未检验：p i r 4 为包含从其他渠道所获得的序列。 p i r p s d 是收集蛋白质序列最多的数据库。 西北工业大学硕上学位论文第一章绪论 5 s w i s s p r o t ( h t t p ：w w w e x p a s y o r g s p r o t s p r o t t o ph t m l ) s w i s s p r o t 数据库由瑞士日内瓦大学( 6 e n e v e s eu n i v e r s i t y ) 和欧洲分子 生物学实验室( e u r o p e a nm o l e c u l a rb i o l o g yl a b o r a t o r y ，e m b l ) 合作创建，目 前由瑞士生物信息学研究所( s w is sb i o i n f o r m a t i c si n s t i t u t e ，s b ) 和欧洲 生物信息学研究所( e u r o p e a n b i o i n f o r m a t i c sl n s t i t u t e ，e b i ) 共同维护。 s w i s s p r o t 数据库的特点是给蛋白质序列以详细的数据注释信息，包括基因名 称、物种来源、分类学位置、蛋白质功能说明、结构域、翻译后修饰、突变体、 与其他数据库的链接、关键词、特征表等信息。而由核酸序列翻译得到的蛋白 质序列则收集在s w l s s - p r o t 下的t r e m b l 数据库中。s w i s s p r o t 所收录的序列 较p i r 为少，但它是注释最为详尽的数据库。 6 p i r n r l 3 d ( h t t p ：w w w - n b r f g e o r g e t o w n e d u p i r m v w d b i n f o n r l 3 d ) p i r - n r l 3 d 是已知结构的蛋白质序列数据库，它将p i r 数据库与p d b 结 构数据库关联起来，包含了二级结构、活性位点、结合位点、修饰位点等结构 和功能的信息。它是由美国乔治敦大学医学中心的国家生物医学研究基金会 ( n a t i o n a lb i o m e d i c a lr e s e a r c hf o u n d a t i o n ，g e o r g e t o w nu n i v e r s i t ym e d i c a lc e n t e r ) 维护的。 1 4 本文主要研究内容 随着人类基因组计划的顺利进展，越来越多的蛋白质序列被测定出来，而 通过实验所能确定了结构与功能的蛋白质序列数目相对较少，因而两者之间的 差距变的越来越大。通过实验确定蛋白质的结构和功能费时、费力、耗财，且 实验中可能还会遇到一些目前无法解决的困难，由此利用计算的手段来研究蛋 白质的结构和功能将扮演重要的角色，利用理论计算方法从序列中提取尽可能 多的信息来指导实验也是项非常有意义的工作。 然而传统的只使用一种技术手段来进行识别仍然存在着许多缺点。在蛋白 质结构分类预测中由于样本类别数太多，仅仅使用一个分类器来识别，需要大 量的口l 练样本，而且存在着结构复杂，计算量大的缺点。为了很好地处理应用 中出现的各种问题，本论文尝试用多分类器组合( c m c ) b 。”。“_ “ ”彰的方法来 两北t 业人学硕士学位论业 第一章绪论 解决这些问题。它利用了不同类型的分类器和特征之间的互补，为获得高性能 的系统提供了新的思路。 目前，基于多个分类器组合进行识别已经被许多应用领域所采纳，特别是 在手写体数字和文字的识别方面”1 ，另外，在人脸识别、语音识别等领域也得到 了广泛的应用。3 7 “蚓。这些应用集中表现在以下三种情况： ( 1 ) 样本不同的特征具有不同的表达形式。例如有些特征是连续值，有些 特征是二进制值，有些特征是模糊语句。如果此时只使用一个分类器来进行分 类识别，则必须要将所有的特征转换成一种统一的形式，再进行分类。而使用 多个分类器时，可以用每个分类器分别处理具有不同表达形式的特征，然后再 通过一个组合器来将它们各自的分类输出组合起来，这样就克服了要进行特征 转换的缺点。 ( 2 ) 当样本的特征具有不同的物理意义或是来自不同的渠道时，这时应该 使用多分类器，而不是使用单分类器来进行识别。假设一个待识别样本的所有 特征都是连续值的模式识别问题，它的某些特征表达了样本在声音方面的属性， 而另一些特征表示样本的外貌特征。如果要使用单分类器进行识别，则必须先 将它们组合成一个矢量，然后进行归一化，但这种归一化常常是很难的。如果 采用多个分类器，它们分别将样本在声音方面的特征和外貌方面的特征进行归 一化并进行分类，再对分类器的输出进行融合，则问题常常变得简单的多。 ( 3 ) 当样本具有非常多的特征时，在高维输入矢量上进行模式识别，不仅 会加大计算的复杂度，而且对识别结果具有一定的负面作用采用多个分类器 分别在不同的样本特征子集上进行识别，再使用组合器将之组合到一起，是一 种好的方法。 基于这些优点，本文将尝试采用多分类器组合算法从蛋白质的一级序列出 发，研究蛋白质结构，包括蛋白质结构类，蛋白质折叠子和蛋白质四级结构的 分类预测，其主要研究内容如下： 1 分析了多分类器组合算法中的级联算法“”3 ，做出了详细的讨论，并将 其用到蛋白质折叠子分类研究中，折叠子分类问题属于多类( 2 7 类) 问题，我们 使用级联算法将其分为两次预测，取得了不错的效果； 西北工业人学硕士学位论文 第一章绪论 2 详细分析了多分类器融合算法的理论框架和常用规则j ，主要研究了 决策模板融合( d t ) “”“1 算法。在d t 算法研究的基础上，我们给出了三种不同 的改进，并设计了不同的实验( 实验主要是针对蛋白质结构类预测) ，来对d t 算 法和各种改进进行验证，实验证明了算法的有效性，也为蛋白质结构类的预测 提供了一种新的思路。 3 首先分析了多分类器选择的理论框架，做出较详细的证明n 5 ”- t 7 3 。在此 基础上，给出了基于局部类精度的分类器选择算法“1 1 ”1 。然后介绍了蛋白质 四级结构的概念和研究情况，并将上述算法运用到蛋白质四级结构预测中。最 后和基本的单分类器算法结果做比较，实验说明了这种思路的可行性。 1 5 论文结构安排 基于前面的讨论，论文个章节的内容安排如下： 第一章介绍论文的研究背景： 第二章简要分析了多分类器组合的情况，从输出信息到组合算法都进行了研究： 第三章首先讨论了多分类器级联算法，然后将其运用到蛋白质折叠子预测当中： 第四章是多分类器融合算法研究及在蛋白质结构类预测中的应用： 第五章是多分类器选择算法研究及在蛋白质四级结构分类的应用； 第六章总结和展望，主要说明论文研究中的闯题和以后的改进方向。 本论文主要研究组合算法和应用，研究重点集中在第三、四、五章。 西北丁业大学硕士学位论文第二章支持向量扫i 和多分类器组合 第二章支持向量机和多分类器组合 本文在运用多分类器组合算法来解决蛋白质结构预测问题时，使用的成员 分类器以支持向量机为主，所以在本章首先对支持向量机和其他分类器进行说 明，然后概述多分类器组合的情况。 2 。1 支持向量机 支持向量机( s v m ) “7 ”1 是近年来国际上新兴的一种机器学习方法，由于 出色的学习性能，该技术已成为当前的研究热点。且已被成功地应用于生物信 息学中：基因微阵列表达模式姗3 、转录起始点6 0 1 、蛋白质家族。、蛋白质亚细 胞定位6 ”“、蛋白质折叠子识别i s 和蛋白质四级结构汹 “6 7 1 等方面。 支持向量机( s v m ) 是 v a p n i k 。7 j ”_ “7 3 等人根据统计 学习理论提出的一种新的机 器学习方法，其最大特点是根 据v a p n i k 的结构风险最小化 原则，尽量提高学习的泛化能 力，即由有限的训练集样本得 到的小误差仍能够保证对独 立的测试集小的误差。另外， 由于支持向量机算法是一个 凸优化问题，因此局部最优解 h 1 1 2 图2 1 线性可分情况下的最优分类线 一定是全局最优解，可防止过学习，这些特点是其它学习算法，如神经网络学 习算法所不及的。应用支持向量机进行分类研究的基本思想可简述为：首先将 输入空间的样本通过某种非线性函数关系映射到一个特征空间中( 维数可能较 高) ，在此特征空间中构造最优分类超平面使两类样本( 可推广到多类样本) 在 此特征空间中可分。映射函数仅与输入空间的低维输入向量和特征空间的点积 西北工业大学硕： 学位论文 第一章 支持向量机和多分类器组合 有关，此点积可用输入空间的核函数来替代，这样就可以构造出特征空间的分 类超平面，而不必清晰地描述特征空间，同时还可避免“维数灾难”，从而解决 高维特征问题。下面为支持向量机的简要描述，详细的描述可查阅文献。8 。“1 。 对于线性可分情况，支持向量机的基本思想可用图2 1 的两维情况说明。 图3 3 中，实心点和空心点代表两类样本，h 为分类线，h 、心分别为过各类中 离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔 ( m a r g i n ) 。所谓最优分类线就是要求分类线不但能将两类样本正确分开( 训练 错误率为0 ) ，而且使分类间隔最大。分类线方程为 x - w + 6 = 0f 2 1 1 我们可以对它进行归一化，使得对线性可分的样本集( 置，m ) ，i = 1 , 2 ， x r “，y ( + l ，- l ，满足 m 【( w x 。) + 6 】一1 0 ， 此时分类间隔等于2 j 帝5l ，使间隔最大等价于使 1 甲最小。满足条件 ( 2 2 ) 且使划w l f 2 最小的分类面就叫做最优分类面( o p t i m a l s e p a r a t i n g h y p e r p l a n e ，o s h ) ，h 、h 。上的训练样本点称为支持向量。 利用l a g r a n g e 优化方法可以把上述最优分类面问题转化为其对偶问题”1 ， 即：在约束条件 咒呸= o ( 2 - 3 a ) 口0i = 1 ，2 ，( 2 - 3 b ) 下对求解下列函数的最大值： q ( a ) ：圭q 一去圭o g i c t j y , y j ( x 。一) ( 2 4 ) f = l i j = l a ，为原问题中与每个约束条件( 2 2 ) 对应的l a g r a n g e 乘予。这是一 个不等式约束下二次函数寻优的问题，存在唯一解。容易证明，解中将只有 西北丁业大学硕上学位论文第二章立持向量机和多分娄器组台 一部分( 通常是少部分) 。，不为零，对应的样本就是支持向量。解上述问 题后得到的最优分类函数是： 厂( x ) = s g n ( w x ) + 6 ) = s g n 西咒( x ，x ) + b ( 2 5 ) l ，o jj 式中的求和实际上只对支持向量进行。b 是分类阈值，可以用任一个支持 向量( 满足( 2 - 2 ) 式中的等号) 求得，或通过两类中任意一对支持向量取中值 求得。 显然，上面的方法在保证训练样本全部被正确分类，即经验风险为零的前 提下，通过最大化分类间隔来获得最好的推广性能。对于线性不可分情况，如 果希望在经验风险和推广性能之间求得某种均衡，可以通过引入正的松弛变量 ( s l a c kv a r i a b l e s ) 磊( f = 1 , 2 ，f ) 来允许错分样本的存在，于是约束( 2 2 ) 变为： ”( w + 6 ) l 一苣磊o ，v i ( 2 6 ) 1 而在目标函数剖叫1 2 中加入惩罚项c 等，最优分类面问题就可以写成： 1 2 1 在约束条件 m ( w ，t ) + 6 卜1 + 毒0i = 1 , 2 ，- 一， ( 2 7 a ) 掌，0 ，i = 1 , 2 ，? ( 2 7 b ) 下最小化：t i p t l 2 + c 等( 2 - 8 ) i = l 其中误差权重c 为某个指定的常数，它实际上起控制对错分样本惩罚程度 的作用，实现错分样本的比例与算法复杂度之间的折衷。对于任何正数k ，优 化问题是一个凸优化问题。当k = 1 ，k = 2 时，优化问题实际上为二次型寻优问 题。训练样本全部被正确分类，即经验风险为零的分类间隔称为硬分类间隔 ( h a r dm a r g i n ) ，而允许有错分样本存在的情况称为最优分类超平面的软分类 间隔推广( s o f tm a r g i ng e n e r a l iz a tio n ) 。 对于非线性问题，可以通过非线性变换转化为某个高维空间中的线性问题， 在变换空间求最优分类面。这种变换可能比较复杂，因此这种思路在一般情况 西北工业大学顶十学位论文第二章支持向量机和多分类器组台 下不易实现。但是注意到，在上面的对偶问题中，不论是寻优目标函数( 2 4 ) 还 是分类函数( 2 5 ) 都只涉及训练样本之间的内积运算( x 工，) 。设有非线性映射 中：r ? h 将输入空间的样本映射到高维( 可能是无穷维) 的特征空间h 中。当在特征空 间h 中构造最优超平面时，训练算法仅使用特征空间中的点积，即中) ， 而没有单独的o 0 出现。因此，如果能够找到一个函数k 使得： 毅墨，而) 2 m o d 。巾( 劫( 2 - 9 ) 这样，在高维空间实际上只需进行内积运算，而这种内积运算是可以用输 入空间中的函数实现的，我们甚至没有必要知道变换中的形式。根据泛函的有 关理论，只要一种核函数聪x i ，勒满足m e r c e r 条件m 3 ，它就对应某一变换空 间中的内积。因此，在最优分类面中采用适当的内积函数麒置，x j ) 就可以实 现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时分类函数也 变为： m ) ：。g n 佳茸y 取，卅6 l ( 2 1 0 ) 这一特点提供了解决算法可能导致的“维数灾难”问题的方法：在构造判 别函数时，不是对输入空间的样本作非线性变换，然后在特征空间中求解；而 是先在输入空间比较向量( 例如求点积或是某种距离) ，然后再对结果作非线性 变换”“。这样，大的工作量将在输入空间而不是在高维特征空间中完成。 常用的核函数有： 多项式核函数：世g ，_ ) = k t + 1 y ( 2 - 1 1 ) 径向基核函数( r b f ) ：世一, x j ) = e x p y 忙一x u 2 ) ( 2 - 1 2 ) s i g m o i d 核函数：k ( ，一) = t a n h b ( x j x j ) + c l ( 2 - 1 3 ) 本文用j o a c h i m s 汹，7 2 t7 ”5 7 们编写的s v m l 程序，该程序是由c 语言编写 的，对于学术用途者可免费从h t t p ：a i s g m d d e t h o r s t e n s v ml i g h t 网 一1 1 两北t 业大学坝i 。学位沦立 第二二鲞支持向量机和多分类器组合 2 2 其他分类器 在本文中除使用支持向量机( s v m ) 外，还使用过贝叶斯分类器( n b ) ，二 次? - f j 另r j 式法( q d ) ，k 近邻算法( k n n ) ，神经网络( s i g m o i d ) ( n n ) ”，c 4 5 决策树“”“等分类器，这些分类器我们分为两类，其中支持向量机、k 一近邻、 神经网络和c 4 5 决策树属于参数型分类器，即在使用时我们要特别注意分类器 的参数选择，因为这直接影响到分类性能。而贝时期分类器和二次判别式则属 于非参数型。以下我们对这些分类器做一说明。 贝叶斯分类器：在本文实验中我们用到的是朴素贝叶斯( n a v i eb a y e s ) 分类 器。这种分类器是基于一个简单的假定：在给定目标值时特征( 属性) 之间相互 条件独立a 其所使用的方法是：出m = a r g m a x p ( a ) ，) l - l p ( a 。i o , ，) ，其中，表 示贝叶斯分类器输出的目标值，口，表示样本的特征( 属性) 。 二次判别式法：y - * 9 9 l 叶斯二次分类器旧 84 。t 2 7 ，对于c 类问题，具体算法 如下：设钡4 试样本为鼻，其判别函数为： f ( x ，x ，) = d 2 瞳，x ，) + i n | c ，f p = l ，c( 2 1 4 ) 其中，爿一表示各类决策向量的均值，c p 是各类的协方差，可以通过训练 样本统、z 。一i 9 ，d 2 扛，_ ，) = 瞳一卫，( c ，) 1 瞳一x 一) 。 于是对给定的测试样本可以根据最小b a y e s 决策函数进行判定： f 忸，肖) = 坛以妒伍，x l l f 扛，x 2 l ，f 伍，) 。 着r = p ，= 1 , 2 ，c ) ，则将待测试样本判为p 类。 k 近邻算法：这个方法是：在n 个已知样本中，找出未知样本x 的k 个近 邻，看这k 卜近邻多数属于哪一类，就把x 归为哪类。在使用时要注意参数 k 的选择，对于两类问题在使用时，一般取奇数。 神经网络：在实验中，我们用到的是反向传播算法( b p ) ，具体可见文献，我 们介绍其步骤如下：( 1 ) 选定权系数初值；( 2 ) 正向计算隐层和输出层各结点 西北工业大学颧上学位论文第二章支持向量帆和多分类_ i 组合 输出；( 3 ) 反向计算误差梯度；( 4 ) 调整权值；( 5 ) 重复2 、3 、4 步直到样本 输出误差足够小。使用时，需要调整的参数有：网络节点、初始权值、学习速 率、允许误差、迭代次数等。在实验中，我们将具体说明。 c 4 5 决策树：决策树方法起源于概念学习系统。决策树是由一个根节点， 若干的叶子节点和非叶子节点构成的二叉树或多叉树。c 4 ，5 决策树是i d 3 算法 的改进，在这里我们不再详细描述i d 3 和c 4 5 决策树的算法，只对c 4 5 对i d 3 的扩展进行说明，c 4 5 在以下几个方面提高了i d 3 算法的性能：( i ) 可以处理 连续值属性：( 2 ) 可以处理缺省值；( 3 ) 隐入修改方法；( 4 ) 可以生成分类规则等。 在实验中需要调整的参数有：修剪次数和叶子数。 我们以后用到的成员分类器( 单分类器) 以支持向量机为主，这主要是考虑 到其出色的学习性能和在生物信息学中的使用情况。在讨论多分类器组合算法 时，我们讨论了多种分类器单特征的情况，但主要集中在多种特征一种分类器 在分类器组合时的算法研究和应用上。 单个分类器，我们使用的是s i p i n a 软件的研究版，对于学术用途者可以免 费从h t t p ：e r i c u n i v l y o n 2 f r “r i c c o s i p i n a h t m l 网址上下载。 2 。3 多分类器组合( c m c ) 对于模式识别问题，最主要的评价标准是看它的识别性能如何。为了实现 尽可能好的识别性能，传统的做法是对于目标问题，分别采用分类器实现，然 后选出其中一个最好的分类器作为最终的解决方案“。但是，研究发现，尽管 其中一个分类器有不错的分类性能，但是不同的分类器产生的误分类集合是不 完全重叠的；同时，还发现对于不同的特征描述这种情况尤其明显。这表明不 同的分类器、不同的特征对于分类的模式有着互补信息，可以利用这种互补信 息来提高识别性能“2 0 扎”6 ，”7 ”。 这种研究发现激发了人们对于多分类器组合的研究兴趣，即把多个分类器 联合起来用于模式识别。同时，也在许多实际应用上取得了很好的结果( 如手写 体识别、时间序列预测、卫星图像的缝表辨识等) 。k i t t l e 等人 l 2 1 对多分类组 合框架进行了分析，并给出了组合理论框架。a 1 i 等“指出当各个分类器有着 西北 ：业大学碗士学位论文第二章支持向量机和多分类器组合 显著不同时，分类器集成的作用更为明显，如采用不同的特征、不同的训练集 合，这样由于不同的分类器采用的分类曲面族不一样，所用的特征也可以不同， 具备相当的互补性。如果能够把不同分类器的优点利用起来，并且抑制他们的 缺点，则这种识别系统能够达到相当高的精度“”j 0 9 。 多分类器组合( c m c ) 不仅可以提高分类的精确性和泛化能力，而且可以提高 时间和空问上的效率，将一个大的特征向量空间划分为几个较小的特征空间后， 在每个小特征空间上构造一个分类器，再将这些分类器组合成一个较大的分类 器比在整个特征空间构造个