Decision Tree Classification Algorithm

o Decision Tree is a Supervised learning technique that can be used for both
classification and Regression problems, but mostly it is preferred for solving
Classification problems. It is a tree-structured classifier, where internal nodes
represent the features of a dataset, branches represent the decision
rules and each leaf node represents the outcome.
o In a Decision tree, there are two nodes, which are the Decision Node and Leaf
Node. Decision nodes are used to make any decision and have multiple
branches, whereas Leaf nodes are the output of those decisions and do not
contain any further branches.
o The decisions or the test are performed on the basis of features of the given
dataset.
o It is a graphical representation for getting all the possible solutions to a
problem/decision based on given conditions.
o It is called a decision tree because, similar to a tree, it starts with the root node,
which expands on further branches and constructs a tree-like structure.
o In order to build a tree, we use the CART algorithm, which stands
for Classification and Regression Tree algorithm.
o A decision tree simply asks a question, and based on the answer (Yes/No), it
further split the tree into subtrees.
o Below diagram explains the general structure of a decision tree:

Note: A decision tree can contain categorical data (YES/NO) as well as numeric data.
Why use Decision Trees?
There are various algorithms in Machine learning, so choosing the best algorithm for the
given dataset and problem is the main point to remember while creating a machine
learning model. Below are the two reasons for using the Decision tree:

o Decision Trees usually mimic human thinking ability while making a decision, so it
is easy to understand.
o The logic behind the decision tree can be easily understood because it shows a
tree-like structure.

Decision Tree Terminologies

 Root Node: Root node is from where the decision tree starts. It represents the entire dataset,
which further gets divided into two or more homogeneous sets.
 Leaf Node: Leaf nodes are the final output node, and the tree cannot be segregated further
after getting a leaf node.
 Splitting: Splitting is the process of dividing the decision node/root node into sub-nodes
according to the given conditions.
 Branch/Sub Tree: A tree formed by splitting the tree.
 Pruning: Pruning is the process of removing the unwanted branches from the tree.
 Parent/Child node: The root node of the tree is called the parent node, and other nodes are
called the child nodes.

How does the Decision Tree algorithm Work?

In a decision tree, for predicting the class of the given dataset, the algorithm starts from
the root node of the tree. This algorithm compares the values of root attribute with the
record (real dataset) attribute and, based on the comparison, follows the branch and
jumps to the next node.

For the next node, the algorithm again compares the attribute value with the other sub-
nodes and move further. It continues the process until it reaches the leaf node of the
tree. The complete process can be better understood using the below algorithm:

o Step-1: Begin the tree with the root node, says S, which contains the complete
dataset.
o Step-2: Find the best attribute in the dataset using Attribute Selection Measure
(ASM).
o Step-3: Divide the S into subsets that contains possible values for the best
attributes.
o Step-4: Generate the decision tree node, which contains the best attribute.
o Step-5: Recursively make new decision trees using the subsets of the dataset
created in step -3. Continue this process until a stage is reached where you
cannot further classify the nodes and called the final node as a leaf node.

Example: Suppose there is a candidate who has a job offer and wants to decide
whether he should accept the offer or Not. So, to solve this problem, the decision tree
starts with the root node (Salary attribute by ASM). The root node splits further into the
next decision node (distance from the office) and one leaf node based on the
corresponding labels. The next decision node further gets split into one decision node
(Cab facility) and one leaf node. Finally, the decision node splits into two leaf nodes
(Accepted offers and Declined offer). Consider the below diagram:
Attribute Selection Measures
While implementing a Decision tree, the main issue arises that how to select the best
attribute for the root node and for sub-nodes. So, to solve such problems there is a
technique which is called as Attribute selection measure or ASM. By this
measurement, we can easily select the best attribute for the nodes of the tree. There are
two popular techniques for ASM, which are:

o Information Gain
o Gini Index

1. Information Gain:

o Information gain is the measurement of changes in entropy after the

segmentation of a dataset based on an attribute.
o It calculates how much information a feature provides us about a class.
o According to the value of information gain, we split the node and build the
decision tree.
 o A decision tree algorithm always tries to maximize the value of information gain,
and a node/attribute having the highest information gain is split first. It can be
calculated using the below formula:

1. Information Gain= Entropy(S)- [(Weighted Avg) *Entropy(each feature)

Entropy: Entropy is a metric to measure the impurity in a given attribute. It specifies

randomness in data. Entropy can be calculated as:

Entropy(s)= -P(yes)log2 P(yes)- P(no) log2 P(no)

Where,

o S= Total number of samples

o P(yes)= probability of yes
o P(no)= probability of no

2. Gini Index:

o Gini index is a measure of impurity or purity used while creating a decision tree in
the CART(Classification and Regression Tree) algorithm.
o An attribute with the low Gini index should be preferred as compared to the high
Gini index.
o It only creates binary splits, and the CART algorithm uses the Gini index to create
binary splits.
o Gini index can be calculated using the below formula:

Gini Index= 1- ∑jPj2

Advantages of the Decision Tree

o It is simple to understand as it follows the same process which a human follow
while making any decision in real-life.
o It can be very useful for solving decision-related problems.
o It helps to think about all the possible outcomes for a problem.
o There is less requirement of data cleaning compared to other algorithms.
Disadvantages of the Decision Tree
o The decision tree contains lots of layers, which makes it complex.
o It may have an overfitting issue, which can be resolved using the Random Forest
algorithm.
o For more class labels, the computational complexity of the decision tree may
increase.

How to avoid overfitting the Decision tree model?

Overfitting is one of the major problem for every model in machine learning. If model is

overfitted it will poorly generalized to new samples. To avoid decision tree from

overfitting we remove the branches that make use of features having low

importance. This method is called as Pruning or post-pruning. This way we will reduce

the complexity of tree, and hence improves predictive accuracy by the reduction of

overfitting.

Pruning should reduce the size of a learning tree without reducing predictive accuracy as

measured by a cross-validation set. There are 2 major Pruning techniques.

 Minimum Error: The tree is pruned back to the point where the cross-validated error

is a minimum.

 Smallest Tree: The tree is pruned back slightly further than the minimum error.

Technically the pruning creates a decision tree with cross-validation error within 1

standard error of the minimum error.

Early Stop or Pre-pruning

An alternative method to prevent overfitting is to try and stop the tree-building process

early, before it produces leaves with very small samples. This heuristic is known as early

stopping but is also sometimes known as pre-pruning decision trees.

At each stage of splitting the tree, we check the cross-validation error. If the error does

not decrease significantly enough then we stop. Early stopping may underfit by stopping

too early. The current split may be of little benefit, but having made it, subsequent splits

more significantly reduce the error.

Early stopping and pruning can be used together, separately, or not at all. Post pruning

decision trees is more mathematically rigorous, finding a tree at least as good as early

stopping. Early stopping is a quick fix heuristic. If used together with pruning, early

stopping may save time. After all, why build a tree only to prune it back again?
Decision Trees
Key concepts:
1. Building decision trees
2. Pruning decision trees

Building Decision Trees

Decision trees are tree-structured models for classification and
regression.
The figure below shows an example of a decision tree to determine
what kind of contact lens a person may wear. The choices (classes)
are none, soft and hard. The attributes that we can obtain from the
person are their tear production rate (reduced or normal), whether
they have astigmatism (yes/no), their age category (presbyopic or
not, young or not), their spectacle prescription (myopia or
hypermetropia).
Caption: Decision tree to determine type of contact lens to be worn by a person. The
known attributes of the person are tear production rate, whether he/she has
astigmatism, their age (categorized into two values) and their spectacle prescription.

Decision trees can be learned from training data. Training data will
typically comprise many instances of the following kind:

Instance 1 attribute1 attribute2

Instance 2 attribute1 attribute2
The decision tree learning algorithm recursively learns the tree as
follows:
1. Assign all training instances to the root of the tree. Set curent
node to root node.
2. For each attribute
a. Partition all data instances at the node by the value of
the attribute.
 b. Compute the information gain ratio from the
partitioning.
3. Identify feature that results in the greatest information gain
ratio. Set this feature to be the splitting criterion at the
current node.
a. If the best information gain ratio is 0, tag the current
node as a leaf and return.
4. Partition all instances according to attribute value of the best
feature.
5. Denote each partition as a child node of the current node.
6. For each child node:
a. If the child node is “pure” (has instances from only one
class) tag it as a leaf and return.
b. If not set the child node as the current node and recurse
to step 2.

Pruning decision trees

Decision trees that are trained on any training data run the risk
of overfitting the training data.
What we mean by this is that eventually each leaf will reperesent a
very specific set of attribute combinations that are seen in the
training data, and the tree will consequently not be able to classify
attribute value combinations that are not seen in the training data.
In order to prevent this from happening, we must prune the
decision tree.
By pruning we mean that the lower ends (the leaves) of the tree are
“snipped” until the tree is much smaller. The figure below shows
an example of a full tree, and the same tree after it has been
pruned to have only 4 leaves.

Caption: The figure to the right is a pruned version of the decision tree to the left.

Pruning can be performed in many ways. Here are two.

Pruning by Information Gain

The simplest technique is to prune out portions of the tree that
result in the least information gain. This procedure does not
require any additional data, and only bases the pruning on the
information that is already computed when the tree is being built
from training data.
The process of IG-based pruning requires us to identify “twigs”,
nodes whose children are all leaves. “Pruning” a twig removes all
of the leaves which are the children of the twig, and makes the
twig a leaf. The figure below illustrates this.
Caption: Pruning the encircled twig in the left figure results in the tree to the right.
The twig now becomes a leaf.

The algorithm for pruning is as follows:

1. Catalog all twigs in the tree
2. Count the total number of leaves in the tree.
3. While the number of leaves in the tree exceeds the desired
number:
a. Find the twig with the least Information Gain
b. Remove all child nodes of the twig.
c. Relabel twig as a leaf.
d. Update the leaf count.

Pruning by Classification Performance on Validation

Set
An alternate approach is to prune the tree to maximize
classification performance on a validation set (a data set with
known labels, which was not used to train the tree).
We pass the validation data down the tree. At each node, we
record the total number of instances and the number of
misclassifications, if that node were actually a leaf. We do this at all
nodes and leaves.
Subsequently, we prune all twigs where pruning results in the
smallest overall increase in classification error.
The overall algorithm for pruning is as follows:
Stage 1:
1. For each instance of validation data:
Recursively pass
• Catalog all twigs in the tree
• Count the total number of leaves in the tree.
• While the number of leaves in the tree exceeds the desired number:

a. Find the twig with the least Information Gain

b. Remove all child nodes of the twig.
c. Relabel twig as a leaf.
d. Update the leaf count.

Other forms for pruning

Pruning may also use other criteria, e.g. minimizing computational complexity, or using other
techniques, e.g. randomized pruning of entire subtrees.