「算法」 KD Tree
一、KD-Tree
1. 介绍
- KD-Tree 是 k 维树的缩写；
- 是在 k 维欧几里德空间上用来组织点的数据结构；
- 是每个节点都为k维点的二叉树；所有非叶子节点可以看作是一个超平面，它把空间分割成两个半空间，该节点的选择与k维中垂直于超平面的那一维有关，其法线为该维度上的单位向量；
- k-d 树是空间二分树（Binary space partitioning ）的一种特殊情况；
2. 应用
k-d 树 可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）；
二、KD-Tree 运算
1. 创建
- 在 K 维数据中选取一个维度 \(K_i\)；
- 在 \(K_i\) 维度上选取中值，并以此将数据划分为两个子集，此中值即为根节点；
- 在两个子集上分别重复上述过程，所得数据作为上述节点的叶节点；
根据分割面选择策略的不同，有多种创建方法:
最典型的轮流法，最大方差法
2. 删除
3. 修改
4. 平衡
5. 查找-最邻近搜索
找出在树中与输入点最接近的点：
从根节点按创建时的规则移动到叶节点；递归回来，此过程中，计算每个节点与输入的距离，并比较；
（1）从根节点开始，递归的往下移；往左还是往右的决定方法与插入元素的方法一样(如果输入点在分区面的左边则进入左子节点，在右边则进入右子节点)；
（2）一旦移动到叶节点，将该节点当作「目前最佳点」；
（3）解开递归，并对每个经过的节点运行下列步骤：
a. 如果目前所在点比目前最佳点更靠近输入点，则将其变为目前最佳点；
b. 检查另一边子树有没有更近的点，如果有则从该节点往下找；
（4）当根节点搜索完毕后完成最邻近搜索；
三、实践
- OpenCV
Bruteforce matcher：暴力法
Flann-based matcher：快速近似最近邻检索
三、思考
- KD-Tree 相比循环，怎么节省了搜索时间
why
四、扩展
- KDTree 中涉及回溯操作，所以对高维向量并不友好；通常维度超过 200 效率就不好，此时应该用 Ball Tree；
why
附录
A. KD-Tree 的创建方法
轮流法
- 选择轴/确定分割面：各维度轮流作为分割面的轴；
以三维空间为例，若根节点是 x 轴垂直分割面，则其子节点皆为 y 轴垂直分割面，其孙节点皆为 z 轴垂直分割面，其曾孙节点则皆为 x 轴垂直分割面，依此类推； - 选择分割点：取该轴坐标的中位数；
此法会产生一个平衡的 k-d 树；然而，平衡的树不一定对每个应用都是最佳的；
why-什么情况下不好
最大方差法
- 选择轴/确定分割面：以方差最大的维度作为分割面的轴；
- 选择分割点：取该轴坐标的中位数；
B. 资料
- libkdtree++, an open-source STL-like implementation of ‘‘k’‘-d trees in C++.
- A tutorial on KD Trees
- kdtree A simple C library for working with KD-Trees
- libANN Approximate Nearest Neighbour Library includes a ‘‘k’‘-d tree implementation
- KD-Tree 算法原理及实现
- K 均值算法原理及初探
Comments