系列文章目录

机器学习的一些常见算法介绍【线性回归，岭回归，套索回归，弹性网络】

文章目录

一、KD算法简介

1.1、kd树简介

1.2、怎样将一个K维数据划分到左子树或右子树？

1.3、在哪个维度上进行划分？

1.4、怎样确保建立的树尽量地平衡？

二、Kd-Tree的构建

三、Kd-Tree的最近邻查找

四、KD树的案例介绍

五、总结

前言

本节主要介绍机器学习当中的KD树算法，下面的案例经供参考

一、KD算法简介

1.1、kd树简介

kd树（k-dimensional树的简称），是一种分割k维数据空间的数据结构，主要应用于多维空间关键数据的近邻查找(Nearest Neighbor)和近似最近邻查找(Approximate Nearest Neighbor)。
其实KDTree就是二叉查找树（Binary Search Tree，BST）的变种。二叉查找树的性质如下：
1）若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
2）若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
3）它的左、右子树也分别为二叉排序树；

1.2、怎样将一个K维数据划分到左子树或右子树？

和构造1维BST树类似，只不过对于Kd树，在当前节点的比较并不是通过对K维数据进行整体的比较，而是选择某一个维度d，然后比较两个K维数据在该维度 d上的大小关系，即每次选择一个维度d来对K维数据进行划分，相当于用一个垂直于该维度d的超平面将K维数据空间一分为二，平面一边的所有K维数据在d维度上的值小于平面另一边的所有K维数据对应维度上的值。也就是说，我们每选择一个维度进行如上的划分，就会将K维数据空间划分为两个部分，如果我们继续分别对这两个子K维空间进行如上的划分，又会得到新的子空间，对新的子空间又继续划分，重复以上过程直到每个子空间都不能再划分为止。以上就是构造 Kd-Tree的过程，上述过程中涉及到两个重要的问题：

1）每次对子空间的划分时，怎样确定在哪个维度上进行划分；

2）在某个维度上进行划分时，怎样确保建立的树尽量地平衡，树越平衡代表着分割得越平均，搜索的时间也就是越少。

1.3、在哪个维度上进行划分？

一种选取轴点的策略是median of the most spread dimension pivoting strategy，统计样本在每个维度上的数据方差，挑选出对应方差最大值的那个维度。数据方差大说明沿该坐标轴方向上数据点分散的比较开（后面会发现，选择方差大的维度主要是为了减少回溯时的代价，减少子树的访问）。这个方向上，进行数据分割可以获得最好的平衡。

1.4、怎样确保建立的树尽量地平衡？

给定一个数组，怎样才能得到两个子数组，这两个数组包含的元素个数差不多且其中一个子数组中的元素值都小于另一个子数组呢？

方法很简单，找到数组中的中值（即中位数，median），然后将数组中所有元素与中值进行比较，就可以得到上述两个子数组。同样，在维度d上进行划分时，划分点（pivot）就选择该维度d上所有数据的中值，这样得到的两个子集合数据个数就基本相同了。

二、Kd-Tree的构建

在K维数据集合中选择具有最大方差的维度k，然后在该维度上选择中值m为pivot对该数据集合进行划分，得到两个子集合；同时创建一个树结点node，用于存储；
对两个子集合重复上述步骤的过程，直至所有子集合都不能再划分为止；

k-d树的构建是一个递归的过程。对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点

三、Kd-Tree的最近邻查找

（1）将查询数据Q从根结点开始，按照Q与各个结点的比较结果向下访问Kd-Tree，直至达到叶子结点。
其中Q与结点的比较指的是将Q对应于结点中的k维度上的值与中值m进行比较，若Q(k) < m，则访问左子树，否则访问右子树。达到叶子结点时，计算Q与叶子结点上保存的数据之间的距离，记录下最小距离对应的数据点，记为当前最近邻点nearest和最小距离dis。
（2）进行回溯操作，该操作是为了找到离Q更近的“最近邻点”。即判断未被访问过的分支里是否还有离Q更近的点，它们之间的距离小于dis。
如果Q与其父结点下的未被访问过的分支之间的距离小于dis，则认为该分支中存在离P更近的数据，进入该结点，进行（1）步骤一样的查找过程，如果找到更近的数据点，则更新为当前的最近邻点nearest，并更新dis。
如果Q与其父结点下的未被访问过的分支之间的距离大于dis，则说明该分支内不存在与Q更近的点。
回溯的判断过程是从下往上进行的，直到回溯到根结点时已经不存在与P更近的分支为止。
注：判断未被访问过的树分支中是否还有离Q更近的点，就是判断"Q与未被访问的树分支的距离|Q(k) - m|"是否小于"Q到当前的最近邻点nearest的距离dis"。从几何空间上来看，就是判断以Q为中心，以dis为半径超球面是否与未被访问的树分支代表的超矩形相交。

四、KD树的案例介绍

本案例依据KD树建立的逻辑过程来编写程序

import numpy  as np
#定义结点类
class Node:def __init__(self, data, lchild = None, rchild = None):self.data = dataself.lchild = lchild#左子树self.rchild = rchild#右子树
#定义kd树
class KD_Tree:def __init__(self):self.kd_tree = None        def create(self, dataset, depth):if len(dataset) > 0:N,m = np.shape(dataset) # N样本数，m为属性temp = 0if depth == 0:#根据最大方差法确定根节点的切分属性var_value=np.array((m,1))for i in range(m):var_value[i] = np.var(dataset[:,i])axis = temp=np.argsort(var_value)[-1]else:axis = (depth + temp)%mmidIndex = int(N / 2)#确定切分的中值数据index = np.argsort(dataset[:,axis])#按照划分轴排序后的序号值sorted_dataset = dataset[index]#按照划分轴排序后的序号的数据集node = Node(sorted_dataset[midIndex])#创建当前节点left_dataset = sorted_dataset[:midIndex]#左子树数据集right_dataset = sorted_dataset[midIndex + 1:]#右子树数据集print('当前切分属性:%d'%axis)print('排序后的数据集:',sorted_dataset)print('当前切分节点:',sorted_dataset[midIndex])if len(left_dataset)!=0:print('左子树数据集:\n',left_dataset)if len(right_dataset)!=0:print('右子树数据集:\n',right_dataset)print(40*'*')node.lchild = self.create(left_dataset, depth + 1)#左子树递归调用node.rchild = self.create(right_dataset, depth + 1)#右子树递归调用def search(self,tree,x):self.nearest_point = None#当前最近邻节点self.nearest_value = None#当前最近邻距离def travel(node,depth = 0):if node is not None:axis = depth%len(x)if x[axis]<node.data[axis]:#当前数据集在切分轴上的取值小于切分点的值travel(node.lchild,depth+1)else:travel(node.rchild,depth+1)distance_Node_x=self.dist(x,node.data)#计算当前节点与查询节点的距离值if self.nearest_point is None or self.nearest_value>distance_Node_x:self.nearest_point = node.dataself.nearest_value = distance_Node_xprint(40*'*')print('当前切分属性:%d',axis)print('当前查询结点:',node.data)print('当前查询距离:',distance_Node_x)print('当前最近邻节点:',self.nearest_point)print('当前最近邻距离:',self.nearest_value)if abs(x[axis]-node.data[axis])<=self.nearest_value:#另外一个节点包含的超球体和当前超球体相交if x[axis]<node.data[axis]:travel(node.rchild,depth+1)else:travel(node.lchild,depth+1)travel(tree)#递归到叶子节点return self.nearest_point,self.nearest_valuedef dist(self, x_1, x_2,p=2):#计算闵可夫斯基距离值，默认为2（即欧几里得距离）x = x_1 - x_2x = np.power(np.abs(x),p)x = np.power(np.sum(x),1/p)return x
print(25*'=','构建kd树',25*'=')
x_train = np.array([[2, 3],[5, 4],[9, 6],[4, 7],[8, 1], [7, 2]])
kd_tree = KD_Tree()#创建一个KD树对象
head = kd_tree.create(x_train,0)#使用KD树create方法构建完整的KD树
print(20*'=','基于kd树的最近邻查找',20*'=')
# kd_tree.preOrder(head)
x_test = np.array([3,4])#定义测试样本
nearest_point, nearest_value = kd_tree.search(head, x_test)
print(40*'*')
print(nearest_point)
print(nearest_value)

程序执行结果展示

========================= 构建kd树 =========================
当前切分属性:0
排序后的数据集: [[2 3][4 7][5 4][7 2][8 1][9 6]]
当前切分节点: [7 2]
左子树数据集:[[2 3][4 7][5 4]]
右子树数据集:[[8 1][9 6]]
****************************************
当前切分属性:1
排序后的数据集: [[2 3][5 4][4 7]]
当前切分节点: [5 4]
左子树数据集:[[2 3]]
右子树数据集:[[4 7]]
****************************************
当前切分属性:0
排序后的数据集: [[2 3]]
当前切分节点: [2 3]
****************************************
当前切分属性:0
排序后的数据集: [[4 7]]
当前切分节点: [4 7]
****************************************
当前切分属性:1
排序后的数据集: [[8 1][9 6]]
当前切分节点: [9 6]
左子树数据集:[[8 1]]
****************************************
当前切分属性:0
排序后的数据集: [[8 1]]
当前切分节点: [8 1]
****************************************
==================== 基于kd树的最近邻查找 ====================
****************************************
None
None