Podobnie jak wszystkie nadzorowane modele systemów uczących się, drzewa decyzyjne są trenowane tak, aby jak najlepiej objaśniały zbiór przykładów treningowych. Optymalne trenowanie drzewa decyzyjnego jest problemem NP-trudnym. Dlatego trenowanie polega zwykle na heurystyce – łatwego do utworzenia algorytmu uczenia, który daje nieoptymalny, ale zbliżony do optymalnego drzewo decyzyjne.
Większość algorytmów do trenowania drzew decyzyjnych korzysta ze strategii chciwego podziału i zwycięstwa. Algorytm zaczyna się od utworzenia pojedynczego węzła (pierwiastka), a potem rekurencyjnie i łatwo rozwija drzewo decyzyjne.
W każdym węźle oceniane są wszystkie możliwe warunki. Algorytm wybiera warunek „najlepszy”, czyli warunek o najwyższym wyniku. Na razie pamiętaj, że wynik jest wskaźnikiem skorelowanym z zadaniem, a warunki są wybierane w taki sposób, aby zmaksymalizować ten wskaźnik.
Na przykład w zbiorze danych Palmer Penguinsy (których podaliśmy w dalszej części tego kursu) większość pingwinów Adeli i Chinstrap ma dzioby dłuższe niż 16 mm, podczas gdy pingwiny białooki mają mniejsze dzioby. W związku z tym warunek długość_bill_mm ≥ 16 umożliwia przewidywanie pingwinów gentoo, ale nie rozróżnia pingwinów Adeli i podbródka. Algorytm prawdopodobnie wybierze ten warunek.
Rysunek 7. Pierwszy krok do wzrostu drzewa.
Następnie algorytm powtarza rekurencyjnie i niezależnie w obu węzłach podrzędnych. Jeśli nie zostaną znalezione żadne warunki spełniające warunki, węzeł staje się liściem. Przewidywanie liczby liści jest określane w przykładach jako najbardziej reprezentatywna wartość etykiety.
Ten algorytm wygląda tak:
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)
Przyjrzyjmy się po kolei krokom trenowania danego drzewa decyzyjnego.
Krok 1. Utwórz poziom główny:
Krok 2. Rozwiń węzeł nr 1. Znaleziono warunek „x1 ≥ 1”. Tworzone są 2 węzły podrzędne:
Krok 3. Rozwiń węzeł nr 2. Nie znaleziono spełniających warunków. Przekształć węzeł w liść:
Krok 4. Rozwój węzła nr 3. Znaleziono warunek „x2 ≥ 0,5”. Zostaną utworzone 2 węzły podrzędne.
Istnieją też inne metody uprawy drzew decyzyjnych. Popularną alternatywą jest optymalizacja węzłów globalnie zamiast stosowania strategii dzielenia i zdobywania.
growing_strategy="BEST_FIRST_GLOBAL".
Więcej informacji znajdziesz w
dokumentacji.
W zależności od liczby i rodzaju cech wejściowych liczba możliwych warunków dla danego węzła może być bardzo duża, a zwykle nieskończona. Na przykład w przypadku warunku progowego $\mathrm{feature}_i \geq t$ kombinacja wszystkich możliwych wartości progowych dla elementu $t \in \mathbb{R}$ jest nieskończona.
Rutyna odpowiedzialna za znalezienie najlepszego stanu jest nazywana rozdzielaczem. Ponieważ konieczne jest przetestowanie wielu możliwych warunków, rozdzielacze to wąskie gardła podczas trenowania drzewa decyzyjnego.
Wynik zmaksymalizowany przez podziałer zależy od zadania. Przykład:
- Do klasyfikacji powszechnie używa się zysku na podstawie informacji i Gini (oba omówione później).
- Do regresji często używa się błędu średniokwadratowego.
Istnieje wiele algorytmów rozdzielających. Każdy z nich ma różną obsługę:
- typ cech; na przykład numeryczne, kategorialne, tekstowe.
- Zadanie, np. klasyfikacja binarna, klasyfikacja wieloklasowa, regresja
- Typ warunku; np. warunek progowy, warunek w zestawie, warunek skośny.
- Kryteria regularyzacji, np. dokładne lub przybliżone podziały warunków progowych.
Dodatkowo istnieją równoważne warianty rozdzielające z różnymi kompromisami dotyczącymi wykorzystania pamięci, wykorzystania procesora, rozkładu obliczeń itd.