机器学习算法之K最近邻

最近邻（K-Nearest Neighbors, KNN）是一种基于实例的学习方法（instance-based learning）

通俗理解

就是选择最近邻，具体来说，就是选择那些“距离”被预测样本最近的K个样本，根据他们的标签值来决定要预测的样本的标签值是什么。

其实所谓最近，实际是最相似。举例：比如在现实中，预测某一个房子的价格，就参考最相似的K个房子的价格，比如距离最近、户型最相似等等。

原理

1、分类和回归的规则：

如果标签是离散变量（分类问题），就投票决定类别；如果是连续变量（回归问题），就看它们的平均取值，以此作为预测的依据。还可以基于“距离”的远近进行加权投票或加权平均，距离越近权重越高。

2、距离度量的选择：

首先，在机器学习中，这里的距离最近不是仅指现实中空间上的距离最近，而是指在特征空间上的距离最近。也就是说，预测某个房子的价格，不仅要看位置上的距离近，而且其他特征上的取值也要近，比如房间数目、层数、物业质量等等，一切有可能影响房价的因素，都可以作为特征，所有特征组成一个特征空间（就像xyz轴组成一个三维空间），在这个特征空间中的距离最近。

其次，不同规则的距离度量，包括欧几里得距离、曼哈顿距离等。

3、K值的选择：偏差与方差权衡

K值越小，偏差越小、方差越大，容易过拟合，不抗噪声。

K值越大，偏差越大、方差越小，容易欠拟合。

4、K近邻方法的实现：kd树算法

也就是说，计算机如何具体找到最近邻的那些样本。略。

5、KNN的bias（归纳偏好）：

就是某算法更偏好的一些假设，当这些假设不成立时，算法就会显露它的缺点。

locality（局部性）：KNN假设特征空间相近的两点更类似；

smoothness（平滑性）：KNN用均值表示距离（即假设均值能很好的表现真正的距离）

equality（同等重要性）：KNN假设特征（维度）都是同等重要的。

算法的评价

优点：

1、原理理解起来容易

2、lazy learning，无需进行训练

3、参数不多（主要是K）

4、在分割线比较模糊的分类问题上表现也能不错

缺点：

1、准确度相对不高

解决方法：调参；换算法

2、也需要面临k值大小的选择

解决方法：交叉验证；经验知识（通常选择一个较小的值）

3、各特征取值范围不同会影响效果：因为涉及到计算距离。

解决方法：归一化（缩放特征取值范围）、标准化（转换为标准正态分布）

4、因样本数量过少或（和）特征数量过多而导致维度灾难：无法满足密采样条件（样本稀疏问题：维度越高，填充空间所需的数据量越多，可能导致无法找到一个“最近”的样本）；计算量太大（高维空间在距离计算上的问题）。

解决方法：增加样本数（不现实）；降维等。

5、数据量也不能过多，因为其所耗时间和空间随着数据量增大。这是由于基于实例的方法需要把所有的实例数据（训练样本）都打包做成模型（因为它需要计算对所有样本的距离，然后排序取最近的），所谓数据即模型。其它方法只需提交训练得到的模型和参数即可。

应用

由于KNN训练的代价小(lazy learning不作训练)，KNN或可被用于在线学习(online machine learning)中，即使用新数据不断训练和更新已有模型从而作出更好的预测。