Decision tree learning is a method for approximating
discrete-valued target functions, in which the learned
function is represented by a decision tree.
2
DECISION T R E E R E P R E S E N T A T I O N
FIGURE: A
decision tree for the
concept PlayTennis.
An example is
classified by sorting
it through the tree to
the appropriate leaf
node, then returning
the classification
associated with this
leaf
3
• Decision trees classify instances by sorting them down the tree from the root to
some leaf node, which provides the classification of the instance.
• Each node in the tree specifies a test of some attribute of the instance, and each
branch descending from that node corresponds to one of the possible values for
this attribute.
• An instance is classified by starting at the root node of the tree, testing the
attribute specified by this node, then moving down the tree branch corresponding
to the value of the attribute in the given example. This process is then repeated
for the subtree rooted at the new node.
4
• Decision trees represent a disjunction of conjunctions of constraints on the
attribute values of instances.
• Each path from the tree root to a leaf corresponds to a conjunction of attribute
tests, and the tree itself to a disjunction of these conjunctions
For example,
The decision tree shown in above figure corresponds to the expression
(Outlook = Sunny 𝖠 Humidity = Normal)
(Outlook = Overcast)
(Outlook = Rain 𝖠 Wind = Weak)
5
APPROPRIATE PROBLEMS F O R
DECISION T R E E L E A R N I N G
Decision tree learning is generally best suited to problems with the following
characteristics:
1. Instances are represented by attribute-value pairs – Instances are described by
a fixed set of attributes and their values
2. The target function has discrete output values – The decision tree assigns a
Boolean classification (e.g., yes or no) to each example. Decision tree methods
easily extend to learning functions with more than two possible output values.
3. Disjunctive descriptions may be required
6
4. The training data may contain errors – Decision tree learning methods are
robust to errors, both errors in classifications of the training examples and errors
in the attribute values that describe these examples.
5. The training data may contain missing attribute values – Decision tree
methods can be used even when some training examples have unknown values
• Decision tree learning has been applied to problems such as learning to classify
medical patients by their disease, equipment malfunctions by their cause, and
loan applicants by their likelihood of defaulting on payments.
• Such problems, in which the task is to classify examples into one of a discrete set
of possible categories, are often referred to as classification problems.
7
T H E BASIC DECISION T R E E L E A R N I N G
ALGORITHM
• Most algorithms that have been developed for learning decision trees are
variations on a core algorithm that employs a top-down, greedy search through the
space of possible decision trees. This approach is exemplified by the ID3
algorithm and its successor C4.5
8
Choosing the Splitting Attribute
At each node, available attributes are evaluated on the basis of separating the classes
of the training examples. A Goodness function is used for this purpose.
Typical goodness functions:
information gain (ID3/C4.5)
information gain ratio
gini index
9
What is the ID3 algorithm?
• ID3 stands for Iterative Dichotomiser 3
• ID3 is a precursor to the C4.5 Algorithm.
• The ID3 algorithm was invented by Ross Quinlan in 1975
• Used to generate a decision tree from a given data set by employing a top-down,
greedy search, to test each attribute at every node of the tree.
• The resulting tree is used to classify future samples.
10
ID3 algorithm
ID3(Examples, Target_attribute, Attributes)
Examples are the training examples. Target_attribute is the attribute whose value is to be predicted
by the tree. Attributes is a list of other attributes that may be tested by the learned decision tree.
Returns a decision tree that correctly classifies the given Examples.
• Create a Root node for the tree
• If all Examples are positive, Return the single-node tree Root, with label = +
• If all Examples are negative, Return the single-node tree Root, with label = -
• If Attributes is empty, Return the single-node tree Root, with label = most common value of
Target_attribute in Examples
11
• Otherwise Begin
• A ← the attribute from Attributes that best* classifies Examples
• The decision attribute for Root ← A
• For each possible value, vi, of A,
• Add a new tree branch below Root, corresponding to the test A = vi
• Let Examples vi, be the subset of Examples that have value vi for A
• If Examples vi , is empty
• Then below this new branch add a leaf node with label = most common value of
Target_attribute in Examples
• Else below this new branch add the subtree
ID3(Examples vi, Targe_tattribute, Attributes – {A}))
• End
• Return Root
* The best attribute is the one with highest information gain
12
Which Attribute Is the Best Classifier?
• The central choice in the ID3 algorithm is selecting which attribute to test at each
node in the tree.
• A statistical property called information gain that measures how well a given
attribute separates the training examples according to their target classification.
• ID3 uses information gain measure to select among the candidate attributes at
each step while growing the tree.
13
ENTROPY MEASURES HOMOGENEITY OF EXAMPLES
• To define information gain, we begin by defining a measure called entropy.
Entropy measures the impurity of a collection of examples.
• Entropy is a measure of uncertainty or disorder in a system. In machine
learning, entropy tells us how pure or impure a dataset is.
• Given a collection S, containing positive and negative examples of some target
concept, the entropy of S relative to this Boolean classification is
Where,
p+ is the proportion of positive examples in S
p- is the proportion of negative examples in S.
14
Example: Entropy
• Suppose S is a collection of 14 examples of some boolean concept, including 9
positive and 5 negative examples. Then the entropy of S relative to this boolean
classification is
15
• The entropy is 0 if all members of S belong to the same class
• The entropy is 1 when the collection contains an equal number of positive and
negative examples
• If the collection contains unequal numbers of positive and negative examples, the
entropy is between 0 and 1
16
17
INFORMATION GAIN MEASURES THE EXPECTED
REDUCTION IN ENTROPY
• Information gain, is the expected reduction in entropy caused by partitioning the
examples according to this attribute.
• The information gain, Gain(S, A) of an attribute A, relative to a collection of
examples S, is defined as
18
An Illustrative Example
• To illustrate the operation of ID3, consider the learning task represented by the
training examples of below table.
• Here the target attribute PlayTennis, which can have values yes or no for
different days.
• Consider the first step through the algorithm, in which the topmost node of the
decision tree is created.
19
Day Outlook Temperature Humidity Wind PlayTennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
solved example of using the ID3 algorithm for a continuous attribute
using information gain with a threshold split.
Example Dataset (Play Tennis)
Example Temperature (°C) PlayTennis
1 40 No
2 35 No
3 30 Yes
4 20 Yes
5 25 Yes
6 15 No
36
Step1: Sort by Temperature
Example Temperature PlayTennis
6 15 No
4 20 Yes
5 25 Yes
3 30 Yes
2 35 No
1 40 No
37
38
39
40
41
42
43
44
Day Outlook Temperature Humidity Wind PlayTennis
D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63