Pretraživanje najbližeg suseda

Pretraživanje najbližeg suseda (engl. Nearest neighbor search, NNS), koji je takođe poznat kao i okolna pretraga, pretraga sličnosti ili pretraga najbliže tačke, je optimizacija problema za pronalaženje najbliže tačke u metričkim prostorima. Problem je, ako je dat komplet „S“ tačaka u metričkom prostoru „M“ i tačka pretrage q ∈ M, pronaći najbližu tačku u S do q. U mnogim slučajevima, M se smatra d-dimenzionalnim Euklidovim prostorom i rastojanje se meri Euklidovom razdaljinom, Menhetn razdaljinom ili drugim merama razdaljine.

Donald Knut u 3. tomu dela „Umetnost kompjuterskog programiranja“ iz 1973. nazvao je to poštanskim problemom, misleći na princip da se uz mesto prebivališta dodeli najblža pošta.

Primene

Problem pretrage najbližeg suseda se pojavljuje u brojnim oblastima primene, uključujući:

• Prepoznavanje šablona – posebno za prepoznavanje optičkog slova
• Statistička klasifikacija – pogledaj k-nearest neighbor algoritm
• Kompjuterski vid
• Računarska geometrija – pogledaj problem najbližeg para tačaka
• Baze podataka – npr. Izvlačenje slika na osnovu sadržine
• Teorija kodiranja – pogledaj dekodiranje maksimalne verovatnoće
• Kompresija podataka – pogledaj mpeg-2 standard
• Sistemi preporuka – vidi colaborative filtering
• Internet marketing – pogledaj kontekstualno oglasavanje i ciljanje na osnovu ponašanja
• DNK sekvenciranje
• Proveravanje pravopisa – predlaganje ispravnog pravopisa
• Otkrivanje plagijata
• Algoritmi pretrage kontakta u „FEA“
• Rezultati sličnosti između profesionalnih igrača radi predviđanja daljeg razvoja karijere
• Analiza grupa – dodeljivanje skupa posmatranja u podskupove (zvani grupe) tako da posmatranja u istoj grupi budu slična na neki način, uobičajeno zasnovano na Euklidovom rastojanju
• Hemijska sličnost

Metode

Razna rešenja su predložena za NNS problem. Koeficijent efikasnosti algoritma zavise od prostora bilo koje data structure koja mora biti održavana. Neformalno posmatranje se uobičajeno naziva kao kletva dimenzionalnosti, kaže da ne postoji generalno resenje za NNS problem koristeći polinomijalno predprocesiranje i polialgoritamsko vreme pretrage.

Linearna pretraga

Najjednostavnije rešenje NNS problema jeste da se izračuna rastojanje od mesta polaska paketa do svake druge tačke iz baze podataka, vodeći računa o „najboljem do sada“. Ovaj algoritam, ponekad moze biti nazvan naivnom prilazu, ima vreme izvršavanja O(Nd), gde je N kardinalnost od S i d je dimenzionalnost od M. Naivna pretraga, uobičajeno, je bolja od deljenja prostora na višim dimenzionalnim prostorima.

Razdvajanje prostora

Još od 1970tih, metodologija separacije i evaluacije je primenjivana na problem. U slučaju Euklidovog rastojanja ovaj prustup je poznat kao prostorni indeks ili metod prostornog pristupa. Nekoliko metoda razdvajanja prostora je razvijeno radi rešavanja NNS problema. Verovatno je najjednostavnije K-D stablo, koje iterativno polovi pretragu prostora na 2 regije zadrđavajući polovinu tačaka regije roditelja. U zavisnosti od razdaljine određene upitom, prosečna složenost je O(logN) u slučaju nasumično dodeljenih poena, najgori slučaj složenosti analize koji je bio izvršen. Alternativno R-stablo strukture podataka je dizajnirano da pomogne pretrazi najbližeg suseda u dinamičnom kontekstu, pošto ima efektivne algoritme za umetanje i brisanja.

U slučaju generalnog metričkog prostora “branch and bound” pristup je poznat kao metričko stablo. Posebni primer uključuje vp-stablo i BK-stablo.

Koristeći set tačaka uzet iz trodimenzionalnog prostora i njegovim stavljanjem ga u BSP stablo, i koristeći datu upitnu tačku iz istog prostora, moguće rešenje problema se nalazi na sledeći način. (Strogo govoreći, ne postoji takva tačka, zbog toga šo ne može biti jedinstvena. Međutim u praksi, obično nam je jedino cilj da nađemo podskup svih postojećih tačka oblaka na najkraćem rastojanju od date upitne tačke). Ideja je, da se za svaku granu stabla pretpostavi da je najbliža tačka u oblaku koja je u poluprostoru, sadrži tačku polaska. Ovo ne mora da bude slučaj, ali je dobra heuaristika. Pošto se rekurzvno prođe kroz problem nalaženja poluprostora, poredi se rastojanje vraćeno kao rezultat sa najkraćim rastojanjem od tačke polaska do podele paketa. Ovo kasnije rastojanje je između tačke polaska i najbliže tačke koja može da postoji u nepretraženom poluprostoru. Ako je ovo rastojanje veće od ranijeg rezultata, onda je jasno da nema potrebe istraživati ostatak poluprostora. Ako postoji takva potreba, tada se mora rešiti problem za drugu polovinu prostora, i onda da uporedi rezultat sa prethodnim, i vrati odgovarajuća vrednost. Performanca ovog algoritma je bliža logaritamskom vremenu nego linearnom kada je polazna tačka blizu oblaka, zbog toga što je rastojanje između polazne tačke i najbliže tačka oblaka blizu nule, algoritam jedino treba da pretraži koristeci polaznu tačku kao ključ za tačan rezultat.

Lokalno osetljivo usitnjavanje

Locality sensitive hashing (LSH) tehnika je za grupisanje tačaka u prostoru u “kante” na bazi izvesne mere razdaljine. Tačke koje su bliže jedna drugoj u odredjenoj matrici su označene i imaju najviše šanse da budu u istoj “kanti”.

NNS u prostorima sa malim unutrašnjim dimenzijama

Pokrivno stablo ima teoretsku vezu zasnovanu na setu podataka konstante udvostručavanja. Granica pretrage je O(c¹² log n), gde je c konstanta ekspanzije seta podataka.

Vector približnih fajlova

U visoko dimenzionalnim prostorima stablo indeksiranja struktura postaje beskorisno zbog toga što rastući procenat čvorova mora biti pregledan. Za ubrzavanje linearne pretrage, kompresovana verzija budućih vektora čuvanih u RAM-u se koristi kao prefilter za setove podataka pri prvom izvršavanju. Finalni kandidati su određeni u drugom stupnju koristeći nekompresovane podatke sa diska za izračunavanje udaljenosti.

Pretraga zasnovana na kompresiji/grupisanju

VA fajl pristup je specijalan slučaj kompresije zasnovan na pretrazi, gde svaka je komponenta kompresovana jedinstveno. Optimalna tehnika kompresije u multidimenzionalnim postorima je vector kvantizacije (VQ), implemetrirana putem grupisanja. Baza podataka se grupiše i najpodesnija grupa se uzima.

Varijante

Postoje brojne varijante za NNS problem, a 2 najpoznatije su pretraga k-najbližih suseda i pretraga ε-približno najbližih suseda.

Literatura

• Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal. 19 (11) http://www.ddj.com/architect/184401449.  (November 2001), 40 - 49, 2001, ISSN:1075-2838, www.ddj.com/architect/184401449
• Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. „An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions”. Journal of the ACM. 45 (6). . стр. 891-923
• Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of the 7th ICDT, Jerusalem, Israel.
• Chung-Min Chen and Yibei Ling - A Sampling-Based Estimator for Top-k Query. ICDE: 617—627. 2002. 
• Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. . ISBN 978-0-12-369446-1. 
• Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. . Springer. 2006. ISBN 978-0-387-29146-8. 
• Shasha, Dennis (2004). High Performance Discovery in Time Series. Berlin: Springer. ISBN 978-0-387-00857-8. 

Spoljašnje veze

• Nearest Neighbors and Similarity Search Архивирано на сајту Wayback Machine (3. новембар 2013) - a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits.
• Similarity Search Wiki a collection of links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbours.
• Metric Spaces Library - An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez.