（计算机软件与理论专业论文）基于svm技术的手写数字识别的研究.pdf

山东师范大学硕士学位论文 基于s v m 技术的手写数字识别的研究 摘要 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是i 扫v a p n i k 于1 9 9 5 年提出的针对分类和回 归问题的统计学习理论，是在高维特征空间使用线性函数假设空间的学习系统。近年来， 其理论研究和算法实现方面都取得了突破性进展，开始成为克服维数灾难和过学习等传 统困难的有力手段。由于s v m 方法具有许多引人注目的优点和有前途的实验性能，越来越 受重视。该技术已成为机器学习研究领域中的热点，并取得很理想的效果，如人脸识别、 手写体数字识别和网页分类等。 手写数字识别在很多领域具有广泛的应用前景，国内外学者对此做了大量的研究工 作，提出了很多预处理和模式识别的算法，大大提高了手写数字的识别精度。但到目前 为止，手写数字识别的识别精度还有待提高，核函数核参数选择等问题尚有待解决。 为了提高手写数字识别的精度，本文将支持向量机应用于手写数字识别，开发了 s v m h d r 软件系统。在系统总结前人工作的基础上，重点研究影响s v m 分类法性能的 各种因子。把这一选择最佳因子的方法流程化，验证了支持向量机在手写数字识别中的 有效性。此外，本文在手写数字的识别过程中提出了引入先验知识的虚拟样本法，期望 该方法能对提高基于支持向量机的手写数字识别的精度起到推动作用。本文主要工作体 现在以下方面： ( 1 ) 对多类分类方法进行分析比较。 着重对一类对余类法( o n e a g a i n s t a 1 1 ) ，成对分类法( o n e a g a i n s t o n e ) 和有n - n 环图法 ( d i r e c t e d a c y c l i cg r a p h ，d a g ) - 一种分类方法进行了比较分析。针对具体数据库，在识别 精确度、训练时间和测试时间方面进行了实验，为手写数字识别选择适用的多类分类方 法。根据实验结果，本文选择使用成对分类方法。 ( 2 ) 对训练算法进行比较分析。 对三种主流训练算法；c h u n k i n g 算法，o s u n a 算法和s m o 算法，在速度、精度和内 存节省等方面进行对比。相比之下，s m o 算法速度较快，精度较高，比较节省内存，且 适合大规模问题的求解。因此，本文选择该算法作为手写数字识别的训练算法。 ( 3 ) 验证支持向量机用于手写数字识别的有效性。 鉴于支持向量机的优点，将其应用于手写数字识别来提高识别精度。将各方面选出的 最优因子用于s v m h d r 软件系统中，使该过程流程化。对具体的手写数字库m n i s t 进行数据预处理，归一化，最佳核函数与核参数的选择，训练和测试等操作。将程序结 果与使用其他技术对同一数据库的识别结果进行比较，验证了s v m 识别方法的有效性。 ( 4 ) 提出引入先验知识的虚拟样本法。 支持向量是训练集的一个子集，基本上可以代表训练集中的全部信息，也就是说只有 山东师范大学硕士学位论文 这个子集对分类问题的求解起作用。因此，在一个s v m 训练得到的支持向量集合上训练 另一个s v m ，其测试性能并不亚于在整个训练集上训练得到的结果。 利用对输入图像的某些变换不会改变识别结果的理论，本文在验证支持向量机在手写 数字识别中有效性的程序基础上，提取出训练集的支持向量，在该集合上进行平移不变 性变换，人工生成了虚拟支持向量，加上没有变换的支持向量，得到数量为原支持向量 五倍的虚拟样本。 然后对得到的虚拟样本进行二次训练，并对m n i s t 手写数字库的测试集进行测试。 与验证s v m 分类法有效性程序的识别结果相比，该方法确实有效地提高了手写数字识别 的精度，得到的结果比较理想。 关键词：s v m ；手写数字识别；多类分类；先验知识；s v m h d r 分类号：t p 3 9 1 。 山东师范大学硕士学位论文 r e s e a r c ho fh a n d w r i t t e nd i g i tr e c o g n i t i o nb a s e do ns v m a b s t r a c t s u p p o r tv e c t o rm a c h i n e ( s v m ) i sak i n do fs t a t i s t i c a ll e a m i n gt h e o r yf o rc 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 ，w h i c hi s p r o p o s e db yv a p n i ki n1 9 9 5 i t sal e a r n i n gs y s t e mu s i n gl i n e a r f u n c t i o nt oa s s u m es p a c ei nh i g h d i m e n s i o nf e a t u r es p a c e i nt h er e c e n ty e a r s ，i th a sg o t b r e a k t h r o u g hi m p r o v e m e n ti ni t st h e o r yr e s e a r c ha n da l g o r i t h mi m p l e m e n t s ，a n dt h e r e f o r ei t b e c o m e sap o w e r f u lm e t h o do fo v e r c o m i n gt h et r a d i t i o n a ld i f f i c u l t i e ss u c ha sd i m e n s i o n d i s a s t e r ，o v e r f i t t i n g ，a n ds oo n s v mi sb e i n gp a i dm o r ea t t e n t i o nt ob e c a u s eo fm a n y r e m a r k a b l ea d v a n t a g e sa n dp r o m i s i n gp e r f o r m a n c ei ne x p e r i m e n t s i th a sb e e nt h ee n t h u s i a s t i c o ft h em a c h i n el e a r n i n gr e s e a r c hd o m a i na n di th a sg o tv e r yi d e a le f f e c t ，s u c ha sf a c e r e c o g n i t i o n ，h a n d w r i t t e nd i g i tr e c o g n i t i o n ，w e bc l a s s i f i c a t i o n ，a n ds oo n h a n d w r i r e nd i g i tr e c o g n i t i o nh a sw i d ea p p l i c a t i v ef o r e g r o u n di nm a n yd o m a i n s ，a n d s c h o l a r si n s i d ea n do u t s i d eh a v ed o n em u c hr e s e a r c hw o r ko ni t t h e yh a v er e p o s e dm a n y p r e p r o c e s s i n ga l g o r i t h m sa n dp a r e mr e c o g n i t i o na l g o r i t h m s ，w h i c hi m p r o v e st h ea c c u r a c yo f h a n d w r i r e nd i g i tr e c o g n i t i o ni ng r e a tm e a s u r e b u tu pt on o w , t h er e c o g n i t i o na c c u r a c ys t i l l n e e dt ob ei m p r o v e da n dt h ep r o b l e mo fs e l e c t i n gk e r n e lf u n c t i o n sa n dk e r n e lp a r a m e t e r ss t i l l n e e dt ob es o l v e d t oi m p r o v et h ea c c u r a c yo f h a n d w r i t t e nd i 【g hr e c o g n i t i o n ，t h i sp a p e ra p p l i e ss u p p o r tv e c t o r m a c h i n et oh a n d w r i t t e nd i g i tr e c o g n i t i o na n de x p l o i t sas o f t w a r es y s t e mn a m e ds v m h d r o nt h eb a s i so fc o n c l u d i n gt h er e s e a r c ho ft h ep e o p l eo ft h ep a s t ，t h i sp a p e r p u t st h ee m p h a s i s o nt h ef a c t o r st h a ti n f l u e n c et h ep e r f o r m a n c eo fs v mc l a s s i f i c a t i o n w ef l o wp r o c e s st h e m e t h o do fc h o o s i n gt h eb e s tf a c t o r st ov a l i d a t et h ee f f e c t i v e n e s so fs u p p o r tv e c t o rm a c h i n ef o r h a n d w r i t t e nd i g i tr e c o g n i t i o n i na d d i t i o n ，am e t h o dn a m e dv i r t u a ls a m p l e si sr e p o r t e di nt h i s p a p e rt oi n t r o d u c ep r i o rk n o w l e d g ei n t oh a n d w r i t t e nd i g i tr e c o g n i t i o np r o c e d u r e ，e x p e c t i n gt o p u s ht h ed e v e l o p m e n to fi m p r o v i n gt h ea c c u r a c yo fh a n d w r i t t e nd i g i tr e c o g n i t i o nb a s e do n s u p p o r tv e c t o rm a c h i n e n l em a i nw o r ko f t h i sp a p e ra p p e a r si nt h ef o l l o w i n ga s p e c t s ： ( 1 ) a n a l y z i n ga n dc o m p a r i n gt h em e t h o d so f m u l t i - c l a s sc l a s s i f i c a t i o n t i l i sp a p e rm a i n l ya n a l y z e sa n dc o m p a r e st h r e ec l a s s i f i c a t i o nm e t h o d s ：o n e - a g a i n s t a 1 1 o n e - a g a i n s t - o n ea n dd i r e c t e da e y c l i cg r a p h ，a n dd o e se x p e r i m e n t so nc o n c r e t ed a t a b a s e st o c o m p a r et h e mi nt h er e c o g n i t i o na c c u r a c y , t r a i n i n gt i m ea n dt e s t i n gt i m ea s p e c t st of i n dt h e m o s ta p p l i c a b l em u l t i c l a s sc l a s s i f i c a t i o nm e t h o df o rh a n d w r i t t e nd i g i tr e c o g n i t i o n a c c o r d i n g t ot h er e s u l t so f t h ee x p e r i m e n t ，t h eo n e - a g a i n s t o n em e t h o di st h em o s ta p p r o p r i a t em e t h o d ( 2 ) c o m p a r i n ga n da n a l y z i n gt h et r a i n i n ga l g o r i t h m s 1 i i 山东师范大学硕士学位论文 c o m p a r i n gt h et h r e em a i nt r a i n i n ga l g o r i t h m s ：c h u n k i n ga l g o r i t h m ，o s u n aa l g o r i t h ma n d s m o a l g o r i t h mi nt h es p e e d ，t h ea c c u r a c ya n dm e m o r ys a v i n g a f t e rc o m p a r i s o n ，w ef i n dt h a t s m o a l g o r i t h mh a sf a s ts p e e d ，h i 曲a c c u r a c ya n dn e e dl e s sm e m o r y , s o i ti sa p p r o p r i a t et ot h e s o l u t i o no fl a r g e - s c a l ep r o b l e m s t h e r e f o r e ，t h es m oa l g o r i t h mi ss e l e c t e df o rh a n d w r i t t e n d i g i tr e c o g n i t i o n ( 3 ) v a l i d a t i n gt h ee f f e c t i v e n e s so fs u p p o r tv e c t o rm a c h i n ef o rh a n d w r i t t e nd i g i tr e c o g n i t i o n t h i sp a p e ra p p l i e ss u p p o r tv e c t o rm a c h i n et oh a n d w r i t t e nd i g i tr e c o g n i t i o nt oi m p r o v et h e r e c o g n i t i o na c c u r a c yb e c a u s eo fi t sa d v a n t a g e s w ef l o wp r o c e s st h ep r o c e d u r eb ya p p l y i n gt h e b e s tf a c t o r s i ne v e r ys t e pt os v m h d rs o f t w a r es y s t e m t h i sp a p e rs h o w sas e r i e so f o p e r a t i o n so nh a n d w r i t t e nd i g i td a t a b a s em n i s ti n c l u d i n gp r e p r o c e s s i n go fd a t a , s c a l i n g ，t h e s e l e c t i o no fb e s tk e r n e lf u n c t i o n sa n dk e r n e lp a r a m e t e r s ，t r a i n i n ga n dt e s t i n g c o m p a r i n gt h e e x p e r i m e n tr e s u l t sw i t ht h o s eu s i n go t h e rt e c h n i q u e so nt h es a m ed a t a b a s ec a nv a l i d a t et h e e f f e c t i v e n e s so f s v mr e c o g n i t i o nm e t h o d ( 4 ) p r o p o s i n gv i r t u a ls a m p l e sm e t h o dt oi n t r o d u c ep r i o rk n o w l e d g e s u p p o r tv e c t o rs e ti sas u b s e to f t r a i n i n gs e t ，a n di tc a r ls t a n d sf o rt h ew h o l ei n f o r m a t i o no f t r a i n i n g s e to nt h ew h o l e ，t h a ti st o s a y , o n l yt h i s s u b s e tw o r k su p o nt h es o l v i n go f c l a s s i f i c a t i o np r o b l e m s t h e r e f o r e ，t h et e s t i n gp e r f o r m a n c eo ft r a i n i n ga n o t h e rs v mo nt h e s u p p o r tv e c t o rs e t ，w h i c hi sg e n e r a t e db yt r a i n i n gas v m ，i sn o tw o r s et h a nt h er e s u l to f t r a i n i n go nt h ew h o l et r a i n i n gs e t o nt h eb a s i so ft h es y s t e mo fv a l i d a t i n gt h ee f f e c t i v e n e s so fs u p p o r tv e c t o rm a c h i n ef o r h a n d w r i t t e nd i g i tr e c o g n i t i o n ，a b s t r a c t i n gt h es u p p o r tv e c t o rs e to ft r a i n i n gs e tu s i n gt h et h e o r y o fs o m et r a n s f o r m a t i o no fi n p u ti m a g ec a l l tc h a n g et h er e c o g n i t i o nr e s u l t s ，a n da p p l y i n g t r a n s l a t i o ni n v a r i a n c ei nt h i ss e tt og e n e r a t ea r t i f i c i a ls u p p o r tv e c t o r s i nt h ee n d ，w ec a ng e ta v i r t u a ls a m p l es e tt h a ti sf i v et i m e so ft h eo r i g i n a ls u p p o r tv e c t o rs e ta d d i n gt h eu n c h a n g e d s u p p o r tv e c t o r s t h e nr e t r a i n i n gt h ev i r t u a ls a m p l e sa n dt e s t i n gt h et e s ts e tu s i n gt h em o d e lg e n e r a t e db y r e t r a i n i n g t h r o u g hc o m p a r i n gt h er e s u l t sw i t ht h o s eo fv a l i d a t i n gt h ee f f e c t i v e n e s so fs v m c l a s s i f i c a t i o nm e t h o d ，w ec a nf i n dt h a tt h ev i r t u a ls a m p l e sm e t h o di m p r o v e st h ea c c u r a c yo f h a n d w r i t t e nd i g i tr e c o g n i t i o nb a s e do ns u p p o r tv e c t o rm a c h i n ee f f e c t i v e l y , a n dt h er e s u l ti s v e r yg o o d k e y w o r d s ： s u p p o r tv e c t o rm a c h i n e ；h a n d w r i t t e nd i g i tr e c o g n i t i o n ；m u l t i c l a s sc l a s s i f i c a t i o n ； p r i o rk n o w l e d g e ；s v m - h d r c ：l a s s i f i e a t i o n ：t p 3 9 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：冥蚋 导师签字 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：关翻 球 导师签字： 学位论文作者签名：关切 卧 导师签字： 签字日期：2 0 06 年手月，7 日 签字日期：z 。午，月， 朐 九匕人 2 山东师范大学硕士学位论文 1 1 研究背景 第一章绪论 1 1 1 手写数字识别技术的含义 手写数字识别( h a n d w r i t t e nd i g i tr e c o g n i t i o n ) 是光学字符识别技术的一个分支，是模 式识别学科的一个传统研究领域。主要研究如何利用电子计算机自动辨认手写在纸张上 的阿拉伯数字。手写数字识别分为脱机手写数字识别和联机手写数字识别。本文主要讨 论脱机手写数字的识别。 随着信息化的发展，手写数字识别的应用日益广泛，研究高识别率、零误识率和低拒 识率的高速识别算法具有重要意义。 1 1 2 手写数字识别技术的理论价值 由于手写数字识别本身的特点，对它的研究有重要的理论价值： ( 1 ) 阿拉伯数字是唯一被世界各国通用的符号，对手写体数字识别的研究基本上与文 化背景无关，各地的研究工作者基于同一平台开展工作，有利于研究的比较和探讨。 ( 2 ) 手写数字识别应用广泛，如邮政编码自动识别，税表系统和银行支票自动处理等。 这些工作以前需要大量的手工录入，投入的人力物力较多，劳动强度较大。手写数字识 别的研究适应了无纸化办公的需要，能大大提高工作效率。 ( 3 ) 由于数字类别只有1 0 个，较其他字符识别率较高，可用于验证新的理论和做深入 的分析研究。许多机器学习和模式识别领域的新理论和算法都是先用手写数字识别进行 检验，验证理论的有效性，然后才应用到更复杂的领域当中。这方面的典型例子就是人 工神经网络和支持向量机( s u p p o r t v e c t o rm a c h i n e ) 【i 。 ( 4 ) 手写数字的识别方法很容易推广到其它一些相关问题，如对英文之类拼音文字的 识别。事实上，很多学者就是把数字和英文字母的识别放在一起研究的。 1 1 3 手写数字识别技术的难点 数字的类别只有l o 种，笔划简单，其识别问题似乎不是很困难。但事实上，一些测 试结果表明，数字的正确识别率并不如印刷体汉字识别率高，甚至也不如联机手写体汉 字识别率高，而只仅仅优于脱机手写体汉字识别。这其中的主要原因是： ( 1 ) 数字笔划简单，其笔划差别相对较小，字形相差不大，使得准确区分某些数字相当 山东师范大学硕士学位论文 困难； ( 2 ) 数字虽然只有1 0 种，且笔划简单，但同一数字写法千差万别，全世界各个国家各 个地区的人都在用，其书写上带有明显的区域特性，很难做出可以兼顾世界各种写法的、 识别率极高的通用性数字识别系统。 虽然目前国内外对脱机手写数字识别的研究已经取得了很大的成就，但是仍然存在两 大难点： 一是识别精度需要达到更高的水平。手写数字识别没有上下文，数据中的每一个数据 都至关重要。而数字识别经常涉及金融、财会领域，其严格性更是不言而喻。因此，国 内外众多的学者都在为提高手写数字的识别率，降低误识率而努力。 二是识别的速度要达到很高的水平。数字识别的输入通常是很大量的数据，而高精度 与高速度是相互矛盾的，因此对识别算法提出了更高的要求。 1 2 手写数字识别的一般方法 1 2 1 识别流程 手写数字识别在学科上属于模式识别和人工智能的范畴。已有的研究针对手写数字识 别流程中的预处理，特征提取和分类器三个方面展开： ( 1 ) 预处理是为了得到更高的分类精度而事先对手写数字进行的处理，它包括图像增 强，二值化，细化和归一化等步骤。 ( 2 ) 原始数据的数量一般很大，样本处在一个高维空间中，通过映射或变换的方法可用 低维空间来表示，这个过程即为特征提取。 ( 3 ) 分类器主要用于字符的识别，如基于距离的分类器，神经网络分类器等。 1 2 2 识别方法 在过去的4 0 年中，学者们提出了许多手写数字识别技术。除本文将主要讨论的支持 向量机方法，简要介绍以下几种。 1 2 2 1 传统的识别方法【1 6 】 l - 统计模式识别方法 建立在统计数学，特别是贝叶斯决策理论基础上，通过模式紧致性、距离和相似性度 量等概念和假定，形成了统计决策方法的一系列结论。该方法是以同类模式具有相同属 性为基础的识别方法，对字符整体的分析。 用来描述事物属性的参量是特征，它可以通过对模式的多个样本的测量值进行统计分 析后按一定准则来提取。例如：在手写数字识别系统中，我们可以把每个数字的图形分 山东师范大学硕士学位论文 为若干小方块，然后统计每- - d , 方块中的黑像素，构成一个多维特征矢量，作为该数字 的特征。必须注意的是；在选择特征时，用于代表各类模式的特征应该把同类模式的各 个样本聚集在一起，而使不同类模式的样本尽量分开，以保证识别系统能具有足够高的 识别率。 统计特征通常包括点密度的测量、矩、特征区域等。 2 结构模式识别方法 对于一个复杂的模式，常常采用分解的方法将其划分成为若干较简单的子模式乃至基 元，通过对基元和子模式识别的综合集成来完成复杂模式的整体识别。结构模式识别方 法是以同类模式具有相似结构为基础的识别方法，从字符的轮廓或骨架上提取字符形状 的基本特征。 结构是指组成一个模式的基本单元( 简称基元) 之间的关系。例如，拼音文字的基元是 字母，若干个字母按一定规律组成一个单字，在识别某一个单字时，如果能判别组成这 个字的各个字母以及它们的( 结构) 关系，就可以识别这个字。基于这种原理，拼音文字 的识别系统中的“字典”应包括字母，以及由字母组成单字的规律。在对某一个单字进 行识别时，则应先提取构成这个单字的字母并分析它的结构，然后将它跟字典中所有已 知单字的基元及其结构关系逐个加以比较，就可以确定待识单字和哪一个已知单字属于 同类别。 结构模式识别一般分为训练过程和识别过程： ( 1 ) 训练过程就是用已知结构信息的模式作为训练样本，先识别出基元和它们之间的连 接关系，并用数字符号表示它们，然后用构造句子的方法来描述生成这些场景的过程， 并由此推断出生成该场景的一种文法规则。 ( 2 ) 识别过程就是对未知结构的模式进行基元识别及其相互关系分析，然后用训练过程 中获得的文法对其进行句法分析，如果它能被已知结构信息的文法分析出来，则该模式 具有与该文法相同的结构，否则就可判定不是这种结构。 与前面提到的统计特征对应，结构特征通常包括圆、端点、交叉点、笔划、轮廓等。 3 传统识别方式的优劣 统计法的优点是易于训练，抗干扰性能较好，而且使用统计特征的分类器，在给定的 训练集上能够得到相对较高的识别率；缺点是没有充分利用模式的结构特性。 结构法比较直观，能反映模式的结构特征，对图像畸变的抗干扰能力较强，在识别过 程中，能有效地结合几何和结构的知识，因此能够得到可靠性较高的识别结果：缺点是 基元的提取很不容易，各基元的关系也比较复杂，当存在干扰及噪声时抗干扰性能较差。 1 2 2 2 较新型的识别方法 i 逻辑特征法 特征的选择对一类模式识别问题来说是独一无二的，即在一类问题中只有1 个模式具 有1 种( 或某i 组合的) 逻辑特征，此方法建立了关于知识表示及组织，目标搜索及匹配 山东师范大学硕士学位论文 的完整体系；对需通过众多规则的推理达到识别目标的问题有很好的效果，但当样品有 缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。 2 模糊模式识别方法 在模式识别的过程中引入了模糊集的概念，由于隶属度函数作为样品与模板相似程度 的量度，故能反映整体的、主要的特性，模糊模式有相当程度的抗干扰与畸变，从而允 许样品有相当程度的干扰与畸变，但准确合理的隶属度函数往往难以建立。目前有学者 在研究，并将其引入神经网络方法形成模糊神经网络识别系统。 3 人工神经网络方法 就是使用人工神经网络方法实现模式识别。可处理一些环境信息十分复杂，背景知识 不清楚，推理规则不明确的问题，允许样品有较大的缺损、畸变。人工神经网络具有学 习和联想功能，在字符识别中主要采用基于b p 算法的多层感知器及多层卷积神经网络； 基于正规化方法构建的径向基网络；以及具有“拓扑保持”特性的自组织特征映射( 包括 学习矢量量化l v q ) 等。神经网络方法的缺点是其模型在不断丰富完善中，目前能识别的 模式类还不够多，神经网络方法允许样品有较大的缺损和畸变，其运行速度快，自适应 性能好，具有较高的分辨率。 事实上，s v m 方法即是一种人工神经网络方法。 4 其它方法 可以把问题域的先验知识或者启发式知识融入上述方法中。还可以对多种方法进行组 合( 集成) 等。 1 3 支持向量机在手写数字识别中的应用 1 3 1s v m 简介 支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 是f l j v a p n i k 于1 9 9 5 年提出的针对分类和回 归问题的统计学习理论，是在高维特征空间使用线性函数假设空间的学习系统，它由一 个来自最优化理论的学习算法训练，是一个准则性的并且强有力的方法。在它提出后的 若干年来，s v m 的性能在广泛的应用中胜过其他大多数的学习系统。由于s v m 方法具有 许多引人注目的优点和有前途的实验性能，越来越受重视，该技术已成为机器学习研究领 域中的热点，并取得很理想的效果，如人脸识别、手写体数字识别和网页分类等。 s v m 的主要思想可以概括为两点： ( 1 ) 它是针对线性可分情况进行分析的，对于线性不可分的情况，通过使用非线性映射 算法，将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得 高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能： ( 2 ) 它基于结构风险最小化理论在特征空间中构建最优分割超平面，使得学习器得到全 局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。 4 山东师范大学硕士学位论文 1 3 2s v m 的优点 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础上的， 根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度，a c c u r a c y ) 和学习 能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推广能力 ( g e n e r a l i z a t i o na b i l i t y ) 。它的主要优点有： ( 1 ) 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本 数趋于无穷大时的最优值； ( 2 ) 该算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点， 解决了在神经网络方法中无法避免的局部极值问题； ( 3 ) 该算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ，在高维 空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较 好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关； ( 4 ) 支持向量机能够自动识别出训练集中的一个子集，此子集基本上可以代表训练集中 的全部信息，也就是说只有这个子集对分类及回归问题的求解起作用，国内外的学者称 之为支持向量( s u p p o r tv e c t o r ) 。 ( 5 ) 在s v m 方法中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类 器、径向基函数( r a d i a lb a s i cf u n c t i o n 或r b f ) 方法、多层感知器网络等许多现有学习算 法，非常方便。 1 3 3s v m 在手写数字识别中的应用 支持向量机在现实世界应用的第一个例子即是手写字符识别问题。这个问题通常用作 分类器的测试平台，最初是为满足美国邮政服务局使用手写邮政编码自动分类邮件的需 要提出的。 b o s e r 和g u y o n 等人利用美国邮政标准手写数字库进行的对比实验，使用多项式核函 数对手写体阿拉伯数字进行了识别。实验结果表明，采用s v m 方法比采用其他神经网络 ( 具有5 层神经网络复杂机构) 算法效果好。支持向量机的出现为基于模式识别的字符识别 领域提供了新的工具，并成功应用于模式识别和函数拟合等领域，其表现优于已知的一 些神经网络方法。 s v m 的不同模型大多在两个数字集上做测试，这两个数字集分别由u s p s ( 美国邮政 服务局) 和n i s t ( 国家标准技术局) 公开提供。v a p n i k 和他的合作者在这两个数据集上做 过实验，用的都是最大间隔和软间隔分类器，主要是用多项式核，尽管s 形核不符合 m e r c e r 条件，也使用过。多类的s v m 也在这些数据上测试过。实验不仅将s v m 跟其他 分类器比较，还对不同类型的s v m 做了比较。它们显示出近似的性能，因此使用几乎相 同的支持向量，它们独立于所选择的核。 5 山东师范大学硕士学位论文 由于s v m 方法较好的理论基础和它在一些领域的应用中表现出来的优秀的推广性 能，近年来，许多关于s v m 方法的研究，包括算法本身的改进和算法的实际应用，都陆 续提了出来。尽管s v m 算法的性能在许多实际问题的应用中得到了验证，但是该算法在 计算上仍然存在一些问题有待解决，包括训练算法速度慢、算法复杂而难以实现以及预 测阶段运算量大等等。 1 4 本文的研究目的及内容 1 4 1 研究目的 本文在系统总结前人工作的基础上，从基于s v m 的手写数字识别的研究出发，重点 研究影响s v m 分类法性能的各种因子。通过实验和比较，从众多的因子中选出性能最佳 的几个因子，并根据它们对分类性能的影响程度从多个方面给出一个合理的评价。最后 把这一选择最佳因子的方法流程化，以期对实际手写数字识别起到一定的指导作用。并 在手写数字的识别过程中引入了先验知识，期望提高手写数字识别的精度。具体如下： ( 1 ) 在手写数字的预处理方面，本文对已有的几种手写数字的预处理方法进行简单介 绍，并对数据格式进行预处理。 ( 2 ) 在核函数与核参数的选择方面，对现有核函数与核参数进行分析比较，选择最适当 的核函数及核参数。 ( 3 ) 在多类分类方法的选择方面，介绍各种多类分类方法，总结它们的优缺点，并通过 实验对三种主要方法的训练时间和精度进行比较分析，为手写数字识别选择合适的多类 分类方法。 ( 4 ) 在训练算法方面，通过对现有的三种主流训练算法的分析比较，选择最优的训练算 法，并将其运用到手写数字识别当中。 ( 5 ) 通过以上各环节，选择最适合手写数字识别的各因子，构成一个流程化的数字识别 过程，期望能够验证s v m 分类法的有效性。 ( 6 ) 在基于s v m 的手写数字识别中使用引入先验知识的虚拟样本法，以期在验证s v m 分类法的有效性的基础上，能够提高手写数字识别的分类精度。 1 4 2 本文内容安排 本文内容安排如下： 第一章，介绍了手写数字识别的广阔应用前景和常用的识别方法，概括了目前支持向 量机技术在手写数字识别中的应用，指出了支持向量机用于手写数字识别的独特优势。 第二章，从统计学习理论入手，介绍了机器学习的基本问题、方法和核心内容，引出 支持向量机的理论基础一结构风险最小化原则；从数学的角度形式化地讨论支持向量机 6 山东师范大学硕士学位论文 的基本理论；对支持向量机的现有三种主流训练算法进行介绍和分析，重点介绍了序列 最小最优化算法。 第三章，介绍脱机手写数字识别的几个方面。对已有的几种手写数字的预处理方法进 行简单介绍，包括图像增强、二值化、细化和归一化；描述了几种多类分类方法并对之 进行优缺点分析；简单介绍了先验知识，并提出将先验知识引入到手写数字识别的过程 中。 第四章，针对基于支持向量机技术的手写数字识别的各个流程，开发了s v m h d r 手写数字识别软件系统。在具体数据库的基础上进行数据的预处理，核函数、核参数的 选择，多类分类方法的选择以及训练算法的选择操作，识别过程使用选择出的最佳因子。 该系统目的是验证s v m 分类法的有效性，并将本文提出的虚拟样本法应用到基于s v m 的手写数字识别过程中。最后，对程序结果进行分析讨论。 结束语对本文的工作进行了简要的总结，并对今后的工作进行了展望。 山东师范大学硕士学位论文 第二章统计学习理论与支持向量机 2 1 统计学习理论与支持向量机的关系 支持向量机理论是建立在统计学习理论( s t a t i s t i c a l l e a r n i n g t h e o r y ) 的基础之上的。传 统统计模式识别的方法都是在样本数目足够多的前提下进行研究的，所提出的各种方法 只有在样本数趋向无穷大时其性能才有理论上的保证。而实际应用中，样本数目通常是 有限的。统计学习理论为解决有限样本学习问题提供了一个统一的框架，可解决神经网 络结构选择问题、局部极小点问题等许多原来难以解决的问题。 支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 是一种在统计学习理论的基础上发展出的 通用学习方法，在解决非线性及高维模式识别问题中表现出许多特有的优势。它的理论 体系涵盖对象极为广泛，包括对偶表示、特征空间、学习理论、优化理论和算法等。近 年来，支持向量机的理论研究和算法实现都取得了突破性进展，开始成为克服“维数灾 难”和“过学习”等传统困难的有力手段。 2 2 机器学习的基本问题和方法 2 2 1 机器学习问题的表示 机器学习问题的目的是根据给定的训练样本，对某系统输入输出之间的依赖关系进行 估计，使它能够对未知作出尽可能准确的预测。其基本模型旧可用图2 1 表示。其中， 系统s 是我们研究的对象，它在给定一定输a x 下得到一定的输出y ，脚f 是我们所求的 学习机，输出为多。 图2 1 机器学习的基本模型 机器学习问题可以形式化地表示为：已知变量y 与输入x 之间存在一定的未知依赖关 系，即存在一个未知的联合概率f ( x ，y ) ，( x 和y 之间的确定性关系可以看作是一个特 例