序

我们都知道 KNN 分类算法有一个缺点，就是在找样本的 K 个最近邻时，需要计算该样本和其他所有样本之间的距离，并对距离进行排序，才能挑选出前 K 个距离最小的。

这个过程中计算量很大，效率低，使得 KNN 难以应用于大数据集。

那么有什么方式能够快速求出样本的最近邻呢？

答案是有，那就是本文要介绍的数据结构：k-d树

一、kd-tree 简介

kd-tree（k-dimensional 树的简称），是一种对 k 维空间中的实例点进行存储以便对其进行 快速检索 的树形数据结构。（也就是说，用一种方式将所有点组织成树形结构，利于快速检索）

主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。

k-d树是空间二分树（Binary space partitioning ）的一种特殊情况。

k-d树是每个节点都为 k 维点的二叉树。

该树中的所有 非叶子节点 可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点。

选择超平面的方法如下：每个节点都与 k 维中垂直于超平面的那一维有关。因此，如果选择按照 x 轴划分，所有 x 值小于指定值的节点都会出现在左子树，所有 x 值大于指定值的节点都会出现在右子树。这样，超平面可以用该 x 值来确定，其法线为 x 轴的单位向量。

Kd-Tree的构建算法：

在 K 维数据集合中选择具有最大方差的维度 k ，然后在该维度上选择 中位数 节点 m 为超平面对该数据集合进行划分，得到两个子集合；同时创建一个树结点node，用于存储该节点 m ；
对两个子集合重复（1）步骤的过程，直至所有子集合都不能再划分为止；如果某个子集合不能再划分时，则将该子集合中的数据保存到叶子结点（leaf node）。

也就是说，先找一个维度（拥有最大方差），用中值对数据进行划分，然后再找一个维度，再用中值对数据进行划分…，直到所有的节点都成为叶子节点被记录在树中。

构建好一棵Kd-Tree后，下面给出利用Kd-Tree进行最近邻查找的算法：

现在有一个待分类样本 Q：