Classification par plus proches voisins, compromis biais-variance ================================================================= 1. Copiez dans my_megawave2/src/ puis compilez les programmes suivants: sample_gm2.c (version corrigée si la vôtre n'est pas correcte) fmpset.c test_error.c 1. Créez deux listes de 10 "centres" à l'aide des commandes echo "0.42 0.58 q" | flreadasc 2 c1 echo "0.58 0.42 q" | flreadasc 2 c2 sample_gm -n 10 -s 0.16 c1 centres1 sample_gm -n 10 -s 0.16 c2 centres2 Puis visualisez le résultat sur une image 400x400 par fconst visu_centres 128 400 400 fmpset -s 400 visu_centres centres1 0 visu_centres fmpset -s 400 visu_centres centres2 255 visu_centres cview -z 2 visu_centres & 2. On veut échantillonner 100 points selon les deux mélanges de Gaussiennes d'écart-type 0.05 associés à ces centres. Créer les fichiers sample1 et sample2 correspondants à l'aide de la commande sample_gm2, puis visualiser le résultat par fconst visu 128 400 400 fmpset -s 400 visu sample1 0 visu fmpset -s 400 visu sample2 255 visu cview -z 2 visu & 3. On souhaite utiliser ces 200 points comme ensemble d'apprentissage pour un algorithme de classification au plus proche voisin (k-plus proches voisins avec k=1). Écrivez un module MegaWave2 classif_ppv qui prend en entrée des 2-Flist e1 et e2 (échantillons des classes 1 et 2), un entier n (taille de l'image résultat), et qui retourne une Cimage de taille n x n, carte de classification associée aux échantillons, discrétisant le carré [0,1]^2 avec des pixels de taille 1/n x 1/n. Un fichier classif_ppv.c avec en-tête pré-rempli est disponible sur la page web du cours. Tester cet algorithme à l'aide des commandes: classif_ppv -n 400 sample1 sample2 ppv1 fmpset -s 400 ppv1 sample1 0 ppv1 fmpset -s 400 ppv1 sample2 255 ppv1 cview -z 2 ppv1 & 4. Pour évaluer les performances de cette classification, on peut estimer la probabilité d'erreur à partir d'échantillons de test générés grâces aux lois des 2 classes (définies par les fichiers centres1 et centres2 et la valeur 0.05 de l'écart-type des gaussiennes). Générez un échantillon de test de taille 2000000 (1000000 échantillons pour chaque classe) puis utilisez le module test_error pour estimer l'erreur de classification. Quelle est l'erreur de classification sur l'échantillon d'apprentissage ? En termes de compromis biais-variance, où se situe-t-on ? 5. Connaissant les lois des deux classes, quel est le classifieur qui minimise la probabilité d'erreur ? Écrivez un module classif_gk qui prend en entrée les 2 mélanges de gaussiennes (centres et écart-type), un entier n (taille de l'image résultat), et qui retourne dans une Cimage de taille n x n la carte de classification optimale associée (partir du fichier classif_gk.c). Visualisez la carte de classification optimale obtenue, puis calculez l'erreur obtenue pour cette carte de classification sur l'échantillon de test et sur l'échantillon d'apprentissage. 6. Implémenter l'algorithme de classification au k-plus proches voisins (classif_kppv.c) et visualiser les cartes de classifications associées pour différentes valeurs de k. Commenter les différences et le rapport avec la carte de classification optimale. 7. Mesurer, pour des valeurs de k impaires allant de 1 à 51, l'erreur de classification sur l'échantillon de test et sur l'échantillon d'apprentissage. Stockez ces valeurs dans deux 2-Flist et visualisez-les au moyen des commandes: set k = 1 \rm erreur_test erreur_app while ( $k <= 51 ) echo "k = $k" classif_kppv -n 400 $k sample1 sample2 kppv echo $k >> erreur_test echo $k >> erreur_app test_error test1 test2 kppv >> erreur_test test_error sample1 sample2 kppv >> erreur_app @ k += 2 end echo "q" >> erreur_test echo "q" >> erreur_app flreadasc 2 erreur_test_fl < erreur_test flreadasc 2 erreur_app_fl < erreur_app flconcat erreur_test_fl erreur_app_fl erreur fkview -g 4 -d 3 -a erreur & Commenter le résultat en termes de compromis biais-variance. Comparer les performances de la classification au k-plus proches voisins avec la classification optimale.