基于支持向量机的手写体数字识别系统设计.doc

第 26 卷 第 6 期计算机工程与设计Computer Engineering and Design2005 年 6 月June 2005V ol . 26N o. 6基于支持向量机的手写体数字识别系统设计蒙庚祥,方景龙( 杭州电子工业学院 软件学院，浙江 杭州 310018)要：数字识别是光学字符识别技术里发展比较早的一种技术，是 OCR 的一个分支。数字识别又分为手写数字识别摘和非手写数字识别，提到的手写数字识别是指脱机手写数字识别。支持向量机是近几年来模式识别领域中的一个新技术，它被广泛应用到文字识别、人脸识别等应用中，是模式识别领域中的研究热点，把支持向量机技术应用到手写数 字识别系统中，以期提高识别系统的性能。关键词：支持向量机； 数字识别； 系统设计中图法分类号：TP391.4文献标识码：A文章编号：1000-7024 (2005) 06-1592-03System design of recognition of handwritten digits by support vector machineMENG Geng-xiang ,FANG Jing-long(School of Software, Hangzhou Institute of Electronics and Engineering, Hangzhou 310018, China)Abstract：Digits recognition is studied earlier than others in char recognition, it is a branch of OCR. Digits recognition is made up of handwritten digits recognition and non-handwritten digits recognition. The handwritten digits recognition that is studied is off-line hand- written digits recognition. Support vector machine is a new technic in pattern recognition in recent years. SVM is used widely in different recognition and it is a hot topic in recognition. SVM is used in the system of handwritten digits recognition, whose goal is to improve the performance of the system .Key words：support vector machine; digits recognition; system design数方法，较好地解决了模式分类器复杂性和推广性之间的矛盾，因而也引起了模式识别领域学者的极大关注。1引言手写数字识别在经过过去几十年的研究取得了很大的成功，识别率在 90%以上，但是作为数字识别它需要更高的识别 率，因为数字识别的错误所带来的影响比文字识别等其他识 别所带来的影响更大，尤其在金融领域数字识别的错误所带 来的后果更是不可低估 1。手写体数字识别是多年来的研究 热点，也是模式识别领域中最成功的应用之一，有很高的商业 价值。目前，市场上也出现了一些手写体数字识别产品，在许 多实用系统(如邮政编码自动识别系统、银行支票自动处理系 统等)中有广泛的应用。显然，高性能的手写体数字识别器有 助于提高实用系统的整体性能，然而现在还没有哪个手写体 数字识别器达到完美的识别性能。因此，进一步提高手写数 字识别系统的识别性能是每一位从事数字识别工作者的追求 目标。学习理论是一种研究有限样本情况下机器学习性质和规 律的理论。在这一理论下发展出的一种通用的模式分类器支持向量机，由于与传统的模式识别方法相比具有推广 能力强、能保证全局最优等优点，这使得支持向量机技术在手 写数字识别系统中有很好的应用前景，因而引起了国内外学 者的极大兴趣。支持向量机通过结构风险最小化准则和核函2支持向量机技术支持向量机(SupportVectorMachine-SVM) 简称 SVM，是统计学习理论中最新的内容，也是最实用的部分。支持向量机 是一种新的机器学习技术，由 Vapnik 和他的同事于 1995 年提 出2。支持向量机方法是建立在统计学习理论的 VC 维理论和 结构风险最小化原理基础上的，根据有限的样本信息在模型 的复杂性（即对特定训练样本的学习精度）和学习能力（即无 错误的识别任意样本的能力）之间寻求最佳折衷，以期获得最 好的推广能力。基于统计学习理论的坚实基础，SVM 有很强的学习能力 和较好的泛化性能。SVM 学习用优化方法得到的结果是全局 最优解，不会产生传统方法中的过学习和局部最小等问题。 SVM 学习结果为支持向量集，通常是学习样本集的一小部分， 支持向量集充分体现了整个样本集的属性。对于样本集 1,，它是线性的或非线性的。关于线,性情况，已有较多介绍这里主要介绍非线性情况。在非线性可分的情况下，可使用一个非线性函数 把数据映射到一个高收稿日期：2 004-05-19。作者简介：蒙庚祥 （19 79-），男，广西桂平人，硕士，研究方向为人工智能。,(+ 1, =1,2,3,（2）多项式内积函数：径向基内积函数(RBF)：sigmoid 内积函数：, = , =exp（14）+1 （15）2考虑到可能存在一些样本不能被决策面正确分类,因此引2 2+入松弛变量0 , 决策面的约束变为：（16）, =tanh(+ 1 , =1,2,3,（3）按照优化理论的 KuhnTucker 定理, 在鞍点, 对偶变量与约束的乘积为 0,即：最佳的决策面应使两类样本到决策面最小的距离为最大,而此最小距离为| 最小化：+ |/=1/。分类问题变成（17）+ 1+ =0, =1,2, ,由式(17) 可以看出, 远离决策面的输入样本所对应的 必定为 0, 而非 0 的 所对应的样本完全确定了决策面, 因此称为 支持向量。对应于 (0, )的样本,有min 1 .（4）+01 ,2 s.t+ =1（18）=1,2,3,+ =1下面先介绍结构风险最小化理论与式（4）的关系关于两类分类问题，结论是对指示函数集中的所有函数根据此式可计算出值, 向量的值可由式(10)中对的偏导数公式求得：( 包括使经验风险最小的函数)，经验风险之间以至少以1 的概率满足如下关系：和实际风险（19）=支持向量判别函数 f(x)可直接表示为：2（20）=sgn,+ln+ 1 ln4支持向量（5）+3支持向量机的训练算法其中 h 是函数集的 VC 维,n 是样本数。可以简单地表示为：+分类判别函数：=sgn（6）, +支持向量它表明，在有限训练样本下, 学习机器的 VC 维越高( 复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能 的差别越大。因此，要使 VC 维尽量小以缩小置信范围，才能 取得较小的实际风险，即对未来样本有较好的推广性。 对于一个规范超平面子集来说，其 VC 维满足不等式：对于这个二次规划问题，经典的解法有积极方集法、对偶方法、内点算法等，但是当训练样本增多时，这些算法便面临 着维数灾，或者由于内存的限制，而导致无法训练，无法应用 SVM 进行模式分类和函数估计。所以如何训练大训练集的 SVM 便成为 SVM 实际应用的瓶颈问题。min2 2 ,+1（7）在当前的支持向量机的训练算法中有 SVM 分解算法、其中 为向量空间的维数，R 为覆盖所有向量的超球体半径，Kerrthi 的近邻算法、张学工的 CSVM、Scholkopf 的 v-SVM 分类器、J.A.KSuykens 提出的最小二乘法支持向量机 LSSVM,Ming- HsuanYang 提出的训练支持向量机的几何方法, SOR (Successi- veOverrelaxation)以及多类时的 SVM 算法和 Platt 提出的 SMO 算法。下面主要介绍序贯最小优化 (sequential minimal optimiza- tion, 简称 SMO)算法，该算法是目前解决大量数据下支持向量 机训练问题的一种十分有效的方法。SMO 是 Platt 提出来解 决大训练样本的问题的。该算法工作集中只有两个样本，其，由（7）式可知可以通过最小化| |使 VC 置信度最小，| |即（6）式中最小。如果固定经验风险，最小化期望风险的问题就变成最小化|小化式子：| 的问题，因此在支持向量机中就是最min 1（8）. +2=1上式第 1 项使两类样本到决策面最小的距离为最大,以提高泛化能力, 第 2 项使错分为最少,常数对两者做出折中。 为求解这个优化问题,引入拉格郎日函数：优点是针对两个样本的二次规划问题可以有解析解的形式，= 1, , , ,+1+从而避免了多样本情形下的数值解不稳定及耗时问题，同时也不需要大的矩阵存储空间,特别适合稀疏样本，其工作集的 选择也别具特色，不是传统的最陡下降法，而是启发式。通过 两个嵌套的循环来寻找待优化的样本变量。在外环中寻找违2=1=1=1（9）其中0 , 函数的极值应满足条件：0,（10）=0,=0,=0背 KKT 最优条件的样本，然后在内环中再选择另一个样本，由此可得到优化问题的对偶形式, 最大化函数：完成一次优化。再循环，进行下一次优化，直到全部样本都满足最优条件。SMO 算法主要耗时在最优条件的判断上，所以 应寻找最合理即计算代价最低的最优条件判别式，同时对常 用的参数进行缓存。SMO 训练算法是当前研究比较多的方法，因此也出现了（11）（12）（13）=max=1 =1s.t. 0=0, =1, ,=1式 (11) 涉及到高维特征空间的点积运算很多 SMO 的改进算法。基本设计思路4手写数字识别现状手写数字识别的一般原理为：首先把数字图像经过预处理，然后得到的数据进行特征提取或不用进行特征提取就可 以直接输入识别器进行识别得到结果。手写数字识别的预处 理通常包括数字图像的二值化处理、细化处理等步骤。数字 图像的二值化处理是将上一步骤所得到的灰度数字图像转化 为二值数字图像，即在数字图像中区分出字符和背景。二值 化处理方法很多，但考虑到大量数字识别的需要，一般只能采 用一维的阈值分割算法进行处理以获得二值化数字图像，预 处理技术在当前比较成熟。在数字识别领域研究重点是特征提取和识别器设计。在 特征提取方面，过去的 40 年中，人们想出了很多办法获取手 写字符的关键特征。这些手段分两大类：全局分析和结构分 析。对前者，我们可以使用模板匹配、像素密度、矩、特征点、 数学变换等技术。这类的特征常常和统计分类方法一起使用。 对后者，多半需要从字符的轮廓或骨架上提取字符形状的基 本特征，包括圈、端点、节点、弧、突起、凹陷、笔画等。经过多 年的研究研究者提出了各种各样识别的方法，比如有一种基 于轮廓信息进行结构分析的手写体数字识别方法6，实验中取 得了较好的识别结果。进入 20 世纪 90 年代以来，人工神经网络（ANN）技术发 展十分迅速，它具有模拟人类部分形象思维的能力，为模式识 别开辟了新的途径，成了模拟人工智能的一种重要方法。在 自由手写体数字识别方面，许多研究工作者使用 ANN 技术做 了不少尝试，有了较大的进展。在众多应用 BP 网研究字符识 别的方法中，可归纳为两种结构形式。第 1 种是只采用一个 一定规模的神经网络完成字符识别。第 2 种是采用两个或两 个以上的神经网络相结合的多系统结构形式，它力求做到各 个子系统间互补性强，从而不必过分追求单个神经网络子系 统的高识别率，却使多子系统结构达到较好的识别效果。除 此之外，近期也提出某些复杂的结构模型，如模块结构、分层 结构等形式的网络。近年来支持向量机已经成为模式识别领域的研究热点， 因此一些学者也开始把支持向量机技术应用到手写数字识别 中，例如有研究者把支持向量机技术与神经网络技术结合，构 成一个复合的识别器来识别手写体数字，在实验中该系统取 得了很好的识别效果。但是，支持向量机应用到手写数字识别中也出现了很多 有待解决的问题，例如训练时间过长、识别速度慢等问题，解 决这些问题还有待进一步研究。图 1 基于支持向量机的手写数字识别系统特征提取对于手写数字图像，虽然没有人脸图像那样有更多的维 数，但是像6464维、3232维对于手写数字识别系统来说已经 算多了，如果直接拿去进行训练识别将会大大影响系统的识 别速度、效率等，因此进行特征提取还是有必要的。在本系统中采用基于核的主成分分析方法 5 进行特征提 取。基于核的主成分分析方法是传统主成分分析 (PCA) 方法5.11的推广。对于样本集 1, , 主成分方向是矩阵 =1= 1的特征向量。对 x 进行非线性变换，可得到=1，其特征向量 v 就是原样本集的非线性主成分方向, 满足= 。将每个样本与该式内积, 得： = , = 1,（21），将它代入(30), .可以证明,特征向量 v 可以写成 =式中,并定义矩阵：= =()=（22）,为矩阵的第 i 行第 j 列个元素，可以得到：= （23）其中 =量 ，即，从矩阵 K 的特征向量 即可求出 的特征向1,空间的主成分方向，通过对式（32）求解，即可获得所要求的特征值和特征向量。对于原空间中的任意向量 x, 它在变换空间中的主成分是 在主成分方向 v 上的投影, 即：（24）=,=1显然, 这里得到的非线性主成分方法只需在原空间中计算用作内积的核函数, 。基于核的主成分分析方法进行特征提取中要采用核函数，实验中可采用各种核函数进行实验比较它们的效果。支持向量机识别器手写数字识别一共有 10 类样本，是属于一个多分类问题。 那么对于像手写数字识别这样的多类分别问题，支持向量机 又怎样处理呢？实验中可以将多个支持向量机的二类分类器 组合起来构成一个多类分类器。构造一个多类分类器的原理是这样的：对于一个 N 类分 类问题，我们需要构造 N 个基于支持向量机的二类分类器，每 一个二类分类器将 N 类中的每一类与其它 N-1 类区分开来， 识别的时候，只要把输入样本依次输入到 N 个分类器，比较 N 个分类器的识别结果，就会得到最终的识别结果4。在本系统 中有 10 类，那就要设计 10 个二类分类器，比如分类器 0 将 0 与 1、2、3、4、5、6、7、8、9 数字分开。实验时将输入向量输入到10 个分类器中进行分类，比较 10 个分类器的分类参数性能判 断输入样本是属于哪个数字，如图 2 所示。(下转第 1598 页)5.25基于支持向量机手写数字识别系统设计基于支持向量机的手写数字识别系统(如图 1 所示) 主要 是利用支持向量机在识别领域良好的识别性能。对于一个完 整的识别系统应包括从图像采集到得出识别结果的过程，由 于本系统主要是用来检验支持向量机在手写数字识别系统中 的应用，所以在本系统中图像采集、样本预处理等就不在提 及，主要是在特征提取方法和识别器设计上下功夫。测试样本数字图像预处理特征提取识别器结果识别器训练特征提取预处理数字图像训练样本最终保持和增强竞争优势，从而更好地实现企业的战略目标，获得最大的利益和持续性发展。炼化企业信息系统方案模型 如图 9 所示。行了比较全面和实际的分析之后，在此基础上，根据“效益驱动、整体规划、分步实施、重点突破”的 CIMS 系统建设原则，能够为企业提供一个实现绩效管理和绩效改进，并且适合企业自身特点，满足其实际生产和管理需要的信息系统设计方 案。参考文献:企业绩效管理1Folkert Herlyn. Computerization benefits for refineries and the MITE masterplanning C. SINOPEC - IBM Petroleum Confe- rence Beijing-November,1998.Danilo Belletti. SINOPEC-IBM petroleum conferenceC.Bei-jing,1998-10.蔡建明. 石油石化企业的挑战和机遇C.北京:SAP 石油天然 气行业发展战略研讨会,2002.SAP 公司. MySAP 产品生命周期管理C. 北京:SAP 石油天然气行业发展战略研讨会,2002.Laudon Kenth C, Jane P Laudon. Management information sys- tem: Organization and technologyM. 4th Edition,New Jersey, USA:Prentice Hall,1996.龙晓云. 绩效优异评估标准M.北京:中国标准出版社, 2002.企业计划/预算目标234图 9石化企业信息系统方案模型58结论信息系统的建设对于企业增强竞争力、提高生产和工作效率是至关重要的，但是企业信息化的庞大投资能否获得回6(上接第 1594 页)而且要有良好的识别速度和识别效率，只有这样才能在实际系统中得到广泛的应用。基于支持向量机的手写数字识别系 统要想在实际中得到应用就必须解决这两方面的问题。支持 向量机有很强的学习能力和较好的泛化性能，因此系统在识 别性能上是比较好的，但是在识别速度、识别效率上就有待