Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Problème des plus proches voisins

Description

Le problème des plus proches voisins (ou problème des k-voisins) est très courant en algorithmique et de nombreux auteurs se sont déjà attaché à construire des algorithmes efficients pour le résoudre rapidement.

Soient:

1. un espace de dimension ;
2. un ensemble A de N points dans cet espace;
3. un nombre .

Le problème des plus proches voisins consiste, étant donné un point x situé dans l'espace D, point n'appartenant pas nécessairment à A, à déterminer quels sont les k points de A les plus proches de x. On parle alors de trouver un voisinage de taille k autour du point x.

Exemple de recherche d'un voisinage de taille 3 autour d'une coordonnée donnée (D=1, k=3).

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).

Solution

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ée, et si oui, l'insérer. On obtient alors un temps de calcul linéaire en la taille de A: O(N) (tant que ).

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

Les optimisations de cet algorithme se basent souvent sur des cas particuliers du problème. Le plus souvent, l'optimisation consiste à effectuer au préalable un algorithme (prétraîtement) pouvant avoir une complexité supérieure à mais permettant d'effectuer par la suite très rapidement un grand nombre de recherches. Il s'agit alors de trouver un juste milieu entre le temps de précalcul et le nombre de recherches qui auront lieu par la suite. Il est évidemment stupide d'effectuer un précalcul si vous ne devez effectuer qu'une seule recherche.

Voir aussi

Arbre d'axe principal