k近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法。本文讨论分类问题中的k近邻法。

k近邻算法

k近邻法：

输入：训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}
其中xi∈X⊆Rn,yi∈Y={c1,c2,...,cK}x_i\in X \subseteq R^n,y_i \in Y = \{c_1,c_2,...,c_K\}xi​∈X⊆Rn,yi​∈Y={c1​,c2​,...,cK​}

输出：实例$x$所属的类$y$

• (1) 根据给定的距离度量，在训练集$T$中找出与$x$最近的k个点，涵盖这k个点的邻域记作$N_k(x)$
• (2) 在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$：
  $$y=argma{x}_{c_j}\sum _{x_i\in N_k(x)}I(y_i=c_j)$$

其中 $i=1,2,...,N,j=1,2,...,K$。$I$为指示函数，相等为1否则为0

k近邻法没有显示的学习过程。

k值的选择

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

如果k过小，对近邻的实例点十分敏感，容易过拟合
如果k过大，可以减小学习的估计误差，但是近似误差会增大，欠拟合

一般k取一个较小的值，采用交叉验证法来选择最优的k值

k近邻法的实现：kd树

实现k近邻法，主要考虑的问题是如何快速k近邻搜索。这点在高维度，数据量大时尤为重要。

构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

kd树是二叉树，表示对k维空间的一个划分。

构造平衡kd树：
输入：k维空间数据集$T=x_1,x_2,...,x_N$
输出：kd树

• (1) 开始：构造根结点，根结点对应于包含$T$的k维空间的超矩形区域。
  选择$x^{(1)}$为坐标轴，以所有实例的$x^{(1)}$坐标轴的中位数作为切分点，沿着通过切分点并与坐标轴垂直的超平面将超矩形区域切成两个子区域。
  由根结点生成深度为1的左右子结点，左子结点对应坐标$x^{(1)}$小于切分点的子区域。将落在切分超平面上的实例点保存在根结点。

• (2) 重复：对深度为j的结点，选择$x^{(l)}$为切分的坐标轴，l=j(mod k) + 1。以该结点的区域中所有实例的$x^{(l)}$坐标的中位数为切分点，沿着通过切分点并与坐标轴垂直的超平面将超矩形区域切成两个子区域

• (3) 直到两个子区域都没有实例存在则停止。

搜索kd树

用kd树的最近邻搜索：
输入：已构造的kd树，目标点x
输出：x的最近邻

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

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