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

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

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

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

目录

​​一、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-近邻算法分类爱情片和动作片

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

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

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

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

表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模块，在模块中填写如下代码并保存：

#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

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

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

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

import kNN
group,labels = kNN.createDataSet()

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

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

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

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

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

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

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

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

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

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

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

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

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

2.Python代码

程序清单 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.利用欧式距离公式计算两个向量点的距离：

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

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

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

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

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

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

'dict' object has no attribute 'iteritems'

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

运行结果如下：

没有学过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）输入：文件名字符串；输出：训练样本矩阵和类标签向量。

程序清单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.代码中数据集下载地址（​​地址​​）。

3.代码运行

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

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

会产生报错：

代码报错1 reload错误

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

from imp import reload

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

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

代码报错2 数据集错误

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

datingTestSet.txt 文件内容

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

datingTestSet2.txt 文件内容

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

执行成功的代码如下：

datingDataMat

datingLabels[0:20]

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

1.Windows 系统安装 Matplotlib

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

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

下载安装过程

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.执行结果

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

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

3.个性化标记散点图

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],15.0*array(datingLabels),15.0*array(datingLabels)) #有标记散点图
plt.show()

2.执行结果

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

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

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

1.优点

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

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

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

2.执行结果

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

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

1.计算方法

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

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.执行结果

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的值来检测错误率是否随变量的变化而变化。

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.执行结果

第一组测试结果

第二组测试结果

三、示例：手写识别系统

1、步骤

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

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

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

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

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

（6）使用算法：。

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

1.准备数据集

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

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

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

部分示例如下：

trainingDigits文件夹

某一个数据集（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.执行结果

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.结果分析

输出结果

1.错误率较低

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

2.运算效率不高

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

四、总结

1、k-近邻算法优缺点

1.优点

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

2.缺点

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

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