《统计学习方法》第 3 章“k 近邻法”学习笔记

k 近邻法

“k 近法”在算法层面理解容易，可以从使用“k 近邻法”处理分类问题入手，解释机器学习中的各种概念和一般流程。

k 近邻法的基本思想

“k 近邻法” 几乎是所有机器学习算法中最简单的算法，它用于分类的核心思想就是“物以类聚，人以群分”，即未标记样本的类别由距离其最近的 $k$ 个邻居投票来决定。

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

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

有监督学习、分类学习、回归

有监督学习的数据包含了“特征”和“标签”。根据这些数据对新的数据的分类进行预测或预测，如果待预测的目标变量是离散值，那么这一类问题称之为“分类问题”；如果待预测的目标变量是连续值，那么这一类问题称之为“回归”问题。

评估算法时不能使用在训练过程中出现过的数据

这一点很像我们以前学习的时候，常常会买一本练习册做题，如果这本练习册没有参考答案，你就不知道自己做对与否。而真正检验你学习水平的大型考试，例如期中考试、期末考试、中考、高考都是重新出题，如果使用以前出现过的题目，则不能检验你学习的真实水平，因为你有可能是记住了问题的解法，而没有理解它。

这就是分离训练数据集和测试数据集的必要性。因此采集到的所有带标签的样本，应该分离一部分用于测试。那么评估算法应该采用什么指标呢？

评估算法好坏的指标

一般地，“ $k$ 近邻法”用于分类问题使用“准确率”作为指标。但是在数据分布不平衡的时候，就不能使用准确率了，而应该使用精准率、召回率、混淆矩阵等，甚至应该看看 auc。

超参数

超参数是算法执行之前认为定义的。“ $k$ 近邻法” 中的 $k$ 就是一个超参数，它决定了模型的复杂度。

“ $k$ 近邻法” 还有其它超参数，使用的距离的定义是欧氏距离还是闵式距离，闵式距离的参数 $p$ 是多少，投票的时候是“平票”还是“加权投票”。

模型的复杂度、过拟合、欠拟合

$k$ 越小，模型就越复杂。极端情况下 $k=1$ ，新来的预测数据的类别取决于训练样本中离他最近的那个样本的类别，如果这个样本恰好是标记错误的样本，预测就可能发生错误，因为它看不到更多数据，就有可能过拟合，学习到的不是样本数据的一般规律。

$k$ 越大，模型就越简单。极端情况下 $k$ 等于所有训练样本的个数，此时每新来一个数据做预测的时候，就直接把训练样本中出现最多的类别数返回就行了，这样的模型过于简单，以致于失去了算法真正的意义，所有的预测数据都返回同一个值，对数据不能很好的预测，这是欠拟合。

网格搜索与交叉验证

网格搜索其实就是暴力搜索，把我们认为可能合理的超参数和超参数的组合输入算法。而评价一组超参数的好坏一定不能使用测试数据集，一般的做法是从训练数据集中再分离出一部分数据用于验证超参数的好坏，并且这种验证超参数好坏的做法要使用不同的训练数据集的子集重复多次，这就是交叉验证。

交叉验证用于选择超参数，由于分离数据集其实带有一定的随机性，把所有的数据集都看一遍，多次取平均的做法，比起一次性随机地使用训练数据集的一部分子集作为测试数据集要靠谱。

网格搜索中就用到了交叉验证，通过框架被封装了起来，不用我们手动实现。

数据标准化

数据标准化是我刚开始接触学习机器学习算法的时候经常被忽略的。由于 k 近邻法使用距离作为度量，数据在量纲上的统一是十分重要的，数据标准化则可以避免计算出来的距离被量纲大的特征所主导。

后面我们可以看到数据标准化在梯度下降中也发挥很大的作用，还有 SVM、K-means 这些距离度量的算法，都要求我们对数据进行标准化。

例如：《机器学习实战》提供的例子。

image-20190217153027062

在数据标准化这件事上，还要注意：训练数据集和测试数据集一定都使用相同的标准化方式，即训练数据集的标准化方式，请看下面的公式。
$标准化的训练数据集 = \cfrac{原始训练数据集数据-训练数据集的平均值}{训练数据集的标准差}$

$标准化的测试数据集 = \cfrac{原始测试集数据集数据-训练数据集的平均值}{训练数据集的标准差}$

测试数据集在标准化的时候，一定也要使用“训练数据集”的平均值和“训练数据集”的标准差，而不能使用测试数据集的。

原因其实很简单：

1、标准化其实可以视为算法的一部分，既然数据集都减去了一个数，然后除以一个数，这两个数对于所有的数据来说，就要一视同仁；

2、训练数据集其实很少，在预测新样本的时候，新样本就更少得可怜，如果新样本就一个数据，它的均值就是它自己，标准差是 0 ，这根本就不合理。

k 近邻算法的三要素

1、超参数： $k$ ；

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

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

手写 k 近邻法的核心代码

Python 代码：

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 近邻法了解机器学习项目的执行流程

使用 iris 鸢尾花数据集。

1、分割训练数据集和测试数据集；

2、只用训练数据集 fit 得到均值和标准差；

3、分别对训练数据集和测试数据集进行 transform，注意：这里只需要传入 X_train 和 y_train 就可以了，不用传入标签；

4、使用 k 近邻法进行评分，注意：传入的特征矩阵一定要经过数据标准化。

image-20190217154816935

k 近邻法的特点

在整理这部分内容的时候，发现优点和缺点其实要在一定的前提下讨论，所以就干脆放在一起，说一说 k 近邻法的特点。

k 近邻法是一个懒惰学习的算法，没有显式的学习过程，即没有它没有训练的步骤，是一个基于记忆的学习算法。

k 近邻法是一种在线学习技术，新数据可以直接加入数据集而不必进行重新训练，但与此同时在线学习计算量大，对内存的需求也较大。基本的 k 近邻法每预测一个“点”的分类都会重新进行一次全局运算，对于样本容量大的数据集计算量比较大。k 近邻法的优化实现：kd 树，即给训练数据建立树结构一样的索引，期望快速找到 $k$ 个邻居，以防止线性扫描。

“多数表决”规则等价于“经验风险最小化”，即算法在训练数据集上“风险”最小。

对异常值和噪声有较高的容忍度，在算距离的时候，异常值和噪声离待预测的点的距离会比较远，且个数较少，就不会参与最终结果的投票。

$k$ 近邻算法天生就支持多分类，类似还有决策树、朴素贝叶斯分类，它们区别于感知机、逻辑回归、SVM 这类原生只用于二分类问题的算法。

维度灾难

在高维空间中计算距离的时候，就会变得非常远。

样本不平衡时，预测偏差会比较大。

$k$ 值大小的选择得依靠经验或者交叉验证得到，不能自己拍脑门随便指定一个。

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

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

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

参考资料

[1] 李航. 统计学习方法（第 2 版，第 3 章“ $k$ 近邻法”）. 北京：清华大学出版社，2019.
说明：介绍了 kd 树，并给出了例子。

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

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

（本节完）

以下为草稿，我自己留着备用，读者可以忽略，欢迎大家批评指正。

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

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

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

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

算法执行的步骤

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

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

李航《统计学习方法》P37

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

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

$k$ 近邻算法的应用领域

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

$k$ 近邻算法的优点

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

$k$ 近邻算法的缺点

基本的 $k$ 近邻算法每预测一个“点”的分类都会重新进行一次全局运算，对于样本容量大的数据集计算量比较大；
维度灾难：在高维空间中计算距离的时候，就会变得非常远；
样本不平衡时，预测偏差比较大，例如：某一类的样本比较少，而其它类样本比较多；
$k$ 值大小的选择得依靠经验或者交叉验证得到。
$k$ 的选择可以使用交叉验证，也可以使用网格搜索（其实是一件事情，网格搜索里面其实就是用的交叉验证）；
$k$ 的值越大，模型的偏差越大，对噪声数据越不敏感，当 $k$ 的值很大的时候，可能造成模型欠拟合； $k$ 的值越小，模型的方差就会越大，当 $k$ 的值很小的时候，就会造成模型的过拟合。

从 $k$ 近邻算法说开

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

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

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

使用一定半径内的点，当数据采样不均匀的时候，该算法可以取得更好的性能：from sklearn.neighbors import RadiusNeighborsClassifier；
$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

《统计学习方法》第 3 章“k 近邻法”学习笔记

k 近邻法的基本思想

有监督学习、分类学习、回归

评估算法时不能使用在训练过程中出现过的数据

评估算法好坏的指标

超参数

模型的复杂度、过拟合、欠拟合

网格搜索与交叉验证

数据标准化

k 近邻算法的三要素

手写 k 近邻法的核心代码

通过 k 近邻法了解机器学习项目的执行流程

k​ 近邻法的特点

维度灾难

参考资料

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

算法执行的步骤

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

近邻算法的应用领域

近邻算法的优点

近邻算法的缺点

从 近邻算法说开

参考资料

k 近邻法的特点

$k$ 近邻算法的应用领域

$k$ 近邻算法的优点

$k$ 近邻算法的缺点

从 $k$ 近邻算法说开