Complétez la classe Evaluate. Cette classe prend en entrée un ensemble d'entraînement et un ensemble de test, ainsi que des valeurs de début et de fin pour les paramètres k (nombre de plus proches voisins) et n (paramètre de la distance de Minkowski). Elle affiche sur la sortie standard les paires (n, k) testées et l'erreur de classification correspondante sur l'ensemble de test.
Le but est de pouvoir calculer les erreurs en validation et en test lorsque l'on varie n et k, afin de mieux comprendre les problèmes posés par la sélection de modèles. On vous fournit dans le fichier de la démo 2 des ensembles mnist_train.amat (1000 exemples), mnist_valid.amat (100 exemples) et mnist_test.amat (1000 exemples), qui sont tirés d'une base de données d'images de chiffres (il y a 10 classes, de 0 à 9).
Par exemple, si vous voulez tester les valeurs de n dans {1,2} et les valeurs de k dans {1,3} sur l'ensemble de validation, vous devriez obtenir:
java Evaluate mnist_train.amat mnist_valid.amat 1 2 1 3
1 1 0.13
1 2 0.18
1 3 0.13
2 1 0.11
2 2 0.14
2 3 0.11
où par exemple la première ligne indique qu'avec n = 1 et k = 1, l'algorithme des K plus proches voisins a une erreur de classification de 18%.
Lorsque cela fonctionne, lancez la (longue) commande
rm -f curve_valid ; rm -f curve_test ; java Evaluate mnist_train.amat mnist_valid.amat 3 3 1 5 > curve_valid ; java Evaluate mnist_train.amat mnist_test.amat 3 3 1 5 > curve_test ; ./plot_curve.py curve_valid curve_test
puis, en attendant que les calculs terminent, passez à la section suivante (revenez ici lorsque des graphiques apparaissent à l'écran).
La commande ci-dessus calcule les courbes d'erreur en validation et en test lorsque n = 3 et k varie dans {1,2,3,4,5}, puis les affiche à l'écran. Quelle est la valeur de k optimale selon l'ensemble de validation ? Est-ce également la valeur de k donnant la meilleure erreur sur l'ensemble de test ? Laquelle des deux courbes (validation ou test) est la plus fiable (i.e. est la plus proche de la vraie erreur de généralisation) ?
Si vous avez le temps, relancez la commande ci-dessus mais en faisant varier n au lieu de k (ou en faisant varier les deux, mais cela peut être très long si vous essayez trop de combinaisons). Observez les différences entre les courbes de validation et de test.
Editez le fichier KNNMulticlassLearner.java.
Rajoutez la méthode suivante :
public int[] decideClassAndFindNeighbors(double[] input)
qui renvoie un tableau d'entiers dans lequel le premier élément est la classe prédite
pour input, et les k autres éléments sont les indices des k plus proches
voisins de input dans l'ensemble d'entraînement.
Editez alors le fichier Test.java. Rajoutez sur la sortie standard, après la classe prédite, l'indice du point de test dans l'ensemble de test, puis la liste des indices de ses k plus proches voisins (séparés par des espaces), suivie par un 1 si le point est bien classifié ou un 0 s'il y a une erreur. Par exemple (on utilise ici l'ensemble de validation pour que cela soit plus rapide à calculer) :
java Test mnist_train.amat mnist_valid.amat 2 3 > valid_result ; cat valid_result
9 0 578 782 940 0
8 1 777 97 41 1
8 2 532 734 188 1
4 3 797 727 369 1
2 4 515 213 917 1
...
Vous allez maintenant visualiser certaines erreurs sur l'ensemble de validation. Repérez l'indice d'un point de validation pour lequel il y a une erreur (par exemple, 0 dans l'exemple ci-dessus). En supposant que vous avez sauvegardé la sortie de Test dans valid_result (comme dans la ligne de commande précédente), vous pouvez alors visualiser le 0-ème point de validation et ses k plus proches voisins par:
./plot_neighbors.py mnist_train.amat mnist_valid.amat 0 valid_result
IMPORTANT : il y avait une erreur dans le fichier plot_neighbors.py initial, elle a été corrigée et vous pouvez télécharger la nouvelle version ici.
Cela affiche à gauche le chiffre de validation, et à sa droite ses k plus proches voisins dans l'ensemble d'entraînement (la vraie classe et la classe prédite sont aussi affichées sur la sortie standard). Visualisez plusieurs points sur lesquels l'algorithme se trompe. Les erreurs vous paraissent-elles compréhensibles ?