KNN算法实现之KD树

一、背景

  了解了KNN算法后,存在一个问题,由于KNN算法需要将所有数据集读入内存,并需要通过计算未知点与所有训练点的距离,筛选出距离最小的k个点。因此在庞大的训练集面前,计算复杂度和空间复杂度都相当得高,KNN算法就显得非常的无力。

二、原理

  将训练集构建出二叉树,利用回溯算法寻找与样点最近的k个训练点,避免与所有训练集计算距离的需求,大大减少了计算复杂度。

三、算法流程

1、KD树的构建

  Kd-树:是对数据点在k维空间{二维(x,y),三维(x,y,z),k维(x,y,z..)}中划分的一种数据结构,主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。本质上说,Kd-树就是一种平衡二叉树。
  
  假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,根据这些数据点构造一个kd树。如下图:
          散点空间图

步骤

  ①6个数据点在x,y维度上的数据方差分别为39,28.63,所以在x轴上方差更大,故先选x轴为坐标轴来切分矩形;
  ②根据x维上的值将数据排序:{(2,3),(4,7),(5,4),(7,2),(8,1),(9,6)}
6个数据的中值为7,所以以数据点(7,2)为节点,通过(7,2)并垂直于x轴的直线来把平面切分成两个矩形;
  ③确定左子空间和右子空间。x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(8,1),(9,6)}
  kd树的构建是一个递归过程,我们对左子空间和右子空间内的数据重复上述过程将空间和数据集进一步细分,如此往复直到空间中任意两个子区域没有实例存在时,停止划分。
  最后可以获得二叉树,如下图:
  二叉树图

2、k-d树上的最邻近查找算法

  目的是检索在k-d树中与查询点距离最近的数据点。

步骤:

  假设查询点A。通过二叉搜索,顺着搜索路径很快就能找到最邻近的近似点,也就是叶子节点B。
  而找到的叶子节点B并不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。
  为了找到真正的最近邻,还需要进行相关的回溯操作。也就是说,算法沿搜索路径反向查找是否有距离查询点更近的数据点。

实例:

以查询(2.1,3.1)为例:

1.二叉树搜索
  此时搜索路径中的节点为{(7,2),(5,4),(2,3)},以(2,3)作为当前最近邻点,计算其到查询点(2.1,3.1)的距离为0.1414
   二叉树搜索实例图
2.回溯查找
  在得到(2,3)为查询点的最近点之后,回溯到其父节点(5,4),并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。
  以(2.1,3.1)为圆心,以0.1414为半径画圆,如下图所示。发现该圆并不和超平面y = 4交割,因此不用进入(5,4)节点右子空间中(图中绿色区域)去搜索;
  最后,再回溯到(7,2),以(2.1,3.1)为圆心,以0.1414为半径的圆更不会与x = 7超平面交割,因此不用进入(7,2)右子空间(图中红色区域)进行查找。至此,搜索路径中的节点已经全部回溯完,结束整个搜索,返回最近邻点(2,3),最近距离为0.1414。
     KDtree回溯法找点

Have a nice day!