Kppv

Kppv

Recherche des plus proches voisins

Le problème de la recherche des plus proches voisins (ou des k plus proches voisins) est très courant en algorithmique et de nombreux auteurs ont proposé des algorithmes efficaces pour le résoudre rapidement.

Soient :

La recherche des plus proches voisins consiste, étant donné un point x de E n'appartenant pas nécessairement à 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).

Sommaire

Méthodes exactes

Recherche linéaire

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 \scriptstyle k \ll N). Cette méthode est appelée la recherche linéaire ou la recherche séquentielle.

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 soufre d'un problème de lenteur. Si l'ensemble A est grand, il est alors extrêmement couteux de tester les N points de l'espace.

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é-traitement) pouvant avoir une complexité supérieure à O(N) 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é-calculs et le nombre de recherches qui auront lieu par la suite.

Partitionnement de l'espace

Il existe des algorithmes efficaces de recherche lorsque la dimension D est petite (inférieure à ~15). La structure la plus connue est le kd-tree, introduite en 1975[1].

Un problème majeur de ces méthodes est de souffrir de la malédiction de la dimension. Lorsque la dimension D est trop grande, ces méthodes ont des performances comparables ou inférieures à une recherche linéaire[2].

Méthodes approximatives

Locality sensitive hashing

Article détaillé : Locality sensitive hashing.

Voir aussi

Notes et références

  1. Bentley, « Multidimensional binary search trees used for associative searching », dans Comm. ACM 18, 509-517, 1975 [texte intégral] 
  2. Piotr Indyk et Rajeev Motwani, « Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. », dans Proceedings of 30th Symposium on Theory of Computing, 1998 [texte intégral] 
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Recherche des plus proches voisins ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Kppv de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • KPPV — Infobox Radio station name = KPPV city = Prescott Valley, Arizona area = Prescott, Arizona branding = The Mix 106.7 FM slogan = Your At Work Station airdate = September 1, 1985 frequency = 106.7 MHz format = Adult Contemporary erp = 3,700 watts… …   Wikipedia

  • KPPV — FM 106.7, Prescott Valley, Arizona (Community » Radio Stations) …   Abbreviations dictionary

  • KDDL — Infobox Radio station name = KDDL city = Chino Valley, Arizona area = Prescott, Arizona branding = Cattle Country 94.3 slogan = airdate = frequency = 94.3 MHz format = Country erp = 4,100 watts haat = 247 meters (810 feet) class = C3 facility id …   Wikipedia

  • KQNA — Infobox Radio station name = KQNA city = Prescott Valley, Arizona area = Prescott, Arizona branding = slogan = airdate = frequency = 1130 kHz format = News power = 1,000 watts (day only) class = D facility id = 53415 coordinates =… …   Wikipedia

  • KPKR — Infobox Radio station name = KPKR city = Parker, Arizona area = Prescott, Arizona branding = River Rat Radio slogan = airdate = February 1, 2008 frequency = 97.3 MHz format = Classic rock erp = 9,500 watts haat = 32 meters (105 feet) class = C3… …   Wikipedia

  • NAB Crystal Radio Awards — logo The NAB Crystal Radio Awards are presented annually by the National Association of Broadcasters to American radio stations. The award was established in 1987 to recognize radio stations for year round commitment to community service.[1]… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”