Esercizio - Albero di decisione ID3 sul dataset del tennis

Testo (slide della lezione sugli alberi). Dai 14 giorni della tabella (Outlook, Temperature, Humidity, Wind $\to$ Play Tennis; $9$ Yes e $5$ No):

1. Costruire l'albero ID3 con il guadagno d'informazione.
2. Classificare i giorni (Sunny, Cool, High, Strong), (Rain, Hot, Normal, Weak), (Overcast, Cool, High, Strong).
3. Ripetere la scelta della radice con l'indice di Gini.

Teoria usata: Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione → (entropia, guadagno d'informazione, Gini, ID3); logaritmi in base 2: Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →.

1. Albero con il guadagno d'informazione

Entropia della radice. $p_{\text{Yes}}=\frac9{14}=0{,}643$, $p_{\text{No}}=\frac5{14}=0{,}357$: $H=-0{,}643\log_20{,}643-0{,}357\log_20{,}357=0{,}643\cdot0{,}637+0{,}357\cdot1{,}485=0{,}410+0{,}530=0{,}940$.

Guadagno per ciascun attributo (media delle entropie dei figli pesata per le dimensioni):

(Verifica di un'entropia: $(2,3)$: $-\frac25\log_2\frac25-\frac35\log_2\frac35=0{,}4\cdot1{,}322+0{,}6\cdot0{,}737=0{,}529+0{,}442=0{,}971$.)

La radice è Outlook. Il ramo Overcast ha solo «Yes»: foglia Yes.

Ramo Sunny (giorni 1, 2, 8, 9, 11: 2 Yes, 3 No, $H=0{,}971$). Per Humidity: High $\to$ giorni 1, 2, 8: tutti No ($H=0$); Normal $\to$ giorni 9, 11: tutti Yes ($H=0$): $IG=0{,}971-0=0{,}971$. Temperature darebbe $0{,}571$ (Hot: 0 Yes 2 No, $H=0$; Mild: 1 Yes 1 No, $H=1$; Cool: 1 Yes 0 No: media $\frac25\cdot0+\frac25\cdot1+\frac15\cdot0=0{,}4$, $IG=0{,}971-0{,}4=0{,}571$); Wind $0{,}020$. Si sceglie Humidity.

Ramo Rain (giorni 4, 5, 6, 10, 14: 3 Yes, 2 No). Per Wind: Weak $\to$ giorni 4, 5, 10: tutti Yes; Strong $\to$ giorni 6, 14: tutti No: $IG=0{,}971$ (massimo). Si sceglie Wind.

Outlook?
├── Sunny    -> Humidity? ( High -> No | Normal -> Yes )
├── Overcast -> Yes
└── Rain     -> Wind?     ( Weak -> Yes | Strong -> No )

Tutte le foglie sono pure: il training è classificato correttamente (accuracy $14/14=1$). Si ottiene lo stesso albero con l'implementazione ID3 del laboratorio.

2. Classificazione di nuovi giorni

• (Sunny, Cool, High, Strong): Outlook = Sunny $\to$ Humidity = High $\to$ No.
• (Rain, Hot, Normal, Weak): Outlook = Rain $\to$ Wind = Weak $\to$ Yes (la temperatura non viene mai usata).
• (Overcast, Cool, High, Strong): Outlook = Overcast $\to$ Yes.

Le regole sono immediatamente leggibili e usano solo tre attributi su quattro: Temperature non compare, perché una volta fissati Outlook e Humidity/Wind non aggiunge informazione.

3. Con l'indice di Gini

$\operatorname{Gini}(S)=1-(\tfrac9{14})^2-(\tfrac5{14})^2=1-0{,}413-0{,}128=0{,}459$. Gini ponderato dei figli:

• Outlook: Sunny $1-0{,}4^2-0{,}6^2=0{,}48$, Overcast $0$, Rain $0{,}48$: $\frac5{14}0{,}48+0+\frac5{14}0{,}48=0{,}343$ (riduzione $0{,}116$);
• Humidity: High $1-(\frac37)^2-(\frac47)^2=0{,}490$, Normal $1-(\frac67)^2-(\frac17)^2=0{,}245$: $0{,}5\cdot0{,}490+0{,}5\cdot0{,}245=0{,}367$;
• Wind: Weak $1-(\frac68)^2-(\frac28)^2=0{,}375$, Strong $0{,}5$: $\frac8{14}0{,}375+\frac6{14}0{,}5=0{,}429$;
• Temperature: Hot $0{,}5$, Mild $0{,}444$, Cool $0{,}375$: $\frac4{14}0{,}5+\frac6{14}0{,}444+\frac4{14}0{,}375=0{,}440$.

Il valore minimo è $0{,}343$ (Outlook): stessa radice dell'entropia. Con dati reali le due misure scelgono quasi sempre lo stesso attributo.

Verifica

import numpy as np
from collections import Counter
def H(ys):
    p = np.array(list(Counter(ys).values())) / len(ys); return -(p * np.log2(p)).sum()
# y = lista di 'Yes'/'No' per i 14 giorni; per ogni attributo A:
# IG = H(y) - sum(len(y_v)/len(y) * H(y_v) for y_v in sottoinsiemi per valore di A)
# risultati: Outlook 0.247, Humidity 0.152, Wind 0.048, Temperature 0.029