Ⅰ 02 KNN算法 - KD Tree
KD Tree 是KNN算法中用于计算最近邻的快速简便的构建方式。
当样本量少的时候，用 brute 直接搜索最近邻的方式是可行的。即计算到所有样本的距离。但当样本量庞大时，直接计算所有样本距离的工作量很大，这种情况使用 KD Tree 可以节约大量时间成本。
KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用 方差最大 的第k维特征n k 作为 根节点 。对于这个特征，选择取值中的 中位数 n kv 作为样本的划分点，对于小于该值的样本划分到 左子树 ，对于大于等于该值的样本划分到 右子树 ，对左右子树采用同样的方式找 方差最大的特征 作为 根节点 ，递归产生KD Tree。
为什么要选择方差最大的进行划分？
构建树的目的是加快我的搜索过程。
既然我想加快我的搜索过程，要就意味着我最终的数据落在某个叶子节点上。我希望只需搜索整个二叉树的某一些列即可，那么最好的划分方式，就是让我的每个分支上数据的差异性最大化。
那么衡量数据差异性的最基础的数学指标是什么？
是方差。方差越大，意味着数据的离散程度就越大，我将离散程度由大到小的数据一分为二，方差小意味着数据更集中到了一起。
现在有一个二维样本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、计算x1和x2每一列对应的方差
a、通过pandas计算出的是 样本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通过numpy计算出的是 总体方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一个树的划分：基于x 1 进行划分
[2,4,5,7,8,9]的中位数是5和7的平均值6。
虽然严格意义上说中位数是6，但是在计算机中我们人为得定义x 1 的中位数是7。
左侧：（2,3）（5,4）（4,7） （7,2）
右侧: （9,6）（8,1）
第二个树的划分：根据右侧（9,6）（8,1）的x 2 进行划分
下侧：x 2 ≤ 6；上侧x 2 ＞6
第二个树的划分：根据左侧（2,3）（5,4）（4,7） （7,2）的x 2 进行划分
寻找2、3、4、7的中位数 4 进行划分
....
注意：每次生成的划分都是一个矩形。当叶子节点无法被继续划分的时候，KD树的构建完成，递归结束。
我们生成了KD Tree后，现在就可以去预测测试集里面的样本目标点了。
1、对于一个目标点，先在KD树里找到包含目标点的叶子节点。
2、以目标点为圆心，以 目标点 到 叶子节点样本实例 的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。
3、然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交。
4、如果相交就倒这个子节点寻找着是否有更加近的近邻，有的话就更新最近邻。
5、如果不相交，直接返回父节点中的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束。
6、此时保存的最近邻节点就是最终的最近邻。
如果现在想找(2,4.5)这点的最近邻，该如何操作？
1、画出二叉树：
2、寻找(2,4.5)这点：
一个比较好的理解方式：首先找到第一个最近邻，然后画出一个圆。然后逐渐收缩圆的半径，查看每次缩小后的圆是否能够和矩形相交于一个更小的最近邻点，如果有则更新。直到回到根节点。
Ⅱ 为啥knn算法的数据结构是kd树
很明显，
kd树只是一种为了提高knn算法查找效率的一种数据结构，当然还有其他的数据结构了，比如ball-tree，https://en.wikipedia.org/wiki/Ball_tree
Ⅲ KNN算法-4-算法优化-KD树
KNN算法的重要步骤是对所有的实例点进行快速k近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询操作时，可以使用kd树对查询操作进行优化。
Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。
k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想象一个三维(多维有点为难你的想象力了)空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：
首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此4个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为8个子空间，此8个子空间即为叶子节点。
常规的k-d tree的构建过程为：
对于构建过程，有两个优化点：
例子：采用常规的构建方式，以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明k-d tree的构建过程：
如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。
如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：
kd树的检索是KNN算法至关重要的一步，给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索。
如在构建好的k-d tree上搜索(3,5)的最近邻时，对二维空间的最近邻搜索过程作分析。
首先从根节点(7,2)出发，将当前最近邻设为(7,2)，对该k-d tree作深度优先遍历。
以(3,5)为圆心，其到(7,2)的距离为半径画圆（多维空间为超球面），可以看出(8,1)右侧的区域与该圆不相交，所以(8,1)的右子树全部忽略。
接着走到(7,2)左子树根节点(5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。
以(3,5)为圆心，其到(5,4)的距离为半径画圆，发现(7,2)右侧的区域与该圆不相交，忽略该侧所有节点，这样(7,2)的整个右子树被标记为已忽略。
遍历完(5,4)的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以(3,5)的最近邻为(5,4)。
举例：查询点（2.1,3.1）
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯'操作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。
举例：查询点（2，4.5）
一个复杂点了例子如查找点为（2，4.5），具体步骤依次如下：
上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。
一般来讲，最临近搜索只需要检测几个叶子结点即可，如下图所示：
但是，如果当实例点的分布比较糟糕时，几乎要遍历所有的结点，如下所示：
研究表明N个节点的K维k-d树搜索过程时间复杂度为： 。
同时，以上为了介绍方便，讨论的是二维或三维情形。但在实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降，几乎接近贪婪线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。
Sklearn中有KDTree的实现，仅构建了一个二维空间的k-d tree，然后对其作k近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。
Ⅳ opencv中是否有kdtree算法
有，位于opencv320\opencv\sources\moles\ml\src
Ⅳ python 如何画出KD数
简单的KNN算法在为每个数据点预测类别时都需要遍历整个训练数据集来求解距离，这样的做法在训练数据集特别大的时候并不高效，一种改进的方法就是使用kd树来存储训练数据集，这样可以使KNN分类器更高效。
KD树的主要思想跟二叉树类似，我们先来回忆一下二叉树的结构，二叉树中每个节点可以看成是一个数，当前节点总是比左子树中每个节点大，比右子树中每个节点小。而KD树中每个节点是一个向量(也可能是多个向量)，和二叉树总是按照数的大小划分不同的是，KD树每层需要选定向量中的某一维，然后根据这一维按左小右大的方式划分数据。在构建KD树时，关键需要解决2个问题：（1）选择向量的哪一维进行划分（2）如何划分数据。第一个问题简单的解决方法可以是选择随机选择某一维或按顺序选择，但是更好的方法应该是在数据比较分散的那一维进行划分（分散的程度可以根据方差来衡量）。好的划分方法可以使构建的树比较平衡，可以每次选择中位数来进行划分，这样问题2也得到了解决。下面是建立KD树的Python代码：
def build_tree(data, dim, depth):
"""
建立KD树
Parameters
----------
data:numpy.array
需要建树的数据集
dim:int
数据集特征的维数
depth:int
当前树的深度
Returns
-------
tree_node:tree_node namedtuple
树的跟节点
"""
size = data.shape[0]
if size == 0:
return None
# 确定本层划分参照的特征
split_dim = depth % dim
mid = size / 2
# 按照参照的特征划分数据集
r_indx = np.argpartition(data[:, split_dim], mid)
data = data[r_indx, :]
left = data[0: mid]
right = data[mid + 1: size]
mid_data = data[mid]
# 分别递归建立左右子树
left = build_tree(left, dim, depth + 1)
right = build_tree(right, dim, depth + 1)
# 返回树的根节点
return Tree_Node(left=left,
right=right,
data=mid_data,
split_dim=split_dim)
对于一个新来的数据点x，我们需要查找KD树中距离它最近的节点。KD树的查找算法还是和二叉树查找的算法类似，但是因为KD树每次是按照某一特定的维来划分，所以当从跟节点沿着边查找到叶节点时候并不能保证当前的叶节点就离x最近，我们还需要回溯并在每个父节点上判断另一个未查找的子树是否有可能存在离x更近的点（如何确定的方法我们可以思考二维的时候，以x为原点，当前最小的距离为半径画园，看是否与划分的直线相交，相交则另一个子树中可能存在更近的点），如果存在就进入子树查找。
当我们需要查找K个距离x最近的节点时，我们只需要维护一个长度为K的优先队列保持当前距离x最近的K个点。在回溯时，每次都使用第K短距离来判断另一个子节点中是否存在更近的节点即可。下面是具体实现的python代码：
def search_n(cur_node, data, queue, k):
"""
查找K近邻，最后queue中的k各值就是k近邻
Parameters
----------
cur_node:tree_node namedtuple
当前树的跟节点
data:numpy.array
数据
queue:Queue.PriorityQueue
记录当前k个近邻，距离大的先输出
k:int
查找的近邻个数
"""
# 当前节点为空，直接返回上层节点
if cur_node is None:
return None
if type(data) is not np.array:
data = np.asarray(data)
cur_data = cur_node.data
# 得到左右子节点
left = cur_node.left
right = cur_node.right
# 计算当前节点与数据点的距离
distance = np.sum((data - cur_data) ** 2) ** .5
cur_split_dim = cur_node.split_dim
flag = False # 标记在回溯时是否需要进入另一个子树查找
# 根据参照的特征来判断是先进入左子树还是右子树
if data[cur_split_dim] > cur_data[cur_split_dim]:
tmp = right
right = left
left = tmp
# 进入子树查找
search_n(left, data, queue, k)
# 下面是回溯过程
# 当队列中没有k个近邻时，直接将当前节点入队，并进入另一个子树开始查找
if len(queue) < k:
neg_distance = -1 * distance
heapq.heappush(queue, (neg_distance, cur_node))
flag = True
else:
# 得到当前距离数据点第K远的节点
top_neg_distance, top_node = heapq.heappop(queue)
# 如果当前节点与数据点的距离更小，则更新队列（当前节点入队，原第k远的节点出队）
if - 1 * top_neg_distance > distance:
top_neg_distance, top_node = -1 * distance, cur_node
heapq.heappush(queue, (top_neg_distance, top_node))
# 判断另一个子树内是否可能存在跟数据点的距离比当前第K远的距离更小的节点
top_neg_distance, top_node = heapq.heappop(queue)
if abs(data[cur_split_dim] - cur_data[cur_split_dim]) < -1 * top_neg_distance:
flag = True
heapq.heappush(queue, (top_neg_distance, top_node))
# 进入另一个子树搜索
if flag:
search_n(right, data, queue, k)525354555657
以上就是KD树的Python实践的全部内容，由于本人刚接触python不久，可能实现上并不优雅，也可能在算法理解上存在偏差，如果有任何的错误或不足，希望各位赐教。
Ⅵ 2 Kd树的构造与搜索
实现kNN算法时，最简单的实现方法就是线性扫描，正如我们上一章节内容介绍的一样-> K近邻算法 ，需要计算输入实例与每一个训练样本的距离。当训练集很大时，会非常耗时。
为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，KD-Tree就是其中的一种方法。
K维空间数据集
其中
随机生成 13 个点作为我们的数据集
首先先沿 x 坐标进行切分，我们选出 x 坐标的中位点，获取最根部节点的坐标
并且按照该点的x坐标将空间进行切分，所有 x 坐标小于 6.27 的数据用于构建左分支，x坐标大于 6.27 的点用于构建右分支。
在下一步中 ,对应 y 轴，左右两边再按照 y 轴的排序进行切分，中位点记载于左右枝的节点。得到下面的树，左边的 x 是指这该层的节点都是沿 x 轴进行分割的。
空间的切分如下
下一步中 ，对应 x 轴，所以下面再按照 x 坐标进行排序和切分，有
最后只剩下了叶子结点，就此完成了 kd 树的构造。
输入：已构造的kd树，目标点x
输出：x的k个最近邻集合L
KD-Tree的平均时间复杂度为 ，N为训练样本的数量。
KD-Tree试用于训练样本数远大于空间维度的k近邻搜索。当空间维数接近训练样本数时，他的效率会迅速下降，几乎接近线性扫描。
设我们想查询的点为 p=(−1,−5)，设距离函数是普通的距离，我们想找距离目标点最近的 k=3 个点。如下：
首先我们按照构造好的KD-Tree，从根结点开始查找
和这个节点的 x 轴比较一下，p 的 x 轴更小。因此我们向左枝进行搜索：
接下来需要对比 y 轴
p 的 y 值更小，因此向左枝进行搜索：
这个节点只有一个子枝，就不需要对比了。由此找到了叶子节点 (−4.6,−10.55)。
在二维图上是蓝色的点
此时我们要执行第二步，将当前结点插入到集合L中，并记录下 L=[(−4.6,−10.55)]。访问过的节点就在二叉树上显示为被划掉的好了。
然后执行第三步，不是最顶端节点。我回退。上面的结点是 (−6.88,−5.4)。
执行 3a，因为我们记录下的点只有一个，小于 k=3，所以也将当前节点记录下，插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4)].。 因为当前节点的左枝是空的，所以直接跳过，继续回退，判断不是顶部根节点
由于还是不够三个点，于是将当前点也插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)]。
此时发现，当前节点有其他的分枝，执行3b，计算得出 p 点和 L 中的三个点的距离分别是 6.62, 5.89, 3.10，但是 p 和当前节点的分割线的距离只有 2.14，小于与 L 的最大距离：
因此，在分割线的另一端可能有更近的点。于是我们在当前结点的另一个分枝从头执行步骤1。好，我们在红线这里：
此时处于x轴切分，因此要用 p 和这个节点比较 x 坐标:
p 的 x 坐标更大，因此探索右枝 (1.75,12.26)，并且发现右枝已经是最底部节点，执行步骤2与3a。
经计算，(1.75,12.26) 与 p 的距离是 17.48，要大于 p 与 L 的距离，因此我们不将其放入记录中。
然后 回退，判断出不是顶端节点，往上爬。
执行3a，这个节点与 p 的距离是 4.91，要小于 p 与 L 的最大距离 6.62。
因此，我们用这个新的节点替代 L 中离 p 最远的 (−4.6,−10.55)。
然后3b，我们比对 p 和当前节点的分割线的距离
这个距离小于 L 与 p 的最大距离，因此我们要到当前节点的另一个枝执行步骤1。当然，那个枝只有一个点。
计算距离发现这个点离 p 比 L 更远，因此不进行替代。
然后回退，不是根结点，我们向上爬
这个是已经访问过的了，所以再向上爬
再爬
此时到顶点了 。所以完了吗？当然不，还要执行3b呢。现在是步骤1的回合。
我们进行计算比对发现顶端节点与p的距离比L还要更远，因此不进行更新。
然后计算 p 和分割线的距离发现也是更远。
因此也不需要检查另一个分枝。
判断当前节点是顶点，因此计算完成！输出距离 p 最近的三个样本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)]。
声明：此文章为本人学习笔记，参考于： https://zhuanlan.hu.com/p/23966698