“k 近邻算法”综述

本来题目想叫“白话 k 近邻算法”，后来想想，“k 近邻算法” 的描述几乎就是“白话”，所以就不故弄玄虚了，接下来的就是一篇笔记呀。

image

图片来自周志华《机器学习》第 10 章第 1 节。

想说一说“k 近邻算法”在机器学习中的地位

“k 近邻算法” 可以说是最容易理解的机器学习算法，所以可以用“k 近邻算法”来作为入门机器学习算法的基本流程的最好材料，因为我们在理解算法上不须要花太多时间。

下面简单说说，“k 近邻算法” 给我们带来了什么。

• 超参数：k 就是一个超参数，这是我们得根据经验，在算法运行之前指定的；
• 数据集分离：我们不能使用所有的样本训练数据，我们还要评估算法的性能，即使是同一个算法，不同的超参数还须要评估好坏，因此，必须从数据集中分离出一部分数据，进行算法好坏，超参数选择的验证；
• 评估算法好坏的准则：k 近邻算法用于分类问题，一个最容易理解的评价指标就是准确率（或者错误率，因为错误率=1-准确率）；
• 交叉验证：交叉验证用于选择超参数，比起简单地那一部分数据作为测试数据集要靠谱，因为分离数据集带有一定随机性；
• 网格搜索：其实就是暴力搜索，把我们认为可能合理的超参数和超参数的组合输入算法，而在其中评估算法好坏，超参数的选择也用到了交叉验证的过程；
• 数据标准化：这一步是一开始学习机器学习算法的时候经常被忽略的，后面我们可以看到数据标准化在梯度下降中也发挥很大的作用；
• 模型复杂度：理解下面这句话 的值越小，模型越复杂， 的值越大，模型越简单，因为 如果和训练数据集一样大的话，其实我们每个预测数据都只能预测为一个类别，即训练数据集中数量最多的那个类别；
• 决策边界：这是分类问题的一个重要且简单的概念。

近邻算法的核心思想

• 物以类聚，人以群分；
• 未标记样本的类别由距离其最近的 个邻居投票来决定。

近邻算法的三要素

1、超参数： ；

2、距离的定义（例如：欧氏距离）；

3、决策的规则（例如：投票表决，或者加权投票）。

算法执行的步骤：

1、选择 和距离的度量；
2、计算待标记的数据样本和数据集中每个样本的距离，取距离最近的 个样本。待标记的数据样本所属的类别，就由这 个距离最近的样本投票产生。

理解 近邻算法的部分核心代码

distances = [np.linalg.norm(point - X) for point in X_train]
print("打印每个点距离待测点的距离：")
for index, distance in enumerate(distances):
    print("[{}] {}".format(index, np.round(distance, 2)))

sorted_index = np.argsort(distances)
print(y_train[sorted_index])

k = 6
topK = y_train[sorted_index][:k]
print(topK)

from collections import Counter

votes = Counter(topK)
mc = votes.most_common(n=1)
print(mc)
print("根据投票得出的点 X 的标签为：", mc[0][0])

k 近邻算法的训练过程，即是利用训练数据集，对特征向量空间进行划分

李航《统计学习方法》P37

说明：从这张图中，你可以看到决策边界。

• 近邻算法是一个懒惰学习的算法，没有显式的学习过程，即没有它没有训练的步骤，是一个基于记忆的学习算法；
• “多数表决”规则等价于“经验风险最小化”（我们的算法在训练数据集上“风险”最小）；
• 近邻算法的优化实现：kd 树，即是给训练数据建立树结构一样的索引，期望快速找到 个邻居，以防止线性扫描。

近邻算法的应用领域

文本分类、模式识别、聚类分析，多分类领域。

要注意的地方

• 使用距离作为度量时，要保证所有特征在数值上是一个数量级上，以免距离的计算被数量级大的特征所主导。例如《机器学习实战》提供的这个例子：

image

• <b><font size='3' color='ff0000'>在数据标准化这件事上，还要注意一点，训练数据集和测试数据集一定要使用同一标准的标准化，看下面的公式。</font></b>

<b><font size='3' color='ff0000'>测试数据集在标准化的时候，一定也要使用“训练数据集的平均值”和“训练数据集的标准差”，而不能使用测试数据集的。</font></b>

原因其实很简单：

1、标准化其实可以视为算法的一部分，既然数据集都减去了一个数，然后除以一个数，这两个数对于所有的数据来说，就要一视同仁；
2、训练数据集其实很少，在预测新样本的时候，新样本就更少得可怜，如果新样本就一个数据，它的均值就是它自己，标准差是 0 ，这根本就不合理。

近邻算法的优点

• 近邻算法是一种在线技术，新数据可以直接加入数据集而不必进行重新训练；
• 近邻算法理论简单，容易实现；
• 准确性高：对异常值和噪声有较高的容忍度；
• 近邻算法天生就支持多分类，区别与感知机、逻辑回归、SVM。

近邻算法的缺点

• 基本的 近邻算法每预测一个“点”的分类都会重新进行一次全局运算，对于样本容量大的数据集计算量比较大；

• 维度灾难：在高维空间中计算距离的时候，就会变得非常远；

• 样本不平衡时，预测偏差比较大，例如：某一类的样本比较少，而其它类样本比较多；

• 值大小的选择得依靠经验或者交叉验证得到。

• 的选择可以使用交叉验证，也可以使用网格搜索（其实是一件事情，网格搜索里面其实就是用的交叉验证）；

• 的值越大，模型的偏差越大，对噪声数据越不敏感，当 的值很大的时候，可能造成模型欠拟合； 的值越小，模型的方差就会越大，当 的值很小的时候，就会造成模型的过拟合。

从 近邻算法说开

• 增加邻居的权重，距离越近，权重越高，参数：weights；

维基百科最近邻居法词条中是这样介绍的：

无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为 ，其中 是到邻居的距离。

• 使用一定半径内的点，当数据采样不均匀的时候，该算法可以取得更好的性能：from sklearn.neighbors import RadiusNeighborsClassifier；

• 近邻算法还可以用于回归，找最近的邻居，计算它们的平均值就可以了。

扩展

参考资料

• 李航《统计学习方法》第 3 章：k 近邻法
  说明：介绍 kd 树，并给出了例子。

• 周志华《机器学习》第 10 章第 1 节
  说明：只简单介绍了思想，并给出了 k 近邻算法虽简单但预测效果在一定情况下比最优贝叶斯估计强的结论（我的这个概括待推敲），没有《统计学习方法》介绍详细。

• [美] Peter Harrington 著，李锐，李鹏，曲亚东 等 译《机器学习实战》第 2 章
  说明：想吐槽一下这本书在这一章节给出的示例代码，很简单的一个算法，它给出的代码变得很复杂，其实并不利于理解 k 近邻算法的基本思想。

• 理解 kd 树的文章：https://www.cnblogs.com/lesleysbw/p/6074662.html

• 理解 balltree 的文章：https://blog.csdn.net/pipisorry/article/details/53156836

• https://blog.csdn.net/skyline0623/article/details/8154911