scipy.spatial.

KDTree#

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

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

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

参数:

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

说明

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

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

可以查询该树以获取任何给定点的 r 个最近邻（可以选择仅返回该点最大距离内的那些邻居）。也可以查询 r 个近似最近邻，效率会大大提高。

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

属性:

datandarray，形状 (n,m): 要索引的 n 个维度为 m 的数据点。除非为了生成一个连续的双精度数组是必要的，否则此数组不会被复制。如果使用 copy_data=True 构建 kd 树，则数据也会被复制。
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)	计算稀疏距离矩阵。