Recherche des plus proches voisins
La recherche des plus proches voisins, ou des k plus proches voisins, est un problème algorithmique classique. De façon informelle le problème consiste, étant donné un point à trouver, dans un ensemble d'autres points, quels sont les k plus proches. La recherche de voisinage est utilisée dans de nombreux domaines, tels la reconnaissance de formes, le clustering, l'approximation de fonctions, la prédiction de séries temporelles et même les algorithmes de compression (recherche d'un groupe de données le plus proche possible du groupe de données à compresser pour minimiser l'apport d'information). C'est en particulier l'étape principale de la méthode des k plus proches voisins en apprentissage automatique. La formulation classique du problème est la suivante. Étant donné un ensemble A de n points, dans un espace métrique E, un entier k plus petit que n, et un point supplémentaire x, trouver les k points de A les plus proches de x. Un cas classique est celui de la recherche du plus proche voisin, c'est-à-dire le cas k=1. Une hypothèse classique est que l'espace sous-jacent E est un espace vectoriel de dimension bornée. L'algorithme naïf de recherche de voisinage consiste à passer sur l'ensemble des n points de A et à regarder si ce point est plus proche ou non qu'un des plus proches voisins déjà sélectionné, et si oui, l'insérer. On obtient alors un temps de calcul linéaire en la taille de A : O(n) (tant que k < n). Cette méthode est appelée la recherche séquentielle ou recherche linéaire. Algorithme naïf : pour i allant de 1 à k mettre le point D[i] dans proches_voisins fin pour pour i allant de k+1 à n si la distance entre D[i] et x est inférieure à la distance d'un des points de proches_voisins à x supprimer de proches_voisins le point le plus éloigné de x mettre dans proches_voisins le point D[i] fin si fin pour proches_voisins contient les k plus proches voisins de x La recherche linéaire souffre d'un problème de lenteur. Si l'ensemble A est grand, il est alors extrêmement coûteux de tester les n points de l'espace.