next up previous
Next: Pseudo-code Up: Algorithme des k plus Previous: Motivation intuitive

Formalisation mathématique

Soit

La prédiction de classification par l'algorithme des k plus proches voisins est donc:


\begin{displaymath}\arg\max_{y\in {\cal Y}} \sum_{(x_i,y_i)\in {\cal V}(x,D_n,d(\cdot,\cdot),k)} I_{\left\{y_i = y\right\}}\end{displaymath}

Une fonction de distance couramment utilisée est la distance euclédienne:


\begin{displaymath}d(a,b) = \sqrt{\sum_{i=1}^d (a_i - b_i)^2}\end{displaymath}

qui est un cas spécifique, avec $p=2$, de la norme $L^p$ de Minkowski:


\begin{displaymath}d(a,b) = \left(\sum_{i=1}^d \vert a_i - b_i\vert^p\right)^{\frac{1}{p}}\end{displaymath}



Hugo Larochelle 2007-02-15