Podobnie jak wszystkie nadzorowane modele systemów uczących się, drzewa decyzyjne są trenowane tak, wyjaśnić zbiór przykładów treningowych. Optymalne trenowanie drzewa decyzyjnego to ze sporym problemem NP. Dlatego trenowanie odbywa się zwykle przy użyciu heurystyki – łatwy do utworzenia algorytm uczenia się, który nie jest optymalny, ale zapewnia jako optymalny schemat decyzyjny.
Większość algorytmów używanych do trenowania drzew decyzyjnych działa z niechęcią różnicą zwycięzcy. Algorytm zaczyna od utworzenia pojedynczego węzła (głównego), rekurencyjnie i zachłannie rozwija drzewo decyzyjne.
W każdym węźle oceniane są wszystkie możliwe warunki i są oceniane. algorytm wybiera „najlepszy”, czyli warunek o najwyższym Jak. Na razie pamiętaj, że wynik to wskaźnik skorelowany z i określone są warunki, które pozwalają zmaksymalizować ten wskaźnik.
Na przykład w Pingwiny (który zawiera przykłady kodu w dalszej części tego kursu), większość Adelie i Chinstrap pingwiny mierzą ponad 16 mm, pingwiny mają mniejsze dzioby. Dlatego warunek bill_length_mm ≥ 16 zapewnia niemal idealne prognozy Pingwiny gentoo, które nie są w stanie rozróżnić między Adelies a Chinstraps. Algorytm prawdopodobnie wybierze ten warunek.
Rysunek 7. Pierwszy krok do hodowli drzewa. .
Algorytm powtarza się następnie rekurencyjnie i niezależnie w obu węzłach podrzędnych. Jeśli nie zostaną znalezione spełnione warunki, węzeł zmieni się w liść. Liść prognoza jest w przykładach określana jako najbardziej reprezentatywna wartość etykiety.
Algorytm ten 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)
Omówmy kroki trenowania określonego drzewa decyzyjnego czyli projektom.
Krok 1. Utwórz pierwiastek główny:
Krok 2. Powiększ węzeł nr 1. Warunek „x1 ≥ 1” został znaleziony. Tworzone są 2 węzły podrzędne:
Krok 3. Powiększ węzeł nr 2. Nie znaleziono spełniających warunków. Niech węzeł w liść:
Krok 4. Powiększ węzeł nr 3. Warunek „x2 ≥ 0,5” został znaleziony. 2 dzieci gdy zostaną utworzone węzły.
Istnieją też inne metody rozwijania drzew decyzyjnych. Popularną alternatywą jest globalną optymalizację węzłów, zamiast stosować strategię dzielenia i pozyskiwania.
growing_strategy="BEST_FIRST_GLOBAL".
Zobacz
zapoznaj się z dokumentacją.
W zależności od liczby i typu cech wejściowych liczba możliwe warunki dla danego węzła mogą być ogromne i zwykle nieskończone. Na przykład w przypadku warunku progowego $\mathrm{feature}_i \geq t$ kombinacji wszystkich funkcji możliwe wartości progowych dla Funkcja $t \in \mathbb{R}$ jest nieskończona.
Rutyna odpowiedzialna za znalezienie najlepszego stanu to tzw. splitter. Ponieważ musi przetestować wiele możliwych warunków, to wąskie gardło w trenowaniu drzewa decyzyjnego.
Wynik zmaksymalizowany przez operatora podziału zależy od zadania. Przykład:
- Zdobywanie informacji i Gini (zarówno omówione później) są powszechnie używane do klasyfikacji.
- Do regresji często stosuje się błąd średniokwadratowy.
Istnieje wiele algorytmów podziału, a każdy z nich obsługuje:
- typ cech, np. liczbowe, kategorialne, tekstowe
- zadanie; na przykład klasyfikacja binarna, wieloklasowa klasyfikacja, regresja
- typ warunku; np. próg, warunek w zestawie, warunek skośny
- kryteria regularyzacji; na przykład dokładne lub przybliżone podziały dla warunków progu
Istnieją również równoważne warianty rozdzielacza o różnych kompromisach. dotyczące wykorzystania pamięci, wykorzystania procesora, dystrybucji obliczeń itd.