Come tutti i modelli di machine learning supervisionato, gli alberi decisionali sono addestrati per spiegare al meglio un insieme di esempi di addestramento. L'addestramento ottimale di un albero decisionale è un problema difficile da risolvere. Pertanto, l'addestramento viene generalmente eseguito utilizzando l'euristica, un algoritmo di apprendimento facile da creare che fornisce un albero decisionale non ottimale, ma vicino a quello ottimale.
La maggior parte degli algoritmi utilizzati per addestrare gli alberi decisionali usa una strategia di divisione e conquista. L'algoritmo inizia creando un singolo nodo (la radice) per far crescere l'albero decisionale in modo ricorsivo e avidamente.
In ciascun nodo, vengono valutate e valutate tutte le possibili condizioni. L'algoritmo seleziona la condizione "migliore", ovvero la condizione con il punteggio più alto. Per il momento, tieni presente che il punteggio è una metrica correlata all'attività e che le condizioni sono selezionate per massimizzare la metrica.
Ad esempio, nel set di dati Palmer Palmer (utilizzato per esempi di codice più avanti in questo corso), la maggior parte dei pinguini di Adelie e Chinstrap hanno una lunghezza del becco superiore a 16 mm, mentre la maggior parte di questi ha un becco più piccolo. Pertanto, la condizione bill_length_mm ≥ 16 fornisce previsioni quasi perfette per i pinguini Gentoo, ma non può distinguere tra i pinguini Adelies e Chinstrap. È probabile che l'algoritmo sceglierà questa condizione.
Figura 7. Il primo passo per far crescere un albero.
L'algoritmo si ripete quindi in modo ricorsivo e indipendente su entrambi i nodi figlio. Quando non vengono trovate condizioni soddisfacenti, il nodo diventa una foglia. La previsione delle foglie è 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 dell'addestramento di un particolare albero decisionale.
Passaggio 1. Crea un root:
Passaggio 2. Fai crescere il nodo 1. È stata trovata la condizione "x1 ≥ 1". Vengono creati due nodi secondari:
Passaggio 3. Fai crescere il nodo 2. Nessuna condizione soddisfacente trovata. Quindi, trasforma il nodo in una foglia:
Passaggio 4. Fai crescere il nodo 3. È stata trovata la condizione "x2 ≥ 0,5". Vengono creati due nodi secondari.
Esistono altri metodi per far crescere gli alberi decisionali. Un'alternativa popolare è ottimizzare i nodi a livello globale invece di utilizzare una strategia di divisione e conquista.
growing_strategy="BEST_FIRST_GLOBAL".
Per ulteriori dettagli, consulta la
documentazione.
A seconda del numero e del tipo di caratteristiche di input, il numero di possibili condizioni per un dato nodo può essere enorme e generalmente 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é deve testare molte condizioni possibili, i splitter sono il collo di bottiglia quando si addestra un albero decisionale.
Il punteggio massimizzato dallo strumento di suddivisione dipende dall'attività. Ad esempio:
- Acquisizione di informazioni e Gini (entrambi trattati in seguito) sono comunemente utilizzati per la classificazione.
- L'errore quadratico medio è comunemente utilizzato per la regressione.
Esistono molti algoritmi di suddivisione, ciascuno con supporto diverso per:
- Il tipo di elementi, ad esempio numerico, categoriale, di testo
- L'attività, ad esempio classificazione binaria, classificazione multiclasse, regressione
- Il tipo di condizione; ad esempio, condizione di soglia, condizione in-set, condizione obbligatoria
- I criteri di regolarizzazione; ad esempio, ripartitori esatti o approssimativi per le condizioni di soglia
Inoltre, esistono varianti di splitter equivalenti con compromessi diversi in termini di utilizzo della memoria, della CPU, della distribuzione dei calcoli e così via.