Probleme – ID3 de bout en bout

1. Le code. Il tient en trente lignes, et il s'exécute.

type arbre = Feuille of bool | Noeud of arbre * int * arbre
(* Noeud (branche « test faux », indice du test, branche « test vrai ») *)

type exemple = { nom : string; att : bool array; eti : bool }

(* Entropie des étiquettes de ex. Vaut 0 sur l'ensemble vide (convention
   0 log 0 = 0). Complexité : Theta(|ex|). *)
let entropie ex =
  let n = List.length ex in
  if n = 0 then 0.0
  else begin
    let p = float_of_int (List.length (List.filter (fun e -> e.eti) ex))
            /. float_of_int n in
    let terme q = if q <= 0.0 then 0.0 else -. q *. (log q /. log 2.0) in
    terme p +. terme (1.0 -. p)
  end

let separer ex t = List.partition (fun e -> e.att.(t)) ex

(* Gain d'information du test t sur ex. Complexité : Theta(|ex|). *)
let gain ex t =
  let (oui, non) = separer ex t in
  let n = float_of_int (List.length ex) in
  entropie ex
  -. float_of_int (List.length oui) /. n *. entropie oui
  -. float_of_int (List.length non) /. n *. entropie non

let majoritaire ex =
  let o = List.length (List.filter (fun e -> e.eti) ex) in
  2 * o >= List.length ex

let homogene ex = match ex with
  | [] -> true
  | e :: r -> List.for_all (fun f -> f.eti = e.eti) r

(* Arbre de décision d'ID3. Précondition : ex non vide.
   Terminaison : la liste tests décroît strictement à chaque appel.
   Complexité : O(|tests|² · |ex|) sur cette version. *)
let rec id3 ex tests =
  if homogene ex || tests = [] then Feuille (majoritaire ex)
  else begin
    let meilleur = List.fold_left
        (fun a t -> if gain ex t > gain ex a then t else a)
        (List.hd tests) tests in
    let (oui, non) = separer ex meilleur in
    let reste = List.filter (fun t -> t <> meilleur) tests in
    Noeud (id3 non reste, meilleur, id3 oui reste)
  end

Terminaison : le variant est la longueur de tests, qui perd une unité à chaque appel récursif et reste positive ; la récursion a donc au plus $|tests|$ niveaux. Correction partielle : par construction, chaque feuille porte l'étiquette majoritaire d'un sous-ensemble homogène — donc exacte — ou d'un sous-ensemble qu'aucun test ne peut plus séparer.

2. L'arbre. L'exécution donne $H(S)=0,9710$, puis les gains $0,6100$ (couvert), $0,4200$ (vent), $0,0200$ (humide) ; la racine est donc « couvert ? ». La branche « non » est homogène : feuille « oui ». La branche « oui » compte cinq jours ($1$ oui, $4$ non, $H=0,7219$), où « vent fort » a un gain de $0,7219$ — il sépare parfaitement — contre $0,1710$ pour « humide ». D'où :

couvert ?
  oui : vent fort ?
          oui : -> non
          non : -> oui
  non : -> oui

C'est exactement l'arbre de la figure du cours, et il commet $0$ erreur sur les dix jours.

3. Zéro erreur n'est pas une bonne nouvelle en soi. C'est le chiffre mesuré sur les données qui ont servi à construire l'arbre : par l'exercice 26.10, un modèle assez souple l'obtient toujours. Ici, l'arbre n'a que trois feuilles pour dix exemples, donc il résume vraiment — mais rien ne le prouve tant qu'on n'a pas testé sur des jours nouveaux. La seule mesure honnête est celle du problème 26.4.

4. Le numéro du jour, et le piège des seuils. Un attribut numérique se teste par « $v\le s$ ? », avec $s$ pris parmi les $n-1$ milieux entre valeurs consécutives. Sur le numéro de jour, le test « numéro $\le 5$ ? » sépare exactement les cinq premiers jours des cinq derniers, c'est-à-dire ici les « oui » des « non » sauf $j_{10}$ : son gain est très élevé, et ID3 le préférerait au bon test. L'arbre obtenu classerait parfaitement les dix jours et serait inutilisable sur le onzième, dont le numéro n'a jamais été vu.

La leçon, et elle vaut au-delà d'ID3 : un attribut qui identifie les exemples obtient toujours le meilleur gain. Il ne prédit rien, il mémorise. On l'écarte à la main, ou l'on pénalise les tests trop fins — mais aucune formule ne remplace la question « cet attribut sera-t-il disponible, et signifiant, sur une donnée nouvelle ? ».