Decision Tree algorithm using

Entropy and Gini Index

Artificial Intelligence 1
 What is decision tree?
• A Supervised learning technique that can be used for both
classification and Regression problems, but mostly it is preferred
for solving Classification problems.
• Contains two nodes: 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.
• 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.
• The decisions or the test are performed on the basis of features of
the given dataset.
• It is a graphical representation for getting all the possible
solutions to a problem/decision based on given conditions.

Artificial Intelligence
2
CONTD…
• In order to build a tree, we use the CART algorithm, which
stands for Classification and Regression Tree algorithm.
• A decision tree simply asks a question, and based on the
answer (Yes/No), it further split the tree into subtrees

Artificial Intelligence
3
 Significance of decision tree

• Decision Trees usually mimic human thinking ability

while making a decision, so it is easy to understand.
• The logic behind the decision tree can be easily
understood because it shows a tree-like structure.

Artificial Intelligence
4
 Decision Tree Terminologies
 Root Node: Node from where the decision tree starts. It
represents the entire dataset, which further gets divided into two
or more homogeneous sets.

 Leaf Node: Final output node, and the tree cannot be segregated
further after getting a leaf node.

 Splitting: 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.

Artificial Intelligence
5
 Decision tree algorithm working

• Step-1: Begin the tree with the root node, says S, which contains
the complete dataset.
• Step-2: Find the best attribute in the dataset using Attribute
Selection Measure (ASM).
• Step-3: Divide the S into subsets that contains possible values
for the best attributes.
• Step-4: Generate the decision tree node, which contains the best
attribute.
• 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.

Artificial Intelligence
6
Illustrative Example

Artificial Intelligence
7
Attribute Selection Measures:
Entropy

Artificial Intelligence 8
 Attribute Selection Measures:
Information Gains

• Information gain is the measurement of changes in entropy after

the segmentation of a dataset based on an attribute.
• It calculates how much information a feature provides us about a
class.
• According to the value of information gain, we split the node and
build the decision tree.
• 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:

Information Gain= Entropy(S)- [(Weighted Avg) *Entropy(each feat

ure)]

Artificial Intelligence
9
 Attribute Selection Measures: Gini
Index

•Gini index is a measure of impurity or purity used while

creating a decision tree in the CART(Classification and
Regression Tree) algorithm.

•An attribute with the low Gini index should be preferred as

compared to the high Gini index.

•It only creates binary splits, and the CART algorithm uses the
Gini index to create binary splits.

•Gini index can be calculated using the below formula:

Gini Index= 1 - ∑jPj2

Artificial Intelligence
10
 Numerical example –
Decision Tree (Entropy, Gini Impurity
& Information Gain)

Artificial Intelligence 11
Artificial Intelligence 12
Artificial Intelligence 13
Artificial Intelligence 14
Artificial Intelligence 15
Computation time is reduced as don’t use
logarithmic function in Gini impurity

Artificial Intelligence 16
 Advantages & Disadvantages of the
Decision Tree
Advantages of the Decision Tree
•It is simple to understand as it follows the same process which a
human follow while making any decision in real-life.
•It can be very useful for solving decision-related problems and to
generate possible outcomes for a problem.
•There is less requirement of data cleaning compared to other
algorithms.

Disadvantages of the Decision Tree

•The decision tree contains lots of layers, which makes it complex.
•It has overfitting issue - resolved using the Random Forest algorithm.
•For more class labels, the computational complexity of the decision
tree may increase.

Artificial Intelligence
17
Naïve Bayes Classifiers

Artificial Intelligence 18
 Naïve Bayes algorithm?
• Naïve Bayes algorithm is a supervised learning algorithm, which is based
on Bayes theorem and used for solving classification problems.
• Naïve Bayes Classifier is one of the simple and most effective Classification
algorithms which helps in building the fast machine learning models that can
make quick predictions.
• It is a probabilistic classifier, which means it predicts on the basis of the
probability of an object.
• The Naïve Bayes algorithm is comprised of two words Naïve and Bayes, Which
can be described as:
 Naïve: It is called Naïve because it assumes that the occurrence of a certain
feature is independent of the occurrence of other features. Such as if the
fruit is identified on the bases of color, shape, and taste, then red, spherical,
and sweet fruit is recognized as an apple. Hence each feature individually
contributes to identify that it is an apple without depending on each other.
 Bayes: It is called Bayes because it depends on the principle of Bayes'
Theorem.

Artificial Intelligence
19
 Bayes’ Theorem
• Bayes' theorem is also known as Bayes' Rule or Bayes' law,
which is used to determine the probability of a hypothesis with
prior knowledge. It depends on the conditional probability.
• The formula for Bayes' theorem is given as:

Where,
P(A|B) is Posterior probability: Probability of hypothesis A on the
observed event B.
P(B|A) is Likelihood probability: Probability of the evidence given
that the probability of a hypothesis is true.
P(A) is Prior Probability: Probability of hypothesis before
observing the evidence.
P(B) is Marginal Probability: Probability of Evidence.

Artificial Intelligence
20
 Working of Naïve Bayes’
Classifier
• Working of Naïve Bayes' Classifier can be understood with the
help of the below example:
• Suppose we have a dataset of weather conditions and
corresponding target variable "Play". So using this dataset we
need to decide that whether we should play or not on a
particular day according to the weather conditions.
• So to solve this problem, we need to follow the below steps:
1. Convert the given dataset into frequency tables.
2. Generate Likelihood table by finding the probabilities of
given features.
3. Now, use Bayes theorem to calculate the posterior
probability.

Artificial Intelligence
21
 Outlook Play

CONTD… 0 Rainy Yes

1 Sunny Yes
2 Overcast Yes
3 Overcast Yes
4 Sunny No
Problem: If the weather is sunny,
then the Player should play or 5 Rainy Yes
not? 6 Sunny Yes
Solution: To solve this, first
7 Overcast Yes
consider the given dataset
8 Rainy No
9 Sunny No
10 Sunny Yes
11 Rainy No
12 Overcast Yes
13 Overcast Yes

Artificial Intelligence 22
CONTD…

Frequency table for the Weather

Conditions:
Weather Yes No
Overcast 5 0
Rainy 2 2
Sunny 3 2
Total 10 5

Artificial Intelligence
23
CONTD…

Likelihood table weather

condition:
Weather No Yes
Overcast 0 5 5/14= 0.35
Rainy 2 2 4/14=0.29
Sunny 2 3 5/14=0.35
All 4/14=0.29 10/14=0.71

Artificial Intelligence
24
 Applying Bayes’ Theorem
• P(Yes|Sunny)= P(Sunny|Yes)*P(Yes)/P(Sunny)
P(Sunny|Yes)= 3/10= 0.3
P(Sunny)= 0.35, P(Yes)=0.71
So, P(Yes|Sunny) = 0.3*0.71/0.35= 0.60
• P(No|Sunny)= P(Sunny|No)*P(No)/P(Sunny)
P(Sunny|NO)= 2/4=0.5
P(No)= 0.29, P(Sunny)= 0.35
So P(No|Sunny)= 0.5*0.29/0.35 = 0.41
As we can see from the above calculation that P(Yes|
Sunny)>P(No|Sunny)
Hence on a Sunny day, Player can play the game.

Artificial Intelligence
25
 Advantages, Disadvantages and
Application
• Advantages
 It can be used for Binary as well as Multi-class Classifications and
performs well in Multi-class predictions as compared to the other
Algorithms.
 It is widely used for text classification problems.
• Disadvantages: Naive Bayes assumes that all features are independent or
unrelated, so it cannot learn the relationship between features.

• Application
 Credit Scoring
 Medical data classification.
 In real-time predictions because Naïve Bayes Classifier is an eager
learner.
 Used in Text classification such as Spam filtering and Sentiment
analysis.

Artificial Intelligence
26
Thank you

Artificial Intelligence 27