Course Name : MACHINE LEARNING

Course Code : 20AM01

Course Instructor : K.Rajasekhar

Semester : VI

Regulation : R23

Unit: 3

​

​

​

​

​

​

​

1

UNIT-3: SYLLABUS

Models Based on Decision Trees:

Decision Trees for Classification, Impurity Measures, Properties, Regression Based on Decision Trees, Bias–Variance Trade-off, Random Forests for Classification and Regression. The Bayes Classifier: Introduction to the Bayes Classifier, Bayes’ Rule and Inference, The Bayes Classifier and its Optimality, Multi-Class Classification, Class Conditional Independence and Naive Bayes Classifier (NBC) .

�

Decision Trees for Classification (Cont’d..)

• Decision tree learning is one of the most widely adopted algorithms for classification, and builds a model in the form of tree structure.
• A Decision Tree is a supervised learning algorithm used for classification and regression.�For classification, it splits the dataset into subsets based on feature values, 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 external nodes represents outcome. .
• The goal of decision tree learning is to create a model (based on the past data called past vector) that predicts the value of the output variable based on the input variables in the feature vector.

​

A Decision Tree Terminologies

A decision tree consists of three types of nodes:

• Root node , Branch node , Leaf node
• Root node: Root node is from where the decision tree starts. It represents the entire dataset, which further gets divided into two or more homogenous sets.
• Leaf node: Leaf nodes are the final output node, and the tree cannot be segregated further after getting a leaf node.
• Decision nodes: are used to make any decision and have multiple branches.
• 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.

Building a Decision Tree

• Decision trees are built based on the training data by implementing recursive portioning.
• It splits the data into multiple subsets on the basis of the feature values.
• First it selects the root node , i.e select one feature from the training data set which predicts the target class in the strongest way.
• The decision tree splits the dataset into multiple partitions , based on the class values of selected feature.
• This is the first set of branches.

Building a Decision Tree

• Like wise the algorithm continues splitting the nodes on the basis of the feature which helps in the best partition , until stopping criterion is reached.
• The usual stopping criteria are-
• All or most of the examples at a particular node have the same class.
• All features have been used up in the portioning
• The tree has grown to a pre-defined threshold limit.

Algorithm for Decision Tree

• 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 contain 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.

A Decision Tree – Example –Car Driving

• The decision to be taken is whether to ‘keep going’ or to ‘stop’ , depends on various situations.
• If the signal is RED in color, then the car should be stopped.
• If there is not enough gas (petrol) in the car should be stopped at the next available gas station.

Attribute Selection Measures (ASM)

• 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 solve such problems there is a technique which is called as Attribute Selection Measure (ASM)

There are two popular techniques for ASM, which are:

• Information Gain
• Entropy

​

Impurity Measures: (cont’d)

• Impurity measures are used in decision tree algorithms to decide how to split data at each node.�They quantify how mixed (impure) the class labels are in a node.
• Goal: Minimize impurity after each split.

Why Impurity Measures Are Needed

• To choose the best feature for splitting
• To create pure leaf nodes (only one class)
• Used in classification trees

Major Impurity Measures

1.Entropy

• Used in ID3 algorithm
• Formula:

​

​

​

Strengths of Decision Trees

• It produces very simple understandable rules.
• For smaller trees , not much mathematical and computational knowledge is required to understand this model.
• Works well for most of the problems
• It can handle both numerical and categorical variables.
• Can work well both with small and large training datasets.
• Decision trees provide a definite clue of which features are more useful for classification.

​

Weakness of Decision Trees

• Decision tree models are often biased towards features having more number of possible values, i.e levels.
• This model gets over-fitted or under-fitted quite easily.
• Decision trees are prone to errors in classification problems with many classes and relatively small number of training examples.
• A decision tree can be computationally expensive to train.
• Large trees are complex to understand.

​

Applications of Decision Trees

• Business Management: Extract useful information from databases.
• Customer Relationship Management: Decision trees are useful for understanding theirs customers needs and preferences.
• Fraudulent statement detection: Detection of fraudulent financial statement (FFS) –discover all hidden information.
• Engineering: Widely used in energy consumption and fault diagnosis.
• Energy consumption – Energy consumption concerns how much electricity has been used by individuals.
• Fault diagnosis: the identification of a faulty parts/tools in machineries.
• Healthcare Management: To discover and/or explore hidden information of patients illness.

​

Properties of Decision Trees Classifiers

• Impurity measures are used to evaluate how well a node is split in a decision tree.

A good impurity measure satisfies the following properties:.

1. Splitting Rule

• A splitting rule defines how the data at a node is divided into child nodes.
• The rule is usually a condition on a feature

Is Age ≤ 30? → Yes / No

The rule divides data into child nodes

II. Criterion for Splitting

The feature for splitting is chosen using a purity measure

• Entropy�Measures randomness in data
• Information Gain�Reduction in entropy after split
• Gini Index�Measures probability of misclassification
• The feature that gives maximum purity is selected

​

​

Properties of Decision Trees Classifiers

3. Binary or Non-Binary Splits

• Decision trees can be:
• Binary → Two child nodes (Yes/No)
• Non-Binary → More than two branches
• Example:
• Gender → Male / Female (binary)
• Day → Mon/Tue/Wed… (non-binary)

4.Termination Condition (Stopping Criteria)

• Tree growth stops when:
• All samples belong to same class
• No features are left
• Maximum depth is reached
• Minimum number of samples is reached

​

​

​

​

Properties of Decision Trees Classifiers

5. Class Labels

• Leaf nodes represent final decision outcomes
• The class label is assigned based on:
• Majority voting
• Highest probability class
• Example:
• If 8 samples are “Yes” and 2 are “No” → Label = Yes

6. Classification

• For classification problems, output is a discrete class
• Example:
• Spam / Not Spam Customer → Buy / Not Buy
• Pass / Fail

7.Transparency (Interpretability)

• Decision trees are easy to understand
• Decisions follow if–else rules
• Highly transparent and explainable
• If Age > 25 AND Income > 50K → Approve Loan

​

​

Properties of Decision Trees Classifiers

8. Handling Mixed Data Types

Can handle:

• Numerical data (Age, Marks)
• Categorical data (Gender, Department)
• No need for feature scaling

9 Eliminating Irrelevant Features

• Features that do not improve splitting are ignored
• Only features with high information gain are selected
• Helps reduce noise in the model

10 Pruning Decision Tree

• Pruning removes unnecessary branches
• Reduces over-fitting

Types:

• Pre-pruning → Stop early
• Post-pruning → Cut after full tree growth

​

​

​

​

​

Regression Based on Decision Trees

Regression based on decision trees is a supervised learning method used to predict continuous-valued outputs.�Unlike classification trees, regression trees output numeric values at leaf nodes. It splits data into smaller subsets using decision rules and fits a model to each subset.

Working Principle

• The dataset is recursively split based on input features
• At each split, the algorithm chooses the feature and threshold that minimizes prediction error
• The process continues until stopping criteria are met

​

​

​

Algorithm (Steps)

1. Splitting the Data: The dataset is recursively split into subsets using a decision criterion (e.g., minimizing variance).

2. Choosing the Best Split: The best split minimizes the Mean Squared Error (MSE) or Mean Absolute Error (MAE).

3. Stopping Criteria: The process continues until a stopping condition is met (e.g., max depth reached or number of samples in a node is below a threshold).

4. Prediction: At each terminal (leaf) node, the model predicts the mean value of the observations in that node.

​

​

​

Regression Based on Decision Trees

Regression Based on Decision Trees

Advantages:

• Simple to understand and interpret.
• Handles both linear and non-linear relationships.
• No need for feature scaling (like normalization or standardization).
• Works well with both small and large datasets.

Disadvantages

• Prone to over-fitting if not pruned.
• Sensitive to small changes in data, leading to high variance.
• Greedy algorithm may not always produce the optimal tree.

​

Bias–Variance Trade-of (Cont’d)

• Bias is the error caused by making too many assumptions in the learning algorithm.
• High bias → The Model is too simple
• Fails to capture the underlying pattern
• Leads to underfitting

Example:�Using a linear regression model for highly curved (non-linear) data.

Characteristics:

• High training error
• High testing error
• Model ignores important features or patterns

​

​

Bias–Variance Trade-of (Cont’d)

Variance

• Variance is the error due to the model being too sensitive to training data.
• High variance → model is too complex
• Learns noise along with data
• Leads to overfitting

Example:�A very deep decision tree that perfectly fits training data but performs poorly on new data.

Characteristics:

• Very low training error
• High testing error
• Model changes a lot with small data changes

​

​

Bias–Variance Trade-of (Cont’d)

Understanding Bias and Variance with an Example

• Consider a student trying to predict house prices based on size.
• High Bias (Underfitting): The student only considers a single factor (Like size) and ignores other features. Their estimate is always inaccurate.
• High Variance (Overfitting): The student memorizes every past sale price, so the prediction changes drastically with small variations in new houses.

​

How to Reduce Bias and Variance

To reduce Bias:

• Use a more complex model, Add more features,
• Reduce regularization

To reduce Variance:

• Collect more training data,Use regularization (L1/L2)
• Prune decision trees
• Use ensemble methods (Random Forest, Bagging)

​

​

Simple Real-World Analogy 🎯

• Bias: Shooting arrows but missing the target consistently
• Variance: Arrows scattered everywhere
• Good model: Arrows close to the center and consistent

​

​

​

Ensemble Learning in Machine Learning

Ensemble learning is a supervised learning technique used in machine learning to improve overall performance by combining the predictions from multiple models.

• Voting (Averaging)
• Bootstrap aggregation (bagging)
• Random forests
• Boosting
• Stacked Generalization (Blending)

​

​

​

Random Forest for classification

• Random forest is a commonly used machine learning algorithm.
• A random forest is an ensemble learning method where multiple decision trees are constructed and they are merged to get a more accurate prediction.
• Random forest became popular because of its ease of use and flexibility in handling both classification and regression problems.
• It gets predictions from each tree and by means of majority voting, it selects the decision which gets the majority vote.

​

​

Random Forest for classification

Steps for Random forest algorithm :

• Multiple random K samples are created from the training dataset using bootstrapping (random sampling with replacement).
• Build the decision tree associated with these K data points on each sample.
• At every split, only a random subset of features is considered.
• Predictions from all trees are combined:
• Classification → Majority voting
• Regression → Average of predictions

​

​

Random Forest Strengths

Strengths:

• It takes less training time as compared to other algorithms.
• It predicts output with high accuracy, even for the large dataset it runs efficiently.
• It can also maintain accuracy when a large proportion of data is missing.

​

• Weakness:
• A weakness of random forest algorithms is that when used for regression they cannot predict beyond the range in the training data, and that they may over-fit datasets that are particular noisy.
• The sizes of the models created by random forests may be very large. It may take hundreds of megabytes of memory and may be slow to evaluate.
• Random forest models are black boxes that are very hard to interpret.

​

Applications of Random Forest

• Banking: In banking sector mostly uses this algorithm for the identification of loan risk.
• Medicine: With the help of this algorithm, disease trends and risks of the disease can be identified.
• Land Use: We can identify the areas of similar land use by this algorithm.
• Marketing: Marketing trends can be identified using algorithm.
• E-commerce: Product recommendation , Price optimization
• Stock market: Stock market prediction,
• Bit coin price detection

​

Random Forest for Regression

• Random Forest Regression is an ensemble learning algorithm that uses multiple decision trees to predict a continuous (numerical) value.
• Instead of relying on one decision tree, it combines the predictions of many trees to give a more accurate and stable result.

How Random Forest Regression Works

• From the original dataset, multiple random samples are created using bootstrapping (sampling with replacement).
• A decision tree regressor is trained on each sample.
• At every split in a tree, only a random subset of features is considered.
• Each tree predicts a numeric value.
• The final prediction is the average of all tree predictions.

​

​

The Bayes Classifier

The Bayes Classifier

The Bayes Classifier

The Bayes Classifier

The Bayes Classifier

The Bayes Classifier

The Bayes Classifier

The Bayes Classifier

Why is it Optimal?

• The Bayes classifier minimizes the probability of classification error.
• For 0–1 loss function, it achieves the minimum possible error rate, called the Bayes Error Rate
• No other classifier can perform better on average

Bayes Error Rate

​

Multi-class classification

• Multi-class classification is a supervised learning task in which each instance is assigned to one of more than two possible classes.
• Algorithms such as Naive Bayes, Decision Trees, k-NN, SVM, and Neural Networks are commonly used to solve multi-class problems.
• Number of classes ≥ 3

Examples (Real-World)

• Handwritten digit recognition → classes: 0–9
• Document classification → sports, politics, education, health
• Image classification → cat, dog, car, bike
• Student grade prediction → A, B, C, D

​

Multi-class classification

Class Conditional Independence?

• Class conditional independence assumes that features are independent of each other given the class label. This assumption simplifies the computation of class-conditional probabilities and forms the foundation of the Naive Bayes classifier.

​

The Naïve Bayes Classifier

The Naïve Bayes Classifier

The Bayes Classifier

The Naïve Bayes Classifier

The Naïve Bayes Classifier

The Naïve Bayes Classifier

The Naïve Bayes Classifier

The Naïve Bayes Classifier