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

  1. ściągnij program C4_5.exe: http://www.cs.put.poznan.pl/mkomosinski/lectures/ML/c45.zip
  2. przejrzyj zawartość plików c4_5.hlp i c45_help.txt. Informacje w nich opisane przydadzą się poniżej.

Zadanie 1. Generowanie drzewa

  1. 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?
  2. 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),
  3. wygeneruj drzewo dla zbioru przykładów "golf" (Tree/Generate); ustawienia standardowe,
  4. przeanalizuj wyniki; czy udało się przeprowadzić pruning?
  5. obejrzyj drzewo. Ile ma węzłów decyzyjnych (warunkowych), a ile liści?
  6. prześledź ścieżkę od korzenia do wybranego liścia,
  7. porównaj estymaty błędu dla drzewa oryginalnego (Unpruned) i uproszczonego (Pruned); zwróć uwagę, że estymata jest podawana dla aktualnie zaznaczonego węzła,
  8. obejrzyj macierz pomyłek (zaleta c4.5: dobre wyniki bez specjalnie długiego ustawiania parametrów).

Zadanie 2. Odpytywanie drzewa (Consult)

  1. spytaj wygenerowane drzewo o dowolny wymyślony przykład
  2. zanotuj estymaty błędu we wszystkich węzłach i – co najważniejsze – liściach
  3. 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
  4. spytaj o przykład “niepełny” (np. tylko outlook=sunny)
  5. spytaj o przykład gdy znany jest rozkład prawdopodobieństwa (np. outook= sunny(0.8), overcast (0.2))
W podpunktach [a, d, e] podaj, skąd wzięły się wyznaczone przez program prawdopodobieństwa decyzji oraz dolne i górne oszacowania (wylicz je na podstawie zanotowanych wartości estymat). Popróbuj z różnymi zapytaniami i w razie potrzeby stwórz własny, minimalny zbiór danych, żeby odkryć/zweryfikować sposób wyliczana tych wartości. Zajrzyj do rozdziału "Tree/Consult" w pliku C45_HELP.TXT.

Zadanie 3. Różnica między gain ratio a gain w praktyce

  1. obejrzyj zbiór testgain (dat i nam)
  2. wygeneruj dla niego dwukrotnie drzewo z użyciem opcji gain ratio i info gain; skomentuj wyniki.

Zadanie 4. Grupowanie wartości atrybutów

  1. wygeneruj drzewo dla zbioru testgain, zaznaczając opcję Subsetting (Criterion pozostaw ustawione na info gain). Jaki wpływ ma użycie grupowania atrybutów?
  2. 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?
  3. 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?
  4. opcjonalnie możesz wykonać taką samą analizę wpływu grupowania także dla zbioru GERMAN.

Zadanie 5. Poszukiwanie optymalnej wielkości drzewa uproszczonego

  1. 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

    ...w funkcji poziomu ufności (odnieś te wyniki do średniej charakterystyki drzewa oryginalnego, nieuproszczonego).

  2. 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).
  3. 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.).

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).

  1. Wyjaśnij zasadę i opcje: Trials, Initial window size, Window increment. Porównaj str. 102/103.
  2. 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

  1. 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.
  2. 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?