（计算机应用技术专业论文）支持向量机和模糊理论在遥感图像分类中的应用.pdf

摘要 遥感图像分类是遥感应用中的最核心技术之一，快速、高精度的遥感图像分类算法是 实现各种实际应用的前提。传统的模式分类方法以经验风险最小化为归纳原则，只有当样 本数趋于无穷时，其性能才能达到理论上的最优。然而在遥感图像分类中，训练样本通常 是有限的。本文借助支持向量机方法在小样本、非线性及高维特征空间中具有良好的分类 性能，针对遥感图像分类的特点，对支持向量机方法及其在遥感图像分类中的应用进行了 深入地研究，主要工作包括： ( 1 ) 对现有的支持向量机训练算法进行了讨论，对支持向量机的二次优化算法进行 了研究，并选择次序最小优化算法作为二次优化算法。 ( 2 ) 对支持向量机的多值分类算法进行了深入研究，深入讨论了一对一s v m 多类 分类器、一对多s v m 多类分类器在遥感图像分类中的应用，并对一对一s v m 多类分类 器产生的混分样本、一对多s v m 多类分类器产生的混分样本和漏分样本使用模糊聚类方 法进行了模糊后处理，组合分类器有效提高了遥感图像的分类精度。 ( 3 ) 讨论了二种模糊支持向量机的原理，并对训练过程中引入模糊引子的模糊支持 向量机训练算法进行了改进，提出边缘效应训练算法的模糊支持向量机训练算法。 ( 4 ) 在决策树多类s v m 算法上进行了一些有益的探索，对如何选择一个较优的决 策树结构在i r i s 数据集和遥感测试数据集上进行了实验，提供了一种行之有效的确定较 优决策树层次结构的类距离方法。 关键词：支持向量机，模糊支持向量机，模糊隶属度，边缘效应，决策树，类距离，遥 感图像分类 a b s t r a c t j 乇e m o t es e n s i n gi m a g ec l a s s j f i c a t i o ni sak e yt e c h n o l o g yi nf e m o t es e n s i n ga p p l i c a t i o n s r a p i da n dh i g h a c c u m c yr e m o t es e n s i n gi m a g ec l a s s i f i c a t i o na l g o r i t l l i l lj st h ep r e c o n d i t i o no f 1 ( i n d so fp r a c t i c a la p p l i c a t i o n s t t a d i t i o n a lp a t t e mc l a s s 墒c a t i o nm e t h o d sa r eb a s e do nt h e p r i n c i p l eo fe x p e r i e n t i a lr i s km j n i m j z a t i o n ，t h e yc a na c h i e v et h eb e s tf e s u l t ，o n l yw h e nt h e n u m b e ro fs a m p l e sa p p m a c h e si n f i n i t y u n f o r t u n a t e i y ，t h en u m b e ro fs a m p l e si s a c t u a l i y l i m i t e d 卸dt h ed a t ad i m e n s i o ni sh i g h t h k i n gi n t oa c j c o u n tt h eg o o dg e n e r a i i z a t i o no fs u p p o n v e c t o rm a c h j n e sj ns m a l ls a m p l e s ，n o n l i n e a r i t ya n dh i g hd i m e n s i o ns p a c e ，a n da c c o r d i n gt o f e a t u r e so fr e m o t es e n s i n gi m a g e ，t h i sd j s s e n a t j o nd e e p l ys t u d i e ss u p p o r tv e c t o rm a c h i n e sa l l d t h e i r 印p l j c a t i o nf o rr e m o t es e n s i n gi m a g ec l a s s i f i c a t j o n t 1 l em a i nc o n t r i b u t i o n so ft h i st h e s i s a r eg i v e na s f o l l o w s ： ( 1 ) w ed i s c u s ss e v e r a l t r a i n i n ga l g o r i t h m so fs v m ，a n d s t u d yt h eq pp m b l e mo fs v m ， a n dt h e ns e l e c tt h es m 0m e t h o da st h eq pa l g o r i t h m ( 2 ) w e d e e p l ys t u d ym u l t i c l a s sa l g o r i t h mo fs v m t h ea p p l i c a t i o no ft w oc l a s s i f i e r s f o rr c m o t es e n s i n gi m a g ec i a s s i f i c a t j o n ，n 锄e l yo n e - a g a i n s t o n es v mm u l t i c l a s sc l a s s i 矗e ra i l d o n e - a g a i n s t t h e r c s ts v mm u l t i c l a s sc l a s s i f i e r ，i si n t m d u c e di nd e t a i l t h e na i m j n ga tt h ec a s e t h a te x i s t i n gt h em i s s e ds a m p l e so rt l i em u l t i v o c a ls a m p l e sv i at w ok i n do fm u l t j c l a s ss v m c l a s s i f i e r ，u s i n gf i l z z ym e t h o dt or e c l a s s i f yt h e s es 锄p l e s e x p e r i m e n tr e s u ns u g g e s tt h em i x e d c l a s s i f ：i e rm a yi m p m v et h ea c c u r a c yo fr e m o t es e n s i n gi m a g ed a s s i f j c a t j o n ( 3 ) w ed j s c u s s 咐ob n do ft h e o r ) ro ff u z z ys u p p o r tv e c t o rm a c h i n e s ( f s v m ) a n d i m p r o v et r a i n i n ga l g o r i t h mo fo n ef s v mw h i c hi m p o r tf i l z z yg e n ei nt m i n i n gp r o c e s s ，a n d t h e np u tf o 九v a r de d g e e f f c c tt r a i n i n ga l g o r i t h mf b rf s v m ( 4 ) s o m eu s e f u ls t u d ya i m i n ga td e c i s i o nt r e es v mm u l t j c l a s sc i a s s i f i e ri s b r i n gt o s u c c e s s a c c o r d i n gt oe x p e r i m e mr e s u l tv i ai r i sd a t a s e ta n dr e m o t es e n s i n gi m a g ed a t a s e t ，w e 百v e 卸e f ! l - e c t i v ec l a s s - d i s t a n c em e t h o dt os e l e c tab e t t e rh i e r a r c h j c a ls t m c t u r eo fd e c i s i o nt r e e k e yw o r d s ：s u p p o nv e c t o rm a c h i n e s ，f u z z ys u p p o nv e c t o rm a c h i n e s ，f u z z ym e m b e r s h i p d e g r e e ，e d g e e 虢c t ，d e c i s i o nt r e e ，c l a s s - d i s t a i i c e ，r e m o t es e n s i n gl m a g cc l a s s i f i c a t i o n 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文巾作了明 确的说明并表示谢意。 签名 日期：z 一6 年3 月z 日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：监磊 江南大学颂二i 二论文 1 1 引言 1绪论 遥感技术是信息革命的产物，是当前人类研究地球资源环境的一种主要技术手段。它 集中了航天、航空、电子学、现代光学及地学等科学的精华，把信息的采集、存储、传输 和应用融为一体，是人类在当今的经济生活中及时了解、掌握地球资源信息的有效手段。 1 9 7 2 年以来，美、法、澳大利亚以及最近我国与巴西等国连续发射了陆地、海洋等地球 资源卫星，形成一个对地球资源、环境进行观察和动态监测的多维探测网，人们得以从大 气、陆地、海洋等不同角度研究地球，从中获得大量前所未有的信息。 至上世纪八十年代，t m 、s p o t 等较高分辨率卫星图像的获取，使应用研究逐步向 城市扩展和城市内部结构变化监测方面拓展，美国和加拿大对其中心城市的变化监测周期 规定为2 5 年，而以土地利用分类为主题的数字图像处理方法研究，则自七十年代中期开 始。遥感在世界范围得到迅速发展与广泛应用，其社会经济效益为世人瞩目。例如，美国 每年利用其陆地资源卫星可获益1 4 亿美元，使用气象卫星资料避免各种灾害损失约2 0 亿美元。 遥感图像分类是遥感应用系统中的最关键技术之一，快速、高精度的遥感图像分类算 法是实现各种实际应用的前提。正因为遥感图像分类有着非常重要的作用，所以遥感图像 的分类一直被从事于遥感信息处理的广大科技人员所重视。许多研究者都在不断试用、改 进乃至探索新的方法，不断提高遥感图像自动分类算法的精度和速度。 支持向量机【1 】( s v m ) 是v a p n j k 等人根据统计学习理论提出的一种学习方法，近年 来在模式识别、回归分析、图像处理和数据挖掘等方面得到了广泛应用。支持向量机方法 根据v a p n i k 的结构风险最小化原则，尽量提高学习机的泛化能力，即由有限训练样本得 到的决策规则对独立的测试集仍能够得到小的误差。此外，支持向量机算法是一个凸二次 优化问题，能够保证找到的极值解就是全局最优解。这些特点使支持向量机成为一种优秀 的学习算法。 应用于遥感图像分类的方法按利用图像要素的不同大体可分为三类：第一类是基于图 像的灰度分类，第二类是基于图像纹理的分类，第三类是基于多源数据融合的分类。本文 首先使用标准s v m 多类分类算法对遥感图像进行分类，并分析其中的缺点而结合模糊理 论加以改进，最后更进一步改进s v m 训练算法来改进分类精度。目前国内也有些关于使 用s v m 方法在遥感图像分类中的研究1 2 _ 6 】，重点主要集中在遥感图像的特征提取上和比较 支持向量机的小样本训练特性，没有对s v m 多类分类器及训练算法改进上进行讨论，因 此研究s v m 多类分类器及其改进算法在遥感分类中的应用，是有实际意义的。 l 绪论 1 2 遥感图像分类研究现状 遥感图像的分类，一般由四个步骤组成：第一步为分类特征波段的选择，第二步为训练 样本的选择，第三步为训练分类器和分类，第四步为对分类精度进行评价。目前对于遥感图 像的自动分类方法讨论较多，应用于遥感图像分类的方法按利用图像要素的不同大体可分 为三类： 第一类是基于图像的灰度信息分类，如最小距离分类法、k m e a n s 方法、最大似然分 类法、神经网络法、主成分分析法等。最小距离分类法的思想是将分类点归入到与分类中 心距离最小的一类，通常该方法分类精度不高1 7 j ok - m e a n s 方法属于动态聚类法，它以误差 平方和最小作为聚类的评判准则i ”。最大似然法必须预先获取各类别的先验性分布知识及 其概率。神经网络分类法是最近发展起来的一种具有人工智能的分类方法，在类别分布的 先验性知识及其概率未知的情况下，它比最大似然法的分类效果要好。b p 神经网络、 k o h o n e n 神经网络、径向基神经网络、模糊神经网络、小波神经网络等各种神经网络在 遥感图像自动分类上都有一定的应用，并取得较好的效果1 9 _ 1 引。但神经网络也有一些缺点， 如局部极值问题，训练收敛速度太慢，对各类分类性能差别较大等。 第二类是基于图像纹理的分类，如共生矩阵法、分形法、m a r k o v 随机场等【1 5 】。这类 方法不仅利用了反映地物差异的光谱信息，而且还利用了刻画地物特征的纹理信息，进一 步提高了分类的精度。 第三类是基于多源数据融合的分类，多源信息融合就是把多种信息( 遥感数据和非遥感 数据) 按照一定的方式有机地组合成统一的信息模型。这类方法有基于知识的推理、信息 融合、空间数据挖掘等。基于知识的推理方法可以利用现有的g i s 数据和先验知识，可以部 分解决分类时遇到的同物异谱和同谱异物的情况【”】。信息融合是利用多个遥感信息源所提 供的反映所处环境或对象的不同特征信息之问的互补性和冗余性，采用有效的方法将它们 融合，弥补单一信息源的缺陷1 1 ”。空间数据挖掘是从空间数据库中提取用户感兴趣的空间模 式与特征、空间与非空间数据的普遍关系及其它一些隐含在数据库中的普遍数据特征的过 程i l 。这类方法可以利用已经获得的相关知识来改进分类结果，但是需解决多种信息不一致 时的问题。为了提高遥感图像分类精度，还必须寻找一些新的学习算法。 1 3 支持向量机理论研究现状 支持向量机( s v m ) 最初用来解决模式识别问题，目的是发现泛化性能好的决策规则， 支持向量( s u p p o nv e c t o r s ) 实际上是训练集的子集，对支持向量的最优分类等价于对训 练集的分类。最近几年中，s v m 在模式识别，回归分析，概率密度函数估计等领域中得 到了广泛的应用1 1 9 。”】。目前对s v m 的研究主要包括以下几个方面： ( 1 ) s v m 算法的改进研究。对算法的改进是目前s v m 研究的主要内容，覆盖面 很广，其中包括：( a ) 训练算法的改进【珏2 7 1 ，降低计算量；( b ) 自适应算法的研究1 2 8 ，2 9 1 ，研 江南大学硕二l 论文 究如何根据要处理的问题，自动选择合适的核函数；( c ) 噪音数据处理1 3 “”j ，由于s v m 仅 依靠数量很少的支持向量，因此对噪音数据较为敏感，需要加强数据的预处理；( d ) 其他 改进，如增量学习m “j ，先验知识融合等等。 ( 2 ) s v m 多值分类研究1 4 “”。s v m 方法的基本理论只考虑了二值分类，如何进行 多值分类，主要有以下方案：( a ) 一一区分模式，对个分类的训练集进行两两区分，构 造( j v 一1 ) 2 个分类器；( b ) 逐一鉴别模式，仅构造个s v m 分类器，每一个s v m 分 类器分别将某一类数据从其他分类数据集中鉴别出来；( c ) 决策树模式，仅构造( 一1 ) 个 分类器，第一次分出二个大的类别，在大的类别里再继续分类直到最后一一分类。( d ) 对 s v m 分类机理进行改进，将多个分类面的参数求解合并到一个最优化问题中，通过求解 该最优化问题一次性实现多类分类。 ( 3 ) s v m 核函数的研究1 4 8 - ”j 。s v m 的性能很大程度上与选择的核函数有关，一旦 确定了核函数，支持向量机的性能就确定了。目前提出的核函数一共有十几种，最常用核 函数只有那么三四个，所以对核函数的改进一直是支持向量机理论研究的热点和难点。 ( 4 ) s v m 的应用研究i ”。虽然s v m 方法在理论上具有很突出的优势，但与其 理论研究相比，应用研究尚相对比较落后。最近几年，应用研究刊逐渐地多起来。在模式 识别和回归分析领域，包括手写体数字识别、人脸检测、语音识别、目标识别，文本分类、 系统辨识、非线性函数逼近等方面，取得了一定的成果。 1 4 模糊理论简介 模糊理论1 5 9 ”l 是1 9 6 5 年由加利福尼亚大学控制论专家z a d e h 教授所开创的，z a d e h 教授首先提出了用隶属度函数来描述模糊概念，创立了模糊集合论，为模糊数学奠定了基 础。8 0 年代以来模糊技术在模式识别、过程控制、故障诊断、交通管理、图像处理、声 音识别等领域得到了普遍的应用，国内外掀起了一股研究模糊的热潮，模糊理论已经显示 出强大的生命力和渗透力，发展前景广阔。在模式识别领域中，基于模糊集理论和模糊逻 辑的模糊理论方法比基于传统集合理论和逻辑方法更加接近人的思维和推理，模糊理论提 供了一个较恰当的框架表示人们的不精确概念和推理方式，当把模糊理论引用到模式识别 领域内时，判断的标准“真”或“假”成了相对的概念，这就帮助我们在模糊的信息环境 中做出精确的判断。 1 5 本文的主要工作 本文的主要工作如下： ( 1 ) 对现有的支持向量机训练算法进行了讨论，对支持向量机的二次优化算法进行 了研究，并选择次序最小优化算法作为二次优化算法。 1 绪论 ( 2 ) 对支持向量机的多值分类算法进行了深入研究，深入讨论了一对一s v m 多类 分类器、一对多s v m 多类分类器在遥感图像分类中的应用，并对一对一s v m 多类分类 器产生的混分样本、一对多s v m 多类分类器产生的混分样本和漏分样本使用模糊聚类方 法进行了模糊后处理，组合分类器有效提高了遥感图像的分类精度。 ( 3 ) 讨论了二种模糊支持向量机的原理，并对训练过程中引入模糊引子的模糊支持 向量机训练算法进行了改进，提出边缘效应训练算法的模糊支持向量机训练算法。 ( 4 ) 在决策树多类s v m 算法上进行了一些有益的探索，对如何选择一个较优的决 策树结构在l r i s 数据集和遥感测试数据集上进行了实验，提供了一种行之有效的确定较 优决策树层次结构的类距离方法。 1 6 本文的章节安排 本文共分6 章，章节安排如下： 第1 章为绪论部分，先介绍论文的背景和研究意义，目前该课题的研究现状，指出本 文的主要研究内容； 第2 章首先实现s v m 标准算法，然后使用构造的多类分类器( 最常见的一对多s v m 多类分类器和一对一s v m 多类分类器) 对遥感图像进行分类，使用快速s m o 算法解决 训练速度慢的问题，然后对分类结果进行分析： 第3 章先介绍模糊方法在遥感测试数据集上的性能，再结合模糊方法解决第2 章构造 的s v m 多类分类器没能解决的混分样本或漏分样本问题，对这些样本进行模糊后处理； 第4 章通过上两步得到的快速训练和模糊后处理的遥感图像分类算法，进一步引入模 糊因子的的模糊支持向量机来改变s v m 分类器的分类边缘，并就改进了模糊因子的模糊 支持向量机进行了实验，实验过程还加入了模糊后处理过程，实验数据结果证明了该方法 在遥感图像分类处理中的有效性： 第5 章讨论了支持向量机多类分类器中的决策树方法，并就决策树算法的局限性进行 了分析，通过聚类中心距离的方法来确定一个分类层次较优的结构，并用i r l s 数据集实 验结果来证明，最后用遥感图像数据测试也证明了该方法的有效； 第6 章为全文的总结，以及对未来工作的展望和建议。 4 江南大学坝i ：论文 2 支持向量机及其改进算法在遥感图像分类中的应用 本章先简单介绍统计学习理论，进一步介绍由统计学习理论发展起来的支持向量机算 法，分析s v m 的训练过程和训练过程中的参数选择问题，对s v m 二类别分类特性进行推 广，构造基本的两种s v m 多类分类器。由于s v m 训l 练过程使用标准q p 算法速度比较慢， 所以实现快速s m o 训练算法，最后对遥感图像进行实验，并对两种不同多类分类器实验 结果进行了对比分析。 2 1 统计学习理论 基于数据的机器学习足现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻 找规律，利用这些规律对未来数据或无法观测的数据进行预测。迄今为止，关于机器学习 还没有一种被共同接受的理论框架，关于其实现方法大致可以分为三种1 2 4 l ： 第一种是经典的( 参数) 统计估计方法。包括模式识别、神经网络等方法在内，现有 机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这 种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局 限性，首先，它需要已知样本分布形式，这需要花费很大代价，还有，传统统计学研究的 是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中， 样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。 第二种方法是经验非线性方法，如人工神经网络( a n n ) 。这种方法利用已知样本 建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学 理论基础。 第三种方法是统计学习理论的方法。与传统统计学相比，统计学习理论( s t a t i s t j c a l k a m i n g1 1 1 e o r v 或s i ) 是一种专门研究小样本情况下机器学习规律的理论，它的核心问 题是寻找种归纳原则以实现最小化风险泛函，从而实现最佳的推广能力。该理论针对小 样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近 性能的要求，而且追求在现有有限信息的条件下得到最优结果。v 。v a p n i k 等人从六、七 十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由 于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重 视。 基于结构风险最小化方法的统计学习理论是一种专门的小样本统计理论，它为研究有 限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架。 由于优异的泛化性能和完备的理论体系，基于统计学习理论的s v m 方法已经成为国际上 机器学习领域新的研究热点。 2 支持向量机理论及其改进算法在遥感图像分类中的应用 2 1 1v c 维 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关 系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数( 包括使经 验风险最小的函数) ，经验风险与期望风险之间至少以1 一r l 概率满足下列关系【1 9 l ： r ( a ) sr w ( 。) + 中( ；，生掣) ( 2 1 ) 其中置信区间巾的定义如下： 中( 争生产) - j 地幽半坐幽 ( 2 _ 2 ) 参数 被称为v c 维( v a p n i k c h e o n e i l l 【i s d i m e n s i o n ) ，f 是训练集的规模，且f 。模式 识别方法中v c 维的直观定义是：对一个函数集，如果存在 个样本能够被函数集中的函 数按所有可能的2 6 种形式分开，则称函数集能够把 个样本打散：函数集的v c 维就是它 能打散的最大样本数目 。v c 维是机器学习复杂度的度量，表明机器学习的最大学习能 力。 v a p n i k 给出了一个关于一间隔分类超平面v c 维上界的定理：如果向量x 属于一 个半径为r 的球中，那么一间隔分类超平面集合的v c 维 有下面的界： 一s m i n ( 等 ，n ) + ， c z s ， 这样，s v m 首先保证了一个小的经验风险( 在训练样本可分时就是零) ，并通过选 择边缘最大的超平面的方式控制了函数集的v c 维，这正是s r m 原则所要求的。我们还 注意到：最优超平面可以在维数很高的空间中构造v c 维较小的函数集。以往很多方法也 意识到需要控制学习机器的复杂性，但多数只限于控制机器中自由参数的个数。v c 维的 概念出现后，我们认识到，是v c 维而不是自由参数的个数真正决定了学习机器的复杂性。 因此，尽管采集了对象的很多特征( 特征空间维数) ，仍有可能在这些特征的综合中找到 简单的依据作出划分。 v a p n 像还作出了如下推论来刻画一间隔分类超平面的推广能力：以概率1 q 我们 可以断定，测试样本不能被一间隔分类超平面正确分类的概率有下面的晃： ；甜+ 腰卜刚壁掣 4 ， 州是没有被正确分类的训练样本数目， 是前面定理所给出的v c 维的界。v a p n i k 还有与此类似的刻画最大间隔超平面推广能力的定理，这里不再赘述。 v c 理论被认为是从有限数据中预测相关性的统一数学框架。尽管v c 理论作为数学 理论已出现了2 0 多年，但人们还没有充分体会到它的理论和实际价值，近期的研究已经 6 江南大学顾：i 。论文 表明v c 理论可以改善各种各样的神经网络学习算法。更为重要的是基于v c 理论的创造 性机器学习方法s v m 的出现。s v m 是由v a p n i k 领导的a t & t b e l l 实验室研究小组提出 的一种新的非常有潜力的分类技术，它开辟了学习高维数据新的天地，这种新的学习算 法可以替代多层感知机、r b f 神经网络和多项式神经网络等已有的学习算法，它也是一 种可实现一些表示问题的建设性方法，在多层感知机、r b f 神经网络和小波神经网络中 有成功运用，同时s v m 方法在实际中的一些应用( 如人脸检测、k d d 和信号处理) 也说 明了v c 维理论的理论和实用价值。 以往机器学习理论的核心是经验风险最小化原则( e r m ) 。如果以大量的样本进行训 练，并且能找到一个相当逼近这些样本的函数，那么它可望对工作样本作出较准确的预 测。这反映了大样本统计学对渐进特性的依赖。6 0 年代的很多学者认为使学习机器具有 好的推广能力的唯一因素就是使它在训练集上的误差最小，因此e r m 原则似乎是不证自 明的。但是事实上，如果学习机器能力( c a p a c i t y ) 过强，能够无误差地适应任意的训i 练 样本，就会导致科学哲学中不可证伪的情况。这是因为它所采用的函数集过于复杂，对 任何训练样本都保持高精度的辨识能力本身就蕴含着对工作样本所作预测的不可靠性。 v a p n i k 提出了v c 维的概念来标志函数集的复杂程度( 迄今为之还没有人提出更好的概 念来标志这种复杂性) ，并用这个概念给出了与分布无关的学习机器推广能力的界。在此 基础上发展出了一系列关于统计学习理论的一致性( c o n s i s t e n c v ) ，收敛速度推广性能 ( g e n e r a l i z a t i o np e 南r m a n c e ) 等的重要结论也就是说，按e r m 原则构造的学习机器在 给定的样本数量下实际风险将会在这个界的范围内。这个界由两部分构成：经验风险和 置信范围( 以v c 维为参数) 。学习机器能力过强( v c 维很大) ，虽然能取得小的经验风 险，但置信范围会很大；v c 维太小又会导致大的经验风险。一个好的归纳原则必须在二 者之间作出权衡。 2 1 2 结构风险最小化理论 由v c 维度的讨论可以看到，经验风险和期望风险依赖于学习机函数族的选择。机器 学习的期望风险是由两部分组成：经验风险和置信区间。置信区间和机器学习的v c 维及 训【练样本数有关，可简单表示为毋( 1 ) 当经验风险变小时，爱信区间在增大中，实际 风险并没有减小。因此要同时最小化经验风险和置信区问。结构风险最小化原则( s r m ) 正是这样一种归纳原则。 给定个具体的训练样本数f ，风险控制由两个因素决定：尺。 ) 和 ( 丘：口a ) ) ，a 表示a 的子集。经验风险由机器学习选择的函数决定，例如选择合适 的a 来控制它。v c 维 由机器学习能够执行的函数集 厶：a a7 来决定。为了控制 ， 这里引入了子集嵌套的结构s 。：= 丘：a a 。 ，其中( ，：a a b ， s c s 2c c s nc 2 支持向量机理论及其改进算法在遥感图像分类中的应用 相应的v c 维满足| l ，s ，s s 。s 这样函数集的v c 维就成为了可控参数。在 子集 丘：a a 。 中选择这样一个函数，它使经验风险和置信区间最小。这种思想被称作 结构风险最小化原理( s t m c t u r a lr i s km i n i m i z a t i o n ，简称s r m ) 。其在s v m 算法的具体体 现为：设计函数集的某种结构使每个子集都能取得最小的经验风险( 如使训练误差为o ) ， 然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最 优函数。对一个给定的训练集，s r m 原则在使风险上界最小的子集中选择使经验风险 最小的函数。结构风险最小化原理如图2 1 所示。 风譬 檗三圈 蠢魏曩予囊i s i c 葛c 5 。 v c 量函】k i 图2 1 结构风险最小化原理图 虽然s r m 原则并不能充分解释s v m 是怎样最小化风险泛函从而获得好的推广能力 的，但从以上定理及推论我们可以看到最大化边缘和s r m 原则的确是有着某种内在的一 致性。s r m 原则定义了在对给定数据的逼近精度和逼近函数的复杂性之间的一种折衷。 s r m 的一般原则可以用不同的方法实现。在实际的算法中，神经网络是通过选择一个适 当构造的机器来保持固定的置信范围并最小化经验风险；支持向量机是保持经验风险固 定并最小化置信范围。实现s r m 原则可以有两种思路，一是在每个子集中求最小经验风 险，然后选择使最小经验风险和置信范围之和最小的子集显然这种方法比较费时，当子 集数目很大甚至是无穷时不可行因此有第二种思路，即设计函数集的某种结构使每个子 集中都能取得最小的经验风险( 如使训练误差为o ) ，然后只需选择选择适当的子集使置 信范围最小，则这个子集中使经验风险最小的函数就是最优函数支持向量机方法实际上 就是这种思想的具体实现和如何根据s r m 准则对某些传统方法进行改进的问题。 2 1 3 最优超平面 设给定的训练集为 ( z 。，y ，) ，( x ：，y ：) ， ， ( x ，_ ) ，) ) ，其中x 。r “，y 一1 ， 江南大学硕：i ：论文 1 ) 。再假设该训练集可被一个超平面线性划分，该超平面记为z ) + 6 = 0 。 如果训练集中的所有向量均能被某超平面正确划分，并且距超平面最近的异类向量之 间的距离最大( 即边缘最大化) ，则该超平面为最优超平而，如图2 2 所示。 n 。g a t i ”。e x a m p l e s ( w x ) + 6 ：0 l + s p a c eo fp o s s i b l ei n p u t sx 图2 2 线性二类划分的最优超平面 其中距离超平面最近的异类向量被称为支持向量( s u p p o r tv e c t o r ) ，一组支持向量可 以唯一地确定一个超平面，两类支持向量问的距离叫分类间隔。 对于线性可分的问题，不失一般性，可假定训练集中的向量满足： y f ( w 工f + 6 ) 1f = 1 ，z ( 2 5 ) 由于支持向量与超平面之间的距离为1 w 0 ，支持向量之间的距离为2 ij w ，即为分 类间隔，因此构造最优超平面使分类间隔最大的问题就转化为在上式的约束下求下式的最 小值： 中( w ) = 1 2 ( 2 6 ) 使分类间隔最大实际上就是对推广能力的控制，这是s v m 的核心思想之。统计学 习理论指出，在维空间中，设样本分布在一个半径为r 的超球范围内，则满足条 件i | wi l = 4 的正则超平面构成的指示函数集， ，w ，6 ) = 醣n ( w x ) + 埘( 跏( ) 为符号函 数) 的v c 维 满足下面的界： m i n ( 陴2 爿2 】，) + 1 ( 2 7 ) 因此使叫j2 最小就是使v c 维的上界最小，从而实现s r m 准则中对函数复杂性的选 择。由式2 7 可知，可以通过最小化1 1w 1 i 使v c 置信度最小。如果固定经验风险，最小化 期望风险的问题就转化为最小化0 w 0 的问题。这就是s v m 方法的出发点。 2 支持向量机理论及其改进算法在遥感图像分类中的应用 v a p n i k 【1 1 证明，如果训练集中的向量能被最优超平面完全划分，则在测试未知样本时 的最大出错概率，即支持向量机期望风险的上界为： 即巾叫】s 糕黼 2 2 支持向量机理论 ( 2 8 ) 支持向量机( s v m ) 理论研究起始于上世纪六十年代的俄国科学家v a p n i k 和他的支 持者的研究，在持续的三十年间统计学习理论( v c 维理论) 得到了很大的发展，上世纪 九十年代终于从统计学习理论的基础上成功构造了s v m 算法。s v m 算法是一种学习机 制，是由v a d n i k 提出的旨在改善传统神经网络学习方法的理论弱点( 如结构的确定靠试 验试凑，没有理论依据) ，最先从最优分类面问题提出了支持向量机网络。新的学习算 法可以替代多层感知机，r b f 神经网络和多项式神经网络等已有的学习算法，它根据有 限的样本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获得最好的泛化能力。 s v m 在形式上类似于多层前向网络，而且也可以被用于模式识别、回归分析、数据挖掘 等方面。但是，支持向量机方法能够克服多层前向网络的固有缺陷，它有以下几个优点： ( 1 ) 它是专门针对有限样本情况的，根据结构风险最小化原则，尽量提高学习机的 泛化能力，即由有限的训练样本得到的小的误差能够保证对独立的测试集仍保持小的误 差， 其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值。 ( 2 ) 算法最终将转化成为一个二次型寻优问题( q u a d r a t i cp r o g m m m i n g ，q p ) ，从理论 上说，得到的将是全局最优点。 ( 3 ) 算法将实际问题通过非线性交换转换到高维的特征空间，在高维空间中构造线 性判别函数来实现原空问中的非线性判别函数，这一特殊的性质能保证机器有较好的泛 化能力，同时它巧妙地解决了维数灾难问题，使得其算法复杂度与样本维数无关。 支持向量机这些特点是其它学习算法( 如人工神经网络) 所不及的。对于分类问题， 单层前向网络可解决线性分类问题，多层前向网络可解决非线性分类问题。但这些网络 仅仅能够解决问题，并不能保证得到的分类器是最优的；而基于统计学习理论的支持向 量机方法能够从理论上实现对不同类别问的最优分类，通过寻找最“坏”的向量，即支 持向量，达到最好的泛化性能。 2 2 1 线性s v m ( 1 ) 线性可分s v m 数学模型的建立 设给定的训练集为 g l ，_ ) ，1 ) ，y 2 ) ，_ ) ，) ) ，其中置r n ，) ， 一1 ，1 ) 。我们将s v m 的最优化问题中的分类超平面做以下归一化：离超平面最近的样本点( 支持向量) 满足 ( w z 。) 一6 = 1 ，若y 2 1 ( 2 9 ) 1 0 江南大学硕二l 二论文 ( w x ，) 一6 = 一1 若y = 一l ( 2 1 0 ) 则最优分类超平面为：( w - ) 一6 = o ，支持向量到超平面的距离为i ( w 一。) 一6l 川w 0 l 川w i l 。于是，这个最优化问题最初的数学提法将是 m i n t m t z e 中( w ，6 ) = 昙1 1 w | | 2 y 。( x 。w 一6 ) 一1 芑0 ( 2 1 1 ) f = 1 ，2 ，f 目标函数是严格上凹的二次型，约束函数是下凹的，这是一个严格凸规划。按照最 优化理论中凸二次规划的解法，我们把它转化为w o l f e 对偶问题来求解：构造h 掣a n g e 函数： 洳，咖) = 剐2 一扣y 旭叭扣，卟o ，f = 1 ，2 ， 沼m ( 其中q 是l a g r a n g e 乘子。) 它应满足条件v 。( w ，口，6 ) = o ，导( w ，口，6 ) = o ， d d ( k u h n 。t u c k e r 条件) ，即w 2 q y 。一和q y j 2o 。将两式代回l a g r a n g e 函数中，消 去w 和6 ，经运算得到原最优化问题的w 0 1 f e 对偶问题： m a x m t z e 脚) = q 一号峨_ ) ，t _ l - l 厶f ，j 盯 哪却 ( 2 _ 1 3 ) q 芑0i = 1 ， 其解是原最优化问题的整体最优解。解出口后利用w = 。y ，z 。确定最优超平面， 注意到只有支持向量所对应的l a 掣a n g e 乘子a 。刁+ 不是o 。 基于最优超平面的分类规则就是下面的判别函数： m ，= 跏 支泓a 她叫一1 沼 其中6 作为偏移值，取值如下：6 = ： 妻n 拂蕾x ( 1 ) + 妻q y 。t z ( 一1 ) 】，公式中，z ( 1 ) 表示属于第一类的某个( 任一个) 支持向量，j ( 一1 ) 表示属于第二类的某个支持向量。 利用w o l f c 对偶问题，不但使问题更好处理，而且使样本在新问题中仅以向量点积 的形式出现，正是这一重要特点，使支持向量机法能推广到非线性情况。由于w o l f e 对 2 支持向量机理论及其改进算法在遥感图像分类中的应用 偶问题带来了这样好的一个副产品，现在对s v m 所作研究一般都从w o l f e 对偶问题开始， 而不将其最初的数学提法作为优化目标。 ( 2 ) 线性不可分情况的处理 为了使s v m 算法能应用于不可分情况，c o n e s 和v a p n i k i 矧在1 9 9 5 年引入了软边缘 最优超平面的概念，引入非负变量量，将约束条件放松为 y 。 ，w + 6 ) 一1 1 一鼻， f = 1 ，2 ，f 同时对目标函数引入惩罚项： 蚋固= 抑卜c 隆) ( 2 1 5 ) ( 2 1 6 ) 求解这个二次规划问题，最终推导所得的w 0 1 f c 对偶问题与线性可分的情况( 式2 1 3 ) 类似如下式2 - 1 7 所示，唯一的区别在于对加了一个上限限制。 m o m i z e s j 2 2 2 非线性s v m 脚，= 扣一三骞嘴城 善q 咒= 0 ( 2 - 忉 c 芑芑0i = 1 ， 上节的算法针对的是输入空间存在线性判别面的情况，对分类面是非线性函数的情 况，理论上应将输入空间通过某种非线性映射，映射到一个高维特征空间，在这个空间中 存在线性的分类规则，可以构造线性的最优分类超平面。但是这种方法带来了两个问题： 一是概念上的问题：怎样在如此高维的空间中找到一个推广性好的分类超平面? 二是技 术上的问题：如何处理高维空间中的计算问题? 前面我们把寻找最优超平面最终归结为其w o l f c 对偶问题，一个很重要的副产品就 是找到了一个克服“维数灾难”，解决技术上问题的绝好方法：如果数学上可以找到一个 函数k ：( 尺“，r ”) 一尺使得k 0 i ，石i ) 就等于五，x f 在高维特征空间中的映射之点 积，那面我们用k i ，zf ) 代替w b l f e 对偶问题中咒和x f 的点积即可，计算量将会大 大减少。事实上确实存在这样的函数，v a p n i k 称之为卷积核函数( c o n v o l u t i o no fl l l l l e r p r o d u c t ，o rk e m e lf u n c t i o n ) 。于是我们只需在输入空间中计算卷积核函数，而不必知道非 线性映射的形式，也不必在高维特征空间中进行计算。 通过上节我们已经看到，线性的s v m 是以的样本间的欧氏距离大小为依据来决定划 江南大学顺士论文 分的结构的。非线性的s v m 中以卷积核函数代替内积后，相当于定义了一种广义的距离， 以这种广义距离作为划分依据。也许并不一定所有的学习机器都要以样