Aller au contenu

Principe et extraction de données

Dans ce TP, on va reprendre un problème de classification, comme dans le TP KNN, mais avec une dimension suffisamment faible pour que les arbres k-d permettent une accélération notable.

On va considérer un jeu de données de 898 pokémons (pas sûr de tous les avoir attrapés...), qui comporte 1032 lignes car certains pokémons y apparaissent sous plusieurs formes. Ce jeu de données est dans le fichier All_Pokemon_knn.csv.

C'est un fichier CSV donc Comma Separated Values. Sa première ligne indique les noms des colonnes séparés par des , : Number,Name,Type 1,....

Ensuite, chaque ligne suivante renseigne un pokémon donné, comme par exemple ce pokémon :

707,Klefki,Steel,Fairy,"['Magician'; 'Prankster']],57,80,91,80,87,75,470,
78.33333333333333,10.85766498326822,6.0,Fast,800000,1.0,75,0.0,0.0,0.0,
0.0,0.5,2.0,1.0,1.0,0.5,0.5,1.0,0.0,2.0,0.5,0.5,0.25,0.5,1.0,0.0,0.5,1.0,
0.5,0.2,3.0,75.0

(la ligne a été coupée ici pour l'affichage). Dans le fichier d'origine, la colonne Abilities contient des virgules entre guillemets : elles ont été remplacées par des ; dans le fichier fourni, ce qui permet de découper chaque ligne simplement selon les virgules.

On va s'intéresser dans ce TP à étudier les liens entre certaines statistiques pour identifier des motifs. Par exemple : est-ce que les statistiques HP,Att,Def,Spa,Spd,Spe permettent de deviner Height ou Weight ?

Tout d'abord, il va falloir lire ce fichier. Pour cela, on rappelle la manière dont on peut écrire des fonctions de lecture des lignes d'un fichier (on va adapter cette fonction dans la suite) :

let rec read_lines f =
    try
        let line = input_line f in
        line :: read_lines f
    with End_of_file -> []

On rappelle les fonctions suivantes d'OCaml :

(* pour obtenir un canal de lecture sur un fichier *)
val open_in : string -> in_channel
(* pour lire une ligne sans le saut de ligne final *)
val input_line : in_channel -> string
(* pour séparer une chaîne selon un caractère :
 * avec '-', "a-bb-c" donne [ "a"; "bb"; "c" ] *)
val String.split_on_char : char -> string -> string list

Question 1. Écrire une fonction

val list_to_dict : string list -> string list -> (string, string) Hashtbl.t

qui prend en entrée deux listes de chaînes de même longueur, les champs et les valeurs, et construit un dictionnaire avec.

Par exemple, si on appelle

list_to_dict ["nom"; "prenom"; "age"] ["Tajiri"; "Satoshi"; "57"]

on va obtenir une table de hachage avec les correspondances comme "age" -> "57".

Question 2. Écrire une fonction

val input_csv : in_channel -> string list

qui lit une ligne dans le fichier donné et renvoie la liste des sous-chaînes obtenues en séparant selon les virgules.

On définit

type pokemon = (string, string) Hashtbl.t

Question 3. En déduire une fonction

val csv_to_dicts : string -> pokemon array

qui prend un nom de fichier CSV, lit la ligne d'en-tête et construit tous les dictionnaires représentant les valeurs des lignes suivantes.

Question 4. Définir un array pokemons qui contient le tableau de tous les dictionnaires du fichier.

Normalisation des coordonnées

Dans le TP précédent, les données étaient semblables en magnitude sur toutes les dimensions car elles étaient de même nature. Mais ici, il ne va pas être raisonnable de calculer des distances avec des HP entre 50 et 150 quand les tailles sont souvent autour de 1 m.

On va ainsi procéder à une renormalisation des données. Pour normaliser une dimension, on calcule \(m\) la valeur minimale et \(M\) la valeur maximale, et on remplace chaque valeur \(v\) par \(\frac{v-m}{M-m} \in [0;1]\).

Question 5. Écrire une fonction

val field_spread : string -> float * float

telle que field_spread field renvoie le couple (min_value, max_value) associé à l'attribut field, qui sera nécessairement un attribut de valeur numérique.

On pourra ainsi convertir la valeur avec float_of_string.

Question 6. Écrire une fonction

val normalize : float * float -> float -> float

telle que l'appel normalize spread v réalise le calcul précédent, où spread est le couple (min_value, max_value).

On définit

type vector = float array

Question 7. Écrire une fonction

val data_vector : string list -> (float * float) list -> pokemon -> vector

qui prend une liste de champs en entrée dont les valeurs sont toutes numériques, la liste de leurs étendues \((min,max)\) associées, un dictionnaire \(d\), et renvoie un tableau de flottants où le \(i\)-ème flottant est la valeur dans \(d\) du \(i\)-ème champ, convertie en float puis normalisée.

Pour classer les données, on va commencer par choisir un champ cible et déterminer les quartiles \((q_1,q_2,q_3)\) associés : le quartile \(q_i\) est une valeur telle qu'environ une proportion \(\frac{i}{4}\) des valeurs de ce champ sont \(< q_i\). Si on trie les \(n\) valeurs \(v_0 \le v_1 \le \dots \le v_{n-1}\), on pourra prendre \(q_i = v_{\lfloor in/4 \rfloor}\). C'est une généralisation de la médiane : on coupe en quatre et on regarde les trois valeurs de séparation.

Question 8. Écrire une fonction

val field_quartiles : string -> float * float * float

qui renvoie les quartiles associés à un champ dans le tableau complet.

On va associer, pour des quartiles \((q_1,q_2,q_3)\) :

  • la classe 0 aux valeurs \(v < q_1\) ;
  • la classe 1 aux valeurs dans \([q_1;q_2[\) ;
  • la classe 2 aux valeurs dans \([q_2;q_3[\) ;
  • la classe 3 aux valeurs \(v \ge q_3\).

Question 9. Écrire une fonction

val classify : float * float * float -> float -> int

qui renvoie la classe d'une valeur.

Question 10. En déduire une fonction

val data_pair : string list -> (float * float) list
    -> string -> float * float * float
    -> pokemon -> vector * int

telle que data_pair fields fields_spreads target target_quartiles pokemon :

  • extrait le vecteur vec des données associé à pokemon pour les champs fields avec les étendues fields_spreads ;
  • calcule la classe de pokemon à l'aide des quartiles target_quartiles pour le champ target ;
  • renvoie alors le couple (vec, classe).

k plus proches voisins naïf

On va chercher maintenant, dans les couples (vec, classe) précédents, à deviner classe à partir de vec en utilisant la méthode des plus proches voisins sur une partie des données.

On va reprendre ce qu'on a fait en C pour les \(k\) plus proches voisins.

Afin de déterminer des données d'entraînement et de test, on ne peut pas prendre un préfixe. En effet, comme les pokémons sont rangés dans l'ordre officiel, cela serait sûrement biaisé.

Question 11. Écrire une fonction

val shuffle_array : 'a array -> unit

qui mélange le tableau.

Remarque

Le mélange de Knuth (ou Fisher-Yates) consiste, pour \(i\) allant de \(1\) à \(n-1\), à échanger a.(i) avec a.(j) où \(j\) est tiré uniformément dans \(\range{0}{i}\) (Random.int (i+1)). Il produit chacune des \(n!\) permutations avec la même probabilité. Attention : tirer \(j\) dans \(\range{0}{i-1}\) ne produit que des permutations circulaires.

Question 12. Écrire une fonction

val split_data : 'a array -> int -> 'a array * 'a array

telle que split_data t clip mélange t puis renvoie un couple (t1, t2) où t1 est le sous-tableau des clip premiers éléments et t2 le sous-tableau du reste.

Pour récupérer un sous-tableau, on rappelle l'existence de la fonction Array.sub.

Question 13. Écrire une fonction

val distance_2 : vector -> vector -> float

qui prend en entrée deux vecteurs de même dimension et renvoie la distance euclidienne entre eux.

Question 14. Écrire une fonction

val distance_1 : vector -> vector -> float

qui prend en entrée deux vecteurs de même dimension et renvoie la distance 1 entre eux : \(d_1(v_1,v_2) = \sum_{i=0}^{n-1} |v_1[i] - v_2[i]|\).

Question 15. Écrire une fonction

val majority : int list -> int

qui prend en entrée une liste d'entiers et renvoie un élément majoritaire (en cas d'égalité, on prend un élément quelconque).

Note : on pourra réaliser une fonction générique fonctionnant avec des valeurs de type 'a en utilisant une table de hachage si on le souhaite.

Question 16. Écrire une fonction

val nearest_neighbors : (vector -> vector -> float)
    -> int -> (vector * 'a) array -> vector -> 'a

telle que l'appel

nearest_neighbors dist k training v

renvoie la classe, ici génériquement de type 'a, de v obtenue par les \(k\) plus proches voisins depuis les données training en utilisant la distance dist.

Question 17. Écrire une fonction

val eval_naive : int -> int -> string list -> string -> float

telle que eval_naive k clip fields target :

  • construit le tableau des (vecteur, classe) où :
    • les vecteurs sont extraits à l'aide des attributs fields ;
    • la classe se déduit des quartiles des valeurs de l'attribut target ;
  • mélange le tableau ;
  • extrait les clip premiers dans training et le reste dans tests ;
  • applique les \(k\) plus proches voisins sur chaque donnée de tests ;
  • renvoie le taux d'erreur, c'est-à-dire la proportion de données de tests mal classées.

On pourra dès maintenant tester cette fonction pour obtenir un affichage tel que celui-ci (les valeurs dépendent du mélange aléatoire) :

Guessing pokemon Height quartile from HP,Att,Def,Spa,Spd,Spe,Weight.
[250training] 1NN : error rate 51.023018%
[250training] 3NN : error rate 51.534527%
[250training] 5NN : error rate 45.524297%
[500training] 1NN : error rate 52.067669%
[500training] 3NN : error rate 46.992481%
[500training] 5NN : error rate 44.172932%
[750training] 1NN : error rate 48.226950%
[750training] 3NN : error rate 50.354610%
[750training] 5NN : error rate 46.099291%

Remarque

Avec quatre classes de même effectif, répondre au hasard donne un taux d'erreur de \(75\,\%\). Les plus proches voisins font mieux, mais les statistiques de combat ne suffisent pas à bien prédire la taille.

k plus proches voisins accéléré avec un arbre k-d

On définit le type suivant :

type 'a kd_tree =
    | Nil
    | Node of (vector * 'a) * int * 'a kd_tree * 'a kd_tree

Le type 'a est le type des éléments qu'on veut ranger dans un arbre k-d et le int désigne la dimension selon laquelle on a découpé les données dans ce nœud.

Pour construire un arbre k-d contenant les vecteurs du tableau a ayant n dimensions, on va adopter l'algorithme récursif suivant :

ConstruitKD(a, d, n)

  • a est un tableau de \(N\) paires (vecteur, donnée) ;
  • n est un entier indiquant la dimension des vecteurs et \(d \in \range{0}{n-1}\) ;
  • si le tableau a est vide, on renvoie l'arbre vide ;
  • si le tableau a est un singleton, on renvoie une feuille contenant son unique élément ;
  • sinon :
    • pour bien séparer en deux, on trie a selon la coordonnée d ;
    • la médiane m est alors au milieu du tableau, on va raisonner sur les éléments strictement à sa gauche et strictement à sa droite ;
    • on construit tg l'arbre de la première moitié avec la dimension d' = (d+1) mod n ;
    • on construit td l'arbre de la seconde moitié avec la dimension d' ;
    • on renvoie un nœud avec l'élément médian, la dimension d, tg à gauche et td à droite.

Question 18. Écrire une fonction

val kd_build : (vector * 'a) array -> int -> int -> 'a kd_tree

qui réalise cet algorithme.

Pour effectuer une recherche des \(k\) plus proches voisins dans un arbre k-d, on adopte là aussi un algorithme récursif :

RechercheKD(dist, k, t, v)

  • dist est une fonction distance, telle qu'on a toujours \(|x_i - y_i| \le \mathrm{dist}(x,y)\) ;
  • k est un entier ;
  • t est un arbre k-d ;
  • v est le vecteur dont on cherche les \(k\) plus proches voisins.

L'algorithme est alors le suivant :

  • si t est Nil, on renvoie la liste vide ;
  • sinon, on est sur un nœud (w,dim,g,d) pour le vecteur w et la dimension dim :
    • si la coordonnée v[dim] \(\le\) w[dim], on effectue récursivement une recherche dans g qui donne une liste vois1 ;
    • sinon, on effectue récursivement une recherche dans d qui donne une liste vois1 ;
    • si vois1 contient k éléments et que pour tout v' dans vois1 on a \(\mathrm{dist}(v,v') \le |v[dim] - w[dim]|\), alors on renvoie vois1 ;
    • sinon, on effectue une recherche dans le sous-arbre non exploré et on obtient une liste vois2 ;
    • on renvoie alors les \(k\) plus proches voisins de vois1 \(\cup\) vois2 \(\cup\) \(\{\) w \(\}\) (si cette union a au plus \(k\) éléments, on la renvoie telle quelle).

Question 19. Écrire une fonction

val kd_search_knn : (vector -> vector -> float) -> int -> 'a kd_tree
    -> vector -> (vector * 'a) list

qui prend en entrée une fonction de distance, un entier k, un arbre k-d t et un vecteur v, et renvoie les \(k\) plus proches voisins de v dans l'arbre t.

Question 20. En déduire une fonction

val eval_kd : int -> int -> string list -> string -> float

qui procède comme eval_naive mais en appliquant l'algorithme des \(k\) plus proches voisins à l'aide d'un arbre k-d construit sur les données d'entraînement, et renvoie le taux d'erreur.

Question 21. Modifiez vos fonctions en rajoutant une référence globale pour mesurer l'efficacité de l'arbre k-d, c'est-à-dire la proportion de calculs évités par le fait de ne parcourir qu'un seul côté. Cela revient à compter le nombre d'appels à kd_search_knn sur un nœud et à le comparer au nombre de calculs de la méthode naïve, c'est-à-dire au produit des tailles des jeux de test et d'entraînement.

On pourra faire en sorte d'avoir l'affichage suivant :

Guessing pokemon Height quartile from HP,Att,Def,Spa,Spd,Spe.
KD-tree efficiency 50.348338%
[250training] 1NN : error rate 53.964194%
KD-tree efficiency 24.361637%
[250training] 3NN : error rate 51.918159%
KD-tree efficiency 16.653708%
[250training] 5NN : error rate 52.173913%
KD-tree efficiency 60.491353%
[500training] 1NN : error rate 50.563910%
KD-tree efficiency 37.242481%
[500training] 3NN : error rate 52.067669%
KD-tree efficiency 27.301504%
[500training] 5NN : error rate 49.436090%
KD-tree efficiency 67.787707%
[750training] 1NN : error rate 50.354610%
KD-tree efficiency 45.421749%
[750training] 3NN : error rate 48.936170%
KD-tree efficiency 32.979669%
[750training] 5NN : error rate 43.617021%

k-moyennes

Question 22. Écrire une fonction

val k_means : (vector -> vector -> float) -> (vector array) -> int ->
    int array * vector array

telle que l'appel k_means dist data k renvoie un couple (classes, centers) où classes.(i) est l'entier de 0 à \(k-1\) qui indique la classe de data.(i) et centers est un tableau à \(k\) éléments qui indique les centroïdes (voir l'algorithme des k-moyennes).

Question 23. Comment pourrait-on étudier les pokémons avec cette fonction pour valider ou invalider la démarche précédente ?

Piste d'exploration : visualisation par la réduction de la dimension

Il peut être intéressant de tracer nos données dans le plan. Pour cela, on peut chercher deux vecteurs unitaires \(\vec{u}, \vec{v}\) et, étant donnée une donnée \(\vec{x}\), obtenir le point du plan \((\vec{u} \cdot \vec{x}, \vec{v} \cdot \vec{x})\).

Comment pourrait-on s'assurer d'avoir de bons vecteurs pour ces projections ?

On effectuera l'exploration en affichant les points avec Graphics ou raylib.