Prořezávání rozhodovacích stromů - Decision tree pruning

Před a po prořezávání

Prořezávání je Komprese dat technika v strojové učení a vyhledávací algoritmy což zmenšuje velikost souboru rozhodovací stromy odstraněním částí stromu, které jsou nekritické a nadbytečné pro klasifikaci instancí. Prořezávání snižuje složitost finále klasifikátor, a tím zlepšuje prediktivní přesnost snížením nadměrné vybavení.

Jednou z otázek, které vyvstávají v algoritmu rozhodovacího stromu, je optimální velikost konečného stromu. Strom, který je příliš velký, riskuje nadměrné vybavení tréninková data a špatně zobecňující na nové vzorky. Malý strom nemusí zachytit důležité strukturální informace o ukázkovém prostoru. Je však těžké určit, kdy by se měl stromový algoritmus zastavit, protože není možné určit, zda přidání jediného dalšího uzlu dramaticky sníží chybu. Tento problém je známý jako horizont efekt. Společnou strategií je růst stromu, dokud každý uzel nebude obsahovat malý počet instancí, a poté pomocí prořezávání odebrat uzly, které neposkytují další informace.^[1]

Prořezávání by mělo zmenšit velikost stromu učení bez snížení prediktivní přesnosti měřené pomocí a křížová validace soubor. Existuje mnoho technik prořezávání stromů, které se liší v měření, které se používá k optimalizaci výkonu.

Techniky

Procesy prořezávání lze rozdělit do dvou typů (pre- a post-prořezávání).

Předřezávání postupy zabraňují úplné indukci tréninkové sady nahrazením kritéria stop () v indukčním algoritmu (např. maximální hloubka stromu nebo zisk informací (Attr)> minGain). Metody předběžného prořezávání jsou považovány za efektivnější, protože nevyvolávají celou sadu, ale stromy zůstávají od začátku malé. Předběžné metody mají společný problém, horizontální efekt. To je třeba chápat jako nežádoucí předčasné ukončení indukce kritériem stop ().

Post-prořezávání (nebo jen prořezávání) je nejběžnějším způsobem zjednodušení stromů. Zde jsou uzly a podstromy nahrazeny listy, aby se zlepšila složitost. Prořezávání může nejen výrazně zmenšit velikost, ale také zlepšit přesnost klasifikace neviditelných objektů. Může se stát, že se přesnost přiřazení na testovací sadě zhorší, ale přesnost klasifikačních vlastností stromu se celkově zvýší.

Postupy jsou rozlišeny na základě jejich přístupu ve stromu (shora dolů nebo zdola nahoru).

Prořezávání zdola nahoru

Tyto procedury začínají na posledním uzlu ve stromu (nejnižší bod). Následující rekurzivně nahoru určují relevanci každého jednotlivého uzlu. Pokud není dána relevance pro klasifikaci, uzel je zrušen nebo nahrazen listem. Výhodou je, že touto metodou nelze ztratit žádné relevantní dílčí stromy. Mezi tyto metody patří zmenšené prořezávání chyb (REP), prořezávání složitosti minimálních nákladů (MCCP) nebo prořezávání minimálních chyb (MEP).

Prořezávání shora dolů

Na rozdíl od metody zdola nahoru začíná tato metoda u kořene stromu. Podle níže uvedené struktury se provádí kontrola relevance, která rozhodne, zda je uzel relevantní pro klasifikaci všech n položek nebo ne. Prořezáním stromu ve vnitřním uzlu se může stát, že bude zrušen celý podstrom (bez ohledu na jeho relevanci). Jedním z těchto zástupců je pesimistické prořezávání chyb (PEP), které s neviditelnými položkami přináší docela dobré výsledky.

Algoritmy prořezávání

Snížené prořezávání chyb

Jednou z nejjednodušších forem prořezávání je zmenšené prořezávání chyb. Počínaje listy je každý uzel nahrazen nejoblíbenější třídou. Pokud není ovlivněna přesnost predikce, bude změna zachována. I když je poněkud naivní, snížené prořezávání chyb má tu výhodu jednoduchost a rychlost.

Složitost nákladů prořezávání

Složitost nákladů prořezávání generuje řadu stromů ${displaystyle T_ {0} tečky T_ {m}}$ kde ${displaystyle T_ {0}}$ je počáteční strom a ${displaystyle T_ {m}}$ je samotný kořen. V kroku ${displaystyle i}$ , strom je vytvořen odstraněním podstromu ze stromu ${displaystyle i-1}$ a jeho nahrazení listovým uzlem s hodnotou zvolenou jako v algoritmu budování stromu. Odstraněný podstrom je vybrán následovně:

Definujte chybovost stromu ${displaystyle T}$ přes soubor dat ${displaystyle S}$ tak jako ${displaystyle operatorname {err} (T, S)}$ .
Podstrom, který minimalizuje ${displaystyle {frac {operatorname {err} (operatorname {prune} (T, t), S) -operatorname {err} (T, S)} {leftvert operatorname {leaves} (T) ightvert -leftvert operatorname {leaves} ( operatorname {prune} (T, t)) ightvert}}}$ je vybrán k odstranění.

Funkce ${displaystyle operatorname {prune} (T, t)}$ definuje strom získaný prořezáváním podstromů ${displaystyle t}$ ze stromu ${displaystyle T}$ . Jakmile je vytvořena řada stromů, je nejlepší strom vybrán zobecněnou přesností měřenou tréninkovou sadou nebo křížovou validací.

Viz také

Reference

Judea Pearl, Heuristika, Addison-Wesley, 1984
Pesimistické prořezávání rozhodovacích stromů na základě velikosti stromu^[2]
L. A. Breslow a D. W. Aha, Zjednodušení rozhodovacích stromů: Průzkum, The Knowledge Engineering Review, sv. 12 (1), 1997, s. 1–47.
J. R. Quinlan, Indukce rozhodovacích stromů, Machine Learning 1, Kluwer Academic Publishers, 1986, s. 81–106.

^ Trevor Hastie, Robert Tibshirani a Jerome Friedman. Prvky statistického učení. Springer: 2001, str. 269-272
^ Mansour, Y. (1997), „Pesimistické prořezávání rozhodovacích stromů na základě velikosti stromu“, Proc. 14. mezinárodní konference o strojovém učení: 195–201

Další čtení

externí odkazy

[tib-1] Trevor Hastie, Robert Tibshirani a Jerome Friedman. Prvky statistického učení. Springer: 2001, str. 269-272

[Mansour1997-2] Mansour, Y. (1997), „Pesimistické prořezávání rozhodovacích stromů na základě velikosti stromu“, Proc. 14. mezinárodní konference o strojovém učení: 195–201

[1]

[2]