Stosowane symboleL liczba klas
T drzewo decyzyjne
t węzeł drzewa
Tt poddrzewo drzewa T o korzeniu w węźle t
TL zbiór liści drzewa T
|TL| liczba liści drzewa T
m liczba przykładów
mi liczba przykładów, dla których dany atrybut przyjmuje wartość i-tą
mj liczba przykładów klasy cj
Dyskretyzacja wstępująca – kryterium stopu
Dalszego łączenia przedziałów należy zaniechać, gdy:
wartość statystyki 2 przekracza pewien ustalony próg (przedziały zbyt się różnią ze względu na rozkład klas);
liczba pozostałych przedziałów osiągnęła minimalną ustaloną wartość (w praktyce między 5 a 15).
Mniej typowe rozwiązania stosowane podczas konstrukcji drzew decyzyjnych
Stosowanie wielu atrybutów w węzłach drzewa
Inkrementacyjna konstrukcja drzew
Stosowanie globalnych kryteriów optymalizacji
Zastosowanie drzew do aproksymacji
Mniej typowe rozwiązania – wiele cech w węzłach (przykładowe rozwiązanie dla cech ciągłych)
dTx < tak nie Reguła decyzyjna zbudowana jest na podstawie kombinacji liniowej cech źródłowych. d – wektor dyskryminacyjny wyznaczony na podstawie kryterium Fishera
- wartość progowa x – wektor cech
Mniej typowe rozwiązania – wiele cech w węzłach
0123456789 8 012345679 6 01234579 9 0123457 7 012345 4 01235 5 0123 3 012 0 12 2 1 Drzewo oddzielające w każdym węźle jedną klasę
Mniej typowe rozwiązania – wiele cech w węzłach
0123456789 01234569 78 7 8 4 69 469 01235 6 9 5 03 0 3 035 12 1 2 Drzewo dzielące w każdym węźle klasy na grupy
Przykłady zastosowań drzew decyzyjnych - klasyfikacja
Metoda Poprawność [%]
CART 86,2 NewID 85,0 C4.5 85,0 Cal5 84,9 Sekw. kl. Fishera
84,4 AC2 84,3 Rozpoznawanie rodzaju gleby na zdjęciach satelitarnych
6 klas (red soil, cotton crop, grey soil, damp grey soil, veg. Stubble, very damp grey soil)
4435 przykładów w zbiorze uczącym i 2000 w zbiorze testowym
36 cech (po 4 zdjęcia o wym. 33 dla każdego fragmentu terenu)
Przykłady zastosowań drzew decyzyjnych – inżynieria oprogramowania
Klasyfikacja modułów oprogramowania; wykrywanie modułów zawierających znaczną liczbę błędów; przewidywanie przed implementacją czy moduł będzie zawierał znaczną liczbę błędów.
16 systemów od 3000 do 112000 linii kodu (Fortran); 4700 modułów; 32% kodu z poprzednich wersji.
74 atrybuty opisujące nakład pracy na napisanie danego fragmentu, zmiany, styl projektowania, styl programowania, rozmiary, złożoność itd.
Kryterium wybory atrybutu: przyrost informacji.
Kryterium stopu: najwyżej N% przykładów w liściu jest klasyfikowanych błędnie.
Przykłady zastosowań drzew decyzyjnych – rozpoznawanie obrazów
Rozpoznawanie chińskich znaków: 3155 klas, 31550 przykładów w zbiorze uczącym, 9345 w zbiorze testowym.
Cechy wygenerowano na podstawie histogramów oraz transformacji Walsh’a; liczba cech wynosiła 64.
Do wyboru cech użyto miary uwzględniającej wariancje poszczególnych klas oraz całego zbioru danych (wzdłuż wektorów określających poszczególne cechy).
Kryterium stopu: próg błędu.
Najdłuższa ścieżka od korzenia do liścia wynosiła 20, średnia długość ścieżki wynosiła 10.
Osiągnięto poprawność ok. 99%.
Comments