基于K-近邻的手写数字识别

基于K-近邻的手写数字识别1K-近邻算法概述K-近邻是用训练实例点形成的单元对特征空间进行划分，然后对于一个测试实例，计算它和所有的已知类别实例点的距离，然后取k个离它最近的实例点通过某种分类决策规则来决定它属于哪种类别。K-近邻使用的模型有三个基本的要素，首先是距离的度量，就是采用什么样的距离来反应两个实例点之间的相似度，在本次实验中采用的是欧式距离。除此之外还有Minkowski距离等。其次，是K值得选择，就是选取离实例点最近的多少个训练实例来决定输入实例的类别。如果K值过小或过大多会对分类结果产生很大的影响。最后，是分类决策规则的制定，大多数情况下采用的是多数表决的规则，即由输入实例的k个邻近的训练实例中的多数决定输入实例的类别。K-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高，空间复杂度高。2准备手写数字数据在本次实验中，构造的系统只能识别0-9的数字。它是由0和1构成的32*32的图片，所以收集的数据就是将图片转为文本格式的数据。这里有两种数据，一种是用来训练的数据，另一种是用来测试的，分别在trainingDigits和testDigits文件中。训练样本大约有2000个，测试样本大约有900个。每个文件命名上也是按照一定的规则来的，文件名的开始的数字就是这个数字真实的标签。然后在测试的时候将其提取出来和分类器所分类别进行比对，就可以得到分类器的错误率。3算法实现3.1k-近邻算法本次实验采用python实现所需要的功能，在编写算法之前，需要安装python中的一些包，比如numpy和scipy，以及画图的matplotlib，画出图形可以便于分析数据。Knn分类的算法实现如下，inX是输入实例，dataSet是已经知道类别的训练数据集，labels是数据集中每个实例对应的类别，k是一个设置值。#核心算法defclassify0(inX,dataSet,labels,k):#shape函数.看数据集有多少行dataSetSize=dataSet.shape[0]#复制并和训练集做差diffMat=tile(inX,(dataSetSize,1))-dataSet#平方sqDiffMat=diffMat**2#求和sqDistances=sqDiffMat.sum(axis=1)#开方distances=sqDistances**0.5#排序sortedDistIndicies=distances.argsort()classCount={}#标签作为键，每种标签的个数作为值foriinrange(k):voteLabel=labels[sortedDistIndicies[i]]#get函数，如果没有这个voteLabel对应的值就初始化为0classCount[voteLabel]=classCount.get(voteLabel,0)+1#itemgertter方法中为1，说明是按照classCount中的第二个值排序的，就是“值”。然后逆序，从大到小sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)returnsortedClassCount[0][0]上面的函数实现的算法首先是将输入实例复制为和数据集一样大小的矩阵，然后计算这个实例和每个数据集中实例的欧式距离。最后进行排序，找出前K个实例，根据他们的类别标签投票得到最终输入实例的类别。3.2将图片文本转化为一维向量上面的算法适用于单个实例是向量的情形。所以对于32*32的手写数字文本，如图3.1所示，要将其转化为1*1024的向量。所以定义函数img2Vector来专门进行转化。它接收一个文件名作为参数。一个文件就是一个手写的数字。它的实现如下。图3.1文本格式手写数字0#将一个32*32的数组转化为一个1*1024的向量defimg2Vector(fileName):returnVect=zeros((1,1024))fr=open(fileName)foriinrange(32):lineStr=fr.readline()forjinrange(32):returnVect[0,32*i+j]=int(lineStr[j])returnreturnVect3.3测试算法实现分类首先根据数据集来构造矩阵，然后读取测试数据集，调用knn算法，得出分类器判定的类别，然后和正确的进行比对，最后算出错误率。代码实现如下：defhandwritingClassTest():#用来存储真正的数字hwLabels=[]#得到文件名的列表trainingFileList=listdir('trainingDigits')#算出总共有多少个文件m=len(trainingFileList)#初始化数据集数组trainingMat=zeros((m,1024))foriinrange(m):#下面是截取文件名，获得真正的数字标签fileNameStr=trainingFileList[i]fileStr=fileNameStr.split('.')[0]classNumStr=int(fileStr.split('_')[0])if(i==0):printfileNameStr,fileStr,classNumStrhwLabels.append(classNumStr)#将得到的这个文件转化为向量trainingMat[i,:]=img2Vector('trainingDigits/%s'%fileNameStr)#下面对测试数据进行处理testFileList=listdir('testDigits')errorCount=0.0mTest=len(testFileList)#对每个数据进行测试foriinrange(mTest):fileNameStr=testFileList[i]fileStr=fileNameStr.split('.')[0]classNumStr=int(fileStr.split('_')[0])#将图片转化为向量vectorUnderTest=img2Vector(testDigits/%s%fileNameStr)#获取由分类器得到的值classifierResutl=classify0(vectorUnderTest,trainingMat,hwLabels,3)printtheclassfiercamebackwith:%d,therealansweris:%d%(classifierResutl,classNumStr)if(classifierResutl!=classNumStr):errorCount+=1.0print\nthetotalnumberoferroris:%d%errorCountprint\nthetotalerrorrateis:%f%(errorCount/float(mTest))其中hwLabels是用来存储训练数据集的真实分类标签的，trainingMat是训练数据集的矩阵，vectorUnderTest是测试集中的一个输入实例，然后设置K值大小为3。最后程序运行的部分结果如图3.2所示。这其中还运用了os包中的listdir函数，帮助我们读取文件名，从中提取出正确的标签。所以程序中需要导包：fromosimportlistdir。图3.2测试结果可以看出错误率是1.16%，已经是相当不错的分类效果了。如果改变K值会对错误率有很大的影响。4总结K-近邻算法是基于实例的学习，使用算法时必须要有接近实际数据的训练样本数据，所以它是有监督学习。并且它必须保存所有的数据集，所以要有大量的存储空间。在判决的时候也会比较的耗时。上面的实验简单实现了通过一个分类器来判断一个手写数字是属于哪一个数字的程序。也大致走了一遍机器学习算法的流程，从数据的收集，处理，到测试算法和使用算法（knn并不需要训练算法）。也包含了机器学习算法的三大要素，即模型、策略、算法。本文是机器学习这门课的课程报告，要感谢高志强老师的悉心教导，才能够让我对机器学习有一个入门的了解。参考文献[1]李航.统计学习方法[M].北京:清华大学出版社,2012.[2]PeterHarrington.MachineLearninginAction[M].北京:人民邮电出版社,2013.