Drzewo decyzyjne

Drzewo decyzyjne (1) Proste drzewo decyzyjne
REKLAMA

ChatGPT. Podstawy i proste zastosowania
−40%29,94 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ż

Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.

Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.

Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:

  • Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
  • Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).

Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.

→ Czytaj całość

Algorytm Bellmana-Forda – 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. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość
Polityka prywatnościKontakt