Data-mining 2012

$k$-plus proches voisins

Pour cette partie, l'objectif est de coder la fonction $kppv$ qui prendra en entrée une matrice contenant les points d'apprentissage, un vecteur contenant les étiquettes de ces points, une matrice contenant les points à étiquetter (de test) et une structure de parametres. En sortie, la function renverra un vecteur d'etiquettes prédites.

L'algorithme des $kppv$ fait appel au calcul de la distance entre un point de test et tous les points d'apprentissage. Le choix de cette distance est un paramètre. Il faudra donc coder une fonction de calcul de distance par distance possible (distance_euclidienne, distance_manhattan, par exemple).
Spécifiez et implémentez la fonction $distance\_euclidienne$
La structure de paramètres aura la forme suivante :
param.nb_voisin : nombre de voisins (entier), param.distance : type de distance (chaine de caractères)

Implémentez la fonction $kppv$

Les données

Afin de tester les kppv, nous allons générer des données synthétiques en 2 dimensions (ce qui permettra de les visualiser).

Il faut avoir un ensemble de données d'apprentissage ($napp$ vecteurs de dimension $d$ et étiquettes avec $c$ classes) ainsi qu'un ensemble de test ($ntest$ vecteurs de dimension $d$ et étiquettes).
Spécifiez et implémentez une fonction de génération de données (qui prend en entrée les différentes dimensions et une structure de parametres et qui renvoie la matrice d'apprentissage, la matrice de test et les deux vecteurs d'étiquettes associées).
- un probleme $gaussien$ : chacune des $c$ classes est tirée selon une loi normale de moyenne et variance différentes
- un problème $separable$ : les données sont tirées uniformément dans l'espace, les classes sont attribuées selon des frontières arbitraires
La structure de paramètres aura la forme suivante :
probleme.nb_classes : nombre de classes à générer (entier), param.type : type de probleme (chaine de caractères)
Implémentez une fonction de visualisation des données générées.

La validation croisée

Pour choisir le meilleur nombre de voisin pour un problème donné, il faut utiliser une méthode de validation. Nous allons implémenter la validation croisée

La validation croisée est une méthode qui prend en entrée un problème (jeu de données d'apprentissage), un algorithme, un jeu de paramètres fixé et un nombre de blocs et qui renvoie l'erreur moyenne obtenue sur chaque blocs isolé pour cet algorithme en utilisant les paramètres spécifiés. L'idée est ensuite de lancer cette fonction pour chaque jeu de paramètres et de sélectionner le jeu qui aura produit la plus faible erreur de validation croisée.
Spécifiez et implémentez la fonction de validation croisée. Pensez qu'elle devra certainement resservir pour d'autres algorithmes.

TP 1 de Data-mining, GMM3, 2012

$k$-plus proches voisins

Les données

La validation croisée