scipy.spatial.KDTree의 'leafsize'이해
문제 설명:
3D 공간에 150k 점이 있고 좌표가 [150k, 3] mm 단위의 행렬에 저장되어 있습니다.
p
반경 내에있는 주어진 지점의 모든 이웃을 찾고 싶습니다 r
. 그리고 저는 그것을 가장 정확한 방법으로하고 싶습니다.
내 leafsize
매개 변수를 어떻게 선택해야 합니까?
from scipy.spatial import KDTree
import numpy as np
pts = np.random.rand(150000,3)
T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)
neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)
np.allclose(sorted(neighbors1), sorted(neighbors2))
True
답변
이 함수 query_ball_point
는 모든 버전의 검색 트리에 대해 올바른 포인트 세트를 반환합니다. 이 leafsize
매개 변수는 쿼리 결과에 영향을주지 않고 결과 성능에만 영향을줍니다.
동일한 데이터 (그러나 다른 잎 크기 매개 변수)에 대해 아래에 표시된 두 개의 트리와 빨간색 원 안의 모든 점을 검색하는 쿼리를 상상해보십시오.

두 경우 모두 코드는 빨간색 원 안에있는 두 점만 반환합니다. 이것은 원과 교차하는 나무의 모든 상자에있는 모든 점을 선택하여 수행됩니다. 이것은 각각의 경우에 다른 양의 작업 (즉, 다른 성능)으로 이어집니다. 왼쪽 트리 (더 큰 잎 크기에 해당)의 경우 알고리즘은 원 안에 13 개의 점이 있는지 확인해야합니다 (상단 교차 상자에 6 개, 하단 교차 상자에 7 개). 오른쪽 트리 (잎 크기가 더 작음)에서는 3 개의 포인트 만 처리됩니다 (상단 교차 상자에 1 개, 하단 교차 상자에 2 개).
이 논리에 따라 항상 작은 리프 크기를 사용하는 것이 합리적이라고 생각할 수 있습니다. 이렇게하면 알고리즘 끝에서 실제 비교 횟수가 최소화됩니다 (포인트가 실제로 쿼리 영역에 있는지 결정). 그러나 그것은 그렇게 간단하지 않습니다. 더 작은 잎 크기는 더 깊은 나무를 생성하여 건설 시간과 나무 순회 시간에 비용을 추가합니다. 리프 수준 비교와 트리 순회 성능의 적절한 균형을 얻는 것은 실제로 트리로 들어가는 데이터 유형과 수행중인 특정 리프 수준 비교에 따라 달라집니다. 이것이 scipy가 leafsize 매개 변수를 인수로 제공하므로 특정 알고리즘에서 최상의 성능을 발휘하도록 조정할 수 있습니다.