|
|
pl:dydaktyka:ml:2014lab3 [2014/03/17 12:12] esimon [Wczytywanie i analiza danych] |
pl:dydaktyka:ml:2014lab3 [2019/06/27 15:50] |
====== 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. | |
| |
{{:pl:dydaktyka:ml:dt.png|Drzewo decyzyjne}} | |
| |
**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 ===== | |
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 ==== | |
<code> | |
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 | |
</code> | |
| |
**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 ===== | |
[[http://www.cs.waikato.ac.nz/~ml/weka/|Weka]], to narzędzie opensource do data miningu. | |
Uruchom je wykonując polecenie | |
<code> | |
weka | |
</code> | |
| |
==== Wczytywanie i analiza danych ==== | |
- Pobierz paczkę plików z danymi: {{:pl:dydaktyka:ml:data.tar.gz|}} | |
- Otwórz w Gedicie plik o nazwie swimming.arff i poznaj strukturę plików uczących dla weki z danymi symbolicznymi. | |
- Uruchom Wekę i kliknij w przycisk **Explorer** | |
- Przeanalizuj pierwszą zakładkę GUI: \\ {{:pl:dydaktyka:ml:weka-preprocess.png|724}} | |
**Pytania** | |
| |
- Wprowadzenie do weki: | |
- Histotgramy | |
- Nieprzydatne cechy | |
| |
==== Drzewa decyzyjne ==== | |
| |
- J48 (i inne) | |
- Zbudowanie drzewa do przykladu z zajec i do innych | |
- User clasifier | |
- ZeroR | |
| |