实现 k 近邻法时，主要考虑的问题是如何对训练数据进行快速 k 近邻搜索，这点在如下的两种情况时，显得尤为必要：
（1）特征空间的维度大（2）训练数据的容量很大时
k 近邻法的最简单的实现是现行扫描（linear scan），这时需计算输入实例与每一个训练实例的距离，但训练集很大时，计算非常耗时，这种方法是不可行的。
为了提高 k 近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。如本文介绍的 kd 树（kd tree，k-dimensional tree）方法（这里的 k 表示样本集的维度，与 k近邻的 k 无关）。
构造 kd 树
kd 树是一种对 k 维空间中的实例进行存储以便对其进行快速检索的树形数据结构。kd树是一种二叉树，表示对 k 维空间的一次划分（partition）。构造 kd 树相当与不断地用垂直于坐标轴（沿着每一个属性列，d=1,2,…,k）的超平面（hyperplane）将 k 维空间划分。
通常依次选择坐标轴对空间划分，选择训练实例点在选定坐标轴上的中位数（median）为切分点。这样得到的 kd 树是平衡的，平衡的 kd 树未必就是最优的。
class Node:def __init__(self, point):# point 表示切分点self.left = Noneself.right = Noneself.point = pointdef median(l):m = len(l)/2return l[m], mdef build_kdtree(X, d, depth):k = len(X[0])X = sorted(X, key=lambda x: x[d])p, m = median(X)tree = Node(p)print p, depthif m > 0:tree.left = build_kdtree(X[:m], (d+1)%k, depth+1)if (m+1) < len(X):tree.right = build_kdtree(X[m+1:], (d+1)%k, depth+1)return tree
搜索 kd 树
class Node:def __init__(self, point):self.left = Noneself.right = Noneself.parent = Noneself.point = pointdef set_left(self, left):self.left = leftleft.parent = selfdef set_right(self, right):self.right = rightright.parent = selfdef search_kdtree(tree, d, target): k = len(tree[0])if tree.point[d] < target[d]:if tree.right != None:return search_kdtree(tree.right, (d+1)%k, target)else:if tree.left != None:return search_kdtree(tree.left, (d+1)%k, target)def update_best(t, best):if t == None: return t = t.pointd = euclidean(t, target)if d < best[1]:best[1] = dbest[0] = tbest = [tree.point, float('inf')]while tree.parent != None:update_best(tree.parent.left, best)update_best(tree.parent.right, best)tree = tree.parentreturn best[0]
分析
如果实例点是随机分布的，kd搜索树的平均时间复杂度为 O(logN)，N<script id="MathJax-Element-5" type="math/tex">N</script> 表示训练实例数。kd 树搜索更适用于训练实例数远大于空间维数时的 k 近邻搜索，当空间维数接近训练实例数（非常畸形，也即接近线性的一颗不平衡的二叉树）时，它的效率会迅速下降，几乎接近线性扫描。
References
[1] k 近邻法
如果觉得《机器学习基础（四十三）—— kd 树（ k 近邻法的实现）》对你有帮助，请点赞、收藏，并留下你的观点哦！
