手写体识别

分数:___________任课教师签字：___________课程作业学年学期：2017——2018学年第二学期课程名称：模式识别作业名称：作业七学生姓名：学号：提交时间：一、问题重述编写手写体识别大作业程序，要求做到以下几点内容：（1）针对“002手写数字数据集（1934+946）”数据包，进行手写体辨识。要求使用之前作业中用到的各类平均值为类中心的最小距离法、KNN近邻法（K取1,3,5）等等。（2）尝试使用神经网络方法进行辨识过程。（3）尝试70000个样本的数据集进行辨识，其中60000个用于训练，10000个用于测试。二、方法原理1、特征选择准则——类别可分性准则类别可分性准则值可以衡量样本的可分程度，取值越大表明样本可分程度越小，可以在一定程度上减小最终的分类错误率。类别可分性准则函数值J的计算公式如下所示11(xm)(xm)n(mm)(mm)icTwiiixccTBiiiiBwSSSJS其中C为类别数，m为总样本均值，mi为某一类均值，X表示样本数据。值得注意的是，并非J取值越大，最终的分类错误率就一定越小。最终的分类结果还与数据的分布特性以及分类器的选择有关。因此在J值取值只需满足条件即可，并非一定要取到最大值。2、特征提取方法——PCA降维当样本数据维数较高时，程序当中涉及到矩阵的运算会有很大负荷，算法的执行效率会大幅降低。因此在训练之前，需要将样本数据进行降维处理。主成分分析法（简称PCA）可以减少样本数据的相关性，突出差异性，是分类、辨识当中常用的降维方法。PCA可以将高维的数据降到任意低的维度上。但是为了保证样本数据不失真，一般要求PCA算法降维中，特征值占比不小于所有特征值之和75%。PCA算法的流程如下图所示。平移坐标系求自相关矩阵求特征值、特征向量特征值从大到小排列取前m个特征向量构成变换矩阵借助变换矩阵将n维转换为m维开始结束图1PCA降维算法流程图3、分类器分类器是整个分类环节当中的最后一项，也是分类过程的关键所在。分类器分为训练和测试两个环节，相应的算法有很多。常用的有基于类均值的最小距离法、KNN近邻法等基本线性分类算法，以及向量机、神经网络等更为复杂的算法。分类结束之后，计算训练错误率和测试错误率，以此为标准检验分类器算法的优劣以及整个分类过程的好坏。（1）基于类均值的最小距离法基于类均值的最小距离法首先计算每类训练样本的均值点，再分别计算每个均值点到测试样本的距离，测试样本归属于距其最近的均值点所在的数据类型。基于类均值的最小距离法算法流程如下：开始mean函数计算各类训练样本均值训练样本：Train测试样本：Studymin函数寻找训练样本中距离测试样本最近的均值点结束确定测试样本的分类结果图2基于类均值的最小距离法流程图（2）KNN近邻法KNN近邻法源自近邻法。KNN近邻法不再单单寻找距测试样本最近的一个点，而是寻找距其最近的K个点，然后按这K个点类型确定测试样本的类型。判断原则往往是少数服从多数。K的取值一般取技术。特别的当K取1，这种方法就是常见的最近邻法。KNN近邻法算法流程如下:开始Pdist2函数计算每个训练样本点到测试样本的距离训练样本：Train测试样本：Study借助tabulate(求元素出现频率)、sort(对向量进行排序)等函数求得训练样本中距测试样本最近的k个点结束根据K个点的类型，少数服从多数，给出测试样本的数据类型。图3KNN近邻法流程图（3）BP神经网络BP网络是一类多层的前馈神经网络。它的名字源于网络训练的过程中，调整网络的权值的算法是误差的反向传播的学习算法，即为BP学习算法。BP算法的结构简单，可调的参数多，训练的算法也多，而且操作性好。BP网是前向网络的核心部分算法，是神经网络中最精华、最完美的部分。本次作业利用BP神经网络算法对样本进行训练测试，并将结果与其他方法进行对比。三、处理流程本次数据处理的数据集为32*32的二值图，保存格式为文本格式。训练样本数为1934，每个数字大约有200个；测试样本数为926个，每个数字个数从80到120不等。整个手写体辨识过程可以分为以下四个阶段：数据采集特征生成特征选择与提取分类器图4手写体辨识过程1、数据采集本次作业所用到的数据为二值化后的文本文档，所以数据采集过程只需要将文档中的数据读取到工作空间即可。本阶段将训练样本和测试样本分别存到两个元胞数组的变量当中，每个元胞含有10个元胞元素，依次对应0~9；每个元胞元素中存放n*1024的矩阵，其中n代表该类数据的样本数，1024代表二值化后的点阵数。2、特征生成本阶段将原始数据进行处理，提取出16个特征元素。特征生成过程如下。将32*32的二值化矩阵平均分成16块，求出每块矩阵当中非零元素的个数，作为相应的特征元素。如，将下图所示的一组数据（类型为0）提取特征值后为[34325014301965308220374011]。0000000000000110000000000000000000000000000011111100000000000000000000000001111111110000000000000000000001111111111100000000000000000001111111111111100000000000000000001111111000111100000000000000000111111000000111000000000000000001111110000001110000000000000000111111000000011100000000000000001111110000000111100000000000000011111100000000011100000000000000111111000000000111000000000000001111100000000000111000000000000011111000000000001110000000000000011111000000000001110000000000000111110000000000011100000000000001111100000000000111000000000000111110000000000001110000000000001111100000000000011100000000000000111100000000000011100000000000001111000000000001111000000000000011110000000000011110000000000000111100000000001111100000000000000111100000000001111100000000000001111100000000111110000000000000011111000000011111100000000000000111110000001111110000000000000001111110001111111100000000000000000111111111111110000000000000000001111111111111000000000000000000001111111111000000000000000000000000111110000000000000图5一组类型为0的原始数据4等分4等分图6将二值均值分块过程3、特征选择与提取为了减小计算量需要对样本进行降维处理。降维方式选择PCA算法，在保证类别可分性准则值满足要求的条件下，特征值占比不小于75%即可。设n表示PCA处理后的维度。表11934与70000两个数据集PCA降维后不同维度下特征值占比和可分性准则PCA处理后的维度1934个样本的数据集70000个样本的数据集特征值占比（%）可分性准则值特征值占比（%）可分性准则值123.932.150424.570.9538243.932.166544.991.0704359.911.851460.020.7927468.871.622269.660.7709576.871.469577.500.7644682.671.307283.800.6956788.091.219788.930.6667890.791.199192.740.6298993.151.168195.460.60681095.321.124597.010.59411196.791.091597.940.58721297.921.070398.770.57981398.801.053999.310.57571499.421.041699.650.57281599.821.035399.930.5707161001.03161000.5700图71934样本集PCA降维后的特征值占比和可分性函数值00.511.522.5010203040506070809010012345678910111213141516类别可分性准则特征值占比/%降维后的维度1934样本集PCA降维后的特征值占比和可分性函数值特征值占比（%）类别可分性准则值图870000样本集PCA降维后的特征值占比和可分性函数值为了减少计算量，选择特征值占比大于75%维度最小的情况。因此针对1934数据集，利用PCA将其降成5维；针对70000数据集，也利用PCA降成5维。4、分类器将PCA降维后的数据（5维）和不进行PCA降维的数据（16维），分别利用基于类均值的最小距离法训练、KNN近邻法（K取1、3、5）、BP神经网络算法，对样本进行训练、测试，得到的错误率如下：表2分类错误率分类器1934样本集70000样本集PCA降维后原始数据PCA降维后原始数据训练测试训练测试训练测试训练测试最小距离0.22910.16810.16800.06550.39030.32280.32950.1739最近邻0.27180.11890.15860.03620.38320.25260.32190.12543NN00.175500.070800.316900.17315NN0.1670.10700.06550.01030.34410.34200.18670.2738BP网络0.10340.15430.02900.05070.21270.28030.10010.1690对分类结果以及之前的工作总结，如下：（1）当数据集规模变大时，各种算法的错误率会增加；（2）PCA降维后虽然会减小运算量，但是会增大分类错误率；（3）几种方法中，基于类均值的最小距离分类算法的效果相对最差，BP神经网络的分类效果相对最好。（4）对于基于类均值的最小距离法、KNN近邻法来说，训练错误率一般是略高于测试错误率的。（5）本作业次设计的分类器对于1934样本集分类效果比较令人满意，但是对于70000样本集分类效果很差，针对大样本数据，算法需要改进00.20.40.60.811.2010203040506070809010012345678910111213141516类别可分性准则特征值占比/%降维后的维度70000样本集PCA降维的特征值占比和可分性函数特征值占比（%）类别可分性准则值四、代码附录：1、数据采集程序：%手写体识别：1934训练样本+946个测试样本%每个txt文件对应32*32的矩阵，转换为一条行向量。clearallcloseall;clc;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%保存训练数据PathTrain=[cd,'\trainingDigits\'];TrainList=dir([PathTrain,'*.txt']);TrainData_Original=cell(