K近邻算法详解

笔者最近准备写一个系列的机器学习算法教程。每篇文章详细讲解一个机器学习的经典算法，旨在让零基础的读者可以快速入门。

1. 算法介绍

k近邻（k-neareast neighbor，kNN）是解决分类与回归问题最基本的算法之一。该算法没有显式的训练过程。

k近邻算法的核心思想用一句话就可以概括：

给定测试样本，基于某种距离度量找出训练集中与其最近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

——《机器学习》第10章

该算法有三个重要要素：距离度量、k值的选择和分类决策规则。

1.1 距离度量

假设一个人身高175cm，体重为65公斤，体重正常。我们可以用 X1 = [175, 60] Y1 = “非肥胖” 来表示这个人。同样，若一个人身高170cm，体重90公斤，体重超标。我们用 X2 = [170, 90] Y2 = “肥胖” 来表示此人。

现在已知一人X = [160,100]（即身高160cm，体重100公斤），我们想要知道此人与前两人的相似程度，从而推断出此人是肥胖还是非肥胖。

这里的相似程度可用距离来表示，若两个人之间的X（特征）越接近，则认为这两个人越相似。

因此，我们需要考虑如何度量两个样本之间的距离。

距离的定义不止一种，一种通用的定义为Lp距离：

该定义为一种范数。当p=2时，即为我们常见的L2范数（欧式距离）；p=1为L1范数（曼哈顿距离）

如下图，欧式距离为两点之间直线段长度，曼哈顿距离为各轴坐标差之和。

所选的距离的度量（曼哈顿距离、欧式距离、L3距离……）不同，各个点之间的距离不同，各点之间的最近邻点也可能不同。

对于上述体重的例子，X=[160,100] 与非肥胖样本 X1=[175,60] 的欧式距离（L2距离）为42.72；X=[160,100] 与肥胖样本X2=[170,90] 的欧式距离为14.14。

待预测样本X与肥胖样本X2更接近，因此我们预测样本X为肥胖样本。

这里有一个值得注意的细节：若我们把身高的单位变为毫米，把体重的单位变成吨。则样本之间的距离也会发生变化。一个人可以是1600mm身高，有0.1吨的体重。此时若是做样本之间欧式距离的计算，则身高的差距会在欧式距离中占据主导地位，而体重之间的差距几乎可忽略不计。

如果我们认为不同特征对结果同等重要的话，我们常常会对特征进行归一化处理——把样本数据缩放到一个指定范围内。

归一化的方法有很多，比如把分布在0-220cm的身高线性变换成分布在-1到1之间的数据、或者缩放成均值为0，方差为1的数据等等。

1.2 K值的选择

之前我们预测体重样本时，是选择与待测样本最近的一个样本来进行参考。

事实上，我们可以选择k个与待测样本最近的样本，并认为k个已知样本中出现次数最多的类别即为待测样本的类别。

有的时候，k值的选择不同，预测的结果也会不同。

上图中，当k=3时，小球应该为红色三角；k=5时，小球应该为蓝色正方形。

在上图中，我们用颜色标记出各个类别的空间。当k>1时，可能会存在k个临近样本中有多个类别出现次数一样多（如右上图白色区域）。此时我们在出现次数最多个几个类别中随机选取一个类别即可。

k值越小，模型越复杂，越容易发生过拟合。k值越大，模型越简单。当k等于训练集样本数的时候，模型只是单纯返回训练集中出现次数最多的类别。

应用中，k值的选择通常为人为设定。一般取值都较小。可用交叉验证法来确定最优的k值。

1.3 分类决策规则

在分类问题（如判断人是否肥胖）中，我们通常是在取k个样本后，采取多数表决：出现次数最多的类别即为待测样本的类别。

亦可使用加权投票：与待测样本越近的样本权重越大，对各类别进行权重求和后，选择权重和最大的类别。

而在回归问题中（如已知一个人身高、年龄、平均每日摄取卡路里等信息，预测此人体重），我们可取k个样本后，对其结果Y进行平均或者加权平均。

2. 代码实现

2.1 核心代码

本段代码改编自《机器学习实战》。在技术杂学铺公众号内回复“机器学习”即可下载电子版。

笔者已将《机器学习实战》第二章kNN全部代码整合为jupyter文件，并改版为python3版本且附带大量中文注释。读者可前往github下载 | jupyter环境安装

2.2 实战任务

这里我们使用sklearn函数库、Iris数据集。相关介绍可见往期文章。

注：本任务需安装sklearn函数库。

已知三种品种的鸢尾花（山鸢尾、维吉尼亚鸢尾、变色鸢尾）的花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性各50条。数据样本如下：

花萼长度	花萼宽度	花瓣长度	花瓣宽度	品种
6.4	2.8	5.6	2.2	2
5.0	2.3	3.3	1.0	1
4.9	2.5	4.5	1.7	2
4.9	3.1	1.5	0.1	0
5.7	3.8	1.7	0.3	0

任务：对Iris数据集，自行划分训练集与测试集，探究kNN算法对此数据集的效果如何。

第一步，导入数据。sklearn函数库自带iris数据集。直接导入即可。

共150条数据，X为样本特征，每个样本有4个数字属性。Y为样本的类别，取值在0、1、2之间。

第二步，划分训练集和测试集。

使用sklearn的函数train_test_split可将数据打乱后划分到训练集与测试集中。其中设置 test_size=0.2表示测试集占总数据的20%

第三步，创建kNN模型。

导入KNeighborsClassifier函数，设置其k的取值为5（n_neighbors）

设置完后我们会看到kNN模型的具体参数：

KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=1, n_neighbors=5, p=2,
           weights='uniform')

我们未设置其距离度量方式。模型默认取p=2，即为欧式距离。分类决策规则默认为多数表决。

使用 模型.fit(训练集特征，训练集类别) 可训练模型（kNN无需训练模型，这里只是绑定了训练集数据。若是其他模型执行fit函数，可能会需要训练一段时间）

第四步，结果评估。

使用 模型.predict(测试集特征) 可得到模型对待测样本的预测结果。在以后的模型应用时，执行此函数即可。

执行 模型.score(测试集特征,测试集类别) 可得到模型对于测试集预测的准确率，即可知道模型的好坏。

此代码文件与2.1节核心代码放在github同一目录下，读者可前往github下载

3. 其他

• k近邻法一般都是线性扫描训练集样本。kd树可提高其搜索效率，其平均计算复杂度为O(logN)。具体算法可见《统计学习方法》。
• kNN虽然算法简单，但在手写数字数据集MNIST上，识别错误率仅为5%，最好的kNN变体算法，识别错误率可低至0.52%！

• 在线可视化kNN

4. 总结

本文我们讨论了机器学习经典算法之一的k近邻算法。讨论其距离度量、k的选择和决策分类规则，并使用sklearn机器学习库来解决鸢尾花的分类问题。

k近邻算法无需提前训练模型，而是根据与待测样本最近的k个样本的信息来预测待测样本。

4.1 k近邻算法优点

• 实现简单
• 无需提前训练模型
• 对异常值不敏感

4.2 k近邻算法缺点

• 训练集过大时预测速度极慢（计算复杂度高）
• 预测时需要保留训练数据集（空间复杂度高）
• 无法给出数据的基础结构信息，不知道典型实例样本有怎样的特征

参考资料

• 《机器学习实战》第2章 k-近邻算法
• 《统计学习方法》第2章 k-近邻算法
• 《机器学习》10.1 k近邻学习