K plus proches voisins pour la classification multi-classes

Après vous être familiarisé avec la théorie, vous allez implémenter l'algorithme des K plus proches voisins dont vous avez écrit le pseudo-code.

Installation des fichiers

Téléchargez le fichier demo_1.tar.gz et décompressez-le par la commande tar zxvf demo_1.tar.gz
Tapez inclure jdk pour vous assurer d'utiliser la version la plus récente de Java
Tapez export PYTHONPATH=/u/dift3390/local/lib/python2.4/site-packages (sous un shell Bash), ou setenv PYTHONPATH /u/dift3390/local/lib/python2.4/site-packages (sous un shell Csh) pour avoir accès aux librairies Python utilisées dans la démo

Vous pouvez aussi ajouter les deux dernières commandes dans votre fichier de démarrage (.bashrc ou .cshrc) afin de ne pas avoir à les taper dans chaque nouveau shell.

Test des K plus proches voisins sur un ensemble de données

Les classes (ou interfaces) suivantes sont fournies et n'ont pas à être modifiées :

Dataset est une interface pour une classe qui permet d'accéder à un ensemble de données
TextDataset est une sous-classe de Dataset qui permet de lire des données où la première ligne est constituée de deux nombres représentant respectivement la taille de la partie entrée (input) et la taille de la partie cible (target), et les lignes suivantes sont les données elles-mêmes (exemple : train.amat)
Distance est une interface pour une classe qui permet de calculer la distance entre deux points
Learner est une classe abstraite pour une classe qui implémente un algorithme d'apprentissage pour la classification
DistanceIndexPair est une classe que vous n'êtes pas obligé d'utiliser, et qui permet de stocker des paires (double distance, int index) qui peuvent ensuite être comparées par des algorithmes Java utilisant l'interface Comparable

Vous devrez compléter les classes suivantes :

MinkowskiDistance est une sous-classe de Distance implémentant la distance de Minkowski vue en cours
KNNMulticlassLearner est une sous-classe de Learner implémentant l'algorithme des k plus proches voisins
Test est un petit programme qui calcule les classes prédites par un KNNMulticlassLearner sur un ensemble de test

Après avoir complété les classes ci-desssus, vous devriez être en mesure d'utiliser votre programme par la commande suivante :
java Test train.amat test.amat 2 1 > out ; ./plot_class.py train.amat test.amat out

Test des K plus proches voisins sur une grille

Afin de visualiser la surface de décision ainsi obtenue, vous allez compléter les deux classes suivantes :

Learner contient une méthode commentée (decideClassOnGrid) que vous devez implémenter (cette méthode doit calculer la sortie du Learner sur une grille 2D, et sauver à la fois la grille et la sortie dans des fichiers, pour plus d'infos voir le code et lire aussi ci-dessous)
Grid est un petit programme qui utilise cette nouvelle méthode pour calculer la sortie d'un KNNMulticlassLearner sur une grille, définie à partir de l'ensemble d'entraînement (voir les méthodes Dataset.getInputMinCoord et Dataset.getInputMaxCoord)

Pour écrire dans un fichier, vous pouvez la classe FileWriter dans java.io, qui a notamment une méthode write(String s). Pensez à inclure votre code dans un bloc try { ... } catch (Exception e) { ... }, sinon il ne compilera pas. Le fichier contenant la sortie du Learner doit simplement être une suite de nombres entiers séparés par des retours à la ligne, tandis que le fichier de grille doit ressembler à quelque chose comme:
2 0
-0.884 -0.924
-0.884 -0.824
-0.884 -0.724
-0.884 -0.624
...

Après avoir complété les classes ci-desssus, vous devriez être en mesure d'utiliser votre programme par la commande suivante :
java Grid train.amat 0.01 2 1 grid.amat out ; ./plot_class.py train.amat grid.amat out

Visualisez la surface de décision. Relancez la commande ci-dessus en changeant le nombre de plus proches voisins et observez les variations.