Mundel Fleming

n. Plusieurs feuilles peuvent être affectées à un même groupe. Chaque feuille est caractérisé par la conjonction des conditions correspondant aux coupures successives qui définissent le chemin conduisant à cette feuille.

11

Applications typiques

Comprendre les critères prépondérants pour l’achat d’u produit ou d’un service Isoler les critères explicatifs d’un comportement d’achat Analyse de risque: détecter les facteurs prédisant un comportement de non paiement Détecter les causes de réclamation

12

Algorithme de construction

13

14

Construction d’un arbre de décision

Démarrer avec un arbre vide et construire l’arbre de manière inductive et descendante Critères d’arrêt : échantillon pur plus d’attributs a tester

Algorithme de construction

Procédure : construire-arbre(X) Si tous les points de X appartiennent au même groupe alors créer une feuille portant le nom de ce groupe sinon choisir le meilleur attribut pour créer un nœud Le test associé à ce nœud sépare X en parties : Xg et Xd construire-arbre (Xg) construire-arbre (Xd) Fin si

15

16

Pour chaque nœud, déterminer :

Un critère de coupure : attribut + test Une mesure de la qualité de la coupure afin de subdiviser au mieux à chaque pas Un critère d’arrêt de la construction de l’arbre Une règle d’affectation de chaque feuille

Définition de la coupure :

Si l’attribut est binaire :

La branche gauche = la réponse « oui » La branche droite = la réponse « non »

Si l’attribut est quantitatif, une coupure est définie par le choix de l’attribut xj et d’un seuil c.

La branche gauche = « xj ≤ c » La branche droite = « xj > c »

Si l’attribut est qualitatif ordonné à m modalités, il y a m – 1 seuils possibles pour un découpage en 2 Si l’attribut est qualitatif nominal à m modalités, il y a 2m – 1 possibilités de découpage en 2

17

Choix du meilleur attribut

La quasi-totalité des méthodes d’induction d’arbres s’appuient sur le même procédé : Pour chaque variable candidate, on réalise le partitionnement des observations et on calcule un indicateur de qualité La variable retenue est celle qui optimise cet indicateur. Les méthodes diffèrent selon l’indicateur utilisé.

18

Mesures d’homogénéité des nœuds

19

20

Notations relatives au nœud t :

J groupes à discriminer n(t) = nombre d’individus au nœud t nk(t) = nombre d’individus du groupe k au nœud t

Mesures d’impureté ou d’hétérogénéité d’un nœud

Indice de diversité de Gini du nœud t

I(t) = ∑

Méthode CART

n k (t) ⎛ n k (t) ⎞ ⎜1 − ⎟ n(t) ⎠ k =1 n(t) ⎝

J

n(t) = ∑ n k (t)

k =1

J

t n1(t) ; … ; nJ(t) tg n1(tg) ; … ; nJ(tg) td n1(td) ; … ; nJ(td)

Entropie de Shannon du nœud t

H(t) = −∑

Méthode C4.5

⎛ n (t) ⎞ n k (t) log ⎜ k ⎟ k =1 n(t) ⎝ n(t) ⎠

J

n(t) = n(tgauche) + n(tdroite)

Toute mesure d’impureté est minimum si le nœud est pur maximum si le mélange est parfait

21

22

Gain d’homogénéité apporté par un nœud

Soit un nœud t divisé en m sous-nœud tj Soit I(tj) les mesures d’hétérogénéité (entropie, Gini…) des sous-nœuds Soit p(tj) les proportions des éléments de t dirigés vers tj le gain d’homogénéité apporté par le nœud t est G(t) = I(t)- ∑ p(t j ) × I(t j )

j

Exemple :

À chaque nœud, choix du test maximisant le gain

23

24

Exemple : Calcul de l’indice de diversité de Gini (méthode CART)

Impureté de l’arbre

L’arbre T est caractérisé par l’ensemble de ses nœuds terminaux L’impureté de l’arbre T de nœuds terminaux T est : n(t) I(T) = ∑ i(t) où N est le nombre total d'individus N t∈T Remarque : Si T’ est issu de T après une coupure à partir du nœud t en 2 nœuds tg et td, la diminution de l’impureté entre T et T’ est

n(t g ) ⎡ ⎤ n(t) n(t d ) I(T) − I(T ') = ⎢i(t) − i(t g ) − i(t d ) ⎥ n(t) n(t) ⎣ ⎦ N

25

26

Utilisation de l’impureté dans l’algorithme de construction de l’arbre

Minimiser l’impureté à chaque coupure = minimiser l’impureté totale de l’arbre Donc l’algorithme détermine, pour chaque variable, le test qui minimise l’impureté puis parmi tous les couples (variable, test), il choisit celui qui minimise l’impureté

Mesure de liaison statistique entre la variable définissant les groupes et l’attribut candidat

Pour évaluer la pertinence d’un attribut dans la segmentation, la méthode CHAID utilise le Khi-2 normalisé par le nombre de degrés de libertés : Le t de Tschuprow varie entre 0 et 1.

t2 =

χ2 n (a − 1)(b − 1)

où a et b sont les nombres de modalités des variables

27

Exemple : Calcul du t de Tschuprow (méthode CHAID)

Règles de décision

28

29

30

Règle d’affectation d’un nœud

p(j/t) =

n j (t) n(t)

Qualité de la règle de décision

Pour mesurer la qualité de la règle de décision, on évalue la probabilité de mauvais classements du nœud t

Le nœud t est affecté au groupe j ⇔ p(j/t) ≥ p (k/t) quel que soit k = 1, …, J Affecter à la feuille le groupe le plus représenté minimise la probabilité de mauvaise affectation sous 2 conditions :

les données constituent un échantillon représentatif de la population les coûts de mauvaise affectation sont unitaires (toutes les mauvaises affectations coûtent 1).

r(t) = ∑ p(k / t)

k≠ j

Ce taux évalue le taux apparent de mauvais classements du nœud t

Si les coûts de mauvaise affectation ne sont pas symétriques, la règle devient : minimiser le coût moyen de mauvaise affectation.

31

32

Taux apparent de mauvais classements de l’arbre

Pour l’arbre T de nœuds terminaux T, le taux de mauvais classements total est

R(T) = ∑ r(t)p(t)

t∈T

Exemple :

Arbre A

G1 : 600 G2 : 600

Arbre B

G1 : 600 G2 : 600

avec p(t) =

n(t) N

G1 : 450 G2 : 150

G1 : 150 G2 : 450

G1 : 300 G2 : 600

G1 : 300 G2 : 0

Affecté à G1

Affecté à G2

Affecté