【机器学习实战学习笔记】之 2 k-近邻算法

小鱼儿 2021-09-17 23:40 733阅读 0赞

本学习笔记参考书目《机器学习实战》第二章。

本章所有本书对应代码及数据集下载请点击（[下载链接][Link 1]）。

本文中博主自己写的代码如有需要，请点击（[下载链接][Link 2]）。

**目录**

一、k-近邻算法概述

1、引入

2、k-近邻算法（kNN）

3、Python实现

二、k-近邻算法应用-改进约会网站的配对效果

1、步骤

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

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

4、准备数据：归一化数值

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

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

三、示例：手写识别系统

1、步骤

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

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

四、总结

1、k-近邻算法优缺点

--------------------

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

## 1、引入 ##

### 1.分类标准引发的问题 ###

以电影为例，电影按照题材分类，如何区分电影的类型？相同类型的电影有哪些共同特征？不同类型电影也会有相同的镜头，如何区分并成功分类？

## 2、**k-近邻算法（kNN）**

**1.定义**

k-近邻算法是机器学习算法，**采用测量不同特征值之间的距离的方法进行分类**。

### 2.算法特点 ###

（1）**优点：**进度高，对异常值不敏感，无数据输入假定。

（2）**缺点：**计算复杂度高，空间复杂度高。

（3）**适用数据范围：**数值型与标称型。

### 3.工作原理 ###

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

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

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

（3）最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。。

### 4.举例 ###

例：使用k-近邻算法分类爱情片和动作片

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FF45FF_t_70][] 图2-1  6部电影的打斗和接吻镜头数

（1）给定一个类型未知的电影，**确定**电影存在多少个打斗镜头和接吻**镜头**。图2-1中问号位置是该未知电影出现的镜头数图形化展示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_F92FFF_t_70][] 表2 - 1  每部电影的打斗镜头数、接吻镜头数以及电影评估类型

（2）**计算**未知电影与样本集中其他电影的**距离**（此处暂时不考虑距离值如何计算）

![20190128195928818.png][] 表2 - 2   已知电影与未知电影的距离

（3）按照距离**递增排序**，可以**找到k个距离最近的电影**。若假定k = 3，得到三个最靠近的电影依次是：He's Not Really into Dudes、Beautiful Woman、California Man。这三部电影均为爱情片，从而推测未知电影是爱情片

### 5.k-近邻算法一般流程 ###

（1）**搜集数据**

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

（3）**分析数据**

（4）**训练算法**：此步驟不适用于k - 近邻算法。

（5）**测试算法**：计算错误率。

（6）**使用算法**：a.需要输入样本数据和结构化的输出结果；

b.运行女-近邻算法判定输入数据分别属于哪个分类；

c.应用对计算出的分类执行后续的处理。

## 3、Python实现 ##

**注：**在学习这块知识时，我对Python的包、模块等概念并不是特别熟悉，可能我在这里采取的方法不是最好的，但是对于初学者来说，如果你在看这本书时，对书中提到的有关于模块的创建于调用不是很熟悉，可以先按照我对步骤来做，先按我的方法将理论学好。如果你对Python有很深刻的了解，或者知道书中相关概念的含义，知道书中所说是什么步骤，欢迎大家与我一起交交流。

### 1.**准备：使用Python导入数据**

1.**创建 kNN.py 的 Python模块**，在模块中填写如下代码并保存：

**2.将kNN文件转存到python.exe文件所在文件夹下（此部分并非按照书中所讲操作）**。如果对自己的安装路径不熟悉，你可以从开始菜单找到Python然后打开文件所在位置。或者尝试去C盘、D盘等你经常安装文件的地方去寻找，如果你没有修改安装路径的习惯，路径一般是：

> C:\\Program Files (x86)\\Python\\Python36

![20190131152049537.png][]

3.**双击python.exe文件，并输入如下代码：**

import kNN
    group,labels = kNN.createDataSet()

回车后输入group，回车，输入labels，回车。如下图所示：

![20190131154409909.png][]

（1）上面一共是4组数据，每组数据有两个已知的属性或者特征值。

（2）group矩阵每行包含一个不同的数据（可以把它想象为某个日志文件中不同的测量点或者入口）。

（3）人类大脑通常只能可视化处理三维以下的事务。为了简单地实现数据可视化，每个数据点通常只使用两个特征。

（4）向量labels包含了每个数据点的标签信息，labels包含的元素个数等于group矩阵行数。将数据点(1，1.1)定义为类A，数据点(0, 0.1)定义为类B （例子中的数值是任意选择的，并没有给出轴标签）。如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFF15F_t_70][] 图 2 - 2  k-近邻算法：带有4个数据点的简单例子

### 2.**从文本文件中解析数据**

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

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

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

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

(4) 确定前k个点所在类别的出现频率；

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

**2.Python代码**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFF85F_t_30][] 程序清单 2-1  k-近邻算法

（1）Python代码

#coding=utf-8
    
    from numpy import *
    
    def classify0(inX, dataSet, labels, k):
        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()#argsort（）是numpy库中的函数，返回的是数组值从小到大的索引值
        classCount = {}
        
        #选择距离最小的k个点 开始
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        #选择距离最小的k个点 结束
        
        
        sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1), reverse = True) #排序
        return sortedClassCount[0][0]

（2）代码解析

a.classify0()  函数有**四个输入参数**：**inX（用于分类的输入向量）、dataSet（输入的样本训练集）、labels（标签向量）、k（用于选择最近邻居的数目）**

b.**标签向量的元素数目和矩阵dataSet的行数相同**。

c.利用欧式距离公式**计算两个向量点的距离**：

![20190201112814860.png][]

注：如果存在四个特征值，以点（1,0,0,1） 和（7,6,9,4）为例，两点间距离计算为：

![20190201113336685.png][]

d.计算完所有点之间的距离后，对数据按照从小到大的次序排序，确定前k个距离最小元素所在的主要分类。

e.，将classCount字典分解为元组列表，使用程序第二行导入运算符模块的 itemgetter 方法，按照第二个元素的次序对元组进行排序（此处排序为逆序，即从大到小排序），返回发生频率最高的元素标签。

f.在python提示符中输入下列命令来预测数据所在分类。

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

**注：在这里有很多人在调用代码时都会报错：**

> 'dict' object has no attribute 'iteritems'

如果大家遇到这种问题，请点击（[解决方案][Link 3]）解决。

运行结果如下：

![20190201162610567.png][]

没有学过Python的同学，可能对黑窗体执行代码和用PyCharm执行代码中的代码转化不太了解，上面这个我是通过PyCharm执行的，全部代码如下：

#coding=utf-8
    
    from numpy import * # 科学计算包numpy
    import operator     #运算符模块
    
    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
    
    def classify0(inX, dataSet, labels, k):
        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 = {}
    
        #选择距离最小的k个点 开始
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]]
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        #选择距离最小的k个点 结束
    
    
        sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1), reverse = True) #排序
        return sortedClassCount[0][0]
    
    group,labels = createDataSet()
    
    print(classify0([0,0],group,labels,3))

### 3.测试分类器 ###

**1.测试原因**

检验分类器是否总是正确及正确率与错误率是多少。

**2.错误率**

（1）分类器给出错误结果的次数除以测试执行的总数。

（2）完美分类器的错误率为0 , 最差分类器的错误率是1.0。

# 二、k-近邻算法应用-改进约会网站的配对效果 #

## 1、步骤 ##

（1）**搜集数据**：提供文本文件

（2）**准备数据**：使用Python解析文本文件。

（3）**分析数据**：使用 Matplotlib 画二维扩散图

（4）**训练算法**：此步驟不适用于k - 近邻算法。

（5）**测试算法**：使用用户提供的部分数据作为测试样本。（测试样本和非测试样本的**区别**在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。）

（6）**使用算法**：产生简单的命令行程序，用户可以输入一些特征数据以判断对方是否为自己喜欢的类型。

## 2、准备数据：从文本文件中解析数据 ##

### 1.数据示例 ###

**1.数据信息**

每个样本数据占一行，共1000行。

**2.数据特征**

（1）每年获得的飞行常客里程数；

（2）玩视频游戏所消耗的时间百分比；

（3）每周消费的冰淇淋公升数。

### 2.数据处理 ###

**1.处理原因**

将特征数据输人到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。

**2.Python代码**

（1）创建file2matrix函数处理格式问题。

（2）**输入：**文件名字符串；**输出：**训练样本矩阵和类标签向量。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_89FFFF_t_70][] 程序清单2 - 2  将文本记录到转换NumPy的解析程序

（3）Python代码

上图中有一处代码错误，for循环后面需要加上一个冒号；全部代码如下

#文本记录解析程序
    def file2matrix(filename):
        
        #打开文件并获取文件有多少行 开始
        fr = open(filename)
        arrayOLines = fr.readlines()
        numberOfLines = len(arrayOLines)
        #打开文件并获取文件有多少行 结束
        
        #创建返回的NumPy矩阵
        returnMat = zeros((numberOfLines,3))
        classLabelVector = []
        index = 0
        
        #解析文件数据到列表 开始
        for line in arrayOLines:
            line = line.strip()
            listFromLine = line.split('\t')
            returnMat[index,:] = listFromLine[0:3]
            classLabelVector.append(int(listFromLine[-1]))
            index += 1
        #解析文件数据到列表 结束
        return returnMat,classLabelVector

（4）代码解析

a.**open()用于打开文件，fr.readlines()及numberOfLines = len(arrayOLines)用于获取文件的行数**

b.**创建以零填充的矩阵NumPy**（为了简化处理，我们将该矩阵的另一维度设置为固定值3）。

c.需要明确通知解释器，告诉它列表中存储的元素值为整型（否则会当做字符串来处理），：

d.代码中数据集下载地址（[地址][Link 4]）。

**3.代码运行**

（1）在命令提示符中输入以下代码

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

会产生报错：

![20190202175320220.png][] 代码报错1 reload错误

需要在前面引入一个包，（产生原因是因为作者使用的Python与我的不同 ）。

from imp import reload

注：此步骤是为了重新加载kNN模块，如果重新打开的命令提示符，无需重新加载。

解决上面的问题，还会有下一个问题：

![20190202204251338.png][] 代码报错2 数据集错误

产生的原因是datingTestSet.txt文件中最后一列不是数值型的，datingTestSet.txt文件如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FF25FF_t_30][] datingTestSet.txt 文件内容

而我们代码中要求是数值型的，所以最简单的方式是我们使用datingTestSet2.txt文件。datingTestSet2.txt文件如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_F582FF_t_30][] datingTestSet2.txt 文件内容

**注：两个数据集第四列对应关系如下**：

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td style="border-color:#ccff66;text-align:center;vertical-align:middle;width:500px;">datingTestSet.txt 数据集</td> 
 <td style="border-color:#ccff66;text-align:center;vertical-align:middle;width:500px;">datingTestSet2.txt 数据集</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:500px;">largeDoses</td> 
 <td style="text-align:center;vertical-align:middle;width:500px;">3</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:500px;">smallDoses</td> 
 <td style="text-align:center;vertical-align:middle;width:500px;">2</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:500px;">didntLike</td> 
 <td style="text-align:center;vertical-align:middle;width:500px;">1</td> 
 </tr> 
 </tbody> 
</table>

执行成功的代码如下：

![20190202214213553.png][] datingDataMat

![20190202214328264.png][] datingLabels\[0:20\]

## 3、分析数据：使用Matplotlib创建散点图 ##

### 1.Windows 系统安装 Matplotlib ###

打开cmd，并输入如下两句话

python -m pip install -U pip setuptools
    python -m pip install matplotlib

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_F5256F_t_70][] 下载安装过程

### 2.无样本类别标签的散点图 ###

**1.Python代码**

#coding=utf-8
    
    from numpy import * # 科学计算包numpy
    import operator     #运算符模块
    import matplotlib
    import matplotlib.pyplot as plt
    
    #文本记录解析程序
    def file2matrix(filename):
    
        #打开文件并获取文件有多少行 开始
        fr = open(filename)
        arrayOLines = fr.readlines()
        numberOfLines = len(arrayOLines)
        #打开文件并获取文件有多少行 结束
    
        #创建返回的NumPy矩阵
        returnMat = zeros((numberOfLines,3))
        classLabelVector = []
        index = 0
    
        #解析文件数据到列表 开始
        for line in arrayOLines:
            line = line.strip() #截取掉回车字符
            listFromLine = line.split('\t') #用 \t 将上一步得到的整行数据分割成一个元素列表
            returnMat[index,:] = listFromLine[0:3] #选取前3个元素，并存储到特征矩阵中
            classLabelVector.append(int(listFromLine[-1])) #索引值-1表示列表中的最后一列元素
            index += 1
        #解析文件数据到列表 结束
        return returnMat,classLabelVector
    
    #加载数据集
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    #print(datingDataMat)
    #print(datingLabels[0:20])
    
    #数据集图像化
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(datingDataMat[:,1],datingDataMat[:,2])
    plt.show()

**2.执行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_F7558F_t_30][] 没有样本类别标签的约会数据散点图

没有样本类别标签的约会数据散点图。难以辨识图中的点究竟属于哪个样本分类。一般采用色彩或其他记号来标记不同的样本分类。

### 3.个性化标记散点图 ###

**1.Python代码**

主要修改了倒数第二行代码，给函数又加上了新的参数，全部代码如下：

**2.执行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_FF585F_t_30][] 带有样本分类标签的约会数据散点图

虽然能够比较容易地区分数据点从属类别，但依然很难根据这张图得出结论性信息。

### 4.采用不同属性值的散点图 ###

**1.优点**

（1）采用不同的属性值可以得到更好效果；

（2）清晰地标识了三个不同的样本分类区域；

（3）具有不同爱好的人其类别区域也不同

**2.执行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_FF852F_t_30][]

## 4、准备数据：归一化数值 ##

### 1.普通方法计算样本距离 ###

**1.计算方法**

![2019020308564649.png][]

计算样本3与样本4的距离：

![20190203085745295.png][]

**2.存在问题**

飞行常客由于数值极大，影响远大于另外两个特征值。

**3.解决方案**

将数值归一化（将取值范围处理为 0到1 或者 -1到1 之间）

### 2.数值归一化 ###

**1.归一化函数**

#归一化特征值
    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)) #tile()函数将变量内容复制成输人矩阵同样大小的矩阵
        normDataSet = normDataSet/tile(ranges,(m,1))
        return normDataSet,ranges,minVals

**2.运行代码**

normMat,ranges,minVals = autoNorm(datingDataMat)
    print("normMat = ")
    print(normMat)
    
    print("ranges = ")
    print(ranges)
    
    print("minVals = ")
    print(minVals)

**3.执行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FF35FF_t_30][]

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

### 1.测试原理 ###

1.测试最原始的方法是：提供已有数据的90%作为训练样本来训练分类器，使用剩余的10%测试分类器，检验正确率。10%的测试数据需要随机选择。

2.定义一个计数器变量，每次分类器错误的分类，计数器+1，程序执行完成后，错误率 = 计数器结果/数据点总数。

**2.存在问题**

飞行常客由于数值极大，影响远大于另外两个特征值。

**3.解决方案**

将数值归一化（将取值范围处理为 0到1 或者 -1到1 之间）

### 2.测试算法 ###

**1.Python代码**

**注：**原书中部分代码采用旧版Python的代码，由于我使用3.x版本，所以部分代码与原书中有出入，主要是输出与原书中不同**。**

def datingClassTest():
        hoRatio = 0.10
        datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
        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])
            print('the classifier came back with: {}, the real answer is : {}'.format(classifierResult,datingLabels[i]))
            if(classifierResult != datingLabels[i]):
                errorCount += 1.0
        #print "the total error rate is : %f" %(errorCount/float(numTestVecs))
        print('the total error rate is : {}'.format(errorCount/float(numTestVecs)))

**2.执行结果**

全部执行结果大家可以自己去运行，在这里，我只给大家看一下部分代码，让大家对算法执行效果能有一定的了解。

> the classifier came back with: 3, the real answer is : 3
> 
> 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: 3, the real answer is : 1
> 
> the total error rate is : 0.05

**3.结果分析**

分类器处理约会数据集的错误率为5%，我们可以改变函数中hoTatio和k的值来检测错误率是否随变量的变化而变化。

<table style="width:435px;"> 
 <tbody> 
 <tr> 
 <td style="border-color:#ccff33;text-align:center;vertical-align:middle;width:200px;">hoRatio</td> 
 <td style="border-color:#ccff33;text-align:center;vertical-align:middle;width:200px;">k</td> 
 <td style="border-color:#ccff33;text-align:center;vertical-align:middle;width:232px;">errorRate</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:200px;">0.02</td> 
 <td style="text-align:center;vertical-align:middle;width:200px;">3</td> 
 <td style="text-align:center;vertical-align:middle;width:232px;">0.0000&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:200px;">0.05</td> 
 <td style="text-align:center;vertical-align:middle;width:200px;">3</td> 
 <td style="text-align:center;vertical-align:middle;width:232px;">0.0200&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:200px;">0.08</td> 
 <td style="text-align:center;vertical-align:middle;width:200px;">3</td> 
 <td style="text-align:center;vertical-align:middle;width:232px;">0.0250&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:200px;">0.1</td> 
 <td style="text-align:center;vertical-align:middle;width:200px;">3</td> 
 <td style="text-align:center;vertical-align:middle;width:232px;">0.0500&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:200px;">0.2</td> 
 <td style="text-align:center;vertical-align:middle;width:200px;">3</td> 
 <td style="text-align:center;vertical-align:middle;width:232px;">0.0800&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;vertical-align:middle;width:200px;">0.4</td> 
 <td style="text-align:center;vertical-align:middle;width:200px;">3</td> 
 <td style="text-align:center;vertical-align:middle;width:232px;">0.0775&nbsp;</td> 
 </tr> 
 </tbody> 
</table>

## 6、使用算法：构建完整可用系统 ##

### 1.算法源码 ###

#约会网站预测函数
    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 years?'))
        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  : {}'.format(resultList[classifierResult - 1]))

**注：**原书中部分代码采用旧版Python的代码，由于我使用3.x版本，所以部分代码与原书中有出入，主要是输入、输出与原书中不同**。**

### 2.测试算法 ###

**1.Python代码**

classifyPerson()

**2.执行结果**

![2019020319185511.png][] 第一组测试结果

![20190203192016586.png][] 第二组测试结果

# 三、示例：手写识别系统 #

## 1、步骤 ##

（1）**搜集数据**：提供文本文件

（2）**准备数据**：编写函数classify0 ( ) 函数，将图像格式转换为分类器使用的list格式。

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

（4）**训练算法**：此步驟不适用于k - 近邻算法。

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

（6）**使用算法**：。

## 2、准备数据：将图像转换为测试向量 ##

### 1.准备数据集 ###

点击文章开头的下载地址下载所有的数字样本，包括trainingDigits文件夹和testDigits文件夹。详情如下：

（1）trainingDigits中有2000左右个例子，包括0-9十个数字，每个数字有200个左右样本。

（2）testDigits中有900左右个例子.

部分示例如下：

![20190203193611468.png][] trainingDigits文件夹

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FF85FF_t_70][] 某一个数据集（32×32）

###  2.转化为向量 ###

为了使用前面的分类器，需要先将图像格式化处理为一个向量。即将32×32的二进制图像转换为1×1024的向量。

**1.Python代码**

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

**2.运行代码**

testVector = img2vector('digits/testDigits/0_1.txt')
    print(testVector[0,0:31])
    print(testVector[0,32:63])

**3.执行结果**

![20190203200908934.png][]

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

### 1.手写识别系统测试代码 ###

#手写识别系统测试代码
    def handwritingClassTest():
        hwLabels = []
        trainingFileList = listdir('digits/trainingDigits') #获取目录内容
        m = len(trainingFileList) #目录中文件个数
        trainingMat = zeros((m,1024)) #每行数据存储一个图像
        for i in range(m):
            #从文件名解析分类数据 开始
            fileNameStr = trainingFileList[i]
            fileStr = fileNameStr.split('.')[0]
            classNumberStr = int(fileStr.split('_')[0])
            #从文件名解析分类数据 结束
            hwLabels.append(classNumberStr)
            trainingMat[i,:] = img2vector('digits/trainingDigits/%s' %fileNameStr)
        testFileList = listdir('digits/testDigits')
        errorCount = 0.0
        mTest = len(testFileList)
        for i in range(mTest):
            fileNameStr = testFileList[i]
            fileStr = fileNameStr.split(',')[0]
            classNumberStr = int(fileStr.split('_')[0])
            vectorUnderTest = img2vector('digits/testDigits/%s' %fileNameStr)
            classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)
            print('the classifier came back with : {}, the real answer is : {}'.format(classifierResult,classNumberStr))
            if(classifierResult != classNumberStr):
                errorCount += 1.0
        print('\nthe total number of errors is : {}'.format(errorCount))
        print('\nthe total error rate is : {}'.format(errorCount/float(mTest)))

### 2.运行代码 ###

**注：**这个代码是直接写在PyCharm中的，书中是在命令提示符中运行，代码有所区别。

handwritingClassTest()

**3.结果分析**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_42FFFF_t_30][] 输出结果

**1.错误率较低**

训练的数据集错误率仅仅约0.0106，不足1.1%，改变变量k的值、训练样本等都会对结果产生影响。

**2.运算效率不高**

运行时每个向量要做2000次距离计算，每个距离计算包括10224个维度浮点运算。计算机会消耗大量开销。（使用笔记本电脑能明显听到运行代码时，CPU中的风扇会狂转）

# 四、总结 #

## 1、k-近邻算法优缺点 ##

### 1.优点 ###

**最简单最有效**的数据分类算法。

### 2.缺点 ###

1.**效率低**，运算耗时，不适合数据量大的数据集。（**解决方案：**使用k决策树，即k-近邻算法优化版）

2.**无法给出任何数据的基础结构信息**，**无法知晓平均实例样本和典型实例样本具有什么特征**。（**解决方案：**使用概率测量方法处理分类问题）

[Link 1]: https://download.csdn.net/download/shuiyixin/10948884
[Link 2]: https://github.com/PureWaterLove/MachineLearningInAction
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FF45FF_t_70]: /images/20210516/103c471defc24e5997485394259e60ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_F92FFF_t_70]: /images/20210516/d42ec1a389df493cbf719610159a7d2a.png
[20190128195928818.png]: /images/20210516/eacad054d3374f6281199807afc3efb0.png
[20190131152049537.png]: /images/20210516/458266309ebc497285ba749221d8c6e7.png
[20190131154409909.png]: /images/20210516/3bfe538d180d4d868bc207c1af639675.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFF15F_t_70]: /images/20210516/7cbc45d35a6c4d5d8c99269eaee7eab8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFF85F_t_30]: /images/20210516/a2c4bd2110fa4a41bd37091f9d63e2a2.png
[20190201112814860.png]: /images/20210516/7b8a40539e5a452ca834faa45e9c7386.png
[20190201113336685.png]: /images/20210516/58e2561e9af24742b472a1fb9d652fe6.png
[Link 3]: https://blog.csdn.net/shuiyixin/article/details/86741810
[20190201162610567.png]: /images/20210516/2996a82a1cf9417a8f52d62aa9bf260f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_89FFFF_t_70]: /images/20210516/3ac376219a1149e587d597777359a248.png
[Link 4]: https://download.csdn.net/download/shuiyixin/10948387
[20190202175320220.png]: /images/20210516/5898134bd46c4a41b89ca92b75c86fa0.png
[20190202204251338.png]: /images/20210516/3d6494f7a0d94016a1166cdac802aba9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FF25FF_t_30]: /images/20210516/4d572ee5e9d74e5c9823bf87e92ed81c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_F582FF_t_30]: /images/20210516/2331a908454c4473ae2f61324111e5db.png
[20190202214213553.png]: /images/20210516/99aca81c317242169d3a9e8bf5f28438.png
[20190202214328264.png]: /images/20210516/dd9e5640ada849fe9337a4c9a85fe2e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_F5256F_t_70]: /images/20210516/12309adcfc4d4f6d9b36e255920fae0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_F7558F_t_30]: /images/20210516/9d8203606b3c41258270bacbe3dc30fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_FF585F_t_30]: /images/20210516/36d0f408d9024e8892d3fa01fb4b5573.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_FF852F_t_30]: /images/20210516/49320b0a7046432c9408494161c8184d.png
[2019020308564649.png]: /images/20210516/cd56dd98e58f46cf87fe54dfd0fd2881.png
[20190203085745295.png]: /images/20210516/3d6fc9f7a38541f5bc9b96d37a75f74a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FF35FF_t_30]: /images/20210516/440f22df4fcb4b7186d1269d82fbf82c.png
[2019020319185511.png]: /images/20210516/284a9486670543abafbd53e8e3b32c07.png
[20190203192016586.png]: /images/20210516/c55e6b4712f54bb8ab6bd96a51250792.png
[20190203193611468.png]: /images/20210516/c7909f65f37847e5968911920fca5ba0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FF85FF_t_70]: /images/20210516/aab33077782340eeb38927e380899943.png
[20190203200908934.png]: /images/20210516/76392b8f7d504f29b63325fb45467eb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_42FFFF_t_30]: /images/20210516/d05928350c7c47769cc5c4f821e84b62.png