AUT476 INTRODUCTION TO MACHINE
LEARNING MODULE 4
,Module 4 – Syllabus
4.1 Decision Trees- 4.2 Entropy, 4.3 Information Gain, 4.4 Tree construction, 4.5 ID3, 4.6 Issues in Decision
Tree learning- Avoiding Over-fitting, Reduced Error Pruning, The problem of Missing Attributes, 4.7 Gain
Ratio, 4.8 Classification by Regression (CART), 4.9 Neural Networks- The Perceptron, 4.10 Activation
Functions, 4.11 Training Feed Forward Network by Back Propagation.
4.1 Decision Trees
➢ Explain the concept of decision tree with an example
➢ Explain/Compare different types of decision trees
Decision Trees are a type of Supervised Machine Learning where the data is continuously
split according to a certain parameter. The tree can be explained by two entities, namely
decision nodes and leaves. The leaves are the decisions or the final outcomes. And the
decision nodes are where the data is split.
An example of a decision tree can be explained using above binary tree. Let’s say you want
to predict whether a person is fit given their information like age, eating habit, and physical
activity, etc. The decision nodes here are questions like ‘What’s the age?’, ‘Does he
exercise?’, ‘Does he eat a lot of pizzas’? And the leaves, which are outcomes like either ‘fit’,
or ‘unfit’. In this case this was a binary classification problem (a yes no type problem).
There are two main types of Decision Trees:
1. Classification trees (Yes/No types) (can explain ID3 algorithm)
What we’ve seen above is an example of classification tree, where the outcome was a
variable like ‘fit’ or ‘unfit’. Here the decision variable is Categorical. Tree models where the
target variable can take a discrete set of values are called classification trees. In these tree
structures, leaves represent class labels and branches represent conjunctions of features that
lead to those class labels.
2. Regression trees (Continuous data types) – (can explain CART algorithm)
Decision trees where the target variable can take continuous values (real numbers) like the
price of a house, are called regression trees.
We Explain Classification trees using an example
1
,Consider the data given in Table 8.1 which specify the features of certain vertebrates
and the class to which they belong. For each species, four features have been
identified: “gives birth”, ”aquatic animal”, “aerial animal” and “has legs”. There are
five class labels, namely, “amphibian”, “bird”, “fish”, “mammal” and “reptile”. The
problem is how to use this data to identify the class of a newly discovered vertebrate.
Construction of the tree
Step 1
We split the set of examples given in Table 8.1 into disjoint subsets according to the
values of the feature “gives birth”. Since there are only two possible values for this
feature, we have only two subsets: One subset consisting of those examples for which
the value of “gives birth” is “yes” and one subset for which the value is “no”.
2
, Step 2
We now consider the examples in Table 8.2. We split these examples based on the
values of the feature “aquatic animal”. There are three possible values for this feature.
However, only two of these appear in Table 8.2. Accordingly, we need consider only
two subsets. These are shown in Tables 8.4 and 8.5.
• Table 8.4 contains only one
example and hence no further splitting
is required. It leads to the assignment
of the class label “fish”.
• The examples in Table 8.5 need to
be split into subsets based on the
values of “aerial animal”. It can be
seen that these subsets immediately
lead to unambiguous assignment of
class labels: The value of “no” leads to
“mammal” and the value “yes” leads
to ”bird”. At this stage, the
classification tree is as shown in
Figure 8.4
Step 3
Next we consider the examples in Table 8.3 and split them into disjoint subsets based
on the values of “aquatic animal”. We get the examples in Table 8.6 for “yes”, the
examples in Table 8.8 for “no” and the examples in Table 8.7 for “semi”. We now
split the resulting subsets based on the values of “has legs”, etc. Putting all these
together, we get the the diagram in tree (Figure 8.5) for the data in Table 8.1
3
LEARNING MODULE 4
,Module 4 – Syllabus
4.1 Decision Trees- 4.2 Entropy, 4.3 Information Gain, 4.4 Tree construction, 4.5 ID3, 4.6 Issues in Decision
Tree learning- Avoiding Over-fitting, Reduced Error Pruning, The problem of Missing Attributes, 4.7 Gain
Ratio, 4.8 Classification by Regression (CART), 4.9 Neural Networks- The Perceptron, 4.10 Activation
Functions, 4.11 Training Feed Forward Network by Back Propagation.
4.1 Decision Trees
➢ Explain the concept of decision tree with an example
➢ Explain/Compare different types of decision trees
Decision Trees are a type of Supervised Machine Learning where the data is continuously
split according to a certain parameter. The tree can be explained by two entities, namely
decision nodes and leaves. The leaves are the decisions or the final outcomes. And the
decision nodes are where the data is split.
An example of a decision tree can be explained using above binary tree. Let’s say you want
to predict whether a person is fit given their information like age, eating habit, and physical
activity, etc. The decision nodes here are questions like ‘What’s the age?’, ‘Does he
exercise?’, ‘Does he eat a lot of pizzas’? And the leaves, which are outcomes like either ‘fit’,
or ‘unfit’. In this case this was a binary classification problem (a yes no type problem).
There are two main types of Decision Trees:
1. Classification trees (Yes/No types) (can explain ID3 algorithm)
What we’ve seen above is an example of classification tree, where the outcome was a
variable like ‘fit’ or ‘unfit’. Here the decision variable is Categorical. Tree models where the
target variable can take a discrete set of values are called classification trees. In these tree
structures, leaves represent class labels and branches represent conjunctions of features that
lead to those class labels.
2. Regression trees (Continuous data types) – (can explain CART algorithm)
Decision trees where the target variable can take continuous values (real numbers) like the
price of a house, are called regression trees.
We Explain Classification trees using an example
1
,Consider the data given in Table 8.1 which specify the features of certain vertebrates
and the class to which they belong. For each species, four features have been
identified: “gives birth”, ”aquatic animal”, “aerial animal” and “has legs”. There are
five class labels, namely, “amphibian”, “bird”, “fish”, “mammal” and “reptile”. The
problem is how to use this data to identify the class of a newly discovered vertebrate.
Construction of the tree
Step 1
We split the set of examples given in Table 8.1 into disjoint subsets according to the
values of the feature “gives birth”. Since there are only two possible values for this
feature, we have only two subsets: One subset consisting of those examples for which
the value of “gives birth” is “yes” and one subset for which the value is “no”.
2
, Step 2
We now consider the examples in Table 8.2. We split these examples based on the
values of the feature “aquatic animal”. There are three possible values for this feature.
However, only two of these appear in Table 8.2. Accordingly, we need consider only
two subsets. These are shown in Tables 8.4 and 8.5.
• Table 8.4 contains only one
example and hence no further splitting
is required. It leads to the assignment
of the class label “fish”.
• The examples in Table 8.5 need to
be split into subsets based on the
values of “aerial animal”. It can be
seen that these subsets immediately
lead to unambiguous assignment of
class labels: The value of “no” leads to
“mammal” and the value “yes” leads
to ”bird”. At this stage, the
classification tree is as shown in
Figure 8.4
Step 3
Next we consider the examples in Table 8.3 and split them into disjoint subsets based
on the values of “aquatic animal”. We get the examples in Table 8.6 for “yes”, the
examples in Table 8.8 for “no” and the examples in Table 8.7 for “semi”. We now
split the resulting subsets based on the values of “has legs”, etc. Putting all these
together, we get the the diagram in tree (Figure 8.5) for the data in Table 8.1
3
