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 CHAID –

Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 1 CHAID – CART – C4.5 et les autres… Ricco RAKOTOMALALA Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 2 Mesures d’Evaluation de la Segmentation -- Impact • Mesures statistiques • Mesures issues de la théorie de l’information Regroupement des modalités • 1 modalité = 1 branche • Arbre Binaire • Arbre m-aire Détermination de la taille « optimale » • Pré-pruning • Post-pruning Autres subtilités : coûts, graphes, arbres obliques, arbres flous Différenciation des méthodes Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 3 Evaluer une segmentation -- Impact Comment les caractériser S1 : Maximalité Distribution « pure » dans les feuilles S2 : Minimalité Pas de modification des distributions S3 : Intermédiaire Modification des distributions, association de certaines valeurs de X avec celles de Y Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 4 Impact Mesures de liaison statistique – CHI-2 et ses normalisations (CHAID) ∑∑ = = ×       × − = K k L l l k l k kl n n n n n n n 1 1 . . 2 . . 2 χ n n y n n y y x x x X Y l K k kl k L l . . 1 1 / Σ Σ M L L M Tableau de calcul Caractériser : la connaissance de X améliore la connaissance des valeurs de Y Principe Comparer les valeurs observées avec les valeurs théoriques lorsque Y et X sont indépendants (produit des marges) CHI-2 varie entre 0 et +oo ( ) ( ) 1 1 2 2 − × − × = L K n t χ T de Tschuprow est une normalisation par les degrés de libertés. Il varie entre 0 et 1. Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 5 S1 : 1.0 Distribution enfant « pure » S2 : 0.0 Pas de modification des distributions S3 : 0.7746 Modification des distributions, association des valeurs de certaines valeurs de X avec celles de Y Impact Exemple pour le t de Tschuprow -- CHAID Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 6 Impact Théorie de l’information – Le gain informationnel (C4.5) Entropie de Shannon Quantité d’information pour connaître les valeurs de Y Entropie Conditionnelle Quantité d’information pour connaître les valeurs de Y Sachant les valeurs de X Gain d’entropie ∑ =       × − = K k k k n n n n Y E 1 . 2 . log ) ( ∑ ∑ = =         × − = L l K k l kl l kl l n n n n n n X Y E 1 1 . 2 . . log ) / ( Gain d’entropie normalisée Gain Ratio – Tenir compte de la distribution marginale de X ) / ( ) ( ) / ( X Y E Y E X Y G − = ) ( ) / ( ) ( ) / ( X E X Y E Y E X Y GR − = Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 7 S1 : 1.0 Distribution « pure » dans les feuilles S2 : 0.0 Pas de modification des distributions S3 : 0.5750 Modification des distributions, association des valeurs de certaines valeurs de X avec celles de Y Impact Exemple pour le gain ratio – C4.5 Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 8 Impact Indice de concentration (CART) Indice de Gini Concentration des valeurs de Y Indice de Gini conditionnel Concentration de Y sachant les valeurs de X Amélioration de la concentration ∑ =      − × − = K k k k n n n n Y I 1 . . 1 ) ( ∑ ∑ = =        − × − = L l K k l kl l kl l n n n n n n X Y I 1 1 . . . 1 ) / ( Indice de Gini = Entropie Quadratique On peut aussi interpréter D comme un gain informationnel Indice de Gini = Variance sur variables catégorielles On peut aussi interpréter D comme une variance inter-classes = variance totale – variance intra ) / ( ) ( ) / ( X Y I Y I X Y D − = Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 9 S1 : 0.5 Distribution « pure » dans les feuilles S2 : 0.0 Pas de modification des distributions S3 : 0.3 Modification des distributions, association des valeurs de certaines valeurs de X avec celles de Y Impact Exemple pour l’indice de Gini – CART Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 10 Impact -- Le rôle de la normalisation Éviter la fragmentation des données – La propriété de Fusion des mesures Y / X1 A1 B1 C1 D1 Total positif 2 3 6 3 14 CHI-2 3.9796 négatif 4 4 8 0 16 T Tschuprow 0.0766 Total 6 7 14 3 30 Segmentation en 4 modalités avec la variable X1 Y / X2 A2 B2 D2 Total positif 2 9 3 14 CHI-2 3.9796 négatif 4 12 0 16 T Tschuprow 0.0938 Total 6 21 3 30 Segmentation en 3 modalités avec la variable X2 • Le t de Tschuprow normalise le CHI-2 • Le Gain Ratio normalise le gain informationnel • Le Gain de Gini n’est pas normalisé (mais on s’affranchit autrement de cette limitation dans CART) Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 11 Regroupement des modalités 1 modalité = 1 branche de l’arbre – C4.5 TYPELAIT ={2%MILK} TYPELAIT ={NOMILK} TYPELAIT ={POWDER} TYPELAIT ={SKIM} TYPELAIT ={WHOLEMILK} 50( 21%) 38( 16%) 153( 63%) 241(100%) 28( 17%) 24( 15%) 109( 68%) 161( 67%) 4( 31%) 1( 8%) 8( 62%) 13( 5%) 1(100%) 0( 0%) 0( 0%) 1( 0%) 1( 9%) 5( 45%) 5( 45%) 11( 5%) 16( 29%) 8( 15%) 31( 56%) 55( 23%) • Simplicité du calcul et d’interprétation • Danger de fragmentation, surtout sur les petits effectifs • Arbres « larges » • La mesure est chargée de favoriser les variables ayant peu de modalités Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 12 Regroupement des modalités L’arbre binaire -- CART • Regroupement de manière à optimiser l’impact • Moins de fragmentation • Arbres « profonds » • La binarisation compense l’absence de normalisation du gain de Gini • La binarisation n’est pas toujours pertinente TYPELAIT ={2%MILK,SKIM} TYPELAIT ={NOMILK,WHOLEMILK,PO... 49( 21%) 34( 15%) 145( 64%) 228(100%) 29( 18%) 26( 16%) 109( 66%) 164( 72%) 20( 31%) 8( 13%) 36( 56%) 64( 28%) Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 13 Regroupement des modalités L’arbre m-aire -- CHAID • Regroupement des feuilles ayant le même « profil » • Moins de fragmentation • Difficulté à régler le paramètre de fusion TYPELAIT ={2%MILK} TYPELAIT ={NOMILK,WHOLEMILK,PO... TYPELAIT ={SKIM} 50( 21%) 38( 16%) 153( 63%) 241(100%) 28( 17%) 24( 15%) 109( 68%) 161( 67%) 21( 30%) 9( 13%) 39( 57%) 69( 29%) 1( 9%) 5( 45%) 5( 45%) 11( 5%) Principe : test d’équivalence distributionnelle Fusionner les feuilles issues de la segmentation Tant que les profils ne sont pas significativement différents NoMilk, Powder WholeMilk High 5 16 Low 1 8 Normal 8 31 Total 14 55 ( ) ( ) ( ) 6309 . 0 31 8 55 / 31 14 / 8 8 1 55 / 8 14 / 1 16 5 55 / 16 14 / 5 55 14 2 2 2 2 =       + − + + − + + − × × = χ 73 . 0 value p )] 1 2 ( ) 1 3 [( 2 = − − × − χ Fusion si (p-value > probabilité critique pour la fusion) Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 14 Détermination de la taille de l’arbre Arbitrage biais - variance Biais : (in)capacité à retraduire des fonctions / concepts « complexes » Variance : dépendance au fichier d’apprentissage Arbre sous-dimensionné 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0 5 0 100 15 0 200 25 0 A pprentis s age Tes t Arbre « optimal » Arbre sur-dimensionné Equipe de recherche en Ingénierie des Connaissances Laboratoire ERIC 15 Détermination de la taille de l’arbre Pre-pruning Critères empiriques • Effectifs sur les nœuds et les feuilles : taille limite avant la segmentation et effectif d’admissibilité • Pureté des feuilles : seuil de spécialisation • Taille de l’arbre Critères statistiques -- CHAID • Test d’indépendance du CHI-2 Simples mais difficiles à déterminer (essais et tâtonnements, dépendant de la taille de la base et du domaine d’étude) Difficile de déterminer un niveau de signification optimal (à fixer très bas à mesure que la taille de la base augmente) Dans la pratique, ça marche quand même : • la uploads/Science et Technologie/ arbres-decision-cart-chaid-c45.pdf