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 weather.nominal.arff.zip) zostało przedstawione poniżej.
Pytanie: Jak Twoim zdaniem wyglądałoby drzewo decyzyjne dla zestawu danych poniżej, spróbuj narysować je na kartce.
| Sky | AirTemp | Humidity | Wind | Water | Forecast | Enjoy |
|---|---|---|---|---|---|---|
| sunny | warm | normal | strong | warm | same | yes |
| sunny | warm | high | strong | warm | same | yes |
| rainy | cold | high | strong | warm | change | no |
| sunny | warm | high | strong | cool | change | yes |
| cloudy | warm | normal | weak | warm | same | yes |
| cloudy | cold | high | weak | cool | same | no |
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:
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 
- zbiór wszystkich wartości atrybutu 
- Podzbiór S, taki że: 
- 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
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).
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
Pytania
