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:VaRt;
  • Testy będące kombinacją wartości kilku atrybutów (ang. multivariate tree):

    t:Va1×Va2××VakRt;

gdzie

  • Va : dziedzina atrybutu a;

  • Rt : zbiór możliwych wyników testu;

  • Dla atrybutów nominalnych ai oraz obiektu x:

    • test tożsamościowy: txaix

    • test równościowy: tx=1if aix=v0otherwise

    • test przynależnościowy: tx=1if aixV0otherwise

  • Dla atrybutów o wartościach ciągłych:

    • test nierównościowy: tx=1if aix>c0otherwise, i.e., aixc 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:

    QT=αsizeT+βaccuracyT,P

    gdzie α,β są liczbami rzeczywistymi

    size(.) jest rozmiarem drzewa

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

\definition

Problem konstrukcji drzew optymalnych: Dane są:

  • tablica decyzyjna S

  • zbiór funkcji testów TEST,

  • kryterium jakości Q

Szukane: drzewo decyzyjne T o najwyższej jakości QT.

  • 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ą:

    kategoriaP,dec=argmaxcVdecP[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=C1C2Cd

gdzie Ci=uX:decu=i.

Wektor p1,,pr, gdzie pi=CiX, nazywamy rozkładem klas decyzyjnych w X.

ConflictX=i<j|Ci|×|Cj|=12(|X|2-|Ci|2)
EntropyX=-CiXlogCiX
=-pilogpi

Funkcja conflictX oraz EntX 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:

Conflictp,1-p=X2p1-p
Entropyp,1-p=-plogp-1-plog1-p

Niech t definiuje podział X na podzbiory: X1Xr. Możemy stosować następujące miary do oceniania testów:

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

    disct,X=conflictX-conflictXi
  • kryterium przyrostu informacji (ang. Inf. gain).

    Gaint,X=EntropyX-ipiEntropyXi

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

N×ipiEntropyXi
  • Monotoniczność: Jeśli t definiuje drobniejszy podział niż t to

    Gaint,XGaint,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=Gaint,Xivt,X

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

ivt,X=-i=1rXiXlogXiX

 

Ocena funkcji testu

  • Rozróżnialność:

    disct,X=conflictX-conflictXi
  • Przyrostu informacji (Information gain).

    Gaint,X=EntropyX-ipiEntropyXi
  • Współczynnik przyrostu informacji (gain ratio)

    Gain_ratio=Gaint,X-i=1rXiXlogXiX
  • Inne (np. Gini's index, test χ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

    eTl - błąd klasyfikacji kandydującego liścia l,

    eTn - błąd klasyfikacji poddrzewa o korzeniu w n.

  • Przycinanie ma miejsce, gdy

    eTleTn+μeTn1-eTnPT,n

    na ogół przyjmujemy μ=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:

    liczba obiektów z nieznanymi wartościamiliczba 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.