机器学习实战—— Chap02.kNN

╰+哭是因爲堅強的太久メ 2023-06-13 11:17 120阅读 0赞

### 机器学习实战—— Chap02.kNN ###

*   *  一、k-邻近算法概述
     *   *  距离度量
         *  算法特点
         *  工作原理
         *  算法的一般流程
         *  K值选择
         *  小结
     *  二、kNN算法理想化实现
     *   *  0.数据准备
         *  1.算法实施
     *  三、实例一：改进约会网站的配对效果
     *   *  问题描述
         *  实现流程
         *   *  (1) 收集数据
             *  (2) 准备数据
             *  (3) 分析数据
             *  (4) 训练算法
             *  (5) 测试算法
             *  (6) 使用算法
     *  四、实例二.手写识别系统
     *   *  问题描述
         *  实现流程
         *   *  (1) 收集数据
             *  (2) 准备数据
             *  (3) 分析数据
             *  (4) 训练算法
             *  (5) 测试算法
             *  (6) 使用算法
     *  总结

## 一、k-邻近算法概述 ##

k-邻近算法，即 *K-Nearest Neighbors Algorithm*

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

### 距离度量 ###

这里提到`距离度量`的概念：

距离度量是用来描述不同元素之间距离远近的标准，而这种“标准”不只有一种。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]

最一般使用的度量单位，也是一般k-临近算法使用的，是欧氏距离。

### 算法特点 ###

*  优点：精度高、对异常值不敏感、无数据输入假定。
 *  缺点：计算复杂度高、空间复杂度高。
 *  适用数据范围：数值型和标称型。

### 工作原理 ###

•存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。

•输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。

•一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类

### 算法的一般流程 ###

•收集数据：可以使用任何方法

•准备数据：距离计算所需要的数值，最后是结构化的数据格式。

•分析数据：可以使用任何方法

•训练算法：（此步骤kNN中不适用)

•测试算法：计算错误率

•使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

### K值选择 ###

•如果选择较小的K值

1.  “学习”的近似误差（approximation error)会减小，但 “学习”的估计误差（estimation error) 会增大，
2.  噪声敏感
3.  K值的减小就意味着整体模型变得复杂，容易发生过 拟合.

•如果选择较大的K值

1.  减少学习的估计误差，但缺点是学习的近似误差会增大.
2.  K值的增大，就意味着整体的模型变得简单.

### 小结 ###

**由此，KNN算法的最重要的三个点可以总结为：**

1.  K值的确定
2.  权重设置：即虽然最后选择了K个数据作为参考依据，但K个数据与测试数据的相对位置各不相同，因此需要对K个数据进行不同的权重设置
3.  距离的度量方式：计算距离是使用`欧氏距离`还是`马氏距离`，`巴氏距离`，`曼哈顿距离`等等，亦或有其他算法。

## 二、kNN算法理想化实现 ##

注意：这一部分是完全架空，在理想、抽象的条件下，为了实现算法而构建的部分。实际应用时，无论是调用诸如sk-learn中封装好的函数，还是重写、设定参数，都会比下面这个复杂且完善。

### 0.数据准备 ###

*  导入了两个模块：第一个是科学计算包NumPy；第二个是运算符模块

from numpy import *
    import operator

*  定义`createDataSet()`函数，用于创建数据集和标签

def createDataSet():
        # 四组二维特征
        group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        # 四组特征的标签
        labels = ['A','A','B','B']
        return group, labels

### 1.算法实施 ###

*  kNN算法的伪代码

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

*  kNN算法实现 `classify0()`函数

二维坐标下，两个向量点的欧式距离计算：

d = ( x A 0 − x B 0 ) 2 + ( x A 1 − x B 1 ) 2 d=\\sqrt\{(xA\_0-xB\_0)^2+(xA\_1-xB\_1)^2\} d=(xA0−xB0)2\+(xA1−xB1)2

def classify0(inX, dataSet, labels, k):
        # numpy函数shape[0]返回dataSet的行数
        dataSetSize = dataSet.shape[0]
        # 将inX重复dataSetSize次并排成一列
        diffMat = tile(inX, (dataSetSize,1)) - dataSet
        # 二维特征相减后平方（用diffMat的转置乘diffMat）
        sqDiffMat = diffMat ** 2
        # sum()所有元素相加，sum(0)列相加，sum(1)行相加
        sqDistances = sqDiffMat.sum(axis = 1)
        # 开平方，计算出距离
        distances = sqDistances ** 0.5
        # argsort函数返回的是distances值从小到大的--索引值
        sortedDistIndicies = distances.argsort()  
        # 定义一个记录类别次数的字典
        classCount = {
        }
        # 选择距离最小的k个点
        for i in range(k):
            # 取出前k个元素的类别
            voteIlabel = labels[sortedDistIndicies[i]]
            # 字典的get()方法，返回指定键的值，如果值不在字典中返回0
            # 计算类别次数
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        # python3中用items()替换python2中的iteritems()
        # key = operator.itemgetter(1)根据字典的值进行排序
        # key = operator.itemgetter(0)根据字典的键进行排序
        # reverse降序排序字典
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        # 返回次数最多的类别，即所要分类的类别
        return sortedClassCount[0][0]

简单测试：

classify0([0,0], group, labels, 3)
    # 'B'

至此构造了第一个分类器，使用这个分类器可以完成很多分类任务。

## 三、实例一：改进约会网站的配对效果 ##

### 问题描述 ###

海伦使用约会网站寻找约会对象。经过一段时间之后，她发现曾交往过三种类型的人:

*  1：不喜欢的人
 *  2：魅力一般的人
 *  3：极具魅力的人

她希望：

*  不喜欢的人则直接排除掉
 *  工作日与魅力一般的人约会
 *  周末与极具魅力的人约会

现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。

### 实现流程 ###

#### (1) 收集数据 ####

案例中提供了文本文件，但是有一个小插曲：

原始的数据文件 datingTestSet.txt，其数据记录是数字与字符混合的：

![在这里插入图片描述][20191116210831294.png]  
这导致了读文件时出现报错`ValueError: invalid literal for int() with base 10: 'largeDoses'`。这种现象很常见，原始数据内部数据结构“混乱”，需要Data Cleaning。

……好在，还有一个datingTestSet2.txt文件，已经将三种不同的labels用数字1~3代替。更多时候需要我们实际修改。

海伦把这些约会对象的数据存放在文本文件 datingTestSet2.txt 中，总共有 1000 行。海伦约会的对象主要包含以下 3 种特征：

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

#### (2) 准备数据 ####

使用Python解析文本文件。讲文本记录通过NumPy转化为分类器可以接受的格式。

构建`file2matrix()`函数，以此来处理输入格式问题:

def file2matrix(filename):
        # 打开文件
        fr = open(filename)
        # 得到文件行数读后，取文件所有内容
        numberOfLines = len(fr.readlines()) 
        # 返回的NumPy矩阵numberOfLines行，3列
        returnMat = zeros((numberOfLines,3))      
        # 创建分类标签向量
        classLabelVector = []                       
        fr = open(filename)
        # 行的索引值
        index = 0
        
        # 解析文件数据到列表，读取每一行
        for line in fr.readlines():
            # 去掉每一行首尾的空白符，例如'\n','\r','\t',' '
            line = line.strip()
            # 将每一行内容根据'\t'符进行切片,本例中一共有4列
            listFromLine = line.split('\t')
            # 将数据的前3列进行提取保存在returnMat矩阵中，也就是特征矩阵
            returnMat[index,:] = listFromLine[0:3]
    #          #  如果还是使用原始数据集，需进行一下修改       
    #          # 根据文本内容进行分类1：不喜欢；2：一般；3：喜欢
    #         if listFromLine[-1] == 'didntLike':
    #             classLabelVector.append(1)
    #         elif listFromLine[-1] == 'smallDoses':
    #             classLabelVector.append(2)
    #         elif listFromLine[-1] == 'largeDoses':
    #             classLabelVector.append(3)
            # 增加一列-1，作为边界判定
            classLabelVector.append(int(listFromLine[-1]))
            index += 1
        # 返回标签列向量以及特征矩阵
        return returnMat,classLabelVector

#### (3) 分析数据 ####

使用Matplotlib画二维扩散图。

**画图这一段开始就有意思了**

*  Ver1.0 原书代码

import matplotlib
    import matplotlib.pyplot as plt
    datingdatamat, datinglabels =file2matrix('datingtestset2.txt')

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

fig = plt.figure()
    ax = fig.add_subplot(111) # 将画布分割成1行1列，图像画在从左到右从上到下的第1块
    ax.scatter(datingdatamat[:, 1], datingdatamat [:, 2])
    plt.show()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]  
调整ax.scatter()的参数

![0003](C:\Users\IvanZhang\Pictures\Coding\0003.png)fig2 = plt.figure()
    ax = fig2.add_subplot(111)
    ax.scatter(datingdatamat [:, 1], datingdatamat [:, 2], 15.0*array(datinglabels), 15.0*array(datinglabels))
    plt.show()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]

散点图改用列1和2的属性值却可以得到更好的效果,分别表示特征值“每年获取的飞行常客里程数”和“玩视频游戏所耗时间百分比”

fig3 = plt.figure()
    ax = fig3.add_subplot(111)
    ax.scatter(datingdatamat [:, 0], datingdatamat [:, 1], 15.0*array(datinglabels), 15.0*array(datinglabels))
    plt.show()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 3]

*  Ver2.0 改进版

import matplotlib.pyplot as plt
    import numpy as np
    
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    color = ['r', 'g', 'b']
    fig = plt.figure()
    ax = fig.add_subplot(311)
    for i in range(1, 4):
        index = np.where(np.array(datingLabels) == i)
        ax.scatter(datingDataMat[index, 0], datingDataMat[index, 1], c=color[i - 1], label=i)
    plt.xlabel('Col.0')
    plt.ylabel('Col.1')
    plt.legend()
    bx = fig.add_subplot(312)
    for i in range(1, 4):
        index = np.where(np.array(datingLabels) == i)
        bx.scatter(datingDataMat[index, 0], datingDataMat[index, 2], c=color[i - 1], label=i)
    plt.xlabel('Col.0')
    plt.ylabel('Col.2')
    plt.legend()
    cx = fig.add_subplot(313)
    for i in range(1, 4):
        index = np.where(np.array(datingLabels) == i)
        cx.scatter(datingDataMat[index, 1], datingDataMat[index, 2], c=color[i - 1], label=i)
    plt.xlabel('Col.1')
    plt.ylabel('Col.2')
    plt.legend()
    plt.show()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 4]

*  Ver3.0 进一步美化

from matplotlib.font_manager import FontProperties
    import matplotlib.lines as mlines
    import matplotlib.pyplot as plt
    
    def showdatas(datingDataMat, datingLabels):
    	#设置汉字格式
    	font = FontProperties(fname=r"C:\Windows\Fonts\simsunb.ttf", size=14)  ##需要查看自己的电脑是否会包含该字体
    	#将fig画布分隔成1行1列,不共享x轴和y轴,fig画布的大小为(13,8)
    	#当nrow=2,nclos=2时,代表fig画布被分为四个区域,axs[0][0]表示第一行第一个区域
    	fig, axs = plt.subplots(nrows=2, ncols=2,sharex=False, sharey=False, figsize=(13,8))
    
    	numberOfLabels = len(datingLabels)
    	LabelsColors = []
    	for i in datingLabels:
    		if i == 1:
    			LabelsColors.append('black')
    		if i == 2:
    			LabelsColors.append('orange')
    		if i == 3:
    			LabelsColors.append('red')
    	#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第二列(玩游戏)数据画散点数据,散点大小为15,透明度为0.5
    	axs[0][0].scatter(x=datingDataMat[:,0], y=datingDataMat[:,1], color=LabelsColors,s=15, alpha=.5)
    	#设置标题,x轴label,y轴label
    	axs0_title_text = axs[0][0].set_title(u'每年获得的飞行常客里程数与玩视频游戏所消耗时间占比',FontProperties=font)
    	axs0_xlabel_text = axs[0][0].set_xlabel(u'每年获得的飞行常客里程数',FontProperties=font)
    	axs0_ylabel_text = axs[0][0].set_ylabel(u'玩视频游戏所消耗时间占比',FontProperties=font)
    	plt.setp(axs0_title_text, size=9, weight='bold', color='red')  
    	plt.setp(axs0_xlabel_text, size=7, weight='bold', color='black')  
    	plt.setp(axs0_ylabel_text, size=7, weight='bold', color='black') 
    
    	#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
    	axs[0][1].scatter(x=datingDataMat[:,0], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5)
    	#设置标题,x轴label,y轴label
    	axs1_title_text = axs[0][1].set_title(u'每年获得的飞行常客里程数与每周消费的冰激淋公升数',FontProperties=font)
    	axs1_xlabel_text = axs[0][1].set_xlabel(u'每年获得的飞行常客里程数',FontProperties=font)
    	axs1_ylabel_text = axs[0][1].set_ylabel(u'每周消费的冰激淋公升数',FontProperties=font)
    	plt.setp(axs1_title_text, size=9, weight='bold', color='red')  
    	plt.setp(axs1_xlabel_text, size=7, weight='bold', color='black')  
    	plt.setp(axs1_ylabel_text, size=7, weight='bold', color='black') 
    
    	#画出散点图,以datingDataMat矩阵的第二(玩游戏)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
    	axs[1][0].scatter(x=datingDataMat[:,1], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5)
    	#设置标题,x轴label,y轴label
    	axs2_title_text = axs[1][0].set_title(u'玩视频游戏所消耗时间占比与每周消费的冰激淋公升数',FontProperties=font)
    	axs2_xlabel_text = axs[1][0].set_xlabel(u'玩视频游戏所消耗时间占比',FontProperties=font)
    	axs2_ylabel_text = axs[1][0].set_ylabel(u'每周消费的冰激淋公升数',FontProperties=font)
    	plt.setp(axs2_title_text, size=9, weight='bold', color='red')  
    	plt.setp(axs2_xlabel_text, size=7, weight='bold', color='black')  
    	plt.setp(axs2_ylabel_text, size=7, weight='bold', color='black') 
    	#设置图例
    	didntLike = mlines.Line2D([], [], color='black', marker='.',
                          markersize=6, label='didntLike')
    	smallDoses = mlines.Line2D([], [], color='orange', marker='.',
    	                  markersize=6, label='smallDoses')
    	largeDoses = mlines.Line2D([], [], color='red', marker='.',
    	                  markersize=6, label='largeDoses')
    	#添加图例
    	axs[0][0].legend(handles=[didntLike,smallDoses,largeDoses])
    	axs[0][1].legend(handles=[didntLike,smallDoses,largeDoses])
    	axs[1][0].legend(handles=[didntLike,smallDoses,largeDoses])
    	#显示图片
    	plt.show()
        
    showdatas(datingDataMat, datingLabels)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 5]

**归一化数值** 构建`autoNorm()`函数

def autoNorm(dataSet):
        # 获取数据的最小值
        minVals = dataSet.min(0)
        # 获取数据的最大值
        maxVals = dataSet.max(0)
        # 最大值和最小值的范围
        ranges = maxVals - minVals
        # shape(dataSet)返回dataSet的矩阵行列数
        normDataSet = zeros(shape(dataSet))
        # numpy函数shape[0]返回dataSet的行数
        m = dataSet.shape[0]
        # 原始值减去最小值（x-xmin）
        normDataSet = dataSet - tile(minVals, (m,1))
        # 差值处以最大值和最小值的差值（x-xmin）/（xmax-xmin）
        normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide
        # 归一化数据结果，数据范围，最小值
        return normDataSet, ranges, minVals

#### (4) 训练算法 ####

此步骤不适用于k-近邻算法。因为测试数据每一次都要与全部的训练数据进行比较，所以这个过程是没有必要的。

形式就如“理想化实现”中的代码

import operator
    
    def classify0(inX, dataSet, labels, k):
        dataSetSize = dataSet.shape[0]
        # 距离度量 度量公式为欧氏距离
        diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
        sqDiffMat = diffMat ** 2
        sqDistances = np.sum(sqDiffMat, axis=1)
        distances = sqDistances ** 0.5
        # 将距离排序：从小到大
        sortedDistIndicies = distances.argsort()
        # 选取前K个最短距离， 选取这K个中最多的分类类别
        classCount = {
        }
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
        return sortedClassCount[0][0]

#### (5) 测试算法 ####

计算错误率，使用海伦提供的部分数据作为测试样本。如果预测分类与实际类别不同，则标记为一个错误。

def datingClassTest():
        # 取所有数据的10% hoRatio越小，错误率越低
        hoRatio = 0.10
        # 将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中
        datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
        # 数据归一化，返回归一化数据结果，数据范围，最小值
        normMat,ranges,minVals = autoNorm(datingDataMat)
        # 获取normMat的行数
        m = normMat.shape[0]
        # 10%的测试数据的个数
        numTestVecs = int(m * hoRatio)
        # 分类错误计数
        errorCount = 0.0
        
        for i in range(numTestVecs):
            # 前numTestVecs个数据作为测试集，后m-numTestVecs个数据作为训练集
            # k选择label数+1（结果比较好）
            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)))

the total error rate is:0.050000

#### (6) 使用算法 ####

产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

约会网站预测函数如下：

def classifyPerson():
        # 定义输出结果
        resultList = ['not at all','in small doses','in large doses']
        # 三维特征用户输入
        percentTats = float(input("percentage of time spent playing video games?"))
        ffMiles = float(input("frequent flier miles earned per year?"))
        iceCream = float(input("liters of ice creram consumed per year?"))
        datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
        # 训练集归一化
        normMat, ranges, minVals = autoNorm(datingDataMat)
        # 生成NumPy数组，测试集
        inArr = array([ffMiles,percentTats,iceCream])
        # 测试集归一化
        norminArr = (inArr - minVals) / ranges
        # 返回分类结果
        classifierResult = classify0(norminArr, normMat, datingLabels, 3)
        print("you will probably like this person: ",resultList[classifierResult -1])

classifyPerson()
    '''
    percentage of time spent playing video games?10000
    frequent flier miles earned per year?10
    liters of ice creram consumed per year?0.5
    you will probably like this person:  not at all
    '''

## 四、实例二.手写识别系统 ##

### 问题描述 ###

构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。

需要识别的数字是存储在文本文件中的具有相同的色彩和大小：宽高是 32 像素 \* 32 像素的黑白图像。

### 实现流程 ###

#### (1) 收集数据 ####

本案例书中提供了文本文件。

目录 trainingDigits 中包含了大约 2000 个例子，每个例子内容如下图所示，每个数字大约有 200 个样本；目录 testDigits 中包含了大约 900 个测试数据。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 6]

#### (2) 准备数据 ####

编写函数 `img2vector()`， 将图像文本数据转换为分类器使用的向量。

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

#### (3) 分析数据 ####

在 Python 命令提示符中检查数据，确保它符合要求。

testvector = 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.])

#### (4) 训练算法 ####

此步骤不适用于 k-近邻算法。因为测试数据每一次都要与全部的训练数据进行比较，所以这个过程是没有必要的。

#### (5) 测试算法 ####

计算错误率，编写函数使用提供的部分数据集作为测试样本，如果预测分类与实际类别不同，则标记为一个错误。

def handwritingClassTest():
        # 1. 导入训练数据
        hwLabels = []
        trainingFileList = listdir('trainingDigits')           #load the training set
        m = len(trainingFileList)
        trainingMat = zeros((m,1024))
        # hwLabels存储0～9对应的index位置， trainingMat存放的每个位置对应的图片向量
        for i in range(m):
            fileNameStr = trainingFileList[i]
            fileStr = fileNameStr.split('.')[0]     #take off .txt
            classNumStr = int(fileStr.split('_')[0])
            hwLabels.append(classNumStr)
             # 将 32*32的矩阵->1*1024的矩阵
            trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
        
        # 2. 导入测试数据
        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)))

handwritingClassTest()
    '''
    the total number of errors is: 10
    
    the total error rate is: 0.010571
    '''

#### (6) 使用算法 ####

可以构造一个小的软件系统，从图像中提取数字，并完成数字识别，我们现实中使用的OCR，以及车牌识别都类似于这样的系统。

## 总结 ##

**KNN的主要优点有：**

1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归

2） 可用于非线性分类

3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)

4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感

5） 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合

6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分

**KNN的主要缺点有：**

1）计算量大，尤其是特征数非常多的时候

2）样本不平衡的时候，对稀有类别的预测准确率低

3）KD树，球树之类的模型建立需要大量的内存

4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢

5）相比决策树模型，KNN模型可解释性不强

k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练数据集的很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。  
k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191116210744451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70
[20191116210831294.png]: https://img-blog.csdnimg.cn/20191116210831294.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019111621093485.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191116210943354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191116210952323.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191116211003324.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191116211016630.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191116211029712.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ==,size_16,color_FFFFFF,t_70