Intelligence Artificielle - Algorithme KNN¶
- Les objets sont représéntés par des vecteurs de $\mathbb{R}^d$,
- On considère la distance euclidienne : $dist(\vec{x}, \vec{y}) = \sqrt{\sum_{i=1}^d (x_i-y_i)^2}$
- On considère $n$ classes : $C_1, C_2, ... C_n$
- On dispose de $N$ objets déjà classés (apprentissage supervisé)
Algorithme KNN :¶
Pour attribuer une classe un nouvel objet représenté par un vecteur $\vec{v}$
on cherche les k objets annotés les plus proches de $\vec{v}$. ($k\in \mathbb{N}^*$)
on donne à $\vec{v}$ la classe majoritaire de ces k objets (tirage au sort en cas d'égalité)
Exemple avec $d=2$¶
Les objets sont ainsi représentables dans le plan. La distance est la distance usuelle.
Il y a 3 classes représentées par
On dispose de 13 objets déjà classés (données d'entraînement)
On souhaite classer un nouvel objet représenté par
Ca dépend de la valeur de k ...¶
- k=1 : on considère le plus proche voisin
- k=2 : on considère les deux plus proches voisins (égalité fréquente ...)
- k=3 : on considère les trois plus proche voisin (égalité possible ...)
- ...
NB : les 13 ppv sont les 13 objets annotés¶
A retenir¶
La classe obtenue peut dépendre de k ...
cas dégénéré : k = N : on obtiendra toujours la classe majoritaire
k > N : impossible d'appliquer l'algorithme
L'algorithme KNN fonctionne bien à condition que ...¶
- les données d'entraînement doivent bien couvrir l'espace sur lequel l'algo sera utilisé
NB : problème en grande dimension, il faudra davantage de données d'entrainement. Exponentiel en fonction de $d$ : on parle du "fléau de la dimension".
- la répartition des classes dans l'espace doit être "nette"
que dire de cet exemple ?¶
on cherche à classer un objet qui est trop loin des objets annotés¶
## que dire de cet exemple ?¶
les classes des objets annotés ne semblent pas liées à leur postion dans l'espace¶
(caractéristiques utilisées non pertinentes ?)
Comment choisir la valeur de k ?¶
en pratique :
plutôt impair (pour éviter les cas d'égalité)
k = 1 présente un intérêt limité
k pas trop grand (souvent $k < \sqrt{N}$)
Exemple d'application¶
Reconnaissance de chiffres manuscrits (MNIST database : 60000 images d'entrainement, 10000 images de test)
Objets à classer : image 28x28 pixels Noir/Blanc (${0,1})
10 Classes : 0 1 2 3 4 5 6 7 8 9
Approche naïve : chaque pixel est une caractéristique : on travaille dans $\{0,1\}^{784}$
Approches plus subtiles : trouver des caractéristiques plus pertinentes et moins nombreuses -> traitement d'image, visualisation des données
