（机械电子工程专业论文）基于支持向量机的目标识别技术研究.pdf

基于支持向量机的目标识别技术研究刘云龙( 机械电子工程)指导教师：刘衍聪教授摘要目标识别是当前计算机视觉与模式识别领域中的一个热点问题，其应用范围广泛，具有重大研究意义。基于统计学习理论的支持向量机( s v m ) ，遵循结构风险最小化原则，有效解决了传统模式识别方法容易出现的过学习和欠学习问题，成为当前模式识别领域的首选分类器。本文对目标识别技术和支持向量机的相关理论进行了综述研究；通过实验证明了将具有平移、旋转、尺度不变性的h u 不变矩应用于目标识别中的有效性；研究设计了基于s v m l i g h t 算法和径向基核函数的支持向量机分类器，对提取的h u 矩不变量进行训练和识别，通过对比实验证明了支持向量机在解决小样本问题上的优势；以人脸为对象设计了一个目标识别系统，分别实现了视频目标捕捉、目标检测、特征提取和目标识别几个功能；通过这个系统进行识别实验，验证了基于支持向量机结合h u 不变矩特征的目标识别技术在目标识别准确率上好于传统b p 神经网络。关键词：目标识别，支持向量机，人脸检测，人脸识别，不变矩s t u d yo nt a r g e tr e c o g n i t i o nt e c h n i q u eb a s e do ns u p p o r tv e c t o rm - a c n el i uy u n - l o n g ( m a c h i n e r ya n de l e c t r o n i ce n g i n e e r i n g )d i r e c t e db yp r o f e s s o rl i uy a n - e o n ga b s t r a c tt a r g e tr e c o g n i t i o ni saf o c u si s s u ei nt h ep a t t e r nr e c o g n i t i o na n di m a g ep r o c e s s i n gf i e l d f o ri t sw i d e l yp r a c t i c a la p p l i c a t i o ni nt h es o c i e t y , t h er e s e a r c hh a s 缸i m p o r t a n ts i g n i f i c a n c e s u p p o r tv e c t o rm a c h i n e ( s v m ) b a s e d - o nt h es t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l ei nt h es t a t i s t i c a ll e m m i n gt h e o r y , s o l v et h eo v e rf i t t i n gp r o b l e me f f e c t i v e l yw h i l eo t h e rt r a d i t i o n a lp a t t e r nr e c o g n i t i o nm e t h o d sc o u l dn o t s os v mb e c o m et h em o s tp o p u l a rc l a s s i f i e ri nr e c o g n i t i o nf i e l d t h i sd i s s e r t a t i o ns u m m a r i z e st h et h e o r ya s s o c i a t e dw i t ht h et e c h n o l o g yo ft a r g e tr e c o g n i t i o na n ds v mi nt h eb e g i n n i n g i tp r o v e st h ev a l i d i t yo fu s i n gh um o m e n t si n v a t i a n c ew i l hd i s p l a c e m e n t , s c a l e ，r o t a t i o n , i l l u m i n a t i o ni n v a r i a b i l i t ya se i g e n v e c t o ro fr e c o g n i t i o n c o n s t r u c tas v l v lc l a s s i f i e rb a s e d0 1 1s v m l i g h ta l g o r i t h ma n dr b fk e r n e l t h e nt r a i nt h ec l a s s i f i e r 丽t hh um o m e n ti n v a r i a n c ef o rr e c o g n i z i n g t h r o u g ht h ec o n t r a s t i v ee x p e r i m a n t , i tp r o v e st h a ts v mc l a s s i f i e rh a sao b v i o u sp r e d o m i n a n c et ot h et r a d i t i o n a lo n e se s p e c i a l l yi ns m a l ls a m p l e sa n dh i g hd i m e n s i o np r o b l e m s i nt h ee n d , at a r g e tr e c o g n i t i o ns y s t e mw l d c hi su s e di nh u m a nf a c er e c o g n i t i o ni se s t a b l i s h e d , t h es y s t e mr e a l i z et a r g e tc a p t u r e ，t a r g e td e t e c t i o n , f e a t u r ee x t r a c t i o na n dt a r g e tr e c o g n i t i o nr e s p e c t i v e l y t h r o u g hp l e n t yo fe x p e r i m e n t so ns t a n d a r dh u m a nf a c ed a t a b a s e , t h er e s u l t ss h o wt h a tt h et e c h n o l o g yo fr e c o g n i t i o nb a s e do ns v ma n dh um o m e n ti n v a r i a n c ei sb e t c 盯t h a nb pn e u r a ln e t w o r k s k e yw o r d s ：t a r g e tr e c o g n i t i o n , s u p p o r tv e c t o rm a c h i n e ，f a c ed e t e c t i o n , f a c er e c o g n i t i o n , m o m e n ti n v a r i a n c e独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它人已经发表或撰写过的研究成果，也不包含为获得中国石油大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：壶l 立五2 0 0 t 年罗月2 4 - 日关于论文使用授权的说明本人完全了解中国石油大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存论文。( 保密论文在解密后应遵守此规定)学生签名：剖未笠2 0 。了年5 月j 4 日导师签名：二量恤乡叩年多月却日中国石油大学( 华东) 硕士论文第1 章绪论第1 章绪论目标识别是近年来图像处理、模式识别、人工智能等领域里最受关注的课题之一。随着社会的发展、科技的进步，其应用范围不断扩大，具有重要的理论研究价值。1 1 国内外研究现状目标识别在一定意义上可以理解为是图像识别，它的主要任务是要确定所摄图像中是否存在感兴趣的目标，并给目标以合理的解释，有时还要确定目标的状态。以识别算法的策略来分，目前常用有两种【1 1 ，一种是由下而上的数据驱动型，另一种是由上而下的知识( 假设) 驱动型。前者不管识别目标属于何种类型，一律先对原始图像进行一般性地分割、标记和特征提取等低层处理，然后将每个带标记的己分割区域( 物体) 的特征向量集与目标模型相匹配；其优点是适用面广，对单目标识别及复杂景物分析系统均适用，具有较强的代换性；缺点是在分割、标记、特征提取等低层处理过程中缺乏知识指导，盲目性大，故工作量大，匹配算法比较复杂。后者利用知识来组合所有针对具体目标类的处理方法：每个目标类的目标模型通过对于这个类中的成员都一致的各种特征及其变化范围来定义，只要这些特征有相应的处理方法来检测或者度量。每个类别都有相关的“控制知识”选择处理时使用哪个特征、以及这些特征使用的顺序，并且组合各个部分匹配处理的结果。这种方法的优点是底层处理是在知识指导下的粗匹配过程，可避免抽取过多不必要的特征集，提高算l中国石油大学( 华东) 硕士论文第1 章绪论法的效率，其精匹配过程也因而变得简单和有针对性。它的缺点是代换性和兼容性差，识别目标改变，知识和假设要随之而变。1 2 课题研究的背景及意义在日常生活中，随着计算机硬件技术的飞速发展，传感器性能的不断提高，以及各类系统软件和应用软件的大量开发和推广，计算机已经从先前单纯的数值计算，应用到文字处理、图形图像处理、语音处理、人工智能及模式识别等各个领域。但计算机对声音、图像等外界信息的直接感知上的局限性，己越来越成为计算机进一步应用发展的障碍，也与其高超的运算能力形成鲜明的对比。因此着眼于拓宽计算机的应用领域，提高计算机感知外部信息能力的新学科一模式识别便应运产生。经过几代研究人员三十多年的不断努力，这一学科正不断发展成熟，在军事、医学、地质、气象等很多领域都取得了可喜的实用成果。本课题来源于山东省东营市科学技术发展计划项目“视频目标特征提取与识别技术研究”，将针对复杂条件下目标特征提取与识别存在的问题，研究在视角变化情况下，如何提取具有平移、尺度、旋转等不变性的特征，以及如何对提取的特征进行有效的训练识别。目标识别属于模式识别的范畴，在一定意义上也可以理解为图像识别，即在一个确定的图像中提取出感兴趣的目标。对于人而言，实现图像理解是一个简单、迅速的过程，而且很大程度上是无意识的。然而对于计算机而言，建立一个稳定、自动并且能够适应各种条件的图像理解系统是非常困难的。这些困难是由图像理解所处理的图像和目标的本性决定的，具体表现两个方面。首先，从图像中准确、完整地提取目标的几何和物理特性是困2中国石油大学( 华东) 硕士论文第1 章绪论难的。所要处理的数字图像，其本质是一个景物的亮度在离散的二维空间上的数字采样，不具备景物的三维结构信息；成像信号随光照条件、视点而变化：而且这些信号还会因为受到高光、二次反射、遮挡、等影响而损失或者丢失信息。在无约束的条件下，不可能建立有效的解析模型来补偿或者消除这些影响。其次，待识别的目标本身很复杂。图像理解所要分析处理的目标种类很多，包括各种自然目标、人造目标。即使能够完整的获取可以准确描述具体目标的图像特征，识别仍然是一个困难的工作。一是因为每个目标类中包含的各个目标的具体实例之间，它们与这个类别的典型目标之间差别可能很大，很多实例不能完全精确描述。二是因为不同目标类之间的区别不仅仅在于它们对应的特征数值上的差别，而且用来定义它们的特征也可能是不同的，这使得准确可靠地对各类目标进行分类成为一个困难的问题 2 1 。再次，目标识别系统的实验仅仅使用了有限数据的数据库，从而导致系统对目标以及背景等相关信息缺乏先验和知识的有效利用。以上的种种限制都使得目标识别面临着关键技术的挑战【3 1 。目标识别研究有着很强的应用背景。尤其是在军事领域，利用卫星或飞机等所拍摄的照片检视或侦查地面目标，因为其范围大，不受国界等的地理限制，一直是获取有关信息的重要手段，成为侦查、制导、警戒以及防卫系统中不可或缺的手段。同时，在国民经济的其它领域，目标识别技术也有着很广泛的应用，比如字符识别嗍，指纹识别【5 1 ，人脸识别6 】川，车牌识别【8 】【9 1 ，飞机机型识别1 0 1 ，条形码识别【l l 】，工业领域的产品自动探伤、检查，生物学领域的细胞分类、染色体分类、放射图像分析等等。如何从图像中获得有用的信息一直是目标识别研究的重要课题。国3中国石油大学( 华东) 硕士论文第1 章绪论内外的科学工作者已经做了大量的研究工作，并取得了一些可喜的成果。进行这方面的研究目的是为了推广其应用，因此寻找解决图像识别的方法来满足实用要求是非常重要的。1 3 论文研究内容本论文在目前目标识别技术已有成果的基础上，分析各种识别方法的技术特点，研究基于支持向量机的目标识别技术，以及具有位移、尺度、旋转、光照等不变性的目标特征提取技术，利用支持向量机作为分类器进行目标的训练与识别，从而提高系统识别率。主要研究内容如下：( 1 ) 通过对目前目标识别技术理论的研究，学习目标检测定位、特征提取以及目标识别方法，选择系统实现平台。( 2 ) 研究支持向量机算法，结合s v m l i g h t 与h u 不变矩特征提取技术进行训练和识别，分析实验结果验证该方法的有效性。( 3 ) 通过实验对s v l 讧和神经网络两种分类方法进行比较，以及在s v m 方法下采用多种核函数进行对比研究，分析实验结果，设计合理的目标识别分类器。( 4 ) 利用v i s u a lc + + 对图像进行处理，并结合图像运算功能强大的m a f l a b 进行特征提取，执行上实现两者的联合，从而提高系统的运算效率。( 5 ) 设计基于支持向量机的目标识别系统，实现实时目标捕捉、目标检测、特征提取、分类器训练以及目标识别等功能，并通过实验验证其可靠性。4中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论第2 章目标识别及支持向量机相关理论目标识别就是图像的模式识别，它是模式识别技术在图像领域中的具体运用，是图像处理的高级阶段。它所研究的是使用机器分析和识别周围物体的视觉图像，从而可得出结论性的判断。2 1 目标识别技术目标识别技术主要分为目标检测、特征提取以及目标识别三个部分。目标检测是指在输入图像中确定所有目标( 如果存在) 的位置、大小、位姿的过程。目标特征提取是目标识别中的关键问题，目标识别的效果好坏受所提取特征优劣的直接影响。2 1 1 目标检测目前目标检测方法分类众多，主要可以将目标检测方法分为以下四类【3 刀：基于知识( k n o w l e d g e - b a s e dm e t h o d s ) 的方法、基于特征不变性( f e a t u r ei n v a r i a n ta p p r o a c h e s ) 的方法、基于范本匹配( t e m p l a t em a t c h i n gm e t h o d s ) 的方法和基于外观( a p p e a r a n c e - b a s e dm e t h o d s ) 的方法。( 1 ) 基于知识的目标检测方法利用对目标的先验知识导出的规则来进行目标检测，即将研究者对目标的了解表达为计算机可以理解的规则，并用这些规则对待检测目标进行提取并验证。早期该方法主要以逐点逐级匹配规则为主，现在多采用金字塔结构的规则结构【3 引。这种方法本身也存在着不足之处，比如识别率不高，对于不同视角的目标由于某些特征的不可见而导致无法使用5中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论该方法，另外用于描述目标特征之间关系的规则也不容易设计。尽管如此，该方法采用的对图像进行马赛克处理、分层次检测和通过先验知识知道目标检测的思想对目标检测的研究提供了很大帮助。( 2 ) 基于模板匹配的目标检测方法采用某个函数来预先定义或参数化表示一类标准目标模式，对于输入图像中的候选目标，独立地计算目标轮廓，以及目标中标志点与标准模式之间的相关性，若相关性值超过了预先设定好的阀值，就接受该候选目标。此方法在实际运用时操作简单，但是困难在于范本的构造。由于目标在图像中所占比例以及背景等很多因素是无法确定的，因此很难构造一个统一标准的模板。( 3 ) 基于外观的目标检测方法和模板匹配中的方法不同，模板匹配中的模板是由专家预定义的，而基于外观方法中的“模板”是通过训练图像中的样本学习得到的。再将这些学习到模型应用到目标图像的检测和识别中。有时候该方法又称为基于统计理论和机器学习的检测方法。归纳起来，基于外观的方法主要有以下几种：主成份分析p c a( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 3 9 4 ”，贝叶斯决策规则( b a y c s d e c i s i o nr u l e ) 【4 2 】，神经网络( n e u r a ln e t w o r k s ) 4 3 4 s ，隐马尔可夫模型( h i d d e nm a r k o v m o d e l s ) 4 6 1 ，支持向量机( s u p p o r t v e c t o r m a c h i n e ) 1 4 _ 7 】【4 引，积分图像( i n t e g r a li m a g e ) 特征法【4 9 】【剐，信息论方法( i n f o r m a t i o n - t h e o r e t i c a la p p r o a c h ) ，归纳学习法( i n d u c t i v el e a r n i n g ) 5 1 】等等。基于外观的目标检测方法有很高的检测率，但需要事先训练检测系统，训练时间较长，另外如何选择合适的训练样本和训练策略也是一个难题。( 4 ) 基于特征不变性的目标检测方法6中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论研究者试图找到目标的不变特征作为检测的依据，这来源于以下事实：人类可以毫不费力的找到视野中的所需目标。由此可推断尽管有着上面所述的诸多变化因素，目标也可能存在不变的特征或共性。基于特征不变性的方法实际上是一种自下而上的方法，它先找出图像中目标的特征，然后根据这些特征的相互关系来判断否是所需目标。2 1 2 特征提取特征提取是目标识别研究的基本问题之一。对于图像识别而言，提取有效的图像特征是完成图像识别的首要任务。目前用于图像识别的特征可以分为下面几种【5 2 】：直观性特征，如图像的边缘、轮廓、纹理或区域等；灰度的统计特征，如直方图特征；变换系数特征，如f o u r i c r 变换、h o u g h 变换、h a d a m a r d 变换等；代数特征，它反映图像的一种内在属性比较典型方法如矩阵的奇异值分解( s v d ) 等。特征提取的目的是获得一组“少而精”的分类特征，即获得特征数目少且分类错误概率小的特征向量。特征提取常常分为两步，特征形成和特征提取【5 3 1 。特征形成就是根据被识别的对象产生一组原始特征。它们可以是传感器的直接测量值，也可以是将传感器的测量值作某些计算后得到的值，这些值称为原始特征，产生这些原始特征的过程称为特征形成，是一种减少特征数目的方法。对高维数据集合的分析，常常是一项很复杂的工作。目标识别系统经常受到高维问题的困扰。特征提取过程是将数据空间( 模式空间) 变换为特征空间，在对象分类过程之前，它利用变量变换使某些变量比其它变量更重要，因此可以将其看成是一种降维，那些更重要的变量称为特征。如果次要的变量可忽略不计，那么就达到了所需的降维目的。虽7中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论然同最初的数据空间相比，特征空间维数降低很多，但它仍保留数据内容的大多数本质信息。此外，从统计意义上讲，次要分量有可能来自于噪声( 或者是来自于目标固有特征无关的外界干扰) ，因此除去这些分量可能会有益处。常用的特征提取方法有主元分析法( p c a ) 、线性判别分析( u a ) 、k - l 变换以及不变矩方法等等。( 1 ) 主成分分析方法主成分分析( p c a ) 是目前应用最广泛的一种特征提取方法，属于一种统计学习方法。它最早是由霍特林提出的，是一个可以去掉随机变量中各元素间相关性的线性变换。此后，卡胡南( k a r h u m e n ) 和列夫( l o e v e ) 【跏提出了一种针对连续信号类似的变换，由这种方法派生的离散图像变换方法，其主要思想是根据样本点在多维目标空间的位置分布，以样本点在空间中变化最大方向，即方差最大的方向，作为判别向量来实现数据的特征提取与压缩。从概率统计观点可知，一个随机变数的方差越大，该随机变量所包含的信息就越多。所谓主成分就是原始数据的所个变量经线性组合( 或映像) 后得到的变量，使变换后的变量方差为最大部分。各个主成分之间是相互线性无关的( 正交的) ，从第一主成分后，均是按方差大小顺序排列( 即对应特征值按大小顺序排列) 。对于特征值为 的主成分( 五也是该主成分的方差) 表示样本点在其方向上的离散程度，丑的贡献率玑可用公式( 2 1 ) 表示聃= 而彘( 2 1 )主成分中方差较小或元较小的主成分被认为包含噪声，在分析时不8中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论使这些变量引入模型，从而使分析的主成分减少，以便达到去除原始图像的冗余信息、保留有用信息、降低特征空间维数、减少噪声和光照变化影响的目的。( 2 ) 线性判别分析方法线性判别分析( l d a ) 最初是由a f i s h e r 在1 9 3 6 年提出的【5 5 】，又被称为f i s h e r 线性判别。在图像特征提取中，从高维空间向低维空间映射不是随意的，要求样本经过映像后在低维空间中更加易于分类，从而达到识别的目的。l d a 就是为解决这样的问题而提出的。它定义了两个扩散矩阵，类内扩散矩阵和类间扩散矩阵，l d a 希望得到从高维样本空间到低维特征空间的变换矩阵能够满足：在降低维数的同时，使得类内扩散矩阵尽量小，类间扩散矩阵尽量大。经过变换后，同一类别内的训练样本特征点将离得更近，不同类别之间的训练样本特征点距离更远，即在降低维数的同时，提高了对目标进行分类的能力。( 3 ) k - l 变换方法在目标识别领域，k l 变换被公认为特征抽取的最有效的方法之一，k - l 展开应用于特征提取，形成了子空间法目标识别的基础。利用矩阵k - l 变换抽取特征，具有稳定性、转置不变性、位移不变性和镜像变换不变性，结合k - l 变换的图像正交基的算法用于目标识别，取得了较好的识别效果。k - l 算法假设数据库里有m 幅目标图像r i ，r 2 ，l ，其灰度平均值为妒，将每一副图像与之相减后构成一组大向量4 = 【中。， d 2 , - o - , 雪。】，其中m ，= l m ，它用于进行主分量分析，找出m 个正交向量及本征值9中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论乃最好地描述数据分布规律，瓦及以是协方差c 矩阵的本征向量和本征值：c = 击薹叩：= 朋7( 2 2 )k - - l 变换以校准后的标准图像作为训练样本集，产生矩阵，即=圭圭(z一以)一朋)7=-l1ll=li = 1z 一纡房( 2 3 )_厶il其中，z 为第f 个训练样本集的图像向量，用行堆栈形成，设图像m ：( n 大d , , i 扮j f ( x ，y ) ，则z =五。丘。：f t m 其中石=z ( ，0 )z ( ，1 )z u ，n - i )式中z 为图像样本集第f 个样本，为第f 帧第，行元素形成的列向量。所= ，：为训练样本集的平均图向量，l 为训练样本的总数。求o = 1出的特征值五及相应的正交归一特征向量q o = o ，1 ，2 ，工一1 ) 。若把转置的因素考虑在内，则变换阵的行既是的特征向量。该矩阵为：u =与lq 2q 吃1e 2 t乞：e ) , t v ，i 。2 e o v m ；v( 2 4 )这就是图像的特征向量，它通过计算矩阵的特征值与特征向量而求出。1 0中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论( 4 ) 不变矩方法矩在统计学中用于表征随机量的分布，而在力学中用于表征物质的空间分布。若把二值图或灰度图看作是二维密度分布函数，就可以把矩技术应用于图像分析中。这样，矩就可以用于描述一副图像的特征，并提取与统计学和力学中相似的特征。计算机系统在识别图像时，应具有的一个重要特征是对图像的平移、旋转以及比例变换具有不变性。一个最直观的方法是要求图像特征本身具有“不变性”，即尽可能寻求图像本身的“不变性”特征，因此不变性特征的研究一直是感知科学和计算机视觉的研究重点。不变矩算法就是一种通过提取具有平移、旋转和比例不变性的数学特征，从而进行图像识别的方法。近年来，二维和三维物体矩不变性的研究引起了越来越广泛的关注。大体上说，不变矩可以分为代数不变矩和积分不变矩。在这两种数学方法的基础上，h u 于1 9 6 1 年发表了其第一篇关于应用图像二维矩进行目标识别的论文，h u 首先提出代数不变矩的概念，并给出了一组基于通用矩组合的代数矩不变量。这些矩具有平移、旋转和尺度不变性。随着研究的进一步深入，研究者们在h u 矩的基础上推导出一些其它的不变矩【刚9 】以及其快速算法。2 1 3 目标识别目前主要有以下几种目标识别方法：( 1 ) 统计决策法统计决策法以概率论和数理统计为基础，它包括参数方法和非参数方法。参数方法主要以b a y e s 决策准则为指导。其中最小错误率和最小风险贝叶斯决策是最常用的两种决策方法。利用该理论，目标识别问题转l l中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论化为一个后验概率的计算问题。该方法是以先验概率已知为前提的，在具体的事例中比较难以满足，需要对其进行先验估计。然而要想得到准确的估计值，需要被估计的样本趋向无穷大，且样本之间要相互独立，这也是比较难以实现的。( 2 ) 结构目标识别结构目标识别是利用目标的结构描述与句法描述之间的相似性对目标进行分类。每个目标由它的各个子部分( 称为子模式或模式基元) 的组合来表示。对目标的识别常以句法分析的方式进行，即依据给定的一组句法规则来剖析模式的结构。当目标中每一个基元被辨认后，识别过程就可通过执行语法分析来实现。结构目标识别的关键是模式基元的选择，但要想选择一个结构简单、含义明确、方便数据描述、易抽取而且结构信息少的基元也是相当困难的。( 3 ) 模糊识别模糊识别是解决目标识别问题时引入模糊逻辑的方法或思想。同一般的目标识别方法相比较，模糊模式识别具有客体信息表达更加合理，信息利用充分，各种算法简单灵巧，识别稳定性好，推理能力强的特点。但准确合理的隶属度函数很难得到，如何建立比较合理的隶属度函数是需要进一步解决的问题。( 4 ) 人工神经网络人工神经网络的主要特点在于其具有信息处理的并行性、自组织和自适应性、具有很强的学习能力和联想功能以及容错性能等，在解决一些复杂的模式识别问题中显示出其独特的优势。但同时，人工神经网络是一种复杂的非线性映像方法，其物理意义比较难解释，在理论上还存在一系列亟待解决的问题；在设计上，网络层数和节点数的确定带有经1 2中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论验性和盲目性；在算法复杂度上，它的算法比较复杂，维数多的时候，训练时间比较长；在算法稳定性上，比较容易陷入局部极小的问题；泛化能力上也比较难以控制。( 5 ) 支持向量机支持向量机是基于统计学习理论的，该理论提出了结构风险最小化的原则：即把函数集分解为一个函数集序列，使各个子集能够根据v c 维的大小排列，在每个子集中寻找最小经验风险。选择最小经验风险和置信范围之和最小的子集，即达到期望风险最小，这个子集中使期望风险最小的函数也即所求的最优函数，这种思想称为结构风险最小化( s 刚) 。支持向量机的基本思想是：首先通过非线性变换将输入空间变换到一个高维空间，甚至是一个无限维空间，然后在这个高维空间求取最优分类面，其中非线性变换是通过核函数的方法来实现的。支持向量机方法通过内积计算比较有效地解决了维数灾难问题，通过在高维空间设计最优分类面，比较好地实现了v c 维最小的问题；在数学上支持向量机的训练问题可转化为一个求解受约束的二次型规划问题，这个问题存在唯一解，避免了神经网络训练结果不稳定、容易陷入局部极小的问题。支持向量机方法在模式识别中，特别是小样本、高维数的模式识别中，具有传统识别方法无法超越的优势，也是现在模式识别领域的首选分类器。2 2 支持向量机基于资料的机器学习是现代智慧技术中重要的方面，研究从观测数据出发寻找规律，利用这些规律对未来的数据或无法预测的数据进行预测。到目前为止，关于机器学习还没有一种被共同接受的理论框架，其1 3中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论实现方法大致可以分为三种：( 1 ) 经典的统计( 参数) 估计方法在这种方法中，参数的相关形式是己知的，训练样本用来估计参数的值。这种方法有很大的局限性，首先，它需要己知样本分布形式，其次，传统统计学研究的是样本数日趋于无穷大时的渐近理论，但在实际问题中，样本数往往是有限的。( 2 ) 经验非线性方法非线性方法，如人工神经网络( a n n ) ，利用己知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。( 3 ) 统计学习理论与前两种方法比较。统计学习理论( 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 )有其自身的优势。它是一种专门研究小样本情况下机器学习规律的理论 1 7 1 。v a p n i k 等人从六、七十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。统计学习理论的一个核心概念是v c 维，它是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标，在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、推广性能等的重要结论【1 8 】【1 9 1 。在此理论的基础上，发展了一种新的学习方法，即支持向量机。支持向量机是以结构风险最小化为归纳原则，从而避开了传统的学习方法难以逾越的障碍，特别是局部极小值问题。由于统计学习理论有着完备的理论体系，加之s v m 具有比较强的推广能力，这使得s v m 受到越来越多的重视。在模式识别、数据挖掘、回归估计等相关领域取得了很好的成果 2 0 - 2 s ，成1 4中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论为继神经网络研究之后一个新的研究热点，它必将有力推动整个机器学习理论和技术的发膨1 2 】【2 9 】。2 21 统计学习理论任何学习机器都可以看成是一组函数的集合，机器学习问题就是从函数集合中选择合适的逼近函数并参数化的过程。所谓学习机器的容量也就是它所对应的函数集的容量，或者叫复杂度。容量或复杂度代表了函数集实现从输入到输出的映射的能力，对学习机器来说，叫做学习能力。容量越大，机器的学习能力就越强。在模式识别问题中，学习能力强的机器能够得到更加复杂的分类面。然而，越复杂的分类面，就越依赖于训练数据分布的细节，这种对训练资料的过于细致的刻画，往往会导致学习机器的推广能力不足。( 1 ) v c 维为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指针，其中最重要的是v c 维( v a p n i k - c h e r v o n e n k i sd i m e n s i o n ) 。v c 维是一组可以被定义成各种类型函数的函数集跨( w 表示未知参数，w 的选择指示了不同类的函数)的一个特性。这里只考虑二类模式识别的情况，所以判别函数可写成f ( x ，w ) _ 1 ，1 慨w 。现在如果一组给定的l 个点可以被分类成全部可能的2 。种结果，那么这组给定点可以被那组函数分类。这组函数集_ ，n 猹的v c 维就是所有训练样本点能够被f ( w ) g 分类的点的最大数目。这里要注意，如果v c 维为h ，那么至少存在一组h 个点可以被分类，但通常来说，1 5中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论并不是所有包含h 个点的样本组都可以被完全分类【1 4 1 。假设数据存在的空间为r 2 ，并且函数集矿( w ) 由有向的直线组成，对与一条给定的有向直线，在线一边的点可以被表示为1 ，线另一边的点可以被表示为- 1 。如图2 1 所示。这里能够找到3 个点被扩( w ) ) 完全分类，但无法找到4 个点也能够被完全分类，所以在平面中的有向直线这个函数集矿( w ) 的v c 维为3 。淋飞。：卜。剖粤t 衫必图2 1 在平面空间的3 点可以被有向直线完全分类v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) ，遗憾的是目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道其v c 维。比如在1 3 维实数空间中线性分类器和线性实函数的v c 维是n + l ，f ( x ，w ) = s i n ( w x ) 的v c 维则为无穷大。对于一些比较复杂的学习机器，如神经网络，其v c 维除了与函数集( 神经网结构) 有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习函数集，如何用理论或实验的方法计算其v c 维是当前统计学习理论中有待研究的一个问题【1 9 】【阍。( 2 ) 推广性的界统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指1 6中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论示函数集中的所有函数( 包括使经验风险最小的函数) ，经验风险心，( w )和实际风险尺( w ) 之间以至少以l 一玎的概率满足如下关系例：r ( w ) s ( w ) + h ( 1 n ( 2 n h ) + 1 ) - i n ( r 4 ) ( 2 5 )其中h 是函数集的v c 维，n 是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险( 训练误差) ，一是置信范围，它和学习机器的v c 维及训练样本数有关，可以简单地表示为：r ( w ) s r 一( w ) + o ( h n )( 2 6 )它表明在有限训练样本下，学习机器的v c 维越高( 复杂性越高) 则置信范围越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。需要指出的是推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤其当v c 维较高时更是如此，而且，这种界只在对同一类学习函数进行比较时有效，可以指导从函数集中选择最优的函数，在不同函数集之间比较却不一定成立。寻找更好地反映学习机器能力的参数和得到更紧的界是统计学习理论今后的研究方向之一。( 3 ) 结构风险最小化传统的模式识别技术是基于经验风险最小化的，而支持向量机则最小化结构风险。结构风险即是指对于一组确定的但分布概率未知的数据，对其进行错误的分辨的可能性。v c 的置信范围取决于所选择的分类函数，而经验风险和实际风险则依赖于由训练过程决定的那个函数，寻找选定函数集的子集，每个子集1 7中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论的风险都被最小化。很明显v c 维h 不可能平滑连续的变化，因为它是一个整数。通过把整个分类函数集分成一个个嵌套的子集来引入一个“结构”，如图2 2 所示。对每个子集，必须既能够算出v c 维h 又能够得他的置信范围。于是经验风险与置信范围之和最小的那个子集就是使期望风险最小的子集。这个子集的判别函数就是最优函数。属睦函数集子集：s l c s 2 cs 3v c 维：啊h 2 如图2 2 结构风险最小化示意图图2 2 表达了统计学习系理论的内容；风险上界是由经验风险和置信范围共同决定的；经验风险和置信范围之间是此消彼长的关系，经验风险随v c 维的增大而减小，置信范围随v c 维的增大而增大；最优函数集对应着风险上界的最低点。在结构风险最小化原则下，一个分类器的设计过程包括以下两方面的任务：一是选择一个适当的函数子集( 使之对问题来说有最优的分类能力) ；一是从这个子集中选择一个判别函数使经验风险最小。2 2 - 2 支持向量机( 1 ) 线性判别式先来考虑二类分类问题。设数据点为t o = 1 , 2 ，m ) ，其相应的值1 8中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论y ；= 1 。每个资料点由一个d 维空间输入或特征空间来描述。令分类函数为：f c x ) = s i g n ( w 工一b ) 。其中向量w 决定了判别平面的方向。标量b 决定了平面的偏移量即阀值。假设这两类是可以被线性分离的，也就是存在一个平面可以正确的将所有的数据点分类成两个集合。可以有无限个可能平面能够正确的进行分类。图2 3 显示了两种不同的分类平面，分别用实现和虚线表示。从直观上看，实平面要好一点，因为它可以允许数据点有些小的变化而不会导致分类错误。除去其它的附加信息，实平面对后续数据的分类有着更好的泛化能力。这个面也就是最优分类面。图2 3 两个可能的分类平面图2 4 分割两凸包最近点的最优分类面图2 4 显示了建立距离两类最远的两个平面的一种方法。将每个类的数据点的外围进行连接，得到凸包，这里的凸包是指能够包含所有该类数据的最小的凸集，检测每个凸包上的点，找到其中距离最近的两个点( d 和c ) 。如果能建立这样一个平面把两类的数据点分割开来，那么在某种意义上讲，这个分类器应该具有不错的分类能力。寻找两个凸包中最近的点，可以通过求解下面的二次规划问题来解决。r a 。i ni k - d l l 2 2c = 薯d = q 而肿c l a t s l，v l e c a l s s - 1( 2 7 )1 9中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论q = 1啦= ls t y f c l a n ly ，e d a s s - i啦0i = 1 ，m可以注意到，分类结果只取决于图2 5 中指示的3 个点。还有另一种方法就是最大化两个支持平面之间的距离。支持平面指能够使得一类中的所有点都在该面的一边。对于分类为+ l 的点，希望存在w 和b 使w 五 6 或w - 五- b o 。假设1 w 一一b i的最小值为k ，由于对于这样的判别函数可以进行比例的改变，所以对其进行归一化得到w 五一b 1 。同样的，对支挣向量图2 5 最大化间距的两最优平面于分类为1 的点可以得到w 葛而l 。为得到距离两集合最远的平面，只需简单的最大化两集合的支撑平面的最大间距，如图2 5 所示。两个支撑平面被相互“推离”，直到它们分别碰到两集合中的点( 支持向量) ，这就是最大边缘算法。两支撑平面v 沙x = b + l 和w x = b - 1 的间距为y = 2 1 1 w 吣所以最大化间距等价于在下列二次规划问题中最小化i l w l l ：2 。卿0 卅1 2 2s t p 焉西峥ly i c l a s s l( 2 8 )w x r o 的点) 得到平面权系数w = 见q x i 和阀值6 。容易证明，解将只有一部分( 通常是少部分) 啦不为零，对应的样本就是支持向量。假设西为最优解，则w + = y ，a i x i 即最优分类面的权系数向量是训练样本中支持向量的线性组合。得到支持向量及向量w 后，分类器中的阀值b 可以通过两类中任意一对支持向量取中值得到。6 = 委 w + x ( 1 ) + w o 工( 一1 ) 】其中，( 1 ) ，工( 一1 ) 表示两类中任何一个支持向量。于是得到最优分类的判别函数为：( x ) = s 弘 ( w x + b ) ) = s g n 4 l y l ( 而工) + 6 ) ( 2 1 0 )2 1中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论( 2 ) 非线性可分对于线性不可分的情况，支撑平面的方法将失效，因为这种情况下无法得到二次规划问题( 2 8 ) 。为解决这个问题，必须放宽约束条件来保证每个数据点都能够合适的处在支撑平面的一边。可以通过对二次规划问题( 2 8 ) 进行一个小的修改，引入一个非负的松弛变量厶，这样加入了一个惩罚项，如下式：卿；n r + c 喜刁s t 弘( ，而一6 ) + z j 1( 2 1 1 )z 。0f = 1 ，m其中c 为惩罚因子，c 越大表示对错误分类的惩罚越大。( 2 1 1 ) 式的对偶式为：哑n丢y 。y 肛口 一一宝啦s t 窆m 嘶= o( 2 1 2 )c 埽- 0f = l ，册( 2 9 ) 式和( 2 1 2 ) 式的唯一区别就是对优增加了一个上界【16 1 。( 3 ) 核方法核方法的基本概念就是把向量映射到一个更蔚维的空间中。考虑一下线性不可分的情况，如图2 6 所示。如果把2 维空间变换到3 维空间如图2 7 所示，黑白两类向量就可以线性分离了。中国石油大学( 华东) 硕士论文第2 章目标识别及支持向量机相关理论图2 6 二维空间中的两类图2 7 三维空间中的情况令o 为高维空间变换，高维空间必须满足其空间的距离已经被定义并且所定义的距离要与原始空间的距离有一定的关系。引入核函数融力来满足上述条件。核函数满足：k ( x ，y ) = ( 烈功)陀1 3 )上式表明通过核函数在高维空间中测量的工与的距离被o 转换。如果通过核函数测量间距并且进行优化，将得到一个非线性的边界。变换空间中的边界可以表示为：w 7 烈工) + 6 = 0( 2 1 4 )将w