k 近邻法（K-Nearest Neighbors Algorithm，k-NN）是一种基本分类与回归方法，通过多数表决等方式进行预测，因此不具有显式的学习过程。

k 近邻算法

输入：训练数据集，其中是实例的特征向量，是实例的类别，；实例特征向量 ；

输出：实例所属的类

1. 根据给定的距离度量，在训练集中找出与最近邻的个点，涵盖这点的的邻域记作；

2. 在中根据分类决策规则决定的类别：
   

k 近邻模型

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

特征空间中，对每个训练实例点，距离该点比其他点更近的所有点组成一个区域，叫做单元。下图是二维特征空间划分的一个例子。

距离度量

设特征空间是维实数向量空间，，的距离定义为

其中，。当时，称为欧氏距离，即

当时，称为曼哈顿距离，即

当时，是各个坐标距离的最大值，即

下图给出了二维空间中取不同值时，与原点的距离为1的点的图形：

k 值的选择

如果选择较小的k值：

• 学习的近似误差减小，但学习的估计误差增大
• 噪声敏感
• 整体模型变复杂，容易发生过拟合

如果选择较大的k值：

• 学习的估计误差减小，但学习的近似误差增大
• 整体模型变简单

分类决策规则

多数表决规则：如果分类的损失函数为0-1损失函数，分类函数为

则误分类的概率是

对给定的实例，其最近邻的个训练实例点构成的集合。如果涵盖的区域的类别是，则误分类率是

要使误分类率最小即经验风险最小，就要使最大，所以多数表决规则等价于经验风险最小化。

k 近邻法的实现：kd 树

构造 kd 树

平衡kd树构造算法：
输入：维空间数据集，其中；
输出：kd树

1. 开始：构造根结点，根结点对应于包涵的维空间的超矩形区域。
   选择为坐标轴，以中所欲实例的坐标的中位数为切分点，将根结点对应的超矩形区域切分成两个子区域。切分由通过切分点并与坐标轴垂直的超平面实现。
   由根结点生成深度为1的左、右子结点：坐子结点对应坐标小于切分点的子区域，右子结点对应于坐标大与切分点的子区域。
   将落在切分超平面上的实例点保存在跟结点。
2. 重复：对深度为j的结点，选择为切分坐标轴，，以该结点的区域中所由实例的坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴垂直的超平面实现。
   由根结点生成深度为的左、右子结点：坐子结点对应坐标小于切分点的子区域，右子结点对应于坐标大与切分点的子区域。
   将落在切分超平面上的实例点保存在跟结点。
3. 直到两个子区域没有实例存在时停止。

下面给出一个例子：

搜索 kd 树

kd树的最近邻搜索算法：
输入：kd树；目标点；
输出：的最近邻。

1. 在kd树中找出包含目标点的叶结点：从跟结点出发，递归地向下访问kd树。若目标点当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
2. 以此叶结点为“当前最近点”。
3. 递归地向上回退，在每个结点进行以下操作：
   3.1 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
   3.2 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。
   如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
   如果不相交，向上回退。
4. 当回退到根结点时，搜索结束。最后的“当前最近点”即为的当前最近邻点。

下面给出一个例子：