cKDTree#
- class scipy.spatial.cKDTree(data, leafsize=16, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)#
用于快速最近邻查找的kd-树
此类别为一组k维点提供索引，可用于快速查找任何点的最近邻。
注意
cKDTree在功能上与KDTree完全相同。在 SciPy v1.6.0 之前，cKDTree具有更好的性能和略微不同的功能，但现在这两个名称仅出于向后兼容性原因而存在。如果不需要与 SciPy < 1.6 兼容，请优先使用KDTree。- 参数:
- dataarray_like, 形状 (n,m)
要索引的n个m维数据点。除非需要生成连续的双精度数组，否则此数组不会被复制，因此修改此数据将导致错误结果。如果kd-树是用 copy_data=True 构建的，则数据也会被复制。
- leafsize正整数，可选
算法切换到暴力搜索的点数。默认值：16。
- compact_nodes布尔值，可选
如果为 True，则构建kd-树以将超矩形缩小到实际数据范围。这通常会生成一个更紧凑的树，对退化输入数据具有鲁棒性，并以更长的构建时间为代价提供更快的查询。默认值：True。
- copy_data布尔值，可选
如果为 True，则始终复制数据以保护kd-树免受数据损坏。默认值：False。
- balanced_tree布尔值，可选
如果为 True，则使用中位数而不是中点来分割超矩形。这通常会生成更紧凑的树和更快的查询，但构建时间更长。默认值：True。
- boxsizearray_like 或标量，可选
将m维环面拓扑应用于KDTree。该拓扑由 \(x_i + n_i L_i\) 生成，其中 \(n_i\) 是整数，\(L_i\) 是第i维的盒大小。输入数据应封装在 \([0, L_i)\) 中。如果任何数据超出此边界，则会引发 ValueError。
- 属性:
- datandarray, 形状 (n,m)
要索引的n个m维数据点。除非需要生成连续的双精度数组，否则此数组不会被复制。如果kd-树是用
copy_data=True构建的，则数据也会被复制。- leafsize正整数
算法切换到暴力搜索的点数。
- m整数
单个数据点的维度。
- n整数
数据点的数量。
- maxesndarray, 形状 (m,)
n个数据点在每个维度上的最大值。
- minsndarray, 形状 (m,)
n个数据点在每个维度上的最小值。
- tree对象, 类 cKDTreeNode
此属性公开了 cKDTree 对象中根节点的 Python 视图。kd-树的完整 Python 视图在首次访问时动态创建。此属性允许您在 Python 中创建自己的查询函数。
- size整数
树中的节点数。
方法
count_neighbors(self, other, r[, p, ...])计算可以形成的附近对数。
query(self, x[, k, eps, p, ...])查询kd-树以查找最近邻
query_ball_point(self, x, r[, p, eps, ...])查找与点 x 距离 r 内的所有点。
query_ball_tree(self, other, r[, p, eps])查找 self 和 other 之间距离至多为 r 的所有点对
query_pairs(self, r[, p, eps, output_type])查找 self 中距离至多为 r 的所有点对。
sparse_distance_matrix(self, other, max_distance)计算稀疏距离矩阵
注意
所使用的算法在 Maneewongvatana 和 Mount 1999 中有所描述。基本思想是kd-树是一种二叉树，其每个节点代表一个与坐标轴对齐的超矩形。每个节点指定一个轴，并根据点在该轴上的坐标是否大于或小于某个特定值来分割点集。
在构建过程中，通过“滑动中点”规则选择轴和分割点，这确保了单元格不会都变得又长又细。
可以查询树以查找任何给定点的r个最近邻（可选地仅返回距离点某个最大距离内的点）。也可以以显着提高效率的方式查询r个近似最近邻。
对于高维度（20已经很高），不要指望这比暴力搜索运行得快多少。高维最近邻查询是计算机科学中一个重大的未解决问题。