k 近邻法是一种基本分类与回归方法，其输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。 k 近邻法利用训练数据集对特征空间进行划分，并作为其分类的 “模型”。k 值的选择，距离度量及 分类决策规则是 k 近邻法的三个基本要素。k 近邻法 1968 年由 Cover 和 Hart 提出。
一、k 近邻算法
给定一个训练数据集，对新的输入实例，在数据集中找到与该实例最近的 $k$ 个实例，这 $k$ 个实例， 实例的多数属于某个类，就把该输入实例分为这个类。k 近邻没有显式的学习过程。
输入：训练数据集$ T=\{(x_1,y_1),...,(x_N,y_N)\}$
输出：实例所属的类别 $y$
- 根据给定的距离度量，在训练集中找出与 $x$ 最近的 $k$ 个点，涵盖这 $k$ 个点的 $x$ 的领域记作$ N_k(x) $;
- 在$ N_k(x) $ 中根据分类决策规则(如多数表决)决定x的类别y：
$$ y = arg \max\limits_{c_j}\sum\limits_{x_i \in N_k(x)} I(y_i=c_j)，i=1,2,...N; j=1,2,...,K$$其中，$I$ 为指示函数，即当$y_i=c_j$时取1，否则为0.
二、k 近邻模型
模型
k 近邻法使用的模型实际上对应于特征空间的划分。模型由三个基本要素——距离度量、k 值的选择和分类决策规则决定。 当三者确定后，对于任何一个输入实例，它所属的类唯一确定。
特征空间中，对每个训练实例点 $x_i$，距离该点比其他更近的所有的点组成一个区域，叫做单元(cell)；每个训练实例 点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。
距离度量
特征空间中两个实例点的距离是两个实例点相似程度的反映。k 近邻模型的特征空间一般是 n 维
实数向量空间 $R^n$。使用的距离是欧式距离或者更一般的$L_p$距离。
$$ L_p(x_i,x_j)=(\sum\limits_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}} $$
这里 $p \ge 1$。当 $p=1$时，称为曼哈顿距离；当 $p=2$时，即为熟知的欧氏距离；当 $p=\infty$时，它是各个坐标距离的
最大值。
k 值的选取
k 值的选择会对 k 近邻的算法结果产生重大影响。
选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，学习的近似误差会减小 只有与输入实例较近的训练实例才会起作用，但缺点是学习的估计误差会增大，即，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
选择较大的 k 值，就相当于用较大邻域中的训练实例进行预测。其优点是减少学习的估计误差，但缺点是学习的近似误差会增大。即，k 值的增大意味着整体的模型变得简单，容易发生欠拟合。
在应用中，k 值一般取一个比较小的数值，通常采用交叉验证法来选取最优的 k 值。
分类决策规则
k 近邻法中的分类决策规则往往是多数表决，即由输入实例的 k 个邻近的训练实例中的多数 类决定输入实例的类。
多数表决规则等价于采用指示函数时的经验风险最小化。
三、k 近邻的实现：kd 树
实现 k 近邻法时，主要考虑的问题是如何对训练数据进行快速 k 近邻搜索。 kd 树是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 kd 树是二叉树，表示对 k 维空间的一个划分。
构造
构造 kd 树相当于不端的用垂直于坐标轴的超平面将 k 维平面切分，构成一系列的 k 维超矩形区域。kd 树的每个结点对应于一个 k 维超矩形区域。
构造方法如下：
- 构造根结点，使根结点对应于 k 维空间中包含所有实例点的超矩形区域；
- 通过下面的递归方法，不断的对 k 维空间进行切分，生成子结点。
- 在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面， 这个超平面通过选取的切分点并垂直于选定的坐标轴；
- 上述超平面将当前区域划分为左右两个子区域(子结点)，实例被分到两个子区域；
- 直到子区域内没有实例时终止(终止时的结点为页结点)
构造平衡 kd 树(切分点选为中位数)具体算法：
输入：k 维空间数据集 $ T=\{x_1,...,x_N\} $，其中 $ x_i = (x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T $
输出：kd 树
- 开始：
- 构造根结点，根结点对应于包含 T 的 k 维空间的超矩形区域。
- 选择 $x^{(1)}$ 为坐标轴，以 $T$中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的 超矩形区域切分为两个子区域。切分由通过切分点并与做坐标轴 $x^{(1)}$ 垂直的超平面实现。
- 由根结点生成深度为 1 的左右子结点，分别对应坐标 $x^{(1)}$ 小于、大于切分点的子区域。
- 将落在切分超平面上的实例点保存在根结点。
- 重复：
- 对深度为 j 的结点，选择 $x^{(l)}$ 为切分的坐标轴，$l=j(mod k)+1 $，以该 结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域 切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。
- 由该结点生成深度为 j+1 的左右子结点，分别对应坐标；
- 将落在切分超平面上的实例点保存在该结点。
- 结束：
- 直到两个子区域没有实例存在时停止，从而形成 kd 树的区域划分。
搜索
以最近邻为例，给定一个目标点，搜索其最近邻：
- 首先找到包含该目标点的叶结点；
- 然后从该叶结点出发，依次退回到父结点；
- 不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。
- 包含目标点的叶结点对应包含目标点的最小超矩形区域；
- 以此叶结点的实例点为当前最近点，目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部，然后返回当前结点的父结点，
- 如果父结点的另一子结点的超矩形区域与超球体相交，则在相交的区域内寻找与目标点更近的实例点，如果存在这样的点，将此点作为新的当前最近点，算法转到更上一级的父结点，继续上述过程；
- 如果父结点的另一子结点的超矩形区域与超球体不相交，或不存在比当前更近的点，则停止搜索。
用 kd 树的最近邻搜索算法：
输入：已构造的 kd 树；目标点 x ； 输出：x 的最近邻
- 在 kd 树中找到包含目标点 x 的叶结点：从根结点出发，递归的向下访问 kd 树。若目标 点 x 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移到右子结点。直到子结点为叶结点为止；
- 以此叶结点为“当前最近点”；
- 递归的向上回退，在每个结点进行一下操作：
- 如果该结点保存的实例点比当前最近点距离目标点更加，则以该实例点为“当前最近点”
- 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超秋体相交：
- 如果相交，可能在另一子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。递归的进行最近邻搜索；
- 如果不相交，向上回退
- 当回退到根结点时搜索结束。最后的“当前最近点”即为 x 的最近邻点。