Vediamo ora un interessante algoritmo di classificazione che si distingue da quelli visti fin’ora.
Alberi decisionali
Dando per scontata la conoscenza della teoria degli alberi, facciamo un veloce ripasso di alcune nozioni base. Un albero, in informatica, è una struttura dati che va letta dall’alto verso il basso. Gli elementi che contengono le informazioni sono chiamati nodi. Le connessioni tra i nodi sono chiamati archi. Il nodo principale o di partenza è chiamato radice ed è caratterizzato dalla mancanza di archi in ingresso. I nodi terminali sono chiamati foglie e sono caratterizzati dalla mancanza di archi in uscita.
In figura sono rappresentati anche il significato di nodo padre, nodo figlio, nodo fratello, sotto-albero e livello, che non andiamo a specificare in dettaglio.
Detto questo, nel campo dell’intelligenza artificiale un albero decisionale o decision tree è un modello che utilizza una struttura dati ad albero per contenere le informazioni ed effettuare le predizioni. La loro natura è tale per cui risultano essere modelli meno “black-box” di altri, in quanto esplicitano negli archi e nei nodi le condizioni che generano la predizione.
Nella figura accanto è rappresentato un semplice albero decisionale di classificazione animale che si basa su due domande (poco accurato, visto che esistono mammiferi che depongono uova…).
Tutto molto bello, ma come fa un albero decisionale a decidere quali condizioni utilizzare per arrivare alla corretta classificazione? La scelta si basa sul guadagno di informazioni.
Prendiamo per esempio un dataset come quello in figura dove ci sono due classi (quadrati e stelle) e due proprietà.
Creando una condizione sulla proprietà 1 per un ipotetico valore 60, il dataset viene suddiviso in due sotto insiemi, ognuno con lo stesso numero di classi (7 quadrati e 7 stelle nel ramo di sinistra, 6 quadrati e 6 stelle nel ramo di destra). Non a caso la condizione è detta condizione di split.
In questo caso il guadagno di informazioni è nullo, perchè il numero delle due classi è identico, per ogni ramo. Quindi questo split risulta essere ininfluente ai fini della classificazione: sia prima che dopo questa condizione, il nostro dato in ingresso avrà comunque una probabilità del 50% di essere un quadrato o una stella.
Creando invece una condizione sulla proprietà 2 per il valore 70, ad esempio, il dataset viene suddiviso in due sottoinsiemi con conteggi diversi per le classi.
Quest’ultima condizione risulta essere più efficace nella ricerca della soluzione finale, in quanto esegue una sorta di pre-classificazione, ottenendo il cosiddetto guadagno di informazioni.
Per valutare la bontà del guadagno di informazioni, si utilizza una metrica chiamata impurità. Essa vale 0 quando una condizione genera un nodo con esempi associati ad un’unica classe. In questo caso si ha un nodo puro che sarà anche una foglia dell’albero.
L’addestramento del modello consisterà nel raggiungere le foglie dell’albero (nodi puri) utilizzando meno condizioni possibili.
L’impurità si può calcolare in vari modi, i più famosi sono il Gini e l’entropia. Senza addentrarci nella teoria, possiamo dire che i due metodi portano a risultati non troppo differenti tra loro, ma il Gini è solitamente meno pesante da calcolare.
Continuando a creare l’albero decisionale, il risultato sarebbe simile a quello in figura.
Come si può vedere, le linee tratteggiate che rappresentano le condizioni di split, consentono di classificare anche dataset particolarmente complessi che non sarebbe facile o sarebbe impossibile classificare con altri metodi.
A maggiore profondità dell’albero, corrisponde maggiore complessità del modello. Come abbiamo già avuto modo di vedere, in generale più un modello è complesso, più è facile mandarlo in overfitting. Quindi un altro obiettivo dell’addestramento sarà quello di generare alberi non troppo profondi.
Codice Python
NOTA: il codice di questo esempio lo trovi qui
Utilizziamo il dataset Indian Liver Patient, che è possibile scaricare da questo link (è comunque presente il file nel github di questo esempio). Il dataset contiene le informazioni mediche di 583 pazienti, con proprietà quali l’età, il sesso, i valori di bilirubina, eccetera ed una classificazione che indica se il paziente è stato sottoposto ad intervento al fegato oppure no. Il dataset scaricabile dal sito è privo dell’header delle colonne. Nel repository in github ho provveduto ad aggiungerla (le informazioni delle colonne sono comunque indicate nel sito di cui sopra).
Carichiamo quindi il dataset e diamo uno sguardo alle proprietà e alle prime righe dei dati.
# carico il dataset
indianLiver = pd.read_csv("./liver.csv")
print("Diamo uno sguardo alla struttura dati")
print(indianLiver.info())
print()
print("Diamo uno sguardo ai dati")
print(indianLiver.head())
print()
Diamo uno sguardo alla struttura dati
RangeIndex: 583 entries, 0 to 582
Data columns (total 11 columns):
AGE 583 non-null int64
GENDER 583 non-null object
TB 583 non-null float64
DB 583 non-null float64
ALK 583 non-null int64
SGPT 583 non-null int64
SGOT 583 non-null int64
TP 583 non-null float64
ALB 583 non-null float64
AG 579 non-null float64
LABEL 583 non-null int64
dtypes: float64(5), int64(5), object(1)
memory usage: 50.2+ KB
None
Diamo uno sguardo ai dati
AGE GENDER TB DB ALK SGPT SGOT TP ALB AG LABEL
0 65 Female 0.7 0.1 187 16 18 6.8 3.3 0.90 1
1 62 Male 10.9 5.5 699 64 100 7.5 3.2 0.74 1
2 62 Male 7.3 4.1 490 60 68 7.0 3.3 0.89 1
3 58 Male 1.0 0.4 182 14 20 6.8 3.4 1.00 1
4 72 Male 3.9 2.0 195 27 59 7.3 2.4 0.40 1
Tutti i campi tranne il sesso sono numerici. Il campo target LABEL è intero e contiene 1 se il paziente è stato operato o 2 se il paziente non è stato operato. Il campo target a questo punto possiamo lasciarlo così com’è (se volete, per esercizio potete provvedere a codificarlo nel solito 0 e 1 come abbiamo già visto negli articoli passati). Dobbiamo invece procedere a codificare il campo del sesso. Per farlo questa volta usiamo un altro metodo: invece di associare un valore numerico al valore Female e Male, splittiamo il campo in due campi dummy che contengono un flag booleano per l’appartenenza al genere femminile o maschile. Ovviamente lo facciamo sfruttando una funzione di Scikit-Learn.
# codifico le colonne non numeriche con delle colonne booleane dummy
# in questo caso la colonna "gender" verrà sostituita da due colonne
# "gender_female" e "gender_male" che indicheranno l'appartenenza al genere
indianLiver = pd.get_dummies(indianLiver)
print("Il dataset modificato con le colonne dummies del sesso")
print(indianLiver.head())
print()
Il dataset modificato con le colonne dummies del sesso
AGE TB DB ALK SGPT SGOT TP ALB AG LABEL GENDER_Female GENDER_Male
0 65 0.7 0.1 187 16 18 6.8 3.3 0.90 1 1 0
1 62 10.9 5.5 699 64 100 7.5 3.2 0.74 1 0 1
2 62 7.3 4.1 490 60 68 7.0 3.3 0.89 1 0 1
3 58 1.0 0.4 182 14 20 6.8 3.4 1.00 1 0 1
4 72 3.9 2.0 195 27 59 7.3 2.4 0.40 1 0 1
Procediamo come al solito suddividendo il dataset in un set di training ed in uno di test (utilizziamo un set di test dimensionato al 30% del dataset completo). Poi eseguiamo la classificazione utilizzando la classe DecisionTreeClassifier, indicando che vogliamo utilizzare l’algoritmo ‘gini’ per valutare l’impurità dei nodi. Da notare che per gli alberi decisionali non è necessario procedere con la standardizzazione o la normalizzazione dei dati. Anzi, per consentire una migliore lettura e comprensibilità delle condizioni prodotte nei vari nodi, è meglio toccare il meno possibile il dataset (fermo restando che alcune codifiche sono necessarie, come abbiamo appena visto).
# istanzio la classe di creazione di alberi decisionali, utilizzando l'algoritmo Gini per calcolare l'impurità
decTree = DecisionTreeClassifier(criterion="gini")
decTree.fit(X_train, Y_train)
Infine calcoliamo l’accuracy sia sul training set che sul test set. Visualizziamo anche la profondità massima dell’albero prodotto.
Uso l'algoritmo 'gini' per l'impurità
Profondità albero: 22
Accuracy train set: 1.0
Accuracy test set: 0.6206896551724138
Come vediamo il risultato è affetto da overfitting (il traininset è perfettamente rappresentato dall’albero, ma l’accuracy sul test set cala sensibilmente). Ora vediamo come è fatto il decision tree ottenuto. Uso la libreria graphviz che consente di creare un PDF con il disegno dell’albero.
NOTA: per utilizzare la libreria Python graphviz è necessario aver installato il programma Graphviz (lo trovate a questo link) e aver incluso nel path di sistema la directory bin del programma. La renderizzazione creerà due file: un file di testo con la descrizione testuale dell’albero (fungono da istruzioni per graphviz) e un file pdf con il grafico dell’albero.
# metto in grafica l'albero decisionale e creo un pdf
dot_data = export_graphviz(decTree, out_file=None,
feature_names=indianLiver.columns.drop("LABEL"))
graph = graphviz.Source(dot_data)
graph.render("liver_tree_gini", view=True)
Come vediamo, l’albero ha una profondità pari a 22 (la radice non viene considerata) e il grafico dimostra una certa complessità.
Facendo uno zoom sul grafico ottenuto, in ogni nodo possiamo vedere diverse righe informative (se avete pazienza, le vedrete più avanti):
- la condizione eseguita (e su quale proprietà del dataset viene applicata)
- la stima della impurità gini
- il numero di esempi del dataset contenuti nel nodo
- il numero di esempi per ogni classe contenuta nel nodo
Negli archi sono invece indicati i valori della condizione del nodo: essendo una condizione booleana, può valere solo True (arco uscente verso sinistra) o False (arco uscente verso destra).
Si nota che in questo caso l’albero porta a foglie pure, cioè nodi terminali con stima gini = 0.
Proviamo ora a ripetere il tutto usando però il metodo dell’entropia per valutare l’impurità dei nodi e analizziamo i risultati di accuracy e l’albero decisionale ottenuto.
# rifaccio usando l'entropia
decTree = DecisionTreeClassifier(criterion="entropy")
decTree.fit(X_train, Y_train)
Uso l'algoritmo 'entropy' per l'impurità
Profondità albero: 17
Accuracy train set: 1.0
Accuracy test set: 0.5862068965517241
Come vediamo, l’accuracy del nuovo decision tree è calata ulteriormente, anche se molto vicina a quella precedente: il modello resta comunque in overfitting.
Anche il grafico dell’albero è diverso, ma non è stravolto. In questo caso ha una profondità pari a 17. Nei nodi le informazioni sono le stesse, con la differenza che questa volta invece della stima gini sarà presente la stima entropy.
Anche in questo caso le foglie sono pure.
Modificando i parametri dell’istanza del classificatore, è possibile variare l’albero decisionale ottenuto. Ad esempio, riprendiamo il metodo gini e forziamo l’algoritmo a creare un albero limitando la massima profondità a 2 e vediamo cosa succede.
# rifaccio usando nuovamente Gini, ma limitando la profondità dell'albero
decTree = DecisionTreeClassifier(criterion="gini", max_depth=2)
decTree.fit(X_train, Y_train)
Uso l'algoritmo 'gini' per l'impurità e limito a 2 la profondità dell'albero
Profondità albero: 2
Accuracy train set: 0.7530864197530864
Accuracy test set: 0.7011494252873564
In questo caso il grafico dell’albero è decisamente semplificato, le foglie non sono più pure, il che significa che la classificazione non è perfetta.
Ma come vediamo dai valori di accuracy, il modello non è più in overfitting.
L’accuracy sul training set è diminuita (infatti le foglie non sono più pure), ma l’accuracy sul test set è aumentata. Ciò significa che questo albero, seppure semplificato, generalizza meglio, riuscendo a classificare meglio i dati in ingresso, in particolare per quei dati che non fanno parte del training set.
Una cosa molto interessante è la comprensibilità delle condizioni: mentre con altri metodi otteniamo una serie di pesi e bias che concorrono ad ottenere il risultato, qui abbiamo delle condizioni. Questo rende gli alberi decisionali ottimi strumenti non solo per la classificazione, ma anche per analizzare i comportamenti di alcuni sistemi. Ad esempio: se creiamo un dataset che contiene proprietà inerenti alla vendita di un negozio (età e sesso dell’acquirente, periodo dell’anno, marca del prodotto, prezzo, posizione nello scaffale, eccetera) e lo utilizziamo per generare un albero decisionale che consenta di capire se un prodotto è stato acquistato o meno, potremmo essere in grado di analizzare tutte le condizioni presenti sui nodi e capire meglio come avvengono le vendite. Questo ci consentirebbe eventualmente di trovare il modo di migliorare le vendite di alcuni prodotti, intervenendo su alcune proprietà (magari facendo risaltare diversamente il prodotto modificando la sua posizione nello scaffale o facendo delle promozioni per fasce d’età o sesso, eccetera).
Foreste casuali
Nel mondo reale che cos’è una foresta? Un insieme di alberi.
Nell’ambito dell’intelligenza artificiale che cos’è una foresta casuale (o random forest)? Un modello di classificazione che sfrutta numerosi alberi decisionali per ottenere un risultato complessivo migliore (migliore generalizzazione, minore overfitting) rispetto a quello che si otterrebbe con ognuno degli alberi presi singolarmente. In generale la metodologia di utilizzare un insieme di modelli che concorrono ad ottenere un risultato migliore è detta apprendimento ensemble, di cui le foreste casuali sono uno dei casi più famosi.
Come si crea una foresta casuale? Innanzitutto si decide quale dovrà essere il numero di alberi che compone la nostra foresta. Più alto è il numero di alberi, più il carico computazionale aumenterà, quindi è necessario arrivare (come sempre) ad un compromesso tra accuracy e sforzo di elaborazione. Successivamente selezioniamo casualmente un insieme di esempi dal nostro dataset. Questo sottoinsieme lo utilizziamo come training set per un albero decisionale. Si ripete la scelta casuale del sottoinsieme di esempi e la generazione di un nuovo albero, fino a quando non raggiungiamo il numero di alberi che compongono la nostra foresta casuale.
Una volta ottenuta la foresta casuale, come eseguiamo una predizione? Si eseguono le predizioni di ogni singolo albero decisionale che compone la foresta, ed infine si utilizza una regola per decidere la classificazione finale in base ai risultati ottenuti da tutti gli alberi. Da questo si capisce l’importanza del numero di alberi che compone la foresta: maggiore è il numero di alberi, migliore sarà il modello, ma maggiore sarà anche lo sforzo di calcolo.
Codice Python
NOTA: il codice di questo esempio lo trovi qui
Riprendiamo l’esempio precedente, utilizziamo la classe RandomForestClassifier per creare la nostra foresta casuale e poi analizziamo i risultati delle accuracy del training set e del test set. Visto che la generazione della foresta utilizza delle selezioni casuali, per rendere i risultati consistenti tra le varie prove, impostiamo un seed, in modo da poter confrontare in modo coerente i vari tentativi che faremo. Inoltre indichiamo che i nostri alberi utilizzeranno la metrica gini per l’impurità.
# istanzio la classe di creazione di foreste casuali
# imposto un random_state per ottenere risultati consistenti nelle varie prove
rndForest = RandomForestClassifier(random_state=0, criterion='gini')
rndForest.fit(X_train, Y_train)
Uso l'algoritmo 'gini' per l'impurità
Accuracy train set: 0.9950617283950617
Accuracy test set: 0.7068965517241379
Notiamo che il risultato è già migliore del primo tentativo eseguito in precedenza con un albero solo. Questo perchè di default la classe di generazione della foresta casuale, utilizza 10 alberi decisionali (a partire dalla versione 0.22 di Scikit-Learn si è passati a 100 come default).
In ogni caso la differenza tra le due accuracy è alta e questo fa supporre che il modello sia comunque in overfitting.
Proviamo indicando che i nostri alberi potranno crescere al massimo fino ad una profondità pari a 2 e ripetiamo la verifica.
# rieseguo limitando la profondità degli alberi
rndForest = RandomForestClassifier(random_state=0, criterion='gini', max_depth=2)
rndForest.fit(X_train, Y_train)
Limito la profondità a 2
Accuracy train set: 0.7209876543209877
Accuracy test set: 0.7011494252873564
Questa volta l’accuracy del training set è calata, ma quella del test set non è migliorata, anzi è leggermente peggiorata. Il modello soffre meno di overfitting, ma siamo comunque vicino al limite di accuratezza. Vediamo se cambia qualcosa lasciando libera la profondità degli alberi ma limitandone a 2 il numero nella foresta.
# aumento gli estimatori
rndForest = RandomForestClassifier(random_state=0, criterion='gini', n_estimators=2)
rndForest.fit(X_train, Y_train)
Limito il numero di alberi a 2
Accuracy train set: 0.8987654320987655
Accuracy test set: 0.7413793103448276
Beh sì, non abbiamo fatto miracoli: è migliorata un po’ l’accuracy sia di train che di test, probabilmente siamo tornati a soffrire un po’ di overfitting (meno di prima), ma tutto sommato questo credo sia il risultato migliore che possiamo trovare con questo metodo di classificazione applicato a questo dataset. Risultato che è comunque migliore di quello ottenuto con un unico albero.
Alla prossima!
Come al solito vi invito a sperimentare questi metodi con altri dataset e modificando i parametri per capire come questi possano variare i risultati.
Noi ci vediamo al prossimo articolo!
Bye!