（运筹学与控制论专业论文）基于支持向量机的手写数字识别的研究.pdf

硕士学位论文 m a s t e r st h e s i s t h er e s e a r c ho nh a n d w r i t t e n n u m e r a l r e c o g n i t i o nb a s e d o ns v m at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to f t h e r e q u i r e m e n t fo yt h em s d e g r e ei nn a t u r a ls c i e n c e b y w u d o n g l i a n g p o s t g r a d u a t ep r o g r a m s c h o o lo fm a t h e m a t i c sa n ds t a t i s t i c s c e n t r a lc h i n an o r m a l u n i v e r s i t y s u p e r v i s o r ：z h a od o n g f a n g a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e m a y 2 0 11 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法 律结果由本人承担。 作者签名： 晏拆家 日期：仞i 年5 - 月 学位论文版权使用授权书 尹 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并向国家有关部门或机构 送交论文的复印件和电子版，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部 分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位论文在解 密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者张吴拆象 日期册年 月彳日 翱弛脚 日期m “锣月7 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的学位论文提 交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规定享受相关权益。屋 塞论塞握銮卮澄卮；旦圭生i 旦= 生；旦三生蕉查： 作者船吴橡录 日期吲1 年”7 日 导师签名： 日期： l o l l 年厂月7 日 ：0 硕士学位论文 m a s t e r st h e s i s 摘要 随着科学技术的快速发展，计算机处理速度越来越快，用计算机解决现实生活 中的问题是一个热点的研究方向。由于手写数字的识别存在于邮件分类、文献检索、 银行票据等很多领域中，因此手写数字识别是模式识别中的一个较为重要的研究方 向，如何提高识别正确率及其效率也是大家奋斗的目标。 本文分四步进行研究手写数字识别。 第一步，相对人脸等其它对象样本向量的维数而言，手写数字样本的向量维数 是较小的，因此直接采用支持向量机+ 多分类算法进行训练和识别。本文选择的多 分类算法有1 ( 1 ( 1 ) 算法、二叉树、二分法和投票法。通过实验结果的分析，得出二 分法和投票法相对较优，但是不足之处在于，要得到高的识别正确率必须要很多训 练样本，这样就必须花很长时间进行训练样本。 第二步，采用p c a 进行降维，可以减少训练样本的时间。但是降维之后，识别 准确率没有得到提高，这可能与所选的样本和样本向量的数据有关。 第三步，从减少训练样本数入手，考虑到训练样本间的相似性，采用相似形态 配对想法来挑选训练样本。结果挑选出6 3 9 个训练样本，对1 0 0 个待测样本进行识 别，识别准确率达到了8 7 ，这个结果对比于第一步的结果有了个明显的提升。 第四步，继续延续第三步的想法，即从减少训练样本入手，通过聚类分析得到 新的训练样本，再进行实验。最后得出结论，即选用相似距离+ 层次聚类中的中间 距离算法+ 多分类的投票算法之后，当挑选出1 8 0 0 个训练样本时，识别正确率达到 9 7 ，这样保证了高的识别正确率，并且大大降低训练样本的时间。 关键词：支持向量机主成分分析聚类分析 ： 硕士学位论文 m a s t e r st h e s i s a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , t h ep r o c e s s i n g s p e e do f c o m p u t e ri sf a s t e ra n df a s t e r u s i n gc o m p u t e r st os o l v er e a ll i f ep r o b l e m si sah o tr e s e a r c h d i r e c t i o n h a n d w r i t t e nn u m e r a lr e c o g n i t i o ne x i s t s i nm a n ya r e a s ，s u c ha st h ee - m a i l c l a s s i f i c a t i o n , t h ed o c u m e n tr e t r i e v a la n dt h eb a n kn o t e s ，s o ，h a n d w r i t t e nn u m e r a l r e c o g n i t i o ni sam o r ei m p o r t a n tr e s e a r c hd i r e c t i o no fp a t t e r nr e c o g n i t i o n h o wt oi m p r o v e t h er e c o g n i t i o n sa c c u r a c ya n de f f i c i e n c yi sag o a lo fu s i nt h i sa r t i c l e ，t h e r ea r ef o u rs t e p sf o rr e s e a r c h i n gh a n d w r i t t e nn u m e r a lr e c o g n i t i o n t h ef i r s ts t e p ，r e l a t i v et ot h ef a c ea n do t h e ro b j e c t s ，t h ev e c t o r sd i m e n s i o no f h a n d w r i t t e nn u m e r a l si ss m a l l e r , t h e r e f o r e ，w ec a nt r a i na n dr e c o g n i z et h es a m p l e sb y u s i n gs u p p o r tv e c t o rm a c h i n ea n dm u l t i c l a s s i f i c a t i o na l g o r i t h md i r e c t l y i nt h i sp a p e r , w ec h o o s ef o u rm u l t i - c l a s s i f i c a t i o na l g o r i t h m sw h i c ha r et h e1 一( 1 ( - 1 ) a l g o r i t h m ，t h e b i n a r yt r e ea l g o r i t h m ，t h ed i c h o t o m ya n dt h ev o t i n gm e t h o d t h r o u g ht h ea n a l y s i so f e x p e r i m e n t a lr e s u l t s ，w ec a ns e et h a tt h ed i c h o t o m ya n dt h ev o t i n gm e t h o da r es u p e r i o r r e l a t i v e l y h o w e v e r , t h ei m p e r f e c t i o ni st h a t ，i fw ew a n tt og e tt h eh i g hr e c o g n i t i o nr a t e ， w eh a v et on e e dal o to ft r a i n i n gs a m p l e s ，s o ，w em u s tt a k eal o n gt i m ef o rt r a i n i n g s a m p l e s t h es e c o n ds t e p ，w ec a nr e d u c et h ed i m e n s i o nb yu s i n gp c a ，w h i c hc a nr e d u c et h e t i m e o ft r a i n i n gs a m p l e s h o w e v e r , b yr e d u c i n gt h ed i m e n s i o n , t h e r e c o g n i t i o n s a c c u r a c yd on o ti m p r o v e ，t h i sr e s u l tm a yb er e l a t e dt os a m p l e sa n dt h ed a t ao fs a m p l e v e c t o r s t h et h i r ds t e p ，w em a yb e g i nw i t hr e d u c i n gt h en u m b e ro ft r a i n i n gs a m p l e s ，c o n s i d e r i n g s i m i l a rs h a p e ，w ec a nc h o o s et h es a m p l e sb yt h ei d e ao fs i m i l a rs h a p e - p a i r i n g a tl a s t6 3 9t r a i n i n g s a m p l e sa r es e l e c t e d ，a n dr e c o g n i z e10 0s a m p l e sb yu s i n gt h e6 3 9t r a i n i n gs a m p l e s ，t h er e s u l ti s 8 7 ，t h i sr e s u l th a sas i g n i f i c a n ti m p r o v e m e n tr e l a f i v i n gt ot h ef i r s ts t e p t h ef o u r t hs t e p ，w ee x t e n dt h ei d e ao ft h et h i r ds t e p ，b u tn e wt r a i n i n gs a m p l e sa r e o b t a i n e db yc l u s t e r i n ga n a l y s i s a tl a s tw es e e ，i fw ec h o o c et h es i m i l a r i t yd i s t a n c e + t h e m i d d l ed i s t a n c e a l g o r i t h mo fh i e r a r c h i c a lc l u s t e r i n g + t h ev o t i n gm e t h o d ，t h eh e r e c o g n i t i o n sa c c u r a c yw i l la r r i v ea t9 7 w h e nt h en u m b e ro ft r a i n i n gs a m p l e si s18 0 0 t h i sr e s u l te n s u r e st h eh i g h r e c o g n i t i o n sa c c u r a c y ，a n dg r e a t l yr e d u c et h et i m eo f t r a i n i n gs a m p l e s k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ；p r i n c i p a lc o m p o n e n ta n a l y s i s ； c l u s t e ra n a l y s i s i i ： 硕士擘位论文 m a s t e r sr j h e s i s 目录 摘要 a b s t r a c t 第一章绪论 i i i l 1 1 模式识别的发展简介1 1 2 图像识别的步骤1 1 3 手写数字的识别。1 1 3 1 研究目的1 1 3 2 常见的研究方法2 1 4 本论文的主要工作2 第二章基于支持向量机对手写数字的识别3 2 1 支持向量机的背景介绍3 2 2 支持向量机的理论介绍3 2 3 手写数字的识别过程5 2 3 1 本章手写数字识别的步骤5 2 3 2 鉴于四个多分类想法，得到四个分类算法6 2 3 3 综合分析16 第三章基于主成分分析法的支持向量机对手写数字的识别。1 8 3 1 主成分分析法的原理1 8 3 2 实验设计及结果1 9 3 3 结果分析2 0 第四章动态寻找训练样本策略的探索。 4 1 动态寻找训练样本策略思想2 l 4 2 动态寻找训练样本策略算法2 2 4 3 实验设计及结果分析2 3 第五章基于聚类分析的训练样本选择。2 5 5 1 聚类分析的理论知识2 5 5 1 1 距离聚类的概念2 5 5 1 2 相似性测度和聚类准则。2 5 5 2 层次聚类法2 6 5 2 1 层次聚类法的算法描述【1 1 2 6 、 0 ，接下来我们要做的是把b 和w 看做变量，来 求l a g r a n g e 函数在约束条件下的极小值。 把( 4 ) 分别对w 和b 求偏微分并令它们等于0 ，就可以把原问题转化为如下 这种较为简单的对偶问题；在约束条件 w = q 只毛 f = l 只q = o ( 5 ) ( 6 ) 口j 0 ，f _ l ，2 ，行 ( 7 ) 之下对口，求下列函数的最大值： m a xq ( 口) = q 一去口j q m 乃( 一誓，) ( 8 ) i = l ，y = l 若口。为最优解，则矿= a l y , x i i = l 最后求解上述问题所得到的最优分类函数是 厂( x ) = s g n ( w x ) + 6 。) ( 9 ) 其中s g n ( ) 是符号函数。 若k 是特征空间的一个内积函数：( 薯) 矽( x ) = k ( ，x ) 从而最优的分类函数为 f - s g n 2 , y ，k ( x j x ) + 6 ( 1 0 ) 从上面的过程可以明白，s v m 的基本思想是通过内积函数进行非线性变换，将输 入空间变换到一个高维的空间，然后再求取最优的分类面心1 。 其中k 函数称之为核函数，常用的4 种核函数瞳3 如下： ( 1 ) 线性函数( d o t ) ：k ( 薯，x ，) = 薯x ， ( 2 ) 多项式函数( p o l y n o m i a l ) ：k ( x ，) = 5 ( x ，薯) + 1 r ( 3 ) 高斯函数( r b f ) ：k ( x ，x j ) = e x p - 6 l x - x , 1 2 】 ( 4 ) 感知机函数( s i g m o i d ) ：k ( x ，薯) = t a n h ( 8 ( x 葺) + c ) 4 、_ 硕士学位论文 m a s t e r s1 h e s i s 2 3 手写数字的识别过程 手写数字是从o 到9 这十种数字的手写体，再通过扫描成对应的图片，本文中 手写数字图片对应的像素是2 4 x 2 4 ，再通过二值变换之后成为了二值化的矩阵，如 fq l lq ，2 4l 果把每个图片x , j - 应的像素通过写成矩阵形式为a ( i ，) = i m m l l 口2 4 l l 口2 a ，m j 2 4 x m i 表示的是数字的类别，j 表示的是第i 类数字的第j 个样本。矩阵a 中的任一元素口卅； 等于o 或l 。本文中手写数字数据由华中师范大学陈增照老师提供。如图1 是处理 过的图片： 图1 2 3 1 本章手写数字识别的步骤 1 数据处理。考虑到每个样本是矩阵的形式，给计算和训练带来麻烦，根据需要， 必须把2 4 x 2 4 的矩阵化为1 5 7 6 的矩阵，让每一行表示一个样本。 2 选择训练样本和测试样本。本章采用逐步增加训练样本的方法来进行，目的是 想考察样本数与识别的准确率及程序实现所花的时间三者之间的关系。 3 选择分类工具，常见的分类方法很多，本章采用的是上述的支持向量机作为分 类的工具。 4 把多类问题化成多个两类问题。由于支持向量机只能对两类进行分类，对于多 类而言，要想把多类分为单一的类，就必须把多类问题化成多个两类问题，再逐一 识别。怎么把多类问题化为多个两类问题呢? 针对本章中的1 0 类样本，有如下想 法5 1 蚴： ( 1 ) 1 一( k - 1 ) 想法描述：我们可以把第一类训练样本和剩下九类训练样本分成 两大类a 和b ，通过识别发现待测样本分在a 类，就可以判断待测样本是第一类， 否则，就在b 类。如果第一次没有得到结果，接下来把第二类训练样本和剩余九类 训练样本分成两大类c 和d ，再进行判断，依次下去，最多可以通过九次判断就可以 确定待测样本属于哪一类。 ( 2 ) 二叉树想法描述：类似想法一，我们可以把第一类训练样本和剩余九类训 练样本分成两大类a 和b ，通过识别如果发现待测样本在a 类，就可以判断待测样 5 硕士学位论文 m a s t e r st h e s i $ 本是在第一类，退出判断；否则就是在b 类。接下来把b 类分成两大类c 和d ， 其中c 类是第二类样本，其它八类就是d 类，再对待测样本进行判断，依次下去， 最多也是通过九次判断就可以确定待测样本属于哪一类。 ( 3 ) 二分法想法描述啼3 ：把1 0 类训练样本折中分成两类a 和b ，其中a 类含第 一类到第五类这五类训练样本，b 类含第六类到第十类这五类训练样本。接下来判 断待测样本属于哪类，如果属于a 类，再把a 类折中分成两类c 和d 类，再判 断待测样本属于哪一类，依次下去最多通过4 次判断就可以确定待测样本属于哪一 类。 ( 4 ) 投票法想法描述瞄1 ：把1 0 类训练样本按照样本类别分成1 0 类，在1 0 类训练 样本任选两个作为被选的样本进行训练，再对待测样本进行识别，这样进行c 二= 4 5 次识别，再对所得的结果分别投票，看哪类投票数最多，待测样本就判定为哪一类。 2 3 2 鉴于四个多分类想法，得到四个分类算法 2 3 2 1 基于1 ( k 1 ) 的分类算法一 s t e p l ： 初始化。对训练样本从o 到9 按照列进行排序得到x ，初始化待测样本 x x ，i = l ，i 1 5 ； s t e p 2 ： 在x 中对每类样本( o ，1 ，2 ，9 ) ，取每类样本5 0 i 个得到新的训练样 本x ；，k = l ，k = 待测样本x x 的行数； s t e p 3 ：对待测样本x x ( k ) 进行分类确认，其中x x ( k ) 表示x x 中第k 个待测样 本；令j _ o ，要求，8 ； s t e p 4 ： 调用分类予函数y = f e n l e i l ( x ，x x ( k ) ，j ) ， 如果y = ox x ( k ) 在第j 类，k = k + 1 ，转向s t e p 3 否则j = j + l ，转向s t e p 4 如果y 等于0 且j 等于8x x ( k ) 在第9 类，k = k + l ，如果转向s t e p 3 s t e p 5 ：对x x ( k ) ( k = 1 ，2 ，3 ，l ) 所得到分类的结果与x x ( k ) 真实的类别进行比对算出 识别正确率； s t e p 6 ：i = i + l ，如果i 1 5 ，转向s t e p 2 , 否则程序终止。 其中算法一中调用的分类子函数是以上述1 ( k 1 ) 想法实现的。其调用的子 函数名为y = f e n t e i l ( x , ，x x ( k ) ，j ) ，表示把置分成两类，j 类和非j 类，在使用支持向 量机，对x x ( k ) 进行分类。 如果x x ( k ) 分到j 类，返回y = o ： 否则返回y = 1 ； 2 3 2 2 算法一对应的实验设计及结果和分析 6 硕士学位论文 m a s t e r st h e s i s 本次实验所选的训练样本数从5 0 0 个开始，即每类样本5 0 个，然后每类样本依 次增加5 0 个，直n i ) l l 练样本总数达到7 5 0 0 个，待测样本数为1 0 0 个，所选的支持 向量机核函数是m a t l a b 自带的二次核函数是“q u a d r a t i c ，对于多分类算法，采 用上述算法一，程序在m a t l a b 7 5 的版本上运行，计算机c p u 为e 2 1 8 0 。结果如下： 表2 1基于1 ( k 1 ) 的分类算法一实现的结果 i样本数正确率时间( s ) l5 0 0 4 7 1 1 0 21 0 0 05 0 2 6 6 315 0 05 6 4 9 6 42 0 0 06 8 6 8 4 52 5 0 07 3 9 3 8 63 0 0 07 6 1 2 2 9 73 5 0 08 0 1 5 6 1 84 0 0 0 8 7 1 9 4 8 94 5 0 09 0 2 3 4 2 1 05 0 0 09 2 2 8 2 5 1 15 5 0 09 2 4 9 1 4 1 26 0 0 09 2 4 6 6 2 1 36 5 0 0 9 4 5 2 5 4 1 4 7 0 0 09 4 5 5 6 1 1 57 5 0 09 5 6 2 2 6 上述数据用图给出如下： 图2 算法一下的训练样本数与识别正确率的关系 7 ：0 硕士学位论文 m a s t e r st h e s i s 图3 算法下的训练样本数与程序实现所需时间的关系 结果分析：图2 、3 分别给出了样本数量与准确率、样本数量与程序实现所需时 间的关系。理论上训练样本越多越能充分的给出样本的特征，就能得到越精确的识 别，如图2 可知，在多分类识别选择1 ( k 1 ) 算法时，随着样本的依次增加识别 的准确率也是逐渐提高的，其趋势是准确率趋于1 0 0 ，这也是符合理论上要求。 如图3 可知，随着样本数的增加，程序实现所花的时间整体上来说是不断增多的， 但有特别情况，当训练样本数从5 5 0 0 个增加到6 0 0 0 个时，所需的时间反而从4 9 1 4 s 降到了4 6 6 2 s ，这可能与所选的算法有关，新增加的训练样本可能减少了支持向量 机算法运行的迭代次数，从而使得分类的速度得到提高。 2 3 2 3 基于二叉树的分类算法二 s t e p l ：初始化。对训练样本从0 到9 按照列进行排序得到x ，初始化待测样本x x ， i = l ，i 1 5 ； s t e p 2 ：在x 中对每类样本( o ，l ，2 ，9 ) ，取每类样本5 0 f 个得到新的训练样本 z ，k = l ，k - 待测样本x x 的行数； s t e p 3 ：对x x ( k ) 进行分类，其中x x c k ) 表示x x 中第k 个待测样本； 令j = o ，要求，8 ； s t e p 4 ：调用分类子函数y = f e n l e i 2 ( x ，a t r ( k ) ，歹) ， 如果y = 0 x x ( k ) 在第j 类，k = k + l ，转向s t e p 3 ； 否则 置= 五一第j 类的训练样本，j = j + l ，转向s t e p 4 ； 8 ，霄、 ：一， 硕士学位论文 m a s t e r st h e s i s 如果y 等于0 且j 等于8x x ( k ) 在第9 类，k = k + 1 ，转向s t e p 3 ； s t e p 5 ：对x x ( k ) ( k = l ，2 ，3 ，l ) 所得到分类的结果与x x ( k ) 真实的类别进行比对， 算出识别正确率； s t e p 6 ：i = i + l ，如果i 1 5 ，转向s t e p 2 ；否则程序终止； 其中调用的分类子函数y = f e n l e i 2 ( x ，x x ( k ) ，) 与算法一中的调用的分类算法 一样。 2 3 2 4 算法二对应的实验设计及结果和分析 本次实验所选的训练样本数从5 0 0 个开始，即每类样本5 0 个，然后每类样本依 次增加5 0 个，直到训练样本总数达到7 5 0 0 个，待测样本数为1 0 0 个，所选的支持 向量机核函数是m a t l a b 自带的二次核函数是“q u a d r a t i c ，对于多分类算法，采 用上述算法二，程序在m a t l a b 7 5 的版本上运行，计算机c p u 为e 2 1 8 0 。结果如下： 表2 2 基于二叉树的分类算法二实现的结果 训练样本数j 下确率时间( s ) 1 2 15 0 04 7 1 1 9 21 0 0 05 0 2 9 5 31 5 0 0 5 6 5 5 7 4 2 0 0 06 8 7 6 9 52 5 0 07 3 1 0 6 0 63 0 0 07 6 1 4 2 6 73 5 0 08 0 1 7 9 7 84 0 0 08 7 2 2 7 0 94 5 0 0 9 0 2 7 2 3 1 0 5 0 0 09 2 3 2 9 7 1 1 5 5 0 09 2 4 8 8 4 1 26 0 0 09 2 4 2 0 2 1 36 5 0 09 4 4 9 3 9 1 47 0 0 09 4 5 2 3 1 1 5 7 5 0 09 5 7 4 0 1 上述数据用图给出如下： 9 硕士学位论文 m a s t e r st h e s i s 瓣 嚣 目 最 髫 训练样本数与识别准确率的关系 5 0 01 0 0 01 5 0 02 0 0 0 2 5 0 0 3 0 0 03 5 0 0 4 0 0 0 4 5 0 05 0 0 05 5 0 06 0 0 06 5 0 07 0 0 07 5 0 0 训练样本数( 个) 图4 算法二下的训练样本数与识别正确率的关系 8 0 0 0 7 0 0 0 6 0 0 0 ，、5 0 0 0 厘4 0 0 0 茁 3 0 0 0 2 0 0 0 l o o o 0 训练样本数与程序实现所需时间的关系 5 0 01 0 0 01 5 0 02 0 0 0 2 5 0 0 3 0 0 03 5 0 04 0 0 04 5 0 05 0 0 05 5 0 06 0 0 0 6 5 0 07 0 0 0 7 5 0 0 训练样本数( 个) 图5 算法二下的训练样本数与程序实现所需时间的关系 结果分析：图4 、5 分别给出了样本数量与准确率、样本数量与程序实现所需 时间的关系。理论上训练样本越多越能充分的给出样本的特征，就能得到越精确的 识别，如图4 可知，在多分类识别选择二叉树算法时，随着样本的依次增加识别的 准确率也是逐渐提高的，其趋势是准确率趋于1 0 0 ，这也是符合理论上要求。如 图5 可知，随着样本数的增加，程序实现所花的时间整体上来说是不断增多的，但 有特别情况，当训练样本数从5 5 0 0 个增加到6 0 0 0 个时，所需的时间反而从4 8 8 4 s 降到了4 2 0 2 s ，这可能与所选的算法有关，新增加的训练样本可能减少了支持向量 机算法运行的迭代次数，从而使得分类的速度得到提高。 1 0 傩喘帆嗍嘣傩嘴嘴嘴嘴嘴 o 9 8 7 6 5 4 3 2 1 硕士学位论文 m a s t e r st h e s i s 2 3 2 5 基于二分法的分类算法三 s t e p l ：初始化。对训练样本从0 到9 按照列进行排序得到x ，初始化待测样本 x x ，i = 1 ，i 1 5 ； s t e p 2 在x 中对每类样本( o ，1 ，2 ，9 ) ，取每类样本5 0 i 个得到新的训练 样本x ，k = l ，k - - - 待测样本x x 的行数； s t e p 3 ：对x x ( k ) 进行分类，其中x x ( k ) 表示x x 中第k 个待测样 本，s = 1 0 ，k l = 5 0 i ； s t e p 4 ：i i = l ，要求i i 5 。 s t e p 5 ：调用分类子函数【m ，刀】= f e n l e i 3 ( x f ，x x ( k ) ，s ，k 1 ) ， 如果m = o 且s 2s = 对( s 2 ) 向上取整； 否则如果m = l 且s 2s = 对( s 2 ) 下取整； 如果m = 0 且占2 置= 取置得上半部分； 否则如果m = l 且s 2 五= 取x ，得下半部分； 如果n 的值在0 到9 之问取值记录x x ( k ) 是第n 类，k = k + l ，转向s t e p 3 ； 否则i i = i i + l ，转向s t e p 4 ； s t e p 6 ：对x x ( k ) ( k = l ，2 ，3 ，l ) 所得到分类的结果与x x ( k ) 真实的类别进行比 对，算出识别正确率； s t e p 7 ：i - - - i + l ，如果i 1 5 ，转向s t e p 2 ；否则程序终止。 其中调用的分类子函数是采用二分法的思想实现的，其函数名为： 【m ，z 】= f e n l e i 3 ( x j ，x x ( k ) ，j ，k 1 ) ，s 记录着训练样本中的类别数，k l 记录着训练样本 中每一类的训练样本数，m 返回的值表示把x x ( k ) 分到对应的部分，如果m = 0 表示 把x x ( k ) 分到了置对应的上半部分，如果m = l 表示把x x ( k ) 分到了z 对应的下半 部分，n 返回的是0 到9 或1 1 这些数，如果n = 1 1 表示二分法没有结束，要继续调 用上面的分类子函数，如果n 返回的是0 到9 之间的数，就表示把x x ( k ) 识别为第 n 类。 2 3 2 6 算法三对应的实验设计及结果和分析 本次实验所选的训练样本数从5 0 0 个开始，即每类样本5 0 个，然后每类样本 依次增加5 0 个，直到训练样本总数达到7 5 0 0 个，待测样本数为1 0 0 个，所选的支 持向量机核函数是m a t l a b 自带的二次核函数是“q u a d r a t i c ，对于多分类算法， 采用上述算法三，程序在m a t l a b 7 5 的版本上运行，计算机c p u 为e 2 18 0 。结果如 下： ： 硕士学位论文 m a s t e r st h e s i $ 表2 3 基于二分法的分类算法三实现的结果 样本数正确率时间( s ) l 15 0 05 0 4 9 2 1 0 0 0 5 6 1 18 3 1 5 0 0 6 9 2 1 6 4 2 0 0 06 9 3 1 6 52 5 0 07 l 4 2 8 63 0 0 07 5 6 4 1 73 5 0 07 5 7 9 8 84 0 0 07 9 9 8 8 9 4 5 0 08 4 1 18 2 1 05 0 0 09 l 1 5 6 9 1 l 5 5 0 09 2 2 3 2 2 1 26 0 0 09 2 2 6 2 5 1 36 5 0 09 0 3 1 3 7 1 47 0 0 09 3 3 8 8 8 1 5 7 5 0 09 5 4 4 5 6 上述数据用图给出如下： 图6 算法三下的训练样本数与识别正确率的关系 1 2 ： 硕士学位论文 m a s t e r st h e s l s o 、- ， 厘 营 星 离 林 棒 骥 训练样本数与程序实现所需的关系 5 0 01 0 0 01 5 0 02 0 0 02 5 0 03 0 0 03 5 0 04 0 0 04 5 0 05 0 0 05 5 0 06 0 0 06 5 0 07 0 0 07 5 0 0 训练样奉数( 个) 图7 算法三下的训练样本数与程序实现所需时间的关系 结果分析t 图6 、7 分别给出了样本数量与准确率、样本数量与程序实现所需 时间的关系。图6 中图像的走势整体是上升的，但是，当样本数从6 0 0 0 个上升到 6 5 0 0 个的时候，识别准确率却出现了微弱的下降，这说明此时增加的五百个样本数 影响了识别。这里可以举个例子，如果突然增加是3 又像8 的训练样本，则识别正 确率就会突然下降。由于手写不同的数字间有很多相似性，所以给识别带来了困难。 遇到增加样本数反而降低了识别率的情况时，我们可以去掉新增加的那些训练样 本，换其它的训练样本。 2 3 2 7 基于投票法的分类算法四： s t e p l ：初始化。对训练样本从0 到9 按照列进行排序得到x ，初始化待测样 x x ，i = l ，i 1 5 ； s t e p 2 在x 中对每类样本( o ，1 ，2 ，9 ) ，取每类样本5 0 i 个得到新的训练 样本z ，k = l ，k _ 待测样本x x 的行数； s t e p 3 - m ( j ) = 0 ，( ，= 1 ，2 ，l ，1 0 ) m ( j ) 表示对第j 类的计数； s t e p 4 ：把训练样本置按照o 到9 这十类分开成m o ，m ，m 2 ，l ，鸠，其中m 表 示对训练样本i ； s t e p 5 ：任取坂，m l ，鸩，l ，鸠中的两个作y g i ) t l 练样本，调用训练函数调和识别 函数分别为： s v m s t r u c t = s v m t r a i n ( m i ，哆) c l a s s e s = c l a s s i f y ( s v m s t r u c t ，朋( 七) ) o 的钙弱筋加坫m 5 ： 硕士学位论文 m a s t e r st h e s i s s t e p 6 ：对x x ( k ) 的类别进行投票：m ( c l a s s e s + 1 ) = m ( c l a s s e s + 1 ) + 1 ； s t e p 7 - n n ( k ) = 投票后，最多的票所对应的类，n n ( k ) 是对厨( 七) 分类的记录； s t e p 8 ：k = - k + l ，如果k - 待测样本x x 的行数，转向s t e p 3 ；否则进行下一步； s t e p 9 对x x ( k ) ( 七= 1 ，2 ，3 ，l ) 所得到分类的结果与x x ( k ) 真实的类别进行比 对，算出识别正确率； s t e p l 0 ：i = i + l ，如果i 1 5 ，转向s t e p 2 ；否则程序终止。 2 3 2 8 算法四对应的实验设计及结果和分析 本次实验所选的训练样本数从5 0 0 个开始，即每类样本5 0 个，然后每类样本 依次增加5 0 个，直n i ) e i 练样本总数达到7 5 0 0 个，待测样本数为1 0 0 个，所选的支 持向量机核函数是m a t l a b 自带的二次核函数是“q u a d r a t i c ，对于多分类算法， 采用上述算法四，程序在m a t l a b 7 5 的版本上运行，计算机c p u 为e 2 1 8 0 。结果如 下： 表2 4 基于投票法的分类算法实现的结果 训练样本数正确率时间( s ) 1 2 15 0 05 9 18 0 210 0 06 4 3 7 8 31 5 0 06 7 5 8 0 42 0 0 07 1 8 0 3 52 5 0 07 l 1 0 4 2 63 0 0 07 4 1 2 1 8 73 5 0 07 8 1 4 4 3 84 0 0 0 8 3 17 0 9 9 4 5 0 08 7 1 9 7 6 1 05 0 0 09 0 2 2 8 5 1 15 5 0 09 2 2 6 2 5 1 26 0 0 09 2 2 9 5 4 1 36 5 0 09 4 3 3 1 3 1 4 7 0 0 09 7 3 6 5 4 1 5 7 5 0 0 9 8 4 0 4 8 1 4 | 酉i n ： 石甄士学位论丈 m a s t e r st h e s i s 上述数据用图给出如下： 图8 算法四下的训练样本数与识别正确率的关系 图9 算法四下的训练样本数与程序实现所需时间的关系 结果分析：图8 、9 分别给出样本数量与识别正确率、程序实现所需时间的关 系。图8 中图像的走势是上升的，识别率正确率从5 9 开始，到9 8 结束，其趋 势是准确率趋于1 0 0 ，这是符合理论上要求。图9 中时间是随着样本的增加而增 加，没有出现异常点。 1 5 ，7 7 、 ：0 硕士学位论丈 m a s t e r st h e s i s 2 3 3 综合分析 图l o 四个算法的识别准确率的比较 图1 1 四种算法实现所需时间的比较 接下来，进行纵向的比较，图1 0 是把四个表的识别准确率放在个图里进行比 较，发现算法一和算法二在识别正确率上是相同的，算法三的识别正确率与算法一、 二的识别j 下确率相比较是忽高忽低，最大的一次相差为1 3 ，最后都达到9 5 的识 别正确率。算法四开始时识别率比前三个算法的识别准确率高，随着样本数的增加， 到后来识别率达到了9 8 ，在四个算法里，算法四在最后得到的结果是最好的。如 果不考虑程序执行的时间，就考虑识别率的话，当训练样本数越大，其识别正确率 1 6 硕士学位论文 m a s t e r st h e s i s 是越高，并且趋于l ，这样可以通过该实验说明用支持向量机来实现就手写数字的 识别已经达到了一个很高的识别水平。图1 1 是把四个表里的程序执行的时间放在 一个图里，通过图像可以明显的看到用算法三所花的时间比用一、二两个算法少， 最大相差达到2 9 4 5 s ，算法四所花的时间增长的比较缓慢，开始比算法三所花的时 间多，当训练样本数达到6 5 0 0 之后，所花的时间比算法三要低。 综合上述四个算法所得的结果分析，可以得出如下几点： ( 1 ) 运用算法一和算法二的支持向量机在执行过程中不管是识别正确率还是 程序执行的时间，都具有相似性，但就程序实现所所花的时间过多；运用算法三的 支持向量机在执行过程中识别正确率得到了保证，同时大大降低了程序执行的时 间，因此选用二分法作为支持向量机的多分类算法是较优的；算法四一直可以保持 较高水平的识别，程序实现所花时间与二分法相当，因此投票法作为支持向量机的 多分类算法也是较优的。 ( 2 ) 当训练样本数取7 5 0 0 个的时候，前三种算法求得的结果均为识别正确率 为9 5 ，这说明1 0 0 个待测样本中有5 个不能正确识别。分别找出在使用前三种不 同算法后