Przycinanie drzew decyzyjnych - Decision tree pruning

Przycinanie to technika kompresji danych w algorytmach uczenia maszynowego i wyszukiwania, która zmniejsza rozmiar drzew decyzyjnych poprzez usuwanie części drzewa, które nie są krytyczne i zbędne do klasyfikowania instancji. Przycinanie zmniejsza złożoność ostatecznego klasyfikatora , a tym samym poprawia dokładność predykcyjną dzięki ograniczeniu nadmiernego dopasowania .

Jednym z pytań pojawiających się w algorytmie drzewa decyzyjnego jest optymalny rozmiar ostatecznego drzewa. Zbyt duże drzewo stwarza ryzyko nadmiernego dopasowania danych uczących i słabego uogólnienia na nowe próbki. Małe drzewo może nie zawierać ważnych informacji strukturalnych o przestrzeni próbki. Jednak trudno jest stwierdzić, kiedy algorytm drzewa powinien się zatrzymać, ponieważ nie można stwierdzić, czy dodanie jednego dodatkowego węzła drastycznie zmniejszy błąd. Ten problem jest znany jako efekt horyzontu . Powszechną strategią jest rozwijanie drzewa, aż każdy węzeł zawiera niewielką liczbę instancji, a następnie użycie przycinania w celu usunięcia węzłów, które nie dostarczają dodatkowych informacji.

Przycinanie powinno zmniejszyć rozmiar drzewa uczenia się bez zmniejszania dokładności predykcyjnej mierzonej zestawem walidacji krzyżowej . Istnieje wiele technik przycinania drzew, które różnią się miarą używaną do optymalizacji wydajności.

Techniki

Procesy przycinania można podzielić na dwa rodzaje (przycinanie przed i po przycinaniu).

Procedury wstępnego przycinania uniemożliwiają całkowitą indukcję zbioru uczącego poprzez zastąpienie kryterium stop() w algorytmie indukcji (np. maks. głębokość drzewa lub przyrost informacji (Attr)> minGain). Uważa się, że metody wstępnego przycinania są bardziej wydajne, ponieważ nie indukują całego zbioru, ale raczej drzewa od samego początku pozostają małe. Metody przycinania mają wspólny problem, efekt horyzontu. Należy to rozumieć jako niepożądane przedwczesne zakończenie indukcji przez kryterium zatrzymania ().

Przycinanie (lub po prostu przycinanie) to najczęstszy sposób uproszczenia drzew. Tutaj węzły i poddrzewa są zastępowane liśćmi, aby zmniejszyć złożoność. Przycinanie może nie tylko znacznie zmniejszyć rozmiar, ale także poprawić dokładność klasyfikacji niewidocznych obiektów. Może się zdarzyć, że dokładność przypisania w zestawie pociągów pogorszy się, ale ogólna dokładność właściwości klasyfikacyjnych drzewa wzrośnie.

Procedury są zróżnicowane ze względu na ich podejście w drzewie (z góry na dół lub od dołu do góry).

Przycinanie oddolne

Procedury te rozpoczynają się w ostatnim węźle drzewa (najniższy punkt). Podążając rekurencyjnie w górę, określają trafność każdego pojedynczego węzła. Jeśli znaczenie dla klasyfikacji nie zostanie podane, węzeł zostanie usunięty lub zastąpiony liściem. Zaletą jest to, że za pomocą tej metody nie można utracić żadnych istotnych poddrzew. Metody te obejmują przycinanie z redukcją błędów (REP), przycinanie przy minimalnym koszcie złożoności (MCCP) lub przycinanie przy minimalnych błędach (MEP).

Przycinanie odgórne

W przeciwieństwie do metody bottom-up, ta metoda zaczyna się od korzenia drzewa. Zgodnie z poniższą strukturą przeprowadzana jest kontrola istotności, która decyduje, czy węzeł jest istotny dla klasyfikacji wszystkich n pozycji, czy nie. Przycinając drzewo w węźle wewnętrznym, może się zdarzyć, że całe poddrzewo (bez względu na jego znaczenie) zostanie usunięte. Jednym z takich przedstawicieli jest pesymistyczne przycinanie błędów (PEP), które przy niewidocznych przedmiotach przynosi całkiem dobre rezultaty.

Algorytmy przycinania

Zmniejszenie błędów przycinania

Jedną z najprostszych form przycinania jest przycinanie z ograniczeniem błędów. Począwszy od liści, każdy węzeł jest zastępowany przez swoją najpopularniejszą klasę. Jeśli dokładność prognozy nie zostanie naruszona, zmiana zostanie zachowana. Choć nieco naiwne, zredukowane przycinanie błędów ma tę zaletę, że jest proste i szybkie .

Przycinanie złożoności kosztów

Przycinanie złożoności kosztów generuje serię drzew, w których jest drzewem początkowym i samym korzeniem. W kroku , drzewo jest tworzone poprzez usunięcie poddrzewa z drzewa i zastąpienie go węzłem liścia o wartości wybranej jak w algorytmie budowania drzewa. Usunięte poddrzewo jest wybierane w następujący sposób: ${\displaystyle T_{0}\kropki T_{m}}$${\displaystyle T_{0}}$${\ Displaystyle T_ {m}}$${\displaystyle i}$${\displaystyle i-1}$

1. Zdefiniuj poziom błędu drzewa w zestawie danych jako .${\displaystyle T}$${\displaystyle S}$${\ Displaystyle \ operatorname {err} (T, S)}$
2. Poddrzewo, które minimalizuje, jest wybierane do usunięcia.${\displaystyle {\frac {\operator {błąd} (\operator {śliwka} (T,t),S)-\operator {błąd} (T,S)}{\lewo\vert \operator {liście} (T )\right\vert -\left\vert \operatorname {liście} (\operatorname {prune} (T,t))\right\vert }}}$

Funkcja definiuje drzewo uzyskane przez wycinanie poddrzew z drzewa . Po utworzeniu serii drzew najlepsze drzewo jest wybierane na podstawie uogólnionej dokładności mierzonej zbiorem uczącym lub walidacją krzyżową. ${\displaystyle \operatorname {śliwka} (T,t)}$${\displaystyle t}$${\displaystyle T}$

Zobacz też

• Przycinanie alfa–beta
• Sztuczna sieć neuronowa
• Heurystyka zerowego ruchu

Bibliografia

• Perła, Judea (1984). Heurystyka . Addisona-Wesleya.
• Mansour, Y. (1997). "Pesymistyczne przycinanie drzew decyzyjnych na podstawie wielkości drzewa" . Proc. XIV Międzynarodowa Konferencja Uczenia Maszynowego . s. 195-201.
• Breslow, LA; Aha, DW (1997). „Uproszczenie drzew decyzyjnych: ankieta”. Przegląd Inżynierii Wiedzy . 12 (1): 1-47. doi : 10.1017/S0269888997000015 .
• Quinlan, JR (1986). „Indukcja drzew decyzyjnych” . Uczenie maszynowe . Wydawnictwa Akademickie Kluwer. 1 : 81–106. doi : 10.1007/BF00116251 .

Dalsza lektura

• Przycinanie drzew decyzyjnych w oparciu o MDL
• Przycinanie drzew decyzyjnych przy użyciu sieci neuronowych z propagacją wsteczną

Linki zewnętrzne

• Szybki, oddolny algorytm przycinania drzew decyzyjnych
• Wprowadzenie do przycinania drzew decyzyjnych