Drzewo decyzyjne

Drzewo decyzyjne (1) Proste drzewo decyzyjne
REKLAMA

Etyczny haking. Praktyczne wprowadzenie do hakingu
−40%53,40 zł
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
−40%53,40 zł

Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.

Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.

Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.

Teoria grafów

Drzewo to taki graf, który jest:

  • prosty – wybraną parę wierzchołków może bezpośrednio łączyć co najwyżej jedna krawędź,
  • spójny – między dowolną parą wierzchołków da się wyznaczyć ścieżkę,
  • acykliczny – taka ścieżka jest dokładnie jedna.

W drzewie decyzyjnym poszczególne węzły (wierzchołki, z których wychodzą co najmniej dwie krawędzie) zawierają proste kryteria podziału, np. sprawdzanie, czy wartość danego atrybutu jest większa od pewnej wartości. Proces decyzyjny rozpoczyna się od węzła określanego jako korzeń. Następnie, w zależności od rezultatu sprawdzania danego kryterium, przechodzi się do kolejnych węzłów. Liście (wierzchołki mające tylko jednego sąsiada) oznaczają końcowe decyzje.

Uczenie maszynowe

Jeśli drzewo ma przewidywać klasę, do której przynależy dany obiekt, jest to drzewo klasyfikacyjne. Jeśli przewidywana jest wartość liczbowa, jest to drzewo regresyjne. Drzewa klasyfikacyjne i regresyjne zbiorczo określane są skrótowcem CART, od ang. Classification and Regression Tree.

Drzewo w uczeniu maszynowym tworzone jest automatycznie na podstawie próbek ze zbioru uczącego. Algorytmy tworzenia drzewa decyzyjnego mogą być różne, polegają one na dodawaniu kolejnych węzłów w taki sposób, aby zbiory próbek mieszczących się w obrębie jednego liścia były jak najbardziej jednorodne. Typowy algorytm budowy drzewa decyzyjnego można zapisać następująco:

  1. Wybierz taki podział zbioru (przez podział rozumiemy atrybut i próg), żeby dwa powstałe w ten sposób podzbiory były jak najbardziej jednorodne. W przypadku drzew klasyfikacyjnych do oceny niejednorodności zbioru często wykorzystywany jest wskaźnik zanieczyszczenia Giniego, w przypadku drzew regresyjnych – odchylenie standardowe.
  2. Dla każdego z otrzymanych podzbiorów:
    1. Jeśli spełniony jest warunek stopu (osiągnięta wystarczająco niska niejednorodność zbioru lub maksymalna głębokość drzewa), utwórz w tym miejscu liść. W przypadku klasyfikacji wartością tego liścia jest ta klasa, która występuje w otrzymanym zbiorze najczęściej. W przypadku regresji zwracaną wartością jest średnia elementów.
    2. W przeciwnym razie wróć do punku 1.

Aby uniknąć przeuczenia, czasami stosuje się dodatkowo mechanizm przycinania (ang. prunning) polegający na tym, żeby usunąć część gałęzi.

Bibliografia

  • P. Gupta, Decision Trees in Machine Learning, Towards Data Science, 2017 [Dostęp 2022-09-17].
  • J. Kozak, P. Juszczuk , Algorytmy do konstruowania drzew decyzyjnych w przewidywaniu skuteczności kampanii telemarketingowej banku, Studia Informatica Pomerania, nr 39 , 2016, s. 49-59, DOI: 10.18276/si.2016.39-05.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 17 września 2022 18:46, ostatnia edycja: 20 września 2022 19:03.

REKLAMA

Zobacz też

Stos (ang. Stack) – struktura danych, w której bezpośredni dostęp jest tylko do ostatnio dodanego elementu. Stos bywa określany także jako kolejka LIFO (z ang. Last In, First Out, czyli: ostatni na wejściu, pierwszy na wyjściu). Stos można sobie wyobrazić jako kilka rzeczy ułożonych „jedna na drugiej” – łatwo można wziąć tylko rzecz leżącą na samym wierzchu, gdyż pozostałe są przykryte.

→ Czytaj całość

Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.

→ Czytaj całość

Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).

→ Czytaj całość
Polityka prywatnościKontakt