next up previous
Next: Formalisation mathématique Up: Algorithme des k plus Previous: Algorithme des k plus

Motivation intuitive

L'algorithme des k plus proches voisins (k-PPV) est certainement un des algorithmes les plus simples d'apprentissage automatique. Il est motivé par l'idée que des entrées $x_t$ semblables devraient avoir des cibles $y_t$ semblables. Ainsi, pour bien définir un algorithme k-PPV, il suffit de définir ce que veut dire ``semblable'' dans le contexte des entrées et de définir l'influence de ces voisins sur la prédiction de la cible pour une entrée de test.

Donc, pour obtenir une prédiction de la cible pour une entrée de test $x$, il suffit de trouver les k plus proches voisins selon une métrique déterminant jusqu'à quel point des entrées sont semblables (par exemple, la distance euclédienne ou norme $L^2$, ou de façon plus générale la norme $L^p$ de Minkowski) et d'utiliser ces k plus proches voisins pour prédire la cible de $x$. Dans un problème de classification, la prédiction correspond à la classe majoritaire parmi les k plus proches voisins, i.e. que l'ensemble des $k$ plus proches voisins votent pour la classe correspondant à leur cible respective et la classe recueillant le plus de vote est choisie en tant que prédiction par l'algorithme.


next up previous
Next: Formalisation mathématique Up: Algorithme des k plus Previous: Algorithme des k plus
Hugo Larochelle 2007-02-15