Recherche du voisin le plus proche - Nearest neighbor search

La recherche du plus proche voisin ( NNS ), en tant que forme de recherche de proximité , est le problème d'optimisation consistant à trouver le point dans un ensemble donné qui est le plus proche (ou le plus similaire) d'un point donné. La proximité est généralement exprimée en termes de fonction de dissemblance : moins les objets sont similaires, plus les valeurs de la fonction sont grandes.

Formellement, le problème de recherche le plus proche voisin (NN) est défini comme suit: étant donné un ensemble S de points dans un espace M et un point d'interrogation q  ∈  M , trouver le point le plus proche de S à q . Donald Knuth dans le vol. 3 de The Art of Computer Programming (1973) l'a appelé le problème du bureau de poste , en référence à une demande d'affectation à une résidence du bureau de poste le plus proche. Une généralisation directe de ce problème est une recherche k -NN, où nous devons trouver les k points les plus proches.

Le plus souvent M est un espace métrique et la dissemblance est exprimée comme une métrique de distance , qui est symétrique et satisfait l' inégalité triangulaire . Encore plus commune, M est considéré comme étant le d de dimension espace vectoriel où dissemblance est mesurée en utilisant la distance euclidienne , la distance Manhattan ou une autre mesure de distance . Cependant, la fonction de dissimilarité peut être arbitraire. Un exemple est la divergence de Bregman asymétrique , pour laquelle l'inégalité triangulaire ne tient pas.

Applications

Le problème de recherche du plus proche voisin se pose dans de nombreux domaines d'application, notamment :

• Reconnaissance de formes – en particulier pour la reconnaissance optique de caractères
• Classification statistique - voir algorithme du k-plus proche voisin
• Vision par ordinateur
• Géométrie computationnelle - voir Problème de la paire de points la plus proche
• Bases de données - par exemple , récupération d'images basée sur le contenu
• Théorie du codage - voir décodage par maximum de vraisemblance
• Compression de données - voir MPEG-2 norme
• Détection robotique
• Systèmes de recommandation , par exemple voir Filtrage collaboratif
• Marketing Internet – voir publicité contextuelle et ciblage comportemental
• séquençage ADN
• Vérification orthographique - suggestion d'orthographe correcte
• Détection de plagiat
• Scores de similarité pour prédire les cheminements de carrière des athlètes professionnels.
• Analyse de cluster - affectation d'un ensemble d'observations en sous-ensembles (appelés clusters) de sorte que les observations dans le même cluster soient similaires dans un certain sens, généralement basées sur la distance euclidienne
• Similitude chimique
• Planification de mouvement basée sur l'échantillonnage

Méthodes

Diverses solutions au problème NNS ont été proposées. La qualité et l'utilité des algorithmes sont déterminées par la complexité temporelle des requêtes ainsi que la complexité spatiale de toutes les structures de données de recherche qui doivent être maintenues. L'observation informelle généralement appelée la malédiction de la dimensionnalité déclare qu'il n'y a pas de solution exacte à usage général pour le NNS dans l'espace euclidien de grande dimension en utilisant le prétraitement polynomial et le temps de recherche polylogarithmique.

Méthodes exactes

Recherche linéaire

La solution la plus simple au problème NNS est de calculer la distance entre le point de requête et chaque autre point de la base de données, en gardant une trace du « meilleur jusqu'à présent ». Cet algorithme, parfois appelé approche naïve, a un temps d'exécution de O ( dN ), où N est la cardinalité de S et d est la dimensionnalité de M . Il n'y a pas de structures de données de recherche à maintenir, donc la recherche linéaire n'a pas de complexité spatiale au-delà du stockage de la base de données. La recherche naïve peut, en moyenne, surpasser les approches de partitionnement d'espace sur des espaces de dimension supérieure.

Partitionnement de l'espace

Depuis les années 1970, la méthodologie des branches et bornes a été appliquée au problème. Dans le cas de l'espace euclidien, cette approche englobe les méthodes d'index spatial ou d'accès spatial. Plusieurs méthodes de partitionnement de l'espace ont été développées pour résoudre le problème NNS. Le plus simple est peut-être l' arbre kd , qui divise itérativement l'espace de recherche en deux régions contenant la moitié des points de la région parente. Les requêtes sont effectuées via une traversée de l'arbre de la racine à une feuille en évaluant le point de requête à chaque division. Selon la distance spécifiée dans la requête, les branches voisines susceptibles de contenir des hits peuvent également devoir être évaluées. Pour un temps de requête à dimension constante, la complexité moyenne est de O (log  N ) dans le cas de points distribués aléatoirement, la complexité dans le pire des cas est de O ( kN ^(1-1/ k )) Alternativement, la structure de données R-tree a été conçue pour prendre en charge le plus proche recherche de voisins dans un contexte dynamique, car il dispose d'algorithmes efficaces pour les insertions et les suppressions tels que l' arbre R* . Les arbres R peuvent donner les voisins les plus proches non seulement pour la distance euclidienne, mais peuvent également être utilisés avec d'autres distances.

Dans le cas de l'espace métrique général, l'approche branch-and-bound est connue sous le nom d' approche de l' arbre métrique . Des exemples particuliers incluent les méthodes vp-tree et BK-tree .

En utilisant un ensemble de points pris dans un espace tridimensionnel et placés dans un arbre BSP , et étant donné un point de requête pris dans le même espace, une solution possible au problème de trouver le point de nuage de points le plus proche du point de requête est donnée dans la description suivante d'un algorithme. (À proprement parler, aucun point de ce type ne peut exister, car il peut ne pas être unique. Mais en pratique, nous ne nous soucions généralement que de trouver l'un des sous-ensembles de tous les points de nuage de points qui existent à la distance la plus courte d'un point de requête donné. ) L'idée est, pour chaque branchement de l'arbre, de deviner que le point le plus proche dans le nuage réside dans le demi-espace contenant le point de requête. Ce n'est peut-être pas le cas, mais c'est une bonne heuristique. Après avoir fait récursivement tout le soin de résoudre le problème pour le demi-espace deviné, comparez maintenant la distance renvoyée par ce résultat avec la distance la plus courte du point de requête au plan de partitionnement. Cette dernière distance est celle entre le point d'interrogation et le point le plus proche possible pouvant exister dans le demi-espace non recherché. Si cette distance est supérieure à celle renvoyée dans le résultat précédent, alors il est clair qu'il n'est pas nécessaire de rechercher l'autre demi-espace. S'il y a un tel besoin, vous devez alors vous donner la peine de résoudre le problème pour l'autre demi-espace, puis comparer son résultat au premier résultat, puis renvoyer le résultat approprié. Les performances de cet algorithme sont plus proches du temps logarithmique que du temps linéaire lorsque le point de requête est proche du nuage, car comme la distance entre le point de requête et le point de nuage de points le plus proche est proche de zéro, l'algorithme n'a besoin d'effectuer qu'une recherche en utilisant le point de requête comme clé pour obtenir le résultat correct.

Méthodes d'approximation

Un algorithme de recherche du voisin le plus proche approximatif est autorisé à renvoyer des points, dont la distance de la requête est la plupart du temps la distance de la requête à ses points les plus proches. L'attrait de cette approche est que, dans de nombreux cas, un voisin le plus proche approximatif est presque aussi bon que l'exact. En particulier, si la mesure de distance capture avec précision la notion de qualité de l'utilisateur, alors les petites différences de distance ne devraient pas avoir d'importance. ${\style d'affichage c}$

Recherche gourmande dans les graphiques de quartier de proximité

Les méthodes de graphe de proximité (telles que HNSW) sont considérées comme l'état de l'art actuel pour la recherche approximative des voisins les plus proches.

Les méthodes sont basées sur un parcours glouton dans des graphes de voisinage de proximité dans lesquels chaque point est associé de manière unique à un sommet . La recherche des voisins les plus proches d'une requête q dans l'ensemble S prend la forme d'une recherche du sommet dans le graphe . L'algorithme de base – la recherche gloutonne – fonctionne comme suit : la recherche commence à partir d'un sommet de point d'entrée en calculant les distances de la requête q à chaque sommet de son voisinage , puis trouve un sommet avec la valeur de distance minimale. Si la valeur de distance entre la requête et le sommet sélectionné est plus petite que celle entre la requête et l'élément courant, alors l'algorithme se déplace vers le sommet sélectionné, et il devient un nouveau point d'entrée. L'algorithme s'arrête lorsqu'il atteint un minimum local : un sommet dont le voisinage ne contient pas de sommet plus proche de la requête que le sommet lui-même. ${\style d'affichage G(V,E)}$${\displaystyle x_{i}\in S}$${\displaystyle v_{i}\in V}$${\style d'affichage G(V,E)}$${\displaystyle v_{i}\in V}$${\displaystyle \{v_{j}:(v_{i},v_{j})\in E\}}$

L'idée des graphes de voisinage de proximité a été exploitée dans plusieurs publications, y compris l'article fondateur d'Arya et Mount, dans le système VoroNet pour l'avion, dans le système RayNet pour le , et dans les algorithmes Metrized Small World et HNSW pour le cas général de espaces avec une fonction de distance. Ces travaux ont été précédés par un article pionnier de Toussaint, dans lequel il a introduit le concept de graphe de voisinage relatif . ${\displaystyle \mathbb {E} ^{n}}$

Hachage sensible à la localité

Le hachage sensible à la localité (LSH) est une technique permettant de regrouper des points dans l'espace en « seaux » sur la base d'une métrique de distance opérant sur les points. Les points proches les uns des autres sous la métrique choisie sont mappés sur le même compartiment avec une probabilité élevée.

Recherche du plus proche voisin dans les espaces de petite dimension intrinsèque

L' arbre de couverture a une limite théorique basée sur la constante de doublement de l'ensemble de données . La borne sur le temps de recherche est O ( c ¹²  log  n ) où c est la constante d'expansion de l'ensemble de données.

Recherche radiale projetée

Dans le cas particulier où les données sont une carte 3D dense de points géométriques, la géométrie de projection de la technique de détection peut être utilisée pour simplifier considérablement le problème de recherche. Cette approche nécessite que les données 3D soient organisées par une projection sur une grille à deux dimensions et suppose que les données sont spatialement lisses à travers les cellules de grille voisines à l'exception des limites des objets. Ces hypothèses sont valables lorsqu'il s'agit de données de capteurs 3D dans des applications telles que l'arpentage, la robotique et la vision stéréo, mais peuvent ne pas s'appliquer aux données non organisées en général. En pratique, cette technique a un temps de recherche moyen de O ( 1 ) ou O ( K ) pour le problème du k-plus proche voisin lorsqu'elle est appliquée aux données de vision stéréo du monde réel.

Fichiers d'approximation vectorielle

Dans les espaces de grande dimension, les structures d'indexation des arbres deviennent inutiles car un pourcentage croissant des nœuds doit être examiné de toute façon. Pour accélérer la recherche linéaire, une version compressée des vecteurs de caractéristiques stockés dans la RAM est utilisée pour préfiltrer les ensembles de données lors d'une première exécution. Les candidats finaux sont déterminés dans une deuxième étape en utilisant les données non compressées du disque pour le calcul de la distance.

Recherche basée sur la compression/le clustering

L'approche du fichier VA est un cas particulier d'une recherche basée sur la compression, où chaque composant de fonctionnalité est compressé de manière uniforme et indépendante. La technique de compression optimale dans les espaces multidimensionnels est la quantification vectorielle (VQ), mise en œuvre par clustering. La base de données est clusterisée et les clusters les plus « prometteurs » sont récupérés. Des gains énormes par rapport à VA-File, des index arborescents et une analyse séquentielle ont été observés. Notez également les parallèles entre le clustering et LSH.

Variantes

Il existe de nombreuses variantes du problème NNS et les deux plus connues sont la recherche du voisin le plus proche k et la recherche du voisin le plus proche ε-approximatif .

k -les voisins les plus proches

k -la recherche du voisin le plusprocheidentifie les k premiersvoisins les plus proches de la requête. Cette technique est couramment utilisée en analyse prédictive pour estimer ou classer un point en fonction du consensus de ses voisins. Les k- graphes des plus proches voisins sont des graphes dans lesquels chaque point est connecté à ses k plus proches voisins.

Plus proche voisin approximatif

Dans certaines applications, il peut être acceptable de récupérer une "bonne estimation" du voisin le plus proche. Dans ces cas, nous pouvons utiliser un algorithme qui ne garantit pas de retourner le voisin le plus proche dans tous les cas, en échange d'une vitesse améliorée ou d'économies de mémoire. Souvent, un tel algorithme trouvera le voisin le plus proche dans la majorité des cas, mais cela dépend fortement de l'ensemble de données interrogé.

Les algorithmes qui prennent en charge la recherche approximative du voisin le plus proche incluent le hachage sensible à la localité , le meilleur bin en premier et la recherche équilibrée basée sur l' arbre de décomposition en boîtes .

Rapport de distance du voisin le plus proche

Le rapport de distance du voisin le plus proche n'applique pas le seuil sur la distance directe du point d'origine au voisin challenger mais sur un rapport de celle-ci dépendant de la distance au voisin précédent. Il est utilisé dans CBIR pour récupérer des images via une "requête par exemple" en utilisant la similitude entre les caractéristiques locales. Plus généralement, il est impliqué dans plusieurs problèmes d' appariement .

Les voisins proches à rayon fixe

Les voisins proches à rayon fixe sont le problème où l'on veut trouver efficacement tous les points donnés dans l' espace euclidien à une distance fixe donnée d'un point spécifié. La distance est supposée fixe, mais le point de requête est arbitraire.

Tous les voisins les plus proches

Pour certaines applications (par exemple l' estimation d'entropie ), nous pouvons avoir N points de données et souhaiter savoir quel est le voisin le plus proche pour chacun de ces N points . Cela pourrait, bien sûr, être réalisé en exécutant une recherche du plus proche voisin une fois pour chaque point, mais une stratégie améliorée serait un algorithme qui exploite la redondance des informations entre ces N requêtes pour produire une recherche plus efficace. Un exemple simple : lorsque nous trouvons la distance du point X au point Y , cela nous indique également la distance du point Y au point X , donc le même calcul peut être réutilisé dans deux requêtes différentes.

Étant donné une dimension fixe, une norme positive semi-définie (incluant ainsi chaque L ^p norme ), et n points dans cet espace, le plus proche voisin de chaque point peut être trouvé en O ( n  log  n ) temps et les m plus proches voisins de chaque point peut être trouvé dans le temps O ( mn  log  n ).

Voir également

Les références

Citations

Sources

• Andrews, L. (novembre 2001). "Un modèle pour le problème du voisin le plus proche" . Journal des utilisateurs C/C++ . 19 (11) : 40-49. ISSN  1075-2838 .
• Arya, S.; Monture, DM ; Netanyahu, N.-É. ; Silverman, R. ; Wu, AY (1998). « Un algorithme optimal pour la recherche approximative du voisin le plus proche dans des dimensions fixes ». Journal de l'ACM . 45 (6) : 891–923. CiteSeerX  10.1.1.15.3125 . doi : 10.1145/293347.293348 . S2CID  8193729 .
• Beyer, K. ; Goldstein, J.; Ramakrishnan, R.; Shaft, U. (1999). "Quand le voisin le plus proche a-t-il un sens ?". Actes du 7ème CIDC .
• Chen, Chung-Min ; Ling, Yibei (2002). "Un estimateur basé sur l'échantillonnage pour la requête Top-k". ICDE : 617-627.
• Samet, H. (2006). Fondements des structures de données multidimensionnelles et métriques . Morgan Kaufmann. ISBN 978-0-12-369446-1.
• Zezula, P.; Amato, G.; Dohnal, V. ; Batko, M. (2006). Recherche de similarité – L'approche de l'espace métrique . Springer. ISBN 978-0-387-29146-8.

Lectures complémentaires

• Shasha, Dennis (2004). Découverte haute performance dans les séries temporelles . Berlin : Springer. ISBN 978-0-387-00857-8.

Liens externes

• Recherche de voisins les plus proches et de similarité - un site Web dédié au matériel pédagogique, aux logiciels, à la littérature, aux chercheurs, aux problèmes ouverts et aux événements liés à la recherche NN. Maintenu par Yury Lifshits
• Wiki de recherche de similarité - une collection de liens, de personnes, d'idées, de mots-clés, d'articles, de diapositives, de codes et d'ensembles de données sur les voisins les plus proches