Apprendimento collettivo Dall’albero decisionale alla foresta casuale

Apprendimento collettivo dall'albero decisionale alla foresta casuale

Scopri il potere dell’apprendimento ensemble

In questo articolo, discuteremo e descriveremo l’apprendimento ensemble.

Inizieremo la nostra discussione con il modello dell’albero decisionale. Successivamente, spiegheremo l’apprendimento ensemble e infine descriveremo il modello Random Forest come un ensemble creato sulla base degli alberi decisionali.

Sia per l’albero decisionale che per il Random Forest, forniremo del codice Python per mostrare come implementarli nel caso di un compito di classificazione.

Il modello dell’albero decisionale

Un albero decisionale (DT) è un modello di apprendimento automatico molto versatile che è in grado di eseguire compiti di regressione e classificazione, avendo la possibilità di lavorare sia con variabili numeriche che categoriche.

Qui, spiegheremo il modello DT, mostrando il suo processo di apprendimento con un po’ di matematica e ne implementeremo uno.

Spiegando il modello DT

Un modello di albero decisionale è un modello di apprendimento automatico simile a uno schema a flusso che è costruito in modo simile a un albero reale. Ha foglie, nodi, radici e rami.

Vediamo come funziona e le sue caratteristiche con un esempio concreto. Supponiamo che un DT debba decidere per noi se rimanere in ufficio o uscire, in base al lavoro che dobbiamo svolgere:

Fonte: Immagine dell'autore. — Fonte: Immagine dell’autore.

Quindi, abbiamo:

Il nodo radice. Questo è dove tutto inizia e rappresenta l’intero dataset.
Le estremità sono chiamate nodi foglia (tutti i rettangoli arancioni) perché sono simili alle foglie degli alberi: sono alla fine.
Nodi interni. Sono nodi che sono stati divisi dai nodi precedenti.
Rami. Sono un insieme di nodi interni e foglie, proprio come negli alberi reali.
La profondità massima rappresenta quanto è profondo un DT; in altre parole, rappresenta quante divisioni ci servono prima di arrivare alle ultime foglie (“tornare a casa/andare in un pub”), partendo dal nodo radice.

L’idea di base dietro ai modelli degli alberi decisionali è utilizzare le caratteristiche del dataset per prendere decisioni e dividere i dati in sottoinsiemi più piccoli. Ogni nodo interno nell’albero rappresenta una caratteristica o un attributo, e i rami rappresentano le diverse decisioni o regole basate sui valori di quella caratteristica.

I nodi foglia rappresentano l’output finale: una classe (in un problema di classificazione) o un valore (in un problema di regressione).

Questo processo è molto simile a come noi, come esseri umani, prendiamo decisioni. Quindi potrebbe sorgere una domanda: come dividono gli alberi decisionali i nodi? In altre parole: come prendono decisioni gli alberi decisionali?

Bene, gli alberi decisionali continuano a dividere fino a quando tutte le foglie sono pure, il che significa che tutti i nodi interni hanno almeno una foglia.

Nella pratica, questo può portare a alberi decisionali molto profondi con molti nodi, il che può facilmente portare all’overfitting. Quindi, quello che facciamo di solito è potare l’albero impostando un limite per la profondità massima (che è uno degli iperparametri degli alberi decisionali).

Impurità e Guadagno di Informazione

Per capire come gli alberi decisionali si dividono fino a quando le foglie sono pure, cioè come prendono decisioni, dobbiamo utilizzare un po’ di matematica per spiegare i concetti di impurità e guadagno di informazione.

In particolare, ci sono due tipi di impurità: entropia e impurità di Gini.

Entropia

In termodinamica, l’entropia rappresenta una misura del disordine molecolare: l’entropia è 0 quando le molecole sono ferme e ben ordinate.

Nell’apprendimento automatico, usiamo l’entropia per misurare l’impurità, seguendo un’idea simile. Definiamo l’entropia come segue [Ref. 2, pagina 88]:

Nel caso di un problema di classificazione, abbiamo che p(i|t) è la proporzione degli esempi che appartengono alla classe i per il nodo t.

Quindi, l’entropia è 0 se tutti gli esempi in un determinato nodo appartengono alla stessa classe, ed è massima (il suo valore massimo è 1) se, in un determinato nodo, abbiamo una distribuzione di classi uniforme.

Impurità di Gini

L’impurità di Gini è una misura di quanto bene una caratteristica separa i dati in diverse classi. Viene definita come la probabilità di misclassificare un esempio scelto casualmente in un dataset. La definiamo come segue [Ref. 1, pagina 169]:

Quindi, dato il fatto che, nel caso di un problema di classificazione, p(i|t) è la proporzione degli esempi che appartengono alla classe i per il nodo t, è per questo che l’impurità di Gini può essere vista come un criterio per minimizzare la probabilità di misclassificazione. Questo perché se abbiamo:

che significa che tutti gli esempi appartengono alla stessa classe, allora:

che significa che il nodo è puro (quindi, le istanze appartengono alla stessa classe, come detto prima).

Quindi, l’impurità di Gini varia da 0 a 1, dove 0 rappresenta un dataset puro (tutti gli esempi appartengono alla stessa classe) e 1 rappresenta un dataset impuro (gli esempi appartengono a più classi).

Facciamo un esempio. Supponiamo di avere un dataset con due classi, A e B, e abbiamo due caratteristiche, P e Q, tra cui scegliere per dividere i dati. Se la caratteristica P produce un’impurità di Gini di 0.2 e la caratteristica Q produce un’impurità di Gini di 0.3, sceglieremmo la caratteristica P per dividere i dati perché produce un’impurità più bassa e quindi un sottoinsieme più puro dei dati.

Quale usare?

sklearn utilizza l’impurità di Gini come predefinita, ma possiamo impostare l’entropia come criterio (questo è un iperparametro dei DT). La verità è che non c’è una grande differenza tra le due: addestrare un DT con entropia e addestrare un altro con impurità di Gini non vale lo sforzo.

Massimizzare il guadagno di informazione

Il guadagno di informazione è una misura della diminuzione dell’impurità di un dataset dopo che una caratteristica viene scelta per dividere i dati. Lo scopo di un albero decisionale, infatti, è selezionare la caratteristica più “significativa” in modo che si ottengano sottoinsiemi più puri dei dati. Quindi, utilizziamo il guadagno di informazione per determinare la qualità relativa di una caratteristica a questo scopo.

Quindi, dato che il guadagno di informazione è una misura di quanto bene una caratteristica separa i dati in diverse classi, vogliamo massimizzarlo.

Lo definiamo come segue [Ref. 2, pagina 88]:

dove abbiamo:

f è la caratteristica da dividere,
Dp e Dn sono, rispettivamente, il dataset del nodo genitore e del n-esimo nodo figlio.
I è l’impurità.
Np e Nn sono, rispettivamente, il numero totale di esempi di addestramento nel nodo genitore e nel n-esimo nodo figlio.

Abbiamo introdotto i concetti di “nodo genitore” e “nodo figlio” sopra. Questi sono termini relativi: ogni nodo che cade sotto un altro nodo è un nodo figlio o sottornodo, e ogni nodo che precede quei nodi figli è chiamato nodo genitore

Quindi, per la formula sopra, il Gain dell’Informazione è la differenza tra l’impurità del nodo genitore e la somma delle impurità dei nodi figli; ciò significa che più bassa è l’impurità dei nodi figli, maggiore è il Gain dell’Informazione.

Ciò significa che un DT prende decisioni con l’obiettivo di massimizzare il Gain dell’Informazione, il che significa ridurre l’impurità in ogni nodo.

Implementare un DT nel caso di un problema di classificazione

Creiamo un dataset, standardizziamo i dati, dividiamo il dataset in set di addestramento e di test, addestriamo il set di addestramento con un modello DT e calcoliamo la matrice di confusione sul set di test:

from sklearn.datasets import make_classificationfrom sklearn.model_selection import train_test_splitfrom sklearn.preprocessing import StandardScalerfrom sklearn.tree import DecisionTreeClassifierfrom sklearn.metrics import confusion_matrix# Creiamo un dataset di classificazioneX, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_classes=2, random_state=42)# Standardizziamo i dati scaler = StandardScaler()X_scaled = scaler.fit_transform(X)# Dividiamo il dataset in set di addestramento e di testX_train, X_test, y_train, y_test = train_test_split(X_scaled, y, test_size=0.2, random_state=42)# Addestriamo il set di addestramento con un modello Decision Treedt_model = DecisionTreeClassifier(random_state=42)dt_model.fit(X_train, y_train)# Calcoliamo la matrice di confusione per il set di testy_test_pred = dt_model.predict(X_test)test_confusion_matrix = confusion_matrix(y_test, y_test_pred)print("Matrice di confusione (Set di test):\n", test_confusion_matrix)

E otteniamo:

Matrice di confusione (Set di test): [[103   9] [ 12  76]]

Questo è un risultato abbastanza buono perché i valori fuori diagonale, che rappresentano falsi positivi e falsi negativi, sono molto pochi.

Apprendimento di insieme

Quando risolviamo un problema di ML, generalmente testiamo diversi modelli di ML sui dati per trovare quello che fa previsioni o classificazioni migliori su nuovi dati non visti.

Un modo per migliorare la soluzione a un problema di ML è combinare alcuni modelli, tipicamente i modelli che si comportano meglio, in un singolo modello unico: chiamiamo questo apprendimento di insieme.

Il gruppo, o insieme, sarà sempre migliore del singolo modello migliore.

Vediamo come funziona.

Il principio del voto

Consideriamo un esempio di classificazione: abbiamo addestrato una macchina a vettori di supporto e un albero decisionale nel caso di un problema di classificazione binaria, e l’accuratezza che otteniamo è di circa 80% per entrambi i classificatori. Ciò significa che entrambi i classificatori predicono la classe corretta nell’80% dei casi, il che può essere abbastanza buono.

Lo scopo dei metodi di insieme è combinare diversi metodi in un singolo classificatore che ha migliori prestazioni di generalizzazione rispetto a ciascun classificatore individuale da solo. Ma come può essere possibile? Come può un meta-classificatore, creato combinando in qualche modo classificatori diversi, avere migliori prestazioni di generalizzazione rispetto ai classificatori individuali?

L’apprendimento di insieme si basa sulla cosiddetta “legge dei grandi numeri”; facciamo un esempio per capirlo [Ref.1, pagina 183]:

“Supponiamo di avere una moneta truccata che ha una probabilità del 51% di uscire testa e una probabilità del 49% di uscire croce. Se lanciamo la moneta 1’000 volte, otterremo circa 510 teste e 490 croci, quindi una maggioranza di teste. Facendo i calcoli, se lanciamo la moneta 1’000 volte, la probabilità di ottenere teste è vicina al 75%. Questo è dovuto alla legge dei grandi numeri: man mano che continuiamo a lanciare la moneta, il rapporto di teste si avvicina sempre di più alla probabilità di teste (51%).”

L’apprendimento dell’insieme sfrutta questo principio quando combina diversi classificatori. Infatti, un modo semplice per creare un classificatore di insieme è aggregare le previsioni di ogni classificatore che abbiamo addestrato e prevedere la classe che ottiene il maggior numero di voti: chiamiamo questo principio il principio della maggioranza dei voti.

Creiamo un diagramma per una migliore comprensione del principio della maggioranza dei voti. Supponiamo di aver addestrato un SVM e un DT su un determinato set di dati che rappresenta un problema di classificazione binaria. Ecco come funziona il principio della maggioranza dei voti:

Sebbene sia possibile combinare qualsiasi tipo di classificatori, questo tipo di principio funziona meglio con classificatori indipendenti perché ogni classificatore indipendente commette errori non correlati agli altri classificatori. In altre parole, ogni classificatore nell’insieme è in grado di catturare un aspetto diverso dei dati e combinando le loro previsioni possiamo ottenere una previsione più accurata rispetto a ciascun classificatore individuale.

La matematica dietro il principio del voto

Utilizziamo un esempio di classificazione per mostrare matematicamente come funziona il principio della maggioranza dei voti.

Vogliamo implementare un algoritmo che ci permetta di combinare diversi classificatori, ognuno associato a un peso per la fiducia. Il nostro obiettivo è costruire un meta-classificatore che bilanci i punti deboli dei classificatori individuali (cioè alto bias o alta varianza) su un set di dati. Possiamo creare un voto di maggioranza ponderato nel seguente modo [Ref. 2, pagina 209]:

Dove abbiamo:

“y” che rappresenta la classe prevista del nostro insieme.
“Wj” che rappresenta un peso associato a un certo classificatore, “Cj”
“Fa” è una funzione che restituisce 1 se la classe prevista del j-esimo classificatore corrisponde a i, quindi nel caso di “Cj(x)=i”

La funzione arg max restituisce l’argomento massimo.

Nel caso in cui abbiamo pesi uguali per ogni classificatore, abbiamo semplicemente quanto segue:

Ricordiamo che in statistica, la moda è il valore che appare più spesso in un insieme di dati, in questo caso, y^ è semplicemente la moda di tutte le uscite dei nostri classificatori.

Quindi, supponiamo di avere un problema di classificazione binaria con tre classificatori e abbiamo:

C1(x) → 1
C2(x) → 0
C3(x) → 0

Abbiamo:

Ora, assegniamo dei pesi ai nostri classificatori come segue:

C1(x) → 1, W1=0.6
C2(x) → 0, W2=0.2
C3(x) → 0, W3=0.2

Quindi, in questo caso, la previsione fatta da C1 ha più peso rispetto agli altri e la classe prevista dall’insieme è 1.

In altre parole, W1=0.6 è tre volte il peso di C2 e C3; vale a dire: 0.6=3⋅0.20.6. Quindi, quello che vogliamo dire è che C1 ha tre volte il peso degli altri due classificatori, e possiamo anche calcolare la previsione dell’insieme con la seguente formula:

Ensembling con bagging e pasting

Bagging è un modo abbreviato per dire bootstrap aggregating.

Nelle statistiche, l’aggregazione di bootstrap è un test che utilizza un campionamento casuale con sostituzione. Sostituzione significa che un punto dati individuale può essere scelto più di una volta.

Invece, pasting è una tecnica di campionamento casuale che non utilizza la sostituzione. Il fatto che il pasting non applichi la sostituzione significa che un punto dati individuale può essere scelto solo una volta.

Utilizziamo uno schema per chiarire il processo del bagging:

Quindi, nel caso sopra descritto, abbiamo preso 5 campioni dal set di addestramento e li abbiamo utilizzati per alimentare tre classificatori/regressori utilizzando la tecnica del bagging; ossia, possiamo utilizzare lo stesso campione preso dal set di addestramento più volte.

Si noti che ogni sottoinsieme contiene un certo numero di sottoinsiemi duplicati e alcuni dei sottoinsiemi originali non compaiono in tutti i sottoinsiemi di resampling, a causa della sostituzione. Per chiarezza: abbiamo alimentato il classificatore/regressore 1 con dati in cui il sottoinsieme n°5 non è presente. E così via per gli altri classificatori/regressori.

Il modello Random Forest

Purtroppo, i DT (decision tree) soffrono di alta varianza e possiamo limitare la loro varianza limitandone la profondità.

Inoltre, i DT regolano le loro previsioni per ogni singola divisione dei dati. Ciò significa che più sono profondi, maggiore è il rischio di overfitting.

Per evitare di dover gestire troppo la varianza alta dei DT, una soluzione per potenziare i DT è creare un’insieme: ecco come nasce un modello Random Forest.

Costruire un modello RF sopra i DT

I metodi di ensemble hanno raggiunto un buon grado di popolarità negli ultimi anni nel campo del ML (machine learning), grazie alle loro buone prestazioni verso l’overfitting.

Una random forest (RF) è un modello di ML che può svolgere sia compiti di classificazione che di regressione ed è costruito come un insieme di alberi decisionali tramite il metodo del bagging. Ciò significa che l’RF ha tutti gli iperparametri di un DT, ma ha anche tutti gli iperparametri di un classificatore/regressore bagging per controllare l’insieme stesso.

Visualizziamo il processo di creazione di un modello RF:

Quindi, qui stiamo creando una foresta di alberi decisionali addestrati su sott campioni, con sostituzione, dei dati di addestramento iniziali.

Inoltre, il modello RF introduce una certa casualità aggiuntiva durante la crescita degli alberi perché, anziché cercare la miglior feature quando si divide un nodo (come avviene nei modelli DT), cerca la miglior feature tra un sottoinsieme casuale delle feature. Ciò comporta un maggiore bias e una minore varianza, quindi un modello migliore rispetto a un singolo DT.

In altre parole, quando si divide un nodo, i DT considerano ogni possibile feature e scelgono quella che produce la maggiore separazione tra i sottonodi. Invece, nel caso di un modello RF, ogni albero può selezionare solo un sottoinsieme casuale delle feature. Ciò aumenta la casualità e la variazione tra gli alberi, risultando in una maggiore indipendenza tra ciascun albero e quindi una maggiore diversificazione.

Visualizziamo questo concetto:

Supponiamo quindi di avere un set di dati con 5 feature. Controllando gli alberi del nostro modello RF possiamo vedere che:

DT 1 considera la caratteristica 1, la caratteristica 3 e la caratteristica 5.
DT 2 considera la caratteristica 1, la caratteristica 4 e la caratteristica 5.
DT 3 considera la caratteristica 2, la caratteristica 3 e la caratteristica 4.

Tutte queste caratteristiche vengono selezionate casualmente per ogni DT del nostro RF.

Supponiamo di aver addestrato in precedenza un singolo DT su tutte le caratteristiche e aver scoperto che la miglior caratteristica per dividere il nodo è la caratteristica 2. Tuttavia, DT 1 e DT 2 non possono essere addestrati sulla caratteristica 2 e sono costretti ad essere addestrati, rispettivamente, sulla caratteristica 3 e sulla caratteristica 4 (entrambe in grassetto nell’immagine precedente).

Finiamo con alberi che sono addestrati su sottoinsiemi casuali diversi dei dati iniziali, ma anche su un sottoinsieme casuale delle caratteristiche, senza sostituzione.

In generale, gli RF non hanno lo stesso livello di interpretabilità dei DT, ma un grande vantaggio degli RF è che non dobbiamo preoccuparci troppo dei loro iperparametri. Ad esempio, di solito non dobbiamo potare un RF, perché l’insieme è robusto al rumore derivante dalla media delle previsioni dei DT che creano il modello.

Il parametro tipico a cui dovremmo prestare attenzione è il numero di alberi che creano l’RF. Possiamo ottenere prestazioni migliori con un numero maggiore di alberi a scapito di un costo computazionale più elevato (abbiamo bisogno di più tempo e risorse hardware).

Implementazione di un RF

Utilizziamo lo stesso dataset che abbiamo utilizzato per l’Albero di Decisione per confrontare i risultati quando stiamo utilizzando un Random Forest:

from sklearn.datasets import make_classificationfrom sklearn.model_selection import train_test_splitfrom sklearn.preprocessing import StandardScalerfrom sklearn.ensemble import RandomForestClassifierfrom sklearn.metrics import confusion_matrix# Creiamo un dataset di classificazioneX, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_classes=2, random_state=42)# Standardizziamo i dati con lo StandardScalerscaler = StandardScaler()X_scaled = scaler.fit_transform(X)# Dividiamo il dataset in set di addestramento e di testX_train, X_test, y_train, y_test = train_test_split(X_scaled, y, test_size=0.2, random_state=42)# Addestriamo il set di addestramento con un modello Random Forestrf_model = RandomForestClassifier(n_estimators=100, random_state=42)rf_model.fit(X_train, y_train)# Calcoliamo la matrice di confusione per il set di testy_test_pred = rf_model.predict(X_test)test_confusion_matrix = confusion_matrix(y_test, y_test_pred)print("Matrice di confusione (Set di test):\n", test_confusion_matrix)

E otteniamo:

Matrice di confusione (Set di test): [[106   6] [  5  83]]

Come possiamo vedere, le prestazioni dell’RF sono migliori rispetto a quelle di un singolo DT perché questa matrice di confusione ha meno elementi non diagonalizzabili (FP e FN) e più elementi diagonalizzabili (TP e TN), come desideriamo.

Conclusioni

In questo articolo, abbiamo discusso come l’apprendimento in ensemble possa migliorare le prestazioni di un singolo modello di apprendimento automatico, partendo da un modello DT e terminando con un RF.

Riferimenti:

[1]: Hands-On Machine Learning with Scikit-Learn & Tensorflow. Aurelien Gueron

[2]: Machine Learning with PyTorch ans Scikit-learn. Sebastian Raschka, Yuxi Liu, Vahid Mirjalili

NOTA: anche quando non espressamente indicato con un numero di pagina, i riferimenti devono essere considerati come da [1] e [2].

Apprendimento collettivo Dall’albero decisionale alla foresta casuale