Wyszukiwanie najbliższego sąsiada

Wyszukiwanie najbliższego sąsiada ( NNS ), jako forma wyszukiwania bliskości , jest problemem optymalizacyjnym polegającym na znalezieniu punktu w danym zbiorze, który jest najbliższy (lub najbardziej podobny) do danego punktu. Bliskość jest zwykle wyrażana za pomocą funkcji odmienności: im mniej podobne obiekty, tym większe wartości funkcji.

Formalnie problem wyszukiwania najbliższego sąsiada (NN) jest zdefiniowany w następujący sposób: mając zbiór S punktów w przestrzeni M i punkt zapytania q ∈ M , znajdź najbliższy punkt w S do q . Donald Knuth w obj. 3 Sztuki programowania komputerowego (1973) nazwał to problemem pocztowym , odnosząc się do wniosku o przypisanie do miejsca zamieszkania najbliższego urzędu pocztowego. Bezpośrednim uogólnieniem tego problemu jest k -NN, w którym musimy znaleźć k najbliższe punkty.

Najczęściej M jest przestrzenią metryczną , a odmienność jest wyrażana jako metryka odległości , która jest symetryczna i spełnia nierówność trójkąta . Jeszcze częściej przyjmuje się, że M jest d -wymiarową przestrzenią wektorową , w której odmienność jest mierzona za pomocą odległości euklidesowej , odległości Manhattanu lub innej metryki odległości . Jednak funkcja odmienności może być dowolna. Jednym z przykładów jest asymetryczna dywergencja Bregmana , dla których nierówność trójkąta nie zachodzi.

Aplikacje

Problem wyszukiwania najbliższego sąsiada pojawia się w wielu obszarach zastosowań, w tym:

Rozpoznawanie wzorców – w szczególności do optycznego rozpoznawania znaków
Klasyfikacja statystyczna - patrz algorytm k-najbliższego sąsiada
Wizja komputerowa – do rejestracji chmury punktów
Geometria obliczeniowa - patrz Problem z najbliższą parą punktów
Bazy danych – np. wyszukiwanie obrazów w oparciu o treść
Teoria kodowania - zobacz dekodowanie z maksymalnym prawdopodobieństwem
Wyszukiwanie semantyczne
Kompresja danych – patrz standard MPEG-2
Wykrywanie robotów
Systemy rekomendacji , np. patrz Filtrowanie oparte na współpracy
Marketing internetowy – patrz reklama kontekstowa i targetowanie behawioralne
sekwencjonowanie DNA
Sprawdzanie pisowni – sugerowanie poprawnej pisowni
Wykrywanie plagiatu
Wyniki podobieństwa do przewidywania ścieżek kariery zawodowych sportowców.
Analiza skupień – przypisanie zbioru obserwacji do podzbiorów (zwanych skupieniami) tak, aby obserwacje w tym samym skupieniu były w pewnym sensie podobne, zwykle w oparciu o odległość euklidesową
Podobieństwo chemiczne
Planowanie ruchu oparte na próbkowaniu

Metody

Zaproponowano różne rozwiązania problemu NNS. O jakości i przydatności algorytmów decyduje złożoność czasowa zapytań oraz złożoność przestrzenna wszelkich struktur danych wyszukiwania, które muszą być utrzymywane. Nieformalna obserwacja, zwykle określana jako przekleństwo wymiarowości, stwierdza, że nie ma dokładnego rozwiązania ogólnego przeznaczenia dla NNS w wielowymiarowej przestrzeni euklidesowej przy użyciu wstępnego przetwarzania wielomianowego i czasu wyszukiwania polilogarytmicznego.

Dokładne metody

Wyszukiwanie liniowe

Najprostszym rozwiązaniem problemu NNS jest obliczenie odległości od punktu zapytania do każdego innego punktu w bazie danych, śledząc „najlepsze do tej pory”. Algorytm ten, czasami nazywany podejściem naiwnym, ma czas działania O ( dN ), gdzie N to liczność S , a d to wymiarowość S . Nie ma żadnych struktur danych wyszukiwania do utrzymania, więc wyszukiwanie liniowe nie ma złożoności przestrzennej poza przechowywaniem bazy danych. Wyszukiwanie naiwne może średnio przewyższać podejście do partycjonowania przestrzeni w przestrzeniach o wyższych wymiarach.

Do porównania odległości nie jest wymagana odległość bezwzględna, a jedynie odległość względna. W geometrycznych układach współrzędnych obliczanie odległości można znacznie przyspieszyć, pomijając obliczanie pierwiastka kwadratowego przy obliczaniu odległości między dwiema współrzędnymi. Porównanie odległości nadal będzie dawać identyczne wyniki.

Podział przestrzeni

Od lat 70. do problemu stosuje się metodologię gałęzi i ograniczeń . W przypadku przestrzeni euklidesowej podejście to obejmuje indeks przestrzenny lub metody dostępu przestrzennego. W celu rozwiązania problemu NNS opracowano kilka metod partycjonowania przestrzeni . Być może najprostszym jest drzewo kd , które iteracyjnie dzieli przestrzeń poszukiwań na dwa regiony zawierające połowę punktów regionu macierzystego. Zapytania są wykonywane poprzez przechodzenie przez drzewo od korzenia do liścia poprzez ocenę punktu zapytania przy każdym podziale. W zależności od odległości określonej w zapytaniu może być konieczne oszacowanie sąsiednich gałęzi, które mogą zawierać trafienia. W przypadku zapytania o stały wymiar średnia złożoność wynosi O (log N ) w przypadku losowo rozmieszczonych punktów złożoność najgorszego przypadku to O ( kN ^(1-1/ k )) Alternatywnie struktura danych R-drzewa została zaprojektowana do obsługi wyszukiwania najbliższego sąsiada w kontekście dynamicznym, ponieważ ma wydajne algorytmy wstawiania i usuwania, takie jak drzewo R* . R-drzewa mogą dawać najbliższych sąsiadów nie tylko dla odległości euklidesowej, ale mogą być również używane z innymi odległościami.

W przypadku ogólnej przestrzeni metrycznej podejście rozgałęzień i ograniczeń jest znane jako podejście drzewa metrycznego . Szczególne przykłady obejmują vp-tree i BK-tree .

Wykorzystując zestaw punktów pobranych z przestrzeni trójwymiarowej i umieszczonych w drzewie BSP oraz biorąc pod uwagę punkt zapytania pobrany z tej samej przestrzeni, podane jest możliwe rozwiązanie problemu znalezienia najbliższego punktu chmury punktów do punktu zapytania w poniższym opisie algorytmu

. (Ściśle mówiąc, taki punkt może nie istnieć, ponieważ może nie być unikalny. Ale w praktyce zwykle zależy nam tylko na znalezieniu dowolnego podzbioru wszystkich punktów chmury punktów, które istnieją w najkrótszej odległości od danego punktu zapytania. ) Chodzi o to, aby dla każdego rozgałęzienia drzewa zgadnąć, że najbliższy punkt w chmurze znajduje się w półprzestrzeni zawierającej punkt zapytania. Może tak nie być, ale jest to dobra heurystyka. Po rekurencyjnym przejściu przez wszystkie problemy związane z rozwiązaniem problemu dla odgadniętej półprzestrzeni, porównaj teraz odległość zwróconą przez ten wynik z najkrótszą odległością od punktu zapytania do płaszczyzny podziału. Ta ostatnia odległość to odległość między punktem zapytania a najbliższym możliwym punktem, który mógłby istnieć w nieprzeszukiwanej półprzestrzeni. Jeśli ta odległość jest większa niż ta zwrócona we wcześniejszym wyniku, to najwyraźniej nie ma potrzeby przeszukiwania drugiej półprzestrzeni. Jeśli jest taka potrzeba, to trzeba zadać sobie trud rozwiązania problemu dla drugiej połowy przestrzeni, a następnie porównać jego wynik z poprzednim wynikiem, a następnie zwrócić właściwy wynik. Wydajność tego algorytmu jest bliższa czasowi logarytmicznemu niż liniowemu, gdy punkt zapytania znajduje się w pobliżu chmury, ponieważ ponieważ odległość między punktem zapytania a najbliższym punktem chmury punktów jest bliska zeru, algorytm musi tylko wykonać wyszukiwanie za pomocą punkt zapytania jako klucz do uzyskania poprawnego wyniku.

Metody aproksymacyjne

$zapytania$ najwyżej razy większa niż odległość od do najbliższych punktów. Atrakcyjność tego podejścia polega na tym, że w wielu przypadkach przybliżony najbliższy sąsiad jest prawie tak dobry, jak dokładny. W szczególności, jeśli miara odległości dokładnie oddaje pojęcie jakości użytkownika, wówczas niewielkie różnice w odległości nie powinny mieć znaczenia.

Chciwe wyszukiwanie w grafach sąsiedztwa

Metody grafów bliskości (takie jak HNSW) są uważane za najnowocześniejsze metody przybliżonego wyszukiwania najbliższych sąsiadów.

Metody opierają się na zachłannym przemierzaniu grafów sąsiedztwa sąsiedztwa, $}$ których każdy punkt powiązany z $x_ {i} \ in$ wierzchołek ${\ Displaystyle v_ {i} \ w V}$ . Poszukiwanie najbliższych sąsiadów zapytania q w zbiorze S przyjmuje postać poszukiwania wierzchołka grafu ${\ Displaystyle G (V, E)}$ . Podstawowy algorytm - wyszukiwanie zachłanne - $się$ od wierzchołka punktu wejścia obliczenie odległości od zapytania q do każdego wierzchołka jego sąsiedztwa ${\ Displaystyle \ {v_ {j}: (v_ {i}, v_ {j}) \ w mi \}}$ , a następnie znajduje wierzchołek o minimalnej wartości odległości. Jeśli odległość między zapytaniem a wybranym wierzchołkiem jest mniejsza niż odległość między zapytaniem a bieżącym elementem, to algorytm przechodzi do wybranego wierzchołka i staje się on nowym punktem wejścia. Algorytm zatrzymuje się, gdy osiągnie lokalne minimum: wierzchołek, którego sąsiedztwo nie zawiera wierzchołka bliższego zapytaniu niż sam wierzchołek.

Idea grafów sąsiedztwa sąsiedztwa została wykorzystana w wielu publikacjach, w tym w nowatorskim artykule Aryi i Mounta, w systemie VoroNet dla samolotu, w systemie RayNet dla . mi n {\ $mathbb {E} ^ {n}}$ oraz w algorytmach Metrized Small World i HNSW dla ogólnego przypadku przestrzeni z funkcją odległości. Prace te poprzedziła pionierska praca Toussainta, w której wprowadził pojęcie względnego sąsiedztwa .

Haszowanie zależne od lokalizacji

Mieszanie wrażliwe na lokalizację (LSH) to technika grupowania punktów w przestrzeni w „wiaderka” w oparciu o pewną metrykę odległości działającą na punktach. Punkty, które są blisko siebie w ramach wybranej metryki, są z dużym prawdopodobieństwem mapowane do tego samego zasobnika.

Wyszukiwanie najbliższego sąsiada w przestrzeniach o małym wymiarze wewnętrznym

Drzewo okładki ma teoretyczną granicę opartą na stałej podwojenia zbioru danych. Ograniczeniem czasu wyszukiwania jest O ( c ¹² log n ), gdzie c jest stałą rozszerzania zbioru danych.

Prognozowane wyszukiwanie promieniowe

W szczególnym przypadku, gdy dane są gęstą mapą 3D punktów geometrycznych, geometria projekcji techniki wykrywania może być wykorzystana do radykalnego uproszczenia problemu wyszukiwania. To podejście wymaga, aby dane 3D były uporządkowane przez rzutowanie na dwuwymiarową siatkę i zakłada, że dane są przestrzennie gładkie w sąsiednich komórkach siatki, z wyjątkiem granic obiektów. Założenia te są ważne w przypadku danych z czujników 3D w zastosowaniach takich jak geodezja, robotyka i widzenie stereoskopowe, ale ogólnie mogą nie mieć zastosowania w przypadku danych nieuporządkowanych. W praktyce ta technika ma średni czas wyszukiwania O ( 1 ) lub O ( K ) dla problemu k- najbliższego sąsiada w zastosowaniu do rzeczywistych danych stereowizyjnych.

Pliki aproksymacji wektorowej

W przestrzeniach wielowymiarowych struktury indeksowania drzewa stają się bezużyteczne, ponieważ i tak trzeba zbadać coraz większy odsetek węzłów. Aby przyspieszyć wyszukiwanie liniowe, do wstępnego filtrowania zbiorów danych przy pierwszym uruchomieniu używana jest skompresowana wersja wektorów cech przechowywanych w pamięci RAM. Ostateczni kandydaci są ustalani w drugim etapie przy użyciu nieskompresowanych danych z dysku do obliczenia odległości.

Wyszukiwanie oparte na kompresji/klastrowaniu

Podejście oparte na plikach VA to szczególny przypadek wyszukiwania opartego na kompresji, w którym każdy komponent funkcji jest kompresowany równomiernie i niezależnie. Optymalną techniką kompresji w przestrzeniach wielowymiarowych jest kwantyzacja wektorowa (VQ), realizowana poprzez grupowanie. Baza danych jest grupowana i pobierane są najbardziej „obiecujące” klastry. Zaobserwowano ogromne korzyści w porównaniu z plikiem VA, indeksami opartymi na drzewie i skanowaniem sekwencyjnym. Zwróć także uwagę na podobieństwa między grupowaniem a LSH.

Warianty

Istnieje wiele wariantów problemu NNS, a dwa najbardziej znane to k -najbliższe sąsiedztwo i ε-przybliżone przeszukiwanie najbliższego sąsiedztwa .

k - najbliżsi sąsiedzi

k -najbliższe wyszukiwanie sąsiadów identyfikuje k najbliższych najbliższych sąsiadów zapytania. Ta technika jest powszechnie stosowana w analityce predykcyjnej do szacowania lub klasyfikowania punktu na podstawie konsensusu jego sąsiadów. Grafy k -najbliższych sąsiadów to grafy, w których każdy punkt jest połączony z k najbliższymi sąsiadami.

Przybliżony najbliższy sąsiad

W niektórych zastosowaniach akceptowalne może być pobranie „dobrego odgadnięcia” najbliższego sąsiada. W takich przypadkach możemy użyć algorytmu, który nie zawsze gwarantuje zwrócenie rzeczywistego najbliższego sąsiada w zamian za poprawę szybkości lub oszczędność pamięci. Często taki algorytm znajdzie najbliższego sąsiada w większości przypadków, ale zależy to w dużej mierze od przeszukiwanego zestawu danych.

Algorytmy obsługujące przybliżone wyszukiwanie najbliższego sąsiedztwa obejmują mieszanie zależne od lokalizacji , najpierw najlepszy pojemnik i zrównoważone wyszukiwanie oparte na drzewie dekompozycji pudełkowej.

Stosunek odległości najbliższego sąsiada

Stosunek odległości najbliższego sąsiada nie stosuje progu do bezpośredniej odległości od pierwotnego punktu do sąsiedniego rywala, ale do stosunku zależnego od odległości do poprzedniego sąsiada. Jest używany w CBIR do pobierania obrazów za pomocą „zapytania według przykładu” z wykorzystaniem podobieństwa między lokalnymi obiektami. Mówiąc bardziej ogólnie, wiąże się to z kilkoma problemami z dopasowaniem .

Stały promień w pobliżu sąsiadów

Stały promień w pobliżu sąsiadów to problem, w którym chce się skutecznie znaleźć wszystkie punkty podane w przestrzeni euklidesowej w danej ustalonej odległości od określonego punktu. Zakłada się, że odległość jest stała, ale punkt zapytania jest dowolny.

Wszyscy najbliżsi sąsiedzi

Dla niektórych zastosowań (np. szacowanie entropii ) możemy mieć N punktów danych i chcieć wiedzieć, który jest najbliższym sąsiadem dla każdego z tych N punktów . Można to oczywiście osiągnąć, uruchamiając wyszukiwanie najbliższego sąsiada raz dla każdego punktu, ale ulepszoną strategią byłby algorytm, który wykorzystuje redundancję informacji między tymi N zapytaniami w celu uzyskania bardziej wydajnego wyszukiwania. Jako prosty przykład: kiedy znajdujemy odległość od punktu X do punktu Y , to również mówi nam o odległości od punktu Y do punktu X , więc to samo obliczenie może zostać ponownie użyte w dwóch różnych zapytaniach.

Biorąc pod uwagę ustalony wymiar, półokreśloną normę dodatnią (a więc obejmującą każdą normę L ^p ) i n punktów w tej przestrzeni, najbliższego sąsiada każdego punktu można znaleźć w czasie O ( n log n ), a m najbliższych sąsiadów każdy punkt można znaleźć w czasie O ( mn log n ).

Zobacz też

Cytaty

Źródła

Andrews, L. (listopad 2001). „Szablon problemu najbliższego sąsiada” . Dziennik użytkowników C/C++ . 19 (11): 40–49. ISSN 1075-2838 .
Arya S.; Góra, DM ; Netanjahu, NS ; Silverman, R .; Wu, AY (1998). „Optymalny algorytm wyszukiwania przybliżonego najbliższego sąsiada w ustalonych wymiarach” . Dziennik ACM . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . doi : 10.1145/293347.293348 . S2CID 8193729 .
Beyer, K.; Goldstein, J.; Ramakrishnan, R.; Wał, U. (1999). „Kiedy najbliższy sąsiad ma znaczenie?”. Obrady 7. ICDT .
Chen, Chung-Min; Ling, Yibei (2002). „Estymator oparty na próbkowaniu dla zapytania Top-k”. ICDE : 617–627.
Samet, H. (2006). Podstawy wielowymiarowych i metrycznych struktur danych . Morgana Kaufmanna. ISBN 978-0-12-369446-1 .
Zezula, P.; Amato, G.; Dohnal, V.; Batko, M. (2006). Wyszukiwanie podobieństw - podejście do przestrzeni metrycznej . Skoczek. ISBN 978-0-387-29146-8 .

Dalsza lektura

Shasha, Dennis (2004). Wykrywanie o wysokiej wydajności w szeregach czasowych . Berlin: Springer. ISBN 978-0-387-00857-8 .

Linki zewnętrzne

Najbliżsi sąsiedzi i wyszukiwanie podobieństw – strona poświęcona materiałom edukacyjnym, oprogramowaniu, literaturze, naukowcom, otwartym problemom i wydarzeniom związanym z wyszukiwaniem NN. Utrzymywany przez Yury Lifshits
Wyszukiwanie podobieństw Wiki – zbiór linków, osób, pomysłów, słów kluczowych, dokumentów, slajdów, kodu i zestawów danych dotyczących najbliższych sąsiadów