k-近邻算法概述

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

|  ■  卜近邻算法 ■  -  i

< .

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

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

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

16  第 2 章 A -近邻算法

本书讲解的第一个机器学习算法是 & 近邻算法（ _ ) , 它的工作原理是：存在一个样本数

据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据

与所属分类的对应关系。输人没有标签的新数据后，将新数据的每个特征与样本集中数据对应的

特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们

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

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

现在我们回到前面电影分类的例子，使用 &- 近邻算法分类爱情片和 1 动作片。有人曾经统计过

很多电影的打斗镜头和接吻镜头，图 2-1 显示了 6 部电影的打斗和接吻 _ 头数。假如有一部未看过

的电影，如何确定它是爱情片还是动作片呢？我们可以使用 _ 来解决这个问题。

California Man

He’s Not Really inlo Dudes

?

Beautiful Woman

Kevin Longblade

Robo Slayer 3000

Amped II

电影中出现的打斗镜头次数

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

首先我们需要知道这个未知电影存在多少个打斗镜头和接吻镜头，图 2-1 中问号位置是该未

知电影出现的镜头数图形化展示，具体数字参见表 2-1 。

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

电影名称

打斗镜头 接吻镜头 电影类型

California Man 3 104 爱情片

He 's Not Really into Dudes 2 100 爱情片

Beautiful Woman 1 81 爱情片

Kevin Longblade 10】 10 动作片

Robo Slayer 3000 99 5 动作片

Amped // 98 2

动作片

? 18 90 未知

即使不知道未知电影属于哪种类型，我们也可以通过某种方法计算出来。首先计算未知电影

与样本集中其他电影的距离，如表 2-2 所示。此处暂时不要关心如何计算得到这些距离值，使用

Python 实现电影分类应用时，会提供具体的计算方法 D

电

现

的

接

吻

镜

头

次

数

2.1  A -近邻算法概述 17

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

________________ 电影名称  ______________ ___________________与未知电影的距离______________________

California Man m 5

He 's Not Really into Dudes 18.7

Beautiful Woman 19.2

Kevin Longblade 115.3

Robo Slayer 3000 117.4

Amped II _________________ m 3 ____________________

现在我们得到了样本集中所有电影与未知电影的距离 ， 按照距离递增排序 ， 可以找到乂个距

离最近的电影。假定 ^=3 ，贝丨』三个最靠近的电影依次是故》 #0; 办 (7// 少如 0/3» 如 、Beautiful Woman

和。_ _ 从 氣 4- 近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部

电影全是爱情片，因此我们判定未知电影是爱情片。

本章主要讲解如何在实际环境中应用々-近邻算法 ， 同时涉及如何使用 ?7 出(^工具和相关的机

器学习术语。按照 1.5 节开发机器学习应用的通用步骤，我们使用 ? 乂出如语言开发&-近邻算法的简

单应用，以检验算法使用的正确性。

k -近邻算法的一般流程 f ,-

■ A . 廣,^a.. :¾

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

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

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

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

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

(6) 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行女-近邻算法判定输

入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

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

首先，创 建 名 为麵 孙的 ? 沖 0 濃 块 ，本章使用的所有代码都在这个文件中。读者可以按照自

己的习惯学习代码，既可以按照本书学习的进度，在自己创建的 ?7^«^ 文件中编写代码，也可以直

接从本书的源代码中复制 _ 仍文件。我推荐读者从头开始创建模块，按照学习的进度编写代码。

无论大家采用何种方法，我们现在已经有了 kNN.py 文件。在构造完整的丨 - 近邻算法之前，我

们还需要编写一些基本的通用函数，在 kNN.py 文件中增加下面的代码：

from numpy import ★

import operator

def createDataSet{)：

group = array([[1.0,1. 1 ]  • [1.0,1. 0], [0,0 ], [0,0.1]])

labels = ['A', 'A', 'B', 'B1]

return group, labels

在上面的代码中，我们导人了两个模块；第一个是科学计算包 > ^ ! ^ ^ 第二个是运算符模块 ,

18  第 2 章 it -近邻算法

女 - 近邻算法执行排序操作时将使用这个模块提供的函数，后面我们将进一步介绍。

为了方便使用。 3^ 社 60 社沾 61^) 函数，它创建数据集和标签，如图 2-1 所示。然后依次执行

以下步骤：保存 _ $ 7 文件，改变当前路径到存储 — .?7 文件的位置，打开 ? 外 1«^ 开发环境。

Xifc^Linux、Mac OS 还是 Windows 都需要在打开终端，在命令提亦符下完成上述操作。只要我

们按照默认配置安装 ?3^(®, 在 01»« 几 ^ 0 8 终端内都可以直接输人 97 比 01^ 而在斯 1«10 评 8 命令

提水符下需要输人。 :\Python2 . 6\python _ exe, 进人 ?7 也 00 交互式开发环境。

进人 ? 丫出 (^ 开发环境之后，输人下列命令导人上面编辑的程序模块 :

>>> import kNN

上述命令导人臟模块。为了确保输人相同的数据集，麵模块中定义了函数 ^ 的七扣壯沾社，在

卩 ” 乜 0 «命令提本符下输入下属命令 :

>>> g ro u p ,la b e ls = kNN.createDataSet()

上述命令创建了变量 910 叩和 1 沾 01 3 ，在 ? 7 出 ^ 命令提示符下，输人变量的名字以检验是否正确

地定义变量：

>>> group

array([[  1 1 . 1]  •

0.1]])

labels

['Af, 'A', 'B,, 'B']

这里有 4 组数据，每组数据有两个我们已知的属性或者特征值。上面的 9!^ 卩?矩阵每行包含一个

不同的数据，我们可以把它想象为某个日志文件中不同的测量点或者入口。由于人类大脑的限制，

我们通常只能可视化处理三维以下的事务。因此为了简单地实现数据可视化，对于每个数据点我

们通常只使用两个特征。

向量 1 必 61 包含了每个数据点的标签信息， 1 处 61 包含的元素个数等于取。叩矩阵行数。这

里我们将数据点 (1 ， 1.1) 定义为类八，数据点 (0, 0.1) 定义为类 8 。为了说明方便，例子中的数值是

任意选择的，并没有给出轴标签，图 2-2 是带有类标签信息的四个数据点。

~ ° - 0.2 0.0 0.2 0.4 0.6 0.8 1.0 1.2

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

2.1 A -近邻算法概述 19

现在我们巳经知道 ?7««^ 如何解析数据，如何加载数据，以及 _ 算法的工作原理，接下来

我们将使用这些方法完成分类任务。

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

本节使用程序清单 2-1 的函数运行 _ 算法，为每组数据分类。这里首先给出卜近邻算法的伪

代码和实际的 ? 乂出 011 代码，然后详细地解释每行代码的含义。该函数的功能是使用&-近邻算法将

每组数据划分到某个类中，其伪代码如下：

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

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

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

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

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

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

? 丫 0«^ 函数 <=13331&0 () 如程序清单 2_1 所示。

程序清单 2 - 1 各近邻算法

def classifyO(inX, dataSet, labels, k ) ：

dataSetSize = daCaSet.shape fO]

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

sqDiffMat = diffMat**2

sqDistances = sqDiffMat.s u m (axis=l)

distances = sqDistances**O.5

sortedDistIndicies - distances .argaort ()

距离计算

classCount={}  选 择 距 离 最 小 资

for  1 in range(k).  的斤个占  ^ \

voteIlabel = labels[sortedDistIndicies[i]]

classCount[votellabel] = classCount.get{voteIlabel,0) + 1

sortedClassCount = sorted(classCount.iteritems(),

key=operator.itemgetter{l), reverse=True)  <~ ^

return sortedClassCount[0] [0]  办 排 序

classifyO () 函数有 4 个输人参数 : 用于分类的输人向量是丨必，输人的训练样本集为 (1313861,

标签向量为 131^13 ，最后的参数义表示用于选择最近邻居的数目，其中标签向量的元素数目和矩

阵如 1 沾 & 的行数相同。程序清单 2-1 使用欧氏距离公式，计算两个向量点 “ 和成之间的距离 0 :

d = 」(xA0 - xB0 )2 +  (xA{ -  xBt )2

例如，点 (0 ， 0) 与 (1, 2) 之间的距离计算为：

V(l-0)2+(2-0)2

如果数据集存在 4 个特征值，则点 (1 ， 0, 0 ， 1) 与 (7, 6, 9 ， 4) 之间的距离计算为：

20  第 2 章 1 -近邻算法

V(7 -1)2 + (6 - 0)2 + (9  一 0)2 + (4  一 1)2

计算完所有点之间的距离后，可以对数据按照从小到大的次序排序。然后，确定前 k 个距离

最小元素所在的主要分类 © , 输人々总是正整数；最后，将 < ^ 尤 0 恤字典分解为元组列表，然后

使用程序第二行导入运算符模块的让挪 9 过 te r^ m ,按照第二个元素的次序对元组进行排序©。

此处的 3# 序为逆序，即按照从最大到最小次序排序，最后返回发生频率最高的元素标签。

为了预测数据所在分类，在卩沖如提示符中输入下列命令 :

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

输出结果应该是艮大家也可以改变输人 [0,0] 为其他值，测试程序的运行结果。

到现在为止，我们已经构造了第一个分类器，使用这个分类器可以完成很多分类任务。从这

个实例出发，构造使用分类算法将会更加容易。

2 .1 .3 如何测试分类器

上文我们已经使用女 - 近邻算法构造了第一个分类器，也可以检验分类器给出的答案是否符合

我们的预期。读者可能会问： “ 分类器何种情况下会出错？ ” 或 者 “ 答案是否总是正确的？ ” 答

案是否定的 , 分类器并不会得到百分百正确的结果 , 我们可以使用多种方法检测分类器的正确率。

此外分类器的性能也会受到多种因素的影响，如分类器设置和数据集等。不同的算法在不同数据

集上的表现可能完全不同，这也是本部分的 6 章都在讨论分类算法的原因所在。

为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分

类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率 — 分

类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器

在某个数据集上的执行效果。完美分类器的错误率为 0 , 最差分类器的错误率是 1.0 ,在这种情况

下，分类器根本就无法找到一个正确答案。读者可以在后面章节看到实际的数据例子。

上一节介绍的例子已经可以正常运转了，但是并没有太大的实际用处，本章的后两节将在现

实世界中使用 / 卜近邻算法。首先，我们将使用 &- 近邻算法改进约会网站的效果，然后使用々-近邻

算法改进手写识别系统。本书将使用手写识别系统的测试程序检测々 - 近邻算法的效果。