Seules les principales méthodes d'induction d'arbres de décision sont décrites dans cette section.
Improved CHAID (Tschuprow Goodness of Split)
Description. Ma méthode préférée, celle que je présente en priorité dans mes enseignements. Elle est directement dérivée de CHAID. Elle apporte quelques améliorations : le critère t de Tschuprow est substitué au KHI-2, essentiellement parce qu'il est normalisé ; des paramètres supplémentaires sont introduits pour mieux contrôler la taille de l'arbre.
Paramètres.
P-level for splitting nodes : Risque critique du test d'indépendance du KHI-2 lors de la segmentation. Si la p-value du test est supérieur à ce seuil, le partitionnement est refusé. Plus on diminue ce seuil, plus petit sera l'arbre de décision.
P-level for merging nodes : Risque critique du test d'équivalence distributionnelle (basé aussi sur une statistique du KHI-2) lors de la fusion. Si la p-value du test est plus petit que ce seuil, les sommets ne sont pas fusionnés. Plus le seuil sera grand, moins nous serons enclins à fusionner, plus l'arbre sera large.
Ajustement de Bonferroni : Les p-value calculées sont faussées car, à chaque étape, nous multiplions les tests pour choisir la meilleure configuration, augmentant ainsi la chance de trouver une segmentation fallacieusement intéressante. Pour contrecarrer cette propension, on peut introduire la correction de Bonferroni, bien connue dans les comparaisons multiples en statistique. A mon sens, mieux vaut ne pas trop s'appuyer sur ce paramètre qui donne l'illusion de « vérité statistique ». Nous sommes dans le cadre de l'induction, si nous souhaitons guider l'apprentissage vers des solutions qui nous conviennent plus (arbre plus petit et/ou moins large), mieux vaut, en toute conscience, manipuler les paramètres "p-level".
Max. depth : Ce paramètre permet de limiter la profondeur de l'arbre. Il a une vraie utilité pratique. Dans la majorité des cas, les utilisateurs lancent un premier traitement « pour voir », prendre connaissance des données, comprendre les différentes interactions entre les variables. Il est tout à fait inutile dans cette première étape de construire un arbre qui peut être immense, illisible, qui rebuterait plus qu'autre chose. Par la suite, l'utilisateur peut le modifier pour produire un arbre performant.
Min size of node to split : Il s'agit de l'effectif minimum pour segmenter. Si un sommet comporte un effectif inférieur à ce seuil, le partitionnement ne sera même pas lancé.
Min size of leaves : Il s'agit de l'effectif d'admissibilité. Lors de la segmentation d'un nœud, on vérifie si toutes les feuilles produites ont un effectif supérieur ou égal à ce seuil. Dans le cas contraire, la segmentation est refusée, SIPINA choisira la variable suivante (si elle passe les critères de segmentation).
Référence. R. Rakotomalala, " Arbres de décision ", in Revue Modulad, n°33, 2005.
Mutithreaded ChAID (Tschuprow)
Description. C'est la version multithread de la méthode "Improved CHAID". Elle est optimisée pour exploiter au mieux les ressources de la machine. Le nombre de thread à utiliser est paramétrable.
Paramètres (additionels par rapport à Improved CHAID).
Number of threads : Nombre de threads à utiliser pour les calculs. Nous pouvons spécifier plus de threads que de nombre de coeurs disponibles, mais cela n'accélèrera pas pour autant les traitements. Nous pouvons également demander à Sipina de détecter le nombre de coeurs du processeur en cliquant sur le bouton "Get number of cores".
Enable post pruning : Active le post-élagage après la phase d'expansion de l'arbre. Dans un processus "bottom-up", les feuilles de mêmes conclusions sont automatiquement supprimées. Lorsque les conclusions sont différentes, la méthode effectue un test de comparaison des taux d'erreurs entre le sommet père et ses feuilles. Si elles ne sont pas significativement différentes, un élagage est opéré.
Sig. level for post pruning : Niveau de signification (risque) utilisé pour la comparaison des taux d'erreurs durant le processus de post-élagage.
Référence. R. Rakotomalala, "Multithreading pour les arbres de décision", Novembre 2010.
C4.5 (Quinlan, 1993)
Description. La méthode de référence au sein de la communauté "apprentissage automatique". Vers la fin des années 1980, Quinlan a publié d'innombrables variantes de son algorithme de base, ID3 (Quinlan, 1979). Avec C4, puis C4.5, il est arrivé à une sorte d'aboutissement dont il a résumé les grandes lignes dans son ouvrage « C4.5: Programs for Machine Learning ».
Notre implémentation s'appuie sur deux aspects essentiels de C4.5, décrits dans l'ouvrage : le choix de la variable de segmentation avec le gain ratio ; le post élagage avec le principe de l'erreur pessimiste. Notons que Quinlan lui même avait mis en ligne le code source de son application. Au fil des versions, un nombre très important d'options destinées à bonifier l'apprentissage, mais ne remettant pas en cause le principal, se sont greffées (jusqu'à la Release 8). Nous ne les avons pas implémentées.
Les qualités de C4.5 ne sont plus à démontrer. Par rapport aux autres techniques, nous dirons qu'elle a tendance à produire des arbres plus grands, plus profonds. Ceci d'autant plus que l'effectif du fichier est important.
Une version commerciale C5.0 a vu le jour par la suite, son contenu scientifique n'est pas connu.
Paramètres.
CL (confidence level) for pessimistic pruning : Niveau de confiance pour le calcul de l'erreur pessimiste, qui est simplement la borne haute de l'intervalle de confiance de l'erreur.
Size of leaves : Taille minimum des feuilles issues de la segmentation. Il faut que 2 des feuilles au moins ait un effectif supérieur ou égal à ce seuil pour que la segmentation soit acceptée.
Références.
R. Quinlan, « C4.5: Programs for Machine Learning », Morgan Kaufman Publishers, 1993.
R. Kohavi, R. Quinlan, « Decision Tree Discovery », in Handbook of Data Mining and Knowledge Discovery, Klosgen & Zytkow Editors, Chapter 16.1.3, pages 267-276, Oxford University Press, 2002.
Cost sensitive C4.5 (Rakotomalala et Chauchat, 2001)
Description. Dans une analyse, les coûts de mauvais classement sont rarement unitaires et symétriques. Dans un problème à 2 classes (malade vs. non-malade par exemple), diagnostiquer l'absence de la maladie chez une personne souffrante n'a pas les mêmes implications que la situation inverse. Il faudrait en tenir compte durant la construction du modèle de prédiction.
Cette méthode est une variante de C4.5 intégrant explicitement la matrice de coûts de mauvais classement lors de l'exploration de l'espace de solutions. Elle a été mise en œuvre dans le cadre d'une étude réelle en partenariat avec une entreprise. Les résultats ont été publiés.
Schématiquement, par rapport à l'algorithme de base C4.5, nous pouvons tenir compte des coûts de 2 manières : (1) durant la phase d'expansion de l'arbre, lors du calcul du critère de segmentation, les expérimentations montrent que cette phase n'est pas très déterminante (Drumond et Holte, 2000) ; (2) durant la phase de post élagage, nous ne calculons plus une erreur pessimiste pour décider de la suppression des feuilles, mais plutôt un coût pessimiste, qui tient compte du poids des sommets.
Il existe un grand nombre de techniques permettant d'introduire les coûts de mauvais classement lors de l'induction. Notre méthode s'est beaucoup inspirée des travaux de Bradford et al. (1998), citée en référence. Elle a le mérite de produire le classifieur en un seul passage sur les données, à la différence des approches basées sur la (re)pondération des observations.
L'intérêt de cette méthode est mis en avant dans un didacticiel traitant de la détection automatique de spams dans les courriels. Nous y apprenons également comment procéder pour introduire les informations sur les coûts dans Sipina.
Paramètres.
CL (confidence level) for pessimistic pruning et Size of Leaves sont les mêmes paramètres que pour C4.5.
Handling costs Growing : Tenir compte des coûts durant la phase d'expansion de l'arbre.
Handling costs Pruning : Tenir compte des coûts durant la phase de post élagage de l'arbre.
Références.
J.H. Chauchat, R. Rakotomalala, M. Carloz, C. Pelletier, « Targeting customer groups using gain and cost matrix : a marketing application », Proc. of Data Mining for Marketing Applications Workshop, PKDD'2001, pp. 1-13, 2001.
J. Bradford, C. Kunz, R. Kohavi, C. Brunk, C. Brodley, « Pruning decision trees with misclassification costs », Proc of 10th ECML, pp. 131-136, 1998.
C. Drummond, R. Holte, « Exploiting the cost of (in)sensitivity of decision tree splitting criteria », Proc. of ICML, pp.239-246, 2000.
ID3-IV (Quinlan, 1986)
Description. ID3-IV (1986) est la (une des) dernière version de ID3, avant que Quinlan ne se tourne vers le post-élagage avec C4 puis C4.5 (et les autres versions commerciales, non publiées qui s'en suivront).
Par rapport à l'algorithme originel (ID 3 - Quinlan, 1979), il apporte un certain nombre d'améliorations, dont une nouvelle stratégie de pré-élagage basée sur un test d'indépendance du KHI-2. Lorsque la segmentation n'est plus significative, le sommet n'est plus segmenté.
Paramètres.
Confidence level : Risque du test d'indépendance du KHI-2 sur un nœud à segmenter. Une p-value du test plus grande que ce constitue une règle d'arrêt de l'expansion de l'arbre.
Référence. J. Quinlan, " Induction of Decision Trees ", in Machine Learning, 1, pp.81-106, 1986.
ASSISTANT 86 (Cestnik et al., 1987)
Description. ASSISTANT 86 fait partie des méthodes dérivées de ID3 (Quinlan, 1979). Elle introduit un certain nombre d'améliorations destinées à mieux guider l'induction.
L'arbre construit est forcément binaire. Lors de la segmentation, ASSISTANT cherche la combinaison qui maximise le gain d'entropie. L'implémentation de SIPINA utilise un algorithme glouton. Il n'est pas question de tester toutes les configurations possibles, surtout lorsque les variables candidates prennent un grand nombre de modalités.
Plusieurs paramètres sont introduits pour contrôler la taille de l'arbre.
Paramètres.
Attribute suitability : Le gain d'entropie (multiplié par l'effectif) sur un nœud est comparé à ce seuil, s'il est plus petit, la segmentation est refusée. Plus ce seuil sera augmenté, plus l'arbre sera réduit. Ce paramètre est assez difficile à manipuler. Nous n'avons pas de référentiel facile à interpréter.
Class frequency : Que l'on appelle seuil de spécialisation dans d'autres logiciels. Si une des modalités de la variable à prédire a une fréquence plus élevée que ce seuil, la segmentation n'est pas réalisée. Ce paramètre varie entre 0 et 100%, plus il sera proche de 100%, plus grand sera l'arbre de décision.
Node weight : Il s'agit de la taille minimum avant segmentation, mais exprimée en termes relatifs. Si le " poids " d'un sommet est plus petit que ce seuil (poids du sommet : effectif du sommet / effectif total), la segmentation n'est pas tentée. Ce paramètre varie entre 0 et 100%. Si on le fixe à 100%, seul la racine sera (éventuellement) segmentée.
Référence. B. Cestnik, I. Kononenko, I. Bratko, " ASSISTANT 86: A Knowledge Elicitation Tool for Sophistical Users ", Proc. of the 2nd European Working Session on Learning, pp.31-45, 1987.
GID3 (Cheng et al., 1988)
Description. GID3 est une " généralisation " de ID3 dans le sens où, lors d'une segmentation, les modalités non informatives de la variable de partitionnement sont fusionnées. L'objectif est de ne produire de feuilles que pour les modalités importantes, et de mettre dans un lot à part (modalité " autres ") celles qui ne sont pas pertinentes pour la prédiction des valeurs de la classe.
Schématiquement, lors d'une segmentation, la technique consiste à détecter la modalité qui minimise l'entropie de Shannon. Puis, on évalue les autres feuilles enfants par rapport à cette référence : si l'entropie est significativement plus élevée, elle est fusionnée avec la feuille " autres ".
Pour déterminer le seuil de signification, les auteurs proposent le paramètre " tolerance level (TL) " : si l'entropie de la feuille est plus grand que " TL * Min ", elle est considérée comme non informative.
Paramètres.
Confidence level : Risque du test d'indépendance lors de la segmentation d'un nœud. Si la p-value du test du KHI-2 est plus grand que ce seuil, le partitionnement est rejeté.
Tolerance level : niveau de tolérance pour la fusion des sommets. Si on fixe une valeur < 1, toutes les feuilles issues de la segmentation seront systématiquement fusionnées. Si TL =1, on aura un arbre binaire. Si TL est très grand, on obtient un arbre identique à ID3-IV (Quinaln, 1986).
Référence. J. Cheng, U. Fayyad, K. Irani, Z. Qian, " Improved decision trees: a generalized version of ID3 ", Proc. of 5th International Conference on Machine Learning, pp.100-108, 1988.
A Limited search induction tree algorithm (Catlett, 1991)
Description. Catlett (1991) est certainement un des premiers data miner de l’histoire. En effet, plusieurs années avant la grande vague du data mining et l’article fondateur de Fayyad (1996), il a présenté une thèse de doctorat explicitement tournée vers l’optimisation des algorithmes de machine learning, en l’occurrence les arbres de décision, dans le traitement des très grandes bases de données.
Le titre de sa thèse, « Megainduction : Machine learning on very large databases », est assez édifiant. Il a ainsi proposé des solutions ad hoc, peut-être sous optimales lorsqu'on s'intéresse exclusivement aux performances en classement, mais qui se justifient pleinement dès lors que l'on souhaite appréhender les très gros volumes.
La méthode « A limited search induction tree algorithm » fait partie justement des solutions préconisées dans sa thèse de doctorat. L’idée est simple, on fixe a priori le nombre de segmentations à réaliser lors de la construction de l’arbre. En dehors du contexte megainduction, la solution peut paraître un tantinet arbitraire. Mais elle vaut autant qu’une autre. En effet, il est très difficile de définir une règle d’arrêt simple et crédible lors de l’expansion de l’arbre. Le post élagage, même s’il est plus efficace pour déterminer la bonne taille de l’arbre, impose la construction dans un premier temps de l’arbre maximum, rédhibitoire sur de très grandes bases.
Paramètres.
Number of max splits : nombre maximum de segmentations que l’on peut introduire lors de la construction de l’arbre
Référence. J. Catlett, « Megainduction : Machine learning on very large databases », PhD Thesis, School of Computer Science, University of Technology, Sydney, Australia, 1991.
CHAID (Kass, 1980)
Description. CHAID est la variante supervisée (variable à prédire catégorielle) des techniques issues de AID (Morgan et Sonquist, 1963), considérée comme l'ancêtre de toutes les méthodes de segmentation.
Cette méthode se démarque de deux manières : le critère de segmentation est le KHI-2 ; les feuilles produites par un partitionnement peuvent être fusionnées si elles présentent des profils (distributions) identiques.
Ces deux particularités se complètent fort heureusement. En effet, le KHI-2 a la fâcheuse tendance de favoriser les variables comportant un grand nombre de modalités. Avec le processus de fusion, on évite l'élaboration d'arbres trop « larges ».
La méthode CHAID est très largement diffusée, très populaire auprès des statisticiens, elle est présente dans de nombreux logiciels commerciaux. Elle l'est moins souvent en revanche dans les logiciels libres, elle est peu connue de la communauté « machine learning ».
L'approche "Improved CHAID" ci-dessus est une variante améliorée de CHAID.
Paramètres.
P-level for splitting nodes : Risque critique du test d'indépendance du KHI-2 lors de la segmentation. Si la p-value du test est supérieur à ce seuil, le partitionnement est refusé. Plus on diminue ce seuil, plus petit sera l'arbre de décision.
P-level for merging nodes : Risque critique du test d'équivalence distributionnelle (basé aussi sur une statistique du KHI-2) lors de la fusion. Si la p-value du test est plus petit que ce seuil, les sommets ne sont pas fusionnés. Plus le seuil sera grand, moins nous serons enclins à fusionner, plus l'arbre sera large.
Ajustement de Bonferroni : Les p-value calculées sont faussées car, à chaque étape, nous multiplions les tests pour choisir la meilleure configuration, augmentant ainsi la chance de trouver une segmentation fallacieusement intéressante. Pour contrecarrer cette propension, on peut introduire la correction de Bonferroni, bien connue dans les comparaisons multiples en statistique. A mon sens, mieux vaut ne pas trop s'appuyer sur ce paramètre qui donne l'illusion de « vérité statistique ». Nous sommes dans le cadre de l'induction, si nous souhaitons guider l'apprentissage vers des solutions qui nous conviennent plus (arbre plus petit et/ou moins large), mieux vaut, en toute conscience, manipuler les paramètres « p-level ».
Référence. G. Kass, « An exploratory technique for investigating large quantities of categorical data », Applied Statistics, 29(2), pp. 119-127, 1980.
