dimanche 30 mars 2008

Listes de décision (vs. arbres de décision)

Les listes de décision (decision list en anglais) font partie des méthodes d’apprentissage supervisé très en vogue au début des années 90. La méthode est très proche de l’induction par arbres, elle produit des règles de production triées et mutuellement exclusives du type « Si condition_1 Alors conclusion_1 Sinon Si condition_2 Alors conclusion_2 Sinon Si… ».

Si le biais de représentation est très proche des arbres de décision, les DL construisent des hyper-rectangles les plus homogènes possibles du point de vue de la variable à prédire, le biais de préférence est différent, elles procèdent par « Separate-and-conquer » et non par « Divide-and-conquer », elles disposent donc un degré de liberté supplémentaire pour mettre en avant les solutions les plus spécialisées. Cette liberté a un prix, cette méthode est souvent sujette au sur apprentissage à force de vouloir détecter à tout prix les sous populations les plus intéressantes, son paramétrage est alors primordial pour éviter qu’elle ne produise des règles couvrant trop peu d’individus et de ce fait non significatives.

La méthode que nous avons implémentée dans TANAGRA est très largement inspirée de CN2 (Clark & Niblett, ML-1989). Nous avons pris quelques libertés : (1) en simplifiant l’exploration de l’espace des hypothèses, nous utilisons un « hill-climbing » simple plutôt qu’un « best-first search », nettement plus coûteux en CPU mais pas vraiment plus efficace ; (2) en introduisant un paramètre supplémentaire, le support de la règle, pour éviter que des règles sur-spécialisées et non-significatives apparaissent.

Dans ce didacticiel, nous comparons les performances de CN2 avec CART. Notons que CN2 ne sait pas manipuler directement les attributs continus, nous devons les discrétiser au préalable, nous utilisons la méthode MDLPC (Fayyad et Irani, 1993) pour cela. Les taux d’erreur sont mesurés par bootstrap. On constate que les méthodes se valent. Ce qui n’est pas étonnant, les biais de représentation sont (quasiment) identiques.

Mots clés : CN2, decision list, listes de décision, arbres de décision, CART, discrétisation
Composants : Supervised Learning, MDLPC, Decision List, C-RT, Bootstrap
Lien : fr_Tanagra_DL.pdf
Données : dr_heart.bdm
Référence : P. Clark, « CN2 – Rule induction from examples ».