KDTree#
- class scipy.spatial.KDTree(data, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)[源代码][源代码]#
kd-tree 用于快速最近邻查找。
此类提供了一个对一组 k 维点的索引，可用于快速查找任何点的最近邻。
- 参数:
- 数据array_like, 形状 (n,m)
要索引的维度为 m 的 n 个数据点。除非必须生成连续的双精度数组，否则不会复制此数组，因此修改此数据将导致错误结果。如果使用 copy_data=True 构建 kd-树，则数据也会被复制。
- leafsize正整数，可选
算法切换到暴力搜索的点数。默认值：10。
- 紧凑节点bool, 可选
如果为 True，kd-树将被构建以缩小超矩形到实际数据范围。这通常会生成一个更紧凑的树，对退化的输入数据具有鲁棒性，并在构建时间更长的情况下提供更快的查询。默认值：True。
- copy_databool, 可选
如果为 True，数据将始终被复制以保护 kd-树 免受数据损坏。默认值：False。
- 平衡树bool, 可选
如果为 True，则使用中位数来分割超矩形，而不是使用中点。这通常会生成更紧凑的树并加快查询速度，但代价是构建时间更长。默认值：True。
- boxsize类似数组或标量，可选
将 m-d 环形拓扑应用于 KDTree。该拓扑由 \(x_i + n_i L_i\) 生成，其中 \(n_i\) 是整数，\(L_i\) 是第 i 维的盒子大小。输入数据应包装到 \([0, L_i)\) 中。如果任何数据超出此范围，则会引发 ValueError。
- 属性:
- 数据ndarray, 形状 (n,m)
要索引的维度为 m 的 n 个数据点。除非有必要生成一个连续的双精度数组，否则不会复制此数组。如果使用 copy_data=True 构建 kd-tree，数据也会被复制。
- leafsize正整数
算法切换到暴力搜索的点数。
- m整数
单个数据点的维度。
- n整数
数据点的数量。
- 最大值ndarray, 形状 (m,)
n 个数据点在每个维度上的最大值。
- 分钟ndarray, 形状 (m,)
n 个数据点在每个维度上的最小值。
- 大小整数
树中的节点数量。
方法
count_neighbors(other, r[, p, weights, ...])计算可以形成多少对附近的配对。
query(x[, k, eps, p, distance_upper_bound, ...])查询 kd-树 以获取最近邻。
query_ball_point(x, r[, p, eps, workers, ...])查找距离点 x 在距离 r 内的所有点。
query_ball_tree(other, r[, p, eps])找出 self 和 other 之间所有距离不超过 r 的点对。
query_pairs(r[, p, eps, output_type])找到 self 中所有距离不超过 r 的点对。
sparse_distance_matrix(other, max_distance)计算一个稀疏距离矩阵。
innernode
叶节点
节点
注释
所使用的算法在 Maneewongvatana 和 Mount 1999 年有所描述。其基本思想是 kd-树是一个二叉树，每个节点代表一个轴对齐的超矩形。每个节点指定一个轴，并根据该轴上的坐标是否大于或小于特定值来分割点集。
在构建过程中，轴和分割点由“滑动中点”规则选择，这确保了单元格不会全部变得细长。
可以查询树以获取任何给定点最近的 r 个邻居（可选地仅返回那些在点某个最大距离内的邻居）。它还可以被查询，以显著提高效率，获取 r 个近似最近的邻居。
对于大维度（20 已经算大），不要期望它比暴力搜索运行得显著更快。高维最近邻查询是计算机科学中一个重大的开放问题。