（运筹学与控制论专业论文）应用于心电图分类的knn和svm分类器研究.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果据我所知，除文中已经注明引用的内容外，本论文不包含其他 个人已经发表或撰写过的研究成果对本文的研究做出重要贡献的个人和 集体，均已在文中作了明确说明并隶示谢意 作者签名：! 控丛鸯日期 学位论文使用授权声明 业厂。7 本人完全了解华东师范大学有关保瞽、使用学位论文的规定，学校有权保留学位 论文并向国家主管部门或其指定机构送盔论文的电子版和纸质版有权将学位论文用 于非赢利目的的少量复制并允许论文进，。学校图书馆被查阅有权将学位论文的内容 编入有关数据库进行检索有权将学位i i ? 文的标题和摘要汇辐出版保密的学位论文 在解密后适用本规定 学位论文作者签名： 日期： v 袭右东 日期：弘即，z ，) 摘要 分类器是模式识别系统的重要组成部分也是机器学习的重要研究领域。支持向量机 ( s u p p o r tv e c t o rm a c h i n e ) 是一种新的分类器，刍于能够较好的解决小样本学习问题并具有较 强的泛化能力，使其迅速成为目前模式识别锈_ 域的研究热点。本文主要研究对象是k n n 和 s v m 两种分类方法。一方面进一步揭示s v i a 的分类机理，针对其在应用中的一些限制提 出和k n n 相结合的改进算法k n n - - s v m ，石广了s v m 的应用范围。另一方面运用k 近 邻法n e a r e s tn e i 曲b o r ) 、s v m 和k n n - - s v v i 对心电图信号进行分类，并对分类结果进行 比较研究。本文的研究工作主要包括以下几7 湎i ： 1 、一种适合心电图特点的数据训练方式 根据心电图数据有八个导联且反映心电b 】量在不同方向上的情况的特点，发现一种不同 以往的对训练样本进行运用的方法：对所有一c 电图按照导联分段划分，样本集每次只取对应 的一个导联进行训练和测试。八个导联一一掣习，这样得到八个输出值，然后对每“测试样 本综合八个导联的判断值，由多数的判断值来决定最终的分类结果。我们把上述这种方法称 作“八个导联并联的学习方式”。以往常见的方式有：把每个心电图的八个导联串联作为样 本进行学习；或只挑取一个导联作为样本进行学习。实验表明，使用八个导联并联的学习方 式比其它两种学习方式，无论是用k n n 还是s 分类器，在提高正确率和降低对参数的敏感 性方面都非常明显。究其原因，跟串联方式相比，我们把样本在特征空间的维数从3 4 4 维降 低到4 3 维；跟只取一个导联作为样本的方式相比，我们充分利用了所有的医学特征，并且 分散了只依靠一个导联作决定的风险和错误b 1 素，结果证明这是一个值得运用的数据处理方 式。 2 、k n n s v m 分类器算法研究； 支持向量机利用靠近边界的少数向量构：j 一个最优分类超平面。在训练分类器时，s v l v l 的着眼点在于两类的交界部分，那些混杂在男一类中的点往往无助于提高分类器的性能，反 而会大大增加训练器的负担，同时它们的存在还可能造成过学习，使泛化能力减弱，为了改 善支持向量机的泛化能力，本文提出了一种ec 进的分类器算法一k n n s v m ：它先对训练 集进行修剪，根据每个样本与其最近邻的k7 p ( kn e a r e s tn e i g h b o o 类标的异同决定其取舍， 然后再用s v m 训练得到分类超平面。实验表明，k n n s v m 相比s v m 在分类正确率，分 类速度以及适用的样本规模上都表现出了一i ! 的优越性。 关键词：模式识别、支持向量、k 近邻分类 、核函数、v c 维、心电图信号 a h t r a c t b e c a u s eo f t h es u i t a b i l i t yf o rs m a l ls a m p l a sa n dt h ew e l lg e n e r a l i z a t i o np e r f o r m a n c e ，s v m h a sb e e nb e c o m et h en e wi n t e r n a t i o n a lr e s e a r ：hh o t s p o to fp a t t e mr e c o g n i t i o nf i e l da tp r e s e n t t h eo b j e c to ft h ep a p e ri so nt h eo n eh a n dt oa n a l y z eu l t e r i o rs v mc l a s s i f i e dp r i n c i p l ea n d0 1 1 t h eo t h e rh a n dp r o p o s en e wa l g o r i t h mf o rs o m t ：l i m i t a t i o ni na p p l i c a t i o n a ni m p r o v e da l g o r i t h m t h a ta p p l y i n gs v mt oa m b i g u i t i e sw a s p r o p o s ：d ，w h i c hd e v e l o p e ds v ma p p l i c a t i o ns c o p e t h e c o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ， ( 1 ) a nn e wm e t h o dt od e a lw i t ht h ee c gd a t a a c c o r d i n gt ot h ec h a r a c t e r i s t i co ft h e3 c gd a t a an e wm e t h o dt ou s et h es a m p l e si s p r e s e n t e d ：t r a i n i n ge a c ho f t h ee i g h tc o n d u c t o r si ，e l o n g i n gt oas a m p l ei nt h ew h o l es e to r t eb yo n e t h e ng i v eac o m p r e h e n s i v ej u d g m e n tb a s e do nt h a to ft h ee i g h tc o n d u c t o r s w em a k eac o n t r a s t b e t w e e nt h i sm e t h o da n da n o t h e rt w om e t h o d sta a tc o n n e c te i g h tc o n d u c t o r sc o n t i n u o u s l yo ro n l y u s eo n ec o n d u c t o r e x p e r i m e n t ss h o wt h a tb yt l ee i g h tc o n d u c t o r sp a r a l l e lt r a i n i n gm e t h o d n o t o n l yt h ea c c u r a c yi si m p r o v e d ，b u ta l s ot h ep e r f 3 r m a n c eo ft h i sa l g o r i t h mi so fh i 曲s t a b i l i t y t h e r e a s o ni sb e c a u s ei th i g h l yd e c r e a s et h es a m p l esd i m e n s i o ni nt h ef e a t u r es p a c ef r o m3 4 4t o4 3 ， a n dc o n s i d e rt h ee i g h tc o n d u c t o r sc o m p r e h e n s i v e l ya sw e l ls oa st od e c e n t r a l i z et h er i s ka n d m i s t a k e nf a c t o r s ( 2 ) k n n s v mc l a s s i f i e da l g o r i t h m s v mf o c u so nt h es a m p l e sb e a rt h eb o u n d a a yi nt r a i n i n gt i m e ，a n dt h o s es a m p l e si n t e r m i x e d i na n o t h e rc l a s sa r eu s u a l l yn og o o dt oi m p r o v et h ec l a s s i f i e r sp e r f o r m a n c e ，i n s t e a dt h e ym a y g r e a t l y i n c r e a s e t h eb u r d e n o f c o m p u t a t i o n a n d t l e i r e x i s t e n c e m a y l e a d t oo v e f i t t i n ga n d d e c r e a s e t h eg e n e r a l i z a t i o na b i l i t y i no r d e rt oi m p r o v et h t g e n e r a l i z a t i o nw ep r e s e n ta ni m p r o v e ds v m ： k n n s v m i tf i r s tp r u n e st h et r a i n i n gs e t ，r a s e n eo rd e l e t eas a m p l ea c c o r d i n gt ow h e t h e ri t sk n e a r e s tn e i g h b o rh a st h es a n l ec l a s sl a b e lw i t hme l f o rn o t , t h e nt r a i nt h en e ws e tw i t hs v mt o o b t a i nac l a s s i f i e r e x p e r i m e n tr e s u l t ss h o wt h a tk n n s v mi sb e t t e rt h a ns v mi ns p e e da n d a c c u r a c yo f c l a s s i f i c a t i o n k e yw o r d s ：p a n e mr e c o g n i t i o n ，s u p p o r tx , e c t o rm a c h i n e ，kn e a r e s tn e i g h b o ra l g o r i t h m ， k e r n e lf u n c t i o n ，f e a t u r es p a c e ，v cd i m e n s i o n ，e c g 应用于心电图分类的k n n 与s v m 分类器研究 1 1 模式识别与分类器 第一章概述 模式并没有统一的定义，也有人将模式定j ：为与混乱相对，可以被命名的实体。而广义 的说，模式是存在于空间和时间中观察的事l 口，并且我们可以区分它们是否相同或相似， 如- - n 图像一张人脸，一个数字，一段话等。具有某些相似性质的事物就构成一个模式 类，如汉字“中”可以有多种写法，但是它们都属于同一类。类内每个具体的事物为该模 式类的一个样本。模式识别的目的就是对未女1 的样本，判别它所在的类别。人类能模式识 别能力使得人们可以很好的认识周围的环境 = 与之交流，如果计算机也具有类似的能力， 那么其智能程度将会大大提高，可以发挥更太的功效，更好的为人类服务。本文能研究课 题就属于计算机模式识别领域。 一般模式识别系统都由相互联系的两大部t 组成，即特征提取器和分类器。为了能有效 地进行模式分类，必须将原始的输入数据迸彳二：变换，以得到有助于分类的信息。这就是特 征提取的作用。一般将原始数据组成的空间裂沩测量空间，而把变换后的空间叫做特征空 间。而模式识别是把每个样本看做特征空间目卜一个点或一个向量，向量的每一分量都代表 某一特征，分类器的作用是对特征空间的点越绗分类，基本做法是在样本训练集基础上确 定某个叛别规则，使按这个判别规则对被识g l 对象进行分类所造成的错误率最小或引起的 损失最小。 模式分类的方法包括统计的方法、近邻法、神经网络分类法、无监督聚类法和新出现 的基于统计学习理论的支持向量机法，支持向量机分类法和近邻分类法是本文研究的主要 问题。 1 2 过适应及分类器的泛化能力问硒 模式识别及一些有关问题( 如曲线拟合) 都含遇到训练过度的问题，即网络的训练的次数 超过一定限度后，其推广性能随着训练次数的增加而下降；或者随着模型复杂度的增加， 训练结果越来越符合训练样本，但对测试数接 的性能却反而下降。神经网络的过学习问题 应用于心电图分类的k , i n 与s v m 分类器研究 就是一个典型的代表：当样本有限时，本来根不错的一个学习机器却可能表现出很差的推 广能力。 原因可概括如下：用于训练的样本数据与全体数据相比，尽管在统计规律上有某种一 致性，但它们毕竟有自己的特性，而且由于；i 实的数据往往带有一定的误差，所有训练样 本只是大体上反映了总体的统计规律，训练自】目的就是要通过这些有偏差的部分数据推测 总体特性，所以当网络训练次数过多，或模型的复杂度过高，它对于训练样本这些特定数 据的描述可以十分精确，但也可能偏离了总t i 数据的分布特性，这可通过一个简单的两类 划分的例子示意说明。见图1 i ，图中圆圈和方块代表两类数据的训练样本，它们的数据源 使得二者的分类边界是一段椭圆弧，每个样2 ：都附加了一定的误差。图( a ) 只能产生线性的 分类边界；图( b ) 、图( c ) 所对应的模型的复杂谣度依次增加，所产生的分类边界也越来越复 杂，与训练样本的吻合程度也不断上升。 ( a ) ( c ) 图i 1 ：过度训练示意图 图( c ) 对应的模型复杂程度最高，对于训鲤；样本的误识率为0 ，但是它的分类边界过于复 杂，由前面对数据源的描述可知，它的推广能力很差。图( a ) 的模型过于简单，无法描述较 为复杂的数据源，而图( b ) 的模型虽然对有误莲的训练样本不能完全正确分类，但它基本上 正确描述了分类边界，具有较好的推广性能。 从实际应用的角度出发，模型的复杂程度( 或灵活性) 的选取也需要适度选择，有的研究 人员为了使这一工作定量化，向模型的错误估计函数中加入了惩罚项 1 】。该项的值随着模 型的复杂度的增加而增加。而训练的目的是任错误估计函数达到极小，这样从一定程度上 可在模型的复杂性和对训练样本的吻合程度：二间有一个折衷考虑。 分类器的设计是对训练样本构造判决边孚- ，这样得到的分类器对于训练集合可以有很 好的识别率( 甚至可达1 0 0 ) ，然而对于不在州练集合中的样本其分类正确率如何昵? 应用于心电图分类的k q n 与s v m 分类器研究 或者说如何提高分类器的泛化能力呢? 这是一个关键问题。 1 3 论文内容简介 如上所述，分类器的构造方法有多种，j 二文主要以近邻分类器和支持向量机为研究对 象，通过对它们的分类原理分析找出二者的联系。由此构造了k n n s v m 分类器，对目 前支持向量机应用中所存在的一些限制做了日进。 本文的第二章详细介绍了近邻分类器( k n n ) 的分类原理。其中k 小n 算法必须明 确两个基本的因素：最近案例的数目( k ) 汞! 距离的尺度。对这个问题进行了讨论，并对 k n n 算法做出了评价。 本文的第三章对统计学习理论和支持向重：机做了较为详尽的描述，进一步解释了支持 向量机是一种具有较好泛化能力的分类器。 本文的第四章首先分析了s v m 和k n n 生- 类器的特性，给出定理描述二者的关系：基 于这个定理，之后提出了将s v m 和k n n 相旮台的一种新分类算法一k n n s v m ：通过 k n n 方法修剪训练集中混杂严重，易导致分类错误的样本，再利用s v m 对修剪后的样本 集进行训练。实验结果表明该方法不仅提高丫s v m 的分类精度和速度，还缓解了s v m 应 用中核函数参数选择困难的状况。 本文的第五章是将上述几种分类器用于惜规1 2 导联心电图的模式识别问题。并发现一 种新的心电数据运用方式：对所有心电图按照导联分段划分，样本集每次只取对应的一个 导联进行训练和测试。八个导联一一学习，：吝样得到八个输出值，然后对每个测试样本综 合八个导联的判断值，由多数的判断值来决：皂匿终的分类结果。实验表明，对心电数据学 习使用该种处理方式比以往常见的八个导联争联作为样本进行学习，或只挑取一个导联作 为样本进行学习的方式，无论是用k n n 还是s v m 分类器，在提高正确率和降低对参数的敏 感性方面都非常明显。实验还显示了k n n 、s v m 、k n n - - s v m 这几种分类器之间的比较 情况，并且显示了s v m 与k n n 相结合的算法的有效性和稳定性。 最后一章总结论文中的主要工作和结果，并展望进一步的工作。 本文的实验样本来自医院的真实数据，包括正常心电图和高血压心电图、心肌梗塞心 电图。 应用于心电图分类的k n n 与s v m 分类器研究 第二章用于分类的k 近邻算法 2 1 近邻法分类规则 近邻法( 简称n n ) 是模式识别非参数法中最重要的方法之一，最初的近邻法是由c o v e r 和h a r t 于1 9 6 8 年提出的，由于该方法在理论上进行了深入分析，直至现在仍是分类方法 中最重要的方法之一。直观地理解，所谓的l ：近邻，就是考察和待分类样本最相似的k 个 样本，根据这k 个样本的类别来判断待分类样本的类别值。在k 近邻分类器中，一个重要 的参数是k 值的选择，k 值选择过小，不能，j 分体现待分类样本的特点，而如果k 值选择 过大，则一些和待分类样本实际上并不相似自】样本亦被包含进来，造成噪声增加而导致分 类效果的降低。 最近邻( n n ) 是将所有训练样本都作为代表点，因此在分类时需要计算待识别样本工 到所有训练样本的距离，结果就是与x 最近自刚练样本所属于的类别。假定有c 个类别 q ，q ，d i 的模式识别问题，每类有标明；! 别的样本1 个，i = 1 ，2 ，ca 我们可以规 定哪类的判别函数为毋 ) 2 鼍i lx 一# m ，：= l ，2 ， 其中# 的角标f 表示q 类，k 表示q 类m 个样本中的第七个。决策规则可以写为： 若 g j ( x ) = m m ( x ) ，f = 1 ，2 ，c ，则决策x q 分类示意图见下图2 1 a 口 a 口 图2 1 ：n n 分类图示 蚰 b 、，、 应用于心电匿分类的l n n 与s v m 分类器研究 k 一近邻n n ) 是n n 的推广，即分类时越拙x 的七个最近邻，看这七个近邻中的多数属 于哪一类，就把j 分到哪一类。我们定义判别函数为岛( d = 龟，f = 1 ，2 ，c ，其中岛表 示_ j 个最近邻中属于类的样本数，决策规则为 g j ( x ) = m t ，则决策x 0 9 分类示意图见图2 2 b a r - t b 4 u 图2 2 ：k n n 分类图示 理论证明，k 一近邻分类有错误率p + p s 2 p 。由上式可知，k 一近邻法错误率在 贝叶斯错误率p 和两倍贝叶斯错误率2 p 之间。正是近邻法的这种优良性质，使它成为模 式识别的重要方法之一。但近邻法需要将所有样本存入计算机，每次决策都要计算待识别 样本x 与全部训练样本# ，f - l ，2 ，c ，；f = 1 ，2 ，m 之间的距离并进行比较，存储量 和计算量都很大。 k - n n 算法必须明确两个基本的因素：最近样本的数目( k ) 和距离的尺度。 k 一般是大于1 的一个整数，表示选择参照案例的数目。 距离的尺度对应一个非负的函数，用来刘画不同数剧列的差异程度。以下是一些常用 表示距离的尺度： 马氏距离( s 是样本点的协方差矩阵) ： d ( 亨，i ) = 瓶焉万：彳两 它考虑到样本点的分布情况。 欧氏距离： 碱椰= 鼢( ”订r ( 2 1 ) ( 2 2 ) 应用于心电图分类的k n n 与s v m 分类器研究 其中”是属性总数，是第i 个样本的第七。、属性值，a k 是第七个属性的权重。此处每个 属性的值均已做过规范化处理，即均值为0 ，标准偏差为1 。 绝对距离： d ( 五，五) = q | 靠一h i ( 2 3 ) 无限模： 、 d ( 耳x ，) = m 。a 。x a k i x * 一靠j ( 2 4 ) 在对心电图的分类实验中，我们对信号e j 距离尺度分别采取了欧氏距离和绝对距离进 行计算。 2 2 关于k n n 的一些处理方法 在k n n 算法里对于模型的选择( 尤其是k 值和距离的尺度) 往往是通过对大量独立的 测试数据、多个模型来验证最佳的选择。下i i 是一些被提及的处理k n n 的方法： k 值一般是事先确定，如l o ，也可以使用动态k 值；使用固定的距离指标，这样只对小 于该指标的案例进行统计。， 已有许多的报告研究距离尺度，可以从数据本身特定的含义考虑如何标识同列数据的 差异，如对于一些具有类别含义的数据可以j 月1 表示不同，0 表示相同，也可设计专用的 公式表达这种距离。一般要把同列数据距离旧值域控制在【0 ，l 】，也就是要标准化丰见范化。 对于多个独立变量来说，为描述不同独立变：垂的差异的重要性可能不同，需要加权处理。 在具体进行搜索时并不一定使用盲目的搜索方法，例如可以构造交叉索引表。利用匹 配成功与否的历史来修改样本库的结构。 对于样本的维护，也并不是简单的增加新样本。也可采用适当的办法来保证空问的大 小，如符合某种条件的样本可以加入库里，同时可以对库里已有符合某种条件的样本进行 删除等。 此外，为考虑提高性能，可以把所有的数据放在内存中，如m b r ( m c m o r y - b a s e d r e a s o n i n g ) 通常指保存在内存中的k 近邻算i 。 6 应用于心电图分类的心n 与$ v m 分类器研究 2 3 结论 k 近邻算法( k - r 心0 是一种预测性的分类算法( 有监督学习) 。它实际并不需要产生额外 的数据来描述规则，它的规则本身就是数据( 样本) 。k n n 属于机器学习的基于样本的学习 f c a s e - b a s e dl e a r n i n g 或e x a m p l e b a s 酣i e a r r a n 9 0 ，它区别于归纳学习的主要特点是直接用已 有的样本来艉决问题，而不是通过规则推导赤解决问题。它并不要求数据的一致性问题， 即可以存在噪音( n o i s e ) ，并且对样本的修改是局部的，不需重新组织。 k 近邻算法综合与未知样本最近的k 个紧邻样本的类别来预测未知样本的类别，而在选 择样本时根据一定的距离公式计算与未知样本的距离来确定是否被选择。其优点是方法简 单，算法稳定，鲁棒性好。其缺点是需要大量样本才能保证数据的精度，此外，更主要的 是它需要计算大量的样本间的距离，导致使拜 上的不便。对于每个新的样本都要遍历一次 全体数据，k n n 计算量要比n a l v e - b a y e s 和谤- 策树要大。对时间和空间的复杂性是必须考 虑的。一般s v m 可以对多个新的数据进行预则，而k n n 则常用在较少数据预测贮使用。 “丘邻分类算法具有主观性，因为必须定义一个距离尺度，由于对距离的理解还不是 深刻的，而分类的结果完全依赖使用的距离，这样对于同一组数据，两个不同的分类算法 会产生两种完全不同的分类结果，一般就需善；专家来评测结果是否有效。由于对结果的影 响的认识是往往属于经验性的，这便限制对 r 种距离的使用。 应用于心电图分类的州与s v m 分类器研究 第三章支持向量机理论 3 1 机器学习的表示与支持向量机方法 机器学习问题的基本模型，可以用图3 1 表示：其中，系统s 是我们研究的对象，它在 给定一定输入x 下得到一定的输出y ，l m 是我们要求的学习机，输出为多。机器学习的 目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输 入作出尽可能准确的预测。 x y 图3 1 ：机器学习示 图 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v f 是v a p n i c 于1 9 9 3 年提出的一种新的模式分 类技术。该方法是建立在统计学习理论的v c 维理论和结构风险最小化基础上，根据有限 的样本信息在模型的复杂性( 即对特定训练样：# 的学习精度，a c c u r a c y ) 和学习能力 即无错 误地识别任意样本的能力) 之间寻求最佳折衷 以期获得最好的推广能力( g e n c r a l i z a t i o n a b i l i t y ) 3 1 。正是这种好的性质使s v m 迅速丘：为国际上机器学习领域新的研究热点并已被 应用于人脸识别、文本识别、手写体识别等 4 域 2 】。 从方法上讲，s v m 首先将数据映射到某个高维空间，以增加数据的可分性，使得原本 线性不可分的样本在高维空间中线性可分，i i 样可简单地用高维空间的一个超平面完成分 类。基本可考虑分为以下三部分： 1 、基于统计学习理论中的结构风险最小化球a 称s r m ) 在s r m 理论中通过最小化分类器的v c 维来控制结构风险，不仅使经验风险最小化 还要使结构风险最小化，使学习具有强的推厂能力：由统计学习中的定理可知，使| | w 酽 墨 应用于心电图分类的k n n 与s v m 分类器研究 最小就是使v c 维的上界最小。而分类间隔冬；于2 l l w 使间隔最大等价于使0 w 旷最 小，实际上就是对推广能力的控制并由此引e 下面最优分类超平面的概率 2 、强调分类超平面是最优的。 最优分类超平面的含义是存在一个超平面旖足对样本的正确划分的条件，而且在这个超 平面两侧的与这个超平面距离最近的两个点：三间的距离最大。这样通过超平面的这两个 点作与超平面平行的向量，所有这样的向量：勾支持向量。由于问题的目标是最优的分类超 平面，它可以被变换为一个不等式约束条件。的二次优化问题。 3 、s v t v l 采用核化技术，不求非线性映射转而求特征空间的内积 s v m 主要通过事先选择的非线性映射璇样本空闻映射到高维特征空间，阻碍着高维 现性空间构造最优分类超平面。根据泛函中 m e r c e r 定理，寻找一个函数( 称核函数) 将样 本空间中内积对应于变换空间中的内积，即避免求非线性映射而求内积。 3 2 支持向量机 s v m 是从线性可分情况下的最优分类面发展而来的，采用的是保持经验风险值固定 而最小化置信范围的策略。我们首先考虑训练数据是线性可分情况下的最优分类超平面， 然后，在3 2 2 小节中我们将其推广到不可分数据的情况。 3 2 1 最优分类超平面 s v t v i 的基本思想可用图3 2 的两维情况说 明。图中，实心点和空心点代表两类样本，j 为分类线，h l ，h 2 分别为过各类中离分类线 最近的样本且平行于分类线的直线，它们之间 的距离叫做分类间隔( m a r g i n ) 。所谓最优分茎： 线就是要求分类线不但能将两类正确分开( 川 练错误率为0 ) ，而且使分类间隔最大。分； 线方程为( w x ) + b = 0 ，我们可以对它进行 9 h 1 0 图3 2 线性可分情况下的最阮分彗嫩 2 巾0 应用于心电图分类的k n n 与s v m 分类器研究 归一化，使得对线性可分的样本，( x i ，y 。) ，x ? r ”，只 1 ，一1 ) ，f _ 1 , 2 ，满足 y ， ( w + x ) + 6 1 ，i = 12 f ( 3 1 ) 此时分类间隔等于2 i fw 使间隔最大等价于使| | w8 2 最小。满足条件( 3 1 ) 且使毒1 1w l l 2 最小的分类面就叫做最优分类面，h 1 ，1 4 2 上的训练样本点就称作支持向量。 使分类间隔最大实际上就是对推广能力 勺控制，这是s v m 的核心思想之一。这一点 可由下面的定理得到【5 l = 定理3 1 在n 维空间中，设样本分布在一个二 径为r 的超球范围内，则满足条件1 ：w 临4 的正则超平面构成的指示函数集厂( x ，w ，6 ) = s g n ( w x ) + 6 ( s 弘( ) 为符号函数) 的v c 维满 足下面的界 h m i n 姑2 a 2 j ) + 1 ( 3 2 ) 因此使1 1w1 1 2 最小就是使v c 维的上界 小，从而实现s i t m 准则中对函数复杂性的选 择。 要找到最优分类超平面，我们需要求解f 面的二次规划问题：最小化泛函 如) = 1 1 w 旷= i l w 州 ( 3 3 ) 约束条件为不等式类型： y i ( w + x ) + 6 】1 ，i = 1 , 2 ， ( 3 4 ) 这个优化问题的解是由下面的拉格朗日函数的鞍点给出的： 如，6 妒圭( w + w ) 一喜q 冰w 吲十6 】_ 1 ( 3 s ) 其中，珥0 为l a g r a n g e 系数，三在鞍点上耗最小值，此时w = w o ，b = 6 0 满足 _ o l ( w o , b o , c t 。) ：o 1 ：圭m 群薯 o w百 tgl(丁wo,bo,口。)：o j ：! y 。留：o a 6 j l “ 此时目标函数的对偶问题为 0 ( 3 6 ) 应用于心电图分类的f n 与s v m 分类器研究 约束条件为： 矿( 口) ：圭q 一要圭y i y i c ，j c t s ( x i * x j ) - j 上i , j = l 咒钟= o 群0i = 1 ，2 ，z ( 3 7 ) ( 3 8 ) ( 3 9 ) 这是一个不等式约束下的二次函数极值问题，且存在唯一解。根据k u l m t u c k e r 条件，这 个优化问题的解必须满足 q m ( w $ x ) + 明一1 ) = 0 ， f = 1 , 2 ，( 3 1 0 ) 因此多数样本对应的将为零，有一部分( 通常是少部分) q 不为零，对应的样本就 是支持向量。要构造最优超平面需要解决的是一个简单的二次规划问题：在约束条件( 3 4 ) 式下最大化( 3 3 ) 式的二次型。 设= ( 衅，钟) 为这个二次优化问题酏解，那么与最优超平面对应的向量w ( ，的模等 于： 1 1 w o l l 2 = 2 w ( a o ) = 彰 ( 3 】1 ) 支持声量 基于最优超平面的分类规则就是下面的指示匪数： 厂( 工) = s g n ( 咒( 薯- x ) + ) ( 3 1 2 ) 互持向量 其中x ，是支持向量，口? 是对应的l a g r a n g e 系数，b o 是常数( 阚值) ， 6 0 ：一昙【( 1 吒+ x ( 1 ) ) + ( 。x ( 一1 ) ) 】 ( 3 1 3 ) 其中用x + ( 1 ) 表示属于第一类的任意一个支持向量，用x ( 一1 ) 表示属于第二类的任一个支 持向量。 3 2 2 广义最优分类面 虽优分类超平面是在线性可分前提下讨仑的，在线性不可分的情况下就是某些训练样 本不能满足式( 3 1 ) 的条件。上述算法应用到线性不可分的数据将会找不到可行解，这点可 通过目标函数的任意增大来验证，我们采取猷做法是在限制条件中引入一个松弛变量最， f _ 1 2 ，z ，变为 应用于心电图分类的k q n 与s v m 分类器研究 只 ( w + z ，) + 6 卜1 + 4 0 f 3 1 4 ) 舌。0i = 1 ， 这样当错误产生时，相应的毒必须达丑一致，所以e 4 是训练错误数的一个上界。 这时广义最优超平面可以进一步演化为在条甓：( 3 1 4 ) 的约束下求下列函数的极小值： 。( w ，。；劲w 卜c ( 老毒) t ( 3 问 为计算方便取七= i ，其中c 为某个指i ! 的常数，它实际上起控制对错分样本惩罚程 度的作用，实现在错分样本的比例和算法复疗渡之间的折衷。指定一个较大的c 可以降低 错分样本的个数。目标函数对应的拉格朗日j 数为： 岛：丢( w + w ) + c 壹鲁一圭q 咒【o ，而) + 6 】一l + 磊 - 圭h 茧 ( 3 1 6 ) 考虑到k k t 条件，可得下式； 斋= 。jw = 喜脯j 鲁= 。等o - 一喜咖 鲁= 。c 叩肛= 。 。1 7 以2 2 点0 ，啦0 ，4 0 q ( 咒 ( w + 蔫) + 6 卜l + 盏) = 3 ，i = 1 2 7 ( c 一) 毒= 0 如前所速，我们能用k k t 补充条件， 式( 3 1 9 ) 和( 3 2 0 ) 决定阈值啦c ，而结合等 式( 3 1 4 ) 和( 3 2 2 ) 显示，如果噶 0 展开成 k ( u ，v ) = 纯( “) f 。( v ) ( 即x ( u ，v ) 描述了在某个特征空间中的一个f 日积) ，充分必要条件是，对使得 9 2 ) 幽 0 成立。 ( 3 2 6 ) ( 3 2 7 ) 在s v m 中，采用不同的函数作为核函 安足( z ，鼍) ，我们可以构造实现输入空间中不 同类型的非线性决策面的学习机器。目前研：恕得最多的核函数主要有三类： ( 1 ) 多项式核函数 x ( x ，) - ( x + 薯) 叫9 所得到的是q 阶多项式分类器； ( 2 ) 径向基函数( r b f ) ，= 哪p 学 1 4 ( 3 2 9 ) r 3 。3 0 ) 应用于心电圈分类的k n n 与s v m 分类器研究 所得分类器与传统r b f 方法的重要区别是，这里每个基函数中心对应一个支持向量，它 们及输出权值都是由算法自动确定的。 ( 3 ) 采用s i g m o i d 函数作为内积 k ( x ，薯) = t a n h ( 0 ，说明样本x 到x + 的距离小于x 到x 一的距离，即x + 是样本x 的最近邻， 这时样本工应与x + 同类，输出为+ 1 ，若g ( 0 ，将其代入s v m 的分类公式，( 工) = s g n ( g ( x ) ) ，可得，( x ) = + 1 ；若 g ( x ) 0 ，同理可得出f ( x ) = 一1 。 4 2k n n - s v m 分类器算法 s v m 和其它分类器相比具有较高的分类l 力，但对于较复杂的问题其分辨率不是很 高。我们对s v m 分类时错分样本的分布进行分析发现，s v m 分类器和其它的分类器一 样，其出错样本点都在分界面附近，这提示我们必须尽量利用分界面附近的样本提供的信 息以提高分类性能。由s v m 理论我们知道，分界面附近的样本基本上都是支持向量，同 时由定理4 1 可知s v m 可以看成每类只有一个代表点的最近邻( n e a r e s tn e i g h b o r tn n ) 分类器。所以我们结合s v m 和k n n 算法，勾造出一种新的算法k n n - s v m 。 应用于心电图分类的k n n 与s v m 分类器研究 4 2 1 算法的产生 支持向量机以其泛化能力强著称，它仅伍考虑类的边界情况，用较少的向量( 支持向 量) 来分类，一方面，它要使得两类边界之问得宽度最大：另一方面，它还要使得错分的 代价不要太高。两方面权衡得结果，就是要使得结构风险取得最小。 争取最大的边界宽度是为了保证分类器有较强的泛化能力，同时这里的“最大”是 有条件的，就是不能付出太多的错分代价，s v m 是这两种要求折衷的结果。在训练分类器 时，s v m 的着眼点在于两类的交界部分，那些混杂在另一类中的点往往无助于提高分类器 的性能，反而会大大增加训练器的计算负担，同时它们的存在还可能造成过学习，使泛化 能力减弱，基于这种想法，本文提出了一种改进的分类器算法k n n - - s v m ：它免对训练 集进行修剪，根据每个样本与其k 个最近邻旧( n e a r e s tn e i g h b o r ) 类标的异同决定其取舍， 然后再用s v m 训练得到分类超平面。实验袁明，k n n - - s v m 相比s v m 在分类正确率， 分类速度以及适用的样本规模上都较优。 4 2 2k n n - - s v m 算法 尽管支持向量机追求的目标是较强的泛针。能力，但相对于具体的样本集，也可能出现 过学习的问题。如两类样本集混叠较严重时s v m 的决策面可能由于过分复杂反而降低 了其泛化能力。 本文提出了一种改进的支持向量机算法k n n - - s v m ：它先对训练集进行修剪，根 据每个样本与其最近邻的k ( k - n n ) 个样本的类标的异同决定其取舍，然后再用s v m 训练 得到分类超平面。实验表明，与s v m 相比，k n n - - s v m 不单在分类正确率上有了较大提 高，而且分类速度更快，并能适用更大规模曲训练样本集。 我们采取下面的策略对训练集进行修剪： 首先找出每一个点的k 近邻，然后对每一个点，如果k 个近邻中标签相异的样本个数 超过标签相同的个数，则将该点删除；反之，则保留此点。 采用欧氏距离或绝对距离作为两个向量：二间的距离。 相对于s v m ，该方法有以下优点： 应用于心电图分类的k 叮n 与s v m 分类器研究 ( 1 ) 分类正确率有望提高 由于修剪了训练集，k n n - - s v m 的分类边界相比s v m 的过于复杂的分类边界有所简 化，因而其泛化能力可能更强，分类正确率可能更高。可见k n n - - s v i v l 是解决由于两类 混叠严重而造成分类器过学习和泛化能力减；问题的有效途径。 ( 2 ) 分类所用时间更短 训练集经过修剪后，分类器的支持向量个致大大减少而分类所用时间与支持向量的个 数是直接相关的( 见0 1 5 ) 式) ，因此就可大j ：节省分类时间。 ( 3 ) 可用于更大训练集 由于修剪过程便较大的训练集变小，因此在同样的硬件条件下，k n n - - s v m 可适用于 更大的训练集。 当然，我们应该指出，上述优点的获得也是付出了一定代价，那就是修剪过程需要额外 的时间，但是这一点代价与上述任何一种收益相比都是微不足道的，因为更高的正确率， 更快的分类速度以及训练更大的样本集是我们追求的首要目标。 需要注意的是： ( 1 ) k n n - - s v m 特别适用于混叠较为严重薛数据集，即两类的交叉区域较大不易划分的情 形，对于混叠很轻，容易划分的情形，t h n n - - s v m 虽然仍具备上述优点，但优势不明 显。 ( 2 ) 在样本集严重不足的情况下，修剪掉现：亨的不多样本显然不可取。这时候荐对样本集 修剪不合时宜，这种情况下，没有必要使用k n n - - s v m ，也就是说，当样本集的规 模处于某一水平之上时，k n n - - s v m 会表现出较为明显的优势。 应用于心电图分类的鼢l n 与s v m 分类器研究 5 1 心电图信号介绍 第五章实验及分析 心电图检查是广泛应用于临床无创性检l 方法之一，对某些疾病特别是心血管疾病的 诊断具有重要的意义。利用计算机辅助识别，c 、电图，进行比较分类，首先要将心电图正确 分割，提取出每一个波形，然后才能进行数接；分析。心电图由一系列相同的波群构成，一 个典型的心电图样本包括以下成分： 厶少十叶 5 2 j 八 6 t 固ss ：一个典型的心皂豳自八个导联e 的心跳 本文的实验数据来自上海中山医院提供的常规1 2 一导联心电图，每份心电图经过转换以 后包含8 个导联，每个导联纪录了1 0 秒钟郇c 心电信号。原始数据每个导联包含了5 0 0 0 个 采样点，所以仅单个样本就有( 8 x 5 0 0 0 ) 自j 数据量。由于个体的差异性，心跳频率不同， 所以针对每个人提取出来的一个完整心跳的果样点数也不一定相同。为了能有效地进行模 式分类，必须将原始的输入数据进行变换，以得到有助于分类的信息。这就是特征提取的 作用。由于心电信号本质上讲是一种非周期和非平稳的信号，而小波分析具有良好的时频 域分析能力，从而它特别适合于非平稳信号的分析和处理。基于小波分析的上述特点，文 2 3 应用于心电图分类的i ( 1 与s v m 分类器研究 献i l l j 提出了一种基于小波多分辨分析方法的篑：法对心电信号进行分段和特征提取，在特征 空间中把样本维数降为3 4 4 ( = 8 4 3 ) 维。 i4 3 个数据点代表一个导联上的一个心跳。 我们的实验对象包含：正常心电图样本1 0 1 1 4 个、高血压心电图样本2 9 6 个、心肌梗塞 心电图样本6 0 8 个，这里所有样本均有人工临床诊断结果。为了均衡起见，每次实验，训 练样本集中的两类样本数量保持对等，测试集中混杂的两类待识别样本数量也对等。以避