1. K近邻法概念与算法

• K近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其K个最近邻的训练实例的类别，通过多数表决等方式进行预测。

• K近邻法不具有显示的学习过程，主要利用训练数据集对特征向量空间进行划分，并作为其分类的模型。

• K值的选择、距离度量及分类决策规则是K近邻法的三个基本要素。

• K值的选择：K较小时，训练误差较小，但估计误差较大，即K值的减小意味着整体模型变得复杂，容易过拟合。反之K较大时，训练误差较大，但估计误差较小，意味着整体模型变得简单。在应用中，K值一般取较小的数值，并采用交叉验证法来选取最优的K值。

• 距离度量：$x_i，x_j$的$L_p$距离定义为：
  $$
  L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^l-x_j^l|)^{\frac{1}{p}}
  $$
  这里$p\geq1$，当$p=2$时，称为欧式距离，当$p=1$时称为曼哈顿距离，当$p=∞$，它是各个坐标距离的最大值。

• K近邻法中的分类决策往往采用多数表决，其等价于经验风险最小化。

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

• KD树是一种对K维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。KD树是二叉树，表示对K维空间的一个划分。

• 构造KD树：通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。

• 搜索KD树：下面介绍如何利用kd树进行k近邻搜索。可以看到，利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

  

  包含目标点的叶结点对应包含目标点的最小超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部。然后返回当前结点的父结点，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。算法转到更上一级的父结点，继续上述过程。如果父结点的另一子结点的超矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。

2. 总结

K近邻方法没有学习的过程，就是根据样本集将假设空间进行区域划分，并对该区域按照多数表决的方法设置类型。当有测试实例时，寻找测试实例对应的最近K个样本实例，并以这K个样本实例中多数的类型为测试实例的类型。