KNN

1.优缺点

优点：精度高，对异常值不敏感，没有数据输入假定

缺点：计算复杂度高，空间复杂度高

2.原理阐述

2.1 概念

存在训练样本，且训练样本都存在分类标签。输入没有标签的新数据后，计算新数据的每个特征与样本集中数据的特征的距离（欧式距离），将每个特征距离加和作为新数据与训练数据的距离，然后算法提取距离最近的前K个数据的分类标签，然后选择这K个数据的分类标签出现次数最多的标签作为预测值。

2.2 K值选择

K值选择问题，因为它对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说：

①如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的泛华误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

②如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的泛化误差，但缺点是学习的训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

③K=N，则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的累，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的K值。

3.算法实现：kd树

实现K近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻排序。

3.1 kd树的构建

1 首先选取方差最大的特征作为第一次划分的超平面。

2 选取此特征的中位数划分平面，然后划分出来的两部分递归即可。

KNN

3.2 搜索kd树

给定一个目标点，搜索其最近邻。首先找到包含目标点的叶节点，然后从该叶节点出发，依次回退到父节点；不断查找与目标点最近邻的节点，当确定不可能存在更近的节点时停止，这样搜索就被限制在空间的局部区域上，效率大为提高。包含目标点的叶节点对应包含目标点的最小矩形区域，以此叶节点的实例点作为当前最近点。

KNN

常用的分类决策规则是多数表决。

· 当维数较大时，直接利用k-d树快速检索的性能急剧下降。假设数据集的维数为D，一般来说要求数据的规模N满足条件：N远大于2的D次方，才能达到高效的搜索。