机器学习札记6—KNN(K近邻)3

kd树

k近邻算法最简单的实现方式线性扫描 linear scan。需要计算每个输入实例和每个训练实例之间的距离；当样本量很大的时候，非常耗时。考虑使用特殊的树形结构：kd树来较少距离的计算。

构造平衡kd树

kd树是一种对k维空间中的实例点进行存储以便快速查找数据的数据结构。

• kd树是一种二叉树，表示对k维空间的划分。

• 不断地用垂直于坐标轴的超平面将k维空间切分，形成一些列的k维超矩形区域。

• kd树的每个节点对应一个k维超矩形区域。

• 具体步骤：

  • 对于给定的数据集T，构造根节点，根节点包含k维空间中所有实例点的矩形区域
  • 选取为坐标轴，以T中的所有坐标的中位数为切分点，生成子节点，不断划分k维空间
  • 在超矩形区域上选择一个坐标轴和此坐标轴上的切分点，确定一个超平面
  • 超平面将矩形区域分为左右两个区域（子区域），实例就被划分到两个区域中
  • 重复上述过程直到子区域内没有实例的时候终止：对于深度为j的结点，选择为切分的坐标轴，

  切分由通过切分点并与坐标轴垂直的超平面来实现

实例

给定一个二维空间的数据集：，构造kd树

实现过程

• 根节点对应包含数据集T的矩形，选择轴，顺序排列是：（2，4，5，7，8，9），中位数是6
• 由于中没有6，选择较近点（7，2），中位数选择7，将空间分为左右两个子矩形区域

image.png

搜索kd树

以k=1为例，通过k最近邻方法来进行搜索：

• 给定一个目标点，首先找到包含目标点的叶结点；
• 包含目标点的叶结点对应包含目标点的最小矩形区域。以此叶结点的实例点为当前最近点
• 目标点的最近邻一定在以目标点为中心并且通过当前最近点的超球体的内部。
• 从该叶节点出发，回退到父节点
• 不断查找与目标点最近邻的节点，当存在不可能更近的点时终止

关于二叉树

二叉查找树是一种树形结构，采用了图的树形结构。每个节点最多两个子节点

• 平衡二叉树：修正不均衡的树，保持均衡状态，提高查找效率
• B树：每个节点不止一个子节点，可以多个；MySQL中用到了B树

特点：

• 每个节点的值均大于其左子树上任意一个节点的值：大于左边
• 每个节点的值均小于其右子树上任意一个节点的值：小于右边