© Copyright StatSoft, Inc., 1984-2024
Przeszukaj Internetowy Podręcznik Statystyki
Drzewa klasyfikacyjne i regresyjne (C&RT)

Wprowadzenie do drzew klasyfikacyjnych i regresyjnych - Podstawowe idee

Wprowadzenie

Modele drzew klasyfikacyjnych i regresyjnych (Classification and Regression Trees - C&RT) umożliwia zarówno budowę modeli służących do rozwiązywania problemów regresyjnych (gdzie zmienną zależną jest cecha ilościową) jak i klasyfikacyjnych (jakościowa zmienna zależna). Klasyczny algorytm C&RT został rozpropagowany przez Briemana i innych (Breiman, Friedman, Olshen i Stone, 1984; zobacz również Ripley, 1996), Ogólne wprowadzenie do drzew klasyfikacyjnych, w szczególności do algorytmu QUEST (Quick, Unbiased, Efficient Statistical Trees) zostało również przedstawione w temacie Właściwości drzew klasyfikacyjnych i poniższe omówienie powtarza to samo, w nieco innym kontekście. Innym algorytmem budowy drzew jest CHAID (Chi-square Automatic Interaction Detector, patrz Kass 1980).

Zagadnienia klasyfikacyjne i regresyjne

Jest wiele algorytmów, których celem jest predykcja wartości zmiennych ciągłych lub kategorialnych, na podstawie zestawu predykcyjnych zmiennych ciągłych lub kategorialnych efektów czynnikowych. Na przykład, w GLM (Ogólne modele liniowe) i GRM (Ogólne modele regresji), określić możemy liniową kombinację (plan) ciągłych predyktorów i kategorialnych efektów czynnikowych (np. z interakcjami drugiego i trzeciego rzędu) do predykcji ciągłej zmiennej zależnej. W GDA (Ogólne modele analizy dyskryminacyjnej), takie plany określamy dla predykcji zmiennej kategorialnej, rozwiązując problem klasyfikacyjny.

Zagadnienia regresyjne. Z regresją mamy do czynienie tam, gdzie chcemy poznać wartość zmiennej ciągłej, na podstawie znajomości wartości jednej lub większej liczby predykcyjnych zmiennych ciągłych oraz, ewentualnie zmiennych kategorialnych. Na przykład, interesuje nas cena domu (ciągła zmienna zależna), przy czym znamy różne ciągłe predyktory (jak np. powierzchnia mieszkania), jak i predyktory kategorialne (jak np. styl architektoniczny, dzielnica miasta, albo kod pocztowy - zmienna na pozór liczbowa, a jednak, w istocie raczej kategorialna). Używając do predykcji ceny domu prostej regresji wielorakiej lub ogólnego modelu liniowego (GLM), poszukujemy linowego równania, za pomocą którego obliczymy interesującą nas cenę. Jest wiele różnych procedur analitycznych dopasowywania do danych liniowych modeli (GLM, GRM, Regresja), modeli nieliniowych (np. Uogólnione modele liniowe i nieliniowe (GLZ), Uogólnione modele addytywne (GAM), itp.), a także modeli nieliniowych, w pełni określanych przez użytkownika (patrz Estymacja nieliniowa), gdzie wpisać można dowolne równanie zawierające parametry, których wartości znajdzie program.
CHAID również wykonuje analizy regresyjne, których wyniki są analogiczne do otrzymywanych w C&RT. Zauważmy, że do regresji wykorzystać można też sieci neuronowe.

Zagadnienia klasyfikacyjne. Klasyfikacja pojawia się tam, gdzie mamy kategorialną zmienną zależną, której wartość (czyli przynależność przypadku do klasy, grupy) chcemy poznać na podstawie znajomości wartości jednej lub większej liczby predykcyjnych zmiennych ciągłych oraz, ewentualnie zmiennych kategorialnych. Na przykład, interesuje nas przewidywanie, czy student otrzyma, czy nie otrzyma dyplomu, czy czytelnik przedłuży prenumeratę, czy nie, itp. To są przykłady prostej klasyfikacji binarnej, gdzie zależna zmienna kategorialna przyjmuje tylko dwie, wyłączające się nawzajem wartości. Jednak może nas też interesować, którego z producentów samochodów wybierze dany klient, albo jakie uszkodzenie wystąpi najprawdopodobniej w danym typie silnika. Tu mamy wiele kategorii, czy klas w zależnej zmiennej kategorialnej. Jest wiele metod analizowania problemów klasyfikacyjnych i predykcji klasy, zarówno na podstawie prostych predyktorów ciągłych (np. dwu- i wielomianowe modele logitowe w GLZ), predyktorów skategoryzowanych (np. analiza log-liniowa tabel wielodzielczych) albo z wykorzystaniem zmiennych obu typów jednocześnie (np. w planach typu ANCOVA, w GLZ lub GDA. Ogólne modele CHAID również analizują problemy klasyfikacyjne, dając wyniki podobnego typu jak w C&RT. Zauważmy, że do klasyfikacji wykorzystać można też sieci neuronowe.

Drzewa klasyfikacyjne i regresyjne (C&RT - Classification and Regression Trees)

Najogólniej, celem analizy z zastosowaniem algorytmu budowy drzew jest znalezienie zbioru logicznych warunków podziału, typu jeżeli, to, prowadzących do jednoznacznego zaklasyfikowania obiektów.

Drzewa klasyfikacyjne

Rozpatrzmy szeroko wykorzystywany przykład danych o klasyfikowaniu irysów (kwiatów kosaćca; Fisher 1936; patrz też pojęcie analiza funkcji dyskryminacyjnej oraz opis metody Analiza funkcji dyskryminacyjnej (GDA)). W pliku danych Irisdat podane są długości i szerokości działek kielicha i płatków trzech odmian irysa (Setosa, Versicol i Virginic). Celem analizy jest znalezienie sposobu przypisania kwiatu do jednej z trzech odmian, na podstawie zmierzonych czterech, różnych jego rozmiarów. W analizie funkcji dyskryminacyjnej znajdowanych jest kilka kombinacji liniowych zmiennych predykcyjnych (tu: długości), pozwalających obliczyć prawdopodobieństwo przynależności do klas, co z kolei, pozwala wybrać najbardziej prawdopodobną klasę dla danego obiektu. Natomiast drzewo klasyfikacyjne, to zbiór warunków logicznych (zamiast równania liniowego) pozwalających zaklasyfikować obiekt:

Interpretacja drzewa jest bezpośrednia: Jeżeli szerokość płatka jest mniejsza lub równa 0,8, to kwiat klasyfikujemy jako Setosa; jeżeli natomiast szerokość płatka jest większa od 0,8, a przy tym mniejsza lub równa 1,75, to kwiat jest zapewne odmiany Virginic; w przeciwnym wypadku jest to Versicol.


Drzewa regresyjne

Ogólna zasada otrzymywania predykcji na podstawie kilku prostych warunków logicznych, daje się też zastosować do zagadnień regresyjnych. Odwołajmy się do przykładu bazującego na danych z pliku Poverty, zawierającego wyniki spisów ludności z roku 1960 i 1970, z losowo wybranych 30 hrabstw. Problem badawczy (w tamtym przykładzie) to znalezienie przyczyn ubóstwa, to znaczy zmiennych, które najlepiej przewidują procent rodzin poniżej progu ubóstwa, w hrabstwach. Bieżąca analiza tych danych, za pomocą drzew regresyjnych określa najlepsze drzewo, z którego wynika co następuje:

Podobnie jak poprzednio i tu interpretacja wyniku jest raczej bezpośrednia: hrabstwa o procencie gospodarstw z telefonem przewyższającym 72% mają z reguły niższy procent ubóstwa. Największe ubóstwo jest w hrabstwach, w których telefonów jest mniej niż 72%, a ponadto zmiana populacji jest na poziomie poniżej -8,3 (szybko ubywa ludzi). Jest to wynik klarowny, łatwy do przedstawienia: są bogate okolice, gdzie niemal wszyscy mają telefon i biedne, bez telefonu, które się wyludniają.

Spojrzenie na wykres rozrzutu wartości przewidywanych względem obserwowanych wystarcza by ocenić jak wyraźnie model rozdziela dwie ostatnie grupy hrabstw.


Zalety metody drzew klasyfikacyjnych i regresyjnych (C&RT)

Jak to wcześniej zaznaczono, jest wiele metod analizy problemów klasyfikacyjnych i regresyjnych, z których może skorzystać analityk. Drzewa klasyfikacyjne, jeśli tylko "działają" i dają dobre predykcje na podstawie kilku warunków, mają wiele zalet w stosunku do innych technik.

Prostota wyników. W większości przypadków interpretacja wyników w postaci drzewa jest bardzo prosta. Ta prostota jest cenna nie tylko dlatego, że nowe przypadki są szybko klasyfikowane (łatwiej sprawdzić kilka warunków logicznych niż obliczać jakąś statystykę klasyfikacyjną dla każdej możliwej grupy lub przewidywanej wartości na podstawie wartości predyktorów w modelu wykorzystującym skomplikowane równania nieliniowe), lecz także z powodu znacznie prostszego "modelu" wyjaśniającego dlaczego obserwacje są klasyfikowane lub przewidywane w taki sposób a nie inny (np. w analizie problemów biznesowych łatwiej przedstawić kilka warunków jeżeli-to niż jakieś skomplikowane równania).

Metody drzew klasyfikacyjnych są nieparametryczne i nieliniowe. Wyniki wykorzystujące metody drzew klasyfikacyjnych i regresyjnych dają się ująć w postaci kilku (zazwyczaj niewielu) warunków logicznych typu jeżeli-to (z węzłów drzewa). Nie ma więc na wstępie żadnego założenia, co do natury związku pomiędzy predyktorami a zmienną zależną - czy jest on liniowy, czy też związek ten modeluje konkretna funkcja wiążąca [zob. np. Uogólnione modele liniowe i nieliniowe (GLZ)], ani nawet czy jest to zależność monotoniczna. Na przykład, niektóre interesujące zmienne ilościowe mogą być dodatnio skorelowane ze zmienną Dochód, jeśli nie przekracza on pewnej wielkości, ale ujemnie gdy jest duży (w drzewie widać taką niemonotoniczność, w postaci podziałów względem zmiennej Dochód). Metody drzew klasyfikacyjnych nadają się więc dobrze do zadań data mining, gdzie często wiedza a priori jest bardzo mała, i nie ma żadnych rozsądnych teorii lub ocen, które zmienne są ze sobą powiązane i w jaki sposób. W tego rodzaju analizach metody drzew klasyfikacyjnych potrafią wykryć związki pomiędzy kilkoma zmiennymi, które nie zostałyby wykryte przez inne techniki analityczne.

Ogólne zagadnienia obliczeniowe oraz unikalne cechy C&RT

Szczegóły dotyczące obliczeń, służących do wyznaczania najlepszych warunków podziału i tworzenia prostych a niosących informację drzew są dosyć zaawansowane. W Breiman i in. (1984) opisany jest algorytm CART® oraz ogólna teoria tworzenia drzew klasyfikacyjnych i regresyjnych. Doskonałe omówienie metod drzew klasyfikacyjnych i regresyjnych wraz z porównaniem z innymi metodami rozpoznawania wzorców i sieciami neuronowymi przedstawione jest w Ripley (1996).

Unikanie przeuczenia: Przycinanie, Sprawdzian krzyżowy, V-krotny sprawdzian krzyżowy

Bardzo duże znaczenie w zastosowaniach drzew klasyfikacyjnych i regresyjnych do "prawdziwych" danych, w których jest duży szum losowy, ma decyzja, w którym momencie przerwać proces podziałów. Na przykład jeśli dane, którymi dysponujemy, zawierają 10 przypadków, to można utworzyć 9 podziałów (warunków jeżeli-to), który wykona doskonałą predykcję każdego z tych przypadków. W ogólności, jeśli wykonamy odpowiednio dużo podziałów, to będziemy mogli "przewidywać" (lepiej byłoby powiedzieć "odtwarzać") oryginalne dane (te które służyły do wyznaczenia podziałów). Oczywiście, wcale nie jest oczywiste, czy taki skomplikowany model (o wielu podziałach) będzie dobrze działał dla próby składającej się z nowych obserwacji, najprawdopodobniej nie będzie.

To ogólne zagadnienie omawiane jest w literaturze na temat drzew klasyfikacyjnych, metod regresyjnych oraz sieci neuronowych i nazywane jest "przeuczeniem" lub "nadmiernym dopasowaniem". Jeśli algorytm tworzenia drzewa nie zatrzyma się, to z danych zostaną "wyekstrahowane" wszystkie informacje, również te, których nie da się uzyskać z całej populacji przy podanym zbiorze predyktorów, czyli np. zmienność losowa lub szum. Ogólne podejście do tego problemu mówi, by przerwać proces tworzenia nowych węzłów z podziałami, gdy kolejne podziały dają niewielki przyrost w trafności predykcyjnej. Na przykład, jeśli jesteśmy w stanie trafnie przewidywać 90% wszystkich przypadków za pomocą 10 podziałów, a 90,1% za pomocą 11, to nie ma większego sensu dodanie jedenastego podziału do modelu. Zatrzymanie procesu podziałów (budowania drzewa) można zadać na podstawie różnych kryteriów.

Gdy algorytm budowy drzewa się już zatrzyma warto zawsze ocenić jakość predykcji za pomocą aktualnie utworzonego drzewa, stosując je do nowych obserwacji, które nie były wykorzystane do budowy modelu. Metoda taka może służyć do "przycinania" drzewa tzn. wyboru drzewa prostszego niż utworzone, ale takiego, które ma podobną trafność predykcyjną względem "nowych" obserwacji.

Sprawdzian krzyżowy. Jedno z podejść polega na zastosowaniu drzewa utworzonego na podstawie jednego zbioru obserwacji (próby uczącej) do innego, niezależnego zbioru obserwacji (próba testowa). Jeśli większość lub wszystkie podziały wyznaczone przez analizę próby uczącej powstały na podstawie "szumu losowego,", to predykcja w próbie testowej będzie bardzo słaba. Wtedy można wnioskować, że wybrane drzewo jest słabe (mało przydatne) i nie ma "właściwej wielkości".

V-krotny sprawdzian krzyżowy. Kontynuując ten tok rozumowania (zob. wyżej sprawdzian krzyżowy), można powtórzyć tą samą analizę wielokrotnie dla różnych losowych prób wybranych z danych, dla każdego rozmiaru drzewa i zastosować ją do obserwacji z prób testowych wybranych losowo. Następnie wybrać (zaakceptować jako model wynikowy) to drzewo, które daje najlepszą średnią trafność predykcji. Zazwyczaj nie będzie to drzewo o dużej ilości węzłów, tzn., najbardziej skomplikowane. Ta metoda przycinania drzewa i wyboru mniejszego z całego ciągu drzew może być bardzo silna i niezwykle użyteczna w przypadku niewielkich zbiorów danych. Ten krok ma kluczowe znaczenie w tworzeniu użytecznych (przydatnych do predykcji) modeli drzew. Ponieważ może on być skomplikowany obliczeniowo, brak go w wielu pakietach do drzew klasyfikacyjnych i regresyjnych.

Przeglądanie dużych drzew: Unikalne narzędzia do zarządzania analizą

Kolejną sprawą związaną z zastosowaniami drzew klasyfikacyjnych i regresyjnych jest możliwość tworzenia bardzo dużych drzew. W praktyce, jeśli dane są skomplikowane i na przykład zawierają wiele różnych kategorii (w problemach klasyfikacyjnych) i wiele predyktorów, to może zostać utworzony model w postaci bardzo dużego drzewa. Nie stanowi to obecnie raczej problemu obliczeniowego, chodzi raczej o problem z prezentacją tego drzewa w sposób wygodny dla analityka i "klienta" analizy.

Analiza układów typu ANCOVA

Klasyczne (Breiman i in., 1984) algorytmy drzew klasyfikacyjnych i regresyjnych obsługują zmienne ilościowe oraz jakościowe. Jednak w praktyce nierzadko łączy się takie zmienne, do celów analizy, w układy predyktorów, takie jak w analizie wariancji/kowariancji z czynnikami głównymi lub interakcjami dla czynników jakościowych i predyktorów ilościowych. Ta metoda analizy układów typu ANCOVA jest dosyć nowa. Widać od razu, że możliwość użycia kodowanych układów pozwala stosować te potężne metody klasyfikacji i regresji do analizowania danych z planów doświadczeń (zob. np. przykład z omówieniem metod planowania doświadczeń w sterowaniu jakością w części Planowanie i analiza doświadczeń w statystykach przemysłowych).

Szczegóły obliczeniowe

W procesie obliczania i tworzenia drzew klasyfikacyjnych i regresyjnych można wyróżnić cztery podstawowe kroki:

Wymienione kroki są bardzo zbliżone do przedstawionych w opisie Drzew klasyfikacyjnych. Zob. w szczególności metody obliczeniowe, a także Breiman et al., 1984

Określenie kryteriów oceny trafności predykcji

Celem stosowania algorytmów drzew klasyfikacyjnych i regresyjnych (C&RT) jest zazwyczaj otrzymanie modelu o najlepszej trafności predykcyjnej. Opcjonalnie, można zdefiniować najtrafniejszą predykcję jako tą, która ma najmniejsze koszty. Pojęcie kosztu zostało stworzone jako uogólnienie na większość sytuacji predykcyjnych idei, że najlepszą predykcję ma model o najniższej stopie błędnych klasyfikacji. W większości zastosowań, miarą kosztu jest stosunek ilości przypadków błędnie zaklasyfikowanych do wszystkich lub wariancja. W tym kontekście predykcja będzie najlepsza, jeśli ma najniższą stopę błędnych klasyfikacji lub najmniejszą wariancję. Potrzeba kierowania się minimalizacją kosztów, a nie samą stopą błędnych klasyfikacji, wynika z tego, że niektóre błędy klasyfikacji mogą mieć bardziej katastrofalne skutki niż inne.

Prawdopodobieństwa a priori. W przypadku jakościowej zmiennej zależnej (problemy klasyfikacyjne), minimalizacja kosztów oznacza najmniejszą proporcję błędnych klasyfikacji przypadków o ile prawdopodobieństwa a priori są proporcjonalne do wielkości klas, a koszty błędnych klasyfikacji równe we wszystkich klasach.

Prawdopodobieństwa a priori wykorzystywane w minimalizacji kosztów mogą mieć duży wpływ na klasyfikację przypadków (obiektów). Oznacza to, że należy zatroszczyć się o właściwe użycie prawdopodobieństw a priori. Jeśli różne prawdopodobieństwa klas nie mają znaczenia w analizie lub wiadomo, że w każdej klasie jest mniej więcej taka sama liczba przypadków, to używamy równych prawdopodobieństw a priori. Jeśli liczności klas odzwierciedlają prawdopodobieństwa klas, co jest np. prawdą w przypadku próby wylosowanej w sposób proporcjonalny (probability sample), to należy użyć ocen prawdopodobieństw klas na podstawie proporcji w próbie. W ostatnim przypadku, gdy wiemy jakie są prawdopodobieństwa (na przykład na podstawie poprzednich badań), używamy ustalonych prawdopodobieństw a priori. Chodzi o to, że wielkości prawdopodobieństw a priori przypisanych klasom mogą służyć do "poprawienia" wag błędnej klasyfikacji dla każdej klasy. W przypadku drzew regresyjnych, nie ma potrzeby podawania tych prawdopodobieństw.

Koszty błędnych klasyfikacji. W pewnych sytuacjach pożądana jest dokładniejsza klasyfikacja niektórych klas zmiennej zależnej niż innych (z powodów niezależnych od liczności klas). Jeśli jako kryterium trafności predykcyjnej wybierzemy koszty błędnych klasyfikacji, to minimalizacja kosztów spowoduje minimalizację proporcji przypadków błędnie zaklasyfikowanych przy czym prawdopodobieństwa a priori będą proporcjonalne do liczebności klas, a koszty błędnych klasyfikacji w każdej z klas będą takie same.

Wagi przypadków. W drzewach klasyfikacyjnych i regresyjnych, wagi przypadków są traktowane jako współczynniki (mnożniki). Przykładowo, stopy błędnych klasyfikacji otrzymane w wyniku analizy danych zagregowanych z podanymi wagami przypadków będą takie jak otrzymane w wyniku analizy tych samych danych, w których każdy z przypadków powtórzony jest tylokrotnie ile wynosi waga.

Należy jednak zauważyć, że korzystanie z wag przypadków w danych zagregowanych w przypadku problemów klasyfikacyjnych związany jest z minimalizacją kosztów. Zamiast wag przypadków dla danych zagregowanych można podać odpowiednie prawdopodobieństwa a priori i/lub koszty błędnych klasyfikacji i otrzymać takie same wyniki, obliczenia są szybsze gdyż unika się przetwarzania wielu przypadków o tej samej wartości wszystkich zmiennych. Przypuśćmy, że zbiór danych zawiera dwie klasy o takiej samej liczbie przypadków, przy czym w pierwszej klasie przypisane są wagi przypadków wynoszące 2, zaś w drugiej wagi wynoszą 3. Jeśli określimy wartości prawdopodobieństw a priori jako odpowiednio 0,4 oraz 0,6, a koszty błędnych klasyfikacji przyjmie równe i przeanalizujemy dane bez wag przypadków, to otrzymamy ten sam wynik tzn. te same stopy błędnych klasyfikacji jak w sytuacji analizy danych zagregowanych z wagami przypadków, prawdopodobieństwami ocenianymi na podstawie liczności klas oraz przyjęcia równych kosztów błędnych klasyfikacji. Takie same wyniki uzyskamy podając równe prawdopodobieństwa a priori oraz podając koszt błędnej klasyfikacji przypadków klasy 1 jako klasy 2 wysokości 2/3 kosztu błędnej klasyfikacji przypadków klasy 2 jako klasy 1 oraz analizując dane bez wag przypadków.

Wybór podziałów

Drugi krok w budowie drzew klasyfikacyjnych i regresyjnych to wybór predyktorów, które mają służyć do utworzenia kolejnego podziału i predykcji przynależności przypadku do klasy zmiennej zależnej lub predykcji wartości ilościowej zmiennej zależnej. Najogólniej rzecz ujmując, program w każdym węźle szuka podziału dającego największe polepszenie trafności predykcyjnej. Mierzymy ją zazwyczaj jakąś miarą zanieczyszczenia węzła, która wskazuje na względną jednorodność (odwrotność zanieczyszczenia) przypadków w węźle końcowym. Jeśli przypadki w węzłach końcowych mają te same wartości to zanieczyszczenie węzła jest minimalne, a jednorodność maksymalna, i predykcja doskonała (odnoście przypadków użytych w obliczaniu modelu, trafność predykcyjna dla nowych przypadków to już odrębna sprawa ...).

W problemach klasyfikacyjnych C&RT daje możliwość wybrania różnych miar niejednorodności: Indeks Giniego, Chi-kwadrat lub G-kwadrat. Indeks Giniego zanieczyszczenia węzła jest miarą najczęściej używana w problemach typu klasyfikacyjnego. Jako miara zanieczyszczenia przyjmuje wartość zero tylko wtedy gdy w węźle są przypadki z dokładnie jednej klasy. Jeśli prawdopodobieństwa a priori oceniane są na podstawie liczności klas, a koszty błędnych klasyfikacji są równe, to miara Giniego niejednorodności w węźle obliczana jest jako suma po wszystkich parach klas iloczynów udziału tych klas w węźle - maksimum osiągane jest w przypadku, gdy liczności klas w węźle są równe, natomiast jeśli wszystkie przypadki w węźle należą do jednej klasy, to miara Giniego wynosi 0. Miara Chi-kwadrat podobna jest do standardowej statystyki Chi-kwadrat obliczanej dla liczności oczekiwanych i obserwowanych (z prawdopodobieństwami a priori uwzględniającymi koszty błędnych klasyfikacji), a miara G-kwadrat jest podobna do chi-kwadrat największej wiarogodności (obliczanej na przykład w module analizy log-liniowej). W problemach typu regresyjnego, program automatycznie wykorzystuje kryterium najmniejszych kwadratów (podobne do stosowanego w obliczeniach regresji metodą najmniejszych kwadratów). Zob. Obliczenia, wzory.

Wybór momentu zakończenia podziałów

Jak to zaznaczono w części Podstawowe idee, w zasadzie podziały można kontynuować aż do uzyskania klasyfikacji doskonałej. Nie ma to jednak większego sensu, gdyż otrzymana struktura drzewa byłaby bardzo złożona i tak samo "dokładna" jak oryginalne dane (o wielu węzłach, w których byłby często pojedyncze obserwacje), taki model najprawdopodobniej nie dawałby dobrych predykcji nowych obserwacji. Potrzebna jest więc rozsądna reguła zatrzymania. W C&RT stosuje są dwie opcje zatrzymania - minimalne n oraz frakcja obiektów.

Minimalna liczność. Jednym ze sposobów kontroli procesu podziałów polega na tym, że podziały prowadzone są do momentu aż wszystkie węzły końcowe będą jednorodne lub będą zawierać nie więcej niż określoną minimalną liczbę przypadków. W C&RT oznacza to wybór opcji minimalne n i określenie pożądanej minimalnej liczby przypadków jako kryterium zatrzymania procesu podziałów. Opcję tą można stosować, jeśli jako reguła zatrzymania analizy ustawiona jest Przytnij przy błędzie złej klasyfikacji, Przytnij przy odchyleniu lub Przytnij przy wariancji.

Frakcja obiektów. Inny sposób kontroli procesu podziałów polega na prowadzeniu podziałów do momentu gdy wszystkie węzły końcowe będą jednorodne lub będą zawierać nie więcej niż określoną frakcję klas (w przypadku problemów typu klasyfikacyjnego, a frakcję przypadków w problemach regresyjnych). Z opcji tej można korzystać, jeśli jako regułę stopu wykorzystujemy bezpośrednie zatrzymanie typu FACT. W C&RT pożądaną minimalną frakcję możemy określamy jako Frakcja obiektów. W problemach klasyfikacyjnych : jeśli prawdopodobieństwa a priori używane w analizie są równe oraz wielkości klas równe, to proces podziałów zostanie zatrzymany gdy węzły końcowe zawierające przypadki więcej niż jednej klasy nie będą miały więcej niż podaną frakcję obiektów. Jeśli prawdopodobieństwa a priori nie są równe, proces podziałów zatrzyma się w momencie, gdy w węzłach końcowych zawierających obserwacje z więcej niż jednej klasy nie będzie więcej niż podana frakcja przypadków. Zob. szczegóły w Loh i Vanichestakul, 1988.

Przycinanie i wybór drzewa właściwej wielkości

Odpowiedni rozmiar drzewa w analizie za pomocą drzew klasyfikacyjnych i regresyjnych jest istotnym problemem, zbyt duże drzewo może być trudne do zinterpretowania. Są pewne ogólne zasady mówiące o tym, jakie powinno być drzewo "właściwej wielkości". Powinno być wystarczająco złożone by odzwierciedlać znane fakty, a jednocześnie powinno być jak najprostsze. Powinno wykorzystywać informacje, które dają przyrost trafności predykcyjnej, a zaniedbywać te które takiego przyrostu nie dają. Powinno, o ile to możliwe, dawać lepsze zrozumienie opisywanego zjawiska. Opcje dostępne w C&RT pozwalają korzystać z dwóch strategii (oddzielnie lub razem) wyboru drzewa "właściwej wielkości" z zestawu wszystkich możliwych drzew. Jedna strategia polega na tworzeniu drzewa tak by dojść do właściwej wielkości, przy czym właściwą wielkość określa użytkownik, na podstawie wcześniejszych badań, informacji diagnostycznych z poprzednich analiz, a nawet intuicji. Druga strategia polega na wykorzystaniu dobrze udokumentowanych procedur podanych przez Breimana i innych (1984) do wybrania drzewa "właściwej wielkości". Procedury nie są niezawodne, jak to zaznaczają autorzy, ale nie opierają się na subiektywnych ocenach.

Bezpośrednie zatrzymanie typu FACT. W tym przypadku sprawdzane są wszystkie możliwe podziały dla każdej zmiennej predykcyjnej w celu znalezienia podziału, przy którym następuje największa poprawa dobroci dopasowania (lub największa redukcja braku dopasowania). Co wyznacza dziedzinę możliwych podziałów przy danym węźle? Dla nominalnych zmiennych predykcyjnych z k poziomami występującymi przy danym węźle mamy 2(k -1) - 1 możliwych kontrastów między dwoma zbiorami poziomów tego predyktora. Dla predyktorów porządkowych z k różnymi poziomami występującymi przy danym węźle mamy k -1 środkowych punktów między różnymi poziomami. Widać zatem, że liczba możliwych podziałów, które muszą być przeanalizowane może być bardzo duża, jeśli będziemy mieli dużo predyktorów z wieloma poziomami, które muszą być analizowane przy wielu węzłach. Pierwszy sposób polega na ustaleniu przez użytkownika wielkości drzewa. Ta metoda zostanie zastosowana, jeśli wybierzemy bezpośrednie zatrzymanie typu FACT jako regułę zatrzymania i podamy Frakcję obiektów , która pozwoli rozwinąć się drzewu do pożądanego rozmiaru. C&RT ma wiele opcji, które dają informacje diagnostyczne, pozwalające ocenić sensowność wybranego drzewa . W szczególności dostępne są trzy opcje sprawdzianu krzyżowego : Próba testowa, v oraz koszt minimalny.

Sprawdzian krzyżowy w próbie testowej. Pierwszy rodzaj sprawdzianu krzyżowego (i najczęściej stosowany) to sprawdzian w próbie testowej. W tym przypadku na podstawie próby uczącej tworzone jest drzewo, a jego trafność oceniana na podstawie predykcji w próbie testowej. Koszt w próbie testowej większy niż w uczącej należy odczytywać jako słaby sprawdzian krzyżowy. W takim przypadku drzewo innej wielkości może być lepsze w sprawdzianie krzyżowym. Próbę testową i uczącą można utworzyć biorąc dwa niezależne zbiory danych lub jeśli mamy dużą próbę, poprzez losowy wybór części przypadków (np. jednej trzeciej, połowy) i użycie jej jako próby testowej.

W module C&RT sprawdzian krzyżowy w próbie testowej wykonywany jest poprzez wskazanie zmiennej identyfikującej próby (uczącą i testową).

V-krotny sprawdzian krzyżowy. Drugi rodzaj sprawdzianu krzyżowego dostępny w C&RT to v-krotny sprawdzian krzyżowy. Ta metoda jest wygodna, jeśli nie ma próby testowej, a próba ucząca jest zbyt mała by z niej wydzielić osobną próbę testową. Podana przez użytkownika wartość 'v' dla tego sprawdzianu (domyślnie 3) określa liczbę podprób, w miarę możliwości równej liczności, losowo tworzonych z próby uczącej. Drzewo podanej wielkości wyliczane jest 'v' krotnie, za każdym razem do obliczeń brane są przypadki z wyłączeniem jednej podpróby, która służy jako próba testowa. Tak więc każda z podprób użyta jest (v - 1) razy w próbie uczącej, a tylko raz jako próba testowa. Koszt SK (sprawdzianu krzyżowego) obliczany jest jako średni koszt z 'v' prób testowych, ta średnia jest oceną kosztu SK.

Przycinanie według minimum złożoności mierzonej kosztem sprawdzianu krzyżowego. W module C&RT stosowane jest przycinanie według minimum kosztu i złożoności sprawdzianu krzyżowego jeśli wybierzemy jako regułę zatrzymania opcję Przytnij przy błędzie klasyfikacji. Jeśli wybierzemy Przytnij przy odchyleniu, to wykonywane jest przycinanie według minimum złożoności mierzonej odchyleniem. Te dwie opcje różnią się tylko sposobem mierzenia błędu predykcji. Opcja Przytnij przy błędzie złej klasyfikacji wykorzystuje koszt równy stopie błędu klasyfikacji przy prawdopodobieństwach a prior estymowanych i równych kosztach błędnych klasyfikacji, a Przytnij przy odchyleniu wykorzystuje miarę opartą o zasady maksymalnej wiarogodności, nazywaną odchyleniem (zob. Ripley, 1996). Szczegóły na temat wykorzystywanych algorytmów z modułu C&RT zaimplementowanych w Przycinaniu według minimum złożoności mierzonej kosztem sprawdzianu krzyżowego zob. Wprowadzenie do drzew klasyfikacyjnych - Podstawowe pojęcia oraz Metody obliczeniowe w części Drzewa klasyfikacyjne.

Sekwencja drzew uzyskanych przy pomocy tego algorytmu ma kilka interesujących własności. Drzewa w sekwencji są zagnieżdżone, ponieważ kolejno przycinane zawierają wszystkie węzły następnego w kolejności mniejszego drzewa. Początkowo, przy przejściu od jednego do następnego w kolejności, mniejszego drzewa, wiele węzłów często zostaje przyciętych, ale przy zbliżaniu się do korzenia przycina się mniej węzłów. Sekwencja największych drzew jest także przycinana optymalnie, ponieważ dla każdej wielkości drzewa w sekwencji nie ma innego drzewa tej samej wielkości, które miałoby mniejsze koszty. Uzasadnienia i wyjaśnienia tych własności znajdują się w: Breiman i in. (1984).

Wybór drzewa po przycięciu. Przycinanie, opisane wyżej, daje sekwencję drzew optymalnie przyciętych. Kolejny krok polega na użyciu odpowiedniego kryterium do wybrania drzewa "właściwej wielkości" z takiego ciągu drzew optymalnych. Naturalne kryterium to koszt SK (sprawdzianu krzyżowego). Chociaż nie ma nic złego w wyborze drzewa z minimalnymi kosztami sprawdzianu krzyżowego jako drzewa właściwej wielkości, to często może się zdarzyć, że będziemy mieli kilka drzew z kosztami sprawdzianu krzyżowego bliskimi minimum. Automatyczna procedura wyboru drzewa może korzystać z propozycji Breimana. Breiman i in. (1984) sugerują, aby jako drzewo właściwej wielkości wybrać drzewo najmniejszej wielkości (najmniej złożone), którego koszty sprawdzianu krzyżowego nie różnią się znacznie od minimalnych kosztów sprawdzianu krzyżowego. Proponują tutaj zasadę jednego błędu standardowego, tzn. jako drzewo właściwej wielkości wybieramy drzewo najmniejszych rozmiarów, którego koszty sprawdzianu krzyżowego nie przekraczają minimalnych kosztów sprawdzianu krzyżowego plus 1 błąd standardowy kosztów sprawdzianu krzyżowego dla drzewa o minimalnych kosztach sprawdzianu krzyżowego. W module C&RT można podawać wartości czynnika dla reguły błędu standardowego (inne niż domyślna wartość 1). Zatem określenie wartości 0,0 da w efekcie jako drzewo właściwej wielkości to o minimalnych kosztach sprawdzianu krzyżowego. Wartości większe od 1,0 prowadzą do wybrania drzew znacznie mniejszych niż drzewo o najmniejszych kosztach sprawdzianu krzyżowego Szczególną zaletą procedury automatycznego wyboru drzewa jest to, że pomaga ona uniknąć nadmiernego dopasowania (przeuczenia) lub niedopasowania do danych.

Jak widać, procedura wyboru jest procesem "automatycznym". Algorytm sam podejmuje wszystkie decyzje prowadzące do wyboru drzewa "właściwej wielkości", może poza wyborem wartości dla reguły błędu standardowego. Niezależnie od sposobu tworzenia i przycinania drzewa C&RT zawiera opcje w oknach wyników lub sprawdzianu krzyżowego pozwalające przeprowadzić sprawdzian krzyżowy dla każdego z drzew z otrzymanej sekwencji drzew. To polecenie pozwala ocenić jak dobrze "zachowuje się" każde z drzew przy wielokrotnym sprawdzianie krzyżowym w różnych próbach losowo wybranych z danych.

Obliczenia, wzory

W drzewach klasyfikacyjnych i regresyjnych ocena dokładności modeli klasyfikacyjnych i regresyjnych dokonywana jest na podstawie różnych formuł. Przy klasyfikacji (skategoryzowana zmienna zależna) dokładność mierzona jest liczbą poprawnych klasyfikacji, przy regresji natomiast (ciągła zmienna zależna) dokładność oblicza się jako średni błąd kwadratowy predykcji.

Poza miarą dokładności, w zagadnieniach klasyfikacyjnych oblicza się następujące miary niejednorodności węzła (node impurity): miarę Gini'ego, uogólnione Chi-kwadrat i uogólnioną miarę G-kwadrat. Miara Chi-kwadrat bazuje na standardowym Chi-kwadrat, obliczanym dla klasyfikacji oczekiwanych i obserwowanych (z uwzględnieniem kosztu błędnych klasyfikacji). Miara G-kwadrat bazuje na Chi-kwadrat największej wiarygodności (podobnie jak to jest w analizie log-liniowej). Miara Gini'ego, opisana niżej, należy do najczęściej używanych w klasyfikacji miar spójności węzła.

W przypadku wykonywania regresji, dla ciągłej zmiennej zależnej, automatycznie stosowana jest miara bazująca na odchyleniu najmniejszych kwadratów (LSD).

Ocena dokładności w klasyfikacji

W zagadnieniach klasyfikacyjnych (przy skategoryzowanej zmiennej zależnej) używane są trzy oceny dokładności: resubstytucji, próby testowej i v-krotnej walidacji. Niżej podane są ich definicje.

Ocena według resubstytucji. Jest to proporcja przypadków błędnie sklasyfikowanych przez model klasyfikujący zbudowany na bazie wszystkich przypadków. Wzór jest następujący:

gdzie X jest funkcją wskaźnikową;

X = 1, jeśli wyrażenie jest prawdziwe

X = 0, jeśli wyrażenie jest fałszywe

oraz d (x) jest klasyfikującym modelem.

Miara ta obliczana jest dla tego samego zbioru danych, na bazie którego zbudowano model d .

Ocena na bazie próby testowej. Wszystkie przypadki danych dzielone są na dwie grupy Z1 i Z2. Oceną dokładności klasyfikacji jest proporcja przypadków w grupie Z2, błędnie sklasyfikowanych przez model zbudowany na bazie grupy Z1. Oblicza się ją następująco:

gdzie N2 jest liczbą przypadków w grupie Z2, która nie była wykorzystywana przy budowie modelu.

V-krotna walidacja krzyżowa. Wszystkie przypadki danych dzielone są na v grup Z1, Z2, ..., Zv o takiej samej, na ile to możliwe liczności. Oceną dokładności klasyfikacji jest proporcja przypadków w grupie Z błędnie sklasyfikowanych przez model zbudowany na bazie przypadków grupy Z -  Zv. Obowiązuje tu następujący wzór:

gdzie obliczone jest dla próby Z - Zv .

Ocena dokładności przy regresji

W zagadnieniach regresyjnych (przy ciągłej zmiennej zależnej) używane są trzy oceny dokładności: resubstytucji, próby testowej i v-krotnej walidacji. Niżej podane są ich definicje.

Ocena według resubstytucji. Oblicza się tu oczekiwany błąd kwadratowy, bazując na predykcji zależnej zmiennej ciągłej. Wzór jest następujący:

gdzie próba ucząca Z składa się z punktów (xi,yi), i = 1,2,...,N. Miara ta obliczana jest dla tego samego zbioru danych, na bazie którego zbudowano model d.

Ocena na bazie próby testowej. Wszystkie przypadki danych dzielone są na dwie grupy Z1 i Z2. Oceną dokładności obliczana jest jak we wzorze poniżej:

gdzie N2 jest liczbą przypadków w grupie Z2, która nie była wykorzystywana przy budowie modelu.

V-krotna walidacja krzyżowa. Wszystkie przypadki danych dzielone są na v grup Z1, Z2, ..., Zv takiej samej, na ile to możliwe liczności. Grupa próbek Z -  Zv użyta zostaje do zbudowania modelu d. Ocena dokładności obliczana jest dla grupy próbek Zv w następujący sposób:

gdzie obliczone jest dla próby Z -  Zv .

Ocena niejednorodności węzła: miara Gini'ego

Miara Gini'ego niespójności węzła jest często używana w sytuacjach gdy zmienna zależna jest zmienną skategoryzowaną. Definicja jest następująca:

w przypadku, gdy nie określono kosztów błędnych klasyfikacji ani niejednakowych prawdopodobieństw a priori, oraz

gdy podano koszty błędnych klasyfikacji lub niejednakowe prawdopodobieństwa a priori.

We wzorach sumowanie przebiega po wszystkich k kategoriach. Natomiast p( j / t) jest prawdopodobieństwem kategorii j w węźle t, a C(i / j ) jest prawdopodobieństwem błędnego sklasyfikowania kategorii  j jako i.

Należy zwrócić uwagę, że określenie niejednakowych prawdopodobieństw a priori może poważnie wpłynąć na dokładność przewidywania przez drzewo danej klasy.

Ocena niespójności węzła: odchylenie najmniejszych kwadratów (LSD)

Odchylenie najmniejszych kwadratów jest często używaną miarą niespójności węzła w sytuacjach gdy zmienna zależna jest zmienną ciągłą. Definicja jest następująca:

gdzie Nw(t) jest ważoną liczbą przypadków w węźle t, wi jest wartością zmiennej ważącej dla przypadku i,  fi jest wartością zmiennej częstotliwości,  yi jest wartością zmiennej odpowiedzi, a y(t)  jest średnią ważoną w węźle t.

Indeks





© Copyright StatSoft, Inc., 1984-2024
STATISTICA is a trademark of StatSoft, Inc.