�Decision Trees

Dr. Dinesh Kumar Vishwakarma

Professor,

Department of Information Technology,

Delhi Technological University, Delhi-110042

dinesh@dtu.ac.in

http://www.dtu.ac.in/Web/Departments/InformationTechnology/faculty/dkvishwakarma.php

Introduction

• A decision tree is a support tool with a tree-like structure that models probable outcomes, cost of resources, utilities, and possible consequences.
• It provides a way to present algorithms with conditional control statements.
• It include branches that represent decision-making steps that can lead to a favorable result.

• The flowchart structure includes internal nodes that represent tests or attributes at each stage.
• Every branch stands for an outcome for the attributes, while the path from the leaf to the root represents rules for classification.

Applications

• Assessing prospective growth opportunities
• Using demographic data to find prospective clients
• Marketing
• Retention of Customers
• Diagnosis of Diseases and Ailments
• Detection of Frauds

​

Advantages

• Easy to read and interpret
• The o/p are easy to read and interpret without requiring statistical knowledge
• Easy to prepare
• take less effort for data preparation
• Less data cleaning required
• There is less data cleaning required once the variables have been created. In cases of missing values and outliers have less significance on the decision tree’s data.

Decision Tree: DT

• Graphical representation of all possible solutions.
• Decisions are based on some conditions.
• Decision made can be easily explained.

A decision tree is a flowchart-like structure in which each internal node represents a "test" on an attribute (e.g. whether a coin flip comes up heads or tails), each branch represents the outcome of the test, and each leaf node represents a class label (decision taken after computing all attributes)

E.g.

Call Centre

Root node

Leaf Node

Decision Node

Decision Tree: DT

Refund

MarSt

TaxInc

YES

NO

NO

NO

Yes

No

Married

Single, Divorced

< 80K

> 80K

Splitting Attributes

Training Data

Model: Decision Tree

Another Example of Decision Tree

categorical

categorical

continuous

class

MarSt

Refund

TaxInc

YES

NO

NO

Yes

No

Married

Single, Divorced

< 80K

> 80K

There could be more than one tree that fits the same data!

Decision Tree Classification Task

Decision Tree

Apply Model to Test Data

Test Data

Start from the root of tree.

Apply Model to Test Data

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

NO

NO

Yes

No

Married

Single, Divorced

< 80K

> 80K

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

NO

NO

Yes

No

Married

Single, Divorced

< 80K

> 80K

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

NO

NO

Yes

No

Married

Single, Divorced

< 80K

> 80K

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

NO

NO

Yes

No

Married

Single, Divorced

< 80K

> 80K

Test Data

Assign Cheat to “No”

Decision Tree Classification Task

Decision Tree

Decision Tree Induction

• Many Algorithms:
• Hunt’s Algorithm (one of the earliest)
• CART
• ID3, C4.5

Hunt’s Algorithm

D_t

?

Hunt’s Algorithm

Don’t

Cheat

Tree Induction

• Greedy strategy.
• Split the records based on an attribute test that optimizes certain criterion.
• Issues
• Determine how to split the records
• How to specify the attribute test condition?
• How to determine the best split?
• Determine when to stop splitting

​

Tree Induction

• Greedy strategy.
• Split the records based on an attribute test that optimizes certain criterion.
• Issues
• Determine how to split the records
• How to specify the attribute test condition?
• How to determine the best split?
• Determine when to stop splitting

​

How to Specify Test Condition?

• Depends on attribute types
• Binary
• Nominal
• Ordinal
• Continuous
• Depends on number of ways to split
• 2-way split
• Multi-way split

Splitting Based on Binary Attributes

• 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

Splitting Based on Nominal Attributes

• Multi-way split: Use as many partitions as distinct values.

​

​

​

• Binary split: Divides values into two subsets. � Need to find optimal partitioning.

OR

Splitting Based on Ordinal Attributes

• Multi-way split: Use as many partitions as distinct values.
• Small (S), Medium (M),
• Large (L), Extra Large (XL)

​

​

• Binary split: Divides values into two subsets. � Need to find optimal partitioning.

​

​

• What about this split?

OR

Splitting Based on Continuous Attributes

• Different ways of handling
• Discretization to form an ordinal categorical attribute
• Static – discretize once at the beginning
• Dynamic – ranges can be found by equal interval bucketing, equal frequency bucketing� (percentiles), or clustering.

​

• Binary Decision: (A < v) or (A ≥ v)
• consider all possible splits and finds the best cut
• can be more compute intensive

Splitting Based on Continuous Attributes…

Tree Induction

• Greedy strategy.
• Split the records based on an attribute test that optimizes certain criterion.

​

• Issues
• Determine how to split the records
• How to specify the attribute test condition?
• How to determine the best split?
• Determine when to stop splitting

​

How to determine the Best Split

Before Splitting: 10 records of class 0,� 10 records of class 1

Which test condition is the best?

How to determine the Best Split

• Greedy approach:
• Nodes with homogeneous class distribution are preferred.
• Need a measure of node impurity:

​

Non-homogeneous,

High degree of impurity

Homogeneous,

Low degree of impurity

Measures of Node Impurity

• There are three popular way to measure impurity is:
• Information Gain
• Gain Ratio
• Gini Index

Concept of Entropy

More organized or Less organized or

ordered (less probable) disordered (more probable)

More ordered Less ordered

less entropy higher entropy

An Open Challenge!

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?

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.

​

​

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.

Measure of Information Content

Entropy Calculations

Entropy Calculations…

Entropy of a Training Set

Consider a dataset of OTPH as shown in the following table with total 24 instances in it.

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

Entropy of a training set…

Specification of the attributes are as follows.

​

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
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

Algorithm ID3

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.

​

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.

Defining Information Gain

Defining Information Gain…

Defining Information Gain…

Compute Information Gain

Missing value

Example

Example…

Example…

Information Gains for Different Attributes

Decision Tree Induction : ID3 Way

Decision Tree Induction : ID3 Way

Age

Eye-sight

Astigmatic

Use Type

✔

Age

Eye-sight

Astigmatic

Age

Eye-sight

Astigmatic

Example 3

Example 3…

Example 3…

• A partially learned decision tree
• There are three possibility to select further attribute Temperature, Humidity, and Wind.
• Intuitively, “Humidity” is the best to choose

Example 3: Information Gain

Example 3: Information Gain…

Outlook has maximum gain

Root Node

Example 3: Information Gain…

• Same strategy is applied recursively to each subset of training instances.

Example 3: Information Gain…

• Further branching at the node reached when outlook is sunny.
• The information gain at daughter node are:
• Temperature: Hot-02, Mild-02, Cool-01

Example 3: Information Gain…

• Similarly, for Humidity and Wind
• Humidity: High-03 (N-3, Y-0), Normal-02(N-0, Y-2)

​

​

​

• Wind: Weak-03(Y-1, N-2), Strong-02 (Y-1, N-1)

​

We choose “Humidity”, since it has highest gain. No further splitting, reached as leaf node

Facts of Information Gain

C4.5�Gain Ratio

Gain Ratio

Dataset

Example :Gain Ratio

Example :Gain Ratio…

• Normalize the information gain by dividing by the split info value to get gain ratio.

Example :Gain Ratio…

• Similarly, it can be calculated for others attributes such as:

​

​

​

​

• Outlook still comes out on top but Humidity is much closers contender because it split the data into two subsets instead three.

CART�GINI INDEX

CLASSIFICATION AND REGRESSION TREE

GINI Index

• The Gini Index facilitates the bigger distributions so easy to implement whereas the Information Gain favors lesser distributions having small count with multiple specific values.
• The method of the Gini Index is used by CART algorithms, in contrast to it, Information Gain is used in ID3, C4.5 algorithms.
• Gini index operates on the categorical target variables in terms of “success” or “failure” and performs only binary split, in opposite to that Information Gain computes the difference between entropy before and after the split and indicates the impurity in classes of elements.

​

GINI Index…

GINI Index…

GINI Index…

Measure of Impurity: GINI

• Gini Index for a given node t :
• Maximum (1 - 1/n_c) when records are equally distributed among all classes, implying least interesting information.
• Minimum (0.0) when all records belong to one class, implying most interesting information.

Examples for computing GINI

P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

Gini = 1 – P(C1)² – P(C2)² = 1 – 0 – 1 = 0

P(C1) = 1/6 P(C2) = 5/6

Gini = 1 – (1/6)² – (5/6)² = 0.278

P(C1) = 2/6 P(C2) = 4/6

Gini = 1 – (2/6)² – (4/6)² = 0.444

Splitting Based on GINI

• Used in CART: Classification And Regression Trees
• When a node p is split into k partitions (children), the quality of split is computed as,

​

​

​

where, n_i = number of records at child i,

n = number of records at node p.

Binary Attributes: Computing GINI Index

• Splits into two partitions
• Effect of Weighing partitions:
• Larger and Purer Partitions are sought for.

B?

Yes

No

Node N1

Node N2

Gini(N1) �= 1 – (5/6)² – (2/6)² �= 0.194

Gini(N2) �= 1 – (1/6)² – (4/6)² �= 0.528

Gini(Children) �= 7/12 * 0.194 + 5/12 * 0.528�= 0.333

Categorical Attributes: Computing Gini Index

• For each distinct value, gather counts for each class in the dataset
• Use the count matrix to make decisions

Multi-way split

Two-way split

(find best partition of values)

Example

Continuous Attributes: Computing Gini Index

• Use Binary Decisions based on one value
• Several Choices for the splitting value
• Number of possible splitting values �= Number of distinct values
• Each splitting value has a count matrix associated with it
• Class counts in each of the partitions, A < v and A ≥ v
• Simple method to choose best v
• For each v, scan the database to gather count matrix and compute its Gini index
• Computationally Inefficient! Repetition of work.

Continuous Attributes: Computing Gini Index...

• For efficient computation: for each attribute,
• Sort the attribute on values
• Linearly scan these values, each time updating the count matrix and computing gini index
• Choose the split position that has the least gini index

Splitting Criteria based on Classification Error

• Classification error at a node t :

​

​

​

• Measures misclassification error made by a node.
• Maximum (1 - 1/n_c) when records are equally distributed among all classes, implying least interesting information
• Minimum (0.0) when all records belong to one class, implying most interesting information

Examples for Computing Error

P(C1) = 0/6 = 0 P(C2) = 6/6 = 1

Error = 1 – max (0, 1) = 1 – 1 = 0

P(C1) = 1/6 P(C2) = 5/6

Error = 1 – max (1/6, 5/6) = 1 – 5/6 = 1/6

P(C1) = 2/6 P(C2) = 4/6

Error = 1 – max (2/6, 4/6) = 1 – 4/6 = 1/3

Misclassification Error vs Gini

A?

Yes

No

Node N1

Node N2

Gini(N1) �= 1 – (3/3)² – (0/3)² �= 0

Gini(N2) �= 1 – (4/7)² – (3/7)² �= 0.489

Gini(Children) �= 3/10 * 0 �+ 7/10 * 0.489�= 0.342

Example: GINI Index

Example: GINI Index…

• First attribute is “Outlook”

Gini(Outlook=Sunny) = 1 – (2/5)² – (3/5)² = 1 – 0.16 – 0.36 = 0.48

Gini(Outlook=Overcast) = 1 – (4/4)² – (0/4)² = 0

Gini(Outlook=Rain) = 1 – (3/5)² – (2/5)² = 1 – 0.36 – 0.16 = 0.48

Then, we will calculate weighted sum of Gini indexes for outlook feature.

Gini(Outlook) = (5/14) x 0.48 + (4/14) x 0 + (5/14) x 0.48 = 0.171 + 0 + 0.171 = 0.342

Example: GINI Index…

• Second attribute is “Temperature”

Gini(Temp=Hot) = 1 – (2/4)² – (2/4)² = 0.5

Gini(Temp=Cool) = 1 – (3/4)² – (1/4)² = 1 – 0.5625 – 0.0625 = 0.375

Gini(Temp=Mild) = 1 – (4/6)² – (2/6)² = 1 – 0.444 – 0.111 = 0.445

​

We’ll calculate weighted sum of gini index for temperature feature

Gini(Temp) = (4/14) x 0.5 + (4/14) x 0.375 + (6/14) x 0.445 = 0.142 + 0.107 + 0.190 = 0.439

Example: GINI Index…

• Third attribute is “Humidity”

Gini(Humidity=High) = 1 – (3/7)² – (4/7)² = 1 – 0.183 – 0.326 = 0.489

Gini(Humidity=Normal) = 1 – (6/7)² – (1/7)² = 1 – 0.734 – 0.02 = 0.244

​

Weighted sum for humidity feature will be calculated next

Gini(Humidity) = (7/14) x 0.489 + (7/14) x 0.244 = 0.367

Example: GINI Index…

• Fourth attribute is “Wind”

Gini(Wind=Weak) = 1 – (6/8)² – (2/8)² = 1 – 0.5625 – 0.062 = 0.375

Gini(Wind=Strong) = 1 – (3/6)² – (3/6)² = 1 – 0.25 – 0.25 = 0.5

​

Gini(Wind) = (8/14) x 0.375 + (6/14) x 0.5 = 0.428

Example: GINI Index…

• Gini Index of all attributes are as:

Decision Tree at First Split

In this tree, overcast has only yes. Hence, it reaches at leaf node

Decision Tree at First Split

In this tree, overcast has only yes. Hence, it reaches at leaf node

DT: GINI Index for sub dataset

• Same procedure is applied for the sub datasets.
• The sub dataset for “sunny” outlook. We need to find the GINI index scores for temperature, humidity and wind features, respectively.

DT: GINI Index for sub dataset

• Gini of temperature for “sunny” outlook.

​

Gini(Outlook=Sunny and Temp.=Hot) = 1 – (0/2)² – (2/2)² = 0

Gini(Outlook=Sunny and Temp.=Cool) = 1 – (1/1)² – (0/1)² = 0

Gini(Outlook=Sunny and Temp.=Mild) = 1 – (1/2)² – (1/2)² = 1 – 0.25 – 0.25 = 0.5

​

Gini(Outlook=Sunny and Temp.) = (2/5)x0 + (1/5)x0 + (2/5)x0.5 = 0.2

DT: GINI Index for sub dataset

• Gini of humidity for sunny outlook.

​

Gini(Outlook=Sunny and Humidity=High) = 1 – (0/3)² – (3/3)² = 0

Gini(Outlook=Sunny and Humidity=Normal) = 1 – (2/2)² – (0/2)² = 0

​

Gini(Outlook=Sunny and Humidity) = (3/5)x0 + (2/5)x0 = 0

DT: GINI Index for sub dataset

• Gini of wind for sunny outlook.

​

Gini(Outlook=Sunny and Wind=Weak) = 1 – (1/3)² – (2/3)² = 0.266

Gini(Outlook=Sunny and Wind=Strong) = 1- (1/2)² – (1/2)² = 0.2

​

Gini(Outlook=Sunny and Wind) = (3/5)x0.266 + (2/5)x0.2 = 0.466

DT: GINI Index for sub dataset

• Decision for sunny outlook.

​

We’ll put humidity check at the extension of sunny outlook.

DT: Second Split

As seen, decision is always no for high humidity and sunny outlook. On the other hand, decision will always be yes for normal humidity and sunny outlook. This branch is over.

Decision Tree: Second Split

DT: Rain_Outlook

• Rain outlook

​

We’ll calculate Gini index scores for temperature, humidity and wind features when outlook is rain.

DT: Rain_Outlook…

• Gini of temperature for rain outlook

Gini(Outlook=Rain and Temp.=Cool) = 1 – (1/2)² – (1/2)² = 0.5

Gini(Outlook=Rain and Temp.=Mild) = 1 – (2/3)² – (1/3)² = 0.444

​

Gini(Outlook=Rain and Temp.) = (2/5)x0.5 + (3/5)x0.444 = 0.466

DT: Rain_Outlook…

• Gini of humidity for rain outlook

Gini(Outlook=Rain and Humidity=High) = 1 – (1/2)² – (1/2)² = 0.5

Gini(Outlook=Rain and Humidity=Normal) = 1 – (2/3)² – (1/3)² = 0.444

​

Gini(Outlook=Rain and Humidity) = (2/5)x0.5 + (3/5)x0.444 = 0.466

DT: Rain_Outlook…

• Gini of wind for rain outlook

Gini(Outlook=Rain and Wind=Weak) = 1 – (3/3)² – (0/3)² = 0

Gini(Outlook=Rain and Wind=Strong) = 1 – (0/2)² – (2/2)² = 0

​

Gini(Outlook=Rain and Wind) = (3/5)x0 + (2/5)x0 = 0

DT: Rain_Outlook…

• Decision for rain outlook
• The winner is wind feature for rain outlook because it has the minimum Gini index score in features.

​

​

DT: at Third Split

• Put the wind feature for rain outlook branch and monitor the new sub data sets.

​

​

As seen, decision is always yes when wind is weak. On the other hand, decision is always no if wind is strong. This means that this branch is over.

Decision Tree: Final

Stopping Criteria for Tree Induction

• Stop expanding a node when all the records belong to the same class
• Stop expanding a node when all the records have similar attribute values.

Decision Tree Based Classification

• Advantages:
• Inexpensive to construct
• Extremely fast at classifying unknown records
• Easy to interpret for small-sized trees
• Accuracy is comparable to other classification techniques for many simple data sets

​

Practical Issues of Classification

• Underfitting and Overfitting

​

• Missing Values

​

• Costs of Classification

Underfitting and Overfitting (Example)

500 circular and 500 triangular data points.

​

Circular points:

0.5 ≤ sqrt(x₁²+x₂²) ≤ 1

​

Triangular points:

sqrt(x₁²+x₂²) > 0.5 or

sqrt(x₁²+x₂²) < 1

Underfitting and Overfitting

Underfitting: when model is too simple, both training and test errors are large

Overfitting due to Noise

Decision boundary is distorted by noise point

Overfitting due to Insufficient Examples

Lack of data points in the lower half of the diagram makes it difficult to predict correctly the class labels of that region

- Insufficient number of training records in the region causes the decision tree to predict the test examples using other training records that are irrelevant to the classification task

Notes on Overfitting

• Overfitting results in decision trees that are more complex than necessary.

​

• Training error no longer provides a good estimate of how well the tree will perform on previously unseen records

​

• Need new ways for estimating errors

Occam’s Razor

• Given two models of similar generalization errors, one should prefer the simpler model over the more complex model.

​

• For complex models, there is a greater chance that it was fitted accidentally by errors in data.

​

• Therefore, one should include model complexity when evaluating a model.

How to Address Overfitting

• Pre-Pruning (Early Stopping Rule)
• Stop the algorithm before it becomes a fully-grown tree
• Typical stopping conditions for a node:
• Stop if all instances belong to the same class
• Stop if all the attribute values are the same
• More restrictive conditions:
• Stop if number of instances is less than some user-specified threshold
• Stop if class distribution of instances are independent of the available features (e.g., using χ ² test)
• Stop if expanding the current node does not improve impurity� measures (e.g., Gini or information gain).

How to Address Overfitting…

• Post-pruning
• Grow decision tree to its entirety
• Trim the nodes of the decision tree in a bottom-up fashion
• If generalization error improves after trimming, replace sub-tree by a leaf node.
• Class label of leaf node is determined from majority class of instances in the sub-tree
• Can use MDL for post-pruning