Come tutti i modelli di machine learning supervisionato, gli alberi decisionali sono addestrati al meglio una serie di esempi di addestramento. L'addestramento ottimale di un albero decisionale è un problema difficile da NP. Pertanto, l'addestramento solitamente avviene utilizzando l'euristica, una un algoritmo di apprendimento facile da creare, che offre un ottimale, albero decisionale.
La maggior parte degli algoritmi usati per addestrare gli alberi decisionali funziona con un ingordo divario e la strategia vincente. L'algoritmo inizia creando un singolo nodo (la radice) in modo ricorsivo e avido dell'albero decisionale.
In ciascun nodo vengono valutate e valutate tutte le possibili condizioni. La l'algoritmo seleziona il "migliore" cioè la condizione con il valore punteggio. Per ora, ti basterà sapere che il punteggio è una metrica correlata l'attività e le condizioni sono selezionate per massimizzare questa metrica.
Ad esempio, nel dominio Palmer Pinguini (utilizzato per gli esempi di codice più avanti in questo corso), quasi tutti i pinguini hanno un becco lungo più di 16 mm, mentre la maggior parte dei i pinguini hanno becchi più piccoli. Pertanto, la condizione bill_length_mm ≥ 16 rende le previsioni quasi perfette per il Pinguini gentos, ma non riesce a differenziare tra Adelies e Chinstrap. Probabilmente l'algoritmo sceglierà questa condizione.
Figura 7. Il primo passo per far crescere un albero. di Gemini Advanced.
L'algoritmo si ripete in modo ricorsivo e indipendente su entrambi i nodi figlio. Quando non vengono trovate condizioni soddisfacenti, il nodo diventa una foglia. La foglia la previsione è il valore dell'etichetta più rappresentativo degli 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 i passaggi per addestrare un particolare albero decisionale in modo più dettagliato.
Passaggio 1. Crea una radice:
Passaggio 2: fai crescere il nodo 1. La condizione "x1 ≥ 1" è stato trovato. Vengono creati due nodi figlio:
Passaggio 3: fai crescere il nodo 2. Nessuna condizione soddisfacente trovata. Quindi, rendi il nodo in una foglia:
Passaggio 4: fai crescere il nodo 3. La condizione "x2 ≥ 0,5" è stato trovato. Due figli vengono creati tutti i nodi.
Esistono altri metodi per coltivare gli alberi decisionali. Un'alternativa popolare è ottimizzare i nodi a livello globale invece di usare una strategia di divisione e eliminazione.
growing_strategy="BEST_FIRST_GLOBAL".
Vedi
documentazione per ulteriori dettagli.
A seconda del numero e del tipo di caratteristiche di input, il numero di e le condizioni possibili per un dato nodo possono essere enormi e generalmente infinite. Ad esempio, data una condizione di soglia $\mathrm{feature}_i \geq t$, dalla combinazione possibile valori di soglia per $t \in \mathbb{R}$ è infinita.
La routine responsabile di trovare la condizione migliore è chiamata splitter. Poiché deve testare molte condizioni possibili, i ripartitori rappresentano un collo di bottiglia durante l'addestramento di un albero decisionale.
Il punteggio massimizzato dalla suddivisione dipende dall'attività. Ad esempio:
- Acquisizione di informazioni e Gini (entrambi più avanti) sono 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 numerico, categorico, testuale
- L'attività; ad esempio classificazione binaria, classificazione, regressione
- Il tipo di condizione; ad esempio condizione di soglia, condizione in-impostata, condizione obliqua
- I criteri di regolarizzazione; ad esempio, suddivisioni esatte o approssimative per le condizioni di soglia
Inoltre, esistono varianti di ripartitori equivalenti con compromessi diversi. per quanto riguarda l'utilizzo della memoria, l'utilizzo della CPU, la distribuzione del calcolo e così via.