Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Systemy decyzyjne – 6. Metoda drzew decyzyjnych – MIM UW

Zagadnienia

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.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.