引言

k近邻算法（k-Nearest Neighbor，简称kNN）：给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最接近的个实例，通过这个实例投票决定该输入实例的类别。

k近邻算法

输入： 熟练集
输出： 实例所对应的类别

1. 根据给定的距离度量方式，在训练数据集中找到距离输入样例最近的个点，将包含这个点的邻域记作
2. 在中根据分类决策规则（如多数表决）将划分到某个类别

特殊地，当等于1时，相当于将输入实例划分到训练数据集中与距离最近点所属的类别。

k近邻模型

唯一确定一个k近邻模型由三方面构成：距离度量方式、k值的选取和分类决策规则。

一、距离度量方式

我们用两个点的距离远近来度量它们的相似程度，近邻模型的特征空间是维实数向量空间，我们常使用欧式距离来衡量两个点的距离，但也可以是更一般的距离：

二、k值的选择

当选取的值较小时，相当于用较小邻域的训练实例进行预测，更容易受噪声干扰（比如邻近的实例点恰好是噪声就会出错），即越小则模型过拟合的风险越大。
当选取的较大时，相当于用较小邻域的训练实例进行预测，这时候与输入实例较远（相似度较小）的训练实例也会对预测产生影响，从而降低模型准确率。

特别的，等于1时相当于用离输入样例最近的训练实例做预测；等于时无论输入实例是什么，都简单地用训练实例中样本数最多的类别作为预测类别。

在应用中，值在比较小的数值范围内取，并且结合交叉验证方法确定最优值。

三、分类决策规则

近邻方法中的分类决策规则往往是多数表决，即由输入实例的个邻近实例中的多数类作为预测类别。

套用监督学习中的损失函数和风险函数知识，多数表决规则等价于经验风险最小化，推导如下：

给定输入实例，其邻近个训练实例构成集合，如果涵盖区域的类别是，那么误分类率为：

要令误分类率即经验风险最小，相当于最大化，也就是多数表决。因此在近邻中多数表决规则等价于经验风险最小化。

kd树

当训练集很大时，计算输入实例和每一个训练实例的距离相当耗时。为了提高近邻搜索的效率，我们使用特殊的结构存储训练数据来减少计算距离的次数，比如树方法。
树（k-dimension tree）是一种对维空间中的实例点进行存储以便对其进行快速检索的二叉树形数据结构。构造树相当于不断用垂直于坐标轴的超平面将维空间切分，构成一系列的维超矩形区域，树上的每一个结点对应于一个维超矩形区域。该超矩形区域垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分。

一、构造kd树

输入： 维空间数据集，其中
输出：树

1. 构造对应包含的维空间的超矩形区域：以为坐标轴，中所有实例的坐标的中位数为切分点将超矩形区域划分为两个子区域。此步生成深度为1的左、右结点：左子结点对应坐标小于切分点的子区域，右子结点对应于坐标大于切分点的子区域。正好落在划分超平面上的实例点保存在根结点。
2. 同样地，对深度为的结点，选择为切分的坐标轴（，因为可能存在对同个维度进行多次划分），以该结点的区域中所有实例的坐标的中位数为切分点划分结点对应的超矩形区域。
3. 直到两个子区域没有实例存在时停止

注意到没，树的思想和二分法很像，并且都能提高搜索的效率。

二、搜索kd树

注意树中的指特征维度数，但近邻算法中的表示最邻近的个点。
搜索方法如下：
输入： 已知的树，目标点
输出： 的最近邻

1. 先找到树中包含目标点的叶结点（即包含输入样例的超矩形区域）：从根结点出发，递归地向下访问直到子结点为叶结点
2. 以该叶结点为“当前最近点”
3. 在该叶子结点递归回退，在每个结点进行如下操作：

• 如果该结点保存的实例点比“当前最近点”更距离目标点更近，则以该实例点为“当前最近点”
• 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。（即检查另一子结点对应的区域是否与该目标点为球心，以目标点与“当前最近点”间的距离为半径的超球体相交）
• 如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，接着，递归地进行最近邻搜索
• 如果不相交，向上回退

4. 当回退到根结点时，搜索结束，最后的“当前最近点”即为的最近邻点。

需要注意的点

1. 如果实例点是随机分布的，那么树的平均计算复杂度是
2. 树更适用于训练实例数远大于空间维数的近邻搜索，当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近于线性扫描（即挨个计算训练数据集每个点和输入样例的距离）
3. 近邻算法既能用于分类，也能用于回归，比较简单的回归就是用近邻点的平均值来预测输入样例的预测值。
4. 近邻模型由三个因素决定：距离度量方法、值选取和分类决策规则

参考

李航 《统计学习方法》