kd树的实现
Katjas-kd-tree的Python项目详细描述
kd树实现
kd搜索树的一种实现，它具有查找最近邻的功能，在大型数据集上使用线性搜索需要很长时间。这就是kd搜索树的来源，因为它们可以一次排除大部分数据集。
这个项目是作为CS110/计算：用算法解决问题课程的最后一个项目创建的。
安装指南
打开命令中心并粘贴以下内容
pip install Katjas-kd-tree
如何运行
安装软件包后，输入
import kd_tree as kd
您现在可以使用以下功能
kd.build_tree(dict)
# this will build a kd-tree from a given dictionary of format key:[values]
kd.distance(lsta,lstb)
# returns the distance between two points a and b with coordinates given by lsta and lstb
kd.find_approx_nearest(tree,value)
# returns the approximate nearest neighbor for a given value
kd.find_exact_nearest(tree,value)
# returns the exact nearest element of the tree to the value
示例用例
在实验室（或CIELAB）颜色空间中的命名颜色数据集中查找最接近的颜色。这种颜色空间的工作原理类似于rbg颜色，但其设计是为了让看起来类似于huymans的颜色在颜色空间中彼此更接近。第一个维度是从亮到暗的光谱，另两个维度描述从负值到正值的绿-红和蓝-黄值。有关实验室颜色的详细信息：https://en.wikipedia.org/wiki/CIELAB_color_space
我们不能使用通常的快速搜索方法或二进制搜索树，因为数据有超过1维，不能简单地排序。因此，我们可以创建一个具有3维的树，其中每个新的级别都沿着一个新的维拆分，并根据需要迭代所有这些级别。这使得我们能够很快地得到最近邻的近似值，并且稍加努力，找到比线性搜索快的最近邻。
# importing a dataset of paint colors and their position in the LAB colorspace
with open ("paintcolors.json") as json_file:
paintcolors=json.load(json_file)
# creating a tree out of the paintcolors
painttree=kd.build_tree(paintcolors)
# finding the approximate and exact nearest color to [0,0,0]
print((kd.distance(kd.find_approx_nearest(painttree,[0,0,0]).value,[0,0,0]),
kd.find_approx_nearest(painttree,[0,0,0]).name,
kd.find_approx_nearest(painttree,[0,0,0]).value))
print(kd.find_exact_nearest(painttree,[0,0,0]))
这将返回近似和精确的最近颜色到[0，0，0]
（0.23327147726897515，“通用黑色”，[0.233007，0.010686，-0.0030215]）
（0.22615200000001437，“微光区”，[0.226152，5.54817E-08，5.84874E-08]）
生成的kd树如下所示（为了清楚起见，节点不在彼此上方）
如果您想自己运行此代码，请从https://github.com/katjadellalibera/KD-tree-implementation/blob/master/paintcolors.json下载数据，从https://github.com/katjadellalibera/KD-tree-implementation/blob/master/example.py下载代码
背景
1，时间复杂度：< > > > 线性搜索以O（n）复杂度运行，因为它必须检查每个值。FopyOnAdxxRealMead以$O（\log（n））的平均复杂度运行，因为它只需要下行一个深度为$\Logi2（n）$的二叉树。在最坏的情况下，我们有一个形状奇怪的树，就像只有两个节点的树，其中最坏的运行时可能是$o（n）$，因为每个节点都被访问。find_exact_nearest函数一次将排除较少的树，但仍在$o（\log（n））$中运行，只是具有较高的常数因子。{STR 1 }空间复杂度：< /强> BR/> 将数据点存储为节点而不是在字典或数组中仍然需要$O（n）$空间复杂度。可能有一个稍高的常数项k，代表分裂维度d和左右子指针，但总复杂度为o（n）$ < p > P >
依赖关系
实现依赖于预安装的包random、math和json以及numpy包。
欢迎加入QQ群-->： 979659372
