Trouver la classe avec les k plus proches voisins

Supposons que l’on a un problème de classification qui consiste à déterminer la classe d’appartenance de nouvelles instances $\mathrm{‘}Xi\mathrm{‘}`Xi`$. Le domaine de valeurs des classes possibles est $\mathrm{‘}1,2,3\mathrm{‘}`\{1,\; 2,\; 3\}`$.

Selon la base de connaissance suivante, déterminez à la main (ou à l'aide d'un tableur) la classe de l’instance $\mathrm{‘}X6\mathrm{‘}`X6`$, dont les valeurs pour les attributs numériques $\mathrm{‘}A1\mathrm{‘}`A1`$ à $\mathrm{‘}A5\mathrm{‘}`A5`$ sont , à l’aide de l’algorithme des k-voisins les plus proches (K-NN) avec $\mathrm{‘}K=1\mathrm{‘}`K=1`$ puis $\mathrm{‘}K=3\mathrm{‘}`K=3`$.

Montrez tous les calculs.

Couleur d'un fruit

On cherche à prédire la couleur d’un fruit en fonction de sa largeur ($\mathrm{‘}L\mathrm{‘}`L`$) et de sa hauteur ($\mathrm{‘}H\mathrm{‘}`H`$).
On dispose des données d’apprentissage suivantes :

Ces données sont placées dans un repère ($\mathrm{‘}L\mathrm{‘}`L`$ en abscisse, $\mathrm{‘}H\mathrm{‘}`H`$ en ordonnée), indiquez pour chaque point sa couleur.

L’objectif ici est d’étudier l’influence des voisins sur la propriété de couleur d’un fruit.

Soit $\mathrm{‘}U\mathrm{‘}`U`$ le nouveau fruit de largeur $\mathrm{‘}L=1\mathrm{‘}`L\; =\; 1`$, et de hauteur $\mathrm{‘}H=4\mathrm{‘}`H\; =\; 4`$.

1. Quelle est sa couleur si l'on considère 1 voisin ?
2. Quelle est sa couleur si l'on considère 3 voisins ?
3. Plutôt que le vote majoritaire, on voudrait considérer le vote des voisins pondérés par la distance. Chaque voisin vote selon un poids $\mathrm{‘}w\mathrm{‘}`w`$ inversement proportionnel au carré de sa distance : $\mathrm{‘}w=1\mathrm{/}{d}^2\mathrm{‘}`w\; =\; 1/d^2`$. \On prend 3 voisins, quelle est la couleur de $\mathrm{‘}U\mathrm{‘}`U`$ ? \Comparez vos résultats à ceux de la question 2.

Distance sur des données non numériques

Arrivé dans la cantina de la planète Tatooine, Han Solo décide de donner des indications à Luke pour qu’il ne provoque pas les extraterrestres belliqueux. Il repère quelques caractéristiques et vous demande de l’aider à fournir des éléments à Luke pour ne pas créer de problèmes et donc pouvoir définir un extraterrestre belliqueux.

Élaborez une distance pour pouvoir mettre en œuvre KNN sur cet exemple.

Distance sur des données mixtes

Après avoir mis un place un entrepôt de données pour stocker les résultats des votes à différentes élections, l’objectif est de maintenant d’exploiter les différentes données de cet entrepôt. Différents partis politiques font donc appel à vous pour les aider à mieux comprendre leurs électeurs.

Un parti cherche à comprendre la composition des votants pour son candidat. Il fait donc appel à vos services pour identifier les différents profils des votants.

On a par exemple les deux votants suivants :

• V1 : {F ; 43 ; NON ; 55.000 ; 14% ; CONTRE}
• V2 : {M ; 38 ; NON ; 28.000 ; 14% ; POUR}

les attributs correspondent à :

• sexe : {F ; M}
• âge : {min : 18 ; max : 102 ; std : 30 ; moy : 50}
• propriétaire : {OUI, NON}
• salaire annuel imposable : {min : 412 ; max : 350.000 ; std : 30.000 ; moy : 32.000}
• taux d'imposition : {0% ; 14% ; 30% ; 41% ; 45%}
• opinion sur le nucléaire : {POUR, CONTRE, NSP}

Définissez formellement une distance permettant de considérer tous les attributs pour mettre en œuvre KNN.

Donnez la distance de V1 à V2 avec cette définition.

title: Algorithme des k plus proches voisins - exercices subtitle : Bloc 2 author: | | Département informatique, Univ. Lille | DIU Enseigner l'informatique au lycée

date: juin 2019