一、k近邻算法

1.1 算法

k近邻算法,假设给定了一个训练数据集,其中实例类别已定。

分类时,对新的实例,根据其k个最近邻的训练实例的类别, 通过多数表决等方式进行预测。 因此,k近邻法不具有显式的学习过程。

1.2 模型

三个基本要素:距离度量、k值、分类决策规则

一般将特征空间,按照每个训练实例点xi,距离该点比其它点更近的所有点组合成一个单元。每个训练实例点拥有一个单元,单元内所有点都标记上类yi。

这样特征空间中每个点的类别都是确定的。

(1)距离

特征空间中两个实例点的距离一般使用欧式距离,或者更一般的$L_p$距离

$$L_p(x_i,x_j)=(\sum^n_{l=1}|x^{(l)}_i-x^{(l)}_j|)^{\frac{1}{p}}$$

其中l=2时为欧式距离,l=1时为曼哈顿距离,l=∞时为各个坐标距离的最大值。

(2)k值

如果k值过小,虽然可能会预测的比较准,但预测结果受邻近点影响过大,如果邻近点恰好为噪声,则会预测错误。

如果k值过大,与输入距离较远的示例也会起到预测作用。

如果k=N,那么总是输出实例中最多的类。

(3)分类决策规则

通常为k个近邻的实例中的最多数类。

二、kd-tree

在进行预测时,需要在训练数据中进行k近邻搜索,如果使用线性扫描,则需要计算输入点与所有训练实例的距离,速度过慢。

2.1 构造kd-tree

kd-tree的构造相当于不断用垂直于坐标轴的超平面将k维空间切分,每个节点对应一个k维超矩形区域。

构造过程:

  • 构造根结点:根结点对应的k维空间包含所有实例点的超矩形区域
  • 递归切分:在超矩形区域中选择一个坐标轴和此坐标轴上的切分点,确定一个超平面,用此超平面将当前超矩形区域切分为左右两个子区域(子结点)
  • 重复此过程,直到子区域内没有实例时终止(叶结点)

2.2 搜索kd-tree

输入:己构造的kd-tree, 目标点x
输出:x的最近邻

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