统计学习方法读书笔记——第三章 k近邻法

• k近邻法(k-nearest neighour, k-NN)是一种基本分类与回归方法，输入为实例的特征向量，输出为实例的类别，可以取多类。
• 假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此k近邻法不具有显式的学习过程。
• 事实上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。
• k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。
• k近邻法的一个实现方法——kd树

3.1 k近邻算法

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最近的k个实例，这k个实例多数属于某个类，就把输入实例分为这个类。

3.2 k近邻模型

k近邻算法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k值选择和分类决策规则决定。

3.2.2 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。可以使用欧氏距离、距离或Minkowski距离等。

Lp距离间的关系

3.2.3 k值的选择

k值的选择会对k近邻法的结果产生重大影响。

• k值较小=>邻域较小=>近似误差减小，只有与输入实例较近的训练实例对预测结果起作用=>估计误差增大，对近邻的实例点非常敏感（若近邻点恰好为噪声，预测就会出错)=>换句话说，k值减小意味着整体模型变复杂，容易发生过拟合。
• k值较大=>邻域较大=>估计误差减小，近似误差增大，较远距离实例点对预测起作用，可能导致预测错误=>k值增大意味着整体模型变简单
  如果k=N，意味着无论输入实例是什么，都将取训练实例中最多的类，模型过于简单，完全忽略训练实例中大量有用信息。
  实际应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优k值。

3.2.4 分类决策规则

k近邻法中的分类决策规则往往是多数表决。多数表决规则等价于经验风险最小化。

3.3 k近邻法的实现：kd树

主要问题：如何对训练数据进行快速k近邻搜索。
最简单方法：线性扫描，耗时大。
可以考虑使用特殊结构存储训练数据，以减少计算距离的次数。下面介绍其中的kd树方法。

3.3.1 构造kd树

kd树是一种对k维空间中的实例点进行存储的二叉树结构，方便快速检索，表示对k维空间的一个划分(partition)，注意这里的k指的是k维，和k近邻法的k意义不同。
构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。
构造kd树的方法：

通常依次选择坐标轴对空间切分，选择中位数作为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。
构造平衡kd树的算法：


一个kd树的例子（二维空间）：

3.3.2 搜索kd树

利用kd树可以省区对大部分数据点的搜索。
思想：首先找到包含目标点的叶节点（二分查找），然后从该叶节点出发，一次回退到父节点，不断查找与目标点最近邻的节点。
kd树的最近邻搜索算法：

如果实例点是随机分布的，kd搜索的平均计算复杂的是，为训练实例数。
适用于训练实例维数远大于空间维数时的k近邻搜索。
当空间维数接近训练维数时，它的效率会迅速下降，几乎接近线性扫描。
kd搜索举例：