Uczenie Maszynowe – drzewa decyzyjne
Ćwiczenie | Generowanie drzew decyzyjnych algorytmem C4.5 |
Cel | Ilustracja różnych aspektów budowania drzew decyzyjych i ich weryfikowania |
Zagadnienia |
drzewa decyzyjne, miara info gain, warunki stopu budowy drzewa, upraszczanie drzew, grupowanie wartości |
Narzędzia |
C4.5 for Windows Inne implementacje: Quinlan, Orange, Weka |
Zbiory danych |
GOLF, TESTGAIN, CRX, MONK2, GERMAN |
Zadanie 0. Program i jego opis
- ściągnij program C4_5.exe: http://www.cs.put.poznan.pl/mkomosinski/lectures/ML/c45.zip
- przejrzyj zawartość plików
c4_5.hlp
ic45_help.txt
. Informacje w nich opisane przydadzą się poniżej.
Zadanie 1. Generowanie drzewa
- obejrzyj w dowolnej przeglądarce tekstowej zawartość plików golf.nam, golf.dat i któregoś z plików z rozszerzeniem .tst. Ile przykładów zawiera zbiór uczący? Iloma atrybutami są one opisane?
- załaduj dane "golf"; zwróć uwagę na informacje w tytule głównego okienka - mówią o danych uczących i testowych (jeśli takowe załadowano),
- wygeneruj drzewo dla zbioru przykładów "golf" (Tree/Generate); ustawienia standardowe,
- przeanalizuj wyniki; czy udało się przeprowadzić pruning?
- obejrzyj drzewo. Ile ma węzłów decyzyjnych (warunkowych), a ile liści?
- prześledź ścieżkę od korzenia do wybranego liścia,
- porównaj estymaty błędu dla drzewa oryginalnego (Unpruned) i uproszczonego (Pruned); zwróć uwagę, że estymata jest podawana dla aktualnie zaznaczonego węzła,
- obejrzyj macierz pomyłek (zaleta c4.5: dobre wyniki bez specjalnie długiego ustawiania parametrów).
Zadanie 2. Odpytywanie drzewa (Consult)
- spytaj wygenerowane drzewo o dowolny wymyślony przykład
- zanotuj estymaty błędu we wszystkich węzłach i – co najważniejsze – liściach
- zmień "Pruning confidence level", spytaj o ten sam przykład i znów zanotuj estymaty błędu we wszystkich węzłach i liściach
- spytaj o przykład “niepełny” (np. tylko outlook=sunny)
- spytaj o przykład gdy znany jest rozkład prawdopodobieństwa (np. outook= sunny(0.8), overcast (0.2))
C45_HELP.TXT
.
Zadanie 3. Różnica między gain ratio a gain w praktyce
- obejrzyj zbiór testgain (dat i nam)
- wygeneruj dla niego dwukrotnie drzewo z użyciem opcji gain ratio i info gain; skomentuj wyniki.
Zadanie 4. Grupowanie wartości atrybutów
- wygeneruj drzewo dla zbioru testgain, zaznaczając opcję Subsetting (Criterion pozostaw ustawione na info gain). Jaki wpływ ma użycie grupowania atrybutów?
- analogicznie dla zbioru CRX: opisz problem (wyszukaj w internecie "CRX dataset"), obejrzyj zbiór (atrybuty A4, A6 i A7 mają wiele wartości); wygeneruj drzewo bez i z grupowaniem. Jaki wpływ ma użycie grupowania atrybutów?
- obejrzyj przy okazji macierz pomyłek dla zbioru uczącego i testującego; czy w tym zastosowaniu przydałaby się macierz kosztów pomyłek?
- opcjonalnie możesz wykonać taką samą analizę wpływu grupowania także dla zbioru GERMAN.
Zadanie 5. Poszukiwanie optymalnej wielkości drzewa uproszczonego
- poszukiwanie optymalnej wielkości drzewa uproszczonego przez dobór poziomu ufności procedury upraszczającej (Pruning confidence level); przeprowadź serię eksperymentów 10-krotnego cross-validation dla zbioru Monk2, ze zmieniającym się poziomem ufności od 0.05 do 0.5, z krokiem co najwyżej 0.05. Sporządź wykres zależności:
- średniego (po cross-validation) rozmiaru drzewa uproszczonego,
- średniej trafności klasyfikowania drzewa uproszczonego na zbiorze testującym,
- średniej estymaty błędu dla drzewa uproszczonego
- poszukiwanie optymalnej wielkości drzewa uproszczonego poprzez prepruning, tj. manewrowanie minimalną licznością węzła (Minimum objects). Dla zbioru CRX warto przebadać przedział od 2 (default) do 10 (nie musi być dla cross validation, wystarczy 1 eksperyment).
- analiza wygenerowanego drzewa: poszukiwanie słabych punktów (liści o małym wsparciu, poddrzew które generują szczególnie dużo błędów, etc.).
...w funkcji poziomu ufności (odnieś te wyniki do średniej charakterystyki drzewa oryginalnego, nieuproszczonego).
Zadanie 6. Windowing
Windowing jest jedną z technik próbkowania danych stosowaną pierwotnie w celu ograniczenia zużycia pamięci i czasu uczenia modelu. Może niekiedy polepszać jakość uzyskanych modeli (porównaj: boosting).
- Wyjaśnij zasadę i opcje: Trials, Initial window size, Window increment. Porównaj str. 102/103.
- Przeanalizuj wyniki dla zbioru CRX. Jaki efekt ma wykorzystanie windowing?
Zadanie 7. Generowanie krzywej uczenia
Np. dla zbioru vote (bo ma wymieszane przypadki) – 300+135 przypadków
- przygotuj kilka[naście] zbiorów uczących o liczności n zmieniającej się od 50 do 300, ze skokiem np. 50 przypadków, poprzez wybieranie pierwszych n ze zbioru vote.dat.
- wykreśl jako funkcję n:
- rozmiar drzewa uproszczonego
- trafność klasyfikowania drzewa uproszczonego na zbiorze testującym.
Zadanie 8. Maksymalizacja trafności
Uzyskaj jak najwyższą trafność klasyfikowania dla zbioru GERMAN w eksperymencie 10-fold CV; podaj ją i dostrojone wartości parametrów. Jakimi parametrami i mechanizmami można manipulować (przejrzyj uważnie wszystkie opcje w menu programu), by szukać najwyższej trafności, a jakich nie powinniśmy w tym celu używać? Kiedy można ufać uzyskanej przez takie manipulowanie trafności, a kiedy można mówić o nadużyciu?