DSS-Unit 6
Q1.Explain decision trees in detail with example.
Ans-Introduction
A Decision Tree is one of the most popular and powerful algorithms used in machine learning and data
analysis. It is a tree-structured model that is used for classification and regression tasks. The structure of
the decision tree is very similar to a tree data structure used in programming. It consists of nodes, branches,
and leaves.
The topmost node of the tree is called the Root Node, which represents the entire dataset and is divided into
two or more homogeneous sets. The internal nodes represent tests on attributes, each branch represents an
outcome of a test, and the leaf nodes represent the final decision or output.
Concept of Decision Tree
In a Decision Tree:
1.Each internal node represents a condition or test on an attribute.
2.Each branch represents the result of the test.
3.Each leaf node represents a class label or output.
The final goal of the Decision Tree algorithm is to create a model that predicts the value of a target variable
by learning simple decision rules inferred from data features.
It is a Supervised Learning Algorithm, meaning it requires labeled input data (training data) to learn from.
Working of a Decision Tree Algorithm
The Decision Tree algorithm works in a top-down approach, known as recursive partitioning. The
algorithm chooses an attribute that best splits the data into different classes. This process is repeated
recursively for each sub-dataset.
Step-by-Step Working:
1.Start with the entire dataset as the root node.
2.Select the best attribute using statistical measures such as:
Entropy
Information Gain
Gini Index
3. Split the dataset into subsets based on the chosen attribute.
4. Repeat the process for each subset until:
All records in a subset belong to the same class, or
No remaining attributes are left to split.
5.The final nodes are the leaf nodes, which represent the classification result.
VG note Page 1
, Mathematical Concepts Used
1. Entropy:
It measures the impurity or disorder in the dataset.
Formula:Entropy=−∑pilog2(pi)
where pi is the probability of each class in the dataset.
Lower Entropy ⇒ Higher purity.
2.Information Gain:
It measures how much information an attribute gives us about the class.
Formula:IG=Entropy(parent)−∑ni/n ×Entropy(i)
The attribute with the highest information gain is chosen for splitting.
3.Gini Index:
It is another measure of impurity used in classification tasks.
Formula:Gini=1−∑pi2
Algorithm Used: ID3 Algorithm
One of the most commonly used algorithms for constructing a decision tree is ID3 (Iterative Dichotomiser
3).
Steps in ID3:
2. Begin with the original dataset as the root node.
3. For each attribute, calculate Entropy and Information Gain.
4. Select the attribute with the highest Information Gain.
5. Split the dataset based on that attribute.
6. Repeat recursively until all data is classified.
Example:=Let us consider a simple example of predicting whether a person will play cricket based on
weather conditions.
Weather Temperature Play Cricket
Sunny Hot No
Sunny Mild No
Cool Yes
Overcast
Rainy Mild Yes
Rainy Cool Yes
VG note Page 2
Q1.Explain decision trees in detail with example.
Ans-Introduction
A Decision Tree is one of the most popular and powerful algorithms used in machine learning and data
analysis. It is a tree-structured model that is used for classification and regression tasks. The structure of
the decision tree is very similar to a tree data structure used in programming. It consists of nodes, branches,
and leaves.
The topmost node of the tree is called the Root Node, which represents the entire dataset and is divided into
two or more homogeneous sets. The internal nodes represent tests on attributes, each branch represents an
outcome of a test, and the leaf nodes represent the final decision or output.
Concept of Decision Tree
In a Decision Tree:
1.Each internal node represents a condition or test on an attribute.
2.Each branch represents the result of the test.
3.Each leaf node represents a class label or output.
The final goal of the Decision Tree algorithm is to create a model that predicts the value of a target variable
by learning simple decision rules inferred from data features.
It is a Supervised Learning Algorithm, meaning it requires labeled input data (training data) to learn from.
Working of a Decision Tree Algorithm
The Decision Tree algorithm works in a top-down approach, known as recursive partitioning. The
algorithm chooses an attribute that best splits the data into different classes. This process is repeated
recursively for each sub-dataset.
Step-by-Step Working:
1.Start with the entire dataset as the root node.
2.Select the best attribute using statistical measures such as:
Entropy
Information Gain
Gini Index
3. Split the dataset into subsets based on the chosen attribute.
4. Repeat the process for each subset until:
All records in a subset belong to the same class, or
No remaining attributes are left to split.
5.The final nodes are the leaf nodes, which represent the classification result.
VG note Page 1
, Mathematical Concepts Used
1. Entropy:
It measures the impurity or disorder in the dataset.
Formula:Entropy=−∑pilog2(pi)
where pi is the probability of each class in the dataset.
Lower Entropy ⇒ Higher purity.
2.Information Gain:
It measures how much information an attribute gives us about the class.
Formula:IG=Entropy(parent)−∑ni/n ×Entropy(i)
The attribute with the highest information gain is chosen for splitting.
3.Gini Index:
It is another measure of impurity used in classification tasks.
Formula:Gini=1−∑pi2
Algorithm Used: ID3 Algorithm
One of the most commonly used algorithms for constructing a decision tree is ID3 (Iterative Dichotomiser
3).
Steps in ID3:
2. Begin with the original dataset as the root node.
3. For each attribute, calculate Entropy and Information Gain.
4. Select the attribute with the highest Information Gain.
5. Split the dataset based on that attribute.
6. Repeat recursively until all data is classified.
Example:=Let us consider a simple example of predicting whether a person will play cricket based on
weather conditions.
Weather Temperature Play Cricket
Sunny Hot No
Sunny Mild No
Cool Yes
Overcast
Rainy Mild Yes
Rainy Cool Yes
VG note Page 2
