本节我们一步步地构造使用k近邻分类器的手写识别系统。为了简单起见，这里构造的系统只能识别数字0到9，参见图2-6。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小 1：宽高是32像素x32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。
示例：使用k-近邻算法的手写识别系统
- 收集数据：提供文本文件。
- 准备数据：编写函数
classify0，将图像格式转换为分类器使用的list格式。- 分析数据：在Python命令提示符中检查数据，确保它符合要求。
- 训练算法：此步骤不适用于k近邻算法。
- 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
- 使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统。
1.该数据集合修改自/"手写数字数据集的光学识别/"一文中的数据集合，该文登载于2010年10月3日的UCI机器学习资料库中http://archive.ics.uci.edu/ml。作者是土耳其伊斯坦布尔海峡大学计算机工程系的E. Alpaydin与C. Kaynak。
2.3.1 准备数据：将图像转换为测试向量
实际图像存储在第2章源代码的两个子目录内：目录trainingDigits中包含了大约2000个例子，每个例子的内容如图2-6所示，每个数字大约有200个样本；目录testDigits中包含了大约900个测试数据。我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果。两组数据没有重叠，你可以检查一下这些文件夹的文件是否符合要求。
图2-6 手写数字数据集的例子
为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个32x32的二进制图像矩阵转换为1x1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。
我们首先编写一段函数img2vector，将图像转换为向量：该函数创建1x1024的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。
def img2vector(filename): returnVect = zeros((1,1024)) fr = open(filename) for i in range(32): lineStr = fr.readline for j in range(32): returnVect[0,32*i+j] = int(lineStr[j]) return returnVect 将上述代码输入到kNN.py文件中，在Python命令行中输入下列命令测试img2vector函数，然后与文本编辑器打开的文件进行比较：
>>> testVector = kNN.img2vector(/'testDigits/0_13.txt/')>>> testVector[0,0:31]array([ 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]) >>> testVector[0,32:63]array([ 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]) 2.3.2 测试算法：使用k近邻算法识别手写数字
上节我们已经将数据处理成分类器可以识别的格式，本节我们将这些数据输入到分类器，检测分类器的执行效果。程序清单2-6所示的自包含函数handwritingClassTest是测试分类器的代码，将其写入kNN.py文件中。在写入这些代码之前，我们必须确保将from os import listdir写入文件的起始部分，这段代码的主要功能是从os模块中导入函数listdir，它可以列出给定目录的文件名。
程序清单2-6 手写数字识别系统的测试代码
def handwritingClassTest: hwLabels = trainingFileList = listdir(/'trainingDigits/') #❶ 获取目录内容 m = len(trainingFileList) trainingMat = zeros((m,1024)) for i in range(m): #❷ （以下三行）从文件名解析分类数字 fileNameStr = trainingFileList[i] fileStr = fileNameStr.split(/'./')[0] classNumStr = int(fileStr.split(/'_/')[0]) hwLabels.append(classNumStr) trainingMat[i,:] = img2vector(/'trainingDigits/%s/' % fileNameStr) testFileList = listdir(/'testDigits/') errorCount = 0.0 mTest = len(testFileList) for i in range(mTest): fileNameStr = testFileList[i] fileStr = fileNameStr.split(/'./')[0] classNumStr = int(fileStr.split(/'_/')[0]) vectorUnderTest = img2vector(/'testDigits/%s/' % fileNameStr) classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print /"the classifier came back with: %d, the real answer is: %d/"% (classifierResult, classNumStr) if (classifierResult != classNumStr): errorCount += 1.0 print /"nthe total number of errors is: %d/" % errorCount print /"nthe total error rate is: %f/" % (errorCount/float(mTest)) 在程序清单2-6中，将trainingDigits目录中的文件内容存储在列表中❶，然后可以得到目录中有多少文件，并将其存储在变量m中。接着，代码创建一个m行1024列的训练矩阵，该矩阵的每行数据存储一个图像。我们可以从文件名中解析出分类数字❷。该目录下的文件按照规则命名，如文件9_45.txt的分类是9，它是数字9的第45个实例。然后我们可以将类代码存储在hwLabels向量中，使用前面讨论的img2vector函数载入图像。在下一步中，我们对testDigits目录中的文件执行相似的操作，不同之处是我们并不将这个目录下的文件载入矩阵中，而是使用classify0函数测试该目录下的每个文件。由于文件中的值已经在0和1之间，本节并不需要使用2.2节的autoNorm函数。
在Python命令提示符中输入kNN.handwritingClassTest，测试该函数的输出结果。依赖于机器速度，加载数据集可能需要花费很长时间，然后函数开始依次测试每个文件，输出结果如下所示：
>>> kNN.handwritingClassTestthe classifier came back with: 0, the real answer is: 0 the classifier came back with: 0, the real answer is: 0..the classifier came back with: 7, the real answer is: 7 the classifier came back with: 7, the real answer is: 7 the classifier came back with: 8, the real answer is: 8 the classifier came back with: 8, the real answer is: 8 the classifier came back with: 8, the real answer is: 8 the classifier came back with: 6, the real answer is: 8..the classifier came back with: 9, the real answer is: 9 the total number of errors is: 11the total error rate is: 0.011628 k近邻算法识别手写数字数据集，错误率为1.2%。改变变量k的值、修改函数handwritingClassTest随机选取训练样本、改变训练样本的数目，都会对k近邻算法的错误率产生影响，感兴趣的话可以改变这些变量值，观察错误率的变化。
实际使用这个算法时，算法的执行效率并不高。因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次，此外，我们还需要为测试向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢？k决策树就是k近邻算法的优化版，可以节省大量的计算开销。