Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:ml:2014lab3 [2014/03/17 11:35] esimon [Algorytm ID3] |
pl:dydaktyka:ml:2014lab3 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 2: | Linia 2: | ||
| //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.// | //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ład drzewa decyzyjnego ===== | ||
| - | Przykładowe drzewo decyzyjne zostało przedstawione poniżej. | + | Przykładowe drzewo decyzyjne (dla danych z {{:pl:dydaktyka:ml:weather.nominal.arff.zip|}}) zostało przedstawione poniżej. |
| {{:pl:dydaktyka:ml:dt.png|Drzewo decyzyjne}} | {{:pl:dydaktyka:ml:dt.png|Drzewo decyzyjne}} | ||
| Linia 33: | Linia 33: | ||
| ==== Przyrost wiedzy (Information Gain) ==== | ==== Przyrost wiedzy (Information Gain) ==== | ||
| - | $$G(A) = H(S) - \sum_{t \in T} p(t)H(t) $$ | + | $$G(A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|}H(S_v) $$ |
| Gdzie, | Gdzie, | ||
| * $H(S)$ - Entropia dla zbioru $S$ | * $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$ | + | * $Values(A)$ - zbiór wszystkich wartości atrybutu $A$ |
| - | * $p(t)$ - Stosunek ilości elementów w $t$ do ilości elementów w $S$ | + | * $S_v$ - Podzbiór S, taki że: $S_v = \left \{ s \in S : A(s) = v \right \}$ |
| - | * $H(t)$ - Entropia podzbioru $t$ | + | * $H(S_v)$ - Entropia podzbioru $S_v$ |
| - | ==== Algorytm ID3 ==== | + | ==== Algorytm ID3 w pseudokodzie ==== |
| <code> | <code> | ||
| ID3 (Examples, Target_Attribute, Attributes) | ID3 (Examples, Target_Attribute, Attributes) | ||
| Linia 62: | Linia 62: | ||
| </code> | </code> | ||
| - | - Zasady budowania drzewa - algorytm ID3 | + | **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//). |
| - | - Policz entropię i informaiton gain - wyznacz korzeń drzewa. | + | * Dla którego z atrybutów entropia jest największa? |
| + | * Dla którego z atrybutów //information gain// jest największy? | ||
| + | * Analizując wyniki, czy dobrze wybrałeś(aś) korzeń drzewa w pytaniu z poprzedniej sekcji? | ||
| ===== Wprowadzenie do Weki ===== | ===== Wprowadzenie do Weki ===== | ||
| - | - Wprowadzenie do weki: | + | [[http://www.cs.waikato.ac.nz/~ml/weka/|Weka]], to narzędzie opensource do data miningu. |
| - | - Histotgramy | + | Uruchom je wykonując w konsoli polecenie. Jeśli program nie jest zainstalowany, ściagnij go ze strony |
| - | - Nieprzydatne cechy | + | <code> |
| - | - J48 | + | $ weka |
| - | - Zbudowanie drzewa do przykladu z zajec i do innych | + | </code> |
| - | - User clasifier | + | |
| - | - ZeroR | + | Jeśli program nie jest zainstalowany, ściągnij go ze strony: [[http://www.cs.waikato.ac.nz/~ml/weka/|Weka]] i uruchom: |
| + | <code> | ||
| + | $ java -jar weka.jar | ||
| + | </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 i odpowiedz na pytania poniżej: \\ {{:pl:dydaktyka:ml:weka-preprocess.png?600|}} | ||
| + | **Pytania** | ||
| + | - Jaki jest rozmiar zbioru uczącego? | ||
| + | - Ile atrybutów występuje w zbiorze uczącym? | ||
| + | - Ile jest instancji jest pozytywnych (//Enjoy=yes//) a ile negatywnych? | ||
| + | - Który z atrybutów najlepiej rozdziela dane? ;) | ||
| + | - Ile elementów ze zbioru danych ma atrybut wilgotność (//humidity//) ustawioną jako //high//? | ||
| + | |||
| + | ==== Drzewa decyzyjne ==== | ||
| + | - Wczytaj plik swimming.arff ze zbioru danych | ||
| + | - Kliknij w zakładkę **Clasify** | ||
| + | - Wybierz za pomocą przycisku **Choose** klasyfikator Id3. | ||
| + | - Upewnij się, że w oknie //Test options// zaznaczona jest opcja //Use training set//. Uwaga! W przyszłości **nie** będziemy korzystać z tej formy testowania - tutaj jesteśmy zmuszeni, z uwagi na niewielki zbiór uczący. | ||
| + | - Kliknij w przycisk **Start**. Przyjrzyj się rezultatowi. Co oznaczają wyniki? \\ {{:pl:dydaktyka:ml:weka-clasify-1.png?600|}} | ||
| + | - Wybierz za pomocą przycisku **Choose** klasyfikator J48 i kliknij **Start**, następnie zwizualizuj drzewo tak jak to pokazano poniżej: \\ {{:pl:dydaktyka:ml:weka-visualize-tree.png?600|}} | ||
| + | - Czy drzewo wygląda tak jak je narysowałeś(aś) na początku laboratorium? \\ {{:pl:dydaktyka:ml:tree-begining.png|}} | ||
| + | |||
| + | ==== Poprawność klasyfikacji ==== | ||
| + | - Załaduj plik {{:pl:dydaktyka:ml:credit-g.arff.gz|credit-g.arff}} do Weki. Zawiera on dane uczące dla systemu, który na podstawie atrybutów zawartych w pliku powinien określać czy dany zestaw wartości atrybutów wskazuje na wiarygodnego klienta banku, czy też nie - czy można przyznać mu kredyt, czy jest to ryzykowne. | ||
| + | - Przejdź do zakładki **Classify** i wybierz algorytm J48. | ||
| + | - W obszarze //Test options// wybierz opcje //Percentage split// z wartością 66% Oznacza to, ze 66% danych posłuży do uczenia, a 34% do walidacji. Jakie to ma znaczenie? | ||
| + | - Uruchom algorytm. Ile procent przypadków zostało poprawnie zaklasyfikowanych? Czy to dobry wynik? | ||
| + | - Zmień klasyfikator na //ZeroR// z gałęzi //rules//. Jakie są wyniki? | ||
| + | - Wypróbuj inne klasyfikatory. Jakie dają wyniki? | ||
| + | - Przejdź do zakładki **Preprocess** i zobacz jak wygląda rozkład atrybutu określającego czy danych zestaw jest //dobry// czy //zły//. Jaka byłaby skuteczność algorytmu który niezależnie od wartości atrybutów "strzelałby" że użytkownik jest wiarygodny? | ||
| + | - Dlaczego przed przystąpieniem do klasyfikacji, warto wcześniej przyjrzeć się danym? ;P | ||
| + | |||
| + | ==== User Classifier ==== | ||
| + | - Zbuduj drzewo z wykorzystaniem klasyfikatora "User Classifier" dla danych z pliku (użyj PPM do "domknięcia" wielokąta): \\ {{:pl:dydaktyka:ml:polygon.png|}} | ||
| + | - Zaakceptuj zbudowane drzewo i zobacz wyniki:\\ {{:pl:dydaktyka:ml:user-accept.png|}} | ||
| + | |||
| + | |||
