• 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

Wyróżniamy 2 klasy funkcji testów

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

  t:Va→Rt;

• Testy będące kombinacją wartości kilku atrybutów (ang. multivariate tree):

  t:Va1×Va2×…×Vak→Rt;

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: t⁢x→ai⁢x

  • test równościowy: t⁢x=1if ai⁢x=v0otherwise

  • test przynależnościowy: t⁢x=1if ai⁢x∈V0otherwise

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

  • test nierównościowy: t⁢x=1if ai⁢x>c0otherwise, i.e., ai⁢x≤c gdzie c jest wartością progową lub cięciem

• 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=α⋅s⁢i⁢z⁢e⁢T+β⋅a⁢c⁢c⁢u⁢r⁢a⁢c⁢y⁢T,P

  gdzie α,β są liczbami rzeczywistymi

  size(.) jest rozmiarem drzewa

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

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 Q⁢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?

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

gdzie Ci=u∈X:d⁢e⁢c⁢u=i.

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

Funkcja c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢X oraz E⁢n⁢t⁢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:

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

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

  d⁢i⁢s⁢c⁢t,X=c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢X-∑c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢Xi

• kryterium przyrostu informacji (ang. Inf. gain).

  G⁢a⁢i⁢n⁢t,X=E⁢n⁢t⁢r⁢o⁢p⁢y⁢X-∑ipi⋅E⁢n⁢t⁢r⁢o⁢p⁢y⁢Xi

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

• Monotoniczność: Jeśli t′ definiuje drobniejszy podział niż t to

  G⁢a⁢i⁢n⁢t′,X≥G⁢a⁢i⁢n⁢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

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

Ocena funkcji testu

• Rozróżnialność:

  d⁢i⁢s⁢c⁢t,X=c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢X-∑c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢Xi

• Przyrostu informacji (Information gain).

  G⁢a⁢i⁢n⁢t,X=E⁢n⁢t⁢r⁢o⁢p⁢y⁢X-∑ipi⋅E⁢n⁢t⁢r⁢o⁢p⁢y⁢Xi

• Współczynnik przyrostu informacji (gain ratio)

  G⁢a⁢i⁢n⁢_⁢r⁢a⁢t⁢i⁢o=G⁢a⁢i⁢n⁢t,X-∑i=1rXiX⋅log⁡XiX

• Inne (np. Gini's index, test χ2, …)

• 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

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

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

• Przycinanie ma miejsce, gdy

  eT⁢l≤eT⁢n+μ⁢eT⁢n⁢1-eT⁢nPT,n

  na ogół przyjmujemy μ=1.

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.