(:construction d'un arbre de décision avec R:)

TP RdF, semaine 9: arbres de décision

Ce TP est réalisé dans l'environnement R. Ce TP est inspiré d'un exercice de Lionel Moisan.

Question de bon sens

Deux joueurs (notés A et B) jouent au jeu suivant: A choisit un nombre entier x entre 1 et N (N étant un nombre connu de A et B), et B doit le deviner en lui proposant successivement des valeurs. Pour chaque valeur possible de x proposée par B, A répond “gagné !”, “x est plus petit”, ou “x est plus grand”.

a) Avant de jouer, B dit à A: “je n’ai pas besoin de plus de 4 propositions pour gagner”. A répond alors à B: “C’est vrai, mais avec mon choix de x tu auras besoin d’exactement 4 propositions”. Que vaut N ?

b) B répond alors: “Avec l’information que tu viens de me donner, je suis presque sûr de gagner avant.” Expliquer le raisonnement de B et calculer la quantité d’information que lui a donnée A par sa réponse.

Variante du jeu du pendu

Le but de cet exercice est d'étudier une variante du jeu du "pendu"

1. Chargement de la base de noms

Charger la base de noms d'animaux grâce à la commande

# Chargement de la base de noms d'animaux
source ("rdfAnimaux.txt")

Ce fichier définit une liste (vecteur) "noms". Afficher le contenu de la liste et calculer le nombre de mots qu'elle contient (valeur à stocker dans la variable "n").

2. But du jeu

Le but du jeu est le suivant: vous choisissez le nom d'un animal, et le programme doit essayer de le deviner le plus rapidement possible en posant uniquement des questions de type :

          "Ce mot contient-il la lettre xxxx ?"

où xxxx est remplacé par une des 26 lettres de l'alphabet (on joue sans les accents et on interdit les noms composés).

Si le programme est sûr de trouver la solution en au plus p questions, quelle est la relation entre n et p ? En déduire une valeur numérique minimale pour p.

3. Que fait ce code?

Selon vous, à quoi sert la fonction suivante ?

maFonction <- function(x) { strtoi(charToRaw(x),16L)-96 }

Renommer cette fonction pour que le nom soit plus explicite.

Expliquer ce que contient la matrice "mat" après exécution des commandes R suivantes:

mat = matrix(rep(0,26*n),nrow=26, ncol=n);
for (i in 1:n)
{
    c = str2int(noms[i]);
    mat[c,i] <- 1;
}

(on supposera que maFonction a été renommée str2int... :-)

4. Quelle lettre est la plus représentée?

Calculer, sous la forme d'un vecteur à 26 colonnes h(i), la proportion de mots qui contiennent (au moins une fois) la lettre i. Quelle est la lettre la plus représentée ?

5. Entropie

Calculer, pour tout i, l'entropie de la partition des mots en deux ensembles, les mots qui contiennent la lettre i et les autres. Il n'est pas nécessaire de faire une boucle, une seule formule suffit à partir du vecteur h. Pour calculer l'entropie, on utilisera des expressions du type log(t^t) plutôt que du type t*log(t) pour contourner le problème de la non définition du logarithme en t=0.

6. Première question

En déduire la 1ère question que doit poser le programme pour maximiser l'information gagnée en moyenne.

(utiliser les fonction max et which.max)

Partie nécessitant plus de réflexion (une aide sera mise en ligne si nécessaire)

7. Partage

Écrire une fonction qui renvoie l'indice i de la lettre associée à la question la plus informative pour le sous-ensemble de mots courant, ainsi que la partition de ce sous-ensemble.

8. Partage itératif

Ecrivez une fonction qui permet de partager itérativement l'ensemble initial en sous-ensembles de plus en plus petits.

9. A vous de jouer

Enfin, écrire une fonction qui permet de jouer interactivement avec l'ordinateur...

(utiliser la fonction scan())

10. Affichage de l'arbre construit

Définir une fonction pour construire et afficher l'arbre de décision optimal associé au jeu

Pour continuer

En modifiant un peu la fonction arbre, calculer :

  • la profondeur maximale de l'arbre,
  • les mots les plus défavorables (i.e. qui nécessitent le plus grand nombre de questions),
  • le nombre moyen de questions nécessaires pour trouver la solution en suivant cet arbre. A quoi faut-il comparer ce nombre et à quoi est due la différence ?

Eléments de correction (mise en ligne le mercredi 29 mars!)

Fonction de partage

str2int <- function(x) { strtoi(charToRaw(x),16L)-96 }
int2str <- function (x) { rawToChar(as.raw(x+96)) }

partage <- function (I) {
    source ("rdfAnimaux-r.txt")
    n <- length(noms)
    mat = matrix(rep(0,26*n),nrow=26, ncol=n);
    for (i in 1:n) { mat[str2int(noms[i]),i] <- 1; }
    relevant <- mat[,I]
    nrelevant <- dim(relevant)[2]
    freq <- matrix(rep(0,26),nrow=26, ncol=1)
    for (i in 1:26) { freq[i] <- sum(relevant[i,]); }

    proba <- freq/nrelevant; probacomp <- 1-proba
    hrel <- -log2(proba^proba); hrelcomp <- -log2(probacomp^probacomp)
    H <- hrel+hrelcomp
    maxR <- which.max(H)

    result <- matrix(rep(0,3*n),nrow=3, ncol=n)

    A <- matrix(,nrow=0, ncol=n)
    for (k in 1:n) { A <- c(A, I[k] & (mat[maxR,k] == 1) ) }
    result[1,] <- A

    B <- matrix(,nrow=0, ncol=n)
    for (k in 1:n) { B <- c(B, I[k] & (mat[maxR,k] == 0) ) }
    result[2,] <- B
    result[3,1] <- maxR
    result
}

Fonction de jeu

joue <- function () {
    print("Choisissez le nom d'un animal...");
    source ("rdfAnimaux-r.txt")
    n <- length(noms)
    mat = matrix(rep(0,26*n),nrow=26, ncol=n);
    for (i in 1:n) { mat[str2int(noms[i]),i] <- 1; }
    n <- dim (mat) [2]
    I <- matrix(rep(TRUE,n),nrow=n,ncol=1)

    while(sum(I)>1) {
        R <- partage(I)
        print(c("Ce mot contient-il la lettre",int2str(R[3,1]),"0/1 + ENTER + Ctrl-D"));
        answer <- scan()
        if (answer==1) I <- (R[1,]==1) else I <- (R[2,]==1)
    }
    print(c("L'animal est : ",noms[I]))
}