Cerca del veí més proper

Descripció: Representació trivial d'un veïnatgede mida tres en dimensió u. El punt negre és aquell del qual busquem el veïnatge.

Cerca l'arbre kd del veí més proper.

La cerca del veí més proper (NNS), com a forma de cerca de proximitat, és el problema d'optimització de trobar el punt d'un conjunt determinat que és més proper (o més semblant) a un punt determinat. La proximitat s'expressa normalment en termes d'una funció de dissimilaritat: com menys semblants són els objectes, més grans són els valors de la funció.

Formalment, el problema de cerca del veí més proper (NN) es defineix de la següent manera: donat un conjunt S de punts en un espai M i un punt de consulta q ∈ M, troba el punt més proper de S a q. Donald Knuth al vol. 3 de The Art of Computer Programming (1973) el va anomenar el problema de l'oficina de correus, fent referència a una aplicació d'assignació a una residència de l'oficina de correus més propera. Una generalització directa d'aquest problema és una cerca k-NN, on hem de trobar els k punts més propers.

Més comunament M és un espai mètric i la dissimilaritat s'expressa com una mètrica de distància, que és simètrica i satisfà la desigualtat del triangle. Encara més comú, M es considera l'espai vectorial d -dimensional on la dissimilaritat es mesura utilitzant la distància euclidiana, la distància de Manhattan o una altra mètrica de distància. Tanmateix, la funció de dissimilaritat pot ser arbitrària. Un exemple és la divergència de Bregman asimètrica, per a la qual la desigualtat del triangle no es compleix.

Mètodes

S'han proposat diverses solucions al problema NNS. La qualitat i la utilitat dels algorismes estan determinades per la complexitat temporal de les consultes, així com per la complexitat espacial de les estructures de dades de cerca que s'hagin de mantenir. L'observació informal anomenada habitualment la maledicció de la dimensionalitat afirma que no hi ha cap solució exacta de propòsit general per a NNS a l'espai euclidià d'alta dimensió utilitzant preprocessament polinomial i temps de cerca polilogarítmica.

Aplicacions

El problema de cerca de veïns més propers sorgeix en nombrosos camps d'aplicació, com ara:

• Reconeixement de patrons, en particular per al reconeixement òptic de caràcters.
• Classificació estadística: vegeu l'algoritme de k-veïn més proper.
• Visió per ordinador: per al registre del núvol de punts.
• Geometria computacional: vegeu el problema del parell de punts més proper.
• Cripanàlisi : per a problemes de gelosia.
• Bases de dades, per exemple, recuperació d'imatges basada en contingut.
• Teoria de la codificació: vegeu la descodificació de màxima probabilitat.
• Cerca semàntica.
• Compressió de dades: vegeu l'estàndard MPEG-2.
• Detecció robòtica.
• Sistemes de recomanació, per exemple, vegeu Filtret col·laboratiu.
• Màrqueting a Internet: vegeu publicitat contextual i orientació per comportament.
• Seqüenciació de l'ADN.
• Correcció ortogràfica: suggerir l'ortografia correcta.
• Detecció de plagi.
• Puntuació de semblança per predir les trajectòries professionals d'esportistes professionals.
• Anàlisi de clúster: assignació d'un conjunt d'observacions en subconjunts (anomenats clústers) de manera que les observacions del mateix clúster siguin similars en algun sentit, normalment basades en la distància euclidiana.
• Semblança química.
• Planificació del moviment basada en mostres.