Zagadnienia

6.1 Metoda drzew decyzyjnych
- 6.1.1 Wprowadzenie
- 6.1.2 Algorytm

6. Metoda drzew decyzyjnych

6.1. Metoda drzew decyzyjnych

6.1.1. Wprowadzenie

6.1.1.1. Definicje

Jest to struktura drzewiasta, w której
- węzły wewnętrzne zawierają testy na wartościach atrybutów
- z każdego węzła wewnętrznego wychodzi tyle gałęzi, ile jest możliwych wyników testu w tym węzle;
- liście zawierają decyzje o klasyfikacji obiektów
Drzewo decyzyjne koduje program zawierający same instrukcje warunkowe

6.1.1.2. Funkcje testu

x	outlook	Temperature	humidity	wind	play(x)
1	sunny	hot	high	weak	no
2	sunny	hot	high	strong	no
3	overcast	hot	high	weak	yes
4	rain	mild	high	weak	yes
5	rain	cold	normal	weak	yes
6	rain	cold	normal	strong	no
7	overcast	cold	normal	strong	yes
8	sunny	mild	high	weak	no
9	sunny	cold	normal	weak	yes
10	rain	mild	normal	weak	yes
11	sunny	mild	normal	strong	yes
12	overcast	mild	high	strong	yes
13	overcast	hot	normal	weak	yes
14	rain	mild	high	strong	no

Wyróżniamy 2 klasy funkcji testów

Testy operują na wartościach pojedyńczego atrybutu (ang. univariate tree):

$t:V_{a}\rightarrow R_{t};$
Testy będące kombinacją wartości kilku atrybutów (ang. multivariate tree):

$t:V_{{a_{1}}}\times V_{{a_{2}}}\times...\times V_{{a_{k}}}\rightarrow R_{t};$

gdzie

Va : dziedzina atrybutu $a$ ;
Rt : zbiór możliwych wyników testu;

Dla atrybutów nominalnych $a_{i}$ oraz obiektu $x$ :
- test tożsamościowy: $t(x)\rightarrow a_{i}(x)$
- test równościowy: $t(x)=\begin{cases}1&\text{if }(a_{i}(x)=v)\\ 0&\text{otherwise}\end{cases}$
- test przynależnościowy: $t(x)=\begin{cases}1&\text{if }(a_{i}(x)\in V)\\ 0&\text{otherwise}\end{cases}$
Dla atrybutów o wartościach ciągłych:
- test nierównościowy: $t(x)=\begin{cases}1&\text{if }(a_{i}(x)>c)\\ 0&\text{otherwise, i.e., }(a_{i}(x)\leq c)\end{cases}$ gdzie $c$ jest wartością progową lub cięciem

6.1.1.3. Optymalne drzewo

Jakość drzewa ocenia się
- za pomocą rozmiaru: im drzewo jest mniejsze, tym lepsze
  - mała liczba węzłów,
  - mała wysokość, lub
  - mała liczba liści;
- za pomocą dokładności klasyfikacji na zbiorze treningowym
- za pomocą dokładności klasyfikacji na zbiorze testowym
Na przykład:

$Q(T)=\alpha\cdot size(T)+\beta\cdot accuracy(T,P)$

gdzie $\alpha,\beta$ są liczbami rzeczywistymi

size(.) jest rozmiarem drzewa

accuracy(.,.) jest jakością klasyfikacji

\definition

Problem konstrukcji drzew optymalnych: Dane są:

tablica decyzyjna $\mathbb{S}$
zbiór funkcji testów $\bf TEST$ ,
kryterium jakości $Q$

Szukane: drzewo decyzyjne $\mathbf{T}$ o najwyższej jakości $Q(\mathbf{T})$ .

Dla większości parametrów, problem szukania optymalnego drzewa jest NP-trudny !
Wnioski:

Trudno znaleźć optymalne drzewo w czasie wielomianowym;

Konieczność projektowania heurystyk.
Quiz: Czy drzewo z przykładu jest optymalne?

6.1.2. Konstrukcja drzew decyzyjnych

Kryterium stopu: Zatrzymamy konstrukcji drzewa, gdy aktualny zbiór obiektów:
- jest pusty lub
- zawiera obiekty wyłącznie jednej klasy decyzyjnej lub
- nie ulega podziale przez żaden test
Wyznaczenie etykiety zasadą większościową:

$kategoria(P,dec)=\arg\max _{{c\in V_{{dec}}}}|P_{{[dec=c]}}|$

tzn., etykietą dla danego zbioru obiektów jest klasa decyzyjna najliczniej reprezentowana w tym zbiorze.
Kryterium wyboru testu: heurytyczna funkcja oceniająca testy.

6.1.2.1. Kryterium wyboru testu

Każdy zbiór obiektów $X$ ulega podziałowi na klasy decyzyjne:

$X=C_{1}\cup C_{2}\cup...\cup C_{d}$

gdzie $C_{i}=\{ u\in X:dec(u)=i\}$ .

Wektor $(p_{1},...,p_{r})$ , gdzie $p_{i}=\frac{|C_{i}|}{|X|}$ , nazywamy rozkładem klas decyzyjnych w $X$ .

	$\displaystyle Conflict(X)$	$\displaystyle=\sum _{{i<j}}\|C_{i}\|\times\|C_{j}\|=\frac{1}{2}\left(\|X\|^{2}-\sum\|C_{i}\|^{2}\right)$
	$\displaystyle Entropy(X)$	$\displaystyle=-\sum\frac{\|C_{i}\|}{\|X\|}\cdot\log\frac{\|C_{i}\|}{\|X\|}$
		$\displaystyle=-\sum p_{i}\log p_{i}$

Funkcja $conflict(X)$ oraz $Ent(X)$ przyjmują

największą wartość, gdy rozkład klas decyzyjnych w zbiorze $X$ jest równomierny.
najmniejszą wartość, gdy wszystkie obiekty w $X$ są jednej kategorii ( $X$ jest jednorodny)

W przypadku 2 klas decyzyjnych:

	$\displaystyle Conflict(p,1-p)$	$\displaystyle=\|X\|^{2}\cdot p(1-p)$
	$\displaystyle Entropy(p,1-p)$	$\displaystyle=-p\log p-(1-p)\log(1-p)$

Niech $t$ definiuje podział $X$ na podzbiory: $X_{1}\cup...\cup X_{r}$ . Możemy stosować następujące miary do oceniania testów:

liczba par obiektów rozróżnionych przez test t.

$disc(t,X)=conflict(X)-\sum conflict(X_{i})$
kryterium przyrostu informacji (ang. Inf. gain).

$Gain(t,X)=Entropy(X)-\sum _{i}p_{i}\cdot Entropy(X_{i})$

Im większe są wartości tych ocen, tym lepszy jest test.

$N\times\sum _{i}p_{i}\cdot Entropy(X_{i})$

Monotoniczność: Jeśli $t^{{\prime}}$ definiuje drobniejszy podział niż $t$ to

$Gain(t^{{\prime}},X)\geq Gain(t,X)$

(analogiczną sytuację mamy dla miary $conflict()$ .
Funkcje ocen testu $t$ przyjmują małe wartości jeśli rozkłady decyzyjne w podzbiorach wyznaczanych przez $t$ są zbliżone.

Zamiast bezwzględnego przyrostu informacji, stosujemy współczynnik przyrostu informacji

$Gain\_ ratio=\frac{Gain(t,X)}{iv(t,X)}$

gdzie $iv(t,X)$ , zwana wartością informacyjną testu $t$ (information value), jest definiowana jak nast.:

$iv(t,X)=-\sum _{{i=1}}^{{r}}\frac{|X_{i}|}{|X|}\cdot\log\frac{|X_{i}|}{|X|}$

Ocena funkcji testu

Rozróżnialność:

$disc(t,X)=conflict(X)-\sum conflict(X_{i})$
Przyrostu informacji (Information gain).

$Gain(t,X)=Entropy(X)-\sum _{i}p_{i}\cdot Entropy(X_{i})$
Współczynnik przyrostu informacji (gain ratio)

$Gain\_ ratio=\frac{Gain(t,X)}{-\sum _{{i=1}}^{{r}}\frac{|X_{i}|}{|X|}\cdot\log\frac{|X_{i}|}{|X|}}$
Inne (np. Gini's index, test $\chi^{2}$ , …)

6.1.2.2. Przycinanie drzew

Problem nadmiernego dopasowania do danych trenujących (prob. przeuczenia się).
Rozwiązanie:
- zasada najkrótszego opisu: skracamy opis kosztem dokładności klasyfikacji w zbiorze treningowym
- zastąpienie podrzewa nowym liściem (przycinanie) lub mniejszym podrzewem.
Podstawowe pytania:
- Q: Kiedy poddrzewo może być zastąpione liściem?
- A: Jeśli nowy liść jest niegorszy niż istniejące poddrzewo dla nowych obiektów (nienależących do zbioru treningowego).
- Q: Jak to sprawdzić?
- A: Testujemy na próbce zwanej “zbiorem przycinania”!

Niech

$e_{T}(l)$ - błąd klasyfikacji kandydującego liścia l,

$e_{T}(n)$ - błąd klasyfikacji poddrzewa o korzeniu w $n$ .
Przycinanie ma miejsce, gdy

$e_{T}(l)\leq e_{T}(n)+\mu\sqrt{\frac{e_{T}(n)(1-e_{T}(n))}{|P_{{T,n}}|}}$

na ogół przyjmujemy $\mu=1$ .

6.1.2.3. Problem brakujących wartości (ang. null-values)

Możliwe są następujące rozwiązania:

Zredukowanie wartości kryterium wyboru testu (np. przyrostu informacji) dla danego testu o współczynnik równy:

$\frac{\text{liczba obiektów z nieznanymi wartościami}}{\text{liczba wszystkich obiektów}}$
Wypełnienie nieznanych wartości atrybutu najczęściej występującą wartością w zbiorze obiektów związanych z aktualnym węzłem
Wypełnienie nieznanych wartości atrybutu średnią ważoną wyznaczoną na jego zbiorze wartości.

Możliwe rozwiązania:

Zatrzymanie procesu klasyfikacji w aktualnym węźle i zwrócenie większościowej etykiety dla tego węzła (etykiety, jaką ma największą liczbę obiektów trenujących w tym węźle)
Wypełnienie nieznanej wartości według jednej z heurystyk podanych wyżej dla przypadku konstruowania drzewa
Uwzględnienie wszystkich gałęzi (wszystkich możliwych wyników testu) i połączenie odpowiednio zważonych probabilistycznie rezultatatów w rozkład prawdopodobieństwa na zbiorze możliwych klas decyzyjnych dla obiektu testowego.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Systemy decyzyjne