[[
✎ pl:dydaktyka:ml:2014lab3
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== 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|}} - Wprowadzenie do weki: - Histotgramy - Nieprzydatne cechy ==== Drzewa decyzyjne ==== - J48 (i inne) - Zbudowanie drzewa do przykladu z zajec i do innych - User clasifier - ZeroR
pl/dydaktyka/ml/2014lab3.1395054236.txt.gz
· ostatnio zmienione: 2019/06/27 15:54 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry