（计算机应用技术专业论文）基于聚类的增量支持向量机动态构造方法研究.pdf

哈尔滨丁稃大学硕十学位论文 摘要 高速连续产生数据的数据流使得需要对原始数据集进行多次扫描挖掘的 传统方法变得力不从心。如何应用结构简单、具有全局最优、推广能力强且 应用最广泛技术之一的支持向量机在数据流上进行高效数据挖掘成为目前的 研究热点问题，其自身的计算复杂性成为处理大规模数据时的“瓶颈 问题。 本文针对数据流上应用支持向量机进行增量式挖掘这一问题，在分析研 究统计学习理论与支持向量机方法的基础上，针对数据流数据挖掘的特点， 研究了支持向量机增量学习方法，提出一种基于聚类的增量支持向量机的动 态构造方法。该方法利用k m e a n s 聚类分析方法调整增量学习算法中的训练 样本集，达到减小同一个样本集中的样本分布差异同时增大不同样本集之间 的样本分布差异，使在动态的数据流上数据特性更加明显，从而提高算法的 性能。其次，分析了现有分类器融合算法不适合多支持向量机分类器融合的 原因，提出一种基于聚类划分的多支持向量机分类器的融合算法，将那些被 某些分类器正确分类但被某些分类器错误分类的样本挑选出来单独处理，借 鉴c m c c 方法的构造过程，利用聚类的结果对特征空间进行划分，并统计 分类器的性能，最后选择在该划分中性能最佳的分类器作为系统的输出。 仿真实验的结果表明，本文给出的基于聚类的增量支持向量机动态构造 算法在分类性能上要优于传统的w m o d e l 增量学习算法，在此基础上提出的 基于聚类划分的多支持向量机分类器融合算法在融合精度上优于投票法、 k - n n 法以及c m c c 等方法。 关键词：统计学习理论；支持向量机；增量学习：聚类分析；分类器融合 哈尔滨工程大学硕十学位论文 a b s t r a c t t h ed a ms t r e a mi sp r o d u c e dc o n t i n u o u s l yw i t hh i g hs p e e d ，w h i c hm a k e st h e t r a d i t i o n a ld a t am i n i n ga p p r o a c hi n e f f e c t i v eb e c a u s et h eo r i g i n a ld a t as e t sa r e i t e r a t i v e l ys c a n n e d h o wt oa p p l ys u p p o r tv e c t o rm a c h i n ew h i c hi sc h a r a c t e r i z e d w i t hs i m p l es t r u c t u r e ，g l o b a lo p t i m i z a t i o na n dg o o dg e n e r a l i z a t i o ni nd a t as t r e a m m i n i n gh a sb e c o m ea h o tr e s e a r c h ，a n dt h ec o m p l e x i t yo f s u p p o r tv e c t o rm a c h i n e b e c o m e st h e b o t t l e n e c k ”p r o b l e mi nd e a l i n gw i t ht h el a r g e - s c a l ed a t as e t i no r d e rt od e a lw i t ht h ed a t as t r e a mm i n i n gw i t hi n c r e m e n t a ls u p p o r tv e c t o r m a c h i n e ，ad y n a m i cc o n s t r u c t i o na l g o r i t h mo fi n c r e m e n t a ls u p p o r tv e c t o rm a c h i n e b a s e do nc l u s t e r i n gi sp r o p o s e da f t e rs e v e r a li n c r e m e n t a ls u p p o r tv e c t o rm a c h i n e a l g o r i t h m sa n dt h ec h a r a c t e r i s t i c so f t h ed a t as t r e a mb a s e do nt h es t a t i s t i cl e a r n i n g t h e o r ya n ds u p p o r tv e c t o rm a c h i n ei sa n a l y z e d f i r s t l y , t h ek m e a n sc l u s t e r i n g m e t h o di su s e dt or e g u l a t et h et r a i n i n gd a t as e to ft h ei n c r e m e n t a ll e a r n i n g ，a i m i n g a tr e d u c i n gt h es a m p l ed i s t r i b u t i o nd i f f e r e n c eo ft h es a m ed a t as e t ，a n di m p r o v i n g t h es a m p l ed i s t r i b u t i o nd i f f e r e n c eo ft h ed i f f e r e n td a t as e t s t h i si sa b l et o a g g r a v a t e t h ec h a r a c t e r i s t i co ft h e d y n a m i cd a t as t r e a ma n di m p r o v et h e p e r f o r m a n c eo fa l g o r i t h m s e c o n d l y , a f t e rt h er e a s o nt h a tt h ee x i s t e dc l a s s i f i e r s c o m b i n a t i o na l g o r i t h m sa r en o ts u i t a b l ef o rm u l t i p l e s u p p o r tv e c t o rm a c h i n e s c o m b i n a t i o ni s a n a l y z e d ，t h em u l t i p l es u p p o r tv e c t o rm a c h i n e sc o m b i n a t i o n a l g o r i t h mb a s e do nc l u s t e r i n gp a r t i t i o ni sp r o p o s e d t h es a m p l e st h a ta r ec o r r e c t l y c l a s s i f i e db ys o m ec l a s s i f i e r sb u tm i s t a k e n l yc l a s s i f i e db yo t h e rc l a s s i f i e r sa r e p i c k e do u tt o d e a lw i t hs o l e l y t h ef e a t u r e s p a c ei sd i v i d e da c c o r d i n gt o t h e c l u s t e r i n gr e s u l t s ，w h i c hi ss i m i l a rt ot h ec o n s t r u c t i o np r o c e s so fc m c ca n dt h e c l a s s i f i e rw h i c hh a st h eo p t i m a lp e r f o r m a n c ei ss e l e c t e da st h ef i n a lo u t p u to f s y s t e m s i m u l a t i o nr e s u l t ss h o wt h a tt h e d y n a m i cc o n s t r u c t i o na l g o r i t h mo f 哈尔滨t 程大学硕士学位论文 i n c r e m e n t a ls u p p o r tv e c t o rm a c h i n eh a sab e a e rc l a s s i f i c a t i o np e r f o r m a n c e c o m p a r e dw i t ht h et r a d i t i o n a lw m o d e li n c r e m e n t a ll e a r n i n ga l g o r i t h r n a n da tt h e s a m et i m e ，t h ep r o p o s e dm u l t i p l es u p p o av e c t o rm a c h i n e sc o m b i n a t i o na l g o r i t h m b a s e do nc l u s t e r i n gp a r t i t i o nh a sb e r e rc o m b i n a t i o np r e c i s i o nt h a nv o t i n g ，k - n n a n dc m c c 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 gv e c t o rm a c h i n e ；i n c r e m e n t a l l e a r n i n g ；c l u s t e r i n ga n a l y z i n g ；c l a s s i f i e r sc o m b i n a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：泐丈 e l 期：伽6 年月ie l 哈尔滨工程大学硕十学位论文 第1 章绪论 1 1 选题背景与研究意义 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 是一种专门研究小样 本情况下机器学习规律的理论【i 习。针对小样本统计问题，该理论建立了一套 既考虑了对渐进性能的要求，又追求在有限信息的条件下得到最优结果新的 理论体系。2 0 世纪6 0 年代v a p n i k 等人发起了这一方面的研究，到2 0 世纪 9 0 年代中期，统计学习理论不断发展和成熟，开始受到越来越广泛的重视。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是在统计学习理论的基础 上发展的一种新的机器学习方法。该方法根据有限的样本信息在模型的复杂 性和学习能力之间寻求最佳折中，以期获得最好的推广能力，只要定义不同 的核函数，就可以实现其它现有的学习算法。正是由于这些优点，支持向量 机已经在众多领域取得了成功的应用。 尽管统计学习理论和支持向量机的发展已经逐渐成熟，但仍然有很多方 面不够完善，比如：许多理论目前还只有理论上的意义；由于本身具有较高 的时间复杂度和空间复杂度而不适于处理大规模的样本等等，这些问题都需 要进一步的研究。尤其是后者，是支持向量机在应用方面进一步推广的“瓶 颈”。随着网络技术和数据获取技术的发展，越来越多的数据以“流 的形式 需要在一定时间内完成处理，如何在源源不断的大规模数据流上应用在小样 本空间上性能优异的支持向量机方法，无疑是支持向量机的新颖应用。 1 2 研究内容 从全局的角度来看数据流，它是一种大规模的数据源；但是从局部的角 度来看，它则是由若干个连续的小规模的样本集组成的数据集。因此，在应 用支持向量机方法进行数据流挖掘时，需要考虑以下几个问题： 哈尔滨工程大学硕士学位论文 1 、如何进行增量学习 支持向量机是基于小样本空间的机器学习方法，因此不能直接将其应用 于数据流挖掘问题中。现有的解决方案一般是两种：增量学习与并行学习， 对于增量学习而言，需要考虑如何结合支持向量机的构造特点来组织数据子 集；而并行学习则是模拟多个并行运算节点对多个数据子集同时进行求解。 由于并行学习实际上是增量学习的一种变形，因此在本论文中一律以“增量 学习 进行阐述。 本论文研究了支持向量机的理论基础与构造方法，对现有的增量学习方 法进行了总结和分析，针对数据流挖掘的特点，选择了合适的增量学习方法 加以改进。 2 、如何动态构造支持向量机分类器 考虑到数据流的特点之一是数据的动态性，因此，在构造适用于数据流 挖掘的支持向量机时，也需要采取动态的方法。 本论文在研究已有的面向数据流挖掘的支持向量机构造方法的基础上， 分析了该方法的不足，提出一种基于聚类的增量支持向量机动态构造算法。 算法使用了聚类方法对初始化的训练样本集进行调整，使得相似的样本尽可 能被调整在一个训练集中，既增加了抽取的支持向量的代表性，又增强了各 样本之间的差异性，从而提高算法的效率。 3 、多个支持向量机分类器如何有效融合 考虑到采用多支持向量机对新增样本进行学习能够弥补由于单一分类器 造成的新增样本分布状况敏感度高的问题，因此，对于在数据流上构造的多 个支持向量机分类器如何进行有效的融合，也是本论文的研究内容之一。 本论文在研究了已有的分类器融合算法的基础上，提出一种基于聚类划 分的多支持向量机分类器选择算法。该算法在设计时充分考虑到了支持向量 机分类器的构造特性，在不同分类结果的样本集上进行聚类，再对特征空间 进行划分，统计划分区域上各分类器的特性，选择最优的分类器作为整个多 分类器系统的最终输出。 2 哈尔滨工挥大学硕十学位论文 1 3 国内外研究现状 支持向量机是基于统计学习理论的新型机器学习方法，是一种专门研究 有限样本分类和预测的学习方法，现已成为机器学习和人工智能界的研究热 点。支持向量机方法拥有完备的数学理论基础，是一种在高位空间表示复杂 函数依赖关系的高效通用手段，它是根据结构风险最小化原则来提高学习机 泛化能力的方法，即由有限训练样本取得的决策规则对独立的测试集仍能够 取得最小误差的一种方法。支持向量机算法是一个凸二次优化问题，能够保 证找到的极值解就是全局最优解。这些特点表明支持向量机是一种优秀的学 习算法，能够避免经典学习算法中存在的过学习、维数灾难、局部极小等问 题【3 j 。同时，支持向量机具有数学形式简单、几何解释直观、全局最优、学 习速度快、泛化能力优良、适合处理高维数据等特点，可以有效地用于许多 分类和回归问题中。目前，支持向量机已经成功的应用于模式识别、遥感图 像分析、非线性系统控制、函数逼近、回归估计和数据分类等众多领域1 4 - 7 。 支持向量机的提出相对其它学习理论来讲不是很久，属于新兴的学习理 论，尽管众多科研人员做了大量的研究工作，但其理论依据和算法尚有很多 问题有待发展和完善，如支持向量机算法中的核函数工作机理【s 。川，支持向量 机算法与其他学习算法关系 1 1 - 。】，支持向量机算法的i ) t l 练速度及其q p ( q u a d r a t i cp r o g r a m m i n g ) 问题的研究 1 5 - 1 9 ，支持向量机多类分类问题 1 9 - 2 0 l 以 及支持向量机增量学习算法等。其中，支持向量机的增量学习问题以其广泛 的应用背景和迫切的需求程度称为支持向量机学习算法中研究最热点的问题 之一，也正是本论文主要讨论和研究的问题。 对于支持向量机的增量学习问题，a h m e ds n 最早提出了s v m 增量训 练算法【2 1 1 ，该算法每次只选- d , 批常规二次算法能处理的数据作为增量，保 留原样本中的支持向量和新增样本混合训练。g a u w e n b e r g h sg 等人提出了增 量训练的精确解【捌，即增加一个训练样本或减少一个训练样本对l a g r a n g e 系 数和支持向量的影响，该算法是有效的。缺点是当样本无限增多时，还必须 放弃一些样本才能够实用，而被丢弃的样本中也可能包含数据集的分类信息， 哈尔滨t 程大学硕士学位论文 过快的样本丢弃率会影响增量学习器的分类精度，在初始样本比较少的情况 下，后继学习可能不稳定，产生振荡。 近些年增量支持向量机领域十分活跃，孔锐等人提出了一种快速增量学 习算法【2 3 】，该算法依据边界向量不一定是支持向量，但支持向量一定是边界 向量的原理，首先选择那些可能成为支持向量的边界向量，进行s v m 的增 量学习，找出支持向量，最终求出最优分类面，提高了训练速度。另外，张 波等人提出了基于中心距离比值的增量运动向量机( c d r i s v m y z , j ，利用中心 距离比值，在保证训练和测试准确率没有改变的情况下，大大提高了收敛速 度。李东晖等人提出了基于壳向量的线性s v m 增量学习算法【2 5 】，通过初始样 本集求得壳向量，进行s v m 训练，得到支持向量集，降低了二次规划过程 的复杂度，提高了整个算法的训练速度和分类精度。 对于单支持向量机的增量学习算法，萧嵘等人提出了s i s v m 方法【2 q ，通 过v a p n i k 的l a g r a n g e 函数鞍点求最优解时，最优解满足的条件为： c o = 咒西( t ) ，0 t r i c ，c t i y i = 0 i f 得出支持向量s v 集充分描述了整个训练数据集数据的特征，对支持向 量集的划分等价于对整个数据集的划分。s i s v m 算法把历史样本训练得到的 支持向量集、新增样本中的错分样本一起训练得到新的分类器，把历史样本 中的剩余样本和新样本的正确分类样本一起作为增量，多次迭代，直到增量 中的错分样本为空，收敛于所得分类器。为了加快对支持向量集搜索的手练 速度，萧嵘等人又提出了口i s v m 算法，有选择的淘汰一些对最终分类影响 很小的样本，从而缩减历史样本集的规模。此方法的时间复杂度为 d ( + d n 2 y ) ，远小于重新计算的复杂度，并且减少了对存储空间的占用， 但缺点是许多参数需要人为选择，增加了实用的难度，并对算法训练结果的 准确性产生不稳定因素。 b a t c h s v m 增量学习算、法【：7 】将新增样本分成互不相交的多个子集，对新 增样本分批训练，每次训练中把位于分类间隔以内的样本加入到历史样本 中，重新训练，直到所有新增样本都训练完毕。该算法降低了空间复杂度， 4 哈尔滨1 = 程大学硕士学位论文 但时间复杂度并没有提高。此外，该算法的应用还是在新增样本的子集具有 相似分布的前提下进行的。后来提出的d m m i s v m 算、法【：s 】改善了b a t c h s v m 增量学习算法中的不足，将历史样本分解成互不相交的n 个子集，训练出 n 个分类器r ，依次对新增样本训练，保留训练精度只，以分类精度小于 所给精度为循环条件，不断改善分类精度小于所给分类精度的分类器，以提 高整体算法的分类精度。 不同的分类器能够提供被处理样本的更多互补信息，因此，多分类器融 合方法往往能够达到比单个的最优分类器更好的性能【2 9 3 2 1 。采用多支持向量机 对新增样本进行学习能够弥补由于单一分类器造成的新增样本分布状况敏感 度高的问题，即采用多个分类器训练，降低新增样本对原分类器的敏感度。 总体来说，多分类器融合方法可以分成两类：分类器整合方法和分类器 选择方法。对于前者，分类器在整个样本的特征空间中的性能被认为是近似 相同的，根据各分类器的整体性能，这些分类器的输出按某种方式整合在一 起来达到一个共同的效果，常见的方法有：投票法、b o r d a 记数法、逻辑回 归法等；而后者考虑到了分类器在样本的特征空间中不同区域的性能存在着 差异，因此要找出在输入样本周围区域中具有最优局部性能的分类器，并以 该分类器的输出作为整个多分类器系统的输出结果。 分类器选择方法的核心问题是对特征空间的划分，w o o d s 等提出的 d c s l a 方、法【3 3 1 中，在样本周围的一个局部区域中估计各分类器的性能，并 从中选择局部性能最优的分类器，但由于要在测试阶段针对每个样本都要估 计分类器的性能，因此时间消耗很大；k u n c h e v a 提出的静态选择分类器的算 法则需要预先确定要划分的区域数目，并没有充分利用训练样本的类别等 信息，因此实用性并不强。文献 3 5 1 描述了一种基于近邻聚类的算法来划分 整个特征空间，但是对被正确分类和被错误分类两种情况的两种样本都进行 聚类分析，增加了运算时间。对于支持向量机分类器而言，因为该方法没有 考虑位于超平面之间的那些样本的分类情况，因此并不能取得有效的实验结 果。 哈尔滨t 程大学硕十学位论文 1 4 论文组织结构 本文内容共分4 章，组织结构及内容简单概括如下： 第1 章为本文的绪论部分，首先介绍了本文所选课题的研究背景，指出 所选课题的研究意义，然后重点介绍了支持向量机的发展历史及目前国内外 的研究现状。最后总结了本文做的主要工作。 第2 章详细地介绍机器学习及统计学习相关理论；介绍了支持向量机及 支持向量；讨论了线性可分、线性不可分及非线性情况的支持向量机的标准 算法；最后，介绍了支持向量机变形算法。 第3 章首先介绍数据流以及基于数据流的数据挖掘，阐述基于数据流的 特点采用增量式学习方式，介绍支持向量机增量学习算法的思想以及典型的 支持向量机增量学习算法。 第4 章对一种基于聚类的增量支持向量机动态构造方法进行介绍，在此 基础上提出了种基于聚类的多分类器融合方法。并且，对于提出的方法进 行了仿真实验和算法性能分析。 最后，总结了本文的主要研究成果，并指出了下一步的研究方向。 6 哈尔滨工程大学硕士学位论文 第2 章相关知识介绍 对支持向量机相关的机器学习理论，以及统计学习理论的基础知识进行 介绍，并就其相关的经验风险最小化、过拟合与泛化、学习一致性理论、v c 维理论以及结构风险最小化理论做了重点介绍，对支持向量机理论起到了一 个很好的理论支撑作用。 2 1 机器学习理论 机器学习( m a c h i n el e a m i n g ) 研究计算机怎样模拟或实现人类的学习行 为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的 性能。它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及 人工智能的各个领域。学习是人类智能的根本特征，但什么是学习，目前还 没有一个统一的定义。学习是一种具有多侧面的现象，包括：获取新知识； 通过教育或实践修正、精化原有知识或技能；归纳、演绎原有知识，将其组 成更为通用和有效的表示形式：借助观察或实验发现新的事实和理论等等。 在众多的观点中，以人工智能大师s i m o n 的观点最受推崇。s i m o n 认为：学 习就是系统在不断重复的工作中对本身能力的增强或改进，使得系统在下一 次执行同样或类似任务时，会比现在做的更好或效率更高【l ，。这种观点是从 行为的效果上去定义学习的本质，认为学习可以改善系统的性能，因而较为 普遍地接受。第二种观点则认为，学习是有用知识的获取过程。这一观点由 于具有较普遍的实用性而受到普遍的接受。 2 1 1 机器学习定义 什么是机器学习，至今也没有一个被广泛认可的准确定义。以字取意， 机器学习是研究如何使用机器来模拟人类学习活动的- - r - j 学科。从前面提到 的s i m o n 的学习观点出发，可以理解为，机器学习就是通过对人类学习过程 7 哈尔滨工程大学硕士学位论文 和特点的研究，建立学习理论和方法，并应用于机器，以改进机器的行为和 性能。机器学习起源于人工智能对人类学习能力的追求，上一阶段的研究几 乎完全局限在人工智能这一领域中，但通过多年的理论发展和应用研究，机 器学习已经开始进入了计算机科学的不同领域，甚至其他学科，成为一种支 持技术和服务技术。它的应用已遍及人工智能的各个分支，如专家系统、自 动推理、自然语言理解、模式识别、计算机视觉、智能机器人等领域。其中 尤其典型的是专家系统中的知识获取瓶颈问题，人们一直在努力试图采用机 器学习的方法加以克服。近年来，随着机器学习理论在诸多应用领域的成功 应用与发展，机器学习己成为计算机科学的基础及热点之一3 6 1 。 机器学习的基本思想就是通过让机器对大量信息的认知，进行内部学习、 分析归类、记忆存储和随时更新等处理过程，达到做出预测输出的目的。机 器学习的基本模型如图2 1 所示。 预测输出夕 图2 1 机器学习基本结构框图 机器学习模型包括三部分 3 7 1 ： 1 、产生器 产生随机变量x r 疗，它们可以从固定的概率分布函数f ( 工) 中独立取 得，但是该概率分布是未知的。 2 、训练器 对于每一个输入向量x 根据一个固定的条件分布函数f ( ylx ) 返回一个 输出值y ，产生输出值所用到的分布函数也是未知的。 3 、学习器 可以实现一定的函数集f ( x ，口) ，口人，其中人是参数集合。 机器学习的目的是根据给定的训练样本求出某系统输入输出之间依赖关 系的一个估计，使它能够对未知输出f ( x ，口) 做出尽可能准确的预测，其中， 8 哈尔滨t 程大学硕十学位论文 函数f ( x ，口) 由参数口控制。给定一个新输入的样本五，和一个特定的参数伍， 系统将给出一个唯一的输出厂( 玉，口) 。确定参数口的过程就是所说的学习过 程。 所谓的机器学习问题就是根据，个独立同分布的训练样本 ( 而，乃) ，( 葺，乃) ，其中，t r “；江1 ，2 ，为样本的数目，咒为类标 号，在一组函数 f ( x ，口) 中找到一个最优的函数f ( x ，口) 对依赖关系进行估 计，使它的期望风险最小。 r ( 叻= l l ( y ，f ( x ，o o ) d f ( x ，y ) ( 2 1 ) 其中 f ( x ，口) ) 称作预测函数集，盯为函数的广义参数。 f ( x ，) 可以表示任 何函数集。l ( y ，f ( x ，口) ) 为由于使用 f ( x ，口) 对y 进行预测而造成的损失函 数。不同类型的学习问题可以采用不同形式的损失函数。 目前，学习问题的形式化表述有很多方面，包括很多特殊的问题。其中， 最基本的机器学习问题有三类：模式识别、函数逼近和概率密度估计d 舯。 对于模式识别问题，输出y 可以分别表示为y = o ，1 ) 或y = 1 ，一1 ) ，被预 测的函数称作指示函数，损失函数可以定义为： ( 少，厂( x ，口) ) = 0 , f y = f ( x , a ) ( 2 - 2 ) 对于这个损失函数，式( 2 1 ) 的风险泛函确定了训练机器和指示函数 f ( x ，鳓所给出的不同概率。把训练机器的输出和指示函数的输出不同的情况 称作分类错误。所以对模式识别问题来讲，学习问题就是根据给定的样本数 据，在概率测度f ( x ，y ) 未知的情况下，寻找使得分类错误概率最小的函数 f ( x ，) 。 ” 在函数回归估计问题中，y 定义为连续变量，其损失函数可以定义为： l ( y ，f ( x ，口) ) = ( y - f ( x ，口) ) 2 ( 2 3 ) 此时，回归函数就是在损失函数( 2 2 ) 下使风险泛函( 2 1 ) 式最小的函数。 对于概率密度估计问题，学习的目的是根据训练样本确定工的概率密度， 被估计的密度函数记为p ( x ，此时的损失函数可以定义为 9 哈尔滨t 程大学硕+ 学位论文 l ( y ，f ( x ，口) ) = - l o g p ( x ，口) ( 2 - 4 ) 密度函数就是在损失函数( 2 3 ) 下使风险泛函( 2 1 ) 式最小的函数。 2 1 2 任务与评价标准 机器学习的任务主要包括以下两个方面【2 】： ( 1 ) 获得对于输入的数据进行分类的能力。如语音信号处理、文字识别、 各种图像处理等，医疗或故障诊断也可以认为是某种意义下的分类，甚至于 电子商务的交易过程。 ( 2 ) 获得解决问题、行为计划和行为控制等的能力。如解决微分问题、 下跳棋和象棋、平衡杠杆和驾驶车辆等。 一般地，可以从以下三个方面对学习系统的学习性能进行评价： ( 1 ) 学习精度：是否能够对输入的数据进行正确、精确的学习和分类。 学习系统的精度性能由分类规模、待分类样本的性质、学习系统的结构、学 习方法等多种因素决定。学习系统输出的结果也有多种形式，例如，分类的 结果是精确的还是模糊的、多义的，给出分类结果的同时是否还可以给出分 类结果的可信度等。 ( 2 ) 解答的正确性和质量：无论是用于分类的学习系统，还是解决问题 的学习系统，都有解答正确问题。同时，正确性不一定保证有好的质量，好 的质量包括可读性、稳定性等多方面的内容。 ( 3 ) 学习速度：虽然大多数学习系统的学习都是在后台进行的，但学习 速度仍然是一个很重要的系统指标。它不仅影响学习系统的设计，同时影响 其实现。一个很费时的学习方法，某种意义上来说也是难以实现的。 近几年，由于金融与经济数据分析、数据库知识发现、信息安全等的需 求，使得机器学习研究的观念发生了很大的变化，非线性、高维、海量数据、 直接面向用户等目标成为新的挑战。在这种需要下，归纳学习由于其性能的 欠缺使其绝对的优势地位有所改变，一些新的学习方法不断涌现，如基于解 释的学习、基于实例的学习等，这些学习方法受到了极大的关注。此外，遗 哈尔滨丁程大学硕士学位论文 传学习方法也有相当迅速的发展。从二十世纪八十年代开始，神经网络的研 究进入新的高潮。同时，由于信息化、网络化飞速的发展，数据挖掘、知识 发现的研究蓬勃发展，贝叶斯网络、决策树、神经网络等学习方法得到了深 入的研究和应用。近年来，各种各样的机器学习研究越来越受到人们的关注， 与机器学习有关的一些学术活动空前活跃，越来越多的机器学习成果应用到 实际应用中。 2 2 统计学习理论 基于数据的机器学习是现代智能技术中的重要方面，主要研究观测数据 ( 样本) 中的规律，并利用这些规律对未来数据或无法观测的数据进行预测。 传统统计学研究的是样本数目趋于无穷大时的渐进理论，现有学习方法也多 是基于这一假设。但实际问题中样本的数量往往是有限的，因此，一些理论 上很优秀的学习方法在实际中的应用并不理想。 与传统统计学相反，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 是一种专门研究小样本情况下机器学习规律的理论【3 2 】。v a p n i k 的著作的出 现是统计学习理论得到正式承认的标志。目前人们普遍认为统计学习理论主 要解决基于训练数据的目标函数和基于分布的目标函数之间的关系的问题 1 4 3 1 。下面具体介绍一些和支持向量机理论密切相关的统计学习理论。 2 2 1 经验风险最小化 从数学的角度来考虑，机器学习问题就是已知以个独立同分布的观测样 本，在同一组预测函数中求一个最优的函数对依赖关系进行估计，使期望风 险r 最小。损失函数是评价预测准确程度的一种度量，它与预测函数厂密切 相关。而的期望风险依赖于概率分布和损失函数，前者是客观存在的，后 者是根据具体问题选定的，带有主观偏好。期望风险的大小直观上可以理解 为，当用进行预测时，“平均 的损失程度，或“平均 犯错误的程度。 前面表述中指出学习的目标是使期望风险最小化，但由于概率测度 哈尔滨 = 程大学硕士学位论文 f ( x ，y ) 未知，可以利用的信息只有样本，公式( 2 1 ) 表示的期望风险无法 计算，如何定义机器学习产生的映射厂与实际系统的映射之间的差异成为关 键问题。传统的学习方法中更多采用了经验风险最小化准则( e m p i r i c a lr i s k m i n i m i z a t i o n ，e i 洲) ，即采用样本误差定义的经验风险。经验风险是用损失 函数来计算的。对于模式识别问题的损失函数来说，经验风险就是训练样本 错误率；对于函数逼近问题的损失函数来说，就是平方训练误差；而对于概 率密度估计问题的损失函数来说，e r m 准则就等价于最大似然法。 1 上 ( 功= 三( ”，f ( x i ，口) ) ( 2 5 ) i = 1 作为对( 2 1 ) 式的估计，设计学习算法使它最小化。对于损失函数( 2 2 ) 而言，经验风险就是训练样本的错误率；而对( 2 3 ) 式的损失函数，经验风 险就是训练误差的平方；而采用( 2 - 4 ) 式损失函数的经验风险最小化就等价 于最大似然方法。一些经典的方法，如回归问题中的最d x - - 乘法、极大似然 法都是经验风险最小化原则在特殊损失函数下的应用。传统的神经网络学习 方法也应用了经验风险最小化原则。 事实上，用经验风险最小化准则代替期望风险最小化并没有经过充分的 理论论证，只是一种直观上合理的想当然做法，但这种思想多年来却在机器 学习方法的研究中占据了主要地位。人们多年来将大部分注意力集中到如何 更好地最小化经验风险上，而实际上，即使可以假定当，趋向于无穷大时( 2 5 ) 式趋近于( 2 1 ) 式，但在很多问题中样本数目却无法接近无穷大。 由于利用经验风险化代替期望风险最小化并没有充分的理论依据，使得 经验风险最小化，即训练误差最小化并不总是导致好的预测效果，而且在某 些情况下反而会导致推广能力的下降，即真实风险的增加。 在某些情况下，经验风险最小化准则会导致过拟合( o v e r f i t t i n g ) 问题， 即当学习机器的学习能力足够强时，经验风险收敛很快，但不能保证收敛到 期望风险。过拟合问题是由于学习机器的泛化性能( g e n e r a l i z a t i o nc a p a c i t y ) 较差引起的。泛化性能定义为学习机器能够对观测样本之外的数据进行正确 映射的能力，它是评价学习机器性能的一个重要指标。问题在于，尽管观测 1 2 哈尔滨丁程大学硕七学位论文 i i iii - i 宣i ii i i 宣i i i i 宣i i i i i i i i i i ii i 宣ii i i i i i 萱i i i i 宣i i i i i i i i i i i i 宣i i i i i i i 嗣 样本独立同分布，却不能保证总体的独立同分布，这使得k h i n c h i n e 大数定 理的条件不能真正得到满足。e r m 准则对于观测样本之外的数据分布是未知 的，其泛化性能得不到有效保障。为解决e r m 的泛化问题，v a p n i k 和a j c h e r v o n e n k i s 研究了经验风险泛函的一致收敛问题m ，在此基础上建立了机 器学习的v c 理论。 2 2 2 学习一致性 所谓学习一致性( c o n s i s t e n c y ) ，就是指当训练样本数目趋于无穷大时， 经验风险的最优值能够收敛到真实风险的最优值。学习一致性及条件是统计 学习理论的基础。如果期望风险和经验风险都依概率收敛于最小可能的风险 值，则这时经验风险最小化归纳原则是一致的。经验风险和期望风险之间的 关系，可以用图2 2 表示，其中尺( ) 为实际可能的最小风险。 图2 2 经验风险和真实风险的关系不意图 定理2 1学习理论关键定理 对于有界的损失函数，经验风险最小化学习一致的充分必要条件是经验 风险在如下意义上一致地收敛于实际风险： l i r r 试s u p ( r ( c o ) - ( 动) e l = 0 ，v 0 ( 2 - 6 ) 。 m 其中，p 表示概率，为函数的广义参数，k ( 砌和r ( 妫分别表示在，1 个样本下的经验风险和对于同一个国的实际风险。 由于这一定理在统计学习理论中的重要性，被称作学习理论的关键定理， 由式( 2 1 ) 及式( 2 5 ) 可知学习一致性的问题既依赖于预测函数集，也依 哈尔滨工程大学硕士学位论文 赖于样本的概率分布。这一定理可以把学习一致性的问题转化为一致收敛问 题，也称为单边一致收敛，与此相对应的是双边一致收敛，即： l i m p s u p i ( r ( c o ) - r 唧( a o ) i 】- o ，v s 0 ( 2 7 ) p m 由于在学习过程中，经验风险和期望风险都是预测函数的泛函。学习的 目的不是用经验风险去逼近期望风险，而是通过求解使经验风险最小化函数 来逼近使期望风险最小化的函数，因此，其一致性条件比传统统计学中的一 致性条件更严格。虽然学习理论关键定理给出了经验风险最小化原理成立的 充分条件，但这一条件并没有给出什么样的学习方法能够满足这些条件。 2 2 3v a p nik - o h e v o n e n kis 维理论 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系 列有关函数集学习性能的指标，v a p n i k c h e v o n e n k i s 维( 简称v c 维) 是其 中最重要的一个定义。模式识别方法中v c 维的直观定义为m 】：对一个指示 函数集，如果存在h 个样本能够被函数集中的函数按所有可能的h 2 种形式分 开，则称函数集能够把h 个样本打散。函数集的v c 维就是它能打散的最大 样本数目h 。若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过一定的阈值将它转化成指示函数 来定义。 简而言之，v c 维描述了组成学习模型的函数集合的容量，即刻画了函 数集合的学习能力。v c 维越大，函数集合越大，其相应的学习能力就越强。 目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数 集知道其v c 维，例如在n 维实数空间中线性分类器和线性实函数的v c 维 是n + l ，而f ( x ，口) = s i n ( a x ) 的v c 维则为无穷大。对于比较复杂的学习机器， 其v c 维除了与函数集有关外，还受算法等其它因素的影响，其确定就更加 困难。对于给定的学习函数集，如何用理论或实验的方法计算其v c 维是当 前统计学习理论中有待研究的一个问题。 1 4 哈尔滨工程大学硕士学位论文 2 2 4 结构风险最小化 结构风险最小化( 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 i 蝴) 原则定义了在对 给定数据的逼近精度和逼近函数的复杂性之间的一种折衷。由于，经验风险 最小化原则在样本数量有限时是不合理的，需要同时最小化经验风险和置信 范围。其实，在传统的学习方法中，学习模型的选择过程本身就是调整置信 范围的过程，如果所选的模型比较适合现有的训练样本，就可以取得比较好 的置信范围。但因为缺乏理论指导，这种选择只能依赖先验知识和经验，造 成了如神经网络等方法对使用者经验的过分依赖。统计学习理论提出了一种 新的策略，即把函数集构造为一个函数子集序列，使各个子集按照v c 维的 大小从大到小排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经 验风险和置信范围，取得实际风险的最小，这种思想称作结构风险最小化， 如图2 3 所示。统计学习理论还给出了合理的函数子集结构应满足的条件以 及在结构风险最小化准则下实际风险收敛的性质。 风险 c 维7 i l 吃绣 子集sc 是( 2 2 墨 图2 3 结构风险最小化示意图 目前，结构风险最小化原则的实现主要有两种思路，第一种是从每个子 集入手，即在每个子集中求最小经验风险，然后选择使最小经验风险和置信 范围之和最小的子集。显然这种方法比较费时，当子集数目很大时不可行。 因此有第二种思路，即设计函数集的某种结构使每个子集中都能取得最小的 哈尔滨 二程大学硕七学位论文 经验风险，然后只需选择适当的子集使置信范围最小，再从这个子集中选出 使经验风险最小的函数，即最优函数。支持向量机方法实际上就是这种思想 的具体实现。 2 3 支持向量机概述 2 3 1 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 由v a p n i k 及其合作者发 明，在1 9 9 2 年计算学习理论会议上进入机器学习领域之后，便受到了广泛的 关注。s v m 建立在结构风险最小化原则基础之上，具有很强的学习能力和泛 化性能，能够较好地解决小样本、高维数、非线性、局部极小等问题，可以 有效地进行分类、回归、密度估计等。支持向量机以其独特的优势得到了全 面快速的发展，现已成为机器学习和数据挖掘领域的标准工具之一。 s v m 的主要思想可以概括为两点： ( 1 ) 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使 用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使 其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行 线性分析成为可能； ( 2 ) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平 面，使得学习机得到全局最优化，并且在整个样本空间的期望风险以某个概 率满足一定上界。 支持向量机是一种建立在统计学习理论的v c 理