scipy.spatial.

KDTree#

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

用於快速最近鄰搜尋的 kd 樹。

此類別提供了一組 k 維點的索引，可用於快速查找任何點的最近鄰。

參數:

dataarray_like，形狀 (n,m): 要建立索引的 m 維 n 個資料點。除非為了產生連續的雙精度浮點數組是必要的，否則不會複製此陣列，因此修改此資料將導致錯誤的結果。如果使用 copy_data=True 建置 kd 樹，也會複製資料。
leafsize正整數，可選: 演算法切換為暴力搜尋的點數。預設值：10。
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 維度的 boxsize。輸入資料應包裝到 \([0, L_i)\) 中。如果任何資料超出此範圍，則會引發 ValueError。

註解

使用的演算法在 Maneewongvatana 和 Mount 1999 中描述。一般概念是 kd 樹是一個二元樹，其每個節點代表一個軸對齊的超矩形。每個節點指定一個軸，並根據點沿該軸的坐標是大於還是小於特定值來分割點集。

在建構過程中，軸和分割點由「滑動中點」規則選擇，這確保了單元格不會都變得又長又薄。

可以查詢樹以獲取任何給定點的 r 個最近鄰（可選地僅返回點的某個最大距離內的鄰居）。也可以查詢樹，以顯著提高效率的方式，來獲取 r 個近似最近鄰。

對於高維度（20 維已經很大），不要期望這比暴力搜尋運行得快得多。高維最近鄰查詢是計算機科學中一個重要的開放問題。

屬性:

datandarray，形狀 (n,m): 要建立索引的 m 維 n 個資料點。除非為了產生連續的雙精度浮點數組是必要的，否則不會複製此陣列。如果使用 copy_data=True 建置 kd 樹，也會複製資料。
leafsize正整數: 演算法切換為暴力搜尋的點數。
mint: 單個資料點的維度。
nint: 資料點的數量。
maxesndarray，形狀 (m,): n 個資料點在每個維度中的最大值。
minsndarray，形狀 (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, ...])	查找點 (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)	計算稀疏距離矩陣。