Arbre de Decision

Objectif: Maitriser les calculs d'un arbre de decision a la main (Gini, gain d'information, split).

Prenez une feuille et un stylo. Resolvez chaque partie AVANT de regarder la solution !

CONTEXTE

Vous devez construire un arbre de decision pour predire si un email est SPAM ou HAM.

Vous avez 10 emails avec 2 features :

Resume : 5 SPAM, 5 HAM

Formule de l'indice de Gini : $Gini = 1 - \sum_{i} p_i^2$

PARTIE 1 : Gini du noeud racine

1.1) Calculez les proportions de chaque classe (SPAM et HAM)

1.2) Calculez l'indice de Gini du noeud racine

1.3) Que signifie cette valeur ? (0 = pur, 0.5 = maximum d'impurete)

PARTIE 2 : Split sur "Mots majuscules"

Si on split sur "Mots majuscules" :

• Branche "Beaucoup" : emails 1, 2, 3, 9 (4 emails)
• Branche "Peu" : emails 4, 5, 6, 7, 8, 10 (6 emails)

2.1) Combien de SPAM et HAM dans chaque branche ?

2.2) Calculez le Gini de la branche "Beaucoup"

2.3) Calculez le Gini de la branche "Peu"

2.4) Calculez le Gini pondere apres ce split

PARTIE 3 : Split sur "Contient gratuit"

Si on split sur "Contient gratuit" :

• Branche "Oui" : emails 1, 2, 4, 10 (4 emails)
• Branche "Non" : emails 3, 5, 6, 7, 8, 9 (6 emails)

3.1) Combien de SPAM et HAM dans chaque branche ?

3.2) Calculez le Gini de la branche "Oui"

3.3) Calculez le Gini de la branche "Non"

3.4) Calculez le Gini pondere apres ce split

PARTIE 4 : Choix du meilleur split

4.1) Quel split reduit le plus l'impurete ?

4.2) Calculez le gain d'information pour chaque split

4.3) Quel feature l'algorithme choisira pour le noeud racine ?

PARTIE 5 : Prediction

Un nouvel email a : Mots majuscules = "Beaucoup", Contient "gratuit" = "Non"

5.1) Si on utilise le split optimal, quelle sera la prediction ?

5.2) Avec quelle confiance (proportion de la classe majoritaire) ?

SOLUTION DETAILLEE

Prenez le temps de comparer avec vos reponses. Verifiez chaque etape !

RAPPEL : Formule de Gini

$$Gini = 1 - \sum_{i} p_i^2 = 1 - p_{SPAM}^2 - p_{HAM}^2$$

PARTIE 1 : Gini du noeud racine

1.1) Proportions :

• Total : 10 emails
• SPAM : 5 → $p_{SPAM} = \frac{5}{10} = \textcolor{#e74c3c}{0.5}$
• HAM : 5 → $p_{HAM} = \frac{5}{10} = \textcolor{#27ae60}{0.5}$

1.2) Gini du noeud racine :

$$Gini_{racine} = 1 - \textcolor{#e74c3c}{0.5}^2 - \textcolor{#27ae60}{0.5}^2 = 1 - 0.25 - 0.25$$

$\boxed{Gini_{racine} = \textcolor{#9B7AC4}{0.5}}$

1.3) Interpretation :

$Gini = 0.5$ est le maximum d'impurete possible pour 2 classes. Le noeud est parfaitement mixte (50/50).

PARTIE 2 : Split sur "Mots majuscules"

2.1) Composition des branches :

• Branche "Beaucoup" (4 emails) : emails 1, 2, 3, 9 → $\textcolor{#e74c3c}{4\ SPAM}$, $\textcolor{#27ae60}{0\ HAM}$
• Branche "Peu" (6 emails) : emails 4, 5, 6, 7, 8, 10 → $\textcolor{#e74c3c}{1\ SPAM}$, $\textcolor{#27ae60}{5\ HAM}$

2.2) Gini "Beaucoup" :

$$Gini_{Beaucoup} = 1 - \left(\frac{4}{4}\right)^2 - \left(\frac{0}{4}\right)^2 = 1 - 1 - 0$$

$\boxed{Gini_{Beaucoup} = \textcolor{#27ae60}{0} \text{ (pur !)}}$

2.3) Gini "Peu" :

$$Gini_{Peu} = 1 - \left(\frac{1}{6}\right)^2 - \left(\frac{5}{6}\right)^2 = 1 - 0.028 - 0.694$$

$\boxed{Gini_{Peu} = \textcolor{#e67e22}{0.278}}$

2.4) Gini pondere :

$$Gini_{split} = \frac{4}{10} \times \textcolor{#27ae60}{0} + \frac{6}{10} \times \textcolor{#e67e22}{0.278}$$

$$Gini_{split} = 0 + 0.167$$

$\boxed{Gini_{majuscules} = \textcolor{#3498db}{0.167}}$

PARTIE 3 : Split sur "Contient gratuit"

3.1) Composition des branches :

• Branche "Oui" (4 emails) : emails 1, 2, 4, 10 → $\textcolor{#e74c3c}{3\ SPAM}$, $\textcolor{#27ae60}{1\ HAM}$
• Branche "Non" (6 emails) : emails 3, 5, 6, 7, 8, 9 → $\textcolor{#e74c3c}{2\ SPAM}$, $\textcolor{#27ae60}{4\ HAM}$

3.2) Gini "Oui" :

$$Gini_{Oui} = 1 - \left(\frac{3}{4}\right)^2 - \left(\frac{1}{4}\right)^2 = 1 - 0.5625 - 0.0625$$

$\boxed{Gini_{Oui} = \textcolor{#e67e22}{0.375}}$

3.3) Gini "Non" :

$$Gini_{Non} = 1 - \left(\frac{2}{6}\right)^2 - \left(\frac{4}{6}\right)^2 = 1 - 0.111 - 0.444$$

$\boxed{Gini_{Non} = \textcolor{#e67e22}{0.444}}$

3.4) Gini pondere :

$$Gini_{split} = \frac{4}{10} \times \textcolor{#e67e22}{0.375} + \frac{6}{10} \times \textcolor{#e67e22}{0.444}$$

$$Gini_{split} = 0.15 + 0.267$$

$\boxed{Gini_{gratuit} = \textcolor{#F7E64D}{0.417}}$

PARTIE 4 : Choix du meilleur split

4.1) Comparaison des Gini apres split :

4.2) Gain d'information :

$$Gain = Gini_{avant} - Gini_{apres}$$

• Gain (majuscules) = $0.5 - 0.167 = \textcolor{#27ae60}{\mathbf{0.333}}$
• Gain (gratuit) = $0.5 - 0.417 = \textcolor{#e67e22}{0.083}$

4.3) Choix de l'algorithme :

$\boxed{\text{L'algorithme choisira "Mots majuscules" (gain = 0.333)}}$

Car ce split reduit le plus l'impurete.

PARTIE 5 : Prediction

Nouvel email : Mots majuscules = "Beaucoup", Contient "gratuit" = "Non"

5.1) Prediction :

• On suit le split "Mots majuscules"
• "Beaucoup" → branche gauche
• Cette branche contient 4 SPAM, 0 HAM
• Prediction : $\textcolor{#e74c3c}{\mathbf{SPAM}}$

5.2) Confiance :

$$Confiance = \frac{4}{4} = 100\%$$

$\boxed{\text{Prediction : SPAM avec 100\% de confiance}}$

RESUME DES RESULTATS

Legende des couleurs :

• $\textcolor{#e74c3c}{Rouge}$ : classe SPAM et proportions
• $\textcolor{#27ae60}{Vert}$ : classe HAM, Gini pur (0), meilleur gain
• $\textcolor{#9B7AC4}{Violet}$ : Gini racine (0.5)
• $\textcolor{#e67e22}{Orange}$ : Gini intermediaires
• $\textcolor{#3498db}{Bleu}$ : Gini final du meilleur split
• $\textcolor{#F7E64D}{Jaune}$ : Gini du split moins performant