To jest stara wersja strony!


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 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 w tabeli z poprzedniej sekcji, policz entropię i przyrost wiedzy dla poszczególnych atrybutów.

  • Dla którego z atrybutów entropia jest największa?
  • Dla którego z atrybutów information gain jest największy?
  • Analizujac wyniki, czy dobrze wybrałeś(aś) korzeń drzewa w z poprzedniego pytania?

Wprowadzenie do Weki

  1. Wprowadzenie do weki:
    1. Histotgramy
    2. Nieprzydatne cechy
  2. J48
    1. Zbudowanie drzewa do przykladu z zajec i do innych
    2. User clasifier
    3. ZeroR
pl/dydaktyka/ml/2014lab3.1395053908.txt.gz · ostatnio zmienione: 2019/06/27 15:54 (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