Decision Trees - Content

1. Decision Trees
2. Regresion Trees
3. Pruning
4. Applications

Decision Trees - Introduction

• What is a decision tree?
  • A hierarchichal data structure
  • Implements a divide and conquer strategy
  • An efficient and non-parametric method
  • Used for the classification and regression tasks
  • Built from a labeled dataset
  • Can be converted into a set of rules

Decision Trees - Classification

• Non-parametric estimation
  • Divides the input space into local regions
  • According to a distance measure (i.e. euclidean norm)
  • Input \(\rightarrow\) uses the corresponding local model created from the training set
• Hierarchical supervised model
• Local region identified by a sequence of recursive partitions (Splits)

Decision Trees - Classification

Decision Trees - Classification

Decision Trees - Classification

• Each branch represents a decision
• Uses a divide and conquer method
• Each node refers to a particular attribute
• Leaf nodes give the classification that applies to instances that reach the leaf through a path
• Number of children of a node is the number of values of the attribute
• Can use with numerical attributes
  • <, >, =

Decision Trees - C4.5

Decision Trees - C4.5

Decision Trees - ID3

• ID3 was the original version (previous to C4.5)
  • Top-down
  • Greedy
• Algorithm
  • Choose a root attribute
    • The one that best classify the examples
    • (statistical measure)
  • Create a descendant node for each value of the attribute of the parent node
    • Assigns examples to the appropriate branch
  • Repeats the process for each descendant node

Decision Trees - ID3

• How does it partitions the data?
  • We quantify the partitions
  • A measure of impurity
  • A partition is pure if, after such a partiion, for all its branches, all instances of each branch belong to the same class
  • How can we measure impurity?
    • Entropy (Ross Quinlan 1986)
    • Gini index (Breiman et al. 1984)
    • Classification error

Decision Trees - ID3

• Given a collection \(S\) of positive and negative examples of a concept, the entropy of \(S\), relative to its boolean classification is:
• \(Entropy(S) = -p_{+} \log_2 p_{+} - p_{-} \log_2 p_{-}\)
• \(p_{+}\): Proportion of positive examples in \(S\)
• \(p_{-}\): Proportion of negative examples in \(S\)
• In general: \(Entropy(S) = \sum\limits_{i=1}^c - p_i(\log_2 p_i)\)
  • \(p_i\): proportion of examples of \(S\) that belong to class \(i\)

\[Entropy([9+, 5-]) = -(9/14) \log_2 (9/14) -(5/14) \log_2 (5/14)\] \[= 0.940\]

Decision Trees - ID3

• If all examples belong to one class, the entropy is 0.
• If we have an equal number of positive and negative examples, the entropy is 1.

Decision Trees - ID3

• The entropy function relative to boolean classification as the proportion \(p+\) of positive examples increases
  • Varies between 0 and 1

Decision Trees - ID3

• Information gain
  • Based on entropy
    • Measure used in information theory
    • Characterizes the impurity of a set of examples
  • Used to evaluate the effectiviness of an attribute at classifying examples
  • It measures the expected reduction of entropy caused by the partition of the examples according to an attribute
  • \(Gain(S,A)\) for attribute \(A\) in relation to the set of examples in \(S\) is defined as:

\[Gain(S,A) = Entropy(S) - \sum\limits_{v \in Values(A)} \frac{|S_v|}{|S|}Entropy(S_v)\] - \(Values(A)\): Set of values that attribute \(A\) may take - \(S_v\): Subset of \(S\) for which attribute \(A\) has value \(v\) - i.e. \(S_v={s \in S | A(S) = v}\)

Decision Trees - ID3 - Example

Decision Trees - ID3 - Example

• 14 examples, 9 positive and 5 negative
• Attribute “Wind”
  • Wind = Weak: 6 positive and 2 negative
  • Wind = Strong: 3 positive and 3 negative
• Then, for the wind attribute:
  • \(S_{Weak}[6+, 2-]\)
  • \(S_{Strong}[3+, 3-]\)

Decision Trees - ID3 - Example

\(Gain(S, Wind) = Entropy(S) - \sum\limits_{v \in \{Weak, Strong\}} \frac{|S_v|}{|S|} Entropy(S_v)\)

\(=Entropy(S) - (8/14)Entropy(S_{Weak}) - (6/14)Entropy(S_{Strong})\)

\(=Entropy(S) - (8/14)(-6/8 \log_2 6/8 - 2/8 \log_2 2/8)\) \(-(6/14)(-3/6 \log_2 3/6 - 3/6 \log_2 3/6)\)

\(= 0.940 - (8/14) 0.811 - (6/14) 1.0\)

\(= 0.048\)

Decision Trees - ID3 - Example

Decision Trees - ID3 - Search Space

• The search space composed by all possible decision trees
• ID3 performs a hill-climbing search in the search space
• Starts with an empty tree
• Progressively considers more elaborated hypotheses that correctly classify the training data
• The evaluation function used to guide hill-climbing is information gain

Decision Trees - ID3 - Search Space

• ID3 (search characteristics)
  • The hypothesis space of decision trees is complete
    • Every discrete valued function can be represented by the tree
    • There is no risk for searching in an incomplete hipothesis space

Decision Trees - ID3 - Search Space

• ID3 (search characteristics)
  • Keeps only the current hypothesis
  • Doesn’t keep all hipotheses consistent with the training examples
  • In its pure form, it doesn’t perform back-tracking
  • Might find a non-optimal solution (local-maxima)

Decision Trees - ID3 - Inductive Bias

• Inductive bias in decision trees
  • Preference for short trees over large ones
  • Preference for trees that put attributes with high information gain close to the root
• Why choosing short over large trees?
  • Ocam’s razor

Decision Trees - ID3 - Overfitting

• Given a hypothesis space \(H\), we say that a hypothesis \(h \in H\) overfits the training data if there exists a hypothesis \(h' \in H\), such that \(h\) has an error smaller than \(h'\) over the training data, but that \(h'\) has an error smaller than \(h\) over the total instances distribution.
  • Training data examples are memorized

Decision Trees - ID3 - Overftiting

• Overfitting may happen because
  • There is noise in the data
  • The data sample is not representative

Decision Trees - ID3 - Overfitting

• How can we avoid overfiting?
  • Stop the tree growth before we reach the overfitting
  • Get an overfitted tree and then prune it (post-prune)

Decision Trees - ID3 - Pruning

• Use of a validation set to avoid overfitting
  • Reduced-error-pruning
    • Considers all the tree nodes for pruning
    • Branches of the tree are eliminated if the resultant tree doesn’t decreases its efficiency
    • We keep as leaf node the most common class of the nodes related with that leaf node

Decision Trees - ID3 - Pruning

• Post-pruning rule
  • Create the whole tree
  • Convert the tree to rules (one rule for each path in the tree from the root to a leaf node)
  • Prune by eliminating any precondition that results in an enhancement of the estimated efficiency
  • Order the rules by its estimated efficiency and consider them in that sequence when classifying new instances

Decision Trees - ID3 - Exercise (to be completed as homework)

• Which attribute is used as the root node in the previous example?
  • Sky, temperature, humidity, or wind?

Regression Trees

• Regresion trees are built almost identically to a classification decision tree
• The impurity measure changes
• The quality (how-good-it-is) of the partition is measured with the mean-square-error (mse)
• Implies minimizing the sum of the expected variance for the two resulting nodes
  • \(\arg\min_{x_j \leq x_j^R, j=1, \dots, M} [P_lVar(Y_l) + P_rVar(Y_r)]\)
  • \(Var(Y_l)\) and \(Var(Y_r)\) \(\rightarrow\) the response vectors for the left and right child nodes
  • \(x_j \leq x_j^R, j=1, \dots, M\) \(\rightarrow\) optimal partition option that satisfies the equation

Regression Trees

Regression Trees

• More detail on how regression trees are built
  • http://www.youtube.com/watch?v=zvUOpbgtW3c

Decision Trees - Extracting rules

• Decision trees make their own attributes selection process
• Some attributes are not considered
• Attributes closer to the root are more important in a global way
• Easy to understand
• Create rules following the conditions of the path from the root to the leafs
  • If humidity = normal then
    • If \(\dots\)

Decision Trees - Extracting rules

• We will cover rule-learning algorithms in the next class

Multivariable Trees

• In the uni-variable case, we only consider the value of an attribute to create a split
• In the multi-variable case, we can use all attributes
  • More general

Decision Trees - Notes

• Decision trees with numerical values (C4.5 or J48)
• What do we do with missing values?
• Complexity for building a tree?
  • \(O(mn \log n) + O(n(\log n)^2)\)
  • \(n\) is the number of data examples
  • \(m\) is the number of attributes
  • First term \(\rightarrow\) build the decision tree without pruning
  • Second term \(\rightarrow\) pruning

Decision Trees - Extensions

• Change the search strategy from hill climbing to beam search or look-ahead
• Generate several decision trees and then combine the results
  • In parallel way with several subsets of data (bagging)
  • In sequential way considering the classification errors and modifying the data (boosting)
  • Using several training data samples and introducing randomness in the way in which attributes are considered in each node (random forest)