Пређи на садржај

Претраживање најближег суседа

С Википедије, слободне енциклопедије

Pretraživanje najbližeg suseda (engl. Nearest neighbor search, ННС), који је такође познат као и околна претрага, претрага сличности или претрага најближе тачке, је оптимизација проблема за проналажење најближе тачке у метричким просторима. Проблем је, ако је дат комплет „S“ тачака у метричком простору „M“ и тачка претраге q ∈ M, пронаћи најближу тачку у S до q. У многим случајевима, M се сматра d-димензионалним Еуклидовим простором и растојање се мери Еуклидовом раздаљином, Менхетн раздаљином или другим мерама раздаљине.

Доналд Кнут у 3. тому дела „Уметност компјутерског програмирања“ из 1973. назвао је то поштанским проблемом, мислећи на принцип да се уз место пребивалишта додели најблжа пошта.

Примене[уреди | уреди извор]

Проблем претраге најближег суседа се појављује у бројним областима примене, укључујући:

Методе[уреди | уреди извор]

Разна решења су предложена за ННС проблем. Коефицијент ефикасности алгоритма зависе од простора било које дата струцтуре која мора бити одржавана. Неформално посматрање се уобичајено назива као клетва димензионалности, каже да не постоји генерално ресење за ННС проблем користећи полиномијално предпроцесирање и полиалгоритамско време претраге.

Линеарна претрага[уреди | уреди извор]

Најједноставније решење ННС проблема јесте да се израчуна растојање од места поласка пакета до сваке друге тачке из базе података, водећи рачуна о „најбољем до сада“. Овај алгоритам, понекад мозе бити назван наивном прилазу, има време извршавања O(Nd), где је N кардиналност од S и d је димензионалност од M. Наивна претрага, уобичајено, је боља од дељења простора на вишим димензионалним просторима.[1]

Раздвајање простора[уреди | уреди извор]

Још од 1970тих, методологија сепарације и евалуације је примењивана на проблем. У случају Еуклидовог растојања овај пруступ је познат као просторни индекс или метод просторног приступа. Неколико метода раздвајања простора је развијено ради решавања ННС проблема. Вероватно је најједноставније К-D стабло, које итеративно полови претрагу простора на 2 регије задрђавајући половину тачака регије родитеља. У зависности од раздаљине одређене упитом, просечна сложеност је O(logN)[2] у случају насумично додељених поена, најгори случај сложености анализе који је био извршен.[3] Алтернативно Р-стабло структуре података је дизајнирано да помогне претрази најближег суседа у динамичном контексту, пошто има ефективне алгоритме за уметање и брисања.

У случају генералног метричког простора “бранцх анд боунд” приступ је познат као метричко стабло. Посебни пример укључује вп-стабло и БК-стабло.

Користећи сет тачака узет из тродимензионалног простора и његовим стављањем га у БСП стабло, и користећи дату упитну тачку из истог простора, могуће решење проблема се налази на следећи начин. (Строго говорећи, не постоји таква тачка, због тога шо не може бити јединствена. Међутим у пракси, обично нам је једино циљ да нађемо подскуп свих постојећих тачка облака на најкраћем растојању од дате упитне тачке). Идеја је, да се за сваку грану стабла претпостави да је најближа тачка у облаку која је у полупростору, садржи тачку поласка. Ово не мора да буде случај, али је добра хеуаристика. Пошто се рекурзвно прође кроз проблем налажења полупростора, пореди се растојање враћено као резултат са најкраћим растојањем од тачке поласка до поделе пакета. Ово касније растојање је између тачке поласка и најближе тачке која може да постоји у непретраженом полупростору. Ако је ово растојање веће од ранијег резултата, онда је јасно да нема потребе истраживати остатак полупростора. Ако постоји таква потреба, тада се мора решити проблем за другу половину простора, и онда да упореди резултат са претходним, и врати одговарајућа вредност. Перформанца овог алгоритма је ближа логаритамском времену него линеарном када је полазна тачка близу облака, због тога што је растојање између полазне тачке и најближе тачка облака близу нуле, алгоритам једино треба да претражи користеци полазну тачку као кључ за тачан резултат.

Локално осетљиво уситњавање[уреди | уреди извор]

Locality sensitive hashing (ЛСХ) техника је за груписање тачака у простору у “канте” на бази извесне мере раздаљине. Тачке које су ближе једна другој у одредјеној матрици су означене и имају највише шансе да буду у истој “канти”.[4]

ННС у просторима са малим унутрашњим димензијама[уреди | уреди извор]

Покривно стабло има теоретску везу засновану на сету података константе удвостручавања. Граница претраге је O(c12 log n), где је c константа експанзије сета података.

Вецтор приближних фајлова[уреди | уреди извор]

У високо димензионалним просторима стабло индексирања структура постаје бескорисно због тога што растући проценат чворова мора бити прегледан. За убрзавање линеарне претраге, компресована верзија будућих вектора чуваних у РАМ-у се користи као префилтер за сетове података при првом извршавању. Финални кандидати су одређени у другом ступњу користећи некомпресоване податке са диска за израчунавање удаљености.[5]

Претрага заснована на компресији/груписању[уреди | уреди извор]

ВА фајл приступ је специјалан случај компресије заснован на претрази, где свака је компонента компресована јединствено. Оптимална техника компресије у мултидимензионалним посторима је вецтор квантизације (ВQ), имплеметрирана путем груписања. База података се групише и најподеснија група се узима.[6][7]

Варијанте[уреди | уреди извор]

Постоје бројне варијанте за ННС проблем, а 2 најпознатије су претрага к-најближих суседа и претрага ε-приближно најближих суседа.

Референце[уреди | уреди извор]

  1. ^ Wебер, Сцхек, Блотт. „А qуантитативе аналyсис анд перформанце студy фор симиларитy сеарцх метходс ин хигх дименсионал спацес” (ПДФ). 
  2. ^ Мооре, Андреw. „Ан интродуцторy туториал он КД треес” (ПДФ). Архивирано из оригинала (ПДФ) 03. 03. 2016. г. Приступљено 18. 11. 2013. 
  3. ^ Лее, D. Т.; Wонг, C. К. (1977). „Wорст-цасе аналyсис фор регион анд партиал регион сеарцхес ин мултидименсионал бинарy сеарцх треес анд баланцед qуад треес”. Ацта Информатица. 9 (1): 23—29. дои:10.1007/БФ00263763. 
  4. ^ А. Рајараман & Ј. Уллман (2010). „Мининг оф Массиве Датасетс, Цх. 3.”. 
  5. ^ Wебер, Блотт. „Ан Аппроxиматион-Басед Дата Струцтуре фор Симиларитy Сеарцх”.  Недостаје или је празан параметар |урл= (помоћ)
  6. ^ Рамасwамy, Росе, ИЦИП 2007. „Адаптиве цлустер-дистанце боундинг фор симиларитy сеарцх ин имаге датабасес”.  Недостаје или је празан параметар |урл= (помоћ)
  7. ^ Рамасwамy, Росе, ТКДЕ 2001. „Адаптиве цлустер-дистанце боундинг фор хигх-дименсионал индеxинг”.  Недостаје или је празан параметар |урл= (помоћ)

Литература[уреди | уреди извор]

  • Andrews, L.. A template for the nearest neighbor problem. C/C++ Users Journal. 19 (11) http://www.ddj.com/architect/184401449.  Недостаје или је празан параметар |title= (помоћ) (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).  Недостаје или је празан параметар |title= (помоћ). стр. 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.  Недостаје или је празан параметар |title= (помоћ)
  • Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. . ISBN 978-0-12-369446-1.  Недостаје или је празан параметар |title= (помоћ)
  • Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. . Springer. 2006. ISBN 978-0-387-29146-8.  Недостаје или је празан параметар |title= (помоћ)
  • Схасха, Деннис (2004). Хигх Перформанце Дисцоверy ин Тиме Сериес. Берлин: Спрингер. ИСБН 978-0-387-00857-8. 

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Pretraživanje_najbližeg_suseda&oldid=27679842”