Zrozumienie „leafsize” w scipy.spatial.KDTree

Question

Opis problemu:

Mam 150k punktów w przestrzeni 3D, których współrzędne są zapisane w macierzy o wymiarze [150k, 3] w mm.

Chcę znaleźć wszystkich sąsiadów danego punktu pznajdujących się w promieniu r. I chcę to zrobić w jak najdokładniejszy sposób.

Jak wybrać leafsizeparametr?

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

Answer 1

Funkcja query_ball_pointzwróci prawidłowy zestaw punktów dla dowolnej wersji drzewa wyszukiwania. leafsizeParametr nie ma wpływu na wyniki kwerendy, tylko wykonywania wyników.

Wyobraź sobie dwa drzewa pokazane poniżej dla tych samych danych (ale różnych parametrów rozmiaru liścia) i zapytanie wyszukujące wszystkie punkty wewnątrz czerwonego koła.

W obu przypadkach kod zwróci tylko dwa punkty, które znajdują się wewnątrz czerwonego koła. Odbywa się to poprzez zaznaczenie wszystkich punktów we wszystkich polach drzewa, które przecinają okrąg. W każdym przypadku prowadzi to do innego nakładu pracy (tj. Innej wydajności). W przypadku lewego drzewa (odpowiadającego większemu rozmiarowi liścia) algorytm musi sprawdzić, czy wewnątrz okręgu znajduje się 13 punktów (6 w górnej przecinającej się ramce i 7 w dolnej przecinającej się ramce). W prawym drzewie (które ma mniejszy rozmiar liścia) przetwarzane są tylko trzy punkty (jeden w górnym skrzynce przecinającej i dwa w dolnym skrzynce przecinającej).

Postępując zgodnie z tą logiką, możesz pomyśleć, że sensowne jest zawsze używanie małego rozmiaru liścia: zminimalizuje to liczbę rzeczywistych porównań na końcu algorytmu (zdecyduj, czy punkty rzeczywiście znajdują się w obszarze zapytania). Ale to nie jest takie proste: mniejszy rozmiar liścia wygeneruje głębsze drzewo, zwiększając koszt czasu budowy i czasu przemierzania drzewa. Uzyskanie właściwej równowagi między wydajnością przechodzenia przez drzewo z porównaniami na poziomie liścia w rzeczywistości zależy od typu danych wprowadzanych do drzewa i konkretnych porównań na poziomie liścia, które wykonujesz. Dlatego scipy dostarcza parametr rozmiaru liści jako argument, abyś mógł dostroić rzeczy, aby działały najlepiej na określonym algorytmie.