机器学习实战（2）——k-近邻算法

老板：来了，老弟！

我：来了来了。

老板：今天你要去看看KNN了，然后我给你安排一个工作！

我：好嘞！就是第二章吗？

老板：对！去吧！

可恶的老板又给我安排任务了！

《机器学习实战》这本书中的第二章为我们介绍了K-近邻算法，这是本书中第一个机器学习算法，它非常有效而且易于掌握，所以可以算是入门级算法了。

那我们现在就一起去学习一下！

2.1 k-近邻算法概述

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

其工作原理是：

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

输入没有标签的新数据后，将新数据的每个特征与样本集中对应的数据对应的特征进行比较，然后算法提取出样本集中特征最相似数据（最近邻）的分类标签。（一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。）

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

其实，光看概念，还是比较抽象的。那么接下来，我们来看一个例子（原谅我思维没有那么丰富，就给大家说一下书中的例子吧，但我稍微做了一些修改，使其更形象一些）。书中的例子也不难，就是一个简单的电影题材分类问题。

老板：小韩啊，看完KNN的原理了吧？

我：看完了！

老板：那我先给你一个简单的任务。

我：≧ ﹏ ≦

老板：你先去预测一下新上映的电影《诺手的爱情》是什么题材的。

我：（啥，这是什么鬼？）没问题没问题!

老板给了一个已知电影题材的数据集，这也就是我们的训练样本集，其中只有两种类型的电影:爱情片和动作片。好，第一步，我们先来看看数据：

我们现在知道每部电影的两个特征，一个是打斗镜头次数，一个是接吻镜头次数。那么，根据KNN的原理，我们就需要计算《盖伦VS诺手》，也就是未知电影与样本集中其他电影的距离。我们先不看怎么计算距离（后面算会提供），我们先来看结果。

好了，经过一番计算，我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。

我们假设k=3，那么距离最近的三部电影分别是：盖伦的爱情，盖伦的爱情2，盖伦的爱情3。这三部电影都是爱情片，所以我们判定《诺手的爱情》是爱情片！

Bingo！！！老板说，加鸡腿！！！

好了，老板也加鸡腿了，流程也走完了，放假了！！！等等，好像少了点啥？？？少了代码怎么行！！！

老板布置了新的任务，用Python代码实现K-近邻算法。没事，不要慌，慢慢来

2.1.1 准备：使用Python导入数据

首先，新建一个名为kNN.py的文件，写入以下代码：

在上面的代码中，我们导入了两个模块：第一个是科学计算包NumPy；第二个是运算符模块，k-近邻算法执行排序操作时将使用这个模块提供的函数。

createDataSet()函数，顾名思义，我们可以看出，这个函数用来创建数据集，与此同时，也创建了对应的标签。group就是我们的数据集，而每一条数据对应的类别标签就是labels。

接下来，写好代码后，我们先测试一下。不管你用什么电脑，我们都先进入python交互式环境，然后输入下列命令导入上面编辑的程序模块：

然后，我们继续输入以下命令，创建两个变量，分别代表数据集和标签。

在python命令提示符下，输入变量的名字以检验是否正确的定义变量：

这里定义了4组数据，每组数据有两个我们已知的属性或者特征值。上面的group矩阵每行包含一个不同的数据，由于人类大脑的限制， 我们通常只能可视化处理三维以下的事务。因此为了简单地实现数据可视化，对于每个数据点我 们通常只使用两个特征。

向量labels包含了每个数据点的标签信息，labels包含的元素个数等于group矩阵行数。这里我们将数据点(1, 1.1)定义为类A，数据点(0, 0.1)定义为类B。为了说明方便，例子中的数值是任意选择的，并没有给出轴标签，图2-2是带有类标签信息的四个数据点。

表格形式：

图表形式（引用书中内容）：

好了，我们已经知道了Python如何解析数据、加载数据以及kNN算法的工作原理，接下来我们就用这些方法编写KNN分类算法。

2.1.2 实施kNN分类算法

首先，我们先来看一下k-近邻算法的伪代码：

然后，我们再来看一下实际的Python代码：

上述代码中有几点需要解释一下，也是我在学习的过程中查阅相关资料的地方。

第一，tile函数：

Numpy的tile()函数，就是将原矩阵横向、纵向地复制。

定义原矩阵：

横向：

纵向：

横向 + 纵向：

第二，欧式距离，两个点的欧式距离公式如下：

d = sqrt{(x1 - x2)^2 + (y1 - y2)^2}

第三，分组后的排序。将classCount字典分解为元组列表，然后使用程序第二行导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序 。此处的排序为逆序，即从大到小排序。

到现在为止，我们已经构造了第一个分类器，使用这个分类器可以完成很多分类任务。从这个实例出发，构造使用分类算法将会更加容易。

搞定！！！老板这次给我们加了一瓶可乐！！！有鸡腿有可乐！！！美滋滋！！！

2.1.3 如何测试分类器

我们在老板的安排下，已经使用k-近邻算法构造了第一个分类器，也可以检验分类器给出的答案是否符合我们的预期。

但是，分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。 此外分类器的性能也会受到多种因素的影响，如分类器设置和数据集等。不同的算法在不同数据集上的表现可能完全不同。

那么，问题来了，我们该如何测试分类器的效果呢？其中一种方法就是错误率。这是一种比较常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。后面我们还会遇到更加适合的方法来测试分类器，但这里我们先只介绍错误率。

错误率 = 分类器给出错误结果的次数 / 预测执行的总数

我们在已知答案的数据上进行测试，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。简单点说，我们用KNN训练出来了一个分类器，然后我们再把训练集丢到分类器里面，看看分类器的分类效果。

到现在，老板给出的任务我们也完成了，代码也写了一部分，也掌握了kNN算法的基本使用，还是很开心的！！

但是，老板又来了。

老板：小韩啊，你这个分类器倒是出来了，但是只在你自己捏造的数据集上运行，不行啊！！

我：（什么？敢说我的算法不行！！！）

老板：这样吧，明天我给你安排一个实在一点的任务，去改进一下约会网站的配对效果。

我：约会网站？听起来不错啊！那加鸡腿不？

老板：不加！！！

我：￣へ￣，老板，我先下班了，明天见！！！