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:
Gdzie
Gdzie,
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