UNIT-2

Unit-2
What is Concept Learning?
• Machine learning is all about teaching computers to learn from data and make decisions without
being explicitly programmed.
• One of the key tasks in machine learning is concept learning, which focuses on learning general
ideas or concepts from specific examples.
• By learning these concepts, machines can classify new data accurately, making this technique
essential for various machine learning applications like image classification, text understanding, and
recommendation systems.
• What is Concept Learning?
• Concept learning in machine learning refers to the process of teaching a machine to identify and
recognize patterns from specific examples or data points.
• In simple terms, concept learning involves learning a general rule from a set of observed instances.
For example, if you show a machine many pictures of cats, it will learn to recognize the concept of a
“cat” and apply that knowledge to identify new cat pictures.

• Concept learning helps machines generalize from data. Instead of memorizing each example, it
creates a broader understanding that can be applied to unseen situations.
• This ability to generalize is what makes machine learning models so powerful.
Types of Concept Learning Tasks
There are two main types of concept learning tasks in machine learning: supervised concept learning
and unsupervised concept learning.
1. Supervised Concept Learning
In supervised concept learning, the machine is given labeled data, meaning each data point has a
known output or target label.
The goal is for the machine to learn the concept by identifying patterns between the inputs and the
labeled outputs.

Example of Supervised Concept Learning:

Consider a dataset of images where each image is labeled as either a “cat” or “dog.”
By analyzing these labeled examples, the machine can learn to classify future images as either a cat
or a dog based on what it has learned from the training data.
 Types of Concept Learning Tasks
2. Unsupervised Concept Learning
In unsupervised concept learning, the machine is given data without labels. The machine’s task is to
identify patterns or groupings within the data. This type of learning is more about discovering hidden
structures in the data rather than learning specific labels.

Example of Unsupervised Concept Learning:

An e-commerce company might use unsupervised learning to group customers based on their
purchasing history.
The algorithm can identify clusters of customers who buy similar products, even though there are no
predefined labels for these groups.
Importance of Concept Learning In Machine Learning
1. Image Classification
Concept learning helps machines recognize objects in images. For example, after learning the concept
of “cat” from many labeled images, a model can identify whether a new image contains a cat, even if it
has never seen that specific image before.
2. Natural Language Processing (NLP)
In NLP tasks, concept learning helps machines understand and process human language. Tasks like
sentiment analysis (detecting emotions in text) and topic modeling (grouping similar text documents)
rely heavily on the machine’s ability to learn concepts from large amounts of text data.
3. Recommendation Systems
Recommendation systems, like those used by Netflix or Amazon, depend on concept learning to
personalize suggestions. These systems learn from users’ past behavior and preferences to recommend
new movies, products, or content that align with those patterns.
4. Fraud Detection
In finance, concept learning is used to identify unusual patterns in transactions that may indicate fraud.
By learning what constitutes normal behavior, models can detect suspicious activities that deviate from
the learned concept.
How Concept Learning Works
Concept learning follows a systematic process where a machine learns to generalize from a set of
data points and apply that understanding to new, unseen data
1. Learning from Examples
The machine starts by analyzing examples or data points. These examples could be labeled (for
supervised learning) or unlabeled (for unsupervised learning). From these examples, the machine
tries to identify patterns and underlying concepts.

2. Hypothesis Formation
Based on the examples provided, the machine forms a hypothesis or a general rule that explains the
data. This hypothesis represents the concept that the machine is trying to learn. For example, a
hypothesis might be “If an image has fur and whiskers, it is a cat.”

3. Hypothesis Space
The machine explores different possible hypotheses to find the best one that fits the data. This
exploration happens within what’s called a hypothesis space, which includes all possible rules or
concepts the machine could learn. The goal is to find the hypothesis that best matches the training
examples.
How Concept Learning Works
4. Generalization
Once a hypothesis is chosen, the machine applies it to new, unseen data.
This process of generalization allows the model to make predictions about
data it hasn’t encountered before, based on the concept it has learned.

5. Refinement
During the learning process, the machine may need to refine its hypothesis
as more data is introduced. It might adjust its concept to better match the
new examples or correct any errors in its initial learning.

This high-level process helps the machine go from specific examples to a

general understanding of a concept that it can apply to new data.
Real-World Applications of Concept Learning
Here are some key real-world examples where concept learning is used effectively:
1. Healthcare
Concept learning is used in healthcare to aid in disease diagnosis. By learning from patient data, machines can
identify patterns that suggest a specific illness or condition. This helps doctors make quicker, more accurate
diagnoses. It’s also used in drug discovery to find potential new treatments based on patterns in biological data.

Example: A model trained to recognize signs of pneumonia in chest X-rays can help doctors identify cases faster
and with greater accuracy.

2. Finance
In the financial industry, concept learning helps detect fraudulent transactions. By analyzing past financial data,
models can learn what normal behavior looks like and flag anything unusual that might indicate fraud.
Additionally, concept learning is used to assess credit risks by identifying patterns in customer financial histories.

Example: A bank might use concept learning to predict whether a customer is likely to default on a loan based on
their spending and repayment history.
Real-World Applications of Concept Learning
3. Retail
Retailers use concept learning in recommendation systems to suggest products to customers based on
their previous purchases and browsing behavior. It’s also used for customer segmentation, which
helps businesses target different groups of customers with personalized marketing strategies.

Example: Amazon’s recommendation engine learns from your shopping history to suggest new
products you might like.

4. Marketing and Advertising

In digital marketing, concept learning helps personalize advertising by predicting what type of
content or products a user is most likely to engage with. This ensures that ads are more relevant,
increasing the chances of customer interaction.

Example: Google Ads uses concept learning to deliver personalized ads to users based on their
search history and online behavior.
Real-World Applications of Concept Learning

5. Manufacturing
Concept learning helps in predictive maintenance, where machines
learn to identify signs of equipment failure before they occur. This
reduces downtime and prevents costly repairs by allowing timely
maintenance.

Example: A manufacturing plant might use concept learning to monitor

machinery data and predict when a machine is likely to break down.
Version space
• Version Space is the subset of the hypothesis space that contains only those hypotheses that are
consistent with all training examples.
• It helps us narrow down the correct hypothesis by eliminating those that don’t match the data.
Version space
Version space
version space
Steps to Find the Find-S Algorithm & The LIST-THEN-ELIMINATE Algorithm
Concept learning can be implemented using various algorithms, two of the popular ones are
the Find-S Algorithm and
the List-Then-Eliminate Algorithm.
1. Find-S Algorithm
The Find-S Algorithm is one of the simplest methods used in concept learning. It helps find the most specific hypothesis
that fits all the positive training examples.
Steps of the Find-S Algorithm:
Step 1: Start with the most specific hypothesis possible (usually the null hypothesis, which does not classify any
example).
Step 2: For each positive example in the training data:
If the example matches the current hypothesis, continue.
If it doesn’t match, update the hypothesis to the least specific generalization that still fits the new example.
Step 3: Repeat the process for all positive examples.
Step 4: The final hypothesis will be the most specific hypothesis that fits all the positive examples.
Example: If you’re training a model to identify dogs and cats and start with a null hypothesis, the algorithm updates the
hypothesis each time a new positive (correctly labeled) example is encountered, gradually learning to distinguish
between the two categories.
List-Then-Eliminate Algorithm

The List-Then-Eliminate Algorithm works by keeping a list of all possible hypotheses and then
eliminating the ones that do not fit the training examples.

Steps of the List-Then-Eliminate Algorithm:

Step 1: Start with a list containing all possible hypotheses (hypothesis space).
Step 2: For each example in the training data, eliminate any hypothesis from the list that doesn’t fit the
example.
Step 3: Repeat this process for all examples until you are left with the set of hypotheses that are
consistent with the training data.
Step 4: Once all inconsistent hypotheses have been eliminated, the remaining hypotheses are the ones
that could explain the data.
Example: In a scenario where the machine is learning to classify animals, the algorithm starts with a
list of all possible categories. With each new training example, it eliminates any hypothesis that
doesn’t fit the data until it finds the best match.
Candidate Elimination Algorithm in Machine Learning (ML)
• Machine learning (ML) is a field that focuses on developing systems capable of learning from data
to identify patterns and make decisions.
• Within ML, a key task is concept learning, which involves finding a hypothesis that best describes
a given set of training examples.
• This process helps machines understand and generalize from data, enabling them to predict
outcomes for new, unseen examples.

• The Candidate Elimination Algorithm (CEA) is an important approach used in concept learning.
• It helps find all hypotheses that are consistent with the training data, ensuring that the model
accurately represents the concept being learned.
• CEA systematically searches through a set of possible hypotheses, refining them based on the data
to identify the most suitable ones.
What is the Candidate Elimination Algorithm?
The Candidate Elimination Algorithm (CEA) is used in machine learning for concept learning. It
identifies all hypotheses that fit the training data, forming a version space—a set of consistent
hypotheses. CEA uses two boundaries:

General Hypothesis (G): The broadest descriptions that fit the data.
Specific Hypothesis (S): The narrowest descriptions that fit the data.
Important Terms Used
Concept Learning: The process of finding a hypothesis that describes a target concept based on
examples, aiming to generalize from specific cases.
General Hypothesis (G): The broadest hypothesis covering all possible instances (e.g.,
G={?,?,…}).
Specific Hypothesis (S): The narrowest hypothesis covering only observed instances (e.g.,
S={p1,p2,…}).
Version Space: The set of all hypotheses consistent with training examples. CEA refines this space
to find the best fit.
SVM (Support Vector Machine)
SVM
 SVM-image 1
Middle Line as Classifier:
• The preferred decision boundary lies in the middle of the data separation.
• It stays approximately equidistant from data in both classes.
Problems with Extreme Lines:
• Lines too close to one class may cause misclassification.
• A line “tight up” against training data may overfit.
"Just Right" Classifier:
• The middle line avoids this and achieves better generalization.
Margin and No-Man’s Land:
• We imagine a ‘no-man’s land’ around the decision boundary.
• Points inside this region are considered too close to classify reliably.
Symmetric Margin:
• The region is symmetric and extends equally on both sides.
• The largest radius of this region is the margin, denoted M.
SVM
Maximum Margin Classifier:
• The middle line in the figure has the maximum [Link] the maximum margin
classifier.
• Support vectors are the most useful data points.
Support Vectors:
• Data points closest to the classification line are called support vectors.
• These are the most critical points for defining the boundary.
• Two Important Arguments:
• The margin should be as large as possible.
SVM-Image2
Support Vectors Only Matter Post-Training:
After training, only support vectors are needed for classification.
This leads to efficient storage and computation.
Classifier Equation:
𝑦=𝑤𝑥+𝑏
y=w⋅x+b
A positive value → ‘+’ class, negative value → ‘o’ class.
No-Man’s Land Inclusion:
Instead of just checking sign, we also check if
∣w⋅x+b∣<M
Such points fall within the margin and are considered ambiguous.
svm cont..
Linear Separability
Linear separability refers to the ability to separate data points of different classes using a straight line
(in 2D), plane (in 3D), or hyperplane (in higher dimensions).
Linear Separability
Linear Separability
Linear Separability
• If you add multiple neurons, each neuron learns its own line.
• These lines divide the input space into different regions.
• By combining the outputs of multiple neurons, the network can:
Create complex, non-linear decision boundaries
• Accurately separate classes that are not linearly separable
Linear separability
• A perceptron draws a straight line to separate classes.

• If this line exists → linear separability.

• If not, use multiple neurons or move to multi-layer networks (like

MLPs).

• This is the foundation of deep learning: combining many neurons to

learn complex patterns.
• You cannot draw a straight line that separates the 0s from the 1s in a 2D plane.
• In the plot shown, crosses (for output 0) and circles (for output 1) cannot be divided with a straight
line.
Why Perceptron Fails on XOR
• A single-layer perceptron can only solve problems that are linearly separable.

• When run on the XOR data, the perceptron:

• Does not converge (doesn’t settle on correct weights)

• Cycles between two incorrect solutions

• So even for this basic problem, the simple perceptron fails.

Historical Insight: Minsky and Papert
In their famous book "Perceptrons" (1969), Marvin Minsky and Seymour Papert:
Proved that perceptrons cannot solve XOR.
This led to a decline in neural network research for nearly two decades.
Solution:
• Use More Neurons or Layers
To solve XOR and more complex tasks:
• Add more neurons
• Use multiple layers (i.e., move to multi-layer neural networks or deep learning)
• This adds complexity to the model but allows it to learn non-linear decision boundaries.
Training Challenge
• Adding more neurons/layers makes training:

• More powerful, but

• Harder — requires more data, computation, and optimization techniques.

Summary:
• XOR is a classic example of a problem that’s not linearly separable.

• Perceptrons cannot solve XOR because they can only find linear decision boundaries.

• This limitation led to key advancements in multi-layer neural networks, which are the
foundation of modern deep learning.
KNN(K-Nearest Neighbours)
K-Nearest Neighbors (KNN) is a supervised machine learning algorithm generally used for
classification but can also be used for regression tasks. It works by finding the "k" closest data points
(neighbors) to a given input and makes a predictions based on the majority class (for classification) or
the average value (for regression). Since KNN makes no assumptions about the underlying data
distribution it makes it a non-parametric and instance-based learning method.
KNN cont...
K-Nearest Neighbors is also called as a lazy learner algorithm because it
does not learn from the training set immediately instead it stores the
dataset and at the time of classification it performs an action on the
dataset.
KNN cont...
The new point is classified as Category 2 because most of its closest neighbors are blue squares.
KNN assigns the category based on the majority of nearby points. The image shows how KNN
predicts the category of a new data point based on its closest neighbours.

The red diamonds represent Category 1 and the blue squares represent Category 2.
The new data point checks its closest neighbors (circled points).
Since the majority of its closest neighbors are blue squares (Category 2) KNN predicts the new data
point belongs to Category 2.
KNN works by using proximity and majority voting to make predictions.
What is 'K' in K Nearest Neighbour?
• In the k-Nearest Neighbours algorithm k is just a number that tells the algorithm
how many nearby points or neighbors to look at when it makes a decision.

• Example: Imagine you're deciding which fruit it is based on its shape and size.
You compare it to fruits you already know.

• If k = 3, the algorithm looks at the 3 closest fruits to the new one.

• If 2 of those 3 fruits are apples and 1 is a banana, the algorithm says the new fruit
is an apple because most of its neighbors are apples.
How to choose the value of k for KNN Algorithm?
• The value of k in KNN decides how many neighbors the algorithm
looks at when making a prediction.
• Choosing the right k is important for good results.
• If the data has lots of noise or outliers, using a larger k can make the
predictions more stable.
• But if k is too large the model may become too simple and miss
important patterns and this is called underfitting.
• So k should be picked carefully based on the data.
 KNN Algorithm Steps
• Load the dataset
• Choose the number of neighbors (K)
• Calculate the distance between the new point and all points in the training dataset
• Most commonly used: Euclidean distance
• Sort the distances and select the K nearest neighbors
• Count the class labels among the K neighbors
• Predict the majority class (classification) or average (regression)
• Return the predicted result
Example: Classifying a Fruit
 knn example
Step 1: Convert Categorical Data
Let’s encode:
Smooth = 0
Rough = 1
So the new fruit is: (160, 1)
knn example cont...
 Remarks on K-NEAREST Neighbours Algorithm
• Distance-weighted KNN is highly effective and widely used in real-world problems.
• It is robust to noisy training data and works well with a large dataset.
• By averaging or weighting the nearest neighbors, KNN can reduce the influence of noisy points.
Inductive Bias of KNN
• KNN assumes that instances close in Euclidean space have similar classifications.
• The model relies on proximity-based similarity for predictions.
 Practical Issues in KNN
All Attributes Considered:
KNN calculates distance using all features, regardless of their relevance.
This is unlike methods like decision trees that select only useful attributes.
Curse of Dimensionality:
With many irrelevant features, distance measures can become inaccurate.
This can degrade KNN’s performance as dimensionality increases.
Solutions:
Weight features differently based on importance (e.g., stretch or shrink axes).
Use cross-validation to determine how much to adjust each axis.
A more drastic fix is to remove irrelevant attributes entirely.
Memory and Computation:
KNN is a lazy learner: it doesn't learn a model during training.
It does all computation at query time, which can be slow without efficient memory indexing.
Naive Bayes classifiers are supervised machine learning algorithms used for
classification tasks, based on Bayes’ Theorem to find probabilities.
The main idea behind the Naive Bayes classifier is to use Bayes’ Theorem to
classify data based on the probabilities of different classes given the features
of the data. It is used mostly in high-dimensional text classification
• The Naive Bayes Classifier is a simple probabilistic classifier and it has very
few number of parameters which are used to build the ML models that can
predict at a faster speed than other classification algorithms.

• It is a probabilistic classifier because it assumes that one feature in the model

is independent of existence of another feature. In other words, each feature
contributes to the predictions with no relation between each other.

• Naïve Bayes Algorithm is used in spam filtration, Sentimental analysis,

classifying articles and many more.
 Why it is Called Naive Bayes?
It is named as "Naive" because it assumes the presence of one feature does not affect other features. The
"Bayes" part of the name refers to its basis in Bayes’ Theorem.
Consider a fictional dataset that describes the weather conditions for playing a game of golf. Given the
weather conditions, each tuple classifies the conditions as fit(“Yes”) or unfit(“No”) for playing golf.
Here is a tabular representation of our dataset.
Example
Introduction to Bayes' Theorem
Introduction to Bayes' Theorem
Naive Bayes Working

1. Terminology
Consider a classification problem (like predicting if someone plays golf based on weather). Then:

This represents:
What is the probability that someone will not play golf given that the weather
is Rainy, Hot, High humidity, and No wind?
 2. The Naive Assumption

The "naive" in Naive Bayes comes from the assumption that all features are independent given the
class. That is:
3. Constructing the Naive Bayes Classifier
We compute the posterior for each class ‘y’ and choose the class with
the highest probability:
 Example: Weather Dataset
Let’s take a dataset used for predicting if golf is played based on:
Outlook: Sunny, Rainy, Overcast
Temperature: Hot, Mild, Cool
Humidity: High, Normal
Wind: True, False
Pre-computation from Dataset
Calculate Posterior Probabilities
Normalize Probabilities

Final Prediction
Naive Bayes for Continuous Features
Example-2
Spam Detection
Let’s say we want to classify whether an email is Spam or Not Spam based on two words: "free" and "win".
Result:
Since 0.25 > 0, the email is classified as Spam.
Types of Naive Bayes Model
There are three types of Naive Bayes Model :

1. Gaussian Naive Bayes

In Gaussian Naive Bayes, continuous values associated with each feature are assumed to be distributed according to
a Gaussian distribution. A Gaussian distribution is also called Normal distribution When plotted, it gives a bell
shaped curve which is symmetric about the mean of the feature values as shown below:

2. Multinomial Naive Bayes

Multinomial Naive Bayesis used when features represent the frequency of terms (such as word counts) in a
document. It is commonly applied in text classification, where term frequencies are important.

3. Bernoulli Naive Bayes

Bernoulli Naive Bayes deals with binary features, where each feature indicates whether a word appears or not in a
document. It is suited for scenarios where the presence or absence of terms is more relevant than their frequency.
Both models are widely used in document classification tasks
Advantages of Naive Bayes Classifier
• Easy to implement and computationally efficient.
• Effective in cases with a large number of features.
• Performs well even with limited training data.
• It performs well in the presence of categorical features.
• For numerical features data is assumed to come from normal
distributions
Disadvantages of Naive Bayes Classifier
• Assumes that features are independent, which may not always hold in real-world
data.
• Can be influenced by irrelevant attributes.
• May assign zero probability to unseen events, leading to poor generalization.
Applications of Naive Bayes Classifier
Spam Email Filtering: Classifies emails as spam or non-spam based on features.
Text Classification: Used in sentiment analysis, document categorization, and
topic classification.
Medical Diagnosis: Helps in predicting the likelihood of a disease based on
symptoms.
Credit Scoring: Evaluates creditworthiness of individuals for loan approval.
Weather Prediction: Classifies weather conditions based on various factors.
 Learning with Trees
Binary Tree is a non-linear and hierarchical data structure where each node has at most two children referred to as
the left child and the right child. The topmost node in a binary tree is called the root, and the bottom-most nodes
are called leaves.

Advantages of binary tree

Decision tree example
ID3
Types of Regression
Types of Regression
Types of Regression
 Perceptron
• The Perceptron is one of the simplest artificial neural network architectures, introduced by Frank
Rosenblatt in 1957. It is primarily used for binary classification.
• At that time, traditional methods like Statistical Machine Learning and Conventional Programming
were commonly used for predictions.
• Despite being one of the simplest forms of artificial neural networks, the Perceptron model proved to
be highly effective in solving specific classification problems, laying the groundwork for
advancements in AI and machine learning.
• Perceptron is a type of neural network that performs binary classification that maps input features to
an output decision, usually classifying data into one of two categories, such as 0 or 1.
• Perceptron consists of a single layer of input nodes that are fully connected to a layer of output nodes.
It is particularly good at learning linearly separable patterns.
• It utilizes a variation of artificial neurons called Threshold Logic Units (TLU), which were first
introduced by McCulloch and Walter Pitts in the 1940s. This foundational model has played a crucial
role in the development of more advanced neural networks and machine learning algorithms.
Perceptron
Perceptron Algorithm
perceptron example
perceptron example
Types of Perceptron
Single-Layer Perceptron is a type of perceptron is limited to learning
linearly separable patterns. It is effective for tasks where the data can
be divided into distinct categories through a straight line. While
powerful in its simplicity, it struggles with more complex problems
where the relationship between inputs and outputs is non-linear.
Multi-Layer Perceptron possess enhanced processing capabilities as
they consist of two or more layers, adept at handling more complex
patterns and relationships within the data.
MLP(Multi Layer Perceptron)
CART
• CART( Classification And Regression Trees) is a variation of the decision tree algorithm. It can
handle both classification and regression tasks.
• Scikit-Learn uses the Classification And Regression Tree (CART) algorithm to train Decision
Trees (also called “growing” trees).
• CART was first produced by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone
in 1984.
• CART(Classification And Regression Tree) for Decision Tree
• CART is a predictive algorithm used in Machine learning and it explains how the target variable's
values can be predicted based on other matters.
• It is a decision tree where each fork is split into a predictor variable and each node has a prediction
for the target variable at the end.
CART
The term CART serves as a generic term for the following categories of decision trees:
Classification Trees: The tree is used to determine which "class" the target variable is most likely to
fall into when it is continuous.
Regression trees: These are used to predict a continuous variable's value.
In the decision tree, nodes are split into sub-nodes based on a threshold value of an attribute.
The root node is taken as the training set and is split into two by considering the best attribute and
threshold value.
Further, the subsets are also split using the same logic. This continues till the last pure sub-set is
found in the tree or the maximum number of leaves possible in that growing tree.
CART Algorithm
Classification and Regression Trees (CART) is a decision tree algorithm that is used for both
classification and regression tasks. It is a supervised learning algorithm that learns from labelled data to
predict unseen data.
Tree structure: CART builds a tree-like structure consisting of nodes and branches. The nodes
represent different decision points, and the branches represent the possible outcomes of those decisions.
The leaf nodes in the tree contain a predicted class label or value for the target variable.
Splitting criteria: CART uses a greedy approach to split the data at each node. It evaluates all possible
splits and selects the one that best reduces the impurity of the resulting subsets. For classification tasks,
CART uses Gini impurity as the splitting criterion. The lower the Gini impurity, the more pure the
subset is. For regression tasks, CART uses residual reduction as the splitting criterion. The lower the
residual reduction, the better the fit of the model to the data.
Pruning: To prevent overfitting of the data, pruning is a technique used to remove the nodes that
contribute little to the model accuracy. Cost complexity pruning and information gain pruning are two
popular pruning techniques. Cost complexity pruning involves calculating the cost of each node and
removing nodes that have a negative cost. Information gain pruning involves calculating the
information gain of each node and removing nodes that have a low information gain.
How does CART algorithm works
The CART algorithm works via the following process:
• The best-split point of each input is obtained.
• Based on the best-split points of each input in Step 1, the new “best” split point is identified.
• Split the chosen input according to the “best” split point.
• Continue splitting until a stopping rule is satisfied or no further desirable splitting is available.
CART
CART algorithm uses Gini Impurity to split the dataset into a decision tree .It does that by
searching for the best homogeneity for the sub nodes, with the help of the Gini index criterion.
Gini index/Gini impurity
The Gini index is a metric for the classification tasks in CART. It stores the sum of squared
probabilities of each class. It computes the degree of probability of a specific variable that is
wrongly being classified when chosen randomly and a variation of the Gini coefficient. It works on
categorical variables, provides outcomes either “successful” or “failure” and hence conducts binary
splitting only.
The degree of the Gini index varies from 0 to 1,
• Where 0 depicts that all the elements are allied to a certain class, or only one class exists there.
• Gini index close to 1 means a high level of impurity, where each class contains a very small
fraction of elements, and
• A value of 1-1/n occurs when the elements are uniformly distributed into n classes and each class
has an equal probability of 1/n. For example, with two classes, the Gini impurity is 1 - 1/2 = 0.5.
CART

CART for Classification

• A classification tree is an algorithm where the target variable is categorical. The

algorithm is then used to identify the "Class" within which the target variable is most
likely to fall. Classification trees are used when the dataset needs to be split into classes
that belong to the response variable(like yes or no)
• For classification in decision tree learning algorithm that creates a tree-like structure to
predict class labels. The tree consists of nodes, which represent different decision points,
and branches, which represent the possible result of those decisions. Predicted class
labels are present at each leaf node of the tree.
How Does CART for Classification Work?
CART for classification works by recursively splitting the training data into smaller and
smaller subsets based on certain criteria. The goal is to split the data in a way that
minimizes the impurity within each subset. Impurity is a measure of how mixed up the
data is in a particular subset. For classification tasks, CART uses Gini impurity

Gini Impurity- Gini impurity measures the probability of misclassifying a random

instance from a subset labeled according to the majority class. Lower Gini impurity
means more purity of the subset.
Splitting Criteria- The CART algorithm evaluates all potential splits at every node and
chooses the one that best decreases the Gini impurity of the resultant subsets. This process
continues until a stopping criterion is reached, like a maximum tree depth or a minimum
number of instances in a leaf node.
CART for Regression
A Regression tree is an algorithm where the target variable is continuous and the tree is used to
predict its value. Regression trees are used when the response variable is continuous. For example,
if the response variable is the temperature of the day.
CART for regression is a decision tree learning method that creates a tree-like structure to predict
continuous target variables. The tree consists of nodes that represent different decision points and
branches that represent the possible outcomes of those decisions. Predicted values for the target
variable are stored in each leaf node of the tree.
How Does CART works for Regression?
Regression CART works by splitting the training data recursively into smaller subsets based on
specific criteria. The objective is to split the data in a way that minimizes the residual reduction in
each subset.
Residual Reduction- Residual reduction is a measure of how much the average squared difference
between the predicted values and the actual values for the target variable is reduced by splitting the
subset. The lower the residual reduction, the better the model fits the data.
Splitting Criteria- CART evaluates every possible split at each node and selects the one that
results in the greatest reduction of residual error in the resulting subsets. This process is repeated
until a stopping criterion is met, such as reaching the maximum tree depth or having too few
instances in a leaf node.
POPULAR CART-BASED ALGORITHMS
CART (Classification and Regression Trees): The original algorithm that
uses binary splits to build decision trees.
C4.5 and C5.0: Extensions of CART that allow for multiway splits and
handle categorical variables more effectively.
Random Forests: Ensemble methods that use multiple decision trees
(often CART) to improve predictive performance and reduce overfitting.
Gradient Boosting Machines (GBM): Boosting algorithms that also use
decision trees (often CART) as base learners, sequentially improving
model performance.
Advantages of CART
• Results are simplistic.
• Classification and regression trees are Nonparametric and Nonlinear.
• Classification and regression trees implicitly perform feature selection.
• Outliers have no meaningful effect on CART.
• It requires minimal supervision and produces easy-to-understand models.
Limitations of CART
Overfitting.
High Variance.
low bias.
the tree structure may be unstable.
Applications of the CART algorithm
• For quick Data insights.
• In Blood Donors Classification.
• For environmental and ecological data.
• In the financial sectors.
Frequently asked Question
What is CART (classification and regression tree)?
• CART is a decision tree algorithm that can be used for both classification and regression tasks. It
works by recursively partitioning the data into smaller and smaller subsets based on certain criteria.
The goal is to create a tree structure that can accurately predict the target variable for new data points.

What is a regression tree in machine learning?

A regression tree is a type of decision tree that is used to predict continuous target variables. It works by
partitioning the data into smaller and smaller subsets based on certain criteria, and then predicting the
average value of the target variable within each subset.

What is the difference between a regression tree and a classification tree?

A regression tree is used to predict continuous target variables, while a classification tree is used to
predict categorical target variables. Regression trees predict the average value of the target variable
within each subset, while classification trees predict the most likely class for each data point.
What is the difference between cart and decision tree?
• CART is a specific implementation of the decision tree algorithm.
There are other decision tree algorithms, such as ID3 and C4.5, that
have different splitting criteria and pruning techniques.

What is the main difference between classification and regression?

• Classification is the task of assigning a category to an instance, while
regression is the task of predicting a continuous value. For example,
classification could be used to predict whether an email is spam or
not spam, while regression could be used to predict the price of a
house based on its size, location, and amenities.