Wzmacniane drzewa klasyfikacyjne i regresyjne

Przeszukaj Internetowy Podręcznik Statystyki

Wzmacniane drzewa klasyfikacyjne i regresyjne

Wzmacniane drzewa klasyfikacyjne i regresyjne - Wprowadzenie do stochastycznego wzmacniania gradientowego
Wzmacnianie gradientowe drzew
Problem nadmiernego dopasowania w stochastycznym wzmacnianiu gradientowym
Stochastyczne wzmacnianie gradientowe i klasyfikacja
Duża liczba klas

Wzmacniane drzewa klasyfikacyjne i regresyjne - Wprowadzenie do stochastycznego wzmacniania gradientowego

Ogólne podejście obliczeniowe wzmacnianych drzew jest znane też pod nazwami TreeNet (™Salford Systems, Inc.) oraz MART (™Jerill, Inc.). Na przestrzeni ostatnich kilku lat technika ta rozwinęła się jako jedna z najpotężniejszych metod predykcyjnego data mining. Implementacje tych algorytmów pozwalają z nich korzystać w problemach regresyjnych oraz klasyfikacyjnych, dla predyktorów ilościowych oraz jakościowych. Szczegółowy opis tych metod od strony technicznej można znaleźć w Friedman (1999a, b) oraz w Hastie, Tibshirani i Friedman (2001).

Wzmacnianie gradientowe drzew

Algorytm wzmacnianych drzew rozwinął się z zastosowania metod wzmacniania do drzew regresyjnych [zob. także Ogólne drzewa klasyfikacyjne i regresyjne (GC&RT)]. Główną ideą jest tworzenie ciągu (bardzo) prostych drzew, z których każde kolejne jest zbudowane do predykcji reszt generowanych przez poprzednie. Tak jak to opisano we Wprowadzeniu do Ogólnych drzew klasyfikacyjnych i regresyjnych, metoda buduje drzewa binarne, tzn. dzieli dane na dwie próby w każdym węźle podziału. Przypuśćmy, że mamy ograniczyć złożoność drzew do 3 węzłów (w rzeczywistości użytkownik może ustalać jaka ma być złożoność): tzn. drzewo składa się z korzenia i dwóch potomków czyli jest tylko jeden podział. W kolejnych krokach wzmacniania (algorytmu wzmacniania drzew) określany jest pojedynczy (najlepszy) podział danych i obliczane są odchyłki wartości obserwowanych od średnich (reszty w każdym podziale). Kolejne drzewo o trzech węzłach jest dopasowywane do tych reszt i wyznacza kolejny podział, który jest dopasowywany do tych reszt i wyznacza kolejny podział, przy którym wariancja reszt (czyli błąd) jest jeszcze mniejsza (dla danego wcześniej ciągu drzew).

Można udowodnić, że taka procedura "addytywnego rozwinięcia ważonego" drzew da w efekcie doskonałe dopasowanie wartości przewidywanych do wartości obserwowanych, nawet jeśli sama natura relacji pomiędzy predyktorami a zmienną zależną jest bardzo złożona (np. nieliniowa). Tak więc metoda wzmacniania gradientowego - dopasowania ważonego rozwinięcia addytywnego prostych drzew - jest bardzo ogólnym i mocnym algorytmem uczenia maszyn.

Indeks

Problem nadmiernego dopasowania w stochastycznym wzmacnianiu gradientowym

Jednym z głównych problemów we wszystkich algorytmach uczenia maszyn jest decyzja "kiedy się zatrzymać" i tym samym jak zapobiec nadmiernemu dopasowaniu algorytmu uczącego do nietypowych aspektów konkretnego zbioru uczącego, które wcale nie polepszają mocy predykcyjnej tworzonego modelu. Problem ten znany jest też pod nazwą nadmiernego dopasowania. Jest to ogólny problem, który dotyczy większości algorytmów uczących wykorzystywanych w predykcyjnym data mining.

Ogólne rozwiązanie tego problemu, zastosowane np. w metodach MARSplines oraz w SNN, polega na obliczeniu jakości modelu na podstawie próby testowej utworzonej z danych, które nie były "wykorzystywane" wcześniej do estymacji modelu. W ten sposób mamy nadzieję ocenić trafność prognostyczną utworzonego rozwiązania oraz rozpoznać w którym momencie zaczyna występować nadmierne dopasowanie.

Podobne podejście jest stosowane we wzmacnianych drzewach. Każde kolejne drzewo budowane jest najpierw na podstawie losowej podpróby z całego zbioru danych. Innymi słowy kolejne drzewa tworzone są do predykcji reszt (z wszystkich poprzednich) w próbach wylosowanych niezależnie. Wprowadzenie pewnego stopnia losowości do analizy może służyć jako zabezpieczenie przeciwko przeuczeniu (ponieważ każde kolejne drzewo budowane jest dla innych obserwacji) i daje modele (addytywne ważone rozwinięcia prostych drzew), które mają własność generalizacji i dobrze przewidują nowe obserwacje, tzn. mają dobrą trafność predykcyjną. Technika ta (tzn. wykonywanie obliczeń dla kolejnych niezależnie pobranych prób losowych) nazywana jest stochastycznym wzmacnianiem gradientowym.

Na wykresie poniżej przedstawiony jest wykres funkcji błędu predykcji dla danych uczących oraz dla prób testowych losowanych niezależnie w każdym kroku.

Na tym wykresie można szybko wskazać punkt, w którym model (składający się z pewnej liczby drzew tworzonych w kolejnych krokach) zaczyna wykazywać nadmierne dopasowanie do danych.

Można zauważyć, że błąd predykcji w próbie uczącej stale maleje w miarę dodawania składników do modelu. Jednakże, w okolicach 33 drzew model dla niezależnie pobranej próby testowej zaczyna zachowywać się coraz gorzej. Oznacza to, że w tym miejscu model zaczyna wykazywać nadmierne dopasowanie do danych.

Indeks

Stochastyczne wzmacnianie gradientowe i klasyfikacja

Do tego momentu wzmacniane drzewa omawiane były tylko pod kątem zastosowania do problemów regresyjnych tzn. predykcji ilościowej zmiennej zależnej. Tą technikę można łatwo rozszerzyć na problemy klasyfikacyjne (opis zob. Friedman, 1999a, rozdział 4.6; w szczególności algorytm 6):

Najpierw budowane są różne wzmacniane drzewa dla (dopasowywane do) każdej kategorii lub klasy jakościowej zmiennej zależnej, po utworzeniu zmiennych (wektorów) z kodami 0 i 1, które wskazują czy obserwacja należy do klasy, czy nie. W kolejnych krokach wzmacniania algorytm wykonuje transformację logistyczną (zob. Estymacja nieliniowa) do obliczenia reszt. Przy obliczeniu ostatecznych prawdopodobieństw klasyfikacyjnych, transformacja logistyczna stosowana jest ponownie do wektora predykcji o wartościach kodowanych 0/1. Algorytm opisany jest szczegółowo we Friedman (1999a; zob. także Hastie, Tibshirani i Freedman, 2001, gdzie jest szczegółowy opis tej ogólnej procedury).

Duża liczba klas

Warto zwrócić uwagę, że taka procedura dla problemów klasyfikacyjnych wymaga budowania oddzielnych ciągów (wzmacnianych) drzew dla każdej z klas. Złożoność obliczeniowa rośnie, gdyż rośnie ilość koniecznych rozwiązań prostej regresji liniowej (dla jednej klasy ilościowej zmiennej zależnej). Tak więc nierozsądne jest analizowanie zmiennych jakościowych, które mają ponad 100 klas, powyżej tej liczby obliczenia mogą wymagać bardzo dużych "nakładów" i czasu. Na przykład, w problemie o 200 krokach wzmacniania oraz 100 kategoriach lub klasach zmiennej zależnej daje 200 * 100 = 20000 pojedynczych drzew!

Indeks