scipy.spatial.

KDTree#

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

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

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

参数:

data类数组, 形状 (n,m): 要索引的 n 个 m 维数据点。除非为了生成连续的双精度数组而必需，否则不会复制此数组，因此修改此数据将导致错误结果。如果 kd 树使用 copy_data=True 构建，数据也会被复制。
leafsize正整数, 可选: 算法切换为暴力搜索的点数。默认值：10。
compact_nodes布尔值, 可选: 如果为 True，则 kd 树的构建会将超矩形缩小到实际数据范围。这通常会生成更紧凑的树，能够抵抗退化输入数据，并能加快查询速度，但会增加构建时间。默认值：True。
copy_data布尔值, 可选: 如果为 True，数据总是被复制以保护 kd 树免受数据损坏。默认值：False。
balanced_tree布尔值, 可选: 如果为 True，则使用中位数而不是中点来分割超矩形。这通常会生成更紧凑的树并加快查询速度，但会增加构建时间。默认值：True。
boxsize类数组或标量, 可选: 对 KDTree 应用 m 维环面拓扑。拓扑由 \(x_i + n_i L_i\) 生成，其中 \(n_i\) 是整数，\(L_i\) 是沿第 i 维的 boxsize。输入数据应封装在 \([0, L_i)\) 中。如果任何数据超出此边界，则会引发 ValueError。

属性:

datandarray, 形状 (n,m): 要索引的 n 个 m 维数据点。除非为了生成连续的双精度数组而必需，否则不会复制此数组。如果 kd 树使用 copy_data=True 构建，数据也会被复制。
leafsize正整数: 算法切换为暴力搜索的点数。
m整数: 单个数据点的维度。
n整数: 数据点的数量。
maxesndarray, 形状 (m,): n 个数据点在每个维度上的最大值。
minsndarray, 形状 (m,): n 个数据点在每个维度上的最小值。
size整数: 树中的节点数。

方法

`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)	计算稀疏距离矩阵。

备注

所使用的算法在 Maneewongvatana 和 Mount 1999 中有所描述。总体思想是 kd 树是一种二叉树，其每个节点代表一个与坐标轴对齐的超矩形。每个节点指定一个轴，并根据点的沿该轴的坐标是大于还是小于某个特定值来分割点集。

在构建过程中，轴和分割点是根据“滑动中点”规则选择的，这确保了所有单元格不会都变得又长又细。

该树可以查询任意给定点的 r 个最近邻（可选地只返回距离该点最大距离内的点）。它还可以查询 r 个近似最近邻，从而显著提高效率。

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