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 semblables devraient avoir des cibles
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 ,
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
, ou de façon
plus générale la norme
de Minkowski) et
d'utiliser ces k plus proches voisins pour prédire la cible
de
. 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
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.