Come tutti i modelli di machine learning supervisionati, gli alberi decisionali vengono addestrati per spiegare al meglio un insieme di esempi di addestramento. L'addestramento ottimale di un albero decisionale è un problema NP-difficile. Pertanto, l'addestramento viene generalmente eseguito utilizzando le heurismi, ovvero un algoritmo di apprendimento facile da creare che genera un albero decisionale non ottimale, ma quasi ottimale.
La maggior parte degli algoritmi utilizzati per addestrare gli alberi decisionali funziona con una strategia di suddivisione e conquista avida. L'algoritmo inizia creando un singolo nodo (la radice) e aumenta in modo ricorsivo e avido l'albero decisionale.
In ogni nodo, tutte le possibili condizioni vengono valutate e assegnate un punteggio. L'algoritmo seleziona la condizione "migliore", ovvero quella con il punteggio più alto. Per il momento, tieni presente che il punteggio è una metrica correlata all'attività e che le condizioni vengono selezionate per massimizzare questa metrica.
Ad esempio, nel set di dati Palmer Penguins (utilizzato per gli esempi di codice più avanti in questo corso), la maggior parte dei pinguini Adelie e Barboni ha un becco lungo più di 16 mm, mentre la maggior parte dei pinguini Gentoo ha un becco più piccolo. Pertanto, la condizione bill_length_mm ≥ 16 genera previsioni quasi perfette per ipinguini di Adelia, ma non riesce a distinguere trapinguini di Adelia e pinguini antartici. L'algoritmo probabilmente sceglierà questa condizione.
Figura 7. Il primo passo per far crescere un albero.
L'algoritmo viene quindi ripetuto in modo ricorsivo e indipendente su entrambi i nodi secondari. Quando non vengono trovate condizioni soddisfacenti, il nodo diventa una foglia. La previsione dell'elemento finale viene determinata come il valore dell'etichetta più rappresentativo negli esempi.
L'algoritmo è il seguente:
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
Analizziamo più in dettaglio i passaggi per l'addestramento di un determinato albero decisionale.
Passaggio 1: crea un utente principale:
Passaggio 2: sviluppa il nodo 1. È stata trovata la condizione "x1 ≥ 1". Vengono creati due nodi secondari:
Passaggio 3: espandi il nodo 2. Non sono state trovate condizioni soddisfacenti. Quindi, trasforma il nodo in una foglia:
Passaggio 4: espandi il nodo 3. È stata trovata la condizione "x2 ≥ 0,5". Vengono creati due nodi secondari.
Esistono altri metodi per sviluppare alberi decisionali. Un'alternativa molto utilizzata è ottimizzare i nodi a livello globale anziché utilizzare una strategia di suddivisione e conquista.
growing_strategy="BEST_FIRST_GLOBAL".
Per ulteriori dettagli, consulta la
documentazione.
A seconda del numero e del tipo di elementi di input, il numero di condizioni possibili per un determinato nodo può essere enorme, in genere infinito. Ad esempio, data una condizione di soglia $\mathrm{feature}_i \geq t$, la combinazione di tutti i possibili valori di soglia per $t \in \mathbb{R}$ è infinita.
La routine responsabile della ricerca della condizione migliore è chiamata splitter. Poiché devono testare molte condizioni possibili, gli splitter sono il collo di bottiglia durante l'addestramento di un albero decisionale.
Il punteggio massimizzato dallo splitter dipende dall'attività. Ad esempio:
- Il guadagno informativo e l'indice di Gini (entrambi trattati in seguito) vengono comunemente utilizzati per la classificazione.
- Lo scarto quadratico medio è comunemente utilizzato per la regressione.
Esistono molti algoritmi di suddivisione, ognuno con un supporto diverso per:
- Il tipo di caratteristiche, ad esempio numeriche, categoriche, di testo
- L'attività, ad esempio classificazione binaria, classificazione multiclasse, regressione
- Il tipo di condizione, ad esempio condizione di soglia, condizione in-set, condizione obliqua
- I criteri di regolarizzazione, ad esempio gli split esatti o approssimativi per le condizioni di soglia
Inoltre, esistono varianti dello splitter equivalenti con compromessi diversi per quanto riguarda l'utilizzo della memoria, l'utilizzo della CPU, la distribuzione del calcolo e così via.