Drzewo decyzyjne

Drzewo decyzyjne (1) Proste drzewo decyzyjne
REKLAMA

Tworzenie aplikacji z wykorzystaniem GPT-4 i ChatGPT. Buduj inteligentne chatboty, generatory treści i fascynujące projekty
−40%35,40 zł
Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
29,90 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ż

Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.

Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.

→ Czytaj całość

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość

Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.

Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.

→ Czytaj całość
Polityka prywatnościKontakt