机器学习算法复习之K最近邻（KNN）
由ypyu创建，最终由ypyu 被浏览 20 用户
K最近邻（K-Nearest Neighbors, KNN）是一种基于实例的学习方法（instance-based learning）
通俗理解
就是选择最近邻，具体来说，就是选择那些在特征空间里“距离”被预测样本最近的K个样本，根据他们的标签值来决定要预测的样本的标签值是什么。
其实所谓最近，实际是最相似。举例：比如在现实中，预测某一个房子的价格，就参考最相似的K个房子的价格，比如距离最近、户型最相似等等。
原理
1、分类和回归的规则：
如果标签是离散变量（分类问题），就投票决定类别；
如果是连续变量（回归问题），就看它们的平均取值，以此作为预测的依据。
还可以基于“距离”的远近进行加权投票或加权平均，距离越近权重越高。
2、距离的度量：
首先，在机器学习中，这里的距离最近不是仅指现实中空间上的距离最近，而是指在特征空间上的距离最近。也就是说，预测某个房子的价格，不仅要看位置上的距离近，而且其他特征上的取值也要近，比如房间数目、层数、物业质量等等，一切有可能影响房价的因素，都可以作为特征，所有特征组成一个特征空间（就像xyz轴组成一个三维空间），在这个特征空间中的距离最近。
其次，不同规则的距离度量，包括欧几里得距离、曼哈顿距离等。
在一个n维空间中，x和y两点的距离是：
欧几里得距离（常用）：
$\sqrt{\sum_{i=1}^{n}{(x_{i}-y_{i})^{2}}}$
曼哈顿距离：
$\sqrt{\sum_{i=1}^{n}{|x_{i}-y_{i}|}}$
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)中，即使用新数据不断训练和更新已有模型从而作出更好的预测。