CART (algoritmus)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. srpna 2020; kontroly vyžadují 2 úpravy .

Algoritmus CART (Classification and Regression Tree) , jak název napovídá, řeší problémy klasifikace a regrese vytvořením rozhodovacího stromu. Byl vyvinut v letech 1974-1984 čtyřmi profesory statistiky: Leo Breiman ( Berkeley ), Jerome Friedman( Stanford ), Charles Stone (Charles Stone, Berkeley ) a Richard Olshen (Richard A. Olshen, Stanford ).

K dnešnímu dni existuje velké množství algoritmů, které implementují rozhodovací stromy: CART , C4.5 , CHAID, CN2, NewId , ITrule a další [1] .

Základní význam algoritmu

Algoritmus CART je navržen tak, aby vytvořil binární rozhodovací strom. Binární (binární) stromy jsou stromy, z nichž každý uzel má po rozdělení pouze dva potomky. Pro algoritmus CART znamená „chování“ objektů vybrané skupiny podíl modální (nejčastější) hodnoty výstupního znaku. Vybrané skupiny jsou ty, u kterých je tento podíl poměrně vysoký. V každém kroku konstrukce stromu pravidlo vytvořené v uzlu rozděluje danou sadu příkladů na dvě části — část, kde pravidlo platí (dítě — vpravo) a část, kde pravidlo neplatí (dítě — vlevo). [2]

Výhodou algoritmu CART je jistá záruka, že pokud ve studované populaci existují požadovaná určení, pak budou odhalena. Kromě toho vám CART umožňuje „nezavírat“ jednu hodnotu výstupní funkce, ale hledat všechny takové hodnoty, pro které můžete najít odpovídající vysvětlující výraz. [3]

Metoda CART se používá pro nominální (obvykle dvouúrovňové) a ordinální prediktorové proměnné. V této metodě jsou vyčísleny všechny možné možnosti větvení pro každý uzel a je vybrána proměnná prediktoru, pro kterou odhadce dává nejlepší skóre.

Pravidla rozdělení

Pro nominální prediktorovou proměnnou, která nabývá hodnot k v daném uzlu, existují přesně 2 (k-1) −1 možností pro rozdělení množiny jejích hodnot na dvě části.

Pro ordinální prediktor, který má v daném uzlu k různých úrovní, existuje k-1 bodů oddělujících různé úrovně. Počet různých možností větvení, které je třeba zobrazit, bude velmi velký: pokud je v problému mnoho prediktorů, pak mají mnoho úrovní hodnot, což znamená, že ve stromu je mnoho terminálních vrcholů. Navíc má tato metoda tendenci volit pro větvení ty prediktorové proměnné, které mají více úrovní, takže je potřeba indikátor, který by umožnil posoudit kvalitu konstruovaného modelu. [čtyři]

Hodnocení kvality modelu

Vyhodnocovací funkce používaná algoritmem CART je založena na intuitivní myšlence snížení nejistoty (heterogenity) v uzlu. Jako příklad zvažte problém se dvěma třídami a uzlem, který má 50 instancí každé třídy. Uzel má maximální nejistotu. Pokud je nalezen oddíl, který rozděluje data na dvě podskupiny příkladů 40:5 v jedné a 10:45 ve druhé, pak se heterogenita intuitivně sníží. Zcela zmizí, když se najde rozdělení, které vytvoří podskupiny 50:0 a 0:50. V algoritmu CART je myšlenka nejistoty formalizována v Gini indexu . Pokud datová sada T obsahuje n dat třídy, pak je Gini index definován následovně [5]

Gini(T)=1-\součet _{{i=1}}^{n}p_{i}^{2}

, kde pi je pravděpodobnost (relativní četnost) třídy i v T . Pokud je množina T rozdělena na dvě části T1 a T2 s počtem příkladů v každém N1 a N2 , pak se index kvality dělení bude rovnat:

Gini_{{\text{split}}}(T)={\frac {N_{1}}{N}}\cdot Gini(T_{1})+{\frac {N_{2}}{N}} \cdot Gini(T_{2})

Nejlepší oddíl je ten, pro který je Ginisplit(T) minimální. Nechť N je počet příkladů v uzlu předka, L , R je počet příkladů v levém a pravém potomkovi, li a ri je počet instancí i -té třídy u levého/pravého potomka. Poté se kvalita oddílu odhadne podle následujícího vzorce:

Gini_{{\text{split}}}={\frac {L}{N}}\cdot \left(1-\sum _{{i=1}}^{n}\left({\frac {l_ {i}}{L}}\right)^{2}\right)+{\frac {R}{N}}\cdot \left(1-\sum _{{i=1}}^{n} \left({\frac {r_{i}}{R}}\right)^{2}\right)\to \min

Pro snížení množství výpočtů lze vzorec transformovat:

Gini_{{\text{split}}}={\frac {1}{N}}\cdot \left(L\cdot \left(1-{\frac {1}{L^{2}}}\cdot \sum _{{i=1}}^{n}l_{i}^{2}\right)+R\cdot \left(1-{\frac {1}{R^{2}}}\cdot \součet _{{i=1}}^{n}r_{i}^{2}\vpravo)\vpravo)\do \min

Protože násobení konstantou nehraje roli při minimalizaci:

{\begin{array}{l}\displaystyle Gini_{{\text{split}}}=L-{\frac {1}{L}}\cdot \sum _{{i=1}}^{n} l_{i}^{2}+R-{\frac {1}{R}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\to \min \ \\displaystyle Gini_{{\text{split}}}=N-\left({\frac {1}{L}}\cdot \sum _{{i=1}}^{n}l_{i}^ {2}+{\frac {1}{R}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\right)\to \min \\\displaystyle { \tilde {G}}_{{\text{split}}}={\frac {1}{L}}\cdot \sum _{{i=1}}^{n}l_{i}^{2 }+{\frac {1}{R}}\cdot \sum _{{i=1}}^{n}r_{i}^{2}\to \max \end{array}}

Výsledkem je, že nejlepší oddíl bude ten, pro který je hodnota maximální. Při konstrukci „rozhodovacího stromu“ metodou CART se tedy hledá taková možnost větvení, při které se hodnota ukazatele Ginisplit(T) co nejvíce sníží .

Svěrací mechanismus

Tento mechanismus, nazývaný prořezávání stromu s minimálními náklady a složitostí (viz článek Pruning na anglické Wikipedii), algoritmus CART se zásadně liší od některých jiných algoritmů pro konstrukci rozhodovacího stromu. V uvažovaném algoritmu je prořezávání kompromisem mezi získáním stromu "správné velikosti" a získáním nejpřesnějšího odhadu klasifikace. Prořezávání (prořezávání) je důležité nejen pro zjednodušení stromů, ale také pro zamezení nadměrného osazení . Metoda spočívá v získání posloupnosti klesajících stromů, ale neberou se v úvahu všechny stromy, ale pouze „nejlepší zástupci“. [jeden]

Křížová validace

Křížová validace je nejsložitější a zároveň originální součástí algoritmu CART. Jedná se o způsob výběru finálního stromu za předpokladu, že soubor dat je malý nebo záznamy souboru dat jsou natolik specifické, že není možné soubor rozdělit na trénovací a testovací sady [1] .

Výhody a nevýhody metody

výhody:

Tato metoda je neparametrická , což znamená, že pro její aplikaci není třeba počítat různé parametry rozdělení pravděpodobnosti.
Pro aplikaci algoritmu CART není třeba předem vybírat proměnné, které se budou podílet na analýze: proměnné se vybírají přímo během analýzy na základě hodnoty Gini indexu .
CART snadno bojuje s odlehlými hodnotami: mechanismus „rozdělení“ (z angl. Splitting), zabudovaný do algoritmu, jednoduše umístí „emise“ do samostatného uzlu, což vám umožní vyčistit dostupná data od šumu.
Chcete-li použít tento algoritmus, není třeba před analýzou brát v úvahu žádné předpoklady nebo předpoklady.
Velkou výhodou je rychlost algoritmu.

nedostatky:

Rozhodovací stromy navržené algoritmem nejsou stabilní: výsledek získaný na jednom vzorku není reprodukovatelný na jiném (strom může růst, zmenšovat se, zahrnovat další prediktory atd.)
V případě, že je nutné sestavit strom se složitější strukturou, je lepší použít jiné algoritmy, protože CART nemusí identifikovat správnou datovou strukturu.

Poznámky

↑ 1 2 3 Chubukova I. A. Data Mining. M.: Binom, 2008
↑ Breiman L., Friedman JH, Olshen RA, & Stone CJ Klasifikace a regresní stromy. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984
↑ Tolstova Yu.N. Analýza sociologických dat. M.: Vědecký svět, 2000
↑ Rozhodovací stromy - matematický aparát CART. Část #1 // http://www.basegroup.ru/trees/math_cart_part1.htm Archivováno 22. ledna 2008 na Wayback Machine
↑ Elektronická učebnice "Statistica" // http://www.statsoft.ru/home/textbook.htm (nepřístupný odkaz)

Literatura

Paklin N.B., Oreshkov V.I. Kapitola 9. // Business Analytics: Od dat ke znalostem (+CD): Výukový program. 2. vyd. - Petrohrad. : Peter, 2013. - S. 459-465. - ISBN 978-5-459-00717-6 .