（计算机应用技术专业论文）核方法的研究及其应用.pdf

摘要 摘要 自1 9 9 5 年v a p n i k 等人提出基于统计学习理论和核技术的支持向量机算法以 来，基于核的机器学习方法( 简称核方法) 取得了迅速的发展，目前已成为人工 智能和机器学习领域的研究热点之一，广泛用于图像处理、生物信息技术、文本 分类和入侵检测技术等多个领域。进一步研究支持向量机，无论对核方法理论的 完善和发展，还是对核方法在应用领域的进一步拓展，都具有十分重要的意义。 支持向量机在一系列的应用中表现出非常优越的性能。但是，其研究仍处于 初级阶段。理论研究与实际应用方面都还有许多问题需要加以解决，主要问题有： 对于大规模数据集的学习如何降低支持向量机的计算复杂度，针对具体的应用领 域如何构造高效的核函数等。 本文主要研究支持向量机的分类与回归，包括简化支持向量机以及支持向量 t ，芑， j 机在农业虫害预测预报中的应用，研究工作提高了支持向量机的分类性能，扩展 了其应用范围。主要创新工作有： ( 1 ) 针对支持向量机对于大规模数据集学习和决策效率低的问题，提出了基于 协同聚类的支持向量机算法，有效地减少了支持向量的数量，提高了分类速度。 针对多类分类问题，将协同聚类的方法进一步扩展，提出了基于协同聚类的多类 支持向量机。同时，对简约支持向量机和最小二乘支持向量机进行了改进。 ( 2 ) 考虑到径向基函数神经网络分类问题中，基函数中心的选取是其分类性能 的关键，提出了利用协同聚类选择基函数中心的方法。与采用模糊c 均值选取方 法相比较，提出的方法具有更好的分类性能。 ( 3 ) 针对大样本数据的回归估计，支持向量过多所引起的计算复杂度高的问 题，提出了一种基于协同聚类的支持向量回归机。实验结果表明提出的方法可以 明显减少测试时间，且回归正确率较好。 ( 4 ) 在介绍多镜像分类器算法的基础上，针对镜像点选取较为复杂的问题，利 用协同聚类的方法代替镜像点选取，提出了一种能有效地提高训练速度的多镜像 分类器算法。 ( 5 ) 农业信息化是我国现代农业技术的一个重要标志，虫害的预测预报工作是 农业信息化重要环节，提高其预测预报水平，可以减少虫害造成的损失，增加农 北京交通大学博士论文 业经济效益。鉴于支持向量机是一种模式分类和回归分析的有力工具，我们建 立了基于核方法的农业虫害预测预报模型，并将我们提出的算法应用到农业虫害 预测预报中，取得了较好的效果。 关键词：统计学习理论，支持向量机，协同聚类，核方法，核函数，回归分 析，预测预报，人工神经网络 a b s t r a c t s in i c ep r o f v a p n i kp r o p o s e dt h es u p p o r tv e c t o rm a c h i n e ( s v m ) b a s e do n s t a t i s t i c a ll e a m i n gt h e o r yi n19 9 5 ，k e r n e lm e t h o db a s e dm a c h i n el e a r n i n ga l g o r i t h m h a sb e e nd e v e l o p e dr a p i d l y i tb e c o m e so n eo ft h eh o tp o i n t si na c a d e m i c r e s e a r c hn o w a n dh a sb e e nw i d e l yu s e di ni m a g ep r o c e s s i n g , b i o l o g yi n f o r m a t i o nt e c h n o l o g y , t e x t c l a s s i 6 c a t i o na n di n t m s i o nd e t e c t i o n ，e t c s o i ti so fg r e a ts i g n i f i c a n c ef o rb o t ht h e d e v e l o p m e n ta n di m p r o v e m e n to f k e r n e lt h e o r ya n di t se x p a n s i o no fa p p l i c a t i o n t h o u g hs v m h a ss h o w ne x c e l l e n tp e r f o r m a n c ei nm a n yf i e l d s ，i ti ss t i l li ni t se a r l y s t a g e m a n yi s s u e si nt h et h e o r e t i c a lr e s e a r c ha n dp r a c t i c a la p p l i c a t i o n sa r e s t i l lt ob e s o l v i 。d ，e g ，h o wt or e d u c et h ec o m p l e x i t yo f t h es v mw h e nt r a i n e do nl a r g e s c a l ed a t a , a n dh o wt oc o n s t r u c tn e wk e r n e lf u n c t i o n sf o rs p e c i f i ca p p l i c a t i o nf i e l d s t h i sp a p e rm a i n l ys t u d i e ss v mc l a s s i f i c a t i o n a n dr e g r e s s i o n ，i n c l u d i n gt h e s i m p l i f i c a t i o no fs v m ，a sw e l l a si t sa p p l i c a t i o ni na g r i c u l t u r a l p e s tf o r e c a s t t h e c l a s s i l e i c a t i o np e r f o r m a n c ei si m p r o v e da n dt h ea p p l i c a t i o nf i e l d s a r ee x p a n d e d t h e m a i nr e s u l t sa r ea sf o l l o w s ： ( 1 ) a sf o rt h el o we f f i c i e n c yo ft h et r a i n i n ga n dd e c i s i o n - m a k i n go f t h es v mo n l a r g e s c a l ed a t a a ns v ma l g o r i t h mb a s e do nc o o p e r a t i v ec l u s t e r i n g 1 sp r o p o s e d ，1 n w h i c hm en m n b e ro fs u p p o r tv e c t o r s i sr e d u c e de f f e c t i v e l ya n dt h es p e e d o f c l a s s i f i c a t i o ni sa l s oi m p r o v e d a sf o rt h em u l t i c a t e g o r yc l a s s i f i c a t i o n ，b y f u r t h e r e x p a n s i o no ft h ec o o p e r a t i v ec l u s t e r i n g ， am u l t i - c a t e g o r yc l a s s i f i c a t i o nm e t h o di s p r e s e n t e d ；r s v ma n dl s s v ma l g o r i t h m a r ei m p r o v e d ( 2 ) t h ec e n t e ro fr b fi st h ek e yt o t h ep e r f o r m a n c eo fr b f n e u r a ln e t w o r k c l a s s i f i c a t i o np r o b l e m s am e t h o do fs e l e c t i n gt h ec e n t e ro fr b f i si l l u s t r a t e d ，w h i c hi s b a s e do nc o o p e r a t i v ec l u s t e r i n g c o m p a r i s o nr e s u l t sw i t ht h ek - m e a n ss e l e c t i o nm e t h o d s h o wt h a tt h ep r o p o s e dm e t h o dp e r f o r m sb e t t e r ( 3 ) f o rc o m p u t i n gc o m p l e x i t yi sh i g hd u e t os u p p o av e c t o r sa r em u c hw h e nl a r g e s 锄p l eo fr e g r e s s i o nf u n c t i o ni s e s t i m a t e d ，am e t h o do fr e g r e s s i o ns v mb a s e do n c o o p e r a t i v ec l u s t e r i n gi sp u tf o r w a r d e x p e r i m e n t a lr e s u l t ss h o w t h a tt e s tt i m en e e d e d b yt h i sm e t h o di ss i g n i f i c a n t l yl e s st h a no t h e r s ，a n dt h er e g r e s s t o np r e c i s i o n i sh i g h e r t h a no t h e r s ( 4 ) b a s e do nam u l t i p l em i r r o rc l a s s i f i c a t i o na l g o r i t h m ，a n dw i t hr e s p e c tt ot h ef a c t m a tm es e l 蕊o no fi m a g ep o i 幽i sq u i t ec o m p l e x ，an e w m u l t i p l em i f r o rc l a s s l t l c a t i o n a l g o r i t h mi sp r o p o s e d ，i nw h i c h t h em i r r o rp a i r sa l er e p l a c e dw i t hc o o p e r a t l v ec l 璐t e l l n g p a i r sa n dm e 仃a i n i n gs p e e d i su p 伊a d e de f f t i v e l y ( 5 ) a 曲c u l t u r e i n f o r m a t i o ni sa l li m p o r t a n ts y m b o l o fm o d 锄a 口c u l 删 t e c h n i q u 岱i no u rc o u n t r y ； f o r e c a s to fp e s ti s a ni m p o r t a n ti i n kma g p c u i t u _ r e i n f o m l a t i o n h i i p r o v i n gt h el e v e lo fp r e d i c t i o n , w ec a n d e c r e a s ep e s td 撇a g e 觚d i n c r e a s ee c o n o m i cb e n e f i t b e c a u s et h es u p p o r t v e c t o rm a c h i n ei sap o w e r f u lt o o lo f r c 肿s s i o na n dc l a s s i f i c a t i o n ，w eh a v eb u i l tak e r n e l m e t h o db a s e d 唧c u l t u r a lp e s t f o 僦a s t i n gm o d e 1 l h ep r o p o s e dm e t h o d sa l ea p p l i e di nt h ep r e d i c t i o n o fa g n 铡l t u r a l p e s t sa n d t h er e s u l t sa r eq u i t eg o o d k e vw 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 tv e c t o rm a c h i n e ，c 0 0 p 耐1 v e c l u 曲e r i n 盘k e m e lm e t h o d ，k e r n e lf u n c t i o n , r e g r e s s i o na n a l y s i s ，f o r e c a s t ，a r t l t i c l a l n 鳓1 1 a 1n e t w o r k 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 导师签名： 签字日期：年月日签字日期：年月日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月日 1 0 3 致谢 本论文是在我的导师田盛丰教授的悉心指导下完成的。从选题到研究，直至 论文的最后完成都凝聚了导师的大量心血。导师渊博的知识、严谨的治学态度、 敏锐的观察力和一丝不苟的敬业精神将使我终身受益。导师不仅为我创造了良好 的学习和科研环境，而且对于我的生活也是关心备至。值此论文完成之际，谨向 尊敬的田老师致以衷心的感谢和诚挚的敬意! 在本文的研究与撰写过程中，得到了黄厚宽教授和于剑教授热心的指导和无 私的帮助。在研究过程中正是他们提出的许多宝贵意见和建议，让我受益匪浅， 在此对黄老师和于老师表示深深的谢意。 衷心感谢王志海教授、林有芳副教授和瞿有利高工以及系里其他老师在学习 和科研工作中给予我的关心和帮助。 在博士学习和论文写作期间，还得到实验室许多同学的帮助，与各位同学的 讨论和交流使我受益匪浅，使我得到了很多有价值的启示和建议，他们是：尹传 环、董兴业、李昆仑、王黎明、贺志、赵翔、董红斌、邓大勇、裴振奎、魏明元、 李向军、陈萍、张莹、赵静、汪廷华等。他们的真诚合作与帮助使我愉快地度过 了读博期间的学习生活，在此一并向他们表示诚挚的谢意! 特别要感谢我的父母及妻子时爱菊女士。在读博期间，正是由于他们的关心、 理解和支持，才使我能够有充沛的精力和充足的时间完成科研工作，没有他们的 付出就不可能有本论文的顺利完成。 最后，谨以本文献给所有关心、帮助和爱护我的老师、亲人和朋友! 第一章绪论 1 1 研究背景 第一章绪论弟一早三百了匕 随着计算机技术的飞速发展，数据采集的速度和数据存储容量都有了极大的 提高，产生了各种大量数据，如人类基因组测序得到的d n a 数据，电信部门的日 常运行数据和农业病虫害的监测数据等。面对这些不断快速增长的数据，如何利 用信息技术对其进行更加有效的处理，并转化为人们可以理解和操纵的知识，进 而提高科学研究、市场分析和预测预报等的效率，既是人们需要迫切解决的问题， 也是计算机工作者研究和关注的焦点。 知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 正是在此背景下提出的，成 为当前数据库技术与人工智能领域研究的热点课题 1 】。机器学习( m a c h i n e l e a r n i n g ，m l ) 是知识发现的重要方法之一，是研究计算机模拟或实现人类的学习 行为，以获取新的知识或技能，重新组织已有的知识结构，使之不断改善自身的 性f l 皂 2 】。机器学习的应用遍及多个领域，如专家系统、人脸识别、语音识别、计 算机视觉和网络安全等。常用的机器学习方法包括支持向量机、贝叶斯网络、遗 传算法、决策树和人工神经网络等。 机器学习发展至今，大体上经历了以下四个阶段 3 8 】： ( 1 ) 第一阶段 1 9 5 7 年，美国计算机科学家r o s e n b l a t t 首次提出了模拟人脑感知和学习能力 的机器学习模型一感知器( p e r c e p t r o n ) 。它是一个具有单层计算单元的前向神经网 络，这标志着人们对机器学习过程进行理论研究的开始。单层感知器是一个具有 一层神经元、采用阈值激活函数的前向网络，通过对网络权值的训练，可以使感 知器对输入向量的响应达到元素为0 或l 的目标输出。因此，可以用于解决模式 识别问题。 ( 2 ) 第二阶段 始于上世纪的6 0 年代，学习理论基础的创立为这一阶段的标志。在这个阶段， 统计学习理论的核心概念- v c ( v a p n i k & c h e r v o n e n k i s ，v c ) 熵和v c 维已经提出 【9 - 1 0 。利用这些概念，发现了泛函空间中的大数定理，研究了它与学习过程的联 系，并得到了关于收敛速率的非渐近界的重要结论。 这个时期的主要工作包括：经验风险最小化原则理论的建立与逐步完善；结 北京交通大学博士学位论文 构风险最小化原则理论的建立；解决不适定问题的理论；密度估计的非参数方法 以及算法复杂度的思想，学习问题的基于最小描述长度( m i n i m u md e s c r i p t i o n l e n g t h ，m d l ) 的归纳推理理论的形成 9 - 1 0 。 ( 3 ) 第三阶段 1 9 8 6 年，r u m e l h a r t 等人提出了多层感知器的反向传播学习( b a c kp r o p a g a t i o n ， b p ) 算法【1 1 1 ，该算法是神经网络理论与应用的一次重大突破，其学习过程由信号 的正向传播与误差的反向传播两个过程组成。在正向传播过程中，输入信息从输 入层经隐单元层逐层处理后，传至输出层。每一层神经元的状态只影响下一层神 经元的状态。同时，将期望的输出和实际输出之间的二次误差沿原来的传递通路 反向传播到输入层，并以此调整各层神经元的权值系数，最终使得误差信号最小。 该阶段是神经网络的最活跃阶段，其丰硕成果使得在此期间其它机器学习方 法无法与其比拟。b p 算法的提出是感知器的一次飞跃，这个阶段的感知器也被称 为神经网络，在数字识别等应用问题上体现出较好的性能。 ( 4 ) 第四阶段 针对神经网络的不足，产生了统计学习理论，即研究小样本条件下机器学习 规律的理论。1 9 9 5 年，v a p n i k 在t h en a t u r eo fs 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 tv e c t o rm a c h i n e ， s v m ) 3 】。与神经网络相比，对于有限样本的学习问题，其具有更嚷实的数学理论 基础，可有效地解决有限样本条件下的高维模型构建问题，并具有更强的推广能 力 1 2 - 1 7 。 基于核的机器学习方法或称核方法( k e r n e lm e t h o d ，k m ) 是以支持向量机为核 心算法的一类新的机器学习方法，是统计学习理论与核技术相结合的产物。它具 有两个显著的特点 1 8 】：首先是在线性与非线性间架设起一座桥梁，其次是通过巧 妙地引入核函数，避免了维数灾难，也没有增加计算复杂度。目前，支持向量机 已成为核机器学习领域内重要的研究内容之一。对支持向量机的深入研究，无论 是对核方法的进一步发展，还是对其在数据处理中的实际应用，都有重要的意义。 本论文就是以支持向量机为主线，对核方法展开研究工作的。 1 2 核方法的研究现状 核理论的研究可以追溯到1 9 0 9 年，m e r c e r 在泛函分析中提出了再生核( m e r c e r 核) 和再生核h i l b e r t 空间。1 9 5 0 年，a r o n s z a j n 等人对其进行了进一步完善 1 9 1 。 1 9 6 4 年，a i z e r m a n 等人将再生核技术用于学习理论的证明【2 0 】。1 9 9 5 年，统计学 2 第一章绪论 习理论的创始人v a p n i k 等人利用“核技巧”( k e r n e lt r i c k ) ，即通过引入核函数代替 内积，构建了一种新的核方法一支持向量机。该方法大大提高了学习性能，掀起 了机器学习领域的一场革命，进一步推动了核理论和核机器学习研究的热潮 【2 1 - 2 2 1 。 此后，研究人员相继提出了许多不同的核方法以及针对支持向量机的改进算 法，使得核理论不断地完善，应用领域不断扩大。1 9 9 8 年，s c h 6 1 k o p f 等人对线性 主成分分析( l i n e a rp r i n c i p a lc o m p o n e n ta n a l y s i s ，l p c a ) 方法进行核化，得到了相 应的核主成分分析( k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ，k p c a ) 方法【2 3 】。核典型相 关分析( k e t n e lc a n o n i c a lc o r r e l a t i o n a n a l y s i s ，k c c a ) 是由m i k a 等人于1 9 9 9 年提出 的方法，是模式识别中进行特征提取的重要技术 2 4 1 。为了更加有效地解决处理结 构数据问题，充分利用数据间的结构特征，研究人员构造了一种特殊的核函数即 结构化数据核函数，如使用邻域核识别纹理图象 2 5 1 ；使用字符串核和词序列核进 行文本分类 2 6 】；使用边界化核进行蛋白质分类等 2 7 】；j a a k k o l a 等人把隐马尔可 夫模型与根据背景知识所设计的核函数相结合，通过支持向量机，在部分资料遗 漏的情况下，仍可取得较好的检测效果【2 8 】。另外，核方法通常采用的是单核学习， 即在学习过程中使用一个核函数。近年来，随着对核方法的深入研究，针对多数 据源或异构数据集问题，s o n n e n b u r g 等人提出了多核学习的概念 2 9 - 3 0 。与单核 学习相比，多核学习可以提高分类精度，鲁棒性更强。r a t s c h 等人则将多核学习 用于生物序列数据的分类，取得了良好的效果 3 1 】。 虽然支持向量机在一系列的应用中表现出非常优越的性能，如支持向量机可 以降低分类面的复杂度，提高分类精度等。但是，支持向量机的研究仍处于初级 阶段，理论研究与实际应用方面都还有许多问题需要加以解决，概括起来主要有 以下几点： 1 核函数的研究 核函数的思想在现实世界中有着广泛的应用。如果一个分类或回归问题，涉 及到点积运算，那么就可以通过引入核函数将问题映射到高维空间中去解决。 目前，核函数的研究工作主要集中在两个方面：一是研究已有核函数的参数 如何选取，即核参数选取的优化问题：二是根据实际应用问题提供的数据，构造 新的高效核函数。关于核参数的选择与核函数的构造等问题的研究虽然已经取得 了一些进展，但是仍不能令人满意 3 2 3 4 。核参数的选择是能否取得理想的预测 结果的重要因素之一，而目前核参数的选择大多数是靠人工估计，根据经验进行 选择，显然存在一定的随意性和局限性。如何构造与实际应用问题有关的核函数， 一直是s v m 研究的重要课题。 3 北京交通大学博士学位论文 另外，s v m 可直接处理向量数据，但是对于结构数据，如字符串、图像和蛋 白质等无法直接输入，如何将结构化数据转换成向量，即构造结构化数据核函数， 然后应用到支持向量机等核方法中，仍是一个亟待解决的难题。因此，构造适合 的结构化数据核函数，设计出高效的核方法也是研究的一个热点。 2 降低支持向量机的计算复杂度 支持向量机的应用受到限制的一个很重要的原因就是需要求解凸二次优化问 题，对于大规模样本的数据集，其计算具有较高的时间和空间复杂度。因此，如 何在不影响分类性能的前提下，降低计算复杂度，提高学习速度，建立高效的求 解支持向量机中的最优化问题算法，成了支持向量机一个很重要的研究方向。其 有关研究工作将在第三章详细介绍。 3 直推式学习 目前分类的研究工作大多是试图设计某种分类器，使其对未来所有可能样本 的预期性能最优 3 5 】。但在很多实际应用中，由于对样本标号需要领域的专家知识 或者需要通过仪器设备的检测，有时成本代价较高，不可能也不必用这样的分类 器对所有可能的样本进行识别，而往往只需要对一些特定的样本进行识别。于是 可以考虑设计一种更为经济和风险最小的分类器，用它来建立一种直接从己知样 本出发对特定的未知样本进行识别和分类的方法和原则。这种推理方式称为直推 式推理( t r a n s d u c t i v ei n f e r e n c e ) 。统计学习领域的直推式学习是一个较新的研究内 容。 1 9 9 8 年，v a p n i k 提出了种半监督机器学习的方法，即直推式支持向量机 3 6 1 。 它是将无标号和有标号数据作为训练集，训练集中仅含有少量有标号和多数无标 号的样本点，大大减少了对有标号样本的需求。直推式学习的特点是：较充分利 用了无标号数据的分布信息，仅考虑在某个指定数据集上的分类精度，而不考虑 在其它数据集上的情况。与归纳式学习相比，直推式学习往往更具普遍性和实际 意义。目前，见到的应用有文本分类、生物信息学中的蛋白质分类等 3 7 3 8 】。但 是，其缺点是无标号样本的动态调整具有一定的随机性。还有与标准的s v m 相比， 直推式学习在线学习的功能差。陈毅松提出了一种新的渐进直推式s v m 3 9 ，可以 在学习过程中对无标签样本点进行动态的调整，较好地适应各种不同的训练样本 的分布。直推式学习仍有许多问题需要解决，值得研究人员深入的研究。 4 多类支持向量机 支持向量机最初是针对二类分类问题提出的，不能直接应用到多类分类问题 中。因此，如何将二类分类方法有效地推广到多类问题，特别是大类别的分类问 4 第一章绪论 题，也是支持向量机理论研究的重要内容之一。 目前，构造s v m 多类分类器的策略主要有以下两种 4 0 州】： 一是直接在多类分类目标函数上进行修改，建立多类分类支持向量机，实现 对多类问题的一次性求解 4 5 t 。其基本思想与下面提到的一对多类似，也是需要构 造多个二类分类器，但不同的是一次性求解多类分类方法是用一个优化问题同时 求解多个二类分类器。这类算法的缺点是变量数目较多，计算复杂度太高，训练 时间较长，不适用于大规模样本的数据集。 二是构造多个支持向量机的二值分类器，将这多个二类分类器组合，来实现 多类分类，这种多类分类方法主要有以下几种。 ( 1 ) 一对多( o n e - a g a i n s t r e s t ) 其基本思想是将某一类的样本作为正类，将剩余类的样本当作负类，这样多 类分类就变成一个二类分类问题。如果有，z ( 厩：2 ) 个类，则m 个类的分类问题就转 化为m 个二类分类的问题。测试时，样本属于决策函数输出值最大的那一类。该 算法主要存在两个缺点：一是当有多个分类器输出的值都达到最大时，无法判断 测试样本的归属类；二是可能会导致正负二类样本数目严重不对称，影响分类性 能。 ( 2 ) 一对- - ( o n e - a g a i n s t o n e ) 该算法是在m 类训练样本中构造所有可能的两类分类器，共需要构造m ( m 一1 ) 2 个二类分类器。其确定样本属于那一类的最常用的方法是最大投票法，即每个二 类分类器都对新样本的类别进行判定，通过投票的方式对相应的类别投上一票， 得票数最多的类为新样本所属的类。此算法的缺点是：分类器的数目会随着类别 的数目m 的变大而急剧增加，导致在决策速度过慢。再者就是当两个类别的票数 相同时，产生不可分的情况。 【3 ) 纠错码方法( e r r o rc o r r e c t i n go u t p u t c o d e sm e t h o d ) 该方法是对类别进行二进制编码，将多类问题转化为多个二类问题。采用纠 错码对类别进行编码，将支持向量机作为码位分类器。 其基本思想是建立一个m x p 的纠错码矩阵，其中m 为类别数，p 为最终决策 函数的个数( 决策函数的输出为1 或一1 ) 。在纠错码方式中，我们构造了p 个两类问 题，每一类都成为某一个两类问题的正样本或者负样本，因此，这个矩阵的每一 项用l 和一1 填充，而在测试样本点石时，计算p 个决策函数关于z 的值，得到一 个元素为1 或一1 的数列，然后将这个数列与纠错码矩阵相比较，如果矩阵中有与 数列完全相同的某一行，则x 必然属于这一行对应的类。如果没有完全相同的某 5 北京交通大学博士学位论文 一行，则根据纠错码矩阵对数列进行纠错，从而找到x 对应的类别。z h a n g 等人选 用h a d a m a r d 矩阵作为纠错码矩阵，取得了比较好的应用效果 4 6 1 。 ( 4 ) 支持向量机决策树 支持向量机决策树是将s v m 和二叉树结合起来，解决多类分类问题。该方法 的基本思想是将所有的类别分成两个子类，再将子类迸一步划分成两个次级子类， 重复执行此过程，直到所有的节点只包含一个类别为止。此方法显然可以避免类 别不可分的情况，并且只需要构造t i t 1 个二类分类器。其优点是测试时，分类速 度快，节省时间。但是，其缺点是分类结果依赖于决策次序，当某个节点发生分 类错误，会产生错误的传递，使下级节点的分类失去意义。 5 增量学习的研究 当训练样本数据过大，无法一次性读入内存或在线学习情况下，训练开始时 无法得到所需要的全部数据时，可以采用支持向量机的增量学习算法( i n c r e m e n t a l l e a r n i n g ) 。将训练集分成几个独立的子集，依次在各个子集上作增量学习，这样不 仅可以舍去无用的样本，节省内存空间，缩短训练时间，而且可以充分地利用以 前的学习结果，使得学习结果具有延续性【4 7 4 8 】。 目前，国内外研究支持向量机增量学习的方法大体上可以分为以下四大类， 即错误驱动法、固定划分法、过间隔法、错误驱动与过间隔结合的方法 4 9 】。 错误驱动法的主要思想是保留支持向量机错分的样本，一旦错分的样本达到 某个给定的阈值时，错误分类的数据与支持向量机的支持向量一起作为训练样本， 用于构造新的支持向量机。此方法简单实用，在分类精度要求不高的情况下，可 以采用此方法。 固定划分法的主要思想是将训练的样本分割为大小固定的集合，当新增的数 据装入内存时，将其与支持向量作为训练集，用于构造新的支持向量机，而所有 的非支持向量样本被丢弃。 过间隔法的主要思想是假设在某个时刻t 的支持向量机为s v m 。，新增加的样 本为 x i , y t ) ，如果溉y 0 越过s v m ，定义的间隔，则保留样本点，否则丢弃此样本点。 选择一个阈值他，如果越过边界的样本点大于肛，则将这m 个样本点与s v m 。的 支持向量一起作为训练样本，构造新的支持向量机s v m f + i 。 错误驱动与过间隔结合法的主要思想是假设在时刻t 的支持向量机为s v m , ， 支持向量为s v 。新增加的样本为 x i , y i ，如果 x i , y i ) 越过s v m ，定义的间隔时，则 保留样本点，否则使用s v m ，对其分类；如果错误分类，保留此样本，否则舍去此 样本。一旦过间隔或错误分类的样本达到阂值他，则使用这他个样本与支持向量 s v ，做为训练集，构造新的支持向量机。 6 第一章绪论 6 多核学习的研究 由于实际应用中经常出现的异类数据源，近年来研究人员提出了基于多核学 习( m u l t i p l ek e r n e l ) 的支持向量机以及实现算法。在现实世界中，往往存在大量的 数据是针对多数据源或异构数据集的，采用单个核函数的效果不是太理想。例如， 输入空间是两个向量组成的空间，第一个向量服从高斯分布，而第二个向量却服 从多项式分布。这时，如果仅仅采用一种核函数就显得不足，若用高斯核函数则 无法利用第二个向量进行有效划分，而如果采用多项式核函数则由于第一个向量 的存在会给分类造成影响。因此，如何进一步研究高效的多核学习的方法成为研 究核方法的热点之一。 多核学习有两层含义：一是可以一次针对不同的属性选择参数不同的核函数， 如根据不同的属性可以选择高斯核函数的不同宽度；二是针对不同的属性选择不 同种类的核函数，如根据不同的属性可以在学习过程中同时选择高斯核函数和多 项式核函数。使用多个核函数的组合，即使不知道最优参数，也可以通过调整权 值找到最合适的参数，显然使用多个核函数的组合要比单个核函数的鲁棒性更强。 7 开拓支持向量机新的应用领域 目前，s v m 与其它核方法主要应用于解决分类与预测问题。分类问题主要包 括文本分类、人脸识别和生物信息处理( 如d n a 数据的分析) 等。预测问题主要包 括时间序列预测和股票市场的分析等。如何进一步拓展新的应用领域，解决更多 的实际问题，也是值得研究的内容。 本文将提出的分类和回归算法应用到农业虫害的预测预报中，取得了较好的 结果。 1 3 核方法的应用 目前，核方法的应用领域非常广泛，主要有以下几个方面： 1 数字识别 手写数字识别是一个传统和典型的模式识别问题，属于光学字符识别技术的 分支。支持向量机最早的应用就是手写数字识别 3 】。手写数字识别己成为测试分 类器性能优劣的一个标准问题，它起源于美国邮政系统自动分拣手写邮政编码的 信函。主要有两个标准的数据库u s p s 和n i s t ，其是一个典型的多类分类。v a p n i k 构造了处理多类问题的支持向量机，主要采用的是多项式核函数、高斯核函数和 s i g m o i d 核函数。其实验结果表明，与其它分类方法相比，支持向量机取得了较好 7 北京交通大学博士学位论文 的效果。 2 文本分类( t e x tc l a s s i f i c a t i o n ) 文本分类是信息检索和文本挖掘的重要组成部分，其主要目的是通过训练一 定的文本集合得到类别与未知文本的映射规则，即计算出文本与类别的相关度， 再采取一定的阈值策略决定文本所属的类别。j o a c h i m s 利用支持向量机在文本分 类方面已经取得了较好的结果 5 0 5 2 。t o n g 等人通过支持向量机主动学习进行文 本分类 5 3 5 4 。l o d h i 等人提出将文本映射到由不同长度的字符串序列组成的特征 空间，在特征空间计算两个文本的点积，即利用字符串核函数设计高效的核算法 进行文本分类 2 6 】。李晓黎等提出了将支持向量机与无监督聚类相结合的分类算 法，并应用于中文网页的分类，都取得了较好的结果 5 5 。 3 人脸识别( f a c er e c o g n i t i o n ) 人脸识别是一种重要的身份验证技术，在现实生活中具有广泛的应用前景。 核方法已经成为人脸识别的一种强有力工具。o s u n a 等人将支持向量机用于人脸识 别中，提高了识别的准确率 5 6 】。研究人员还利用核主成份分析算法在高维空间中 提取人脸图像的主成分，可以更有效地抽取高维特征空间的非线性特征，提高识 别率；基于核的f i s h e r 判别分析方法也有效地用于人脸识别，取得了较好的效果 5 5 ， 5 7 - 5 8 】。 4 生物信息技术( b i o i n f o r m a t i c s ) 生物信息学是一个涉及多个领域的综合性学科，涉及到分子生物学( 如生物 化学、遗传学和结构生物学等) 、计算机科学( 计算机理论、人工智能、机器学习、 动态程序设计等) 、物理、化学和数学( 算法建模、概率论与统计学等) 。目前，生 物信息学已经成为生物医学、农学、遗传学和细胞生物学等学科发展的强大推动 力量，也是药物设计和环境监测的重要组成部分，不仅具有重大的理论意义，而 且具有巨大的经济效益。 核函数反映地是样本之间相似性的度量。因此在许多研究当中，研究人员经 常是根据具体的应用领域寻找具有物理、化学和生物意义的相似性，构造新的高 效核函数，来提高核方法的分类和回归性能。b r o w n 等人分别将支持向量机应用 于生物信息技术，包括基因微阵列数据分析、蛋白质数据的分析以及基因表达式 的分析等 5 9 】。另外还有很多关于支持向量机在生物信息技术方面的应用，例如 d n a 数据的分析以及异体同形蛋白质的检测 3 7 ，6 0 - - 6 4 。 此外，核方法在其它领域也有许多成功的应用，例如m i i l l e r 等人将支持向量 机应用于时间序列预测 6 5 - - - 6 6 ，5 7 1 。s c h s l k o p f 和c a m p b e l l 等人提出了一种基于 第一章绪论 s v m 的奇异点的检测方法1 1 4 ，6 7 1 ，用于故障检测等。s v m 应用于网络安全的异 常检测，也取得了比较好的效果 6 8 7 2 。 1 4 本论文研究的主要内容 本论文的研究内容主要包括以下几个部分： 1 介绍了核方法的有关概念和理论。讨论了支持向量机几种典型的变形。从 七个方面出发，着重分析和讨论了最典型的核方法支持向量机目前需要研究和解 决的问题。 2 大规模数据集学习时，支持向量机难以满足实际应用的需要。针对此问题， 在研究和分析目前有关算法基础上，提出了基于协同聚类的支持向量机方法，实 现了对支持向量数目的有效简约，取得了较好的效果。并提出了一种新的镜像分 类器算法。对径向基函数神经网络的基函数中心选择进行了改进，提高了其分类 性能。同时，对简约支持向量机和最小二乘支持向量机算法进行了改进。 3 将提出的算法应用于农业虫害预测预报中。在国家大力支持农业信息化的 背景下，提出的算法具有一定的理论和现实意义。 1 5 本论文的体系结构 全文共分七章，第一章主要介绍了研究背景，机器学习的发展过程，核方法 的研究现状及其应用，支持向量机目前需要解决的问题。 其余章节的安排如下： 第二章简单介绍了统计学习理论，对机器学习、核方法的原理和常用核方法 的分类、核函数的理论基础和性质进行了归纳和总结。系统阐述了支持向量机的 基本思想和理论，介绍和比较了几种常用的变形支持向量机算法。总结了结构化 数据核函数构造的几种方法。 第三章针对支持向量机对于大规模数据集学习和决策效率低的问题，提出了 基于协同聚类的支持向量机算法，能够有效地简约支持向量的数量，从而达到提 高分类速度的目的。针对多类分类问题，将协同聚类的方法进一步扩展，提出了 基于协同聚类的多类分类的方法。针对大样本数据回归函数估计时，支持向量过 多所引起的计算复杂度高的问题，提出了基于协同聚类的支持向量回归机。同时， 对r s 和l s s v m 进行了改进。 9 北京交通大学博士学位论文 第四章r b f 神经网络也是一种核方法，在简要介绍了径向基函数神经网络分 类基础上，针对径向基函数中心选取问题，提出了一种有效的基于协同聚类的径 向基函数神经网络的分类方法。 第五章在简要介绍了多镜像分类器算法的基础上，针对镜像点选取较为复杂 的问题，利用协同聚类的类中心对近似地代替镜像点对，提出了一种新的能有效 地提高训练速度的多镜像分类器算法。 第六章简要介绍了农业信息化的基本概念，人工智能技术在农业信息化中的 应用。虫害的预测预报是有效防治虫害发生和减少农业经济损失的依据。提出了 一种基于核方法的虫害预测预报模型，将本文提出的方法应用到农业预测预报中， 实验结果证明是可行的。 第七章是对全文的总结，并对下一步研究工作进行了展望。 1 0 第二章模式分析的核方法 第二章模式分析的核方法 本章从理论研究的角度出发，对核方法的基本原理和相关理论，尤其是最典 型的核方法支持向量机做进一步的阐述。 2 1 核方法原理及常用方法分类 核方法的基本原理与常用的核方法分类是研究核方法的基础，系统地掌握这 些知识对进一步认识和深入地研究核方法具有非常重要的意义。 2 1 1 核方法原理 假设己知某个学习算法是基于准则构造一个分类函数，且在构造过程中只涉 及到样本点之间的点积运算，