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

Pseudo-code

On définit un algorithme d'apprentissage en précisant sa procédure d'entraînement et de prédiction pour une nouvelle entrée de test. Étant donné que la procédure d'entraînement de l'algorithme k-PPV consiste simplement à mettre en mémoire l'ensemble d'entraînement $D_n$, voici donc la procédure de prédiction:


\begin{pseudocode}{k-PPV-CalculPrediction}{x}
\par
\FOR i \GETS 1 \TO m \DO
c[i...
...GETS c[y_i] + 1\\
\END\\
\END\\
\RETURN{\arg\max_i c[i]}\\
\end{pseudocode}

Lorsque $dists$ est une liste non triée, la procédure de prédiction s'exécute en temps $O(nk)$. Il est cependant possible d'obtenir un temps d'exécution dans $O(n\log(k))$, en utilisant une queue de priorité (monceau).



Hugo Larochelle 2007-02-15