CS3491- Artificial Intelligence

and Machine Learning

Unit III
SUPERVISED LEARNING
Topic: Decision Tree
Decision Tree
Decision Tree Analysis is a general,
predictive modelling tool
It has applications spanning a number of
different areas
Decision trees are constructed via an
algorithmic approach that identifies ways to
split a data set based on different
conditions
It is one of the most widely used and
practical methods for supervised learning
Decision trees are non-parametric
supervised learning method.
Goal:
To create a model that predicts the value of
a target variable by learning simple decision
rules inferred from the data features
The decision rules are generally in form of
if-then-else statements
The deeper tree, the more complex the
rules and fitter the model.
Some of the Terminologies
Instances
Refer to vector of features or attributes that
defines the input space.
Attributes
A quantity describing an instance
Concepts
The function that maps input to output
Target concept
The function that we are trying to find. i.e.,
the actual answer
Some of the Terminologies
Hypothesis class
Set of all the possible functions
Sample
A set of inputs paired with a label, which is the
correct output (also known as the training set)
Candidate concept
A concept that we think is the target concept
Testing set
Similar to the training set and is used to test
the candidate concept and determine its
performance.
General Structure of Decision
tree
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:
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.
Types of Decision Tree
4 popular types of decision tree algorithms:
ID3
CART (Classification and Regression Trees)
Chi-Square
Reduction in Variance
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.
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
Decision Tree Terminologies
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:
Algorithm
 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.
 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
Depatment
into two leafof CSE, Ramco
nodesInstitute of Tec
(Accepted
hnology, RJPM
offers and Declined offer).
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:
Information Gain
Gini Index
Information Gain:
 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 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,
 S= Total number of samples
 P(yes)= probability of yes
 P(no)= probability of no
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:
 2
Pruning: Getting an Optimal
Decision tree
Pruning is a process of deleting the
unnecessary nodes from a tree in order to
get the optimal decision tree.
A too-large tree increases the risk of
overfitting, and a small tree may not
capture all the important features of the
dataset.
Therefore, a technique that decreases the
size of the learning tree without reducing
accuracy is known as Pruning.
There are mainly two types of
tree pruning technology used:
Cost Complexity Pruning
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.
It helps to think about all the 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 may have an overfitting issue, which can
be resolved using the Random Forest
algorithm.
For more class labels, the computational
complexity of the decision tree may
increase.
Decision Tree:
Implementation
Data Pre-processing step
Fitting a Decision-Tree algorithm to
the Training set
Predicting the test result
Test accuracy of the result(Creation of
Confusion matrix)
Visualizing the test set result.
Decision Tree for playing tennis
dataset
Play [Link] contains the data set.
Play Tennis Implementation Using Sklearn
Decision Tree [Link] is the
implementation.

09/16/2025
1. Data Pre-Processing Step:
2. Fitting a Decision-Tree algorithm
to the Training set
3. Predicting the test result
4. Test accuracy of the result
(Creation of Confusion matrix)
5. Visualizing the training set
result:
6. Visualizing the test set result: