K-Nearest Neighbor

KNN

KNN的算法思想非常简单，不赘述。
K值的选择有讲究，一般使用交叉验证的方法来确定K值。

KD树

KNN naive的实现实现方法是线性扫描法，但是这种方法效率很差，训练集很大时非常耗时。好一点的方法是使用一个最大堆，时间复杂度为$O(nlogK)$。

下面介绍基于树的方法：kd树。

kd树是二叉树，表示对k维空间的一个划分。相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的超矩形区域。

kd树的构造方法如下：

---

输入：数据集$D=\lbrace x_1,x_2,…,x_n \rbrace$
其中$x_i=(x_i^{(1)},…,x_i^{(k)})$为$k$维空间的样本

---

1) 构造根结点，根节点对应于包含$D$的$k$维空间超矩形区域。选择$x^{(1)}$为坐标轴，以$D$中所有样本的$x^{(1)}$坐标的中位数作为切分点，切成两部分。落在超平面上的点保存在根节点，在超平面左侧、右侧的节点分别根节点深度为1的左右孩子。
2) 重复：对深度为$j$的节点，选择$x^{(l)}$作为切分的坐标轴，满足$l=j\; mod\; k + 1$，坐标轴轮流选，一轮完了再重复.
3) 迭代停止条件：如果一个节点的左右孩子中都没有样本，那么停止迭代

---

输出：kd树

---

下面介绍使用kd树进行k近邻搜索，使用最大堆辅助结构

---

输入：已构造的kd树，目标点$x$，近邻数$K$，空最大堆$hp$

---

1. 从根节点出发，递归地向下访问kd树，若目标$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到结点为叶节点为止。对每一个路过的节点，添加元素维护最大推（留下小的）。
2. 递归的向上回退，在每个节点$p$进行以下操作
   • 检查该结点未被访问过的结点$p_c$对应的区域是否有比堆顶元素更近的点或堆容量未满。具体的，检查$p_c$对应的区域是否与以目标点为求心、以目标点与堆顶元素距离为半径的球体相交
   • 如果相交或$hp$容量未满，以$p_c$结点为根节点执行1，否则继续回溯
3. 当对根节点的回溯完成以后，结束

---

输出：最大堆$hp$内元素即为$s$的$K$近邻

---

kd树更适用于训练实例数远大于空间维度数时的计算，空间维度接近训练实例数时，效率会迅速下降，几乎接近线性扫描。