""" Corso Machine Learning Engineer - Modulo 03, Lezione 5 "Alberi decisionali: come si sceglie una domanda con Gini ed entropia" OBIETTIVO DI QUESTO FILE ------------------------ Tre esercizi su un dominio nuovo rispetto all'articolo: il triage dei ticket di assistenza di un gestionale. Cento ticket arrivati in un giorno, di cui 80 sono "richiesta di informazioni" e 20 sono "bug reale". L'albero deve imparare a riconoscere i 20. 1. le due misure di impurità, scritte da zero: Gini ed entropia su conteggi di classe; 2. il guadagno di una domanda, e un caso - raro e per questo istruttivo - in cui GINI ED ENTROPIA SCELGONO DOMANDE DIVERSE sugli stessi dati. Non è un errore di arrotondamento: è la prova che il criterio è una scelta; 3. perché il guadagno di informazione premia le colonne con troppi valori distinti (l'id del ticket ha il guadagno massimo possibile) e come il rapporto di guadagno lo smonta. COME SI USA ----------- python3 esercizi.py Il file gira anche così com'è: stampa quali esercizi mancano ancora. AMBIENTE DICHIARATO ------------------- Python 3.12+ e NumPy 2.3. Nessun altro pacchetto. python3 -m venv .venv && source .venv/bin/activate pip install "numpy>=2.0" Tutti e tre gli esercizi sono DETERMINISTICI: nessun numero casuale. Ogni valore atteso in fondo al file si ricava con carta, penna e i logaritmi in base 2 di 3, 5 e 9. """ import numpy as np # ---------------------------------------------------------------------- # I dati: cento ticket, due classi. # # classe 0 = "richiesta di informazioni" 80 ticket # classe 1 = "bug reale" 20 ticket # # Due domande candidate per la radice dell'albero. Entrambe sono domande vere # che un team di assistenza si pone davvero. # # DOMANDA A - "il ticket arriva dalla chat del prodotto?" # si' (60 ticket): 60 informazioni , 0 bug # no (40 ticket): 20 informazioni , 20 bug # # DOMANDA B - "il ticket contiene un allegato?" # no (90 ticket): 80 informazioni , 10 bug # si' (10 ticket): 0 informazioni , 10 bug # # Una isola un gruppo puro di 60 "informazioni"; l'altra isola un gruppo puro # di 10 "bug". Quale conviene? Dipende dalla misura, e qui si vede. # ---------------------------------------------------------------------- PADRE = np.array([80, 20]) DOMANDA_A = [np.array([60, 0]), np.array([20, 20])] DOMANDA_B = [np.array([80, 10]), np.array([0, 10])] # ---------------------------------------------------------------------- # ESERCIZIO 1 - Le due misure di impurità # # Dato un vettore di conteggi di classe, calcola: # # Gini = 1 - somma_k p_k^2 # entropia = - somma_k p_k * log2(p_k) con la convenzione 0*log0 = 0 # # dove p_k è la frazione della classe k nel nodo. # # Domanda: quale delle due vale più in un nodo 50/50? E quanto valgono # entrambe in un nodo puro? # ---------------------------------------------------------------------- def impurita(conteggi, misura): """Impurita' di un nodo, dai conteggi di classe. Parametri --------- conteggi : np.ndarray di interi non negativi, uno per classe. misura : "gini" oppure "entropia". Ritorna ------- float, oppure None se l'esercizio non è ancora svolto. Due casi limite obbligatori, perché nell'albero si presentano a ogni foglia: - nodo vuoto (tutti i conteggi a zero): restituisci 0.0, non un nan; - classe assente (p_k = 0): il suo contributo all'entropia è 0, non -inf. In NumPy, `0 * np.log2(0)` vale `nan`, non 0: devi filtrare le probabilità nulle a mano, con `p = p[p > 0]`. È la trappola numero uno di questa lezione, e non da' nessun messaggio d'errore utile. """ # TODO (esercizio 1): sostituisci `return None` con il calcolo. return None # ---------------------------------------------------------------------- # ESERCIZIO 2 - Il guadagno di una domanda # # Il guadagno è l'impurità del padre meno la media PESATA dell'impurità dei # figli, dove il peso di ciascun figlio è la quota di esempi che vi finiscono: # # guadagno = I(padre) - somma_figli ( n_figlio / n_padre ) * I(figlio) # # Calcolalo per le due domande, con entrambe le misure, e confronta. # # Domanda: le due misure scelgono la stessa domanda? # ---------------------------------------------------------------------- def guadagno(conteggi_figli, misura): """Riduzione di impurità prodotta da una divisione. Parametri --------- conteggi_figli : lista di np.ndarray, un vettore di conteggi per figlio. misura : "gini" oppure "entropia". Ritorna ------- float, oppure None se l'esercizio non è ancora svolto. Il padre si ricostruisce sommando i figli: non va passato. È anche un controllo gratuito di coerenza, perché se la somma dei figli non torna, la divisione ha perso o duplicato esempi. """ # TODO (esercizio 2): sostituisci `return None` con il calcolo. return None # ---------------------------------------------------------------------- # ESERCIZIO 3 - La colonna che vince sempre, e non serve a niente # # Fra le colonne della tabella dei ticket c'è `id_ticket`: cento valori # distinti su cento righe. Dividere su quella colonna produce cento figli da un # esempio ciascuno: tutti puri, impurità zero, guadagno MASSIMO. E un modello # inutile, perché su un ticket nuovo quell'id non è mai stato visto. # # Il rimedio di Quinlan (C4.5) è dividere il guadagno per quanto la divisione # è "larga", misurata come l'entropia della distribuzione dei figli: # # informazione_di_split = - somma_figli ( n_figlio/n ) * log2( n_figlio/n ) # rapporto_di_guadagno = guadagno / informazione_di_split # # Scrivi l'informazione di split e confronta i rapporti di guadagno. # # Domanda: quanto vale l'informazione di split per cento figli da uno? # ---------------------------------------------------------------------- def informazione_di_split(conteggi_figli): """Entropia della distribuzione delle DIMENSIONI dei figli. Non guarda le classi: guarda solo quanti esempi finiscono in ciascun ramo. Una divisione binaria bilanciata vale 1 bit; una divisione in cento rami da un esempio vale log2(100) bit. Ritorna ------- float, oppure None se l'esercizio non è ancora svolto. """ # TODO (esercizio 3): sostituisci `return None` con il calcolo. return None def divisione_su_id(n_esempi, conteggi_padre): """Costruisce la divisione patologica: un figlio per ogni id. Già pronta. Distribuisce gli esempi del padre in `n_esempi` figli da uno, rispettando le proporzioni delle classi. Ogni figlio è puro per costruzione. """ figli = [] for classe, quanti in enumerate(conteggi_padre): for _ in range(int(quanti)): v = np.zeros(len(conteggi_padre), dtype=int) v[classe] = 1 figli.append(v) assert len(figli) == n_esempi return figli # ---------------------------------------------------------------------- # Runner # ---------------------------------------------------------------------- def _sezione(titolo): print() print(titolo) print("-" * len(titolo)) def _da_fare(numero): print(f" [ ] Esercizio {numero} non ancora svolto: completa il TODO qui sopra.") def esegui_esercizio_1(): _sezione("Esercizio 1 - Gini ed entropia") casi = [ ("padre, 80/20", PADRE), ("nodo 50/50", np.array([50, 50])), ("nodo puro", np.array([37, 0])), ("nodo vuoto", np.array([0, 0])), ("tre classi 1/1/1", np.array([10, 10, 10])), ] for nome, conteggi in casi: g = impurita(conteggi, "gini") e = impurita(conteggi, "entropia") if g is None or e is None: _da_fare(1) return False print(f" {nome:<18} conteggi {str(conteggi):<14}" f" Gini {g:.6f} entropia {e:.6f}") print(" Gini sta tra 0 e 1-1/K, l'entropia tra 0 e log2(K): due scale") print(" diverse, quindi i loro guadagni NON si confrontano tra loro.") return True def esegui_esercizio_2(): _sezione("Esercizio 2 - quale domanda mettere nella radice") if impurita(PADRE, "gini") is None: print(" [ ] Serve prima l'esercizio 1: il guadagno usa l'impurità.") return False for misura in ("gini", "entropia"): i_padre = impurita(PADRE, misura) g_a = guadagno(DOMANDA_A, misura) g_b = guadagno(DOMANDA_B, misura) if g_a is None or g_b is None: _da_fare(2) return False vincente = "A (canale chat)" if g_a > g_b else "B (allegato)" print(f" {misura:<9} I(padre) = {i_padre:.6f}") print(f" domanda A -> guadagno {g_a:.6f}") print(f" domanda B -> guadagno {g_b:.6f}" f" vince: {vincente}") print(" Le due misure scelgono domande DIVERSE. Gini premia la domanda") print(" che rende quasi puro il ramo GRANDE; l'entropia premia quella che") print(" abbassa di più l'incertezza media, e la sua pendenza vicino alle") print(" distribuzioni estreme è più ripida. Nessuna delle due è") print(" sbagliata: il criterio è un iperparametro, da validare.") return True def esegui_esercizio_3(): _sezione("Esercizio 3 - la colonna id_ticket") per_id = divisione_su_id(100, PADRE) candidate = [ ("domanda A (2 rami)", DOMANDA_A), ("domanda B (2 rami)", DOMANDA_B), ("id_ticket (100 rami)", per_id), ] if impurita(PADRE, "entropia") is None: print(" [ ] Serve prima l'esercizio 1.") return False print(" divisione | guadagno | info di split | rapporto") for nome, figli in candidate: g = guadagno(figli, "entropia") s = informazione_di_split(figli) if g is None or s is None: _da_fare(3) return False rapporto = g / s if s > 0 else float("inf") print(f" {nome:<22} | {g:8.6f} | {s:13.6f} | {rapporto:8.6f}") print(" Il guadagno grezzo incorona id_ticket: azzera l'impurità perché") print(" memorizza il dataset. Il rapporto di guadagno la retrocede") print(" all'ultimo posto, perché la penalizza per quanto è larga.") print(" Nota pratica: scikit-learn non implementa il rapporto di guadagno;") print(" usa divisioni binarie e si difende con min_samples_leaf e") print(" max_features. La difesa vera resta una: togliere dalla tabella le") print(" colonne che sono identificatori.") return True def main(): print("Corso MLE - Modulo 03, Lezione 5 - esercizi di codice") fatti = sum(bool(f()) for f in (esegui_esercizio_1, esegui_esercizio_2, esegui_esercizio_3)) print() print(f"Esercizi completati: {fatti} su 3.") if fatti < 3: print("Completa i TODO e rilancia: python3 esercizi.py") if __name__ == "__main__": main() # ====================================================================== # SOLUZIONI DI RIFERIMENTO # ====================================================================== # # --- Esercizio 1 ------------------------------------------------------- # def impurita(conteggi, misura): # conteggi = np.asarray(conteggi, dtype=float) # totale = conteggi.sum() # if totale == 0: # return 0.0 # p = conteggi / totale # p = p[p > 0] # qui si evita il nan di 0*log(0) # if misura == "gini": # return float(1.0 - np.sum(p ** 2)) # if misura == "entropia": # return float(-np.sum(p * np.log2(p))) # raise ValueError(f"misura sconosciuta: {misura}") # # Atteso: # padre 80/20 Gini 1 - 0.64 - 0.04 = 0.320000 # entropia 0.8*log2(1/0.8) + 0.2*log2(1/0.2) # = 0.8*0.321928 + 0.2*2.321928 = 0.721928 # nodo 50/50 Gini 0.500000 entropia 1.000000 # nodo puro Gini 0.000000 entropia 0.000000 # nodo vuoto Gini 0.000000 entropia 0.000000 # tre classi Gini 1 - 3*(1/9) = 0.666667 entropia log2(3) = 1.584963 # Il massimo di Gini con K classi è 1 - 1/K; quello dell'entropia è log2(K). # Sono due scale diverse: 0.5 di Gini e 1.0 di entropia descrivono lo stesso # nodo 50/50. Per questo i guadagni non si confrontano tra misure, solo tra # domande a misura fissata. # # --- Esercizio 2 ------------------------------------------------------- # def guadagno(conteggi_figli, misura): # figli = [np.asarray(c, dtype=float) for c in conteggi_figli] # padre = np.sum(figli, axis=0) # n = padre.sum() # if n == 0: # return 0.0 # pesata = sum((f.sum() / n) * impurita(f, misura) for f in figli) # return float(impurita(padre, misura) - pesata) # # Atteso, e questo è il cuore dell'esercizio: # # GINI (I(padre) = 0.320000) # domanda A: figlio (60,0) -> 0 ; figlio (20,20) -> 0.5 # pesata = 0.6*0 + 0.4*0.5 = 0.200000 # guadagno = 0.320000 - 0.200000 = 0.120000 # domanda B: figlio (80,10) -> 1 - (8/9)^2 - (1/9)^2 = 1 - 0.790123 # - 0.012346 = 0.197531 ; figlio (0,10) -> 0 # pesata = 0.9*0.197531 = 0.177778 # guadagno = 0.320000 - 0.177778 = 0.142222 # Gini preferisce B. # # ENTROPIA (I(padre) = 0.721928) # domanda A: figli -> 0 e 1.0 ; pesata = 0.4*1.0 = 0.400000 # guadagno = 0.721928 - 0.400000 = 0.321928 # domanda B: figlio (80,10): H = (8/9)*log2(9/8) + (1/9)*log2(9) # = 0.888889*0.169925 + 0.111111*3.169925 # = 0.151045 + 0.352214 = 0.503258 # pesata = 0.9*0.503258 = 0.452932 # guadagno = 0.721928 - 0.452932 = 0.268996 # L'entropia preferisce A. # # Due criteri, due radici diverse, stessi dati. Il caso è costruito ma non # artificiale: succede quando una domanda isola un gruppo puro PICCOLO (B # isola 10 bug) e l'altra rende quasi puro un gruppo GRANDE (A isola 60 # informazioni). L'entropia, che cresce molto rapidamente appena una classe # compare, premia l'abbattimento dell'incertezza media; Gini, che è una # parabola, premia la massa resa omogenea. # Conseguenza operativa: `criterion` non è un dettaglio estetico. Se due # alberi addestrati con criteri diversi danno risultati diversi in validazione, # è normale, e la scelta si fa con la validazione come ogni iperparametro. # # --- Esercizio 3 ------------------------------------------------------- # def informazione_di_split(conteggi_figli): # dimensioni = np.array([np.asarray(c).sum() for c in conteggi_figli], # dtype=float) # n = dimensioni.sum() # if n == 0: # return 0.0 # q = dimensioni / n # q = q[q > 0] # return float(-np.sum(q * np.log2(q))) # # Atteso: # domanda A : guadagno 0.321928 ; info di split H(0.6, 0.4) = 0.970951 ; # rapporto = 0.331512 # domanda B : guadagno 0.268996 ; info di split H(0.9, 0.1) = 0.468996 ; # rapporto = 0.573560 # id_ticket : guadagno 0.721928 (azzera tutta l'entropia del padre: # ogni figlio è puro) ; info di split = log2(100) = 6.643856 ; # rapporto = 0.108659 # # Classifica col guadagno grezzo: id_ticket (0.7219) > A (0.3219) > B (0.2690). # Classifica col rapporto: B (0.5736) > A (0.3315) > id_ticket (0.1087). # La colonna più inutile del dataset passa dal primo all'ultimo posto. # Dettaglio dei conti a mano: H(0.9, 0.1) = 0.9*log2(10/9) + 0.1*log2(10) # = 0.9*0.152003 + 0.1*3.321928 = 0.136803 + 0.332193 = 0.468996. # E log2(100) = 2*log2(10) = 6.643856.