Cette page regroupe quelques références (ouvrages, chapitres d’ouvrages) que j’ai effectivement lues et qui me paraissent intéressantes. Elles sont classées par date d’édition. Sauf ouvrages anglo-saxons incontournables, je privilégie les références en français.
Decision Trees for Analytics Using SAS Enterprise Miner – de Ville et Neville, 2013
L'ouvrage de Barry de Ville et Paidrac Neville est à la fois un survey et un guide pour les méthodes d'induction par arbre. Quelques spécificités du logiciel SAS Enterprise Miner sont mises en avant. Le résumé complet est accessible ici.
Référence : Barry de Ville and Padraic Neville, "Decision Trees for Analytics Using SAS Enterprise Miner", SAS Institute, June 2013.
Data Mining with Decision Trees - Theory and Applications – Rokach et Maimon, 2007
L’ouvrage de Rokach et Maimon fait un état des lieux des avancées autour de l’induction des arbres de décision. Le résumé complet est accessible ici.
Référence : L. Rokach and O. Maimon, "Data Mining with Decision Trees - Theory and Applications", Series in Machine Perception and Artificial Intelligence, vol. 61, World Scientific Publising, 2007.
Méthodes de segmentation – Tenenhaus, 2007
Dans le chapitre 13 de son ouvrage (pages 501 à 546), Michel Tenenhaus décrit tout d’abord les principales mesures d’association entredeux variables (X et Y). Ct aspect est très important parce qu’il détermine le choix de la variable de segmentation dans la construction d’un arbre de décision.
Par la suite, l’auteur décrit tour à tour les méthodes CHAID, CART et SIPINA (la « méthode » SIPINA destinée à la construction des graphes d’induction). L’inventaire est relativement approfondi. Nous trouvons dans l’ouvrage des formules peu détaillées par ailleurs, comme la correction de Bonferroni à apporter au risque critique pour la segmentation avec des variables nominales ou ordinales (page 519) ; ou encore, l’écart-type de l’erreur de prédiction à utiliser lors du post-élagage pour les arbres de régression (page 533).
Référence : M. Tenenhaus, « Statistique - Méthodes pour décrire, expliquer et prévoir », Dunod, 2007.
Arbres de régression et de discrimination – Saporta, 2006
Dans la section 19.1 de son ouvrage (pages 487 à 493), Gilbert Saporta décrit brièvement les tenants et aboutissants des arbres dans l’analyse prédictive : le choix des variables de segmentation, la détermination de la taille de l’arbre, l’utilisation d’un arbre, les avantages et inconvénients des arbres de décision. L’accent est mis sur la méthode CART de Breiman et al. (1984). Les copies d’écran proviennent du logiciel SPAD.
La section s’inscrit dans un chapitre plus général (chapitre 19) consacré aux algorithmes d’apprentissage supervisé.
Référence : G. Saporta, « Probabilités, Analyse des données et Statistique », Technip, 2006.
Segmentation par arbre - Nakache et Confais, 2003
Cette partie (la 3-ème) de l'ouvrage de Nakache et Confais est dédiée à la segmentation par arbres. Deux aspects retiennent principalement l'attention : une description approfondie de la méthode CART (Breiman et al., 1984) ; l'instanciation de la segmentation dans les domaines connexes telles que l'analyse des données de survie.
Dans le chapitre 8, la description de CART est fidèle à l'ouvrage original. Tous les éléments importants sont passés en revue : le critère de division d'un segment avec l'indice de Gini ; la prise en compte des données incomplètes avec les divisions suppléantes ; etc. La procédure de détermination de l'arbre " optimal " à l'aide du post-élagage, très élaboré dans CART, est particulièrement détaillée.
Ce chapitre est largement illustré par une étude de cas sous le logiciel SPAD.
Le chapitre 9 décrit l'induction des arbres de régression. C'est suffisamment rare pour être signalé. Bien que tenant une place non négligeable dans l'ouvrage originel de Breiman et al. (1984), la méthode est à peine effleurée dans les livres ou les publications scientifiques. Avec un peu moins de détail certes que dans le chapitre précédent, les auteurs présentent l'essentiel de l'approche. C'est un des rares descriptifs dont on dispose dans les références en langue française.
Bref, cette référence peut constituer un substitut tout à fait valable pour tous ceux qui seraient rebutés par l’aridité de la monographie de Breiman et al (1984).
Le chapitre 10 enfin est une vraie originalité. Les auteurs montrent une généralisation des arbres dans le traitement des données de survie. Non pas que la méthode soit réellement originale, c'est plutôt son intégration dans un ouvrage à large diffusion qui l'est. Les références donneront aux lecteurs tous les pointeurs s'ils veulent approfondir la méthode.
Référence : J.P. Nakache, J. Confais, " Statistique Explicative Appliquée : analyse discriminante, modèle logistique, segmentation par arbre ", Technip, 2003.
Les arbres de décision – Tufféry, 2002
Dans l’ouvrage de Tufféry, les arbres de décision interviennent à deux endroits. La section 4.6.4 présente la méthode de manière simplifiée, les trois grandes méthodes C4.5 (ou C5.0 pour la version commerciale), CART et CHAID sont positionnées les unes par rapport aux autres.
Plus intéressant peut être pour les praticiens, l’auteur, dans la section 10.8.2 (pages 237 à 248), décrit la mise en œuvre des arbres de décision dans un problème de scoring. Les illustrations et le discours permettent de mesurer les avantages et les inconvénients des arbres dans le traitement de problèmes réels.
Pour les personnes qui ne sont pas familiarisées avec SAS-Enterprise Miner, les copies d’écran donnent une idée des sorties du logiciel et de la lecture qu’on peut en avoir.
Référence : S. Tufféry, « Data Mining et Socring : Bases de données et gestion de la relation client », Dunod, 2002.
Arbres de partitionnement – Bardos, 2001
Chapitre 4 de l'ouvrage de Bardos, le texte décrit la méthode CART, plus ou moins succinctement. On y retrouve en tous les cas les points importants : choix des variables de segmentation basé sur la réduction d'un critère d'impureté ; post élagage avec le mécanisme de coût complexité.
La section XII intéressera les praticiens. Il présente les résultats que peut produire un arbre de décision en analyse financière. Dans l'exemple traité, l'objectif est de mettre à jour les déterminants de la défaillance des entreprises dans le secteur du bâtiment.
Référence : M. Bardos, " Analyse discriminante - Application au risque et scoring financier ", Dunod, 2001 ; chapitre 4.
Segmentation - Lebart et al., 2000
Lebart et al. (2000) consacre une section à la discrimination par arbres dans leur ouvrage. La description assez succincte est basée sur la méthode CART, à l’instar de la très grande majorité des ouvrages en français. Il s’agit quand même d’un survol assez rapide, avec une présentation classique du gain d’impureté comme critère de segmentation, et du post- élagage.
Dans la sous section 3.5.5, les auteurs positionnent les arbres par rapport aux autres méthodes de discrimination. Les réflexions émises sont très pertinentes. Elles permettent de bien situer ce que représentent les arbres parmi les autres méthodes prédictives : qu’est-ce qu’on peut en attendre, qu’est-ce que les arbres ne pourront jamais faire.
Référence : L. Lebart, A. Morineau, M. Piron, « Statistique exploratoire multidimensionnelle », Dunod, 2000 ; section 3.5, chapitre 3.
Graphes d'induction - Apprentissage et Data Mining – Zighed et Rakotomalala, 2000
Écrit avec un collègue, cet ouvrage reprend en grande partie ma thèse de doctorat.
Il se démarque néanmoins par la " Partie 2 ", très didactique, où les méthodes les plus populaires (CHAID, CART et C4.5) sont présentées de manière détaillée. En effet, si la CART est largement décrite dans les ouvrages en langue française, C4.5 et CHAID sont souvent passés sous silence. Pourtant il s'agit de méthodes très largement répandues dans la communauté scientifique, et programmées dans une foultitude de logiciels commerciaux. Les chapitres qui s'y rapportent positionnent les avantages et inconvénients de ces techniques.
Autre aspect intéressant, le chapitre 8, toujours dans la partie 2, consacrée à la segmentation binaire généralisée permet de ramener dans un cadre commun les variantes consacrées au traitement des variables d'intérêt nominales, ordinales et continues. Le formalisme adopté donne des éléments de compréhension sur l'essence de l'induction par arbres, il permet aussi de mieux comprendre les différentes généralisations que l'on pourrait apporter lorsque l'on décide de traiter d'autres types de problèmes (les arbres de classification par ex., où on traite en bloc un groupe de variables d'intérêt).
Référence : D.A. Zighed, R. Rakotomalala, " Graphes d'Induction - Apprentissage et Data Mining ", Hermès, 2000.
Graphes d’Induction – Rakotomalala, 1997
Ma thèse de doctorat. Ma principale contribution aura été de compiler, de classer, les innombrables variantes qui existaient à l'époque concernant la construction d'un arbre de décision. C'étaient le temps où la méthode monopolisait les conférences en apprentissage automatique. Le besoin de faire le point sur tout cela se faisait sentir.
Plusieurs aspects sont étudiés en détail : les mesures utilisées pour le choix de la variable de segmentation sur un sommet ; la détermination de la bonne taille de l'arbre ; les différentes manières d'extraire les règles dans un arbre ; les justifications théoriques des graphes d'induction, généralisation des arbres de décision ; la discrétisation des attributs continus.
Autre élément très positif avec le recul, le logiciel SIPINA qui implémente une très grande majorité des approches décrites dans le rapport. Combien de thèses consacrent un chapitre sur des implémentations, qui ne sont disponibles nulle part, utilisées dans des expérimentations que personne ne pourra jamais reproduire ? Le fait d'avoir mis en accès libre SIPINA (Version 2.5 en l'occurrence) permet à tout un chacun de vérifier l'efficacité de ces variantes sur leurs propres données. Et le logiciel est toujours diffusé à ce jour. La version 3.x de SIPINA a pris le relais depuis. Plusieurs techniques d’induction d’arbres de décision, y compris la fameuse méthode CART de Breiman et al. (1984) prenant en charge les coûts de mauvais classement, y sont proposés.
Référence : R. Rakotomalala, " Graphes d'Induction ", Thèse de Doctorat, Université Claude Bernard Lyon 1, 1997.
Arbres de discrimination binaire - Guéguen, 1994
Chapitre 7 rédigée par A. Guéguen dans un ouvrage collectif, il décrit principalement la méthode CART de Breiman et al. (1984), abordant tous les points important de l'approche, notamment le post élagage.
Elément intéressant, la section 7.8 détaille les calculs sur une étude de cas. Le lecteur peut ainsi suivre dans le détail la séquence des calculs et la détermination de l'arbre " optimal ".
Comme nous pouvons le constater dans cette page consacrée aux références bibliographiques, ce texte arrive à une période où les écrits en français relatifs aux arbres de décision sont quasiment inexistants.
Référence : A. Guéguen, " Arbres de discrimination binaire ", in Analyse discriminante sur variables qualitatives, G. Celeux et J.P. Nakache éditeurs, Polytechnica, 1994.
C4.5 – Programms for Machine Learning – Quinlan, 1993
Au premier abord, cet ouvrage laisse perplexe. Près de 60% du texte (pages 109 à 287) est constitué du code source en C de son programme. On se sent un peu spolié de l'avoir payé aussi cher.
Pour ce qui est du texte utile (pages 1 à 107), on est étonné dans un premier temps du faible niveau technique, avec très peu de formules ou de démonstrations.
Dans un second temps, on se rend compte que l'auteur a réellement pris beaucoup de recul par rapport à la méthode, allant avant tout à l'essentiel, sans essayer de noyer tout cela dans un charabia pseudo-mathématique comme on le voit trop souvent hélas dans les monographies. L'exposé est très clair, accessible pour des non spécialistes. L'auteur s'attache à mettre en évidence la quintessence de l'induction par arbres. Il aborde les sujets clés tels que le choix des variables de segmentation, le post-élagage, l'extraction des règles à partir d'un arbre, la discrétisation floue lors du traitement des variables continues, etc.
Manifestement, Quinlan sait de quoi il parle. Il s’attache à mettre en avant avec des mots simples les aspects les plus importants de la construction d’un arbre de décision. Finalement, je ne suis pas si déçu que cela d’avoir acheté ce livre. Même si j’ai un peu du mal à avaler les 179 pages de listing C imprimé.
Référence : R. Quinlan, « C4.5 : Programs for Machine Learning », Morgan Kaufmann, 1993.
Classification and Regression Trees – Breiman et al., 1984
« LA » monographie de référence. Celle que tout chercheur s’intéressant aux arbres de décision se doit d’avoir dans sa bibliothèque. Elle est absolument incroyable par la qualité du discours des auteurs, par le niveau des réflexions qu’ils émettent. Il reste néanmoins que sa lecture est assez ardue. La présentation est parfois très technique. Certains thèmes sont abordés plusieurs fois, à différents endroits, avec des prismes différents. A l’évidence, l’ouvrage ne convient pas aux amateurs éclairés ou les étudiants, ceux qui cherchent avant tout à comprendre l’intérêt et la trame sous-jacente à la construction des arbres de décision.
Attribuons une mention particulière au chapitre 5 « Strengthening and Interpreting » qui suggère différentes pistes pour améliorer l’efficacité des arbres. Certaines des idées qui y sont émises ont inspiré des thèses de doctorats d’autres chercheurs, comme les arbres obliques de Sreerama Murthy (1994) par exemple.
De même, le chapitre 8 « Regression Trees » est exclusivement dédié aux arbres de régression est tout à fait remarquable (pages 216 à 265). Je ne connais pas d’autre référence qui expose avec un tel niveau de détail les caractéristiques de cette méthode. Les arbres de régression sont souvent présentés comme une variante des arbres de décision dans la littérature, avec quelques mots simplement pour expliquer les spécificités de la méthode relative à la prise en compte d’une variable cible quantitative.
Une référence à lire et à relire…
Référence : L. Breiman, J. Friedman, R. Olshen, C. Stone, « Classification and regression trees », Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984.
