《机器学习实战》第二章学习笔记：K-近邻算法（代码详解）

《机器学习实战》数据资料以及总代码可以去GitHub中下载：
GitHub代码地址：https://github.com/yangshangqi/Machine-Learning-in-Action
—————————————————————————————————————————————————————

1、k-近邻算法概述

简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

k-近邻算法
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
k-近邻算法（kNN），它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

一般来说，只选择样本数据集中前k个最相似的数据，这就是 k-近邻 算法中k的出处，通常k是不大于20的整数。

书上举了一个简单但是经典的例子——电影分类，有人曾经统计过很多电影的打斗镜头和接吻镜头，图2-1显示了6部电影的打斗和接吻镜头数。

首先需要知道这个未知电影存在多少个打斗镜头和接吻镜头，图2-1中问号位置是该未知电影出现的镜头数图形化展示，具体数字参见表2-1。

首先计算未知电影与样本集中其他电影的距离，如表2-2所示。

按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是He’s Not Really into Dudes、Beautiful Woman和California Man。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。

k-近邻算法的一般流程
(1) 收集数据：可以使用任何方法。
(2) 准备数据：距离计算所需要的数值，最好是结构化的数据格式。
(3) 分析数据：可以使用任何方法。
(4) 训练算法：此步骤不适用于k-近邻算法。
(5) 测试算法：计算错误率。
(6) 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

1.1准备：使用python导入数据

首先，创建名为kNN.py的Python模块，本章使用的所有代码都在这个文件中。读者可以按照自己的习惯学习代码，既可以按照本书学习的进度，在自己创建的Python文件中编写代码,也可以直接从本书的源代码中复制kNN,py文件。我推荐读者从头开始创建模块，按照学习的进度编写代码。无论大家采用何种方法,我们现在已经有了kNN.py文件。在构造完整的k-近邻算法之前，我们还需要编写-些基本的通用函数，在kNN.py文件中增加下面的代码:

from numpy import *
import operator
# 函数说明:创建数据集
def createDataSet():
    #六组二维特征
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    #六组特征的标签
    labels = ['爱情片','爱情片','爱情片','动作片','动作片','动作片']
    return group, labels

在上面的代码中,我们导入了两个模块:第-一个是科学计算包NumPy;第二个是运算符模块。
由于我们将改代码保存为了KNN.py文件，所以我么你可以通过命令行来导入该模块：

>>> import KNN

上述命令导入kNN模块。为了确保输人相同的数据集，kNN模块中定义S函数createDataSet,在Python命令提示符下输人下属命令:

>>> group, labels = KNN.createDataSet()

这里有4组数据，每组数据有两个我们已知的属性或者特征值。上面的group矩阵每行包含一个不同的数据,我们可以把它想象为某个日志文件中不同的测量点或者人口。由于人类大脑的限制，我们通常只能可视化处理三维以下的事务。因此为了简单地实现数据可视化,对于每个数据点我们通常只使用两个特征。

向量1abels包含了每个数据点的标签信息，labe1包含的元素个数等于group矩阵行数。这里我们将数据点(1, 1.1)定义为类A，数据点(0, 0.1)定义为类B。为了说明方便，例子中的数值是任意选择的，并没有给出轴标签，图2-2是带有类标签信息的四个数据点。

现在我们已经知道Python如何解析数据，如何加载数据，以及kNN算法的工作原理，接下来我们将使用这些方法完成分类任务。

1.2 实施KNN分类算法

对未知类别属性的数据集中的每个点依次执行以下操作：
(1) 计算已知类别数据集中的点与当前点之间的距离；
(2) 按照距离递增次序排序；
(3) 选取与当前点距离最小的k个点；
(4) 确定前k个点所在类别的出现频率；
(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

根据两点距离公式（欧氏距离公式），计算两个向量点xA和xB之间的距离。

按照步骤，接下来对数据按照从小到大的次序排序。选择距离最小的前k个点，并返回分类结果。

def classify(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0] #获得第 i + 1 维的长度
    #tile用法：表示inX这个列表， 第一个维度重复dataSetSize遍， 第二个维度重复1遍
    #diffMat表示inX这个集合到dataSet的差是多少
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2 #求出该矩阵内数各个值的的平方
    sqDistances = sqDiffMat.sum(axis=1)# sum(axis = 0)计算每一列的和sum(axis = 1)计算每一行的和
    distances = sqDistances**0.5   #开根号  12 ~ 18 就是在求sqrt((x1 - x2)**2 + (y1 - y2)**2)
    sortedDistIndicies = distances.argsort() #注意argsort()它不会改变原来的数组，它返回一个新的数组，它的数据元素是（默认是从小到大）索引值
    classCount={}          #字典
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        #这一步就是在求哪个标签出现的次数最多
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #get函数：在字典中寻找voteIlabel的值， 如果不存在返回0
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse = True)# 将字典中的值从小到大排序
    return sortedClassCount[0][0]  # 获得字典中第一个元素所对应的值

计算完所有点之间的距离后，可以对数据按照从小到大的次序排序。然后，确定前k个距离最小元素所在的主要分类,输人K总是正整数;最后，将classCount字典分解为元组列表,
然后使用程序第二行导入运算符模块的temgetter方法,按照第二个元素的次序对元组进行排序。此处的排序为逆序，即按照从最大到最小次序排序，最后返回发生频率最高的元素标签。
为了预测数据所在分类，在Python提示符中输入下列命令:

>>> KNN.classify([0, 0],group,labels,3)

输出结果应该是B，大家也可以改变输入[0, 0]为其他值，测试程序的运行结果。
到现在为止，我们已经构造了第一个分类器,使用这个分类器可以完成很多分类任务。
从这个实例出发，构造使用分类算法将会更加容易。

1.3如何测试分类器

有点那种我们依据自己的经验进行判断的意思，也就是上面我说的看“接吻动作”和“打斗动作”，然后进行判断的意味。

看到这，你可能会问：“分类器何种情况下会出错？”或者“答案是否总是正确的？”答案是否定的，分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。此外分类器的性能也会受到多种因素的影响，如分类器设置和数据集等。除此之外，不同的算法在不同数据集上的表现可能完全不同。

为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率——分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为0，最差分类器的错误率是1.0。同时，我们也不难发现，k-近邻算法没有进行数据的训练，直接使用未知的数据与已知的数据进行比较，得到结果。因此，可以说k-邻近算法不具有显式的学习过程。

2.示例: 使用k-近邻算法改进约会网站的配对效果

这里是一个比较有意思的话题产生的例子，也就是婚介网站等等的约会网站帮助你相亲，我的朋友海伦就是这样一个人，她一直使用在线约会网站寻找适合自己的约会对象，但是她发现尽管约会网站会推荐不同的人选，但并不是每一个人她都喜欢。经过一番总结，她发现曾交往过三种类型的人：不喜欢的人、魅力一般的人和极具魅力的人。

她希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外，海伦自己还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。

在约会网站上使用k-近邻算法
(1) 收集数据：提供文本文件。
(2) 准备数据：使用Python解析文本文件。
(3) 分析数据：使用Matplotlib画二维扩散图。
(4) 训练算法：此步骤不适用于k-近邻算法。
(5) 测试算法：使用海伦提供的部分数据作为测试样本。测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
(6) 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

2.1准备数据：从文本文件中解析数据

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦的样本主要包含以下3种特征：

每年获得的飞行常客里程数
玩视频游戏所耗时间百分比
每周消费的冰淇淋公升数

在将上述特征数据输人到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。在kNN.py中创建名为file2matrix的函数，以此来处理输人格式问题。该函数的输人为文件名字符串，输出为训练样本矩阵和类标签向量。

将下面的代码增加到kNN.py中。

def file2matrix(filename):
    fr = open(filename)
    # read( )：表示读取全部内容当无参数的时候      readline( )：表示每次读出一行   readlines( )是读取所有的行
    # 每一行作为一个元素放在列表里面 。 所以arrayOLines为列表
    arrayOLines = fr.readlines();
    numberOfLines = len(arrayOLines)         #得到文件的行数
    returnMat = zeros((numberOfLines,3))        #创建一个有 number行， 每行有 3 个元素的矩阵， 默认值为0
    classLabelVector = []                       #将数据中的信息解析到列表
    index = 0
    for line in arrayOLines:
        line = line.strip() #strip() 方法用于移除字符串头尾指定的字符（默认为空格)
        listFromLine = line.split('\t') #将字符串line以制表符分割成列表
        returnMat[index,:] = listFromLine[0:3] # 将listFromLine中的前3个元素加入到returnMat[index]中
        classLabelVector.append(int(listFromLine[-1])) #获得数据列表中的最后一个元素
        index += 1
    return returnMat,classLabelVector

从上面的代码可以看到，Python处理文本文件非常容易。首先我们需要知道文本文件包含多少行。打开文件，得到文件的行数。然后创建以零填充的矩阵NumPy❷(实际上，NumPy是一个二维数组，这里暂时不用考虑其用途)。为了简化处理，我们将该矩阵的另- -维度设置为固定值3，你可以按照自己的实际需求增加相应的代码以适应变化的输入值。循环处理文件中的每行数据❸，首先使用函数1ine. strip()截取掉所有的回车字符，然后使用tab字符\t将上一步得到的整行数据分割成-个元素列表。接着,我们选取前3个元素,将它们存储到特征矩阵中。Python语言可以使用索引值-1表示列表中的最后- -列元素,利用这种负索引，我们可以很方便地将列表的最后一-列存储到向量classLabelvector中。 需要注意的是，我们必须明确地通知解释器，告诉它列表中存储的元素值为整型，否则Python语 言会将这些元素当作字符串处理。以前我们必须自己处理这些变量值类型问题，现在这些细节问题完全可以交给NumPy函数库来处理。

在Python命令提示符下输入下面命令:

>>>>>> reload (kNN)
>>>datingDataMat , datingLabels = kNN. file2matrix ( 'datingTestSet. txt')
>>> datingLabels [0:20]
{3，2，1，1，1，1，3，3，1，3，1,1,2，1，1，1，1,1,2，3]

现在已经从文本文件中导人了数据,并将其格式化为想要的格式,接着我们需要了解数据的真实含义。当然我们可以直接浏览文本文件，但是这种方法非常不友好，- -般来说，我们会采用图形化的方式直观地展示数据。下面就用Python工具来图形化展示数据内容,以便辨识出一些数据模式。

2.2 分析数据：使用matplotlib创建散点图

首先我们使用Matplotib制作原始数据的散点图，在Python命令行环境中，输入下列命令:

>>> import matplotlib
>>> import matplotlib. pyplot as plt
>>> fig = plt. figure ()
>>> ax = fig.add subplot (111)
>>> ax. scatter (datingDataMat [;i1], datingDataMat[:,2])
>>> plt. show ()

输出效果如图2-3所示。散点图使用datingDataMat矩阵的第二、第三列数据,分别表示特征值“玩视频游戏所耗时间百分比”和“每周所消费的冰淇淋公升数”。

由于没有使用样本分类的特征值，我们很难从图2-3中看到任何有用的数据模式信息。一般来说，我们会采用色彩或其他的记号来标记不同样本分类，以便更好地理解数据信息。Matplotlib库提供的scatter函数支持个性化标记散点图上的点。重新输人上面的代码，调用scatter函数时使用下列参数:

>>> ax. scatter (dat ingDataMat [:,1]， datingDataMat[;,2] ,
15.0*array (datingLabels)，15. 0*array (datingLabels) )

上述代码利用变量datingLabels存储的类标签属性,在散点图上绘制了色彩不等、尺寸不同的点。你可以看到-一个与图2-3类似的散点图。从图2-3中，我们很难看到任何有用的信息，然而由于图2-4利用颜色及尺寸标识了数据点的属性类别，因而我们基本上可以从图2-4中看到数据点所属三个样本分类的区域轮廓。

2.3 准备数据:归一化数值

表2-3给出了提取的四组数据，如果想要计算样本3和样本4之间的距离，可以使用下面的方法：

很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于表2-3中其他两个特征——玩视频游戏的和每周消费冰淇淋公升数——的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

在处理这种不同取值范围的特征值时，通常采用的方法是将数值归一化，如将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：

其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。

我们需要在文件kNN.py中增加一一个新函数autoNorm()，该函数可以自动将数字特征值转化为0到1的区间。

def autoNorm(dataSet):
    minVals = dataSet.min(0)# min(0)返回该矩阵中每一列的最小值 min(1)返回该矩阵中每一行的最小值
    maxVals = dataSet.max(0)# 得到的是一个矩阵
    ranges = maxVals - minVals # 让最大值-最小值
    normDataSet = zeros(shape(dataSet)) # 创建矩阵
    print(normDataSet)
    m = dataSet.shape[0] #获得第一维的元素个数
    normDataSet = dataSet - tile(minVals, (m,1)) #当前值减去最小值， tile()函数，将矩阵minVals复制m份
    normDataSet = normDataSet/tile(ranges, (m,1)) #将数字特征值转化为了0到1的区间
    return normDataSet, ranges, minVals

在函数autoNorm()中，我们将每列的最小值放在变量minVals中，将最大值放在变量maxVals中，其中dataSet .min (0)中的参数0使得函数可以从列中选取最小值，而不是选取当前行的最小值。然后，函数计算可能的取值范围，并创建新的返回矩阵。正如前面给出的公式，为了归一化特征值，我们必须使用当前值减去最小值，然后除以取值范围。需要注意的是，特征值矩阵有1000 x 3个值，而minVals和range的值都为1 x3。为了解决这个问题，我们使用NumPy库中tile()函数将变量内容复制成输人矩阵同样大小的矩阵，注意这是具体特征值相除，而对于某些数值处理软件包，/可能意味着矩阵除法，但在NumPy库中，矩阵除法需要使用函数linalg.solve (matA, matB)。

在Python命令提示符下，重新加载kNN.py模块，执行autoNorm函数，检测函数的执行

>>> reload (kNN)
>>> normMat， ranges, minVals = kNN. autoNorm (dat i ngDataMat)
: >》> normMat
array([[ 0.33060119,0.58918886，0.69043973] ,
[ 0.49199139， 0.50262471， 0.13468257]，
[ 0.34858782， 0.68886842 , .0.59540619] ,
....
[ 0.93077422,0.52696233,0.58885466]，
[ 0.76626481 , 0.44109859,0.88192528] ,
[ 0.0975718 ，0.02096883 ,0.02443895]] )
>>> ranges
array([ 8. 78430000e+04,2.02823930e+01,1.69197100e+00])
>>> minVals
array([ 0. , 0, 0.001818] )

2.4测试算法:作为完整程序验证分类器

机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。需要注意的是，10%的测试数据应该是随机选择的，由于海伦提供的数据并没有按照特定目的来排序，所以我么你可以随意选择10%数据而不影响其随机性。

前面已经提到可以使用错误率来检测分类器的性能。对于分类器来说，错误率就是分类器给出错误结果的次数除以测试数据的总数，完美分类器的错误率为0，而错误率为1.0的分类器不会给出任何正确的分类结果。代码里我们定义一个计数器变量，每次分类器错误地分类数据，计数器就加1，程序执行完成之后计数器的结果除以数据点总数即是错误率。

为了测试分类器效果，在kNN,py文件中创建函数datingClassTest,该函数是自包含的你可以在任何时候在Python运行环境中使用该函数测试分类器效果。在kNN.py文件中输入下面的程序代码。

#拿出 10% 的数据去测试该算法的出错率
def datingClassTest():
    hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio) #得到测试用的数据数量
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print("the total error rate is: %f" % (errorCount/float(numTestVecs)))
    print(errorCount)

在Python命令提示符下重新加载kNN模块，并输人kNN . datingClassTest(),执行分类器测试程序，我们将得到下面的输出结果:

>>> kNN, datingClassTest ()
the classifier came back with: 1，the real answer is; 1
the classifier came back with: 2，the real answer is: 2
the classifier
came back with: 1，the real answer" is: 1
the classifier came back with: 2，the real answer is: 2
the classifier came back with: 3，the real answer is: 3
the classifier came back with: 3，the real answer is: 1
the classifier came back with: 2，the real answer is: 2
the total error rate is: 0. 024000

分类器处理约会数据集的错误率是2.4%，这是-一个相当不错的结果。我们可以改变函数datingClassTest内变量hoRatio和变量k的值,检测错误率是否随着变量值的变化而增加。依赖于分类算法、数据集和程序设置,分类器的输出结果可能有很大的不同。这个例子表明我们可以正确地预测分类,错误率仅仅是2.4%。海伦完全可以输入未知对象的属性信息，由分类软件来帮助她判定某- -对象的可交往程度: 讨厌、一般喜欢、非常喜欢。

2.5 使用算法：构建完整可用系统

上面已经在数据上对分类器进行了测试，现在终于可以使用这个分类器为海伦来对人们分类。我们会给海伦一小段程序，通过该程序海伦会在约会网站上找到某个人并输入他的信息。程序会给出她对对方喜欢程度的预测值。

将下列代码加入到kNN.py并重新载人kNN。

# 2.2.5 约会网站预测函数
def classifyPerson():
    resultList = ['largeDos es', 'smallDoses', 'didntLike']  # 3种预测结果集
    percentTats = float(input("Please input percentage of time spent playing vedio games?"))
    ffMiles = float(input("frequent flier miles earned consumed per year?"))
    iceCream = float(input("Liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
    classifierResult = classify((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print("You will probably like this person : %s " % resultList[classifierResult - 1])

上述程序清单中的大部分代码我们在前面都见过。唯- :新加入的代码是函数raw_input()。该函数允许用户输人文本行命令并返回用户所输人的命令。为了解程序的实际运行效果,输入如下命令:

>>> kNN. classifyPerson ()
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5 
You wi1l probably like this person : in smal1 doses

目前为止，我们已经看到如何在数据上构建分类器。这里所有的数据让人看起来都很容易，但是如何在人不太容易看懂的数据上使用分类器呢?从下一-节的例子中,我们会看到如何在二进制存储的图像数据上使用kNN。

3.示例：手写识别系统

本节我们一步步地构造使用k-近邻分类器的手写识别系统。为了简单起见，这里构造的系统只能识别数字0到9，参见图2.6。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小:宽高是32像素x 32像素的黑白图像。尽管采用文本格式存储图像不能有效的利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

示例：使用k-近邻算法的手写识别系统
(1) 收集数据：提供文本文件。
(2) 准备数据：编写函数classify0()，将图像格式转换为分类器使用的list格式。
(3) 分析数据：在Python命令提示符中检查数据，确保它符合要求。
(4) 训练算法：此步骤不适用于k-近邻算法。
(5) 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
(6) 使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统。

3.1 准备数据:将图像转换为测试向量

实际图像存储在第2章源代码的两个子目录内:目录trainingDigits中包含了大约2000个例子，每个例子的内容如图2-6所示,每个数字大约有200个样本;目录testDigits中包含了大约900个测试数据。我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果。两组数据没有覆盖，你可以检查一下这些文件夹的文件是否符合要求。

为了使用前面两个例子的分类器，我们必须将图像格式化处理为-个向量。我们将把一个32 x32的二进制图像矩阵转换为1 x 1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。我们首先编写- -段函数img2vector, 将图像转换为向量:该函数创建1 x 1024的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组
中，最后返回数组。

#2.3.1 准备数据：将图像转换为单行测试向量
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]

3.2 测试算法: 使用K-近邻算法识别手写数字

上节我们已经将数据处理成分类器可以识别的格式，本节我们将这些数据输人到分类器,检测分类器的执行效果。程序清单2-6所示的自包含函数handwri tingClassTest ()是测试分类器的代码，将其写人kNN.py文件中。在写入这些代码之前，我们必须确保将from OS import listdir写人文件的起始部分，这段代码的主要功能是从os模块中导人函数listdir,它可以列出给定目录的文件名。

# 2.3.2使用k近邻算法识别手写数字
# 测试代码，查看错误率
def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')     #得到文本列表
    m = len(trainingFileList)   #获取长度
    trainingMat = zeros((m,1024)) # 初始化矩阵
    for i in range(m):
        fileNameStr = trainingFileList[i]# 得到第i个文本
        fileStr = fileNameStr.split('.')[0]     #以小数点分割字符串，并得到第 0 个元素
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        #将图像转换为单行测试向量
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')      #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        #使用K近邻算法
        classifierResult = classify(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 目录中的文件执行相似的操作，不同之处是我们并不将这个目录下的文件载入矩阵中，而是使用classifyO()函数测试该目录下的每个文件。由于文件中的值已经在0和1之间，本节并不需要使用2.2节的autoNorm()函数。

在Python命令提示符中输人KNN.handwritingClassTest(),测试该函数的输出结果。依赖于机器速度，加载数据集可能需要花费很长时间，然后函数开始依次测试每个文件,输出结果
如下所示:

>>> kNN. handwritingClassTest ()
the 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: B
the classifier came back with: 8，the real answer is: 8
the classifier came back with: 8，the real answer is: 8
the classifier cane 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: 11
the total error rate is: 0.011628

k近邻算法识别手写数字数据集,错误率为1.2%。改变变量k的值、修改函数handwriting-ClassTest随机选取训练样本、改变训练样本的数目，都会对k近邻算法的错误率产生影响，感兴趣的话可以改变这些变量值,观察错误率的变化。
实际使用这个算法时,算法的执行效率并不高。因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次，此外，我们还需要为测试向量准备2MB的存储空间。是否存在- -种算法减少存储空间和计算时间的开销呢? k决策树就是k-近邻算法的优化版，可以节省大量的计算开销。