第3章 k近邻法

3.1 k近邻算法

输入：训练数据集，其中为实例的特征向量，为实例类别
输出：实例所属的类别

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

• 在中根据分类决策规则（如多数表决）决定的类别：，其中为指示函数

  3.2 k近邻模型

  3.2.1 模型

  k近邻法中，当训练集、距离度量、 k值及分类决策规则(如多数表决)确定后，对于任何一个新的输入实例，它所属的类唯是唯一确定的

3.2.2 距离度量

特征空间中两个实例点的距离是两个实例点相似度的反映，可以使用

设特征空间是维实数向量空间，
的：，其中（以确保是凸函数）

：曼哈顿距离， ：欧氏距离， ：切比雪夫距离， 由右图可知，时，

3.2.3 k值的选择

选择较小的k：预测结果会对近邻的实例点非常敏感，如果恰巧是噪声，容易发生过拟合
选择较大的k：可以减少学习的估计误差，但近似误差会增大；如果，那么无论输入实例是什么，都将简单地预测它属于在训练集中最多的类
通常k取较小的数值，采用交叉验证法来选取最优的k值

3.2.4 分类决策规则

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

那么误分类的概率是：

如果涵盖的区域类别是，那么误分类是：
要使经验风险最小，就要使最大
这就说明了多数表决规则等价于经验风险最小化

3.3 k近邻法的实现：kd树

实现k近邻时，主要考虑的问题是如何对训练数据进行快速k近邻搜索

最简单的方法是线性扫描，这要求计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的

现考虑特殊的机构存储kd树，以减少计算距离的次数

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

3.3.1 构造kd树

输入：k维空间数据集，其中，
输出：kd树

（1）构造根结点。选择为坐标轴，以中所有实例的坐标轴的中位数（存在于序列）为切分点，生成深度为1的左右子节点：左子结点对应坐标%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-78%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(572%2C412)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%22389%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%22890%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=x%5E%7B%281%29%7D&id=PQno5)小于切分点的子区域，右结点对应坐标%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-78%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(572%2C412)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%22389%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%22890%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=x%5E%7B%281%29%7D&id=G3fxV)大于切分点的子区域
（2）重复。 对深度为的结点， 选择为坐标轴，，以该结点区域中所有实例的坐标的中位数（存在于序列）为切分点，生成结点深度为的左右子结点：左子结点对应坐标小于切分点的子区域，右结点对应坐标大于切分点的子区域
（3）直到两个子区域没有实例存在停止

例 构造的kd平衡树

3.2.2 搜索kd树

算法 用kd树最近邻搜索

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

（1）在kd树上找出包含目标点的叶结点：从根节点触发，递归向下访问kd树。若目标点当前维度的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到结点为叶结点为止
（2）以此叶结点为“当前最近点”
（3）递归地向上回退，在每个结点进行以下操作：

1. 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”
2. 如果超圆与父节点的前面有交集，则检查父节点的另一个子节点之是否可能为“当前最近点”

（4）回退到根节点，结束搜索

例 已知3.2.1中的kd树，求中的最近邻点

|
1. 寻找到叶节点，距离为2.69，当“前最近点为”

1. 以为圆心，2.67为半径的圆，与父结点的切线相交
   检查另一个子节点，距离为1.80<2.69
   更新“当前最近点”为

2. 继续回溯，以以为圆心，1.80为半径的圆，与父结点的切线不相交
   且已经回溯到根节点，于是“当前最近点”就是 | | | —- | —- |

算法 用kd树k近邻搜索

输入：已构造的kd树，目标点
输出：的k近邻

（1）在kd树上找出包含目标点的叶结点：从根节点触发，递归向下访问kd树。若目标点当前维度的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点，直到结点为叶结点为止
（2）将该叶节点插入“当前k近邻点集”
（3）递归地向上回退，在每个结点进行以下操作：

1. 如果“当前k近邻点集”元素数量小于k或者该节点距离小于“当前k近邻点集”中最远点距离，那么将该节点插入“当前k近邻点集”
2. 检查另一子结点对应的区域是否与以目标点为球心、以目标点与于“当前k近邻点集”中最远点间的距离为半径的超球体相交。

如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，接着，递归地进行最近邻搜索；
如果不相交，向上回退；
（4）回退到根节点，结束搜索