Obliczanie odległości do k-tego najbliższego sąsiada dla wszystkich punktów w zestawie

W przypadku aplikacji uczenia maszynowego moja grupa musi obliczyć odległość euklidesową do tego najbliższego sąsiada w zbiorze dla każdego (dla od 5 do około 100 oraz kilkaset do kilku milionów). Obecnie podejście albo oczywiste z drzewem kd na , które gdy jest wysokie, ajest stosunkowo niski, nigdy nie wygrywa. (Wszystko jest w pamięci.) $k$ $X$ $x \in (X \cup Y) \subset \mathbb R^d$ $d$ $|X| \approx |Y|$ $O(d \lvert X \rvert \lvert X \cup Y \rvert)$ $X$ $d$ $|X|$

Wydaje się jednak, że musi istnieć lepszy sposób niż brutalna siła - przynajmniej taki, który wykorzystuje nierówność trójkąta, a może z hashami wrażliwymi na lokalizację. Racjonalnie ścisłe zbliżenie jest również potencjalnie w porządku.

Badania, które udało mi się znaleźć, wydają się koncentrować na problemie znalezienia pojedynczego najbliższego sąsiada (lub takiego, który jest w przybliżeniu najbliższy). Czy problem, którego szukam, ma inną nazwę, czy jest związek z powiązanym problemem, o którym nie myślałem?

reference-request cg.comp-geom near-neighbors Dougal
źródło

drzewa kd wykorzystują nierówność trójkąta. Czy próbowałeś użyć innych drzew do partycjonowania danych przestrzennych? Kolejna rzecz, nad którą możesz się zastanowić (nic nie wiem na temat algorytmu uczenia maszynowego), czy określone punkty mają tendencję do posiadania struktury, co może pomóc ci w szybkim znajdowaniu hiperpłaszczyzn i używaniu ich w drzewie podobnym do kd zamiast zwykłej mediany podział współrzędnych, który działa słabo w wysokich wymiarach.

Ross Snider,

@RossSnider dzięki za sugestie. I oczywiście drzewa KD używają nierówności trójkąta, ale myślałem o czymś, co byłoby szybsze niż brutalna siła. :) Jakie inne rodzaje drzew do partycjonowania danych przestrzennych poleciłbyś? Z listy Wikipedii wydaje się, że tylko drzewa vp wydają się mieć zastosowanie i nie wydają się lepsze od drzew kd dla odległości euklidesowej. Zastanowię się, czy istnieje lepszy sposób definiowania oddzielających hiperpłaszczyzn, ale nie przychodzi mi to do głowy.

Dougal,

Wydaje mi się, że miałem nadzieję, że fakt, że wiemy, że oceniamy to dla wszystkich (a także innych punktów), pozwoli na jakąś pomoc w algorytmie. Nie jestem jednak pewien, czy tak jest.

X

$X$

Dougal

co to typowo w aplikacjach?

k

$k$

Suresh Venkat

@SureshVenkat Zwykle używamy około 3, czasem trochę większego.

k

$k$

Dougal

Odpowiedzi:

Oto prosta sztuczka, która może się przydać. Rozważ losową próbkę, która wybiera każdy punkt z prawdopodobieństwem 1 / k. Łatwo jest zweryfikować, że z dużym prawdopodobieństwem dokładnie jeden z najbliższych sąsiadów będzie w próbie. Oblicz najbliższego sąsiada w próbce. Powtórz to O (k log n) razy. Z dużym prawdopodobieństwem k najbliższych punktów w $O(k \log n)$ obliczone punkty są najbliższymi sąsiadami twojego zapytania. Zatem znalezienie najbliższego sąsiada jest równoznaczne z robieniem $O( k \log n)$ zapytania najbliższego sąsiada.

Krótko mówiąc, daj mi szybką strukturę danych do odpowiadania na zapytania najbliższego sąsiada, a chętnie dam ci szybką strukturę danych k-najbliższego sąsiada.

Sariel Har-Peled
źródło

Niezła sztuczka. Ponowne użycie próbek dla różnych punktów zapytania powinno być w porządku, prawda? Aby obliczyć

k

$k$ -Najbliższy sąsiad dla każdego punktu w zestawie, muszę tylko zbudować strukturę danych

O (k \log n)

$O(k \log n)$ czasy.

Dougal,

Ponowne użycie próbek jest trudne, ponieważ wtedy wymagasz, aby stała próbka działała dla KAŻDEJ kwerendy (kwantyfikacja jest odwrócona), a zatem prawdopodobieństwa by się zmieniły. Ogólnym pomysłem byłoby więc zbudowanie zestawu próbek o większym rozmiarze (zależy to od # zapytań) i użycie ich, jeśli to jest problem.

Suresh Venkat

@SureshVenkat Ah, oczywiście. Usiądę i ustalę rzeczywiste prawdopodobieństwo. Dziękuję wszystkim!

Dougal,

Jeśli zrobisz

O (k \log (1 / δ))

$O( k \log (1/\delta))$ próbki, a następnie każde zapytanie zakończy się pomyślnie

\geq 1 - δ

$\geq 1-\delta$ . Zauważ, że ta sztuczka jest nieco lepsza niż na pierwszy rzut oka - masz

O (k \log n)

$O(k \log n)$ próbki, każda z nich wielkości

O (n / k)

$O( n/k)$ (z dużym prawdopodobieństwem, jeśli

k

$k$ nie jest zbyt duży). Co oznacza lepszy czas zapytania dla każdej próbki.

Sariel Har-Peled,

Tanim przybliżonym rozwiązaniem wykorzystującym „hash wrażliwy na lokalizację” byłoby przekonwertowanie każdego punktu na jego postać z przeplotem bitowym:

[xxx, rrr, zzz] -> xyzxyzxyz

następnie sortuj Radix do wstępnego przetwarzania.

Wybierz punkt, w którym chcesz zapytać, i idź $k$ wskazuje w obu kierunkach, aby uzyskać rozmiar $2k$ zestaw; następnie weź $kth$ najbliżej twojego punktu. Zobacz także ten artykuł autorstwa Connora i Kumara.

Zobacz także ten artykuł Callahan i Kosaraju.

Chad Brewbaker
źródło