Drzewa decyzyjne

 

Zbiory danych

Do testowania algorytmu konstrukcji drzewa decyzyjnego przygotowane są trzy zbiory danych: lenses, car, tic. Dla każdego z tych zbiorów dostępny jest plik tekstowy zawierający w wierszach kolejne wektory cech (w ostatniej kolumnie numer klasy) oraz plik z opisem danych (atrybuty, klasy). Wartości atrybutów i numery klas muszą być kolejnymi liczbami całkowitymi większymi od zera.

Budowa drzewa decyzyjnego

Do konstrukcji drzewa służy funkcja addnode. Zaimplementowany został w niej algorytm, w którym w każdym węźle wybierany jest atrybut o minimalnej entropii. Skrypt buduj_lenses zawiera wszystkie polecenia związane z przygotowaniem danych, konstrukcją drzewa i  testowaniem.

Struktura drzewa decyzyjnego

Funkcja addnode zwraca drzewo w postaci tablicy, której każda kolumna odpowiada jednemu węzłowi. Liczba wierszy jest o jeden większa od maksymalnej liczby wartości atrybutów. W ostatnim wierszu znajduje się numer atrybutu wykorzystanego w węźle (lub numer klasy gdy węzeł jest liściem). W pozostałych wierszach podane są numery węzłów potomnych (lub zera gdy węzeł jest liściem).

Jeśli np. pewna kolumna ma postać [2 0 4 1]’ to znaczy, że w węźle tym wykorzystano atrybut 1. Dla pierwszej wartości atrybutu z węzła wychodzi gałąź do węzła w 2 kolumnie tablicy, dla drugiej wartości nie ma gałęzi (sytuacja taka może mieć miejsce, gdy w zbiorze uczącym nie było przykładów o tej wartości atrybutu 1), dla trzeciej do węzła w kolumnie 4.

Jeśli kolumna ma postać [0 0 0 3]’ to znaczy, że dany węzeł jest liściem, do którego przypisano klasę 3.

Poza opisaną tablicą skonstruowane drzewo można „narysować” w pliku tekstowym korzystając z funkcji printnode.

Ćwiczenia

1. Otwieramy skrypt buduj_lenses.
   W pierwszym poleceniu należy wpisać ścieżkę i nazwę pliku lenses.txt. Efektem działania pierwszego fragmentu pliku jest podział zbioru danych na zbiór uczący p1 (nieparzyste wiersze) i testowy p2 (parzyste wiersze).
   Następny fragment  odpowiada za tworzenie drzewa (funkcja addnode) i zapisane go w pliku o podanej nazwie.
   Ostatnie instrukcje obliczają błąd klasyfikacji (liczba błędnie klasyfikowanych / liczba wszystkich wektorów) dla zbioru uczącego i testowego.
2. Uruchamiamy skrypt buduj_lenses dla danych lenses.
   Po skonstruowaniu drzewa dostępne są następujące zmienne:
   D – drzewo w postaci tablicy
   p1 – wektory uczące
   klasy1 – numery klas wektorów uczących
   p2 – wektory testowe
   klasy2 – numery klas wektorów testowych
3. Klasyfikacja. Funkcja jakaklasa umożliwia klasyfikację pojedynczego wektora cech
   k = jakaklasa(D,[3 1 2 1 1])
   lub całego zbioru danych
   k = jakaklasa(D,p2)
   Funkcja zwraca dla każdego przykładu numer klasy, lub 0 jeśli przykład nie dotrze do żadnego liścia (podczas obliczania błędu takie przypadki traktowane są jak przykłady błędnej klasyfikacji).

4.      Uruchamiamy skrypt wykres.  Rysowany jest wykres błędu tworzony w miarę rozbudowy drzewa. Błąd dla zbioru uczącego (czerwony) spada do zera (podczas konstrukcji drzewa węzły dzielone są tak długo, aż docierają do nich tylko obrazy jednej klasy). Błąd dla zbioru testowego (niebieski) początkowo spada, a potem zaczyna rosnąć.
Wykres ten ilustruje zjawisko nadmiernego dopasowania drzewa do danych uczących. Widać, że warto byłoby zakończyć konstrukcję drzewa wcześniej.

5.      Analizując drzewo D należy zastanowić się, w którym miejscu należałoby przyciąć drzewo, aby uzyskać mniejszy błąd klasyfikacji.
Pomocna może okazać się funkcja rozklad, która zwraca tablicę zawierającą liczby przykładów poszczególnych klas docierających do poszczególnych węzłów. Element tablicy o współrzędnych (i,j) to liczba obrazów klasy i w węźle j. Wywołanie funkcji:
roz = rozklad(D,Pnauka,KlasyNauka)
Inna funkcja:

g = glebokosc(D)

zwraca głębokość, na której leży każdy z węzłów drzewa D

Błąd klasyfikacji sprawdzamy korzystając z funkcji blad:
blad(D,Pnauka,KlasyNauka) %błąd dla zbioru uczącego
blad(D,Ptest,KlasyTest)   %błąd dla zbioru testowego
Dla drzewa D skonstruowanego dla danych lenses można np. usunąć ostatnie dwie kolumny (dwa liście) pamiętając o zamianie węzła będącego ich poprzednikiem na liść (należy przypisać mu etykietę klasy najliczniej reprezentowanej; w tym wypadku przypisanie etykiety klasy 3 prowadzi do redukcji błędu).

6.      Powtarzamy opisane ćwiczenia dla zbiorów car oraz tic.
- w pliku buduj_lenses.m zmieniamy nazwę zbioru danych
- uruchamiamy skrypt buduj_lenses
- uruchamiamy skrypt wykres
Z wykresów ponownie widać, że wskazane byłoby zmniejszenie drzewa.

Zadanie:

1.      Przycinanie drzewa
Następujące wywołanie funkcji pomocniczej:
usun_galaz(D,nr_wezla)
powoduje wyzerowanie w tablicy D kolumny o numerze nr_wezla oraz wszystkich kolumn odpowiadających potomkom danego węzła (cala gałąź zostaje usunięta). Konieczne będzie jeszcze utworzenie liścia w danym węźle, czyli przypisanie do liścia etykiety klasy – np. najliczniej w nim reprezentowanej.

2.      Po zaimplementowaniu własnej metody przycinania porównujemy błąd  klasyfikacji przed i po przycięciu dla zbioru uczącego oraz testowego. Dla podanego przez prowadzącego  zbioru danych dobieramy metodę przycinania tak, aby jak najbardziej zmniejszyć średni błąd klasyfikacji dla zbioru testowego (poprawić uogólnianie)  niezależnie od zawartości zbioru uczącego – skrypt buduj_xxx.m. Można przy tym dodatkowo podzielić zbiór do uczenia na podzbiór do budowy drzewa i walidacji – sprawdzania jak może wyglądać uogólnianie lub zbudować drzewo wykorzystując wszystkie przykłady do uczenia.

3.      Porównanie drzew decyzyjnych do sieci neuronowych biorąc pod uwagę uogólnianie.

Pliki do pobrania:

Zestaw 1
Zestaw 2
Zestaw 3
Zestaw 4

Zestaw 5