ADIUM/L/z2

Na zajęciach

Wczytać zbiór do klasyfikacji wina z repozytorium UCI. Pierwszą kolumnę, przechowującą numer klasy wina, przesunać aby stała się ostatnią.

Napisać skrypt dzielący podany na wejście zbiór danych w sposób losowy na dwa podzbiory: uczący i testowy w zadanej na wejście proporcji (np.: 70%, 80%, itp.). Skrypt ma zwracać na wyjściu wydzielone podzbiory. Sugestia: losowość wierszy --- które trafią do zbioru uczącego, a które do testowego --- można zrealizować za pomocą polecenia randperm.

Na podstawie informacji z wykładu:

Napisać trzy skrypty wyliczające tzw. "nieczystość" węzła (poddziedziny), każdy w innej wersji, jako: (1) błąd klasyfikacji, (2) entropię warunkową, (3) indeks Gini'ego.

Napisać skrypt, który dla podanego na wejście zbioru danych (w szczególności tylko dla części uczącej) i wybranej funkcji nieczystości buduje rekurencyjnie pełne drzewo CART. Sugestia: drzewo można reprezentować sobie jako macierz, tj. każdy wiersz macierzy byłby węzłem w drzewie, a kolejne kolumny mogą trzymać następujące informacje: (1) czy węzeł jest liściem, (2) nr zmiennej, na której "rozcięcie", (3) wartość "rozcięcia", (4) nr wiersza lewego dziecka, (5) nr wiersza prawego dziecka, (6) nr klasy (skojarzonej z tym węzłem). W razie potrzeb można oczywiście przechować więcej kolumn z dodatkowymi informacjami (np. nr wiersza rodzica).

Napisać skrypt do klasyfikacji pojedynczego punktu (wektora) x za pomocą drzewa CART. Skrypt, poczynając od korzenia drzewa, powinien "przesiewać" punkt wejściowy w dół drzewa, idąc odpowiednio w lewo lub w prawo, i zwracać nr klasy w momencie, gdy dojdzie do liścia.

Napisać skrypt, który za pomocą poprzedniego skryptu do klasyfikacji pojedynczego punktu, wykona zbiorczą klasyfikację wielu punktów (np. całej części uczącej lub całej części testowej). Skrypt ma zwracać odsetek poprawnych klasyfikacji. Za pomocą tego skryptu obliczyć poprawność klasyfikacji pełnego drzewa na części uczącej i testowej.

Zrealizowanie powyższych punktów jest na ocenę: 0.6. Poniższe punkty na pełną ocenę.

Napisać skrypt, który na wejście przyjmuje pełne drzewo CART i ustaloną wartość kary za 1 liść (lambda). Skrypt ten ma rekurencyjnie przebiegać wszystkie możliwe poddrzewa pełnego drzewa i każdemu z nich wystawiać liczbową ocenę heurystyczą: błąd klasyfikacji + liczba liści * kara za 1 liść. Jako wynik skrypt ma zwracać drzewo optymalne w sensie tej heurystyki (czyli o minimalnej jej wartości). Sugestia: wygodnie jest wykorzystać z poziomu MATLABA klasę Javy: java.util.HashMap. Wartości heurystyki i same poddrzewa można wówczas przechowywać właśnie w hashmapach. Dzięki temu mamy też małą złożoność wkładania i wyciągania elementów do/z hashmapy - dokładnie O(1) - czyli "natychmiast". Kluczami w hashmapach mogą być np. numery wierszy z pełnego drzewa biorące udział w poddrzewie (np. posortowane i zamienione dla wygody na string).

Napisać skrypt, który na wejście przyjmuje pełne drzewo CART i zbiór możliwych wartości kary z 1 liść (zbiór lambd). Skrypt ten za pomocą poprzedniego skryptu i procedury kroswalidacji (podanej na wykładzie), ma znajdować optymalną wartość kary i optymalne przycięte drzewo CART.

Dla znalezionego przyciętego drzewa obliczyć poprawność klasyfikacji na częściach uczącej i testowej. Porównać te wyniki z wynikami dla pełnego drzewa.