手写数字体识别的支持向量机方法.doc

基于支持向量机的手写数字识别第一章 绪论1.1研究背景 1.1.1数字识别概述阿拉伯数字是人类文明的标志之一，也是人们进行交流与沟通的主要媒介。数字作为世界经济发展的信息载体，展示了世界各族人民的思维和认知方式。在我们的日常生活中，每天都要进行大量的文档处理工作，税单、银行支票、汇款单、信用卡账单的处理，以及邮局信函的分检等等，如何利用计算机字符识别和文档处理技术，使人们从这些繁重的手工劳动中解放出来已成为一个迫切需要解决的问题。计算机文字识别，是计算机和人之间进行信息沟通的一座桥梁。计算机文字识别一直是图像识别领域中十分活跃的研究课题。它被认为是典型的图像识别应用研究课题。随着信息时代的到来，如何实习数字识别的自动识别与处理将直接关系到我国信息事业的发展。数字识别是一种类别的识别问题，在理论和技术上都具有较大的研究价值。其中，数字识别特别是手写数字识别因其需要较高的识别精度和较快的识别速度被视为识别领域中“最难的领域”，成为国内外研究的热点。1.1.2数字识别的问题和困难 数字的类别只有十种，笔划也比较简单，其识别问题似乎不是很困难，但事实上，一些测试结果表明，数字的正确识别率并不如印刷体汉字识别正确率高，甚至也不如连机手写提汉字识别率高。这其中的主要原因如下：第一， 手写数字字形相差不大，比如“1”和“7”，“3”和“ 8”很相似，使得准确区分某些数字相当困难；第二， 在实际应用中，对数字识别单字识别正确率的要求要比文字要苛刻得多。这是因为，数字没有上下文关系，每个单字的识别都事关重要，而且数字识别经常涉及的财会、金融领域其严格性使其准确率要求更高。此外，大批量数据处理对系统速度又有相当的要求，许多理论上很完美但速度过低的方法行不通的。因此研究高性能的数字识别算法是一个有相当的挑战性的任务。第二章 数字识别技术 2.1数字识别的方法 数字识别是图像内容识别的一个应用领域，且有被识别的数较少，只有十个数字，阿拉伯数字笔画少的特点。所以手写阿拉伯数字的识别采用的方法相对于人脸识别、汉字识别等应用领域来说可以采用更为灵活的方法，例如基于神经网络的BP学习算法、SVM方法等。但无论使用那种方法，都需要通过基本的图像处理技术来对图像进行预处理，才能获得这些方法的输入信息。下面我们来介绍这两种方法。2.1.1神经网络的BP学习算法神经网络是模拟人脑内部结构，在模拟推理、自动学习等方面接近人脑的自组织和并行处理的数学模型，包括输入层、隐含层、输出层。其优点之一是，不依赖于对象，通过学习将输入、输出以权值的方式编码，把它们联系起来。神经网络在数据挖掘中的优势是：噪声数据的强承受能力，对数据分类的高准确性，以及可用各种算法进行规则提取。因此，常常借助神经网络来进行数据挖掘。BP学习过程可以描述如下： 1）工作信号正向传播。输入信号从输入层经隐单元，传向输出层，在输出端产生输出信号，这是工作信号的正向传播。在信号的向前传递过程中网络的权值是固定不变的，每一层神经元的状态只影响下一层神经元的状态。如果在输出层不能得到期望的输出，则转入误差信号方向传播。2）误差信号方向传播。网络的实际输出与期望输出之间的差值即为误差信号，误差信号由输出端开始逐层向前传播，这是误差信号的反向传播。在误差信号方向传播的过程中，网络的权值由误差反馈进行调节。通过权值的不断修正使网络的实际输出更接近期望输出。- 13 -工作信号误差信号图为多层感知器的一部分，其中有两种信号：一是用实线表示的工作信号，工作信号正向传播；二是用虚线表示的误差信号，误差信号反向传播。2.1.2 SVM算法SVM方法定义最优线性超平面，并把寻找最优线性超平面的算法归结为求解一个凸规划问题。进而基于Mercer核展开定理，通过非线性映射，把样本空间映射到一个高维乃至于无穷维的特征空间（Hilbert空间），使在特征空间中可以应用线性学习机的方法解决样本空间中的高度非线性分类和回归等问题。 简单地说就是升维和线性化。升维，即是把样本向高维空间做映射，一般只会增加计算的复杂性，甚至会引起“维数灾”，因而人们很少问津。但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间却可以通过一个线性超平面实现线性划分（或回归）。SVM的线性化是在变换后的高维空间中应用解线性问题的方法来进行计算。在高维特征空间中得到的是问题的线性解，但与之相对应的却是原来样本空间中问题的非线性解。 一般的升维都会带来计算的复杂化。SVM方法巧妙地解决了这两个难题：由于应用了核函数的展开定理，所以根本不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾”。这一切要归功于核的展开和计算理论。因此人们又称SVM方法为基于核的一种方法。核方法研究是比SVM更为广泛和深刻的研究领域。 2.2支持向量机与多层前向网络区别（1） 采用径向基核函数时，支持向量机实现的是一种径向基核函数分类器，径向基核函数的中心位置以及中心数目、网络的权值都是又训练过程中自动确定，而传统RBF网络对这些参数的确定则依赖于经验知识。（2） 当采用SIGMOID 函数作为核函数时，支持向量机实现的是一种多层感知齐神经网络。应用SVM 方法，隐结点的权值都是在设计（训练）的过程中自动确定的.而多层感知器的隐结点数目是需要依赖经验知识事先确定的.此外，在多层感知器中，模型复杂性的控制是通过使特征数目尽量小，也就是使隐层神经元数目尽可能小来实现的，而支持向量即与此不同，它是通过控制与维树无关的模型复杂性来实现学习机器的设计。（3） 与径向函数网络和多层感知器相比，支持向量机避免了在前者的设计中经常使用的启发式结构，它不依赖于设计者的经验知识；而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部极小值，也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。第三章 支持向量机原理如图2-1所示为二维两类线性可分模式，图中的圈和三角分别表示两类的训练样本，H维把两类没有错误的分开的分类线，、分别为过各类样本中离分类线最近的点且平行于分类线的直线，那么和之间的距离即为两类的分类间隔。所谓最优分类线就是要求分类线不但能将两类无错误的分开，而且要使两类的分类间隔最大。前者是保证经验风险最小（为0），后者实际上是为了使置信范围最小，从而使实际风险最小，这是对结构风险最小化原则的具体实现，推广到高维空间，最优分类线就成为最优超平面。 图2-1 最优分类示意图margin设训练样本输入为 ，i=1，.,l，对应的希望输出为，其中+1和-1分别代表两类的类别标识，假设分类面方程为。为使分类面对所有样本正确分类并且具备分类间隔，就要就它满足如下约束： （3-1）可以计算出，分类间隔为 （3-2）现在的目标就是在服从约束式（3-4）的条件下最大化分类间隔，这可以通过最小化的方法来实现。那么，求解最优超平面问题就可以表示成如下的约束优化问题：即在条件式（3-4）的约束下，最小函数： （3-3）为了解决这个约束最优化问题，引入式（3-6）所示的lagrange函数： （3-4）其中，为lagrange系数，现在的问题就是关于w和b求L的最小值。把式（3-6）分别对w和b求偏微分并令其等于0，就可以把上述问题转化为一个较简单的“对偶”问题：求L的最大值，其约束条件为L关于w和b的梯度均为0以及。即在约束条件： (3-5a) ，i=1，,l (3-5b)下对求解下列函数的最大值: （3-6） 如果为最优解,那么 （3-7）即最优超平面的权系数向量是训练样本向量的线性结合。求解上述问题后得到的最优分类函数是： （3-8）此时约束条件就变为： (3-9)当分类出现错误时, 大于0,因此, 是训练集中错分样本数的上界.这样就需要在目标函数中为分类误差分配一个额外的代价函数,即引入错误惩罚分量。所以，现在目标函数就变为 (3-10)其中C0是一个指定的常数,它控制对错分样本的惩罚程度,C越大表示对错误的惩罚越重.现在的问题就是在式(3-11)的约束条件下求式(3-12)所示函数的极小植,即折中考虑最大分类间隔和最少错分样本,就得到了线性不可分情况下的最优超平面。第四章 数字识别的支持向量机的方法4.1识别过程第一步：训练样本的采集和处理。对训练样本进行采集，先准备0到9的几个字数字字符，格式为“*.bmp”,每个字符有10张，这样就得到了100张训练样本，然后进行图像处理，将样本图像读入之后，进行灰度化，得到灰度图像，再对得到的灰度图像进行二值化，为此，我们令灰度值大于200的为1，小于200的记为0，得到样本的二值图像，再把数字所在的区域提取出来，最后对提取出来的区域进行归一化，将其变为5*7的矩阵形式，得到训练样本的特征矢量。第二步：数字识别的训练：得到训练样本的特征矢量后，再构造训练样本对应的标号，构造10*10矩阵，向量每一列表为1，则表示判别为相应类，其他为-1，例如2字符，则这行向量表示为（-1 -1 1 -1 -1 -1 -1 -1 -1 -1），再选择核函数类型，训练SVM，。第三步：待识别数字进行识别：由Mousedraw程序从手写板读入手写数字作为待测样本，首先同样对其进行图像处理，将其化为5*7的待测特征矢量，再应用svcoutputi对其进行判别，实验结果如下图所示：待识别数字3 数字识别结果待识别数字6数字识别结果待识别数字4数字识别结果4.2识别结果分析从上述结果可以看出，当手写字体比较正式的情况下，其识别效果较好，但当手写字比较随意时，识别效果比较差，这存在两方面因素，一种是由于训练样本的数目太少，不能得到比较好的效果，另一种是当SVM识别多类模式时，其判别比较复杂，而在此只考虑了比较简单的一种情况。4.3支持向量机与BP网络结果比较（1）支持向量机是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优解,而多层前向网络针对的是大量的样本,其目标是样本趋于无穷大时的最优解。（2）支持向量机最终将转化为一个二次型寻优问题，从理论上说，得到的将是全局最优点，解决了在神经网络方法无法避免的局部极值问题；而多层前向网络BP有时会导致极值问题。（3）支持向量机能够自动识别出训练集中的一个子集，此子集基本上可以代表训练集中的全部信息，也就是说只有这个子集对分类及回归问题的求解起作用，而多层前向网络BP算法导致极值问题。（4）与多层感知器相比，支持向量机避免了在前者的设计中经常使用的启发式结构，它不依赖于设计者的经验知识；而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部极小值，也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。第五章 结论支持向量机解决二分类问