Rozhodovací stromy

• induktivní odvozovací metoda
• strategie rozděl a panuj
• její reprezentací je strom rozhodnutí - rozhodovací strom
• dělíme na
  • binární stromy (vždy dvě větve z uzlu)
    • rychlejší výpočet (méně možností)
    • více uzlů
    • zpravidla přesnější
    • klasifikace
  • obecné stromy
    • lepší interpretovatelnost člověkem
    • menší strom
    • segmentace

• Kořen reprezentuje celou množinu vstupních dat.
• Uzel, který není listem, reprezentuje rozhodovací pravidlo pro dělení (větvení).
• Větev reprezentuje výsledek pravidla
• Listy reprezentují třídy do kterých jsou data klasifikovány. (případně hodnoty atributů)

1. Projdi trénovací množinu a najdi nejlepší atribut pro rozdělení
2. Rozděl množinu podle hodnoty atributu
3. Rekurzivně zpracuj každou část

BuildTree(Node t, Training database D, Split Selection Method  SSSS )

 Apply  SSSS to D to find splitting criterion
 if (t is not a leaf node)
    Create children nodes of t
    Partition D into children partitions
    Recurse on each partition
 endif

• kriteriem volby je informační zisk G, jehož mírou je entropie E

• entropie vyjadřuje míru nehomogenity dat

<m>E(S) = − p_+ log_2 p_+ − p_-log_2 p_-</m>

<m>E(S) = - sum{i=1}{m}{p_i log_2 p_i}</m> ,

kde <m>p_i</m> je pravděpodobnost, že vzorek patří do třídy C

• očekávaná míra redukce entropie množiny S, při rozdělení podle atributu A

<m>G(S,A) = E(S) - sum{v in V(A)}{}{} delim{|}{S_v}{|}/delim{|}{S}{|}E(S_v)</m> ,

kde <m>V(A)</m> je množina možných hodnot <m>A</m>,
<m>S_v</m> je podmnožina <m>S</m>, kde vzorky mají hodnotu atributu <m>A = v</m>.

• E(S) je entropie množiny S,
• druhý člen je hodnota entropie množiny S, při rozdělení podle atributu A.

• ID3
• CHAID
• CART Clasification and regreion tree
• QUEST
• MARS
• TreeNet - namisto stromu, les malych stromu

• postupuje shora dolů
• používá hladového algorytmu
• kritériem pro výběr atributu je maximalizace informačního zisku

• CHi-squared Automatic Interaction Detector
• Jeden z nejrozšířenějších rozhodovacích stromů v komerční oblasti
• obecný strom

• Začíná se u celého souboru
• Postupné větvení / štěpení souboru (přípustné je rozdělení na libovolný počet větví vycházejících z jednoho uzlu)
• rekurzivní algoritmus - každý uzel se dělí podle stejného předpisu
• Zastaví se, pokud neexistuje statisticky signifikantní rozdělení ⇒ vzniká list
  • Obvykle je navíc podmínka minimálního počtu případů v uzlu a/nebo v listu, příp. maximální hloubky stromu
• Používá kontingenční tabulky
• Exhaustive CHAID – provádí podrobnější prohledávání + adjustaci signifikancí při většinou stále únosné rychlosti počítání

• Pro všechny atributy
  1. Vytvoř kontingenční tabulku výstup x atribut (rozměr k x l)
  2. Pro všechny dvojice hodnot atributu spočti chí-kvadrátový test podtabulky (k x 2)
  3. „Podobné“ (=ne signifikantně odlišné) dvojice postupně spojuj (počínaje nejnižšími hodnotami chí-kvardrátu) a přepočítávej výchozí kontingenční tabulku. Zastav se, když signifikance všech zbylých podtabulek je vyšší než stanovená hodnota.
  4. Zapamatuj si spojené kategorie a signifikanci chí-kvadrátu výsledné tabulky s redukovanou dimenzionalitou
  5. Vyber atribut, kde je tato signifikance nejnižší
  6. Pokud jsou splněny podmínky štěpení, rozděl případy v uzlu podle již „spojených“ kategorií

• Classification And Regression Tree
• binární strom
• Algoritmus je založen na počítání míry diverzity („nečistoty“) uzlu
• Používa se Giniho míra diverzity

<m>div_{Gini} = 1 – sum{}{}{p^{2}_{i}}</m>

,kde <m>p_i</m> jsou relativní četnosti v uzlech

1. strom necháme vyrůst do maximální šíře ⇒ vede k přeučení
2. zpětně odstraníme listy a větve, které podle vhodně zvoleného statistického kriteria nelze považovat za významné (většinou se používá cross-validation)

• Quick, Unbiased and Efficient Statistical Tree
• Kriterium volby dělícího atributu na základě statistického testu nezávislosti atribut x výstup ⇒ mírně suboptimální, ale rychlé, navíc výběr štěpící proměnné je nevychýlený
• nominální výstup (=závisle proměnná)

• Generalized, Unbiased, Interaction Detection and Estimation
• kromě po částech konstantní aproximace nabízí i po částech polynomiální
  • „kříženec“ regresního stromu a mnohorozměrné regrese
  • vhodné pro data, u kterých může být na místě jistá míra spojitosti aproximace

• Multivariate Adaptive Regression Splines
• Metoda blízce příbuzná rozhodovacím stromům
  • lze si ji představit jako jakýsi rozklad aproximační funkce do elementárních „stromů“ s jedním štěpením a s lineární namísto konstantní aproximací v obou polopřímkách

• Namísto jednoho velkého stromu „les“ malých
• Výsledná predikce vzniká váženým součtem predikcí jednotlivých složek