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ładowe drzewo decyzyjne dla danych z zestawu poniżej:

@relation weather.symbolic

@attribute outlook {sunny, overcast, rainy}
@attribute temperature {hot, mild, cool}
@attribute humidity {high, normal}
@attribute windy {TRUE, FALSE}
@attribute play {yes, no}

@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no

Algorytm ID3 służący do budowania drzew decyzyjnych bazuja na dwóch parametrach, które można wyliczyć bezpośrednio ze zbioru uczącego:

• Entropii - będącej miarą zróżnicowania danych
• Przyrostu wiedzy (Information Gain) - miara różnicy Entropii przed i po rozbiciu zbioru danych przy pomocy atrybutu

Gdzie

• - 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)
• - zbiór klas w zbiorze
• - Stosunek liczby elementów z klasy do liczby elementów w zbiorze

Gdzie,

• - Entropia dla zbioru
• - Podzbiór powstały z rozbicia zbioru przez atrybut , w taki sposób, że
• - Stosunek ilości elementów w do ilości elementów w
• - Entropia podzbioru

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

1. Zasady budowania drzewa - algorytm ID3
2. Policz entropię i informaiton gain - wyznacz korzeń drzewa.

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