机器学习实战笔记-k-近邻算法

机器学习实战笔记-k-近邻算法

目录

 1. k-近邻算法概述

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

 3. 示例：手写识别系统

 4. 小结

本章介绍了《机器学习实战》这本书中的第一个机器学习算法：k-近邻算法，它非常有效而且易于掌握。首先，我们将探讨k-近邻算法的基本理论，以及如何使用距离测量的方法分类物品；其次我们将使用Python从文本文件中导入并解析数据；再次，本文讨论了当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见错误；最后，利用实际的例子讲解如何使用k-近邻算法改进约会网站和手写数字识别系统。

1. k-近邻算法概述

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

k-近邻算法

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

k-近邻算法（kNN）的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

现在我们回到前面电影分类的例子，使用k-近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头，图1显示了6部电影的打斗和接吻镜头数。假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？我们可以使用kNN来解决这个问题。

 

 图1 使用打斗和接吻镜头数分类电影

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

表1 每部电影的打斗镜头数、接吻镜头数以及电影评估类型

电影名称	打斗镜头	接吻镜头	电影类型
California Man	3	104	爱情片
He’s Not Really into Dudes	2	100	爱情片
Beautiful Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Robo Slayer 3000	99	5	动作片
Amped II	98	2	动作片
?	18	90	未知

计算未知电影与样本集中其他电影的距离，我们可以比较其相似度：

表2 已知电影与未知电影的距离

电影名称	与未知电影的距离
California Man	20.5
He’s Not Really into Dudes	18.7
Beautiful Woman	19.2
Kevin Longblade	115.3
Robo Slayer 3000	117.4
Amped II	118.9

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

k-近邻算法的一般流程

(1)收集数据：可以使用任何方法。 

(2)准备数据：距离计算所需要的数值，最好是结构化的数据格式。 

(3)分析数据：可以使用任何方法。

(4)训练算法：此步驟不适用于1 近邻算法。 

(5)测试算法：计算错误率。 

(6)使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类。

1.1 准备：使用Python导入数据

创建名为kNN.py的Python模块，在kNN.py文件中增加下面的代码：

# -*- coding: utf-8 -*-
from numpy import *
import operator
 
def createDataSet():
    """ 
    函数作用：构建一组训练数据（也就是样本),其实这里的样本是我们自己构造 
    的数据，样本容量很少，真实的情况是读取文本数据。 
    同时给出样本的标签以及labels。标签的意思就是样本四个数据的各个类别 
    比如[1.0,1.1]属于A类等。 
    """  
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

这个函数创建了我们将要使用的样例数据集。

在Python shell中输入下列命令测试上面的函数：

>>> import kNN

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

1.2 实施kNN算法

k-近邻算法的伪代码

对未知类型属性的数据集中的每个点依次执行以下操作：

(1) 计算已知类别数据集中的点与当前点之间的距离；

(2) 按照距离增序排序；

(3) 选取与当前点距离最近的k个点；

(4) 决定这k个点所属类别的出现频率；

(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

函数实现如下：

def classify(inX, dataSet, labels, k):

    """ 

    inX 是输入的测试样本，是一个[x, y]样式的，也就是我们需要想知道的 

    数据到底属于哪类A活着B，就想上面说的未知电影是爱情还是动作影片。 

    dataset是训练样本集 

    labels是训练样本标签其实就是类别A和B 

    k是top k最相近的。说实话开始我并不理解，其实很简单就是选取离自己 

    最近的k个样本，具体我在上面会有介绍 

    """  

    dataSetSize = dataSet.shape[0] # 数据集大小

    #dataSet.shape 结果是（4，1）返回矩阵的行数和列数。  

    # 那么shape[0]获取数据集的行数，    

    # 行数就是样本的数量 这里就是4 

    # 计算距离

    """  

    下面的求距离过程就是按照欧氏距离的公式计算的。  

    即 根号(x2-x1）^2+(y2-y1)^2) 。比如（1，2），（2，3） 

    这两个点的距离就是（2-1）^2+（3-2）^2,然后开根号计算。 

    """    

    diffMat = tile(inX, (dataSetSize, 1)) - dataSet

    """ 

    由于dataset数据是一个4行1列的数据，而我们测试的数据，是一个一行一列的数据， 

    比如（1，0）。由于要把这个值跟测试数据每一个都进行减法。为了方便就必须是构造 

    一个同样结构的矩阵数据，用tile方法相当于copy inX四次沿着行。比如以前是（1，0） 

    那么tile（inX，（4，1））变成啦 

    1  0 

    1  0 

    1  0 

    1  0  

    """  

    sqDiffMat = diffMat**2

    # 然后就是平方每个进行减法的值

    sqDistances = sqDiffMat.sum(axis=1)

    """ 

    sqDiffMat ＝ 

    [[ 1.    1.21] 

    [ 1.    1.  ] 

    [ 0.    0.  ] 

    [ 0.    0.01]] 

   sqDiffMat.sum(axis=1) 把所有的值都加起来沿着 x轴，而都是一行行的加那么结果。四个值 

    ［2.21. 2. 0. 0.01］  

   sqDiffMat.sum(axis=0)  但是当我们把axis=0结果就发生了变化。都是一列列的加， 

    而只有两个值所有的x值加在一起，所有的y值加在一起 

    我们发现只有x值都都在一起，然后y都加在一起。 

    [ 2.    2.22] 

    """  

    distances = sqDistances**0.5

    # 按距离排序

    sortedDistIndicies = distances.argsort()

    """  

    distances  =[ 1.48660687  1.41421356  0.          0.1       ] 

    distances.argsort()  这个函数就是返回从小到大的值的索引，也就是距离 

    值按照由近到远排列距离索引值。 

    比如最大就是第一个（index ＝ 0）最小值就是第三个（index＝2） 

    那么返回顺序就是如下。 

    sortedDistIndicies＝[2 3 1 0] 

    """  

    # 统计前k个点所属的类别

    classCount = {}

    for i in range(k):

        votaIlabel = labels[sortedDistIndicies[i]]

        classCount[votaIlabel] = classCount.get(votaIlabel, 0) + 1

    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

      """ 

      sorted函数的作用就是排序，一般是从小到大，但是这里reverse=True 

      表示从反过来啦从大到小 

      classCount.iteritems()用于返回一个 iterator， 

      关于iteritems()方法以及其他相关函数见下面博客 我觉得研究的很好。 

      Python dictionary items()系列函数的使用 

      http://blog.csdn.net/revilwang/article/details/38686635 

      operator.itemgetter(1) 获取前面的classCount.iteritems()中 

      第二个值进行操作，按照第二个升序排列。 

      比如下面这个例子 

      >>> d = {'data1':3, 'data2':1, 'data3':2, 'data4':4}   

      >>> sorted(d.iteritems(), key=itemgetter(1), reverse=True)   

      >>>[('data4', 4), ('data1', 3), ('data3', 2), ('data2', 1)]   

      """   

    # 返回前k个点中频率最高的类别

    return sortedClassCount[0][0]

    """ 

    返回这个list或者怎么说第一个数值对中第一个值。这里是B， 

    比如下面例子就是data4 

    >>> d 

    [('data4', 4), ('data1', 3), ('data3', 2), ('data2', 1)] 

    >>> d[0][0] 

    'data4' 

    """  

计算距离时直接使用了欧式距离公式，计算两个向量点xA和xB之间的距离：

 

计算完所有点之间的距离后，可以对数据按照从小到大的次序排序。然后，确定前k个距离最小元素所在的主要分类，输入k总是正整数；最后，将classCount字典分解为元组列表，然后按照第二个元素的次序对元组进行排序，最后返回发生频率最高的元素标签。

预测数据所在分类：

>>> import kNN  

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

>>> kNN.classify0([0, 0], group, labels, 3)  

'B'  

输出结果应该是B。

1.3 如何测试分类器

上文我们已经使用k-近邻算法构造了第一个分类器，也可以检验分类器给出的答案是否符合我们的预期。然而分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。

为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率——分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为0，最差分类器的错误率是1.0，在这种情况下，分类器根本就无法找到一个正确答案。然而错误率几乎不会达到1.0，因为即使是随机猜测，也会有一定概率猜对的。因此，错误率一般存在一个上限，且具体的值会与各类型之间的比例关系直接相关。

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

我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现曾交往过三种类型的人：

 不喜欢的人

 魅力一般的人

 极具魅力的人

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

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

数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。

海伦的样本主要包含以下3种特征：

 每年获得的飞行常客里程数

 玩视频游戏所耗时间百分比

 每周消费的冰淇淋公升数

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

def file2matrix(filename):

    fr = open(filename)

    numberOfLines = len(fr.readlines())  # get the number of lines in the file

    returnMat = zeros((numberOfLines, 3))  # prepare matrix to return

    classLabelVector = []  # prepare labels return

    fr = open(filename)

    index = 0

    for line in fr.readlines():

        line = line.strip()

        listFromLine = line.split('\t')

        returnMat[index, :] = listFromLine[0:3]

        classLabelVector.append(int(listFromLine[-1]))

        index += 1

    return returnMat, classLabelVector

Python处理文本文件非常容易——

 首先我们需要知道文本文件包含多少行。打开文件，得到文件的行数。

 然后创建以零填充的矩阵NumPy。

 循环处理文件中的每行数据，首先使用函数line.strip()截取掉所有的回车字符，然后使用tab字符\t将上一步得到的整行数据分割成一个元素列表。

 接着，我们选取前3个元素，将它们存储到特征矩阵中。

 Python语言可以使用索引值-1表示列表中的最后一列元素，利用这种负索引，我们可以很方便地将列表的最后一列存储到向量classLabelVector中。

测试代码：

>>> import importlib

>>> importlib.reload(kNN)

>>> datingDataMat, datingLabels = kNN.file2matrix('datingTestSet.txt')

>>> datingDataMat

>>> datingLabels

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

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

>>> import matplotlib

>>> import matplotlib.pyplot as plt

>>> fig = plt.figure()

>>> ax = fig.add_subplot(111)

>>> ax.scatter(datingDataMat[:,1], datingDataMat[:,2])

>>> plt.show()

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

图3 没有样本类别标签的约会数据散点图。难以辨识图中的点究竟属于哪个样本分类

重新输入上面的代码，在调用scatter函数时使用下列参数：

>>> ax.scatter(datingDataMat[:,1], datingDataMat[:,2], 15.0 * array(datingLabels), 15.0 * array(datingLabels))

完整代码：

>>> import importlib

>>> importlib.reload(kNN)

>>> datingDataMat,datingLabels = kNN.file2matrix('datingTestSet2.txt')

>>> import matplotlib

>>> import matplotlib.pyplot as plt

>>> fig = plt.figure()

>>> ax = fig.add_subplot(111)

>>> from numpy import *

>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))

>>> plt.show()

上述代码利用变量datingLabels存储的类标签属性，在散点图上绘制了色彩不等、尺寸不同的点。

利用颜色及尺寸标识了数据点的属性类别，因而我们基本上可以从图4中看到数据点所属三个样本分类的区域轮廓。

图4 带有样本分类标签的约会数据散点图。虽然能够比较容易地区分数据点从属类别，但依然很难根据这张图得出结论性信息，而下图采用列1和2的属性值可以得到更好的效果

图中清晰地标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同，并以红色的'*'表示类标签1、蓝色的'o'表示表示类标签2、绿色的'+'表示类标签3，修改参数如下：

import matplotlib
import numpy as np
from numpy import *
from matplotlib import pyplot as plt
from matplotlib.font_manager import FontProperties 
 
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())  # get the number of lines in the file
    returnMat = zeros((numberOfLines, 3))  # prepare matrix to return
    classLabelVector = []  # prepare labels return
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector
zhfont = FontProperties(fname='C:/Windows/Fonts/simsun.ttc',size=12)
 
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
fig = plt.figure()

plt.figure(figsize=(8, 5), dpi=80)
ax = plt.subplot(111)

datingLabels = np.array(datingLabels)
idx_1 = np.where(datingLabels==1)
p1 = ax.scatter(datingDataMat[idx_1,0],datingDataMat[idx_1,1],marker = '*',color = 'r',label='1',s=10)
idx_2 = np.where(datingLabels==2)
p2 = ax.scatter(datingDataMat[idx_2,0],datingDataMat[idx_2,1],marker = 'o',color ='g',label='2',s=20)
idx_3 = np.where(datingLabels==3)
p3 = ax.scatter(datingDataMat[idx_3,0],datingDataMat[idx_3,1],marker = '+',color ='b',label='3',s=30)

plt.xlabel(u'每年获取的飞行里程数', fontproperties=zhfont)
plt.ylabel(u'玩视频游戏所消耗的事件百分比', fontproperties=zhfont)
ax.legend((p1, p2, p3), (u'不喜欢', u'魅力一般', u'极具魅力'), loc=2, prop=zhfont)
plt.show()

 图5 每年赢得的飞行常客里程数与玩视频游戏所占百分比的约会数据散点图。约会数据有三个特征，通过图中展示的两个特征更容易区分数据点从属的类别

2.3 准备数据：归一化数值

不同特征值有不同的均值和取值范围，如果直接使用特征值计算距离，取值范围较大的特征将对距离计算的结果产生绝对得影响，而使较小的特征值几乎没有作用，近乎没有用到该属性。如两组特征：{0, 20000, 1.1}和{67, 32000, 0.1}，计算距离的算式为：

 

显然第二个特征将对结果产生绝对得影响，第一个特征和第三个特征几乎不起作用。

然而，对于识别的过程，我们认为这不同特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

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

newValue = (oldValue – min) / (max – min)

其中min和max分别是数据集中的最小特征值和最大特征值。

添加autoNorm()函数，用于将数字特征值归一化：

def autoNorm(dataSet):

    minVals = dataSet.min(0)# 分别求各个特征的最小值

    maxVals = dataSet.max(0)# 分别求各个特征的最大值

    ranges = maxVals - minVals# 各个特征的取值范围

    normDataSet = zeros(shape(dataSet))

    m = dataSet.shape[0]

    normDataSet = dataSet - tile(minVals, (m, 1))

    normDataSet = normDataSet / tile(ranges, (m, 1))  # element wise divide

    return normDataSet, ranges, minVals

对这个函数，要注意返回结果除了归一化好的数据，还包括用来归一化的范围值ranges和最小值minVals，这将用于对测试数据的归一化。

注意，对测试数据集的归一化过程必须使用和训练数据集相同的参数（ranges和minVals），不能针对测试数据单独计算ranges和minVals，否则将造成同一组数据在训练数据集和测试数据集中的不一致。

查看经过归一化后的数据：

>>> import importlib

>>> importlib.reload(kNN)

>>> normMat, ranges, minVals = kNN.autoNorm(datingDataMat)

>>> normMat

array([[ 0.44832535,  0.39805139,  0.56233353],

       [ 0.15873259,  0.34195467,  0.98724416],

       [ 0.28542943,  0.06892523,  0.47449629],

       ...,

       [ 0.29115949,  0.50910294,  0.51079493],

       [ 0.52711097,  0.43665451,  0.4290048 ],

       [ 0.47940793,  0.3768091 ,  0.78571804]])

>>> ranges

array([  9.12730000e+04,   2.09193490e+01,   1.69436100e+00])

>>> minVals

array([ 0.      ,  0.      ,  0.001156])

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

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

创建分类器针对约会网站的测试代码：

def datingClassTest():

    hoRatio = 0.50  # hold out 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 = classify0(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)

 

执行分类器测试程序：

>>> import importlib

>>> importlib.reload(kNN)

>>> kNN.datingClassTest()

the classifier came back with: 3, the real answer is: 3

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: 1, the real answer is: 1

..................................................................................

the classifier came back with: 1, the real answer is: 1

the classifier came back with: 1, the real answer is: 1

the classifier came back with: 2, the real answer is: 2

the total error rate is: 0.064000

33.0

 

分类器处理约会数据集的错误率是6.4%，这是一个相当不错的结果。我们可以改变函数datingClassTest内变量hoRatio和变量k的值，检测错误率是否随着变量值的变化而增加。

这个例子表明我们可以正确地预测分类，错误率仅仅是6.4%。海伦完全可以输入未知对象的属性信息，由分类软件来帮助她判定某一对象的可交往程度：讨厌、一般喜欢、非常喜欢。

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

综合上述代码，我们可以构建完整的约会网站预测函数：

def classifyPerson():

    resultList = ['not at all','in small doses','in large doses']

    percentTats = float(input("percentage of time spent playing video gemaes?"))

    #percentTats = float(raw_input("percentage of time spent playing video gemaes?"))#raw_input改为input

 
    ffMiles = float(input("frequent flier miles earned 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 = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)

    print("You will probably like this person: ",resultList [classifierResult - 1])

 

为了解程序的实际运行效果，输入如下命令：

>>> import importlib

>>> importlib.reload(kNN)

>>> kNN.classifyPerson()

percentage of time spent playing video gemaes?10

frequent flier miles earned per year?10000

liters of ice cream consumed per year?0.5

You will probably like this person:  in small doses

 

其中的粗体字是用户的输入。

目前为止，我们已经看到如何在数据上构建分类器。

3. 示例：手写识别系统

 本节我们一步步地构造使用&-近邻分类器的手写识别系统。为了简单起见，这里构造的系统只能识别数字0到9 ，参见图2.6。需要识别的数字已经使用图形处理软件，处理成具有相同的色

彩和大小 : 宽髙是32像素 X32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

示例：使用k-近邻算法的手写识别系统

(1)收集数据：提供文本文件。

(2)准备数据：编写函数classify 0 ( ) , 将图像格式转换为分类器使用的制格式。

(3)分析数据：在Python命令提示符中检查数据，确保它符合要求。

(4)训练算法：此步驟不适用于各近邻算法。

(5)测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记

为一个错误。

(6)使用算法：本例没有完成此步驟，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统。

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

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

为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个32x32的二进制图像矩阵转换为1 x 1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。我们首先编写一段函数img2vector，将图像转换为向量：该函数创建1 x 1024的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.])

 

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

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

手写数字识别系统的测试代码：

def handwritingClassTest():

    hwLabels = []

    trainingFileList = listdir('trainingDigits')  # load the training set

    m = len(trainingFileList)

    trainingMat = zeros((m, 1024))

    for i in range(m):

        fileNameStr = trainingFileList[i]

        fileStr = fileNameStr.split('.')[0]  # take off .txt

        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)

        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)))

在程序清单中，将trainingDigits目录中的文件内容存储在列表中，然后可以得到目录中有多少文件，并将其存储在变量m中。接着，代码创建一个m行1024列的训练矩阵，该矩阵的每行数据存储一个图像。我们可以从文件名中解析出分类数字 。该目录下的文件按照规则命名，如文件9_45.txt的分类是9，它是数字9的第45个实例。然后我们可以将类代码存储在hwLabels向量中，使用前面讨论的img2vector函数载入图像。在下一步中，我们对testDigits目录中的文件执行相似的操作，不同之处是我们并不将这个目录下的文件载人矩阵中，而是使用classify0()函数测试该目录下的每个文件。由于文件中的值已经在0和1之间，本节并不需要使用2.2节的autoNorm ()函数。

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

>>> import importlib

>>> importlib.reload(kNN)

>>> 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: 8

the classifier came back with: 8, 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的值、修改函数handwritingClassTest随机选取训练样本、改变训练样本的数目，都会对k-近邻算法的错误率产生影响，感兴趣的话可以改变这些变量值，观察错误率的变化。实际使用这个算法时，算法的执行效率并不高。因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次 ，此外，我们还需要为测试向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢？k决策树就是A-近邻算法的优化版，可以节省大量的计算开销。

4. 小结

k-近邻算法是分类数据最简单最有效的算法，本章通过两个例子讲述了如何使用k-近邻算法构造分类器。k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练数据集的很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。

k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。下一章我们将使用概率测量方法处理分类问题，该算法可以解决这个问题。