====== 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

===== Princip =====
==== Popis stromu ====

  * 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ů)
==== Tvorba rozhodovacího stromu ====

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

==== Algoritmus ====

<code>
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

</code>

==== Kriterium volby testovacího atributu ====
  * kriteriem volby je informační zisk **//G//**, jehož mírou je entropie **//E//**

=== Entropie ===
  * entropie vyjadřuje míru nehomogenity dat
== Entropie v booleovské klasifikaci ==
<m>E(S) = − p_+ log_2 p_+  −  p_-log_2 p_-</m>

== Entropie nabývající m různých hodnot ==
<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

=== Informační zisk (gain) ===
  * 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.

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


==== ID3 (C4.5, C5 (See5)) ====
  * postupuje shora dolů
  * používá hladového algorytmu
  * kritériem pro výběr atributu je maximalizace informačního zisku

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

=== Princip ===
  * 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í

=== Algoritmus ===

  * Pro všechny atributy
    - Vytvoř kontingenční tabulku výstup x atribut (rozměr k x l)
    - Pro všechny dvojice hodnot atributu spočti chí-kvadrátový test podtabulky (k x 2)
    - „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.
    - Zapamatuj si spojené kategorie a signifikanci chí-kvadrátu výsledné tabulky s redukovanou dimenzionalitou
    - Vyber atribut, kde je tato signifikance nejnižší
    - Pokud jsou splněny podmínky štěpení, rozděl případy v uzlu podle již „spojených“ kategorií

==== CART / C&RT ====
  * 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

=== Princip ===
  - strom necháme vyrůst do maximální šíře => vede k přeučení
  - 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)

==== QUEST ====
  * 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á)

==== GUIDE  ====
  * 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

==== MARS ====
  * 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

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