Drzewa decyzyjne

Drzewo decyzyjne to graficzna metoda wspomagania procesu decyzyjnego, stosowana w teorii decyzji. Algorytm drzew decyzyjnych jest również stosowany w uczeniu maszynowym do pozyskiwania wiedzy na podstawie przykładów.

Przykład drzewa decyzyjnego

Przykładowe drzewo decyzyjne (dla danych z weather.nominal.arff.zip) zostało przedstawione poniżej.

Drzewo decyzyjne

Pytanie: Jak Twoim zdaniem wyglądałoby drzewo decyzyjne dla zestawu danych poniżej, spróbuj narysować je na kartce.

SkyAirTempHumidityWindWaterForecastEnjoy
sunnywarmnormalstrongwarmsameyes
sunnywarmhighstrongwarmsameyes
rainycoldhighstrongwarmchangeno
sunnywarmhighstrongcoolchangeyes
cloudywarmnormalweakwarmsame yes
cloudycoldhighweakcoolsameno

Algorytm ID3

Algorytm ID3 służy do budowania drzew decyzyjnych. Bazuje on na dwóch parametrach, które wyliczane są dla każdego nowego węzła drzewa decyzyjnego. Parametry te to:

  • Entropia - będąca miarą zróżnicowania danych
  • Przyrost wiedzy (Information Gain) - miara różnicy Entropii przed i po rozbiciu zbioru danych $S$ przy pomocy atrybutu $A$

Entropia

$$H(S) = - \sum_{x \in X} p(x) \log_{2} p(x) $$

Gdzie

  • $S$ - Aktualny zbiór danych dla którego liczona jest entropia (dla każdego węzła drzewa będzie to inny - odpowiednio mniejszy zbiór danych)
  • $X$ - zbiór klas w zbiorze $S$
  • $p(x)$ - Stosunek liczby elementów z klasy $x$ do liczby elementów w zbiorze $S$

Przyrost wiedzy (Information Gain)

$$G(A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|}H(S_v) $$

Gdzie,

  • $H(S)$ - Entropia dla zbioru $S$
  • $Values(A)$ - zbiór wszystkich wartości atrybutu $A$
  • $S_v$ - Podzbiór S, taki że: $S_v = \left \{ s \in S : A(s) = v \right \}$
  • $H(S_v)$ - Entropia podzbioru $S_v$

Algorytm ID3 w pseudokodzie

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples (highest Information Gain).
        Decision Tree attribute for Root = A.
        For each possible value, v_i, of A,
            Add a new tree branch below Root, corresponding to the test A = v_i.
            Let Examples(v_i) be the subset of examples that have the value v_i for A
            If Examples(v_i) is empty
                Then below this new branch add a leaf node with label = most common target value in the examples
            Else below this new branch add the subtree ID3 (Examples(v_i), Target_Attribute, Attributes – {A})
    End
    Return Root

Pytanie Korzystając ze zbioru danych z tabeli z poprzedniej sekcji, policz entropię i przyrost wiedzy dla poszczególnych atrybutów. Uwaga - w przykładzie mamy do czynienia z problemem binarnym, więc sumy ze wzorów tak naprawdę będą tylko dwuelementowe (poza liczeniem information gain dla atrubutu sky).

  • Dla którego z atrybutów entropia jest największa?
  • Dla którego z atrybutów information gain jest największy?
  • Analizując wyniki, czy dobrze wybrałeś(aś) korzeń drzewa w pytaniu z poprzedniej sekcji?

Wprowadzenie do Weki

Weka, to narzędzie opensource do data miningu. Uruchom je wykonując w konsoli polecenie. Jeśli program nie jest zainstalowany, ściagnij go ze strony

$ weka 

Jeśli program nie jest zainstalowany, ściągnij go ze strony: Weka i uruchom:

$ java -jar weka.jar

Wczytywanie i analiza danych

  1. Pobierz paczkę plików z danymi: data.tar.gz
  2. Otwórz w Gedicie plik o nazwie swimming.arff i poznaj strukturę plików uczących dla weki z danymi symbolicznymi.
  3. Uruchom Wekę i kliknij w przycisk Explorer
  4. Przeanalizuj pierwszą zakładkę GUI i odpowiedz na pytania poniżej:

Pytania

  1. Jaki jest rozmiar zbioru uczącego?
  2. Ile atrybutów występuje w zbiorze uczącym?
  3. Ile jest instancji jest pozytywnych (Enjoy=yes) a ile negatywnych?
  4. Który z atrybutów najlepiej rozdziela dane? ;)
  5. Ile elementów ze zbioru danych ma atrybut wilgotność (humidity) ustawioną jako high?

Drzewa decyzyjne

  1. Wczytaj plik swimming.arff ze zbioru danych
  2. Kliknij w zakładkę Clasify
  3. Wybierz za pomocą przycisku Choose klasyfikator Id3.
  4. Upewnij się, że w oknie Test options zaznaczona jest opcja Use training set. Uwaga! W przyszłości nie będziemy korzystać z tej formy testowania - tutaj jesteśmy zmuszeni, z uwagi na niewielki zbiór uczący.
  5. Kliknij w przycisk Start. Przyjrzyj się rezultatowi. Co oznaczają wyniki?
  6. Wybierz za pomocą przycisku Choose klasyfikator J48 i kliknij Start, następnie zwizualizuj drzewo tak jak to pokazano poniżej:
  7. Czy drzewo wygląda tak jak je narysowałeś(aś) na początku laboratorium?

Poprawność klasyfikacji

  1. Załaduj plik credit-g.arff do Weki. Zawiera on dane uczące dla systemu, który na podstawie atrybutów zawartych w pliku powinien określać czy dany zestaw wartości atrybutów wskazuje na wiarygodnego klienta banku, czy też nie - czy można przyznać mu kredyt, czy jest to ryzykowne.
  2. Przejdź do zakładki Classify i wybierz algorytm J48.
  3. W obszarze Test options wybierz opcje Percentage split z wartością 66% Oznacza to, ze 66% danych posłuży do uczenia, a 34% do walidacji. Jakie to ma znaczenie?
  4. Uruchom algorytm. Ile procent przypadków zostało poprawnie zaklasyfikowanych? Czy to dobry wynik?
  5. Zmień klasyfikator na ZeroR z gałęzi rules. Jakie są wyniki?
  6. Wypróbuj inne klasyfikatory. Jakie dają wyniki?
  7. Przejdź do zakładki Preprocess i zobacz jak wygląda rozkład atrybutu określającego czy danych zestaw jest dobry czy zły. Jaka byłaby skuteczność algorytmu który niezależnie od wartości atrybutów „strzelałby” że użytkownik jest wiarygodny?
  8. Dlaczego przed przystąpieniem do klasyfikacji, warto wcześniej przyjrzeć się danym? ;P

User Classifier

  1. Zbuduj drzewo z wykorzystaniem klasyfikatora „User Classifier” dla danych z pliku (użyj PPM do „domknięcia” wielokąta):
  2. Zaakceptuj zbudowane drzewo i zobacz wyniki:
pl/dydaktyka/ml/2014lab3.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0