Decision Tree
The General Algorithm
Unit-IV
General Algorithm
❖ The objective of a decision tree algorithm is to construct a tree
T from a training set S.
❖ lf all the records ins belong to some class c(subscribed =yes, for
example), or if S is sufficiently pure (greater than a preset
threshold), then that node is considered a leaf node and
assigned the label c.
❖ The purity of a node is defined as its probability of the
corresponding class
❖ The algorithm constructs subtrees T1, T2 ••• for the subsets of s
recursively until one of the following criteria is met:
❖ All the leaf nodes in the tree satisfy the minimum purity threshold.
❖ The tree cannot be further split with the preset minimum purity
threshold.
❖ Any other stopping criterion is satisfied (such as the maximum depth of
the tree).
The first step in constructing a decision tree is to choose
the most informative attribute.
A common way to identify the most informative attribute
is to use entropy-based methods, which are used by
decision tree learning algorithms such as ID3 (or Iterative
Dichotomiser 3)
The entropy methods select the most informative attribute
based on two basic measures:
◦ Entropy, which measures the impurity of an attribute
◦ Information gain, which measures the purity of an attribute
Given a class X and its label x Є X , let P(x) be the probability
of x. Hx the entropy of X, is defined as
Let x = 1 represent heads and x = 0 represent tails. The entropy of the unknown result of the
next toss is maximized when the coin is fair. That is, when heads and tails have equal
probability P( x = 1) = P( x = 0) = 0.5, entropy Hx = - (0.5 x log1 0.5 + 0.5 x log2 0.5) = 1 .
Detecting Significant Splits
Decision Tree Algorithms
Decision tree induction is a top-down, recursive and divide-and-conquer
approach.
The procedure is to choose an attribute and split it into from a larger
training set into smaller training sets.
Different algorithms have been proposed to take a good control over
1. Choosing the best attribute to be splitted, and
2. Splitting criteria
Several algorithms have been proposed for the above tasks. In this lecture,
we shall limit our discussions into three important of them
• ID3
• C 4.5
• CART
CS 40003: Data Analytics 9
ID3: Decision Tree Induction Algorithms
Quinlan [1986] introduced the ID3, a popular short form of Iterative
Dichotomizer 3 for decision trees from a set of training data.
In ID3, each node corresponds to a splitting attribute and each arc is a
possible value of that attribute.
At each node, the splitting attribute is selected to be the most informative
among the attributes not yet considered in the path starting from the root.
CS 40003: Data Analytics 10
Algorithm ID3
In ID3, entropy is used to measure how informative a node is.
◦ It is observed that splitting on any attribute has the property that average entropy
of the resulting training subsets will be less than or equal to that of the previous
training set.
ID3 algorithm defines a measurement of a splitting called Information
Gain to determine the goodness of a split.
◦ The attribute with the largest value of information gain is chosen as the splitting
attribute and
◦ it partitions into a number of smaller training sets based on the distinct values of
attribute under split.
CS 40003: Data Analytics 11
Defining Information Gain
CS 40003: Data Analytics 12
Defining Information Gain
CS 40003: Data Analytics 13
Defining Information Gain
Definition 9.4: Weighted Entropy
CS 40003: Data Analytics 14
ID3 Algorithm
Information Gain Calculation
Age Eye-sight Astigmatism Use type Class
1 1 1 1 3
1 1 1 2 2
1 1 2 1 3
1 1 2 2 1
1 2 1 1 3
1 2 1 2 2
1 2 2 1 3
1 2 2 2 1
16
CS 40003: Data Analytics
Calculating Information Gain
Age Eye-sight Astigmatism Use type Class
2 1 1 1 3
2 1 1 2 2
2 1 2 1 3
2 1 2 2 1
2 2 1 1 3
2 2 1 2 2
2 2 2 1 3
2 2 2 2 3
CS 40003: Data Analytics 17
Calculating Information Gain
Age Eye-sight Astigmatism Use type Class
3 1 1 1 3
3 1 1 2 3
3 1 2 1 3
3 1 2 2 1
3 2 1 1 3
3 2 1 2 2
3 2 2 1 3
3 2 2 2 3
CS 40003: Data Analytics 18
Algorithm C 4.5 : Introduction
CS 40003: Data Analytics 19
Algorithm C4.5 : Introduction
CS 40003: Data Analytics 20
Algorithm: C 4.5 : Introduction
Algorithm: C 4.5 : Gain Ratio
Definition 9.8: Gain Ratio
CS 40003: Data Analytics 22
CART Algorithm
CS 40003: Data Analytics 23
Gini Index of Diversity
Definition 9.6: Gini Index
CS 40003: Data Analytics 24
Gini Index of Diversity
Definition 9.7: Gini Index of Diversity
CS 40003: Data Analytics 25
Gini Index of Diversity and CART
CS 40003: Data Analytics 26
CART Algorithm : Illustration
Example 9.15 : CART Algorithm
Suppose we want to build decision tree for the data set EMP as given in the
table below.
Age Tuple# Age Salary Job Performance Select
Y : young 1 Y H P A N
M : middle-aged
2 Y H P E N
O : old
3 M H P A Y
Salary
4 O M P A Y
L : low
M : medium 5 O L G A Y
H : high 6 O L G E N
Job 7 M L G E Y
G : government 8 Y M P A N
P : private
9 Y L G A Y
Performance 10 O M G A Y
A : Average
11 Y M G E Y
E : Excellent
12 M M P E Y
Class : Select
13 M H G A Y
Y : yes
N : no 14 O M P E N
CS 40003: Data Analytics 27
CART Algorithm : Illustration
CS 40003: Data Analytics 28
CART Algorithm : Illustration
Yes No
{O} {Y,M}
CS 40003: Data Analytics 29
CART Algorithm : Illustration
Yes No
{H} {L,M}
CS 40003: Data Analytics 30
Evaluating a Decision Tree
Decision trees use greedy algorithms, in that they always
choose the option that seems the best available at that
moment.
At each step, the algorithm selects which attribute to use for
splitting the remaining records.
This selection may not be the best overall, but it is
guaranteed to be the best at that step.
There are a few ways to evaluate a decision tree.
First, evaluate whether the splits of the tree makesense.
Having too many layers and obtaining nodes with few
members might be signs of overfitting.
In overfitting, the model fits the training set well, but it
performs poorly on the new samples in the testing set.
Figure illustrates the performance of an
overfit model
For decision tree learning, overfitting can be caused by
either the lack of training data or the biased data in the
training set.
Two approaches can help avoid overfitting in decision
tree learning.
• Stop growing the tree early before it reaches the point
where all the training data is perfectly classified.
• Grow the full tree, and then post-prune the tree with
methods such as reduced-error pruning and rule-based
post pruning.
Decision trees are computationally inexpensive, and it is
easy to classify the data.
The outputs are easy to interpret as a fixed sequence of
simple tests.
Decision Trees in R
In R, rpart is for modeling decision trees, and an
optional package rpart .
plot enables the plotting of a tree.
In R, first set the working directory and initialize the
packages.
setwd { "c: /")
[Link]("[Link]") # install package [Link]
library("rpart") # load libraries
library("[Link]")
The working directory contains a
comma-separated-value (CSV) file named DTdata. csv.
Play,Outlook,Temperature,Humidity,Wind
yes,ra:ny,cool,normal,FALSE
no,rainy,cool,normal,TRUE
yes,overcast,hot,high,FALSE
Display a summary of play_decision.
summary(play_decision)
Play·no :3 yes:7
Outlook Temperature Humidity overcast::2.
rain;.4· sunny :4 cool:5 bot :2 mild:3
high :·l normal:6
The following code snippet shows how to use the rpart
function to construct a decision tree.
fit <- rpart(Play- Outlook+ Temperature +Humidity+
Wind,method="class”,
data=play_decision,
control=[Link](minsplit=1),
parms=list(split=‘information’))
Enter sununary (fit) to produce a summary of the
model built from rpart.
The output produced by the summary is difficult to
read and comprehend.
The rpart. plot () function from the rpart. plot
package can visually represent the output in a
decision tree
[Link](fit, type=4, extra=1)
Parameter type is a character string denoting the type
of the predicted value.
Set it to either p rob or class to predict using a decision
tree model and receive the result as either the class
probabilities or just the class