decision trees (DT) are everywhere

• daily life
• medicine
  symptoms $\ \ \to \ \ $ diagnosis
• playing Go, Chess, ..
• ..

optimal decicion trees

• data:
  $\quad \begin{array}{rcl} \mbox{training} & \ \Leftrightarrow \ & \mbox{testing}\\ \mbox{(over)fitting}& \ \Leftrightarrow \ & \mbox{generalization}\\ & \vdots &\\ \mbox{complex}& \ \Leftrightarrow \ & \mbox{simple} \end{array} $

whether to play tennis

• classical decision-tree example
• training data

• attributes: Outlook, Temperature, ..
• class: PlayTennis
• prediction / testing

decision tree complexities

• how to find out that
  • 'temperature' irrelevant
  • 'outlook' $\ \to\ $ 'overcast' enough
  • 'outlook' $\ \to\ $ 'humidity' does not need 'wind'
  • 'outlook' $\ \to\ $ 'wind' does not need 'humiditiy'
• generic problem
  : elimination of irrelevant attributes
  : taking relevant decisions first
• e.g. symptons $ \ \to\ $ diagnosis

simple rule - complicated tree

• starting with 'wind'
  : overfitting?

constructing decision trees

• CART (Classification and Regression Tree); binary
• ID3 (Iterative Dichotomiser)
  • select attributes with maximal information gain
  • minimizing entropy (uncertainty)

entropy

• probability density function (PDF)

• continuous or discrete (flipping a coin)
• entropy $\ \ H[p]=-\big\langle \ln(p)\big\rangle$

information gain

• entropy with respect to classification (yes/no)
• tennis example $\ \ N=14, \qquad N_{\mbox{yes}}=9, \qquad N_{\mbox{no}}=5$

• maximum $\ \ \log_2(M)=1, \qquad\quad M=2$

conditional entropy

• attribute 'outlook' has three possible events

• average (over all possible events) entropy

• information gain for attribute 'outlook'

• gains nearly a quarter

determining optimal attribute

'outlook'

'wind'

'humidity'

'temperature'

information gain

• constant $\ \ H_{\mbox{initial}}=0.940$

• 'outlook' best, 'temperature' miserable

recursive entropy weighting

• attribute with highet information gain
  $\to \ \ $ root of decision tree
• repeat recursively

Gini index

• one (of many) alternatives to information gain

• minimizing
• expanding the entropy for large probabilities

• where $ \ \ p_\alpha\to 1, \qquad\quad \sum_\alpha p_\alpha=1$

entropy vs. Gini

• case $\ \ M=2$

overfitting - pruning

• given enough nodes,
  one can fit every decision process

avoiding overfitting

• pre-pruning
  : stop when new branches become statistically insignificant
• post pruning
  : grow full tree, then remove branches
  $\rightarrow\ \ $ replacing subtree by leaf
• optimal tree
  performance $\ \ \leftrightarrow \ \ $ overfitting
  • performance with respect to validation data set
  • complexity penalty

range of algorithms

• CART (binary)
• ID3 (here + ...)
• C4.5 (includes pruning)
  • permits real-valued attributes
  • allow missing values
  • robust to noise

pruning example

evaluation of job offer

• here: only working principle
• increasing error rate
  increasing performance
  : statistical relevance, reduced complexity, ...

pruned graph

drawing graphs

• a range of open-source oftware:
  
• quick and dirty: GraphViz
  
  • nodes arranged automatically
  • fine tuning sometimes difficult
• for Linux: dot
  and neato / circo / twopi
  for distinct node location algorithms (all based on dot)

graph G { 
 one -- two -- three -- four -- one
/* run with
 * circo -Tpdf test.dot -o test.pdf
 * neato -Tpdf test.dot -o test.pdf
 * dot   -Tpdf test.dot -o test.pdf
 */
}

job evaluation graph

digraph G {                          // digraph: directed graph

         rankdir=TD;                 // top-down, try LR
         node   [penwidth=2.0]       // for all nodes

         salary      [shape="oval",color="#000099",fontcolor="#000099"]    
         increase    [shape="oval",color="#000099",fontcolor="#000099"]  
         hours       [shape="oval",color="#000099",fontcolor="#000099"]
         holidays    [shape="oval",color="#000099",fontcolor="#000099"]
         retirement  [shape="oval",color="#000099",fontcolor="#000099"]

         salary      [label="salary"]    
         increase    [label="prospective wage increase"]    
         hours       [label="# working hours"]    
         holidays    [label="# holidays"]    
         retirement  [label="early retirement possible?"]    

         good1     [shape="box",color="#009900",fontcolor="#009900"]
         good2     [shape="box",color="#009900",fontcolor="#009900"]
         good4     [shape="box",color="#009900",fontcolor="#009900"]
         bad1      [shape="box",color="#990000",fontcolor="#990000"]
         bad2      [shape="box",color="#990000",fontcolor="#990000"]
         bad4      [shape="box",color="#990000",fontcolor="#990000"]

         good1       [label="good"]    
         good2       [label="good"]    
         good4       [label="good"]    
         bad1        [label="bad"]    
         bad2        [label="bad"]    
         bad4        [label="bad"]    

       {rank=same; holidays; hours}                     // on same rank level
       {rank=same; bad1; retirement; good1; increase } 


          salary  -> holidays                         [label=" high"]
                     holidays -> retirement           [label=" <20"]
                     holidays -> good1                [label=" >20"]
                                 retirement -> good2          [label=" yes"]
                                 retirement -> bad2           [label=" no"]
          salary  -> hours                            [label=" low"]
                     hours    -> increase             [label=" <35"]
                     hours    -> bad1                 [label=" >35"]
                                 increase   -> bad4           [label=" <4%"]
                                 increase   -> good4          [label=" >4%"]

/* some info 
 *
 * http://www.graphviz.org/Documentation.php
 * dot -Tpdf test.dot -o test.pdf
*/
}