机器学习--k近邻法理论知识（二）
机器学习 | k近邻法理论知识（二）
读者朋友们大家好，今天我们将讲解k近邻法的实现：KD树。
构造KD树
KD树是K-dimension Tree的缩写，是对数据点在k维空间中划分的一种数据结构，主要应用于多维空间关键数据的搜索。KD树是一种平衡二叉树，构造KD树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。KD树的每个节点对应于一个K维超矩形区域。KD树的好处在于可以省去大部分数据点的搜索，将搜索限制在空间的局部区域上，减少搜索的计算量，极大地提高了效率。
KD构造方法
构造根结点，使根结点对应于K维空间中包含所有实例点的超矩形区域；通过递归方法，不断地对K维空间进行切分，生成子结点。
在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（ 子结点）；这时，实例被分到两个子区域。
这个过程直到子区域内没有实例时终止。在此过程中，将实例保存在相应的结点上。
KD树构造算法
输入：k维空间数据集\(T = \lbrace x_1,x_2,...,x_N \rbrace\)，其中\(x_i = (x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T\)，, i = 1, 2, ..., N；
输出：KD树
（1）构造根结点，根结点对应于包含T的k维空间的超矩形区域
➢选择x (1)为坐标轴，以T中所在实例的x (1)坐标的中位数为切分点，将根结 点的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴x (1) 垂直 的超平面实现；
➢由根节点生成深度为1 的左右两个节点，左子节点对应坐标x (1)小于切分点 的子区域， 右子节点对应坐标x (1)大于切分点的子区域；
➢将落在切分超平面上的实例点保存于根节点。
（2）采用递归方法构造其他节点
➢ 对深度为j的结点， 选择x(l)为切分的坐标轴，l=j，以该节点的区域中所有实 例的x(l) 坐标的中位数作为切分点， 将该节点对应的超矩形区域垂直切分成 两个子区域。切分由通过切分点并与坐标轴 x(l)垂直的超平面实现；
➢ 由该节点生成深度为j+1的左右两个节点， 左子节点对应坐标x(l)小于切分点 的子区域，右子节点对应坐标x(l)大于切分点的子区域；
➢ 将落在切分超平面上的实例点保存于该节点。
（3）直到两个子区域没有实例存在时停止，从而形成KD树的区域划分。
例子
给定一个二维空间的数据集：T = {(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)}，构造一个平衡KD树。
（1）首先找根结点。选择x(1)维，按照x(1)维对数据集进行排序，得到：A(2, 3)、D(4, 7)、B(5, 4)、F(7, 2)、E(8, 1)、C(9, 6)。观察发现对于x(1)维来说其中位数为7（按照排好序的数据集，其中位数的所在位置对应下标的中位数，即可使用 median = dataset[ len(dataset) / 2来确定），故选择F(7, 2)作为根结点。
按照x(1)维划分，将小于7的划分到根节点的左子树中，大于7的划分到根节点的右子树中（该过程类似搜索二叉树）。对应的树结构如下:
（2）此时对左右子树递归处理。此时要选取x(2)维对子节点分别进行划分。
根结点的左子树：对于节点 (2,3), (4,7), (5,4)，按照 x (2) 维进行排序 (2,3), (5,4), (4,7), 选择中位数 (5,4)作为子树根节点，同理将小于4的放到 B(5,4)节点的左子树中，大于4的放到B (5,4)节点的右子树中。
根结点的右子树：对节点 (8,1), (9,6)进行排序，并选择中位数6,由于 1<6,将E(8,1)作为C (9,6)的左孩子。到此，KD树构造完成，如图所示：
搜索KD树
建立好KD树之后，我们应该知道如何对KD数进行搜索以此来进行分类处理。
给定一个目标点，搜索其最近邻。
➢首先找到包含目标点的叶结点。包含目标点的叶结点对应包含目标点的最小 超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在 以目标点为中心并通过当前最近点的超球体内部；
➢然后从该叶结点出发，依次回退到父结点。如果父结点的另一子结点的超矩 形区域与超球体相交， 那么在相交的区域内寻找与目标点更近的实例点。如 果存在这样的点，将此点作为新的当前最近点；
➢算法转到更上一级的父结点，继续上述过程。如果父结点的另一子结点的超 矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。
例子
还是上述建立KD树的例子，输入的实例点为K(8.5, 1)，求最近邻。
（1） 首先K点的x(1)维的值为8.5，大于根结点的7，所以进入右子树，如图所示：
（2）到了根结点的右子树之后，看K点的x(2)维，坐标为1，小于C点的x(2)维坐标6，则走到其左子树，如图所示：
（3）到了叶子结点E(8, 1)之后，进行算法的第二步，首先将E节点作为最近邻，此时KE间距离为0.5（欧氏距离）。然后递归往上退。首先从E到C，对C点进行操作，发现KC距离为五点多，大于KE距离，于是不更新最近邻，然后对C点进行继续操作，判断当前最近邻距离画一个圆是否与C点切割面相交，如图所示：
看到C点切割面与其没有相交，于是退回到C的父节点F，对F进行操作。首先判断FK距离与当前最近邻的距离，FK的距离为根号下1.25，大于0.5，所以不更新最近邻距离，为了判断F点的另一半区域是否有更小的点，判断一下当前最近邻的距离画一个圆是否与F点切割面相交，如图所示：
发现无交点，此时已经是根结点，无法回退，故可以保留当前最短距离点E点就是我们要找的最近邻点。由此搜索完毕。
下周我们将对K近邻法进行实践，谢谢大家的观看！