Drzewa k-d: Szybkie Wyszukiwanie najbliższego sąsiada w przestrzeni wielowymiarowej

Dlaczego sprawdzanie każdego punktu nie skali się

Najwyraźniej possible sposób na znalezienie najbliższego sasiedniego punktu polega na szukaniu siłą naiwnym: oblicz odległość zapytania do każdego punktu w zestawie danych, śledź najmniejszą odległość widoczną do tej pory i zwróć ten punkt, który ją osiągnął. Zawsze daje poprawny wynik, ale kosztuje ono O(n) czasu na każde zapytanie, ponieważ wszystkie n punkty muszą być odwiedzone niezależnie od sytuacji. Dla małej liczby punktów jest to błyskawiczne, ale dla systemu lokalizatora adresowego zawierającego miliony adresów lub systemu robotykowego, który musi sprawdzać bliskie przeszkody kilkakrotnie na sekundę, ponowne przeanalizowanie całego zestawu danych dla każdego zapytania staje się brzegiem. Nudne jest to, że większość tej pracy jest bezużyteczna: już po tym, jak znasz kandydat na najbliższy punkt 50 metrów dalej, nie ma potrzeby dokładnego obliczenia odległości do punktu w drugiej części miasta. Drzewo k-d to sposób na organizację danych w przedsprawdzaniu tak, aby wyszukiwanie mogło rozpoznać 'drugą stronę miasta' jako pojedyncze prunowalne gałąź zamiast tysięcy indywidualnych punktów do sprawdzenia jedno po drugim.

budowanie drzewa: podział na alternujących osiach

Drzewo k-d (krótkiemu zapisowi dla drzewa k-wymiarowego) organizuje zestaw punktów, dzieląc przestrzeń rekurencyjnie za pomocą hiperpłaszczyzn zgodnych z osiami. Na korze punkty są podzielone na dwa półprzestrzeni według współrzędnej w jednym wymiarze, co najczęściej polega na wyborze punktu medianowego wzdłuż tej osi, aby podział był równomierny. Punkty poniżej mediany wpadają do lewego poddrzewa, a punkty powyżej do prawego poddrzewa, a sam punkt medianowy staje się węzłem podziału. Kluczowe jest to, że wymiar podziału obraca się z głębokością: dla danych 2-wymiarowych możesz podzielić się na współrzędną x na głębokości 0, y na głębokości 1, ponownie na x na głębokości 2 i tak dalej, cyklicznie przechodząc przez wszystkie k wymiary w procesie opadu. Każdy podział dzieli pozostałe punkty prawie na pół, co pozwala budować równomierny drzewo w czasie O(n log n) ogólnie (znalezienie mediany wśród m punktów zajmuje około O(m) czasu, stosowanej przez O(log n) poziomów rekurencji). Wynikiem jest dwuczłonowe drzewo o głębokości około log2(n), w którym każdy węzeł reprezentuje prostokątny (lub w wyższych wymiarach, hiperprostokątny) obszar przestrzennego, z każdym dzieckiem obszarem zawartym w sposób stricte wewnątrz rodzica.

Szukanie: Spadaj, Potem Wróć i Wytnij

Zapytanie o najbliższy sąsiada zaczyna się tak jak wyszukiwanie binarne: na każdym węźle porównuje się współrzędną punktu zapytania w wymiarze rozdzielającym ten węzeł do wartości węzła, a następnie idzie w lewo lub prawo, aż dotrze do liścia. Punkt na tym liściu staje się początkowym „najlepszym obecnym” przypuszczeniem, z jakąś odległością r do zapytania. Ale to przypuszczenie nie musi być poprawne, ponieważ bliższy punkt mógłby leżeć dokładnie po stronie rozdzielającej, którą wyszukiwanie pomija. W związku z tym algorytm wraca w górę drzewa i na każdym przodkowym węźle zadaje tanie pytanie geometryczne: czy region, który nie został jeszcze wybrany, może zawierać punkt o odległości r od zapytania? To sprawdzane jest porównując r do odległości między punktem zapytania a samą płaszczyznę rozdzielającą, co to jedno wymiarowe odejmowanie. Jeśli ten nieprzeglądany region jest dalej niż obecna najlepsza odległość, całe drzewo na tej stronie wytniemy i pomijamy bez sprawdzania punktów wewnątrz; jeśli może zawierać coś bliższego, wyszukiwanie rekurencyjnie kontynuuje się do tego regionu i możliwe jest aktualne zaktualizowanie najlepszego obecnego. Ta decyzja o wytnięciu lub eksplorowaniu na każdym przodkowym węźle daje drzewom k-d ich szybkość: na równych drzewach z rozłożeniem punktów prawie jednorodnym, zapytanie dotyka tylko około O(log n) węzłów na średnim poziomie, ponieważ większość gałęzi jest eliminowana przez test wytnięcia bez żadnej obliczonej odległości dla każdego punktu.

Złośliwość wymiarowości

O(log n) zachowanie średnio-casowe nie jest darmowy posiłek, a zależy od liczby wymiarów k pozostającej w dobrej mierze modestnej, ogólnie w zakresie kilku do kilkudziesięciu. Gdy k rośnie, test przycinający słabnie bardzo: w wysokiej wymiarowości, objętość blisko 'kątów' obszaru znacząco przewyższa objętość blisko jego centrum, więc najbliższy prawdziwy sasiad punktu zapytania jest nieproporcjonalnie prawdopodobny na znajdując się po przeciwnej stronie granicy podziału, która wygląda odległym tylko w jednym kierunku, ale rzeczywiście jest blisko w ogólnej kwestii. Test geometryczny, który pozwala na przeskakiwanie gałęzi przy niskim wymiarowości, coraz częściej nie wyklucza niczego, więc coraz więcej gałęzi musi być badane zgodnie ze wszystkim. Ta zjawisko, często nazywane złośliwością wymiarowością, oznacza, że gdy k rośnie do setek, średnio-casowe wydajność zapytań drzewa k-d spada powrotnie ku O(n), takim samym koszcie jak szukanie brutalne liniowe, ale teraz z dodatkowym obciążeniem przeszukiwania drzewa na wierzchołku. W praktyce to dlaczego drzewa k-d są najbardziej skuteczne dla około 2 do 20 wymiarów, a wysokiej wymiarowości szukanie podobieństwa (np. w wstawkach tekstowych lub obrazów z setkami wymiarów) typowo przełącza się na metody przybliżone, takie jak haszowanie czułe na lokalizację lub grafy najbardziej podobnych sąsiadów.

Gdzie K-D drzewa pojawiają się w praktyce

K-D drzewa są niezmiernie przydatne w zastosowanych geometrii, ponieważ wiele rzeczywistych problemów redukuje się do 'znalezienia bliskiego obiektu', które powtarza się wielokrotnie. Aplikacje mapowe i logistyki korzystają z nich do odpowiedzi na pytania takie jak ' najbliżej leżąca stacja ładowania', ' najbliżej leżący sklep' lub ' najbliżej leżący kierowca dostaw'. W uczeniu maszynowym, klasyfikator najbliższych sąsiadów (k-NN) przewiduje etykietę nowego punktu danych poprzez znalezienie jego k najbardziej podobnych przykładów i przyjęcie głosu większościowego. Budowanie drzewa K-D nad danymi treningowymi zmienia to, co byłoby optymalizacją w czasie O(n) na szybsze zapytanie, co ma znaczenie przy klasyfikacji wielu nowych punktów względem dużego zestawu danych treningowych. Grafika komputerowa wykorzystuje drzewa K-D (oraz ich kreacje jak drzewa BSP) do przyspieszenia tracenia promieniowego, szybko określając, które z milionów trójkątów sceny dany promień mógłby możliwe jest przecięcie zamiast testowania każdego trójkąta w scenie. Robotyka i planowanie ruchu korzystają z nich do szybkiego wykrywania kolizji i pytań dotyczące najbardziej bliskich przeszkód, umożliwiając robotom lub samochodom autonomicznym wielokrotną sprawdzanie otoczenia względem chmury punktów zdetekowanych przeszkód wielokrotnie na sekundę bez ponownego skanowania całej chmury przy każdym testowaniu.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz K-D Trees: Fast Nearest-Neighbor Search in Multidimensional Space i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.