Cos’è un Albero di Decisione?

Cos’è un Albero di Decisione?

Un albero di decisione è un utile algoritmo di apprendimento automatico utilizzato per entrambi i compiti di regressione e classificazione. Il nome “albero di decisione” deriva dal fatto che l’algoritmo continua a dividere il set di dati in porzioni sempre più piccole fino a quando i dati non sono stati divisi in istanze singole, che vengono quindi classificate. Se si visualizzassero i risultati dell’algoritmo, il modo in cui le categorie vengono divise assomiglierebbe a un albero con molte foglie.

Questa è una definizione rapida di un albero di decisione, ma analizziamo più in dettaglio come funzionano gli alberi di decisione. Avere una migliore comprensione di come funzionano gli alberi di decisione, nonché dei loro casi d’uso, ci aiuterà a sapere quando utilizzarli durante i progetti di apprendimento automatico.

Formato di un Albero di Decisione

Un albero di decisione è simile a un diagramma di flusso. Per utilizzare un diagramma di flusso, si inizia dal punto di partenza, o radice, del diagramma e poi, in base a come si rispondono ai criteri di filtro di quel nodo di partenza, si passa a uno dei nodi possibili successivi. Questo processo viene ripetuto fino a quando non si raggiunge un punto di fine.

Gli alberi di decisione funzionano in modo essenzialmente simile, con ogni nodo interno dell’albero che rappresenta una sorta di test o criterio di filtro. I nodi esterni, i punti finali dell’albero, sono le etichette per il punto di dati in questione e vengono chiamati “foglie”. I rami che collegano i nodi interni al nodo successivo sono caratteristiche o congiunzioni di caratteristiche. Le regole utilizzate per classificare i punti di dati sono i percorsi che vanno dalla radice alle foglie.

Algoritmi per Alberi di Decisione

Gli alberi di decisione funzionano con un approccio algoritmico che divide il set di dati in punti di dati individuali in base a diversi criteri. Queste divisioni vengono effettuate con diverse variabili, o caratteristiche diverse del set di dati. Ad esempio, se l’obiettivo è determinare se si sta descrivendo un cane o un gatto in base alle caratteristiche di input, le variabili su cui si divide il dato potrebbero essere cose come “unghie” e “abbaia”.

Quindi, quali algoritmi vengono utilizzati per dividere effettivamente i dati in rami e foglie? Ci sono vari metodi che possono essere utilizzati per dividere un albero, ma il metodo più comune di divisione è probabilmente una tecnica chiamata “divisione binaria ricorsiva“. Quando si esegue questo metodo di divisione, il processo inizia dalla radice e il numero di caratteristiche nel set di dati rappresenta il numero possibile di divisioni possibili. Una funzione viene utilizzata per determinare quanto costa ogni possibile divisione in termini di accuratezza, e la divisione viene effettuata utilizzando il criterio che sacrifica meno accuratezza. Questo processo viene eseguito ricorsivamente e sottogruppi vengono formati utilizzando la stessa strategia generale.

Per determinare il costo della divisione, viene utilizzata una funzione di costo. Una funzione di costo diversa viene utilizzata per i compiti di regressione e classificazione. L’obiettivo di entrambe le funzioni di costo è determinare quali rami hanno i valori di risposta più simili, o i rami più omogenei. Considerate che si desidera che i dati di test di una certa classe seguano percorsi specifici e questo ha senso intuitivo.

In termini di funzione di costo per la regressione per la divisione binaria ricorsiva, l’algoritmo utilizzato per calcolare il costo è il seguente:

somma(y – previsione)^2

La previsione per un gruppo specifico di punti di dati è la media delle risposte dei dati di training per quel gruppo. Tutti i punti di dati vengono eseguiti attraverso la funzione di costo per determinare il costo per tutte le possibili divisioni e la divisione con il costo più basso viene selezionata.

Per quanto riguarda la funzione di costo per la classificazione, la funzione è la seguente:

G = somma(pk * (1 – pk))

Questo è il punteggio di Gini, ed è una misura dell’efficacia di una divisione, in base a quanti esempi di classi diverse sono presenti nei gruppi risultanti dalla divisione. In altre parole, quantifica quanto sono misti i gruppi dopo la divisione. Una divisione ottimale si verifica quando tutti i gruppi risultanti dalla divisione consistono solo di input di una classe. Se una divisione ottimale è stata creata, il valore “pk” sarà 0 o 1 e G sarà uguale a zero. Potreste essere in grado di indovinare che la peggiore divisione è quella in cui c’è una rappresentazione 50-50 delle classi nella divisione, nel caso di classificazione binaria. In questo caso, il valore “pk” sarebbe 0,5 e G sarebbe anche 0,5.

Il processo di divisione si termina quando tutti i punti di dati sono stati trasformati in foglie e classificati. Tuttavia, potreste voler interrompere la crescita dell’albero precocemente. Gli alberi grandi e complessi sono propensi a sovrapprendere, ma diversi metodi possono essere utilizzati per combattere questo. Un metodo per ridurre il sovrapprendimento consiste nell’indicizzare un numero minimo di punti di dati che verranno utilizzati per creare una foglia. Un altro metodo per controllare il sovrapprendimento consiste nel limitare l’albero a una profondità massima, che controlla quanto può essere lungo un percorso dalla radice a una foglia.

Un altro processo coinvolto nella creazione di alberi di decisione è la potatura. La potatura può aiutare a migliorare le prestazioni di un albero di decisione eliminando i rami che contengono caratteristiche che hanno poco potere predittivo/poca importanza per il modello. In questo modo, la complessità dell’albero viene ridotta, è meno probabile che si verifichi il sovrapprendimento e l’utilità predittiva del modello aumenta.

Quando si esegue la potatura, il processo può iniziare dalla parte superiore dell’albero o dalla parte inferiore dell’albero. Tuttavia, il metodo più semplice di potatura consiste nell’iniziare dalle foglie e cercare di eliminare il nodo che contiene la classe più comune all’interno di quella foglia. Se l’accuratezza del modello non peggiora quando si fa questo, allora il cambiamento viene conservato. Ci sono altri metodi utilizzati per eseguire la potatura, ma il metodo descritto sopra – potatura con riduzione dell’errore – è probabilmente il metodo più comune di potatura degli alberi di decisione.

Considerazioni per l’Utilizzo di Alberi di Decisione

Gli alberi di decisione sono spesso utili quando la classificazione deve essere eseguita ma il tempo di calcolo è una limitazione importante. Gli alberi di decisione possono chiarire quali caratteristiche nel set di dati scelto hanno il potere predittivo maggiore. Inoltre, a differenza di molti algoritmi di apprendimento automatico in cui le regole utilizzate per classificare i dati possono essere difficili da interpretare, gli alberi di decisione possono produrre regole interpretabili. Gli alberi di decisione possono anche utilizzare sia variabili categoriche che continue, il che significa che è necessaria meno pre-elaborazione rispetto agli algoritmi che possono gestire solo uno di questi tipi di variabili.

Gli alberi di decisione tendono a non funzionare molto bene quando vengono utilizzati per determinare i valori di attributi continui. Un’altra limitazione degli alberi di decisione è che, quando si esegue la classificazione, se ci sono pochi esempi di training ma molte classi, l’albero di decisione tende a essere inaccurato.