杏彩体育官网入口网址:最近邻搜索 KD树 生动图示理解笔记

　　最近邻搜索，不仅属于机器学习基础理论KNN的范畴，并且在实际工作比如 召回ANN 检索中也经常用到，如果小明当初能早些看到并行世界中我总结的这篇文章，肯定会有不一样的结果。这次我们就先来总结下 最近邻算法(NN)中的KD树的相关知识点。

　　最近邻搜索（Nearest Neighbor Search）是指在一个确定的距离度量和一个搜索空间内寻找与给定查询项距离最小的元素。暴力搜索的解法时间复杂度是O(n), 使用KD-tree 能降低时间复杂度。由于维数灾难，我们很难在高维欧式空间中以较小的代价找到精确的最近邻。近似最近邻搜索（Approximate Nearest Neighbor Search）则是一种通过牺牲精度来换取时间和空间的方式从大量样本中获取最近邻的方法。

　　本质上，k-d树是一种空间划分树，是一种平衡二叉树。将整个k维的向量空间不断的二分，从而划分为若干局部空间，然后搜索的时候，不断进行分支判断，选择其中的局部子空间，避免了全局空间搜索。举个例子，当k=3 的时间，KD-tree 就会将三维空间分割成如下图的形式：

　　1. 选择维度：KD树建树采用的是从m个样本的n维特征中，分别计算n个特征的取值的方差，用方差最大的第k维特征 来作为根节点。

　　3. 分割数据：对于所有第k维特征的取值小于 v的样本，我们划入左子树，对于第k维特征的取值大于等于 v的样本，我们划入右子树。

　　4. 递归迭代：对于左子树和右子树，我们采用和刚才同样的办法来找方差最大的特征来做更节点，将空间和数据集进一步细分，如此直到所有点都被划分。

　　6个数据点在x，y维度上的数据方差分别为39，28.63，在x轴上方差更大，所以分割维度为x。

　　根据x维上的值将数据排序，6个数据的中值(即中间大小的值)为7，所以分割数据点为（7,2）。这样，该节点的分割超平面就是直线). 左子空间和右子空间分别递归：

　　分割超平面x=7将整个空间分为两部分：x=7的部分为左子空间，包含3个节点={(2,3),(5,4),(4,7)}；另一部分为右子空间，包含2个节点={(9,6)，(8,1)}；然后左右子空间分别重复进行上述过程。

　　BBF（Best Bin First）是一种改进的k-d树最近邻查询算法。从上文KD树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”来决定的，并没有考虑查询路径上数据点本身的一些性质。

　　BBF的查询思路就是将“查询路径”上的节点进行排序，如按各自分割超平面（称为Bin）与查询点的距离排序。回溯检查总是从优先级最高的（Best Bin）的树节点开始。