Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:ml:2014lab3 [2014/03/17 11:35] esimon [Algorytm ID3] |
pl:dydaktyka:ml:2014lab3 [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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_{t \in T} p(t)H(t) $$ | ||
| - | |||
| - | Gdzie, | ||
| - | * $H(S)$ - Entropia dla zbioru $S$ | ||
| - | * $T$ - Podzbiór powstały z rozbicia zbioru $S$ przez atrybut $A$, w taki sposób, że $S = \bigcup_{t \in T} t$ | ||
| - | * $p(t)$ - Stosunek ilości elementów w $t$ do ilości elementów w $S$ | ||
| - | * $H(t)$ - Entropia podzbioru $t$ | ||
| - | |||
| - | ==== Algorytm ID3 ==== | ||
| - | <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> | ||
| - | |||
| - | - Zasady budowania drzewa - algorytm ID3 | ||
| - | - Policz entropię i informaiton gain - wyznacz korzeń drzewa. | ||
| - | |||
| - | ===== Wprowadzenie do Weki ===== | ||
| - | - Wprowadzenie do weki: | ||
| - | - Histotgramy | ||
| - | - Nieprzydatne cechy | ||
| - | - J48 | ||
| - | - Zbudowanie drzewa do przykladu z zajec i do innych | ||
| - | - User clasifier | ||
| - | - ZeroR | ||
