构造KD树，并用KD树求最近邻点

本文是对《KD-tree的原理以及构建与查询操作的python实现》的解读

KD树是一种特殊的数据结构，Python中常用的数据结构无法表示该数据结构。作者将KD树分解为“节点树”，每个节点树包含有“根节点”、“切分维度”、“左子树”、“右子树”四部分。作者首先创建了一个类KD_node，并用该类的对象去表示每一个节点树，代码如下：

class KD_node: def __init__(self, point = None, split = None, LL = None, RR = None): """ point: 数据点 split: 划分域 LL，RR: 节点的左右子树 """ self.point = point self.split = split self.left = LL self.right = RR

对于切分维度，作者选取了样本在其上分量的方差达到最大的维度作为切分维度，理由是：方差越大，说明这个维度上的数据波动越大，，也就说明了他们就越不可能属于同一个空间，需要在这个维度上对点进行划分。首先定义生成KD树的函数createKDTree，用于生成KD树，代码如下：

def createKDTree(root, data_list): """ root: 当前的根节点（ 最终要将KD_node的一个对象赋值给root ） data_list: 数据点的集合(数组) return: 构造的KDTree的树根 """ LEN = len(data_list) if LEN == 0: return # 数据点的维度 dimension = len(data_list[0]) # 方差 max_var = 0; # 最后选择的划分域 split = 0; for i in range(dimension): # i 为“维度”循环变量 l1 = [] for t in data_list: # t 为以root为根节点的子树下的“训练数据”循环变量 l1.append(t[i]) var = computeVariance(l1) if var > max_var: max_var = var split = i # 根据划分域的数据对数据点进行排序 data_list = sorted( data_list, key = lambda x : x[split] ) # 选择下标为len/2的点作为切割点 point = data_list[LEN/2] root = KD_node(point, split) root.left = createKDTree(root.left, data_list[0:(LEN/2)]) root.right = createKDTree(root.right, data_list[(LEN/2 + 1):LEN]) return root def computeVariance(arrayList): """ arrayList: 存放的数据点 return: """ for ele in arrayList: ele = float(ele) LEN = len(arrayList) array = numpy.array(arrayList) sum1 = array.sum() # arrayList各元素之和 array2 = array*array sum2 = array2.sum() # arrayList各元素平方之和 mean = sum1/LEN variance = sum2/LEN - mean**2 return variance