Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 1 Ricco RA

Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 1 Ricco RAKOTOMALALA Ricco.Rakotomalala@univ-lyon2.fr Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 2 Arbres de décision – Apprentissage par partitionnement Objectif : on veut construire des sous-groupes les plus « homogènes » du point de vue de la variable à prédire La variable qualitative Y prend ses valeurs dans {+,-} Le sous-groupe Gi est complètement pur du point de vue de Y, il ne possède que des individus portant la valeur + de Y La description des sous-groupes repose sur : la fonction f et ses paramètres éventuels α les variables exogènes Xi ) ( alors ) ( si + = ∈ Y Gi ω Ωa Gi + + + + + + + + + + + ++ + + + + - - - - - - - - - L’idée est de trouver le plus rapidement Possible (avec le moins de variables) des groupes où P(Y=+) # 1 Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 3 Arbres de décision – Un exemple Numéro Infarctus Douleur Age Inanimé 1 oui poitrine 45 oui 2 oui ailleurs 25 oui 3 oui poitrine 35 non 4 oui poitrine 70 oui 5 oui ailleurs 34 non 6 non poitrine 60 non 7 non ailleurs 67 non 8 non poitrine 52 oui 9 non ailleurs 58 non 10 non ailleurs 34 non Y X 5 5 Infarctus = OUI Infarctus = NON Tableau des fréquences absolues, tous les individus sont présents 2 3 3 2 douleur ailleurs poitrine Les individus qui ont une douleur dans la poitrine, numéros {1,3,4,6,8} {2,5,7,9,10} 1 2 2 0 1 3 1 0 âge ≤48.5 > 48.5 inanimé {1,3} {4,6,8} {2} {5,7,9,10} oui non Premier sous-groupe, complètement homogène du point de vue de la variable à prédire : il est constitué exclusivement d ’individus qui ont un infarctus A résoudre : • choix de la variable de segmentation • traitement des variables continues • règle d’arrêt dans la construction • décision sur une feuille Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 4 Arbres de décision – Choix de la variable de segmentation On choisit la variable X* telle qu ’elle est la plus liée (corrélée) avec Y on utilise la quantité du χ² calculée sur le tableau de contingence (croisement de Y avec Xi) pour quantifier cette liaison { } K l i i k a l k L i i Y X X et Y Y card n Y x x i ) ) ( ) ( / ( , , 1 , 1 , = = Ω ∈ = ω ω ω M L i X Y p i X , 2 , , 1 * max arg χ K = = Amélioration : la mesure du χ² augmente avec n, l ’effectif sur le nœud à segmenter le nombre de lignes le nombre de colonnes Ces valeurs sont constantes dans les comparaisons deux à deux du χ² Les variables qui ont beaucoup de modalités (et ainsi induisent beaucoup de colonnes dans le tableau de contingence) sont avantagés ) 1 )( 1 ( ² , , − − = i X Y L K n t i X Y i χ (le t de Tschuprow varie entre 0 et 1) Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 5 Arbres de décision – Traitement des variables continues Comment est réalisé le choix du point de coupure (ex: d ’où vient la valeur 48.5 de découpage de l ’âge dans l ’arbre exemple) Point de coupure : borne de discrétisation il doit toujours être situé entre deux points consécutifs sur l ’axe de la variable quantitative il permet de définir un tableau de contingence âge 35 O O 45 70 O N 60 52 N Points de coupures candidats Définit le tableau de contingence 48.5 40 40 , 2 2 0 . 2 1 . 40 40 < = = ≥ < Age Infarctus non Inf oui Inf age age χ 5 . 48 , 2 2 0 . 1 2 . 5 . 48 5 . 48 < = = ≥ < Age Infarctus non Inf oui Inf age age χ ... Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 6 Arbres de décision – Règle d’arrêt Quand décider qu’un sommet devient une feuille ? Homogénéité des groupes : critère de précision (confiance) Pureté d’un sommet Seuil de spécialisation (ex. si une classe est représentée à 98% -> stop) Effectif des groupes : critère de support Taille minimale pour segmenter (ex. en dessous de 10 obs, on ne segmente plus) Effectif d’admissibilité (ex. si un des sommets produit couvre moins de 2 obs. -> refus) Test d’indépendance du CHI-2 : démarche statistique      * 1 * 0 avec lié est : ts indépendan : X Y H X et Y H Comment fixer le risque du test ? L’idée est surtout de contrôler la profondeur de l’arbre ! Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 7 Arbres de décision – Avantages et inconvénients Avantages : • connaissances « intelligibles » -- validation d’expert • traduction directe de l’arbre vers une base de règles • sélection automatique des variables pertinentes • non paramétrique • traitement indifférencié selon le type des variables • robuste face aux données aberrantes • rapidité intéressante sur des bases de taille moyenne • possibilité pour le praticien d’intervenir dans la construction Inconvénients : • problème de stabilité sur les petites bases de données • recherche « pas-à-pas » : difficulté à trouver les interactions • temps de traitement dès que la base ne tient plus en mémoire Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 8 Bibliographie : arbres de décision • « Arbres de Décision », R. Rakotomalala, Revue MODULAD, 33:163-187, 2005 (http://www.modulad.fr/). Le point sur les méthodes • « Graphes d’Induction », D. Zighed et R. Rakotomalala, Hermès, 2000. Encyclopédique, description approfondie des méthodes • « Classification and Regression Tree », L. Breiman, J. Friedman, R. Olshen et C. Stone, 1984. « La » bible – Très peu accessible malheureusement mais d’une très grande richesse uploads/Science et Technologie/ arbres-de-decision-introduction.pdf