Učení rozhodovacího stromu, používané ve statistice, dolování dat a strojovém učení, používá rozhodovací strom jako prediktivní model, který mapuje pozorování o položce k závěrům o cílové hodnotě položky. Více popisné názvy pro takové stromové modely jsou klasifikační stromy nebo regresní stromy. V těchto stromových strukturách listy představují popisky tříd a větve představují spojení funkcí, které vedou k těmto popiskům tříd.
V rozhodovací analýze lze použít rozhodovací strom, který vizuálně a explicitně reprezentuje rozhodování a rozhodování. V datovém dolování popisuje rozhodovací strom data, ale ne rozhodnutí; výsledný klasifikační strom může být spíše vstupem pro rozhodování. Tato stránka se zabývá rozhodovacími stromy v datovém dolování.
Strom ukazující přežití cestujících na Titaniku („sibsp“ je počet manželů nebo sourozenců na palubě). Čísla pod listy ukazují pravděpodobnost přežití a procento pozorování v listu.
Učení rozhodovacího stromu je metoda běžně používaná při dolování dat. Cílem je vytvořit model, který předpovídá hodnotu cílové proměnné na základě několika vstupních proměnných. Příklad je uveden vpravo. Každý vnitřní uzel odpovídá jedné ze vstupních proměnných; pro každou z možných hodnot této vstupní proměnné jsou okraje k potomkům. Každý list představuje hodnotu cílové proměnné dané hodnotami vstupních proměnných reprezentovaných cestou od kořene k listu.
V datovém dolování lze rozhodovací stromy popsat také jako kombinaci matematických a výpočetních technik, které napomáhají popisu, kategorizaci a zobecnění daného souboru dat.
Data přicházejí v záznamech formuláře:
Závislá proměnná, Y, je cílová proměnná, kterou se snažíme pochopit, klasifikovat nebo zobecnit. Vektor x se skládá ze vstupních proměnných, x1, x2, x3 atd., které se pro tento úkol používají.
Termín Classification And Regression Tree (CART) analýza je zastřešující termín používaný k odkazu na oba výše uvedené postupy, poprvé zavedený Breiman et al. Stromy používané pro regresi a stromy používané pro klasifikaci mají některé podobnosti – ale také některé rozdíly, jako je postup používaný k určení, kde se rozdělit.
Některé techniky, často nazývané ensemblové metody, sestavují více než jeden rozhodovací strom:
Učení se pomocí rozhodovacího stromu je konstrukce rozhodovacího stromu z tréninkových n-ticů označených třídou. Rozhodovací strom je struktura podobná průtokovému grafu, kde každý vnitřní (ne-listový) uzel označuje test na atributu, každá větev představuje výsledek testu a každý listový (nebo terminálový) uzel má popisek třídy. Nejvyšší uzel ve stromu je kořenový uzel.
ID3 a CART byly vynalezeny nezávisle přibližně ve stejnou dobu (b/w 1970-80), přesto sledují podobný přístup pro učení se rozhodovacímu stromu z tréninkových tuplů.
Algoritmy pro konstrukci rozhodovacích stromů obvykle pracují shora dolů tak, že v každém kroku vyberou proměnnou, která nejlépe rozdělí sadu položek. Různé algoritmy používají pro měření „nejlepší“ různé metriky. Ty obecně měří homogenitu cílové proměnné v rámci podskupin. Některé příklady jsou uvedeny níže. Tyto metriky jsou aplikovány na každou kandidátskou podskupinu a výsledné hodnoty jsou kombinovány (např. zprůměrovány), aby poskytly měřítko kvality rozdělení.
Giniho nečistota, používaná algoritmem CART (klasifikace a regresní strom), je míra, jak často by náhodně vybraný prvek ze sady byl nesprávně označen, kdyby byl náhodně označen podle rozložení popisků v podmnožině. Giniho nečistota může být vypočtena součtem pravděpodobnosti, že každá položka bude vybrána, krát pravděpodobnosti chyby v kategorizaci této položky. Svého minima (nuly) dosáhne, když všechny případy v uzlu spadají do jedné cílové kategorie.
Pro výpočet Giniho nečistoty pro množinu položek předpokládejme, že i převezme hodnoty v {1, 2, …, m}, a nechť fi je zlomek položek označených hodnotou i v množině.
Používá algoritmy generování stromů ID3, C4.5 a C5.0. Získávání informací je založeno na konceptu entropie z teorie informací.
V rozhodovacím stromu všechny cesty od kořenového uzlu k listovému uzlu pokračují spojkou, neboli AND.
V rozhodovacím grafu je možné pomocí disjunkcí (ORs) spojit další dvě cesty pomocí MML (Minimum message length). Rozhodovací grafy byly dále rozšířeny, aby bylo možné se dynamicky učit dříve neuvedené nové atributy a používat je na různých místech v grafu. Obecnější schéma kódování vede k lepší přesnosti predikce a pravděpodobnostnímu skórování log-loss.[citace nutná] Obecně platí, že rozhodovací grafy odvozují modely s menším počtem listů než rozhodovací stromy.
Vyhledávání pomocí evolučních algoritmů
Evoluční algoritmy byly použity k vyhnutí se lokálním optimálním rozhodnutím a prohledávání prostoru rozhodovacího stromu s malým a priori zkreslením.