scipy.spatial.

KDTree#

class scipy.spatial.KDTree(data, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)[source]#

用于快速最近邻查找的 kd 树。

此类提供对一组 k 维点的索引，可用于快速查找任何点的最近邻。

参数：

dataarray_like, shape (n,m): 要索引的 m 维的 n 个数据点。除非需要生成一个连续的双精度数组，否则不会复制此数组，因此修改此数据会导致错误的结果。如果 kd 树是在 copy_data=True 的情况下构建的，则数据也会被复制。
leafsize正整数，可选: 算法切换到蛮力搜索的点数。默认值：10。
compact_nodes布尔值，可选: 如果为 True，则构建 kd 树以将超矩形缩小到实际数据范围。这通常会生成更紧凑的树，该树对退化的输入数据具有鲁棒性，并以构建时间更长为代价提供更快的查询。默认值：True。
copy_data布尔值，可选: 如果为 True，则始终复制数据以保护 kd 树免受数据损坏。默认值：False。
balanced_tree布尔值，可选: 如果为 True，则使用中位数而不是中点来分割超矩形。这通常会生成更紧凑的树，并以构建时间更长为代价提供更快的查询。默认值：True。
boxsizearray_like 或标量，可选: 对 KDTree 应用 m-d 环形拓扑。拓扑结构由 \(x_i + n_i L_i\) 生成，其中 \(n_i\) 是整数，\(L_i\) 是沿第 i 维的盒子大小。输入数据应包装在 \([0, L_i)\) 中。如果任何数据超出此范围，则会引发 ValueError。

备注

使用的算法在 Maneewongvatana 和 Mount 1999 中进行了描述。基本思想是 kd 树是一棵二叉树，其每个节点都表示一个轴对齐的超矩形。每个节点都指定一个轴，并根据其沿该轴的坐标是否大于或小于特定值来分割点集。

在构建过程中，轴和分割点由“滑动中点”规则选择，该规则确保单元格不会全部变长变细。

可以查询树以获取任何给定点的 r 个最近邻（可以选择只返回那些在该点的一定最大距离内的邻居）。还可以对其进行查询（效率大大提高），以获取 r 个近似最近邻。

对于高维度（20 已经是很大了），不要指望它比蛮力运行得快得多。高维最近邻查询是计算机科学中一个重要的开放性问题。

属性：

datandarray, shape (n,m): 要索引的 m 维的 n 个数据点。除非需要生成一个连续的双精度数组，否则不会复制此数组。如果 kd 树是在 copy_data=True 的情况下构建的，则数据也会被复制。
leafsize正整数: 算法切换到蛮力搜索的点数。
mint: 单个数据点的维数。
nint: 数据点的数量。
maxesndarray, shape (m,): n 个数据点在每个维度上的最大值。
minsndarray, shape (m,): n 个数据点在每个维度上的最小值。
sizeint: 树中节点的数量。

方法

`count_neighbors`(other, r[, p, weights, ...])	计算可以形成多少个附近的对。
`query`(x[, k, eps, p, distance_upper_bound, ...])	查询 kd 树以获取最近邻。
`query_ball_point`(x, r[, p, eps, workers, ...])	查找与点(s) 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)	计算稀疏距离矩阵。