KDTree的原理及Python实现
1. 原理篇
我们⽤⼤⽩话讲讲KD-Tree是怎么⼀回事。
1.1 线性查
假设数组A为[0, 6, 3, 8, 7, 4, 11]，有⼀个元素x，我们要到数组A中距离x最近的元素，应该如何实现呢？⽐较直接的想法是⽤数组A中的每⼀个元素与x作差，差的绝对值最⼩的那个元素就是我们要的元素。假设x = 2，那么⽤数组A中的所有元素与x作差得到[-2, 4, 1, 6, 5, 2, 9]，其中绝对值最⼩的是1，对应的元素是数组A中的3，所以3就是我们的查结果。
1.2 ⼆分查
如果我们有⼤量的元素要在数组A中进⾏查，那么1.1的⽅式就显得不是那么⾼效了，如果数组A的长度为N，那么每次查都要进⾏N次操作，即算法复杂度为O(N)。
1. 我们把数组A进⾏升序排列，得到[0, 3, 4, 6, 7, 8, 11]；
2. 令x = 2，数组中间的元素是6，2⼩于6，所以2只可能存在于6的左边，我们只需要在数组[0, 3, 4]中继续查；
3. 左边的数组中间的元素是3，2⼩于3，所以2只可能存在于3的左边，即数组[0]；
4. 由于数组[0]⽆法再分割，查结束；
5. x需要跟我们最终到的0，以及倒数第⼆步到的3进⾏⽐较，发现2离3更近，所以查结果为3。
这种查⽅法就是⼆分查，其算法复杂度为O(Log2(N))。
1.3 BST
除了数组之外，有没有更直观的数据结构可以实现1.2的⼆分查呢？答案就是⼆分查树，全称Binary Search Tree，简称BST。把数组A建⽴成⼀个BST，结构如下图所⽰。我们只需要访问根节点，进⾏值⽐较来确定下⼀节点，如此循环往复直到访问到叶⼦节点为⽌。
1.4 多维数组
现在我们把问题加点难度，假设数组B为[[6, 2], [6, 3], [3, 5], [5, 0], [1, 2], [4, 9], [8, 1]]，有⼀个元素x，我们要到数组B中距离x最近的元素，应该如何实现呢？⽐较直接的想法是⽤数组B中的每⼀个元素与x求距离，距离最⼩的那个元素就是我们要的元素。假设x = [1, 1]，那么⽤数组A中的所有元素与x求距离得到[5.0, 5.4, 4.5, 4.1, 1.0, 8.5, 7.0]，其中距离最⼩的是1，对应的元素是数组B中的[1, 2]，所以[1, 2]就是我们的查结果。
1.5 再次陷⼊困境
如果我们有⼤量的元素要在数组B中进⾏查，那么1.4的⽅式就⼜显得不是那么⾼效了，如果数组B的长度为N，那么每次查都要进⾏N 次操作，即算法复杂度为O(N)。
1.6 什么是KD-Tree
这时候已经没办法⽤BST，不过我们可以对BST做⼀些改变来适应多维数组的情况。当当当当~，这时候该KD-Tree出场了。废话不多说，
先上图：
1.7 如何建⽴KD-Tree
您可能会问，刚在那张图的KD Tree⼜是如何建⽴的呢？ 很简单，只需要5步：
1. 建⽴根节点；
2. 选取⽅差最⼤的特征作为分割特征；
3. 选择该特征的中位数作为分割点；
4. 将数据集中该特征⼩于中位数的传递给根节点的左⼉⼦，⼤于中位数的传递给根节点的右⼉⼦；
5. 递归执⾏步骤2-4，直到所有数据都被建⽴到KD Tree的节点上为⽌。
不难看出，KD Tree的建⽴步骤跟BST是⾮常相似的，可以认为BST是KD Tree在⼀维数据上的特例。KD Tree的算法复杂度介于
O(Log2(N))和O(N)之间。
1.8 特征选取
您可能还会问，为什么⽅差最⼤的适合作为特征呢？ 因为⽅差⼤，数据相对“分散”，选取该特征来对数据集进⾏分割，数据散得
更“开”⼀些。
1.9 分割点选择
您可能⼜要问，为什么选择中位数作为分割点呢？ 因为借鉴了BST，选取中位数，让左⼦树和右⼦树的数据数量⼀致，便于⼆分查。
1.10 利⽤KD-Tree查元素
KD Tree建好之后，接下来就要利⽤KD Tree对元素进⾏查了。查的⽅式在BST的基础上⼜增加了⼀些难度，如下：
1. 从根节点开始，根据⽬标在分割特征中是否⼩于或⼤于当前节点，向左或向右移动。
2. ⼀旦算法到达叶节点，它就将节点点保存为“当前最佳”。
3. 回溯，即从叶节点再返回到根节点
4. 如果当前节点⽐当前最佳节点更接近，那么它就成为当前最好的。
5. 如果⽬标距离当前节点的⽗节点所在的将数据集分割为两份的超平⾯的距离更接近，说明当前节点的兄弟节点所在的⼦树有可能包含更近的点。因此需要对这个兄弟节点递归执⾏1-4步。
1.11 超平⾯
所以什么是超平⾯呢，听起来让⼈⼀脸懵逼。
以[0, 2, 0], [1, 4, 3], [2, 6, 1]的举例：
1. 如果⽤第⼆维特征作为分割特征，那么从三个数据点中的对应特征取出2, 4, 6，中位数是4；
2. 所以[1, 4, 3]作为分割点，将[0, 2, 0]划分到左边，[2, 6, 1]划分到右边；
3. 从⽴体⼏何的⾓度考虑，三维空间得⽤⼀个⼆维的平⾯才能把空间⼀分为⼆，这个平⾯可以⽤y = 4来表⽰；
4. 点[0, 2, 0]到超平⾯y = 4的距离就是 sqrt((2 - 4) ^ 2) = 2；
5. 点[2, 6, 1]到超平⾯y = 4的距离就是 sqrt((6 - 4) ^ 2) = 2。
2. 实现篇
本⼈⽤全宇宙最简单的编程语⾔——Python实现了KD-Tree算法，没有依赖任何第三⽅库，便于学习和使⽤。简单说明⼀下实现过程，更详细的注释请参考本⼈github上的代码。
2.1 创建Node类
初始化，存储⽗节点、左节点、右节点、特征及分割点。
class Node(object):
def __init__(self):
self.father = None
self.left = None
self.right = None
self.feature = None
self.split = None
2.2 获取Node的各个属性
def __str__(self):
return "feature: %s, split: %s" % (str(self.feature), str(self.split)) 2.3 获取Node的兄弟节点
@property
def brother(self):
if self.father is None:
ret = None
else:
if self.father.left is self:
ret = self.father.right
else:
ret = self.father.left
return ret
2.4 创建KDTree类
初始化，存储根节点。
class KDTree(object):
def __init__(self):
< = Node()
2.5 获取KDTree属性
便于我们查看KD Tree的节点值，各个节点之间的关系。
def __str__(self):
ret = []
i = 0
que = [(, -1)]
while que:
nd, idx_father = que.pop(0)
ret.append("%d -> %d: %s" % (idx_father, i, str(nd)))
if nd.left is not None:
que.append((nd.left, i))
if nd.right is not None:
que.append((nd.right, i))
i += 1
return "\n".join(ret)
2.6 获取数组中位数的下标
def _get_median_idx(self, X, idxs, feature):python获取数组长度
n = len(idxs)
k = n // 2
col = map(lambda i: (i, X[i][feature]), idxs)
sorted_idxs = map(lambda x: x[0], sorted(col, key=lambda x: x[1]))    median_idx = list(sorted_idxs)[k]
return median_idx
2.7 计算特征的⽅差

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。