K近邻法之kd树

主要目的

kd树的提出主要是用来减少距离计算的次数

众所周知,在实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索,这点在特征空间的维数大及训练数据容量大时尤其必要。

而当前比较常用的方法就是线性扫描(linear scan),这时要计算输入实例与每一个训练实例的距离,当训练集很大时,计算非常耗时,这种方法显然不可行。

为了提高k近邻搜索的效率,可以考虑使用特殊结构存储训练数据,以减少计算距离的次数,这里介绍kd树方法

构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树,表示对k维控件的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间进行切分,构成一系列的k维超矩形区域,kd树的每个结点对应于一个k维超矩形区域。 kd树示意图

构造kd树方法如下:

构造根节点,使得根节点对应于k维空间中包含所有实例点的超矩形区域;通过下面的递归方法,不断地对k维空间进行切分,生成子节点。在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域切分为左右两个子区域(子节点);这时,实例被分到两个子区域。这个过程直到子区域内没有实例时终止(终止时的结点为叶子结点)。在此过程中,将实例保存在相应的结点上。

kd树原理示意 通常,依次选择坐标轴对空间切分,选择训练实例点在选定坐标轴上的中位数(median)为切分点,这样得到的kd树是平衡的。注意,平衡的kd树搜索时的效率未必就是最优的

算法

输入: k维空间数据集\(T = \lbrace x_1 , x_2 , ... , x_n \rbrace\), 其中$ x_i = ( x_i^{(1)}, x_i^{(2)}, … , x_i^{(k)} ) , i = 1,2 ,,,N$;

输出:kd树

开始

构造根节点,根节点对应于包含T的k维控件的超矩形区域。

选择\(x^{(1)}\)为坐标轴,以\(T\)中所有实例的\(x^(1)\)坐标的中位数为切分点,将根节点对应的超矩形区域切分为两个子区域,切分由通过切分点并与坐标轴\(x^{(1)}\)垂直的超平面实现。

由根节点生成神队为1的左、右子结点:左子节点对应坐标\(x^{(1)}\)小于切分点的子区域,右子节点对应于坐标\(x^{(2)}\)大于切分点的子区域

将落在切分超平面上的实例点保存在根节点。

重复

对深度为j的结点,选择\(x^{(l)}\)为切分的坐标轴, l = j (mod k) + 1 , 以该结点的区域中所有实例的\(x^{(l)}\)坐标的中位数为切分点,将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴\(x^{(l)}\)垂直的超平面实现。

由该结点生成深度为j+1的左、右结点: 左子节点对应坐标\(x^{(l)}\)小于切分点的子区域,右子节点对应坐标\(x^{(l)}\)大于切分点的子区域。

将落在切分超平面上的实例点保存在该结点

循环迭代

知道两个子区域没有实例存在时停止,从而形成 了kd树的区域划分。

实例

看完上面的概念和算法应该有一点头绪了,这里举一个二维空间的例子,方便理解。

给定一个二维空间的数据集:\[T = \lbrace (2,3)^T , (5,4)^T , (9,6)^T, (4,7)^T , (8,1)^T , (7,2)^T \rbrace\] 构造一颗平衡kd树。

根节点对应包含数据集T的矩形,选择\(x^{(1)}\)轴,6个数据点的\(x^{(1)}\)坐标的中位数是7,以平面\(x^{(1)} = 7\)将空间分为左、右两个子矩形(子节点);接着,左矩形以\(x^{(2)} = 4\)分为两个自矩形,右矩形以\(x^{(2)} = 6\)分为两个子矩形,如此递归,最后得到如下图所示的特征空间划分和kd树

特征空间划分 kd树

可能会有人问,为什么是\(x^{(1)} -> x^{(2)} -> x^{(1)}\)这样的顺序呢?注意看上面的步骤中重复l = j (mod k) +1

搜索kd树

有了kd树以后,接下来就应该可以对kd树进行搜索。

给定一个目标点,搜索其最近邻。首先找到包含目标点的叶子节点;然后从该叶子节点出发,依次回退到父节点;不断查找与目标点最邻近的结点,当确定不可能在更近的结点时终止。这样搜索就被限制在空间的局部区域上,效率大为提高。

包含目标点的叶子节点对应包含目标点的最小超矩形区域。以此叶子节点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中细腻并通过当前最近点的超球体的内部。然后返回当前节点的父节点,如果父节点的另一子节点的超矩形区域与超球体相交,那么在相交的区域内寻找与目标点更近的实例点,如果存在这样的点,将此点作为新的当前最近点。算法转到更上一级的父节点,继续上述过程,如果父节点的另一个子节点的超矩形区域与超球体不相交,或者不存在比当前最近点更近的点,则停止搜索。

算法描述

输入:已构造的kd树;目标点x;

输出: x的最近邻

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

使用条件(局限)

如果实例点是随机分布的,kd树搜索的平均计算负载读为O(logN),这里N是训练实例数。kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时,它的效率就会迅速下降,几乎接近线性扫描

实例

给定一棵kd树,根节点为A,其子节点为B,C等,树上共存储7个实例点;另有一个输入目标实例点S,求S点的最近邻。kd树如下图 kd树实例

首先在kd树种找到包含点S的叶子节点D,以点D作为近似最近邻,真正的最近邻一定在以点S为中心,通过点D的圆的内部。然后返回节点D的父节点B,在节点B的另一个子节点F的区域内搜索最近邻。节点F的区域与圆不相交,不可能有最近邻点,继续返回上一级父节点A,在节点A的另外一个字节点C的区域内搜索最近邻。节点C的区域与圆相交;该区域在圆内的实例点有点E,点E比点D更近,成为最新的最近邻近点。最后的结果是点E是点S的最近邻。

热评文章