JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 120

Decision Tree Classification�

Dr. Debasis Samanta

Associate Professor

Department of Computer Science & Engineering

2 of 120

The Learning Objectives…

Concept of Decision Tree

Use of Decision Tree to classify data

Basic algorithm to build Decision Tree

Some illustrations

Concept of Entropy

Basic concept of entropy in information theory
Mathematical formulation of entropy
Calculation of entropy of a training set

Decision Tree induction algorithms

ID3
CART
C4.5

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

3 of 120

Basic Concept

A Decision Tree is an important data structure known to solve many computational problems

Example 9.1: Binary Decision Tree

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

4 of 120

Basic Concept

In Example 9.1, we have considered a decision tree where values of any attribute if binary only. Decision tree is also possible where attributes are of continuous data type

Example 9.2: Decision Tree with numeric data

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

5 of 120

Some Characteristics

Decision tree may be n-ary, n ≥ 2.

There is a special node called root node.

All nodes drawn with circle (ellipse) are called internal nodes.

All nodes drawn with rectangle boxes are called terminal nodes or leaf nodes.

Edges of a node represent the outcome for a value of the node.

In a path, a node with same label is never repeated.

Decision tree is not unique, as different ordering of internal nodes can give different decision tree.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

6 of 120

Decision Tree and Classification Task

Decision tree helps us to classify data.

Internal nodes are some attribute

Edges are the values of attributes

External nodes are the outcome of classification

Such a classification is, in fact, made by posing questions starting from the root node to each terminal node.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

7 of 120

Decision Tree and Classification Task

Example 9.3 : Vertebrate Classification

What are the class label of Dragon and Shark?

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Name	Body Temperature	Skin Cover	Gives Birth	Aquatic Creature	Aerial Creature	Has Legs	Hibernates	Class
Human	Warm	hair	yes	no	no	yes	no	Mammal
Python	Cold	scales	no	no	no	no	yes	Reptile
Salmon	Cold	scales	no	yes	no	no	no	Fish
Whale	Warm	hair	yes	yes	no	no	no	Mammal
Frog	Cold	none	no	semi	no	yes	yes	Amphibian
Komodo	Cold	scales	no	no	no	yes	no	Reptile
Bat	Warm	hair	yes	no	yes	yes	yes	Mammal
Pigeon	Warm	feathers	no	no	yes	yes	no	Bird
Cat	Warm	fur	yes	no	no	yes	no	Mammal
Leopard	Cold	scales	yes	yes	no	no	no	Fish
Turtle	Cold	scales	no	semi	no	yes	no	Reptile
Penguin	Warm	feathers	no	semi	no	yes	no	Bird
Porcupine	Warm	quills	yes	no	no	yes	yes	Mammal
Eel	Cold	scales	no	yes	no	no	no	Fish
Salamander	Cold	none	no	semi	no	yes	yes	Amphibian

8 of 120

Decision Tree and Classification Task

Example 9.3 : Vertebrate Classification

Suppose, a new species is discovered as follows.

Decision Tree that can be inducted based on the data (in Example 9.3) is as follows.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Name	Body Temperature	Skin Cover	Gives Birth	Aquatic Creature	Aerial Creature	Has Legs	Hibernates	Class
Gila Monster	cold	scale	no	no	no	yes	yes	?

9 of 120

Decision Tree and Classification Task

Example 9.3 illustrates how we can solve a classification problem by asking a series of question about the attributes.

Each time we receive an answer, a follow-up question is asked until we reach a conclusion about the class-label of the test.

The series of questions and their answers can be organized in the form of a decision tree

As a hierarchical structure consisting of nodes and edges

Once a decision tree is built, it is applied to any test to classify it.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

10 of 120

Definition of Decision Tree

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Definition 9.1: Decision Tree

11 of 120

Building Decision Tree

In principle, there are exponentially many decision tree that can be constructed from a given database (also called training data).

Some of the tree may not be optimum

Some of them may give inaccurate result

Two approaches are known

Greedy strategy

A top-down recursive divide-and-conquer

Modification of greedy strategy

ID3
C4.5
CART, etc.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

12 of 120

Built Decision Tree Algorithm

Algorithm BuiltDT
Input: D : Training data set
Output: T : Decision tree

Steps

If all tuples in D belongs to the same class C_j

Add a leaf node labeled as C_j

Return // Termination condition

Select an attribute A_i (so that it is not selected twice in the same branch)

Partition D = { D₁, D₂, …, D_p} based on p different values of A_i in D

For each D_k ϵ D

Create a node and add an edge between D and D_k with label as the A_i’s attribute value in D_k

For each D_k ϵ D

BuildTD(D_k) // Recursive call

Stop

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

13 of 120

Node Splitting in BuildDT Algorithm

BuildDT algorithm must provides a method for expressing an attribute test condition and corresponding outcome for different attribute type

Case: Binary attribute

This is the simplest case of node splitting

The test condition for a binary attribute generates only two outcomes

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

14 of 120

Node Splitting in BuildDT Algorithm

Case: Nominal attribute

Since a nominal attribute can have many values, its test condition can be expressed in two ways:

A multi-way split
A binary split

Muti-way split: Outcome depends on the number of distinct values for the corresponding attribute

Binary splitting by grouping attribute values

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

15 of 120

Node Splitting in BuildDT Algorithm

Case: Ordinal attribute

It also can be expressed in two ways:

A multi-way split
A binary split

Muti-way split: It is same as in the case of nominal attribute

Binary splitting attribute values should be grouped maintaining the order property of the attribute values

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

16 of 120

Node Splitting in BuildDT Algorithm

Case: Numerical attribute

For numeric attribute (with discrete or continuous values), a test condition can be expressed as a comparison set

Binary outcome: A > v or A ≤ v

In this case, decision tree induction must consider all possible split positions

Range query : v_i ≤ A < v_i+1 for i = 1, 2, …, q (if q number of ranges are chosen)

Here, q should be decided a priori

For a numeric attribute, decision tree induction is a combinatorial optimization problem

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

17 of 120

Illustration : BuildDT Algorithm

Example 9.4: Illustration of BuildDT Algorithm

Consider a training data set as shown.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Attributes:

Gender = {Male(M), Female (F)} // Binary attribute

Height = {1.5, …, 2.5} // Continuous attribute

Class = {Short (S), Medium (M), Tall (T)}

Given a person, we are to test in which class s/he belongs

18 of 120

Illustration : BuildDT Algorithm

To built a decision tree, we can select an attribute in two different orderings: <Gender, Height> or <Height, Gender>

Further, for each ordering, we can choose different ways of splitting

Different instances are shown in the following.

Approach 1 : <Gender, Height>

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

19 of 120

Illustration : BuildDT Algorithm

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

20 of 120

Illustration : BuildDT Algorithm

Approach 2 : <Height, Gender>

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

21 of 120

Illustration : BuildDT Algorithm

Example 9.5: Illustration of BuildDT Algorithm

Consider an anonymous database as shown.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Is there any “clue” that enables to select the “best” attribute first?

Suppose, following are two attempts:

A1🡪A2🡪A3🡪A4 [Naïve]
A3🡪A2🡪A4🡪A1 [Random]

Draw the decision trees in the above-mentioned two cases.

Are the trees different to classify any test data?

If any other sample data is added into the database, is that likely to alter the decision tree already obtained?

22 of 120

Concept of Entropy

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

23 of 120

Concept of Entropy

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

More organized or Less organized or

ordered (less probable) disordered (more probable)

More ordered Less ordered

less entropy higher entropy

24 of 120

Concept of Entropy

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Universe!

What was its entropy value at its starting point?

25 of 120

An Open Challenge!

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Two sheets showing the tabulation of marks obtained in a course are shown.

Which tabulation of marks shows the “good” performance of the class?

How you can measure the same?

Roll No.	Assignment	Project	Mid-Sem	End-Sem
12BT3FP06	89	99	56	91
10IM30013	95	98	55	93
12CE31005	98	96	58	97
12EC35015	93	95	54	99
12GG2005	90	91	53	98
12MI33006	91	93	57	97
13AG36001	96	94	58	95
13EE10009	92	96	56	96
13MA20012	88	98	59	96
14CS30017	94	90	60	94
14ME10067	90	92	58	95
14MT10038	99	89	55	93

Roll No.	Assignment	Project	Mid-Sem	End-Sem
12BT3FP06	19	59	16	71
10IM30013	37	38	25	83
12CE31005	38	16	48	97
12EC35015	23	95	54	19
12GG2005	40	71	43	28
12MI33006	61	93	47	97
13AG36001	26	64	48	75
13EE10009	92	46	56	56
13MA20012	88	58	59	66
14CS30017	74	20	60	44
14ME10067	50	42	38	35
14MT10038	29	69	25	33

26 of 120

Entropy and its Meaning

Entropy is an important concept used in Physics in the context of heat and thereby uncertainty of the states of a matter.

At a later stage, with the growth of Information Technology, entropy becomes an important concept in Information Theory.

To deal with the classification job, entropy is an important concept, which is considered as

an information-theoretic measure of the “uncertainty” contained in a training data

due to the presence of more than one classes.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

27 of 120

Entropy in Information Theory

The entropy concept in information theory first time coined by Claude Shannon (1850).

The first time it was used to measure the “information content” in messages.

According to his concept of entropy, presently entropy is widely being used as a way of representing messages for efficient transmission by Telecommunication Systems.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

28 of 120

Measure of Information Content

People, in general, are information hungry!

Everybody wants to acquire information (from newspaper, library, nature, fellows, etc.)

Think how a crime detector do it to know about the crime from crime spot and criminal(s).

Kids annoyed their parents asking questions.

In fact, fundamental thing is that we gather information asking questions (and decision tree induction is no exception).

We may note that information gathering may be with certainty or uncertainty.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

29 of 120

Measure of Information Content

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

30 of 120

Definition of Entropy

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

The entropy of a set of m distinct values is the minimum number of yes/no questions needed to determine an unknown values from these m possibilities.

Definition 9.2: Entropy

31 of 120

Entropy Calculation

How can we calculate the minimum number of questions, that is, entropy?

There are two approaches:

Brute –force approach
Clever approach.

Example 9.7: City quiz

Suppose, There is a quiz relating to guess a city out of 8 cities, which are as follows:

Bangalore, Bhopal, Bhubaneshwar, Delhi, Hyderabad, Kolkata, Madras, Mumbai

The question is, “Which city is called city of joy”?

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

32 of 120

Approach 1: Brute-force search

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

33 of 120

Approach 2: Clever approach

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

34 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Lemma 9.1: Entropy calculation

Entropy Calculation

35 of 120

Entropy in Messages

We know that the most conventional way to code information is using binary bits, that is, using 0s and 1s.

The answer to a question that can only be answered yes/no (with equal probability) can be considered as containing one unit of information, that is, one bit.

In other words, the unit of information can also be looked at as the amount of information that can be coded using only 0s and 1s.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

36 of 120

Entropy in Messages

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

37 of 120

Entropy in Messages

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

The entropy of a set of m distinct values is the number of bits needed to encode all the values in the most efficient way.

Definition 9.3: Entropy

38 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

39 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

40 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

k			No. Q
6	117649	16.84413	17	2.8333
21		58.95445	59	2.8095
1000		2807.3549	2808	2.8080
…..	…..	…..	…..	…..

41 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Lemma 9.4: Entropy Calculation

42 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

43 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

44 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

It may be interesting to note that even with variable length encoding, there are several ways of encoding. Few of them are given below.

The calculation of entropy in the observed cases can be obtained as:

Anyway, key to finding the most efficient way of encoding is to assign a smallest number of bits to the object with highest frequency and so on.

The above observation is also significant in the sense that it provides a systematic way of finding a sequence of well-chosen question in order to identify an object at a faster rate.

1) 1.75	2) 2	3) 3.875

45 of 120

Information Content

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Lemma 9.3: Information content

Based on the previous discussion, we can easily prove the following lemma.

46 of 120

Entropy Calculation

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Theorem 9.4: Entropy calculation

47 of 120

Entropy of a Training Set

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

48 of 120

Entropy of a Training Set

Example 9.10: OPTH dataset

Consider the OTPH data shown in the following table with total 24 instances in it.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Age	Eye sight	Astigmatic	Use Type	Class
1 1 1 1 1 1	1 1 1 1 2 2	1 1 2 2 1 1	1 2 1 2 1 2	3 2 3 1 3 2
1 1 2 2 2 2	2 2 1 1 1 1	2 2 1 1 2 2	1 2 1 2 1 2	3 1 3 2 3 1
2 2 2 2 3 3	2 2 2 2 1 1	1 1 2 2 1 1	1 2 1 2 1 2	3 2 3 3 3 3
3 3 3 3 3 3	1 1 2 2 2 2	2 2 1 1 2 2	1 2 1 2 1 2	3 1 3 2 3 3

A coded forms for all values of attributes are used to avoid the cluttering in the table.

49 of 120

Entropy of a training set

Specification of the attributes are as follows.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Age	Eye Sight	Astigmatic	Use Type
1: Young	1: Myopia	1: No	1: Frequent
2: Middle-aged	2: Hypermetropia	2: Yes	2: Less
3: Old

50 of 120

Note:

The entropy of a training set implies the number of yes/no questions, on the average, needed to determine an unknown test to be classified.

It is very crucial to decide the series of questions about the value of a set of attribute, which collectively determine the classification. Sometimes it may take one question, sometimes many more.

Decision tree induction helps us to ask such a series of questions. In other words, we can utilize entropy concept to build a better decision tree.

How entropy can be used to build a decision tree is our next topic of discussion.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

51 of 120

Decision Tree Induction Techniques

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

Choosing the best attribute to be splitted, and

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

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

52 of 120

Algorithm ID3

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

53 of 120

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.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

54 of 120

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.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

55 of 120

Defining Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

56 of 120

Defining Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

57 of 120

Defining Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Definition 9.4: Weighted Entropy

58 of 120

Defining Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Definition 9.5: Information Gain

59 of 120

Information Gain Calculation

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

60 of 120

Information Gain Calculation

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

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

61 of 120

Calculating Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

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

62 of 120

Calculating Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

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

63 of 120

Information Gains for Different Attributes

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

64 of 120

Decision Tree Induction : ID3 Way

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

65 of 120

Decision Tree Induction : ID3 Way

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Age

Eye-sight

Astigmatic

Use Type

Age	Eye	Ast	Use	Class
1	1	1	1	3
1	1	2	1	3
1	2	1	1	3
1	2	2	1	3
2	1	1	1	3
2	2	1	1	3
2	2	2	1	3
3	1	1	1	3
3	1	2	1	3
3	2	1	1	3
3	2	2	1	3

Age	Eye	Ast	Use	Class
1	1	1	2	2
1	1	2	2	1
1	2	1	2	2
1	2	2	2	1
2	1	1	2	2
2	1	2	2	1
2	2	1	2	2
3	1	1	2	3
3	1	2	2	3
3	2	1	2	2
3	2	2	2	3

✔

Age

Eye-sight

Astigmatic

Age

Eye-sight

Astigmatic

66 of 120

Frequency Table : Calculating α

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

67 of 120

Frequency Table : Calculating α

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Class

68 of 120

Calculation of α using Frequency Table

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Example 9.12 : OTPH Dataset

With reference to OPTH dataset, and for the attribute Age, the frequency table would look like

Column Sums

	Age=1	Age=2	Age=3	Row Sum
Class 1	2	1	1	4
Class 2	2	2	1	5
Class 3	4	5	6	15
Column Sum	8	8	8	24

N=24

69 of 120

Calculation of α using Frequency Table

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

70 of 120

Proof of Equivalence

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

71 of 120

Proof of Equivalence

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

72 of 120

Proof of Equivalence

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

73 of 120

Limiting Values of Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

74 of 120

Limiting Values of Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Example 9.14: Limiting values of Information gain

Consider a training set shown below.

Data set Table A X Table X

X	Y	Class
1	1	A
1	2	B
2	1	A
2	2	B
3	2	A
3	1	B
4	2	A
4	1	B

	1	2	3	4
A	1	1	1	1
B	1	1	1	1
	2	2	2	2

	1	2
A	2	2
B	2	2
	4	4

Frequency table of X

Frequency table of Y

Table Y

75 of 120

Limiting values of Information Gain

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

76 of 120

Splitting of Continuous Attribute Values

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

77 of 120

Splitting of Continuous attribute values

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

78 of 120

Algorithm CART

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

79 of 120

CART Algorithm

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

80 of 120

Gini Index of Diversity

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Definition 9.6: Gini Index

81 of 120

Gini Index of Diversity

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

82 of 120

Gini Index of Diversity

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Definition 9.7: Gini Index of Diversity

83 of 120

Gini Index of Diversity and CART

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

84 of 120

n-ary Attribute Values to Binary Splitting

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

85 of 120

n-ary Attribute Values to Binary Splitting

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Yes No

86 of 120

n-ary Attribute Values to Binary Splitting

Case2: Continuous valued attributes

For a continuous-valued attribute, each possible split point must be taken into account.

The strategy is similar to that followed in ID3 to calculate information gain for the continuous –valued attributes.

According to that strategy, the mid-point between a_i and a_i+1 , let it be v_i, then

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Yes No

87 of 120

n-ary Attribute Values to Binary Splitting

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

88 of 120

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.

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Tuple#	Age	Salary	Job	Performance	Select
1	Y	H	P	A	N
2	Y	H	P	E	N
3	M	H	P	A	Y
4	O	M	P	A	Y
5	O	L	G	A	Y
6	O	L	G	E	N
7	M	L	G	E	Y
8	Y	M	P	A	N
9	Y	L	G	A	Y
10	O	M	G	A	Y
11	Y	M	G	E	Y
12	M	M	P	E	Y
13	M	H	G	A	Y
14	O	M	P	E	N

Age

Y : young

M : middle-aged

O : old

Salary

L : low

M : medium

H : high

Job

G : government

P : private

Performance

A : Average

E : Excellent

Class : Select

Y : yes

N : no

89 of 120

CART Algorithm : Illustration

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

90 of 120

CART Algorithm : Illustration

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

{O} {Y,M}

Yes

91 of 120

CART Algorithm : Illustration

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

{H} {L,M}

Yes

92 of 120

CART Algorithm : Illustration

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

93 of 120

CART Algorithm : Illustration

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

94 of 120

Calculating γ using Frequency Table

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

95 of 120

Calculating γ using Frequency Table

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

96 of 120

Illustration: Calculating γ using Frequency Table

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

	1	2	3
Class 1	2	1	1
Class 2	2	2	1
Class 3	4	5	6
Column sum	8	8	8

97 of 120

Illustration: Calculating γ using Frequency Table

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

98 of 120

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Illustration: Calculating γ using Frequency Table

99 of 120

Decision Trees with ID3 and CART Algorithms

Example 9.17 : Comparing Decision Trees of EMP Data set

Compare two decision trees obtained using ID3 and CART for the EMP dataset. The decision tree according to ID3 is given for your ready reference (subject to the verification)

Decision Tree using ID3

Decision Tree using CART

Data Analytics (CS61061)

DSamanta@IIT Kharagpur

Age

Job

Performance

100 of 120

Algorithm C4.5

Data Analytics (CS61061)

100

DSamanta@IIT Kharagpur

101 of 120

Algorithm C 4.5 : Introduction

Data Analytics (CS61061)

101

DSamanta@IIT Kharagpur

102 of 120

Algorithm C4.5 : Introduction

Data Analytics (CS61061)

102

DSamanta@IIT Kharagpur

103 of 120

Algorithm: C 4.5 : Introduction

Although, the previous situation is an extreme case, intuitively, we can infer that ID3 favours splitting attributes having a large number of values

compared to other attributes, which have a less variations in their values.

Such a partition appears to be useless for classification.

This type of problem is called overfitting problem.

Note:

Decision Tree Induction Algorithm ID3 may suffer from overfitting problem.

Data Analytics (CS61061)

103

DSamanta@IIT Kharagpur

104 of 120

Algorithm: C 4.5 : Introduction

Data Analytics (CS61061)

104

DSamanta@IIT Kharagpur

105 of 120

Algorithm: C 4.5 : Gain Ratio

Data Analytics (CS61061)

105

DSamanta@IIT Kharagpur

Definition 9.8: Gain Ratio

106 of 120

Data Analytics (CS61061)

106

DSamanta@IIT Kharagpur

107 of 120

Data Analytics (CS61061)

107

DSamanta@IIT Kharagpur


Frequency	32	0	0	0


Frequency	16	16	0	0

108 of 120

Distribution 3

Distribution 4

Distribution 5: Uniform distribution of attribute values

Data Analytics (CS61061)

108

DSamanta@IIT Kharagpur


Frequency	16	8	8	0


Frequency	16	8	4	4


Frequency	8	8	8	8

109 of 120

Data Analytics (CS61061)

109

DSamanta@IIT Kharagpur

110 of 120

Information gain signifies how much information will be gained on partitioning the values of attribute A

Higher information gain means splitting of A is more desirable.

On the other hand, split information forms the denominator in the gain ratio formula.

This implies that higher the value of split information is, lower the gain ratio.
In turns, it decreases the information gain.

Further, information gain is large when there are many distinct attribute values.

When many distinct values, split information is also a large value.
This way split information reduces the value of gain ratio, thus resulting a balanced value for information gain.

Like information gain (in ID3), the attribute with the maximum gain ratio is selected as the splitting attribute in C4.5.

Data Analytics (CS61061)

110

DSamanta@IIT Kharagpur

111 of 120

Data Analytics (CS61061)

111

DSamanta@IIT Kharagpur

112 of 120

Summary of Decision Tree Induction Algorithms

We have learned the building of a decision tree given a training data.

The decision tree is then used to classify a test data.

For a given training data D, the important task is to build the decision tree so that:

All test data can be classified accurately

The tree is balanced and with as minimum depth as possible, thus the classification can be done at a faster rate.

In order to build a decision tree, several algorithms have been proposed. These algorithms differ from the chosen splitting criteria, so that they satisfy the above mentioned objectives as well as the decision tree can be induced with minimum time complexity. We have studied three decision tree induction algorithms namely ID3, CART and C4.5. A summary of these three algorithms is presented in the following table.

Data Analytics (CS61061)

112

DSamanta@IIT Kharagpur

113 of 120

Table 11.6

Data Analytics (CS61061)

113

DSamanta@IIT Kharagpur

Algorithm	Splitting Criteria	Remark
ID3

114 of 120

Data Analytics (CS61061)

114

DSamanta@IIT Kharagpur

Algorithm	Splitting Criteria	Remark
CART

115 of 120

Data Analytics (CS61061)

115

DSamanta@IIT Kharagpur

Algorithm	Splitting Criteria	Remark
C4.5

In addition to this, we also highlight few important characteristics of decision tree induction algorithms in the following.

116 of 120

Notes on Decision Tree Induction algorithms

Optimal Decision Tree: Finding an optimal decision tree is an NP-complete problem. Hence, decision tree induction algorithms employ a heuristic based approach to search for the best in a large search space. Majority of the algorithms follow a greedy, top-down recursive divide-and-conquer strategy to build decision trees.

Missing data and noise: Decision tree induction algorithms are quite robust to the data set with missing values and presence of noise. However, proper data pre-processing can be followed to nullify these discrepancies.

Redundant Attributes: The presence of redundant attributes does not adversely affect the accuracy of decision trees. It is observed that if an attribute is chosen for splitting, then another attribute which is redundant is unlikely to chosen for splitting.

Computational complexity: Decision tree induction algorithms are computationally inexpensive, in particular, when the sizes of training sets are large, Moreover, once a decision tree is known, classifying a test record is extremely fast, with a worst-case time complexity of O(d), where d is the maximum depth of the tree.

Data Analytics (CS61061)

116

DSamanta@IIT Kharagpur

117 of 120

Data Analytics (CS61061)

117

DSamanta@IIT Kharagpur

Data Fragmentation Problem: Since the decision tree induction algorithms employ a top-down, recursive partitioning approach, the number of tuples becomes smaller as we traverse down the tree. At a time, the number of tuples may be too small to make a decision about the class representation, such a problem is known as the data fragmentation. To deal with this problem, further splitting can be stopped when the number of records falls below a certain threshold.

Tree Pruning: A sub-tree can replicate two or more times in a decision tree (see figure below). This makes a decision tree unambiguous to classify a test record. To avoid such a sub-tree replication problem, all sub-trees except one can be pruned from the tree.

Notes on Decision Tree Induction algorithms

118 of 120

Data Analytics (CS61061)

118

DSamanta@IIT Kharagpur

Notes on Decision Tree Induction algorithms

119 of 120

Reference

Data Analytics (CS61061)

119

DSamanta@IIT Kharagpur

The detail material related to this lecture can be found in

Data Mining: Concepts and Techniques, (3^rd Edn.), Jiawei Han, Micheline Kamber, Morgan Kaufmann, 2015.

Introduction to Data Mining, Pang-Ning Tan, Michael Steinbach, and Vipin Kumar, Addison-Wesley, 2014

120 of 120

Any question?

Data Analytics (CS61061)

120

DSamanta@IIT Kharagpur

You may post your question(s) at the “Discussion Forum” maintained in the course Web page!