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_nodesbool, 可选
如果为 True，则构建 kd-树以将超矩形收缩到实际数据范围。这通常会生成一个更紧凑的树，该树对退化输入数据具有鲁棒性，并以更长的构建时间为代价提供更快的查询。默认值：True。
- copy_databool, 可选
如果为 True，数据总是被复制以保护 kd-树免受数据损坏。默认值：False。
- balanced_treebool, 可选
如果为 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正整数
算法切换到暴力搜索的点数。
- mint
单个数据点的维度。
- nint
数据点的数量。
- maxesndarray, 形状 (m,)
n 个数据点在每个维度上的最大值。
- minsndarray, 形状 (m,)
n 个数据点在每个维度上的最小值。
- tree对象, class cKDTreeNode
此属性公开了 cKDTree 对象中根节点的 Python 视图。kd-树的完整 Python 视图在第一次访问时动态创建。此属性允许您在 Python 中创建自己的查询函数。
- sizeint
树中的节点数。
方法
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)计算稀疏距离矩阵
附注
所使用的算法在 [1] 中描述。其基本思想是 kd-树是一种二叉树，其每个节点代表一个轴对齐的超矩形。每个节点指定一个轴并根据点沿该轴的坐标是大于还是小于某个特定值来分割点集。
在构建过程中，轴和分割点是根据“滑动中点”规则选择的，这确保了单元格不会都变得又长又细。
可以查询树以获取任何给定点的 r 个最近邻（可选地只返回距离该点最大距离内的邻居）。也可以查询 r 个近似最近邻，从而大大提高效率。
对于高维度（20已经很高），不要期望它比暴力搜索运行得显著快。高维最近邻查询是计算机科学中一个重大的开放问题。
参考文献
[1]S. Maneewongvatana 和 D.E. Mount，“Analysis of approximate nearest neighbor searching with clustered point sets，”Arxiv 电子预印本，1999，https://arxiv.org/pdf/cs.CG/9901013