一、k近邻算法

1.1 算法

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

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

1.2 模型

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

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

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

（1）距离

特征空间中两个实例点的距离一般使用欧式距离，或者更一般的$L_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的最近邻点。