（信号与信息处理专业论文）组合分类器在新生儿疼痛表情识别中的应用.pdf

南京邮电大学硕上研究生学位论文 摘要 摘要 近年来，有关新生几疼痛的研究证实，反复的疼痛刺激会对新生儿( 尤其对早产儿和 危重j l ) 产生一系列近期和远期的不良影响，因此医学界正致力于开发出新生儿疼痛评估 工具。在评估新生儿疼痛时，专家认为仅靠生理变化来评估疼痛是远远不够的，因为其它 非疼痛的刺激也可引起类似生理反应，因此必须与行为评估方法联合应用。新生儿疼痛的 行为反应包括躯体活动、哭泣、睡眠以及面部表情的改变，其中面部表情的改变被视为是 一种最好的疼痛评估指标。开发一种基于面部表情识别的新生儿疼痛自动评估系统具有非 常重要的意义和价值，而表情分类作为表情识别的最后一个环节具有至关重要的作用。本 文所做的工作就是在新生儿面部表情特征提取的基础上进行表情分类。 本文在研究支持向量机和a d a b o o s t 算法的基础上，研究了组合a d a b o o s t 和r b f s v m 的可行性，并设计开发了组合分类算法_ a d a b o o s t s v m 。把该算法应用于新生儿疼痛表 情识别中。主要工作如下：( 1 ) 针对多分类情况，对当前流行的s v m 多分类技术进行了 深入研究，并讨论了a d a b o o s t s v m 所采用的多分类策略。( 2 ) 在建立新生儿疼痛表情数 据库的基础上，设计并实现了基于a d a b o o s t s v m 的新生几表情分类系统，并使用该系统 进行了模型初始参数的实验。实验表明在固定惩罚因子c 的基础上，逐步减少高斯带宽参 数o r 到一个适当值可以极大的改善性能。( 3 ) 通过对a d a b o o s t s v m 和单个s v m 分类器 以及基于决策树的a d a b o o s t 算法进行新生儿疼痛表情识别比较，得出本文应用的 a d a b o o s t s v m 分类算法性能优于其他两种分类算法。 关键字：新生儿疼痛，面部表情识别，a d a b o o s t s v m ，组合分类 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t n o w a d a y s ，m a n ys t u d i e ss h o wt h a tt h er e p e a t e d l yp a i n sw i l li m p a c to nn e o n a t e ，e s p e c i a l l y f o rp r e m a t u r ei n f a n t s b e c a u s eo ft h a t ，h e a l t hd e p a r t m e n ti sw o r k i n gt od e v e l o pt h ep a i n a s s e s s m e n tt o o l s t oe v a l u a t et h en e o n a t a lp a i n ，t h ee x p e r t sc o n s i d e ri tt ob en o te n o u g ht oa s s e s s t h ep h y s i o l o g i c a lc h a n g e sa l o n eb e c a u s eo t h e r n o n p a i ns t i m u l i c a l la l s oc a u s es i m i l a r p h y s i o l o g i c a lr e s p o n s e s ，s u c ha sb o d ya c t i v i t y ，c r y i n g ，s l e e pa n df a c i a le x p r e s s i o nc h a n g e se t c a m o n gt h e s er e s p o n s e s ，t h ef a c i a le x p r e s s i o n sa r er e g a r d e da so n eo ft h eb e s ti n d i c a t o r so fp a i n e v a l u a t i o n ，w h i l et h eb o d ya c t i v i t ya n dc r y i n gw h i c hw i l lh a p p e ni no t h e rs i t u a t i o nw a s n o tv e r y e n o u g hf o rt h ep a i n t h es i t u a t i o ni n c l u d e sh u n g e r ，f e a ra n du n e a s e t h e r e f o r e ，t h em a i nw a y t oe v a l u a t et h en e o n a t a lp a i n f u le x p r e s s i o ni st h eh u m a nf a c i a le x p r e s s i o nr e c o g n i t i o n a st h e l a s ts t e po fe x p r e s s i o nr e c o g n i t i o n ，t h ee x p r e s s i o nc l a s s i f i c a t i o np l a y sa ni m p o r t a n tr o l e t h i s p a p e rf o c u s e so nf a c i a le x p r e s s i o nc l a s s i f i c a t i o nb a s e do nt h en e o n a t a lf a c i a le x p r e s s i o nf e a t u r e e x t r a c t i o n b a s e do ns u p p o r tv e c t o rm a c h i n e sa n da d a b o o s ta l g o r i t h m ，t h i s p a p e rs t u d i e dt h e f e a s i b i l i t yo fc o m b i n i n ga d a b o o s ta n dt h er b f s v m ，a n dd e s i g n e da n di m p l e m e n t e dt h e e n s e m b l ec l a s s i f i c a t i o na l g o r i t h m s - - - - a d a b o o s t s v m a tl a s t ，w ea p p l i e dt h ea d a b o o s t s v mt o t h er e c o g n i t i o no fn e o n a t a lp a i ne x p r e s s i o n t h em a i nw o r k sa r ei n c l u d e d 筋f o l l o w ( 1 ) t h e c u r r e n tp o p u l a rm u l t i c l a s s i f i c a t i o nm e t h o do fs v ma n dm u l t i c l a s s i f i c a t i o n s t r a t e g yf o r a d a b o o s t s v ma r ed i s c u s s e d ( 2 ) a f t e rb u i l d i n gt h en e o n a t a lp a i nf a c i a le x p r e s s i o nd a t a b a s e ，t h e n e o n a t a le x p r e s s i o nc l a s s i f i c a t i o ns y s t e mb a s e do na d a b o o s t s v mi sd e s i g n e da n d i m p l e m e n t e d i no r d e rt of i n dt h es u i t a b l ei n i t i a lp a r a m e t e r so fs y s t e m ，w ec a r r i e do ne x p e r i m e n t s e x p e r i m e n t r e s u l t ss h o wt h a ts e l e c t i n g a p p r o p r i a t eg a u s s i a nb a n d w i d t hp a r a m e t e r s 仃 m a yg r e a t l y i m p r o v et h ep e r f o r m a n c ew h i l et h ef i x e dp e n a l t yf a c t o rc i sg i v e n , ( 3 ) c o m p a r e d 州t l ls i n g l e s v ma n dd e c i s i o n t r e eb a s e da d a b o o s ta l g o r i t h m ，t h ea d a b o o s t s v m a l g o r i t h mh a st h eb e t t e r p e r f o r m a n c e k e y w o r d s ：n e o n a t a lp a i n ，f a c i a le x p r e s s i o nr e c o g n i t i o n , a d a b o o s t s v m ， e n s e m b l ec l a s s i f i c a t i o l l i l 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：亟主琴日期：￥：旦! ! 一 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生虢趟翮繇差麴胁 俨驴t ，t 南京邮电大学硕士研究生学位论文第一章绪论 1 1 课题背景 第一章绪论 早期大部分麻醉学者认为新生儿不会有疼痛的感觉，所以新生儿疼痛一直未予重视和 正确处理。近年来，有关新生儿疼痛的研究证实，反复的疼痛刺激会对新生儿( 尤其对早 产儿和危重儿) 产生一系列近期和远期的不良影响，因此医学界正致力于开发出较好的新 生儿疼痛评估工具。 临床上，将疼痛定义为一种主观的体验，认为评估疼痛的最可靠的方法是通过自我评 估报告 3 3 】。大多数成年人都能用语言来描述疼痛的部位、时间和强度及疼痛的经历，但新 生儿不能自述自己的疼痛经历，只有通过诊断或其它方法来评估疼痛。有关研究表明，忽 视疼痛可能导致新生儿中枢神经系统的缓慢变化，经常性疼痛会带来负面影响和其它显著 的长期性影响【3 4 ，3 5 1 。 在评估新生儿疼痛时，专家认为仅靠生理变化来评估疼痛是远远不够的，因为其它非 疼痛的刺激也可引起类似生理反应【3 6 】，例如恐惧和兴奋。新生儿疼痛的行为反应包括身体 活动、哭泣、睡眠以及面部表情的改变。其中面部表情被视为是一种最好的疼痛评估指标 7 1 ，而身体活动与哭泣对于指示疼痛不是很具体，因为它们在其它的情形下也会发生，如 饥饿、恐惧和不安【3 8 】。为此，人脸表情识别是评估新生儿疼痛表情的主要手段。 视觉是人类观察世界和认知世界的重要手段。视觉信息在人类感知外界环境方面起着 主要的作用，人类的大脑所处理的大部分信息来自于视觉。计算机视觉是通过计算机实现 人的视觉功能对客观世界三维场景的感知、识别和理解，其最终目标是模拟人类的视 觉能力，理解并解释周围的世界。目标的识别和理解是计算机视觉的核心内容之一。人脸 是人们社会交流中所关注的焦点，它在辨别身份和传递感情方面起着主要的作用m 。尽管 从人的面部特征推断人的性格和智力这种能力还没有得到证实，但是识别出人脸的能力确 实是很显著的。在人的一生当中，能够识别出成千上万的面孔。即便是分离很多年之后， 只要是简单的看一眼，也能辨别出相似的面孔。而且这种能力具有很强的鲁棒性，即便人 的发型、面部表情或是年龄有很大变化，也能辨认得出来。因此，入脸的视觉信息处理很 多世纪以来一直吸引了很多哲学家和科学家的浓厚兴趣。 南京邮电大学硕士研究生学位论文 第一章绪论 本文的研究内容是新生儿疼痛面部表情自动识别理论和方法，主要是通过组合 a d a b o o s t 和s v m ( s u p p o r t v e c t o rm a c h i n e ) ，应用a d a b o o s t s v m 6 】对新生儿面部疼痛表隋进 行识别和分类，同时为了验证该算法的可行性，设计并实现了一个原型评估工具，并把该 算法和现有的算法进行性能比较分析。其研究可为医护人员客观、可靠、有效地评估疼痛 提供科学的依据，以便在临床上及时采取相应的治疗措施，以减轻新生儿的疼痛。 1 2 国内外研究现状 1 2 1 人脸表情识别研究现状 人脸表情识别需要图像处理、模式识别、人工智能、计算机视觉等方面的发展为其提 供必要的条件。这是一个涉及心理学、生理学、行为学、社会学、传感器技术、计算机科 学等诸多领域的交叉课题，其发展受到其他领域的制约和影响。关于人脸表情识别的技术 研究，已经有很多该领域的国际会议出现，例如，1 9 9 7 年的a v b p a 国际会议( i n t e r n a t i o n a l c o n f e r e n c eo na u d i o a n dv i d e o b a s e da u t h e n t i c a t i o n ) ，19 9 5 年开始的a f g r 国际会议 ( i n t e r n a t i o n a lc o n f e r e n c eo na u t o m a t i cf a c ea n dg e s t u r er e c o g n i t i o n ) 。而且出现了很多人脸 表情识别工具，如：f e r e t 【4 1 1 ，f r v t 2 0 0 0 1 4 2 1 ，f r v t 2 0 0 2 t 4 3 1 ，x m 2 v t s l 4 4 1 。至少存在两个 理由说明该技术需要得到进一步的发展。其一是商业上的广泛应用；其二是该技术已经发 展了将近3 0 年，已经具有一定的理论和经验基础。 1 2 2s v m 分类器研究现状 支持向量机是v v a p n i k 教授等人在统计学习理论基础上发展起来的一种新的机器学 习方法。它具有坚实的统计学习理论基础，并己被广泛的应用于机器视觉领域，这些领域 包括字符识别、手写笔、文本识别和人脸表情识别等。 自从v v a p n i k 教授等人提出支持向量机以来，国内外已有很多学者应用支持向量机 进行图像分类。其中，m a s h a o 通过最大化数据点之间的边缘和最大化决策边界来最小化误 分类，并且为了平衡模型复杂性和训练错误率，引入了惩罚因子c1 4 5 j 。s h e r y lb r a h n a m 等人把表情分类为疼痛表情和非疼痛表情两种，进而通过实验表明s v m 可以较好的对这两 种表情进行很好的分类1 2 。p a i - h s u e nc h e n 在一个通用的并可扩展的二元工作集的方式下 研究了s m 0 分解算法，同时得到了如下的结果1 3 1 ：( 1 ) 一个渐近收敛定理；( 2 ) 一个关 2 南京邮电大学硕士研究生学位论文 第一章绪论 于收缩缓冲技术的通用定理的证明；( 3 ) 算法是线性收敛的。 支持向量机以二分类器为设计初衷，已经有很多学者研究多分类支持向量机技 术 2 3 , 2 4 , 2 6 1 。总的来说，多分类支持向量机存在如下几种策略：一对多、一对一和d d a g 方法【2 6 1 。 一对多方法是个简单而且有效的方法【4 6 】。其基本思想是假如存在k 类，该方法把这个k 类问题划分成一个二分类问题：其中一个类表示“正”类，而所有其它的类合并表示为“负” 类，对于这个二分类问题训练一个二分类器，然后，用同样的思想将余下的k l 类划分为 一个二分类问题，直至必类全部被分类。文献 2 9 介绍了一对一方法，而文献 3 0 ，3 1 首 先把该方法应用到支持向量机中。该方法建造丛冬型个分类器，且每一个分类器用来区分 z 一个对类。而文献 2 6 介绍了d d a g 方法，该方法旨在解决一对一方法在测试阶段的相同 投票数问题。它的训练阶段和一对一方法是相同的，同样是训练出丛车型二分类器。然而， z 在测试阶段，它采用一种带根二叉有向无环图，对于图中的每一个节点，要么没有出边， 要么有两条出边，因此该图有丛冬型个节点和尼条出边。其中，每一个节点是第f 和第j z 类的二元支持向量机。给定一个测试样本x ，算法从根节点开始，评估一个二元决策函数。 然后根据输出值进入左子树或者右子树进行递归处理，直到叶子节点。 1 2 3a d a b o o s t 研究现状 提升( a d a b o o s t ) 是一个迭代过程，用来自适应地改变训练样本的分布，使得基分类 器聚焦在那些很难分的样本上。不像装袋( b a g g i n g ) ，提升( b o o s t i n g ) 给每一个训练样 本赋一个权值，而且可以在每一轮提升过程结束时自动地调整权值。 a d a b o o s t 算法最早由f r e u n d 和s c h a p i r e 所提出【1 5 j ，旨在解决提升算法的不足。例如： k e a r n s 和v a l i a n t 首先提出关于一个弱学习算法的问题，那就是一个仅仅略好于随机投票 的弱分类器经过提升算法之后能够建构成一个“强”的学习算法【4 7 ，4 8 】。a d a b o o s t 的算法基 本思想是：算法开始时，所有样本都赋予相同的权值，从而使得它们被选作训练的可能性 一样。根据训练样本的抽样分布来抽取样本，得到新的样本集。然后，由该训练集归纳一 个分类器，并用它对原数据集中的所有样本进行分类。每一轮提升结束时更新训练样本的 权值。增加被错误分类的样本的权值，而减少被正确分类的样本的权值。使得分类器在随 后迭代中关注那些很难分类的样本。 南京邮电大学硕士研究生学位论文 第一章绪论 1 2 4 组合分类器 组合分类器是通过聚集多个分类器的预测来提高分类准确率。组合方法由训练数据构 建一组基分类器，然后通过对每个基分类器的预测进行投票等方法来进行分类。组合分类 器的性能如果要优于单个分类器必须满足两个必要的条件：( 1 ) 基分类器之间应该是相互 独立的；( 2 ) 基分类器应当好于随机猜测分类器。 构建组合分类器有许多方法，其中最主要的有以下四种方法： ( 1 ) 通过处理训练数据集。这种方法根据某种抽样分布，通过对原始数据进行再抽 样来得到多个训练集。抽样分布决定一个样本选作训练的可能性大小，并且可能因试验而 异。然后，使用特定的学习算法为每一个训练集建立一个分类器。其中装袋和提升就是两 种处理训练数据集的组合方法。 ( 2 ) 通过处理输入特征。在这种方法中，通过选择输入特征的子集来形成每个训练 集。子集可以随机选择，也可以根据领域专家的建议选择。一些研究表明，对那些含有大 量冗余特征的数据集，这种方法的性能非常好。随机森林就是一种处理输入特征的组合方 法，它使用决策树作为基分类器。 ( 3 ) 通过处理类标号。这种方法适用于类数足够多的情况。通过将类标号随机划分 成两个不相交的子集a o 和彳1 ，把训练数据变换为二元问题。类标号属于子集a o 的训练样 本指派到类0 ，而那些类标号属于子集彳1 的训练样本被指派到类l 。然后，使用重新标记 过的数据来训练一个基分类器。重复重新标记类和构建模型步骤多次，就得到一组基分类 器。 ( 4 ) 通过处理学习算法。许多学习算法都可以这样来处理：在同一个训练数据集上 多次执行算法可能得到不同的模型。例如，通过改变一个人工神经网络的拓扑结构或各个 神经元之间联系的初始权值，就可以得到不同的模型。 到目前为止，组合分类方法已经被很多学者所研究。其中，两个常用的组合分类技术 是装袋和提升 4 9 1 。提升较之装袋有更高的性能【1 8 1 。在众多提升算法中，a d a b o o s t 5 1 】通过 维护一组训练样本的权值并在每一次迭代后根据错误率调整权值，调整权值的基本规则 是：提高那些误分样本的权值，而减少正确分类的样本的权值。a d a b o o s t 算法之所以成功 是因为它可以扩大边缘f 5 2 】，这样能够加强a d a b o o s t 的泛化能力。支持向量机来自于结构 风险最小化理论。通过使用核技术从输入空间到高维特征空间的映射，s v m 可以在特征空 问中找到最大超平面，同时使用一个惩罚因子c 来平衡模型复杂性和训练误差。为了避免 4 南京邮电大学硕士研究生学位论文 第一章绪论 维灾难而引入了核技术，其中最常用的核函数是r b f 核函数，该核函数使用一个叫高斯带 宽的参数。根据r b f s v m 的性能分析【5 4 1 ，可以知道高斯带宽仃是一个重要的参数。如果给 定一个较小的惩罚因子c ，r b f s v m 的性能极大的依赖于高斯带宽仃，因此r b f s v m 的 性能调整可以简单的调整仃。 1 3 本文工作 在支持向量机和a d a b o o s t 算法的基础上，本文对组合a d a b o o s t 和s v m 的可行性进 行研究，同时设计并实现原型工具对算法的可行性进行验证，最后通过实验对 a d a b o o s t s v m 和单个s v m 、a d a b o o s t s v m 和基于决策树的a d a b o o s t 算法进行性能比较， 实验表明：a d a b o o s t s v m 要优于其它的分类器。主要研究工作如下： 1 在新生儿疼痛表情特征数据的基础上，应用a d a b o o s t s v m 算法解决图像分类的问题。 2 在开源项目w e k a 和l i b s v l d 的基础上，设计实现原型评估工具一一基于 a d a b o o s t s v m 的新生儿表情分类系统。 3 通过实验对a d a b o o s t s v m 和单独的s v m 进行比较；对a d a b o o s t s v m 和基于决策树的 a d a b o o s t 分类器进行比较。 南京邮电大学硕士研究生学位论文 第二章支持向量机 2 1 支持向量机原理 第二章支持向量机 。 6 南京邮电大学硕士研究生学位论文 第二章支持向量机 缘。由于8 l 的边缘大于b 2 的边缘，因此8 1 就是训练样本的最大边缘超平面。 具有较大边缘的决策边界比那些具有较小边缘的决策边界具有更好的泛化误差。直觉 上，如果边缘比较小，决策边界任何细微的扰动都可能对分类产生显著的影响。因此，那 些决策边界边缘较小的分类器对模型的过分拟合更加敏感，从而对未知的样本上的泛化能 力很差。 统计学习理论给出了线性分类器边缘与其泛化误差之间关系的形式化解释，称为结构 风险最小化( s t r u c t u r a lr i s km i n i m i z a t i o n ，s r m ) 理论。该理论根据分类器的训练误 差r e 、训练样本数和模型的复杂度h ，给出了分类器的泛化误差的一个上界r 。形式化 的，在概率1 7 7 下，分类器的泛化误差在最坏情况下满足： 避+ 妒睁掣 亿妒 其中，矽是能力h 的单调增函数。 考虑一个包含个- v w i 练样本的二分类问题。每一个样本表示为一个二元组 ( ，儿) ( f _ 1 ，2 ，n ) ，其中薯= ( ，t ：，) 2 ，对应于第f 个样本的属性集。为方便记，令 ” - i ，1 ) 表示它的类标号。一个线性分类器的决策边界可以写成如下形式： w x + b = 0( 2 2 ) 其中，w 和b 是模型的参数。 任何位于决策边界上的样本都必须满足公式( 2 2 ) 。例如，如果屯和而是两个位于决 策边界上的点，则 伽+ 6 = 0 w x b + 6 = 0 两个方程相减便得到： w ( 屹- x b ) + b = o 其中，g 。一) 是一个平行于决策边界的向量，它的方向是从毛到。由于点积的结 果为0 ，因此，w 的方向必然垂直于决策边界，如图2 2 所示： 7 南京邮电大学硕士研究生学位论文第二章支持向量机 对于任何位于决策边界上方的方块t ，可以证明： t + 6 = 后 ( 2 3 ) 其中k 0 。类似地，对于任何位于决策边界下方的圆圈t ，可以证明： w t + 6 = 后 ( 2 4 ) 其中七 _ l - c j ，矿y ，= f ( w i ) 2 矽( 一) + 6 l 一嘭，矿y ；f 彰o ，j = l ， ( 2 1 7 ) 其中，训练数据薯通过函数和惩罚因子c 映射到一个高维空间。 南京邮电大学硕士研究生学位论文 第二章支持向量机 为了最大化压，i l ( 两组数据之间的边缘) 而最，j 、化( ) r 。如果数据是线性不 可分的，存在一个能够减少训练误差数量的惩罚短语：c y 。，董。可以在形式化短语 i 一，2 i ， ( ) r w f 和训练误差之间达到一个平衡。 在公式2 1 7 中，存在k 个决策函数： ( w 1 ) r 矽( x ) + b 1 ( 矿) r ( x ) + 6 七 其中，x 是这些决策函数的最大值： c l a s s “工暑a r gm a x ( ( ) t ( x ) + 6 j ) ( 2 1 8 ) 2 4 2 一对一方法 又献1 2 9 j 介缁了该方法，而文献1 3 0 ，3 1 j 首先把该方法应用到支持向量机中。该方法 建造后( 七一个分类器，且每一个分类器处理两个类的样本数据。对于训练第f 和第，类数 据，该方法试图解决下面的二分类问题： 捌参言( ) r + c ；? ( ) 7 ( w 扩) 2 矽( 薯) + 6 扩1 一第，f y ，= 7 ( w 扩) 2 矽( ) + 矿_ l - 舌t o ， 矿y ，f ( 2 1 9 ) 在建构所有的分类器后，有很多不同的方法进行测试。文献 3 0 采用投票策略：如果 s 初( ( w 9 ) r ( x ) + 矿) 显示出x 为第f 类，那么第f 类的投票个数加一。否则，第类的投票 个数增加一。根据最后投票我们可以决定x 属于哪一类。必须考虑的是该方法可能遇到两 个类的投票数是相同的情况。这里我们只是简单的选择为较小的分类号序号。 1 2 南京邮电大学硕士研究生学位论文 第二章支持向量机 2 4 3d d a g s v m 方法 该方法旨在解决一对一方法在测试阶段的相同投票数问题。它的训练阶段和一对一方 法是相同的，同样是训练出丛冬型二元支持向量机。然而，在测试阶段，它采用一种带根 z 二叉有向无环图，对于图中的每一个节点，要么没有出边，要么有两条出边，因此该图有 k ( k - 1 ) 内部节点和七条出边。其中，每一个节点是第f 和第类的二元支持向量机。给定 2 一个测试样本x ，算法从根节点开始，评估一个二元决策函数。然后根据输出值进入左子 树或者右子树进行递归处理。直到叶子节点，叶子节点也标记了该类。 定义2 1 ：给定一个空间x ，一组布尔函数f = 扩：x 专 o ，1 ) ，由定义在f 上的个 类别的有向无环图d d a g 决策的类d d a g ( f ) 可以被用作一个带根二叉有向无环图d d a g 来表 示，该有向图存在个出边，每一个出边被标记为类标号，每一个内部节点被标记为某一 个函数f 。图3 4 显示了一个4 类的决策有向无环图。 图2 1 一个4 类d d a g 给定输入x x ，为了评估一个特定的d d a g ，首先从根节点开始，根节点的二元布尔 函数被计算。如果函数值是o ，节点就从左出边进入左子树，否则就从右出边进入右子树。 同时计算下一个节点的二元布尔函数，直到到达叶子节点，叶子节点标记了类标号。d d a g 1 3 南京邮电大学硕士研究生学位论文 第二章支持向量机 和操作一个列表的效果相同，每一个节点都从列表中消除一个类标号。列表首先初始化为 包含所有类别的列表。如果一个节点是两个类中的其中一个，那么另外一个类从列表中排 除出去，并且d d a g 接着测试新列表中的第一个和最后一个元素。当仅仅只有一个类存在 于列表中为止。 2 5 小结 本章介绍了支持向量机的基本原理，在此基础上对核函数进行了简介，包括线性核函 数、多项式形式核函数、径向基核函数、s 型核函数和样条核函数，进而总结了s v m 的特 征。考虑到s v m 主要处理二分类问题，本章最后详细论述了当前s v m 在处理多类问题上的 主要策略。 1 4 南京邮电大学硕士研究生学位论文 第三章组合分类器 3 1a d a b o o s t 算法 第三章组合分类器 目前，组合方法( e n s e m b l em e t h o d ) 已经成为机器学习中一个主要的发展方向，它通 过合并多个中等精度的分类器来获得一个高精度的分类器。两个最常用的组合技术分别是 提升( b o o s t i n g ) 和装袋( b a g g i n g ) 技术。和装袋比较，提升技术在大多数情况下都优 于装袋技术【1 扪。 a d a b o o s t 是提升算法的改进，它是由f r e u n d s c h a p i r e 所提出【1 3 1 。旨在解决提升算 法存在的不足。例如：k e a r n s 和v a l i a n t 首先提出关于一个弱学习算法的问题，那就是一 个仅仅略好于随机投票的弱分类器经过提升算法之后能够建构成一个“强”的学习算法 4 7 , 4 8 。它同时也是一个迭代过程，用来自适应地改变训练样本的分布，使得基分类器聚焦 在那些很难分的样本上。而a d a b o o s t 给每一个训练样本赋一个权值，而且在每一轮提升 过程结束时自动地调整权值。 a d a b o o s t 的算法基本思想是：算法开始时，所有样本都赋予相同的权值，从而使得它 们被选作训练的可能性一样。根据训练样本的抽样分布来抽取样本，得到新的样本集。然 后，由该训练集归纳一个分类器，并用它对原数据集中的所有样本进行分类。每一轮提升 结束时更新训练样本的权值。增加被错误分类的样本的权值，而减少被正确分类的样本的 权值。使得分类器在随后迭代中关注那些很难分类的样本。 令( x j ，乃沙= 1 ，2 ，j 表示包含n 个训练样本的集合。在a d a b o o s t 算法中，基分类器c j 的重要性依赖于它们的错误率。错误率定义为： 毛= 始w , i ( e ( 。) 乃) 纽1 ， 其中，如果谓词p 为真，则i ( p ) = 1 ，否则为0 。基分类器c f 的重要性由以下参数给出： 铲l l n ( 字) 2 ， 如果错误率接近0 ，则口，具有一个很大的正值，而当错误率接近1 时，有一个很大 南京邮电大学硕士研究生学位论文 第三章组合分类器 的负值。参数q 也被用来更新训练样本的权值。为了说明这一点，假定表示在第j 轮 提升迭代中赋给样本k ，y 。) 的权值。a d a b o o s t 的权值更新机制由以下给出： = 默e ： z ；l ( 3 3 ) 其中，乃是一个正则因子，用来确保”= 1 。公式3 3 给出的权值更新公式增加 f 那些被错误分类样本的权值，并减少那些已经被正确分类的样本的权值。 a d a b o o s t 算法将每一个分类器q 的预测值根据q 进行加权，而不是使用多数表决的方 案。这种机制允许a d a b o o s t 惩罚那些准确率很差的模型；另外，如果任何中间轮产生高 于5 0 的误差，则权值将被恢复为开始值哆= k ，并重新进行抽样。一个基本的a d a b o o s t 算法如下( 图3 1 ) ： 1 ：输入：输入个带标记的训练样本集，咒l k ，儿) ，x n ，j ， ，好，选择基分类器( 例 如决策树) ，以及迭代次数r ，、 2 初始化：对所有的样本f = 1 , 2 ，n ，设置初始权值向量为d l 【f ) = 蜘。 w = w l = 专睁- ，2 ， 3 令k 表示提升的次数。 4f o rf = lt ok ，d o 5 根据w ，通过对d 进行抽样( 有放回) 产生训练集p 。 6 在皿上训练基分类器g 7 用c l 对原训练集d 中的所有样本分类。 8 通过下面公式计算加权误差： 岛2 专l 手嵋仃( c l ( _ ) 乃) j 9 如果加权误差蜀 0 5 ，那么 重置个样本的权值。m ，= 哗= 专i f = 1 ，2 ， ，并返回步骤4 。 l o 计算：昙l n 生兰 11 根据公式( 3 3 ) 更新每个样本的权值。 1 2e n d f o r 1 3 g ) = 缴m a x 柏 k ，l o g - “- ，- 1 图3 1a d a b o o s t 算法 对a d a b o o s t 组合分类器，其训练误差受下式的限制网： 1 6 m 只 = 、l，、i，鼍，i、， 勺勺 南京邮电大学硕士研究生学位论文第三章组合分类器 址兀网 ( 3 4 ) 其中e 1 是基分类器f 的差错率。如果基分类器的差错率小于o 5 ，则q = 0 5 一所，其中乃 度量了分类器比随机