《机器学习实战》读书笔记之一:k-近邻算法原理与代码实现详解


一、前言

本系列文章是学习《机器学习实战》一书的读书笔记,并非按原文照抄,而是在理解原书的基础上融入了本人个人理解。同时,原书代码是基于Python2实现的,而本系列文章所有代码是用Python3实现的,因此代码与原书也会稍有不同。如果你使用本系列文章的代码,请一定在Python3下运行,否则你会遇到意想不到的问题。

此文是《机器学习实战》的读书笔记的第一篇,介绍该书中讲解的第一个机器学习算法:k-近邻算法,也称kNN(k-NearestNeighbor的缩写)算法。

二、算法原理

将输入数据的每个特征数据与训练样本集对应的特征数据进行比较,从而提取出样本集中特征最相似(即最邻近)的k个数据,将这k个数据中比例最高的分类标签作为输入数据的分类标签。 由于每个训练样本数据都是有标签的,所以kNN算法是监督学习的一种算法。

1. 举例说明

假设有一组电影分类的样本数据集,根据电影中打斗镜头数和接吻镜头数的不同,被区分为动作片和爱情片。

有如下7部电影样本数据,其中6部已知类型,1部未知类型。我们希望从这6部电影中找到某种规律,从而预测未知类型的“电影7”属于什么类型。

电影名称 打斗镜头数 接吻镜头数 电影类型
电影1 3 104 爱情片
电影2 2 100 爱情片
电影3 1 81 爱情片
电影4 101 10 动作片
电影5 99 5 动作片
电影6 98 2 动作片
电影7 18 90

将上面样本数据在图中表示出来:

完整代码在这里

import numpy as np
import matplotlib.pyplot as plt

x=np.array([3,2,1,101,99,98,18])
y=np.array([104,100,81,10,5,2,90])

colors = (['black','black','black','black','black','black','red'])
plt.scatter(x, y, c=colors)

plt.xlabel('打斗镜头数')
plt.ylabel("接吻镜头数")
plt.rcParams['font.sans-serif'] = ['FangSong']
plt.rcParams['axes.unicode_minus'] = False
plt.show()

图中6个黑色的点表示上面样本数据集中的6部已知类型的电影,其中3部爱情片,3部动作片。红色的点表示我们将要预测的未知类型的“电影7”。

根据kNN算法原理,我们需要首先计算出图中红色点与所有黑色点的距离。大家都还记得计算两个点之间的距离公式吧。 如果点1记为($x_1$,$y_1$),点2记为($x_2$,$y_2$),那么点1与点2的距离为:

$$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^{2}}$$

通过距离公式计算得到所有6个黑色点到红色点的距离如下表:

电影名称 与电影7的距离计算公式 与电影7的距离
电影1 $\sqrt{(3-18)^{2} + (104-90)^{2}}$ 20.5
电影2 $\sqrt{(2-18)^{2} + (100-90)^{2}}$ 18.7
电影3 $\sqrt{(1-18)^{2} + (81-90)^{2}}$ 19.2
电影4 $\sqrt{(101-18)^{2} + (10-90)^{2}}$ 115.3
电影5 $\sqrt{(99-18)^{2} + (5-90)^{2}}$ 117.4
电影6 $\sqrt{(98-18)^{2} + (2-90)^{2}}$ 118.9

按照距离递增排序,可以找到k个距离最近的电影。 假设k=3,那么距离最近的3部电影是电影2电影3电影1。从输入数据集中知道,这三部电影都是爱情片,因此我们判定电影7是爱情片。 注意,kNN算法是按照距离最近的k个数据的类型来决定未知数据类型的。如果k个距离最近的数据不是唯一类型,将把k个数据中比例最高的类型作为未知数据的类型。 例如,如果我们把k设为4,得到距离最近的4部电影分别是电影2电影3电影1电影4。这4部电影中,其中有三部爱情片,比例是75%,只有一部是动作片,比例是25%。因此我们判定未知电影还是爱情片。

三、算法实现

根据前面的算法原理以及例子,我们将k-近邻算法用Python实现。实现代码中主要进行以下操作:

  1. 计算已知类别数据集中每个点与未知点的距离
  2. 按照距离递增排序
  3. 选取与未知点距离最小的k个点
  4. 确定前k个点中所有类别的比例,
  5. 返回前k个点比例最高的类别,作为未知点的预测分类。

1. Python3代码实现

创建knn.py文件并输入如下代码:

from numpy import *
import operator
import sys

def classifier(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 = {}
    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]

def createDataSet():
    dataSet = array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ['爱情片', '爱情片', '爱情片', '动作片', '动作片', '动作片']
    return dataSet, labels

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    input = [int(sys.argv[1]), int(sys.argv[2])]
    k = 4
    output = classifier(input, dataSet, labels, k)
    print(output)

2. 运行代码

在命令行当前目录下执行上面python脚本,并将未知电影的打斗镜头数和接吻镜头数作为参数传递给脚本,结果将输出如下:

C:\tmp> knn.py 18 90
爱情片

可见,上面的代码输出未知电影为“爱情片”,结果与我们之前推导的结果完全一致。 现在我们可以用这个程序来预测任意的输入数据了,例如:

C:\tmp> knn.py 10 100
爱情片

C:\tmp> knn.py 90 10
动作片

这里下载knn.py的完整代码。

3. 代码解析

程序首先导入依赖模块,本算法将用到最重要的numpy,以及operatorsys模块,因此将他们导入。

from numpy import *
import operator
import sys

上面的核心代码在分类器函数classifier()中,有4个输入参数,分别为:

  • inX: 输入数据,将要预测的数据,用数组表示,如[18, 90]
  • dataSet: 训练数据集,即已知类型的数据,用numpy的矩阵表示
  • labels: 训练数据集的分类,用数组表示,数组中每一个值表示dataSet中对应的数据的分类。
  • k:k-近邻算法的k值

classifier()函数第一行获取dataSet数据集的数据个数,使用了numpy数组的shape属性。dataSet是传入的参数,它是由createDataSet()函数创建的numpy数组(二维矩阵):

dataSet = array([[3,104], [2,100], [1,81], [101,10], [99,5], [98,2]])
print(dataSet)
[[  3 104]
 [  2 100]
 [  1  81]
 [101  10]
 [ 99   5]
 [ 98   2]]

numpy的array()函数可以通过传入一个python标准的list来创建一个numpy数组,numpy数组可以是多维的,对于二维数组也可称为矩阵。而我们的输入数据集dataSet就是一个二维数组,即是一个6x2的矩阵,6表示总共有6个数据样本,2表示每个数据样本有2列,即2个特征(打斗镜头数和接吻镜头数)。所以我们的数据集dataSet是一个6行2列的矩阵。

dataSet.shape是numpy提供的,可以获取numpy数组的维数,因为dataSet是一个6行2列的矩阵,因此dataSet.shape输出如下:

dataSet.shape
(6, 2)

classifier()函数第一行调用dataSet.shape[0],表示返回第一维的大小:

dataSetSize = dataSet.shape[0]
print(dataSetSize)
6

classifier()函数第二行使用了numpy的tile()函数,该函数原型为numpy.tile(A,reps),接收两个参数,表示把A根据reps重复输出。请参见numpy.tile对该函数的详细介绍。

classifier()函数中先按如下调用tile()函数:

tile(inX, (dataSetSize, 1))

第一个参数是由命令行输入的参数构成的Python标准list:

input = [int(sys.argv[1]), int(sys.argv[2])]

假如输入18, 90,则input为:

inX = [18, 91]
print(inX)
[18, 91]

我们先看看tile(inX, (dataSetSize, 1))输出长什么样子:

tmpMat = tile(inX, (dataSetSize, 1))
print(tmpMat)
[[18 91]
 [18 91]
 [18 91]
 [18 91]
 [18 91]
 [18 91]]

可以看到,tile()函数将输入的list在行方向上重复了6次,列方向上1次,从而变成了一个6行2列的矩阵。

接下来,用新构造的矩阵与数据集dataSet做减法。矩阵的减法大家都还记得吧,就是对应位置的数值做减法,因此得到相减之后的矩阵diffMat如下。

diffMat = tmpMat - dataSet
print(diffMat)
[[ 15 -13]
 [ 16  -9]
 [ 17  10]
 [-83  81]
 [-81  86]
 [-80  89]]

由于矩阵减法要求两个矩阵具有相同维数,因此我们也可以理解为什么需要先用tile()函数构造一个与dataSet相同维数的矩阵了吧。 接下来,对diffMat做平方运算,也就是对diffMat矩阵的每一个数做平方运算,得到sqDiffMat如下:

sqDiffMat = diffMat**2
print(sqDiffMat)
[[ 225  169]
 [ 256   81]
 [ 289  100]
 [6889 6561]
 [6561 7396]
 [6400 7921]]

接下来,对sqDiffMat矩阵求和。这里使用了numpy的sum()函数,请参见numpy.sum对该函数的详细介绍。

sum()函数的axis参数指定对哪一维数据求和,如果不指定axis,将对整个矩阵所有数据求和。axis=0表示对矩阵的第一维数据求和,对于上面的二维矩阵,就是对每一列求和。axis=1表示将矩阵的第二维数据求和,对于上面的二维矩阵,也就是对每一行求和,比如第一行的两个数相加得到第一个值,225 + 169 = 394,以此类推对所有行求和,最后得到一个数组如下:

sqDistances = sqDiffMat.sum(axis=1)
print(sqDistances)
[  394   337   389 13450 13957 14321]

接下来对求和后的数组sqDistances求平方根,得到所有点与未知点的距离:

distances = sqDistances**0.5
print(distances)
[ 19.84943324  18.35755975  19.72308292 115.97413505 118.13974776 119.67038063]

至此,我们已经求出了数据集dataSet中所有数据与输入数据之间的距离,distances数组中的每一个数就是dataSet中每一组数据与输入数据的距离。

可以看到,我们使用numpy的数组操作,代码非常简单,一次性可以求出所有数据到输入数据的距离,而不用通过遍历来求每个数据到输入数据的距离。

接下来,对上面求出来的距离进行排序。首先使用numpy的argsort()函数对distances排序,这个函数返回数组数值从小到大的索引值:

sortedDistIndicies = distances.argsort()
print(sortedDistIndicies)
[1 2 0 3 4 5]

从上面输出可以看出,索引为1(也就是数组的第2个,因为索引是从0开始的,)的数值最小,排在第一位,我们回头去看看distances数组,确实是数组的第2个数最小,为18.35755975。索引为2(数组的第3个数)的数值倒数第二小,排在第二位,数值为19.72308292。以此类推,可以得到上面相同的输出,从而也证明了argsort()函数的正确性。

接下来,程序通过for循环来找出距离最近的前k个数的类别,并统计每种类别的个数。

本程序中,k被设置为固定值4,所以程序只需要循环4次对前面已经排好序的数组进行统计。而labels是createDataSet()函数设置的,对应着dataSet中每组数组的类型。

k = 4
labels = ['爱情片', '爱情片', '爱情片', '动作片', '动作片', '动作片']

程序定义了一个集合classCount用于存放统计结果。每次循环先获取当前的类型,再对这个类型进行累加,最后将统计结果保存到集合classCount中。

classCount = {}
for i in range(k):
    voteIlabel = labels[sortedDistIndicies[i]]
    classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

我们打印classCount将得到如下输出:

print(classCount)
{'爱情片': 3, '动作片': 1}

从输出可以看出,经过统计后,前k(也就是4)个距离最近的数据中,类型为动作片的个数为1,类型为爱情片的个数为3。

最后,程序对classCount集合进行排序,按照集合value值从高到低排序,得到一个排好序的tuple列表。这里用到了Python内置的sorted函数。请参见Python 内置函数sorted()在高级用法

sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) 
print(sortedClassCount) 
[('爱情片', 3), ('动作片', 1)]

最后我们只需要返回排好序的tuple列表的第一个,则得到tuple('爱情片',3),再返回这个tuple的第一个,则得到程序预测的结果类型。

type = sortedClassCount[0][0]
print(type)
爱情片

文章作者: yglong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 yglong !
评论
  目录