K近邻法

简介

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

模型

模型由三个基本要素：距离度量、k值的选择、分类决策规则决定。

1. 距离度量：
   k近邻模型的特征空间是n维实数向量空间$R^N$RN，使用的距离是欧式距离，但也可以是更一般的$L_p$Lp​距离或Minkowski距离。
   $x_i, x_j\in{R^N}$xi​,xj​∈RN, $x_i=(x_i^{(1)}, x_i^{(2)}, ...,x_i^{(n)})^T, x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T$xi​=(xi(1)​,xi(2)​,...,xi(n)​)T,xj​=(xj(1)​,xj(2)​,...,xj(n)​)T，
   $x_i$xi​，$x_j$xj​的$L_p$Lp​距离定义为：$L_p(x_i, x_j)=(\sum{|x_i^{l}-x_j^{l}|^p})^{\frac{1}{p}}$Lp​(xi​,xj​)=(∑∣xil​−xjl​∣p)p1​，$(p>=1)$(p>=1)
   当$p=2$p=2时，称为欧式距离，当$p=1$p=1时，称为曼哈顿距离，当$p=\infty$p=∞时，它是各个坐标距离的最大值。
2. k值的选择：
   如果选择较小的k值，“学习”的近似误差会减小，但是估计误差会增大，预测结果会对近邻的实例点非常敏感。k值的减小意味着整体模型变复杂，容易发生过拟合。
3. 分类决策规则：
   多数表决规则。

算法

k近邻法最简单的实现方法是线性扫描，但是耗时，为了提高效率，采用kd树。
kd树是二叉树，表示对k维空间的一个划分。
具体算法（构造kd树）：
输入：k维空间数据集$T=\{x_1,x_2,...x_N\}$T={x1​,x2​,...xN​}，其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T$xi​=(xi(1)​,xi(2)​,...,xi(k)​)T
输出：kd树
step1. 开始：构造根节点，根节点对应于包含T的k维空间的超矩形区域。选择$x^{(1)}$x(1)为坐标轴，以T中所有实例的$x^{(1)}$x(1)坐标的中位数为切分点，将根节点对应的超矩形区域且分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$x(1)垂直的超平面实现。
由根节点生成深度为1的左、右子节点：左子节点对应坐标$x^{(1)}$x(1)小于切分点的子区域，右子节点对应于坐标$x^{(1)}$x(1)大于切分点的子区域。
将落在切分超平面上的实例点保存在根节点。
step2. 重复：对深度为j的节点，选择$x^{(l)}$x(l)为切分的坐标轴，$l=j$l=j mod k+1，以该节点的区域中所有实例的$x^{(l)}$x(l)坐标的中位数为切分点，将该节点对应的超矩形区域且分为2个子区域，切分由通过切分点并与坐标轴$x^{(l)}$x(l)垂直的超平面实现。
由该节点生成深度为$j+1$j+1的左、右子节点：左子节点杜英坐标$x^{(l)}$x(l)小于切分点的子区域，右子节点对应坐标$x^{(l)}$x(l)大于切分点的子区域。
将落在切分超平面上的实例点保存在该节点。
step3. 直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。

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

实例

二维空间数据集：$T=\{(2,3)^T, (5,4)^T, (9,6)^T, (4,7)^T, (8,1)^T, (7,2)^T\}$T={(2,3)T,(5,4)T,(9,6)T,(4,7)T,(8,1)T,(7,2)T}
首先，构造一个平衡kd树：

1. $x^{(1)}$x(1)维度中，有2，5，9，4，8，7这些数，中位数为7，取$x^{(1)}$x(1)=7做垂直分割线，分为左右2个子区域。
   左子区域：$(2,3)^T, (5,4)^T, (4,7)^T$(2,3)T,(5,4)T,(4,7)T
   右子区域：$(9,6)^T, (8,1)^T$(9,6)T,(8,1)T
2. $x^{(2)}$x(2)维度中，对左子区域取中位数，为4，取$x^{(2)}$x(2)=4做垂直分割线，分为上下2个子区域。
   上子区域：$(4,7)^T$(4,7)T
   下子区域：$(2,3)^T$(2,3)T
   $x^{(2)}$x(2)维度中，对右子区域取中位数，为6，取$x^{(2)}$x(2)=6做垂直分割线，分为上下2个子区域。
   下子区域：$(8,1)^T$(8,1)T
3. 以此类推，直到每个点都在分割线上。

参考文献

《统计学习方法》 李航