（控制理论与控制工程专业论文）支持向量机在医学数据分析中的应用.pdf

大连理工人学硕十学位论文 摘要 支持向量机( s v m ) 是基于统计学习理论，借助最优化方法来解决机器学习问题的 新工具，是统计学习理论中的结构风险最小化思想在实际中的体现。由于支持向量机出 色的学习性能，该技术已成为机器学习界的研究热点，并在很多领域( 如语音识别、人 脸图像识别、文章分类等) 得到了成功的应用。 针对支持向量机算法的不足，本文提出了一种预先提取训练样本的方法，将改进的 模糊c 均值聚类( f c m ) 与支持向量机结合起来。通过模糊c 均值聚类对训练样本进 行预处理，提取所有可能是支持向量的样本作为新的训练样本，同时剔除孤立点，从而 提高了分类的精度和训练速度。 本文将改进的算法应用在医学数据分析中，分别是儿童异常步态分类、心电图分类、 心脏病诊断。主要内容如下： ( 1 ) 对儿童异常步态进行分类。通过比较三种不同核函数组成的分类器，得出采 用径向基函数作为核函数的分类效果最好，准确率达到9 7 5 1 。将本算法与其它算法 进行比较，实验结果表明，该算法能够有效地识别步态变化，较好地解决了小样本数据在 步态分类中泛化能力差的问题。 ( 2 ) 对三种心电图进行分类。本文采用数学形态学去除基线漂移；然后采用小波 变换的模极大值检测r 峰值点；考虑到小波包变换的性能，对采集好的心电样本采用小 波包分解提取能量特征；最后使用本算法进行分类，得到的分类结果为9 7 0 3 。 ( 3 ) 对心脏病的诊断。分别采用了常规算法和本算法对u c i 机器学习库中的心脏 病数据进行分类，结果表明，本算法优于常规算法，具有更好的学习能力和泛化能力。 综上所述，改进的支持向量机，提高了分类的准确率，具有可行性和有效性。其优 良特性表明本算法在医疗诊断中具有很大的应用潜力。 关键词：统计理论学习；支持向量机；模糊聚类；医学数据分析 支持向蛩机在医学数据分析中的应用 a p p l i c a t i o no fs u p p o r t v e c t o rm a c h i n ei nm e d i c a ld a t aa n a l y s i s a b s t r a c t s u p p o r tv e c t o rm a c h i n e ( s v m ) i sa l li m p l e m e n t a t i o no fm i n i m i z a t i o np r i n c i p l eo f s t r u c t u r er i s ki ns t a t i s t i c st h e o r y b e c a u s eo fi t se x c e l l e n tl e a r n i n gc a p a b i l i t y ，t h i st e c h n o l o g y i sb e c o m i n gh o ts u b j e c to fr e s e a r c hi nm a c h i n el e a r n i n ga n dh a sb e e nw i d e l yu s e di nm a n y f i e l d s ，s u c ha sv o i c er e c o g n i t i o n ，f a c ed e t e c t i o n s ，e t c an e w a l g o r i t h mh a sb e e np r o p o s e di nt h i sp a p e rb yc o m b i n i n gm o d i f i e df c m a n ds v m b yp r e p r o c e s s i n gt r a i n i n gs a m p l e s ，e x t r a c t i n ga l lp o s s i b l es u p p o r t v e c t o r sa n dr e m o v i n g o u t l i e r s ，t h en e wa l g o r i t h mi m p r o v e st h ea c c u r a c yo fc l a s s i f i c a t i o na n dt r a i n i n gs p e e d i nt h i sp a p e r ，t h em o d i f i e da l g o r i t h mi su s e di nm e d i c a ld a t aa n a l y s i s t h em a i nc o n t e n t s o ft h i sp a p e ra r eo u t l i n e da sf o l l o w s ： ( 1 ) c l a s s i r ya b n o r m a lg a i to fc h i l d r e n b yc o m p a r i n gt h r e ec l a s s i f i e r su s i n gt h r e e d i f f e r e n tk e r n e lf u n c t i o n s ，t h ec o n c l u s i o ni st h a tt h ec l a s s i f i e rw i t hr a d i a lb a s i sf u n c t i o na s k e r n e li st h eb e s t ，w i t ht h ea c c u r a c yo f9 7 51 m o r e o v e r ，b yc o m p a r i n gt h ea l g o r i t h mw i t h o t h e r s ，t h ea c c u r a c yi sb e t t e r s ot h er e s u l ts h o w st h i sm e t h o dc a ne f f e c t i v e l yi d e n t i f yg a i t c h a n g e s i ti sab e t t e rs o l u t i o nt ot h ep r o b l e mo fp o o rg e n e r a l i z a t i o no fs m a l ls a m p l eo fd a t ai n t h ec l a s s i f i c a t i o no fg a i t ( 2 ) c l a s s i f yt h r e ek i n d so fe c g f i r s t l y , t h ee c g i sp r e p r o c e s s e d t h em a t h e m a t i c a l m o r p h o l o g yi su s e dt or e m o v eb a s e l i n ed r i f t s e c o n d l y ，w a v e l e tm o d u l u sm a x i m u mm e t h o di s a p p l i e dt od e t e c trp e a kp o i n t t h i r d l y ，w a v e l e tp a c k e ti su s e dt oe x t r a c te n e r g yf e a t u r e f i n a l l y , t h ec l a s s i f i c a t i o na c c u r a c yc a l lb ea c h i e v e da t9 7 0 3 b yt a k i n gt h ea l g o r i t h m ( 3 ) d i a g n o s e t h eh e a r td i s e a s e t h ed a t af r o mu c im a c h i n el e a r n i n gl i b r a r ya r ec l a s s i f i e d u s i n gt h ec o n v e n t i o n a la l g o r i t h ma n dt h em o d i f i e da l g o r i t h mr e s p e c t i v e l y t h er e s u l ts h o w s t h a tm o d i f i e da l g o r i t h mi ss u p e r i o rt oc o n v e n t i o n a la l g o r i t h m i na d d i t i o n ，c o m p a r i n gw i t h o t h e ra l g o r i t h m s ，t h ea l g o r i t h mh a sb e t t e rl e a m i n gc a p a b i l i t ya n d g e n e r a l i z a t i o nc a p a b i l i t y a saw h o l e ，t h em o d i f i e da l g o r i t h mh a sa d v a n t a g ei nc l a s s i f i c a t i o na c c u r a c y , f e a s i b i l i t y a n de f f e c t i v e n e s s t h ee x c e l l e n tp r o p e r t i e so ft h i sa l g o r i t h ms h o w st h eg r e a tp o t e n t i a lo f a p p l i c a t i o ni nm e d i c a ld i a g n o s i s k e yw o r d s ： s t a t i s t i c a ll e a r n i n gt h e o r y ；s u p p o r r tv e c t o rm a c h i n e ；f u z z yc l u s t e r i n g ； m e d i c a ld a t aa n a l y s i s 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：主蟹避抽2 盔医邀揠盆堑尘鱼幽 作者签名：丞云 日期：一趔壁年堡月j l 日 人连理i ：大学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 童垫鲤扭丕。医盗盘握窆拉生笾廛困 作者签名：塑堕日期：丝堡年垒月丝日 导师签名：盈逝 日期：迦星年监月盟日 大连理t 大学硕十学位论文 1绪论 数据挖掘是从海量的数据中发现对人们有用信息的过程。它的基本任务有很多，如 分类、聚类、关联规则等。支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 算法是数据挖 掘中的一项新技术，主要用于解决分类、回归等问题。本文首先介绍了支持向量机算法 的理论基础、基本原理，然后针对其中存在的一些问题和不足进行改进，提出了支持向 量机改进算法，最后将改进算法用于医学数据分析中，对算法的效率及实用性进行验证。 如下是课题的研究现状以及论文研究的主要内容的简要概述。 1 1 课题的背景 医学信息具有模式的多态性( 纯数据、图像、信号、文字记录等) 、不完整性( 疾病信 息的客观不完整和描述疾病的主观不完整) 、较强的时间性和冗余性。在医学数据的采 集中，通常夹杂着噪声，这些噪声对医生的正确诊断产生了一定的负面影响。以上因素 的存在决定了医学数据的复杂性。面对复杂而独特的医学数据，传统的统计方法只适用 于部分符合统计规律的数据的分析；而对于很大部分非规范化形式的数据，如何找到一 种很好的分析方法，有针对性的进行分析，成为近年来医学数据分析方法的研究热点。 此外，传统的医疗渗断主要依赖于医生的专业知识。然而医学专家知识实际上是一种经 验和规律的总结，它所依据的理论是模糊的、不完全的，背景信息也常常不够清楚，因 此，医学领域的专家知识是不完备的。此外，医学专家的实践是有限的，在实践过程中 医学专家只能获得本领域的部分知识。从数学意义上讲，医疗诊断专家知识具有难以克 服的不完备性。这种不完备性决定了在选择其知识表达和获取方法时，应该以提高知识 的完备性作为标准。 目前的医疗诊断专家系统是将专家的诊断经验转化为规则，只要向系统中输人患者 的症状，就能迅速地做出判断，这样可以减少医生主观判断的失误。但是专家系统的诊 断标准是根据某个或某几个专家的经验柬制订的，缺乏客观性和普遍性。此外，专家系 统的推理规则和结论都是预先设计好的，有些患者的临床表现可能不在此范围内，因此， 有一定的局限性。以上原因决定了这类专家系统的知识获取有较大限制，再加上专家系 统自身存在自学习困难、推理效率较低等原因，使得这类系统只能用于简单的疾病诊断。 数据挖掘技术因为能够对大量的、复杂的数据进行处理，通过某种算法，实现模式的自 动提取。所以采用数据挖掘对医疗数据进行分析，可以挖掘出有价值的诊断规则，从而 排除人为因素的干扰，增强诊断的客观性。这些优势使得数据挖掘技术逐渐成为一种重 要的医学数据分析方法。 支持向量机住医学数据分析中的应用 1 2 国内外研究的状况 首次将数学模型引入到临床医学诊断要追溯到1 9 5 9 年，美国的l e d l e y 等人开创了 计算机辅助诊断的先例，l e d l e y 使用基于布尔代数和贝叶斯定理作为计算机诊断模型用 于诊断肺癌病例，并在1 9 6 6 年，结合上述研究首次提出了“计算机辅助诊断 ( c o m p u t e r a i d e dd i a g n o s i s ) 这个概念【l 】。r m o r p u r g o 和s m u s s i 采用一阶谓词逻辑和产生式规则 两种知识表达方法组建多个数据库，开发出供医生参考的智能诊断决策系统【2 】。f i r r i o l o fj 等人则利用启发式规则进行知识表达，对唾腺肿瘤的组织病理进行分析f 3 1 。 2 0 世纪7 0 年代，我国开始智能医疗领域的研究，最开始常用概率统计法，也就是 数字计算法，从疾病的临床资料( 症状、体征、理化检查) 发生的频率与疾病概率之间 建立明确统计学分析，从而得出最相似的诊断。8 0 年代后，使用疾病的数值表示与专家 的推理相结合的一种方法。两种方法都要通过一定的数学模型来实现，常见的数学模型 有b a y e s 公式、模糊数学及加权求和。9 0 年代以后，支持向量机、决策树等方法也逐渐 应用到医疗领域研究中。 目前人工神经网络在生物医学中的高分子序列分析、图像分析及辅助诊断等许多领 域，取得了很好的效果。相比较专家系统，神经网络有并行处理方式、自学习能力、联 想记忆和容错等优点。特别在分类诊断以及基于分类的智能控制和优化求解方面，神经 网络系统比传统的专家系统性能更为优越。人工神经网络在医疗诊断中主要有以下几个 方面【4 】= ( 1 ) 临床疾病。诊断急性心肌梗塞是最早应用神经网络进行诊断的疾病之一。此后， 陆续将呼吸衰竭、痴呆、精神疾病等疾病应用人工神经网络进行诊断，取得了良好的诊 断结果。 ( 2 ) 波形分析。主要包括心电图的波形分析( 心肌梗塞、心室肥厚、房性、室性异位 节律、房颤、室颤、室扑、s t t 波形改变等) ，肌电图分析、脑电图分析( 老年性痴呆、 瘫痛等) 。 ( 3 ) 影像学分析。应用于x 线的骨肿瘤、胸部及肺部肿瘤珍断、p e t 扫描、核磁共 振扫描等。 但是，人工神经网络存在着过学习问题、知识获取过程可解释性差等局限性，因此 在理论上缺乏实质性进展。在统计学习理论上发展起来的支持向量机凭借其良好性能， 可以解决有限样本学习问题、具有较好的泛化能力，越来越多的应用于智能医学数据分 析领域，成为当前智能医疗诊断研究的热点。 支持向量机是在统计学习理论的基础上发展起来的一种新的通用学习方法。与传统 统计学相比，统计学习理论是一种号门研究有限样本情况下机器学习规律的理论【5 击l 。 大连理【人学硕十学位论文 v a p n i k 从2 0 世纪6 0 年代开始致力于此方面的研究，到9 0 年代中期，随着线性不可分 问题在理论上的解决，统计学习理论更加严密和成熟【7 j 。统计学习理论是建立在严密的 理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方 法纳入其中，有望帮助解决许多原来难以解决的问题( 比如神经网络结构选择问题、局 部极小点问题等) ；同时，在这一理论基础上，发展了一种新的通用学习方法一支持向 量机。支持向量机较好地解决了小样本、非线性、高维数、局部极小点等实际问题。近 年来，支持向量机在模式识别、回归分析、函数逼近、信号处理等领域得到了广泛的应 用，支持向量机的方法根据结构风险最小化原则，尽量提高学习机的泛化能力。它将分 类器的优化问题转化为求解一个凸二次规划的问题，所得的解是唯一的且为全局最优 解，这样就不存在一般神经网络的局部极值问题。 1 3 本文的内容安排 本文研究了支持向量机算法的理论基础和基本原理。在此基础上，分析了现有的支 持向量机算法的不足，对原算法进行了改进，提出了基于模糊聚类的支持向量机算法。 改进的算法在训练分类器之前对训练样本集进行预处理，把那些不可能是支持向量的数 据去掉。这样不仅可以减少训练集的规模，也可以去掉那些孤立点，从而减少了训练时 间，并将改进的支持向量机应用到医疗数据分析中。 本论文第一章，给出了课题的背景、国内外研究状况、本文的内容安排。第二章介 绍了基本的理论知识。第三章针对支持向量机的缺点，把改进的模糊c 均值聚类 ( w f c m ) 和支持向量机结合起来，形成基于w f c m 的支持向量机算法，从而提高分 类的准确率，降低了训练的时间。第四章把算法应用在儿童的步态分类中。第五章探讨 本算法在对心电图分类方面的应用。实验数据取自m i t b i h 心律不齐数据库。首先采 用形态学对心电图滤波，去除基线漂移；再用小波包分解提取能量特征；经过支持向量 机分类后，分类准确率达到9 7 0 3 。第六章是利用本算法对一t l , 脏病数据进行分类，实 验表明可以，得到了较高的分类准确率。最后总结全文、给出展望。 支持向量机在医学数据分析中的应用 2 支持向量机算法 2 1统计学习理论和支持向量机 传统的统计学研究是渐进理论，即当样本数目趋向无穷大时的极限特性，统计学中 关于估计的一致性、无偏性和估计方差的界等，都属于这种渐进特性。然而在实际的问 题中，样本往往是有限的，现有的基于传统统计学的学习方法在有限样本的情况下难以 取得理想的效果。上世纪9 0 年代中期，有限样本情况下的机器学习理论逐渐成熟起来， 形成了一个较完善的理论体系一统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s t l ) 【8 】，为 人们系统地研究小样本情况下机器学习问题提供了有力的理论基础。其主要内容包括以 下四个方面： ( 1 ) 经验风险最小化原则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的理论； ( 3 ) 在这些界的基础上建立的小样本归纳推理原理； ( 4 ) 实现这些方法的原则的实际方法( 算法) 。 支持向量机是在该理论体系下产生的一种新的、非常有力的机器学习新方法，是贝 尔实验室研究人员v a p n i k 等人在统计学习理论三十多年的研究基础之上发展起来的一 种全新的机器学习算法，也使统计学习理论第一次对实际应用产生了重大影响。支持向 量机是基于统计学习理论的结构风险最小化原则的，它将最大分界面分类器思想和基于 核的方法结合在一起，较好地解决了以往困扰很多学习方法的小样本、非线性、过学习、 高维数、局部极小值等实际问题，表现出了很好的泛化能力。目前，支持向量机作为小 样本学习的最佳理论，开始受到越来越广泛的重视。 2 1 1v c 维 v c 维是由v a p n i k 和c h e r v o n e n k i s 提出的，它描述了组成学习模型的函数集的“表 达能力，即函数集合学习性能的指标。函数集的v c 维概念是建立在点集被函数集“打 散”的基础上的，因此首先引入点集被函数集打散的概念。 定义2 1n ( f ，z 。) 。设f 是一个假设集，即由在xcr ”上取值为1 或1 的若干函 数组成的集合。记z ，= “，z 。) 为x 中的m 个点组成的集合。当取遍f 中的所有可 能的假设时，产生的m 维向量( f ( x 。) ，f ( x m ) ) 。定义伊，z 。) 为上述m 维向量中不同 的向量的个数【引。 大连理t 大学硕士学位论文 定义2 2z 。被，打散。设f 是一个假设集，z 卅= x ，x 。) 为x 中的m 个点组成 的集合。如果伊，z 。) = 2 “，称z 。被，打散，或f 打散z 。 例2 1 设x 为2 维空间x = ( 一，x ：) ) 。令f 是x 上的线性指示函数的集合，即 f = f ( x ，口) = s g n ( a 2 x 2 + a l x l + a o ) ) 令z 3 = x l ，x 2 ，x 3 ) cx ，且x 1 , 工2 ，x 3 不共线。现在说明z 3 被f 打散。事实上，对 x ，x 2 黾分别标上“+ 标号或“ 标号，共有2 3 = 8 种标号方式。对每一种标号方式， 都存在厂f ，使得“+ 标号和“”标号被f = 0 分开，如图2 1 所示。图中“ 表 示“+ 标号的点，“o 表示“ 标号的点。这表明n ( f ，z ，) = 2 3 ，即z ，被，打散。 图2 1 f i g 2 1 定义2 3 增长函数。增长函数n ( f ，m ) ，定义为：n ( f ，m ) = m a x n ( f ，z 。) ：z 。cx ) 。 其中z 。= x ，x 。) 是中的m 个点组成的集合，m a x ) 是对这些点跑遍x 而言的。 假设集f 能打散的点的个数越多，表明，的“表达能力 越强。，的v c 维就是使 n ( f ，朋) = 2 “成立的最大的m 值。 定义2 4v c 维。假设集f 是一个由x 上取值为1 或一1 的函数值组成的集合。定 义f 的v c 维为：v c d i m ( f ) = m a x m ：n ( f ，m ) = 2 m ) 。 当 m ：n ( f ，m ) = 2 ”) 是一个无限集合时，定义v c d i m ( f ) = o o 。 由定义2 4 可知，f 的v c 维就是它能打散的x 中的点的最大个数。换句话说，若 存在m 个点组成的集合z 。能被f 打散，且任意m + 1 个点的集合z 州不能被f 打散，则 支持向量机住医学数据分析中的鹰用 f 的v c 维就是m ；若任给正整数m ，都存在聊个点组成的集合z 。能被f 打散，则f 的v c 维就是o o 。 2 1 2 推广误差边界 为构造适合小样本学习的归纳学习原理，可以通过控制学习机器的推广能力来达到 此目的。结构风险最小化归纳过程克服了经验风险最小化的缺点，获得了更好的学习效 果。统计学习理论系统地研究了对于各种类型的函数集、经验风险和实际风险之间的关 系，即推广误差边界【1 0 】。对于两类学习机器的推广能力，统计学习给出了如下估计真实 风险r ( a ) 的不等式，即对于任意口f ( r 是抽象参数集合) ，至少以概率l - r 满足以 下不等式， 尺( 口) r 唧( 口) 4 - 甲( 譬) ( 2 1 ) 其中， 矗 甲( 等) = ， ( 2 2 ) r 唧以) 表示经验风险；甲( 等) 称为置信风险；，是样本个数：参数h 称为一个函数集合 f 的v c 维。 上面不等式说明了学习机器的实际风险是由两部分组成的：一是经验风险( 训练误 差) ；另一部分称作置信范围，它和学习机器的v c 维及训练样本数有关。所以机器学 习过程不仅要使经验风险最小，还要使v c 维尽量小，对未来样本才会有较好的推广能 力，这是结构风险最小化准则的基本思想。 2 1 3 结构风险最小化归纳原理 结构风险最小化归纳原理的基本想法是：如果要求风险最小，就需要不等式( 2 1 ) 中 的两项相互权衡，共同趋于极小；另外，在获得的学习模型经验风险最小的同时，希望 学习模型的推广能力尽可能大，这样就需要h 值尽可能小，即置信风险尽可能小】。 根据风险估计公式( 2 1 ) ，如果固定训练样本数目，的大小，则控制风险只陋) 的参量 有两个：r ) 与h 。其中： ( 1 ) 经验风险依赖于学习机器所选定的函数厂 ，x ) 这样我们可以通过控制口来控 制经验风险。 大连理t = 大学硕士学位论文 ( 2 ) v c 维h 依赖于学习机器所工作的函数集合。为了获得对h 的控制，可以将函 数集合结构化，建立h 与各函数子结构之间的关系，通过控制对函数结构的选择来达到 控制v c 维h 的目的。具体做法如下： 首先，运用以下的方法将函数集合 f ( a ，x ) ，口r ) 结构化。考虑函数嵌套子集的集 合，s lcs 2c cs kc c 最。其中，s = 厂( x ，口) ，口f i ) ，并且有： s + = u ( 2 3 ) p u u ll， 七 结构s 中的任何元素& ( 或一个函数集合) 拥有一个有限的v c 维h 。，且 7 l l h 2 吃( 2 4 ) 如果给定一组样本( x i ，y 。) ，( x 2 ，y ：) ，( _ ，y ，) ，结构风险n 4 , 化原理在函数子 集s 。中选择一个函数f ( x ，口? ) 来最小化经验风险，同时，& 确保置信风险是最小的。以 上的思想就称为“结构风险最小化归纳原理 。如图2 2 所示，已知一个嵌套的函数子 集序列s 。，s ：，s 。，它们的v c 维分别对应为岛，h 2 ，h 。，而且有j i i 。- h 2 ，吃。 图中给出了真实风险、经验风险与置信风险分别与v c 维h 的函数变化关系曲线。显然 随着h 的增加，经验风险r ( 口) 递减，这是因为h 增加，根据v c 维的定义，对应的函 数集合的描述能力增加，学习能力就增强，可以使有限样本的经验风险很快地收敛，甚 l 至于变为o ；根据式( 2 2 ) ，置信风险甲( 等) 随着h 的增加而增加；这样，真实风险r ( a ) 是 f 一个凹型曲线。所以，要获得最小的真实风险，就需要折中考虑经验风险与置信风险的 取值。 根据这一分析，可以得到两种运用结构风险最小化归纳原理构造的学习机器的思 路： ( 1 ) 给定了一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在每个 子集中求取最小经验风险，然后选择经验风险与置信风险之和最小的子集。当子集数目 较大的时候，此方法较为费时，甚至于不可行。 ( 2 ) 构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小的经验 风险( 例如，使得训练误差为0 ) 。然后，在这些子集中选择适当的子集使得置信风险最 小，则相应的函数子集中使得经验风险最小的函数就是所求解的最优函数。支持向量机 算法就是采用此方法构造的学习机器【i i 】。 支持向鼙机在医学数据分析中的麻j 羁 风险 图2 2 结构风险最小化归纳原理 f i g 2 2 s t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e 2 2 支持向量机算法的基本方法 假定大小为z 的训练集为r = ( 石。，y 。) ，( x 2 ，y 2 ) ，( _ ，y ，) ) ，其中t r ”，y ， 1 , - 1 ) ， i = 1 ，。问题是构造一个用于二类分类的决策函数，将测试数据尽可能正确地分类。 下面对训练集为线性或者非线性两种情况分别讨论。 2 2 1线性情况 如果训练集是线性可分的，则存在着超平面： x ) + b = 0( 2 5 ) 使得训练集中的正类输入和负类输入分别位于该超平面的两侧，或者说存在参数对 沏，b ) ，使得： ”= s g n ( ( c o ) + b ) ，i = 1 ，( 2 6 ) 由统计学习理论知，如果训练集没有被超平面错误分丌，并且距超平面最近的样本 数据与超平面之i h j 的距离最大，则该超平面为最优超甲面。为了得到最优超平面，做了 大连理t 大学硕士学位论文 两个与最优超平面平行的超平面，女口图2 3 所示。所以最优超平面的求解需要最大化高， 即最小化崾，为如下的二次规划问题： 砚王n 狮1 2 ( 2 7 ) j f y i ( c o t + 6 ) 1 i = 1 , 2 ，z ( 2 8 ) 则决策函数为： “x ) = s g n ( ( c o 硝+ b 1( 2 9 1 国x + b = - 1 缈x + b = 0 为最优超平面 图2 3 最优分类超平面 f i g 2 3o p t i m a lc l a s s i f i c a t i o nh y p e r p l a n e 口 o 第一类 第二类 支持向量 训练集为线性不可分时，需引入非负松弛变量每，f = 1 , 2 ，。，z ，分类超平面的最优 化问题为： r a 劬i 铊n ! 1 2 + c 善1 轰 s t y i ( c o t x i + 6 ) 1 一誊 当0 ，i = 1 ， ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 支持向鼍机住医学数据分析中的应用 其中参数c 是用来控制训练样本错误的程度。c 越小，被错分的训练样本个数会越 大，而c 越大，得到的超平面会越接近于线性支持向量机，即训练样本被错分的个数会 越少。 采用拉格朗r 乘子法求解这个具有线性约束的二次规划问题，即： 三p ：知缈1 t 2 + c 圭参一圭口；【y i ( 0 9 x i + b ) 一1 + 量卜i 屈磊 ( 2 1 3 ) 其中，口；，屈为拉格朗日乘子口；0 ，屈0 ，令l 对国，b ，f 的一阶导数为零， 得： 磊8 l ：国一圭q y i x i ：0 ( 2 1 4 ) 一= f f l 一 ，f z =tz a 缈 鲁 、 豢：一i 哪：0 ( 2 1 5 ) 铀鲁“2 、7 石8 ；：c 一呸一层：0 ( 2 1 6 ) a 芎t ln、 将( 2 1 4 ) 一( 2 1 6 ) 代入( 2 1 3 ) 中，最终得到对偶最优化问题： m ，i n 去口t q 口一p t 口 ( 2 1 7 ) 口， s t 0 口i c ，i = 1 ，z( 2 1 8 ) y 丁口= 0 ( 2 1 9 ) 最优化求解得到的口i 中，口f 可能是：口f = 0 ；0 口f c ；口，= c ：后两者 所对应的为支持向量( s u p p o r tv e c t o r ，s v ) 。由( 2 1 4 ) 式，可知只有支持向量对缈有 贡献，也就对最优超平面、决策函数有贡献，支持向量由此得名，对应的学习方法称之 为支持向量机( s v m ) 。在支持向量中，所对应的称为边界支持量( b o u n d a r ys u p p o r t v e c t o r ，b s v ) ，实际上是错分的训练样本点，所对应的x i 称为标准支持i f i 量( n o r m a l s u p p o r tv e c t o r ，n s v ) 。根据k a r u s h k u h n t u c h e r 条件( 简称k k t 条件) 知，在最优点， 拉格朗同乘子与约束的积为0 ，即 q ”功。x i ，+ 舅b ：) - 。1 + 参1 = 。 ( 2 2 0 ) 一1 0 大连理r 大学硕十学位论文 对于标准支持向量( 0 0 ，则参= 0 ，因此，对于任一标 准支持向量口j ，y i ( 缈_ + 6 ) 一1 = 0 ，从而计算参数6 为： 相应的决策函数为： ， b = y j - z y j 口f x j _ ( 2 2 1 ) f = l ， 厂( 石) = s 印( 口，y ；碍+ 6 ) ( 2 2 2 ) 式( 2 1 7 ) ( 2 1 9 ) 中的约束条件约束了彩，b 使得经验误差为0 ，同时最小化恻1 2 使v c 维最小。因此，式( 2 1 7 ) ( 2 1 9 ) 的最优化体现了结构风险最小化准则，具有较好的推广 能力。 2 2 2 非线性情况 训练集为非线性时，通过一个非线性函数o ( x ) 将训练集数据x 映射到另一个空间 中。在新的空间中使用线性支持向量机算法。因此，在非线性情况，分类超平面为： c o ( x ) + b = 0( 2 2 3 ) 决策函数为： ( z ) = s g n o ( x ) + b 】( 2 2 4 ) 最优分类超平面问题描述为： m i n l 国nc 窆茧 (225)b 2 ， ” 鲁“ 、 s d y f ( 1 0 ( x f ) + b ) l 一茧( 2 2 6 ) 点0 ，f 1 ，( 2 2 7 ) 类似上一节，得到对偶最优化问题： m a i nj 1 缶l 蔷1 y y j a f i t j k ( x ，) 一再i 口， ( 2 2 8 ) ， 趴ty y i 口f ：0 _ 一ol i f = l ( 2 2 9 ) 支持向蕈机存医学数据分析中的麻瑙 0 口f c ，i = 1 ，z ( 2 3 0 ) 其中k ( 五，z ，) = ( t ) ( 0 ) 称为核函数a 决策函数和参数6 分别为： f ( x ) = s g n ( a ，y ，k ( 五t ) + 6 ) ( 2 3 1 ) i = l ， 6 = y ，一y f 口f k ( x i ，j c j ) ( 2 3 2 ) i = 1 核函数的选择必须满足m e r c e 条件【1 0 】。常见的核函数有如下几种形式：线性核函数 k ，t ) = 一一；多项式核函数k ( x t ，x j ) - - ( x , 一+ 1 ) d ； 径向基核函数 k ( x j ，x j ) = e x p ( 忙x 川2 声2 ) 。 支持向量机的训练过程如图2 4 所示： 图2 ，4支持向量机训练过程的结构图 f i g 2 4 t h ef l o wc h a r to fs v mt r a i n i n g 大连理t 大学硕十学位论文 2 2 3 支持向量机算法综述 支持向量机训练算法中，核心的问题就是要求解一个凸二次规划的优化问题，对于 数据集样本数量很大的时候，二次规划的求解是非常困难的。为了提高计算效率很多研 究者提出了改善支持向量机算法性能的方法，主要分为三类：二次规划算法、分解算法 和增量算法。 ( 1 ) 二次规划求解法 最优化方法中，二次规划已经有较成熟的理论。在s v m 中求解条件极值，通常采 用罚函数和单纯行等方法【1 2 13 1 。 ( 2 ) 分解算法 在学习样本集很大时存储核矩阵需要一个随样本大小二次增长的内存空间，内存大 小限制了计算机对大学习样本集的正常处理d 4 。此外，当训练样本增加时，二次规划算 法也将面临维数灾难。各种分解算法策略由此提出。如c h u n k i n g 算法【l5 1 、序列最小优 化算法( s m o ) 【1 6 】等。 c h u n k i n g 算法：c h u n k i n g 算法( 选块算法) 是一种不完全的分解算法，基本思想 是去掉对应于非支持向量的l a g r a n g e 乘子口，= 0 的那些训练样本，而只对支持向量计算 相应的l a g r a n g e 乘子口f 。由于实际的s v s ( s u p p o r tv e c t o r s ) 是未知的，于是通过引入k k t 条件进行逐步迭代，最终得到全局最优解。c h u n k i n g 算法将矩阵规模由训练样本数目的 平方减少到具有非零l a g r a n g e 乘子的样本数的平方，但这也只是在一定程度上解决了大 数据集的二次规划问题，其方法的目的是要找出所有的支持向量，因而最终需要存储相 应的核函数矩阵，本质上c h u n k i n g 算法中存储空间需求仍受支持向量数目的限制。 序列最小优化方法( s m o ) ：s m o 方法中每一步计算选择一个最小的优化问题来 求解，是分解算法中的特例。两个变量的优化问题可直接通过分析方法解决，相比复杂 的优化器运算，时间效率要高很多，但也产生了优化次数增大的问题。与此同时最优条 件的判断需耗费大量的计算时间。 ( 3 ) 集成多种技术的支持向量机分类算法 除了以上介绍的两类训练算法之外，研究者们也积极的应用先进的计算技术与支持 向量机相结合，综合各种方法的优点，使得支持向量机的性能也得到了显著的提高。 在文献【1 7 】中，先应用处理模糊和不确定性知识能力很强的粗集属性约减理论，减少 非线性映射的输入维数，按最小条件属性集构造新的现场测量数据库，然后再应用s v m 学习数据，建立预测模型，大大提高了支持向量机的训练速度。类似的属性约减方法减 少输入维数的还有遗传算法的特征提取【1 8 1 等。文献提出的加权p c a ( 主元分析1 支持向 支持向每机在医学数据分析中的应用 量机算法，则较好的解决了学习样本数目不平衡对分类性能所带来的影响。这些性能方 面的改进都在不断拓宽支持向量机在实际生活中的应用领域【2 们。 ( 4 ) 多类别分类算法 标准的支持向量机是针对二值分类问题提出来，由二值分类器向多值分类器的推广 则有一对一和一对多【2 1 】两种方法，它们都是组合多个二值分类器进行多类别分类，但有 不可区分的区域出现。文献【2 2 】将决策树学习与s v m 结合来解决多类别分类问题，且不 断完善二叉树的生成方法，取得很好的分类性能，并成功应用于工程实践。 2 3s v m 与神经网络的性能比较 2 。3 1s v m 与神经网络的相似性 ( 1 ) 非线性学习能力 支持向量机和神经网络都具有良好的非线性学习能力。支持向量机理论体系中最早 提出的最大间隔分类器只能进行线性学习，那时的应用还很有局限性。随着理论的逐步 发展，由于核函数的引入，支持向量机通过变换将非线性输入映射到高维特征空间，然 后再进行最优化求解，使得它能有效的处理非线性学习问题。 神经网络由大量神经元组成，一个由非线性神经元互联而成的神经网络自身就是非 线性的，并且非线性是一种分布于整个网络中的特殊性质。正是神经网络的这种非线性 性质，使得它表现出复杂的智能处理能力和非线性处理能力，并成功的应用于多个领域。 ( 2 ) 模型结构 神经网络的模型结构 目前，在人工神经网络的实际应用中，绝大部分的神经网络模型采用b p 网络和它 的变化形式，它也是前向网络的核心部分，体现了人工神经网络最精华的部分。神经网 络是由一个输入层、一个隐含层和一个输出层组成。 支持向量机的模型结构 支持向量机的模型结构与神经网络的模型结构相类似。图2 5 所示，支持向量机相 当于含有一个隐层的三层b p 网络。在支持向量机中的支持向量对应于神经网络的隐含 层。 人连理一l ：大学硕十学位论文 k 图2 5 支持向量机示意图 f i g 2 5 s t r u c t u r eo fs v m 权值 )核函数 输入向量 2 3 2s v m 的优势 ( 1 ) 神经网络的特点 神经网络是在生物神经学研究成果的基础上提出来的，是对人脑神经组织结构和行 为的模拟，它被认为是目前最好的学习算法之一。神经网络通过使用一个很庞大的简单 计算单元间的相互连接来获得好的学习结果。这些简单计算单元也称为“神经元或者 “处理单元”。神经网络的计算能力很明显具有以下两点： 大规模并行分布式结构； 神经网络学习能力以及由此而来的泛化能力。 神经网络具有强大的学习能力，易于实现并行运算，具有自适应性和容错能力，可 以实现联想记忆及聚类等自组织学习。理论上神经网络可以逼近任何的连续函数，如果 隐含层包含足够多的神经元，它还可以逼近任何具有有限断点的非连续函数。但考虑到 相关计算的复杂性问题和神经网络的推广能力，神经网络的尺寸是应该尽可能小的。小 的神经网络具有较快的计算速度，并且构建代价比较便宜，其性能也更容易了解。 但神经网络也具有其不可避免的局限性：网络结构的确定比较复杂，网络结构不合 适容易产生过拟合与欠学习等问题，需要很多的先验知识：基于传统统计学经验风险最 小化原则，在小样本情况下，经验风险与实际风险的差异比较明显，学习效果不佳；采 用梯度( 导数) 技术，局部计算简单，但会出现局部最小值问题。 ( 2 ) s v m 的特点 系统结构简单 支持向量机在医学数据分析中的应用 支持向量机的结构表面上类似与于三层前馈神经网络，但它们有着根本的不同。支 持向量机结构非常简单，不需要过多