Unit 3

Classification

Classification
Classification is a supervised learning method in which the computer learns from past data
and then predicts a category (class) for new data.

✔ Classification → Predicts categories (Yes/No, Male/Female, Spam/Not Spam)

✔ Regression → Predicts numbers (price, marks, temperature)

In classification, we give the computer many past examples where the correct answer (class)
is already known.
The computer learns patterns from these examples and creates rules.

Later, when we give new data, the computer uses those rules to predict the correct class.

Example: Email Spam Detection

Training Data (Past)

We give the computer past emails marked as:

• Spam
• Not Spam

For example:

Email Text Class

"You won 1 lakh!" Spam

"Free vacation offer" Spam

"Meeting at 5 PM" Not Spam

"College assignment attached" Not Spam

The computer studies this data and learns rules like:

• If email contains "free", "win", "offer" → it is probably Spam

• If email contains meeting, assignment → it is probably Not Spam
Prediction (Future Data)
Now we give a new email:

➡“Free recharge coupon for you!”

The computer applies the learned rules and predicts:

✔ Spam

This is classification!

10.1 Classification Problems

A classification problem means we want to predict a category (class) for a new item, based
on patterns learned from past data.

We have:

✔ A dataset with many observations (rows of data)

✔ Each observation has

• Explanatory attributes (also called predictive variables)

• One target attribute (also called label/class) that we want to predict

The explanatory attributes can be:

• Numbers (age, marks, weight)

• Categories (gender, city, subject)

The target class is always categorical (Yes/No, Male/Female, Pass/Fail, Good/Bad).

The dataset contains explanatory attributes (predictive variables) and one target attribute
(class).
If the target has 2 classes, it is binary classification.
If it has more than 2 classes, it is multiclass classification.
The model finds patterns in the explanatory variables and creates classification rules to
predict the class of new examples.
Example:
Predicting whether a student will Pass or Fail based on hours studied and attendance.
Types of Classification

1. Binary Classification (2 classes only)

Examples:

• Spam or Not Spam

• Pass or Fail
• Fraud or Not Fraud
• Cancer or No Cancer

2. Multiclass Classification (more than 2 classes)

Examples:

• Classifying fruits → Apple, Mango, Banana

• Predicting grades → A, B, C, D
• Identifying animal type → Dog, Cat, Cow, Horse

Example 10.1 – Retention in the mobile phone industry. Example 5.2 on the analysis of
customer loyalty in the mobile phone industry is a binary classification problem in which the
target attribute takes the value 1 if a customer has discontinued service and 0 otherwise. The
features of each customer, described in Table 5.3, represent the predictive attributes. The
purpose of a classification model is to derive general rules from the examples contained in
the dataset and to apply these rules in order to assign the class to new instances for which the
target value is unknown.
In this way, the classification model may prove useful in identifying those customers who are
likely to discontinue service, and therefore to drive a retention marketing campaign.

This is a binary classification problem because there are only two possible classes:

• 1 = Customer has discontinued the service (churned)

• 0 = Customer is still using the service (not churned)

What do we want to do?

We want to predict whether a new customer will discontinue the service or continue using it.

How do we do it?

We use past data of customers.

This database has information like:

• Age
• Monthly bill
• Internet usage
• Customer complaints
 • Number of months with company
• Payment method
• Offers availed, etc.

These are called predictive attributes (or features).

Example

Imagine your dataset has these customers:

Customer Monthly Bill Complaints Months With Company Has Discontinued (Target)

A ₹599 3 5 months 1 (left the service)

B ₹299 0 24 months 0 (still using)

C ₹499 2 8 months 1 (left the service)

D ₹799 0 36 months 0 (still using)

What does the classification model do?

It studies this data and creates simple rules like:

• If complaints > 2 AND months < 6 → customer may discontinue (class 1)

• If months > 24 AND complaints = 0 → customer will not discontinue (class 0)

These rules help the company identify customers who are at high risk of leaving and provide
special offers to retain them.

Example 10.2 – Segmentation of customers phoning a call center.

Many services and manufacturing companies nowadays have a call center that their
customers may call to request information or report problems. In order to size the staff and
the activities of a call center and to verify the quality of the services offered, it is useful to
classify customers based on the number of calls made to the call center. The target attribute
may be obtained through a proper discretization of the numerical variable indicating the
number of calls, setting for example: class 0 ≡ no calls, class 1 ≡ 1 call, class 2 ≡ from 2 to 4
calls, class 4 ≡ more than 4 calls. Again predictive attributes are provided by the features of
the customers. Hence, the segmentation of the customers with respect to the number of calls
made to the call center is a multicategory classification problem.

This is a multicategory classification problem, because customers are divided into more
than two classes.

Target attribute (class) based on number of calls:

• Class 0 → No calls
 • Class 1 → 1 call
• Class 2 → 2 to 4 calls
• Class 3 → More than 4 calls

What is the purpose?

To understand customer behaviour based on how many times they call the call center.

Companies can use this to:

• Check service quality

• Identify problematic customers
• Predict staff requirements for handling calls

Example

Suppose you have this dataset:

Customer City Age Type of Plan Income Number of Calls Class

A Mumbai 25 Prepaid 25k 0 Class 0

B Pune 40 Postpaid 40k 1 Class 1

C Delhi 32 Prepaid 30k 3 Class 2

D Nagpur 29 Postpaid 60k 7 Class 3

What does the classification model do?

It finds patterns like:

• Young prepaid users call more often (Class 2 or 3)

• Postpaid users with high income call less (Class 0 or 1)

These patterns help the company:

• Improve call center services

• Provide self-service options
• Assign staff according to call volume

Flow of a Classification Problem

A classification system has three main parts:
 1. Generator
2. Supervisor
3. Classification Algorithm

1. Generator (Source of Data)

The generator is like a machine that produces examples/data.

It gives us input values (also called feature vectors x) such as:

• Age
• Salary
• Number of calls
• Internet usage
• Test marks
• Temperature
• Colour, etc.

These data points come from an unknown real-world process, so we don’t know the exact
probability of how they are generated.
This is written as:

Px(x) → probability distribution of the input data (unknown).

Example

Generator gives you a student’s marks in different subjects:

x = (Math = 80, Science = 65, English = 70)

You only know the marks, not how they were generated.

2. Supervisor (Gives the Correct Class)

The supervisor tells us the correct class/label for each example.

This is usually a teacher, expert, or existing database.

The supervisor uses an unknown probability:

Py|x(y|x) → probability of class y given the input x.

Example

Using the marks above, the supervisor may classify the student as:

• “Pass” (1)
• “Fail” (0)
So, the supervisor gives the correct answer for each input.

Example:
x = (80, 65, 70) → Supervisor says “Pass”

3. Classification Algorithm (Learns the Rule)

The classification algorithm takes:

• Inputs (from the generator)

• Correct answers (from the supervisor)

and learns a rule to classify future data.

This rule is a function called:

(from the hypothesis space F)

The algorithm tries to minimize error using a loss function.

Example

After learning many examples:

The algorithm may produce a rule like:

• If average marks > 40 → “Pass”

• Else → “Fail”

This rule is used to predict new student results.

Flow Diagram

Generator → produces input x

Supervisor → gives correct class y

Classifier → learns a rule f* to map x → y

Example: Email Spam Detection

Generator

Produces email features like:

• Words inside the mail

• Sender address
• Attachment type
• Email length

So x = (features of email)

Supervisor

Labels emails as:

• Spam (1)
• Not spam (0)

Classifier

Learns rules like:

• If email contains “win money”, “lottery” → Spam

• Else → Not spam
Phases of Classification:

A classification model learns in 3 steps:

1. Training Phase

2. Test Phase

3. Prediction Phase

1. Training Phase (Learning the Rules)

• In this phase, the model is given some examples whose class/label is already
known.

• This part of the dataset is called the Training Set (T).

• The algorithm studies these examples and learns patterns or rules.

Example

Suppose you want a model to detect whether a customer will leave a mobile company
(“Yes” or “No”).

Training data example:

Customer Age Monthly Bill Complaints Left Company (Target)

25 300 5 Yes

40 500 0 No

The algorithm learns rules like:

• If complaints > 3 → Customer may leave

• If bill is high and complaints are low → Customer stays

This is the training phase — the model is learning.

2. Test Phase (Checking Accuracy)

• After learning, the model is tested on new examples that it has never seen before.
 • This part of the dataset is called the Test Set (V = D – T).

• We already know the correct answers for the test set.

• We compare:

Predicted Class vs Actual Class

This helps to calculate the accuracy of the model.

Simple Example

Test data:

Age Monthly Bill Complaints Actual: Left?

30 350 4 Yes

Model Prediction: Yes

If prediction = actual → correct.

If not → incorrect.

To avoid fake accuracy, the training set must not include the test set. They should be
separate.

3. Prediction Phase

• This is the final and most important phase.

• The model is now used to classify new, future data.

• These new observations do not have a known target class.

• The model applies the rules learned during the training phase.

Simple Example

New customer details:

Age Monthly Bill Complaints

22 250 6

The model predicts:

This customer is likely to leave.

This is the prediction phase — using the model in the real world.

Taxonomy of Classification Models – Simple Explanation

"Taxonomy" means classification or grouping.

Classification models can be grouped into four main categories:

1. Heuristic Models

2. Separation Models

3. Regression Models

4. Probabilistic Models

1. Heuristic Models

These models use simple, easy-to-understand rules to classify data.

These are simple rule-based models like KNN and decision trees.

They use intuitive methods such as distance and if–else rules.

Methods:

• Nearest Neighbor Method (KNN)

• Classification Trees

• KNN:
“If you are similar to your neighbors, you belong to their group.”
Example:
If most neighbors near you are "Sports shoes buyers", you are predicted as a "Sports
shoes buyer".

• Decision Tree:
This model works like a “question-answer” tree.
Example:

o Does customer have many complaints? → Yes → Likely to leave

o No? → Likely to stay

These methods are easy, fast, and intuitive, like using common sense.
2. Separation Models (Models that separate data into regions)

These models try to divide the data space into different regions where each region
represents a class.

These models divide data into regions using boundaries.

Methods:

• Perceptron

• Neural Networks

• Support Vector Machines (SVM)

• Discriminant Analysis

These models draw boundaries to separate different classes.

Example:
To separate emails into Spam and Not Spam, SVM may draw a line or curve between them.

Think of it like:

Blue points on one side

Green points on the other side
A boundary (line/curve) divides them.

If a new point appears, its side decides its class.

3. Regression Models

These models assume there is a mathematical relationship between input attributes and
the target class. Logistic regression is used for binary classification.

Method:

• Logistic Regression (for 0/1, Yes/No cases)

These models calculate probabilities, like:

• “What is the probability a student will pass the exam?”

• “What is the probability a customer will buy the product?”

If probability > 0.5 → Predict "Yes"

Else → Predict "No"
Example:
A logistic regression model predicts:

A customer has 80% probability of buying the product → Predict Buy.

4. Probabilistic Models (Use probability theory)

These models estimate probabilities of each class using Bayes' theorem.

Methods:

• Naive Bayes

• Bayesian Networks

These models answer:

“Based on given data, which class is more probable?”

Example: Email classification

Naive Bayes checks the probability:

• Probability(email is SPAM | words inside email)

If SPAM probability is higher → classify as SPAM.

Evaluation of Classification Models

When we build a classification model, we must check how good the model is. To do this, we
evaluate it using different criteria:

1. Accuracy

• Accuracy means how correctly the model predicts the class of new data.

• If a model gives more correct predictions, it has high accuracy.

• We compare different models using their accuracy and select the one with the best
performance.
Example:
A model predicts whether an email is Spam or Not Spam.
If out of 100 test emails, it predicts 90 correctly → Accuracy = 90%

2. Speed

Speed means how fast a classification model learns and makes predictions.

• Some models take less time to train and are good for large datasets.

• Sometimes we train the model using a small portion of the data (random sampling)
to reduce training time.

• A good classification method should also:

o Work even when some data is missing

o Handle outliers (unusual values)

o Give similar accuracy even if training data changes a little

→ This is called robustness.

3. Scalability

• Scalability means the model’s ability to handle very large datasets.

• A scalable model should still work well even when the amount of data increases a
lot.

Example:
A model that works with 1,000 records should also work with 1 million records without
becoming too slow.

4. Interpretability

• Interpretability means how easily humans can understand the model’s rules.

• If the goal is not just prediction but also explaining how decisions are made, the
model should be simple and clear.

• Experts or users should be able to understand how the model is making decisions.
Example:
A decision tree is easy to understand, but a neural network is difficult to explain.

10.2.1 Holdout Method

The Holdout Method is the simplest way to check how good a classification model is.

How it works:

1. You have m total observations (your full dataset D).

2. You divide D into two separate groups:

o Training set (T) → used to train the model

o Test set (V) → used to check accuracy

These two sets must be disjoint (no repeated data).

How we choose T and V

• We randomly pick t observations for training (T).

• The remaining v = m – t observations form the test set (V).

• Generally:

o Training set = 50% to 67% (1/2 to 2/3)

o Test set = remaining data

Accuracy Calculation

After training the model on T, we test it on V.

The accuracy obtained from V is written as accA(V).

Disadvantage of Holdout Method

Because the test set V is chosen randomly:

• The accuracy value may be higher or lower depending on which data happened to go into V.

• So, accuracy is not always reliable from a single split.

Therefore, more advanced methods are used.

10.2.2 Repeated Random Sampling

Repeated Random Sampling is an improvement over the holdout method.

How it works:

Instead of doing the holdout split once, we do it multiple times.

1. Repeat the following r times:

o Randomly choose a training set Tk of size t

o Remaining data forms test set Vk

o Train the model on Tk

o Test it on Vk

o Record accuracy accA(Vk)

2. After r repetitions, calculate the average accuracy:

𝑟
1
𝑎𝑐𝑐𝐴 = ∑ 𝑎𝑐𝑐𝐴(𝑉𝑘 )
𝑟
𝑘=1

This average gives a more reliable estimate.

Advantages

• More accurate than the basic holdout method.

• Reduces the impact of a “bad” or “unlucky” train-test split.

Disadvantages

• There is no control over how many times each observation appears in training or test sets.

• An outlier may appear too often in training/test sets and affect the result.

• More computationally expensive (because repeated many times).

10.2.3 Cross-Validation

Cross-validation is a method used to evaluate a classification model more accurately.

It improves over the Holdout and Repeated Random Sampling methods.

Main Idea of Cross-Validation

• The dataset D is divided into r equal parts (called folds).

 • Every observation appears:

o exactly once in a test set

o r − 1 times in training sets

This makes the evaluation fair and balanced.

How Cross-Validation Works

1. Divide dataset D into r disjoint (non-overlapping) subsets:

L₁, L₂, ..., Lᵣ

2. Perform r iterations:

o In iteration k:

▪ Use Lₖ as the test set Vₖ

▪ Use all other subsets as the training set Tₖ

Mathematically,

𝑉𝑘 = 𝐿𝑘
𝑇𝑘 = ⋃ 𝐿𝑙
𝑙≠𝑘

3. Train and test the classifier r times.

4. Compute the average accuracy of all r tests:

𝑟
1
𝑎𝑐𝑐𝐴 = ∑ 𝑎𝑐𝑐𝐴(𝑉𝑘 )
𝑟
𝑘=1

This gives a more reliable estimate of accuracy.

Example: Tenfold Cross-Validation (r = 10)

This is one of the most popular methods.

• Split data into 10 equal parts: L₁, L₂, …, L₁₀

• Perform 10 rounds:

o Round 1 → Test on L₁, Train on L₂–L₁₀

 o Round 2 → Test on L₂, Train on L₁ + L₃–L₁₀

o …

o Round 10 → Test on L₁₀, Train on L₁–L₉

Finally, average all 10 accuracy values.

This is shown in Figure 10.3.

Special Case: Leave-One-Out Cross-Validation (LOOCV)

Set r = m, where m = total number of observations.

• Each test set has only 1 observation.

• Training uses m − 1 observations.

• You repeat this m times (once for each observation).

✔ Advantage:

• Uses maximum training data

• Very accurate estimate of model performance

✖ Disadvantage:

• Very slow (requires m trainings)

Stratified Cross-Validation (Very Important!)

When classes are imbalanced, we must ensure that each fold has the same class proportion as the
whole dataset.

Example:
If in full data:

• 20% customers churn (class = 1)

• 80% customers stay (class = 0)

Then each fold Lₖ should also have 20% churners.

We achieve this by stratified random sampling.

This prevents biased accuracy results.

10.2.4 Confusion Matrices

1. What is a Confusion Matrix?

A Confusion Matrix is a table used to evaluate the performance of a classification model.

It compares:

• Actual class values (real results)

• Predicted class values (model results)

It helps us understand how many predictions are correct and how many are wrong, and what type
of errors the model is making.

2. Confusion Matrix for Binary Classification

For binary classification (Yes/No, 1/0, Positive/Negative), the confusion matrix is a 2 × 2 table.

Structure

Actual \ Predicted Positive Negative

Positive True Positive (TP) False Negative (FN)

Negative False Positive (FP) True Negative (TN)

3. Meaning of Each Term (Very Important)

1. True Positive (TP)

• Model predicts Positive

• Actual value is Positive

• Correct prediction

Example:
Patient has a disease → model says disease present

2. True Negative (TN)

• Model predicts Negative

• Actual value is Negative

 • Correct prediction

Example:
Patient is healthy → model says healthy

3. False Positive (FP)

• Model predicts Positive

• Actual value is Negative

• Wrong prediction

• Also called Type-I Error

Example:
Patient is healthy → model says disease present

4. False Negative (FN)

• Model predicts Negative

• Actual value is Positive

• Wrong prediction

• Also called Type-II Error

Example:
Patient has disease → model says healthy

4. Numerical Example

Problem

A disease prediction model tested on 100 patients

Actual \ Predicted Disease (Yes) No Disease

Disease (Yes) 40 10

No Disease 5 45

So:

• TP = 40
 • FN = 10

• FP = 5

• TN = 45

5. Measures Derived from Confusion Matrix

1. Accuracy

Definition

Percentage of correct predictions.

Formula

𝑇𝑃 + 𝑇𝑁
𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 =
𝑇𝑃 + 𝑇𝑁 + 𝐹𝑃 + 𝐹𝑁

Calculation

40 + 45
𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 = = 0.85 = 85%
100

Limitation:
Accuracy can be misleading when data is imbalanced.

2. Error Rate

Definition

Percentage of wrong predictions.

Formula

𝐹𝑃 + 𝐹𝑁
𝐸𝑟𝑟𝑜𝑟 𝑅𝑎𝑡𝑒 =
𝑇𝑜𝑡𝑎𝑙

Calculation

5 + 10
𝐸𝑟𝑟𝑜𝑟 = = 15%
100
3. Precision

Definition

Out of all predicted positives, how many are actually positive?

Formula

𝑇𝑃
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =
𝑇𝑃 + 𝐹𝑃

Calculation

40
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = = 0.89 = 89%
40 + 5

Important when false positives are costly

(Spam detection, fraud alerts)

4. Recall (Sensitivity / True Positive Rate)

Definition

Out of all actual positives, how many did the model correctly detect?

Formula

𝑇𝑃
𝑅𝑒𝑐𝑎𝑙𝑙 =
𝑇𝑃 + 𝐹𝑁

Calculation

40
𝑅𝑒𝑐𝑎𝑙𝑙 = = 0.80 = 80%
40 + 10

Important when missing a positive is dangerous

(Disease detection, fraud detection)

5. Specificity (True Negative Rate)

Definition

Out of all actual negatives, how many are correctly identified?

Formula
 𝑇𝑁
𝑆𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 =
𝑇𝑁 + 𝐹𝑃

Calculation

45
𝑆𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 = = 0.90 = 90%
45 + 5

Important in medical screening

6. False Positive Rate (FPR)

Formula

𝐹𝑃
𝐹𝑃𝑅 =
𝐹𝑃 + 𝑇𝑁

Calculation

5
𝐹𝑃𝑅 = = 10%
50

7. False Negative Rate (FNR)

Formula

𝐹𝑁
𝐹𝑁𝑅 =
𝐹𝑁 + 𝑇𝑃

Calculation

10
𝐹𝑁𝑅 = = 20%
50

8. F1-Score

Definition

Harmonic mean of Precision and Recall

Formula
 2 × 𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 × 𝑅𝑒𝑐𝑎𝑙𝑙
𝐹1 =
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 + 𝑅𝑒𝑐𝑎𝑙𝑙

Calculation

2 × 0.89 × 0.80
𝐹1 = ≈ 0.84
0.89 + 0.80

Best when class imbalance exists

ROC Curve Charts

What is an ROC Curve?

ROC (Receiver Operating Characteristic) curve is a graph used to check how good a classification
model is.
It helps us:

• Visually measure the accuracy of a classifier

• Compare different classification models

• Understand the trade-off between correct and incorrect predictions

Why Do We Use ROC Curves?

Sometimes accuracy alone is misleading, especially when:

• One class is very small (like disease detection or customer churn)

• We want to identify important cases (positive class)

ROC curve gives a better evaluation of model performance.

Axes of ROC Curve

An ROC curve is a 2-D graph:

Axis Meaning

X-axis False Positive Rate (FP rate)

Axis Meaning

Y-axis True Positive Rate (TP rate)

True Positive (TP)

Correctly predicted positive cases

Example: Patient has disease and model predicts disease

False Positive (FP)

Incorrectly predicted positive cases

Example: Patient is healthy but model predicts disease

Important Points on ROC Curve

(0, 1) – Ideal Classifier

• No false positives

• All true positives detected

• Perfect model

(0, 0)

• Classifier predicts negative for all cases

• Misses all positives

(1, 1)

• Classifier predicts positive for all cases

• Many false alarms

Trade-Off Concept

• Increasing True Positives usually increases False Positives

• ROC curve shows this trade-off visually

Example: Medical Diagnosis

Problem

Predict whether a patient has a disease.

• Positive class = Has disease

 • Negative class = Healthy

Model Behavior

• If model is strict → fewer false positives but may miss sick patients

• If model is lenient → more sick patients detected but more false alarms

Each setting gives a different point on the ROC curve.

ROC Curve Interpretation

• Curve closer to top-left corner → Better model

• Curve near diagonal → Random guessing

• Higher curve → Higher accuracy

AUC (Area Under Curve)

• AUC measures the overall performance of a classifier

• Value ranges from 0 to 1

AUC Value Meaning

1.0 Perfect classifier

0.9 Excellent

0.7 Good

0.5 Random guessing

Higher AUC = Better classifier

Classification Trees

What is a Classification Tree?

A classification tree is a popular machine learning method used in data mining to classify data into
different groups or classes.

It works like a flowchart:

• Start at the top (root)

• Ask questions based on data features

• Move down branches

• End at a final decision (class label)

Classification trees are widely used because:

• They are easy to understand

• They are fast to compute

• They work well even if some data is missing

• They handle outliers properly

• They give clear rules that humans can easily interpret

How Does a Classification Tree Work?

• The tree is built during the training phase

• Data is split step-by-step using a top-down approach. This method is called Top-Down
Induction of Decision Trees

• At each step, data is divided into smaller groups

Important Parts of a Classification Tree

1. Root Node

• The top node of the tree

• Contains the complete dataset

• It is divided into smaller groups

2. Branching

• Data is split into two or more child nodes

• Each branch represents a condition

3. Splitting Rule (Separating Rule)

• A rule used to divide data at each node

• Example:

o Age ≤ 45 or Age > 45

4. Leaf Node

• The final node

• Gives the classification result

• No further splitting

Classification Rule

• The path from the root node to a leaf node

• Forms a simple IF–THEN rule

• Example:
IF age ≤ 45 AND residence = north THEN class = Yes

Types of Classification Trees

1. Binary Trees

• Each node has only two branches

• Example:

o Yes / No

o True / False

2. Multi-Split Trees

• A node can have more than two branches

• Useful for attributes with many values

• Example:

o Area of residence → North, South, Center, Islands

3. Univariate Trees

• Splitting is based on only one attribute at a time

• Example:
 o Age

o Area

o Authorized communication

Types of Attribute Splits

1. Binary Attribute

• Two possible values

• Example:

o Authorized communication → Yes / No

2. Nominal (Categorical) Attribute

• More than two categories

• Example:

o Area → North, South, Center, Islands

3. Numerical Attribute

• Numbers

• Example:

o Age ≤ 45 or Age > 45

Stopping Criteria

At each node, the algorithm checks whether to:

• Continue splitting OR

• Stop and make it a leaf node

Stopping happens when:

• All data belongs to one class

• Data is too small

• Tree becomes too complex

Pruning Criteria

Pruning helps reduce tree size and improve accuracy.

Types of Pruning:

1. Pre-pruning

o Stops tree growth early

o Prevents over-complex trees

2. Post-pruning

o Removes unnecessary branches

o Done after the tree is fully built

Neural Networks

Neural networks are computer models inspired by the human brain.

Just like the brain has neurons that send and receive signals, a neural network has artificial neurons
that process information.

Neural networks are used for:

• Classification (Yes/No, Pass/Fail, Spam/Not Spam)

• Regression (predicting continuous values like price, temperature)

Example:

• Predict whether an email is spam or not

• Predict house prices

• Recognize faces or handwriting

Neural networks are computer models that learn patterns directly from data, without needing
fixed or pre-written rules. They work in a way similar to the human brain.

These networks are built from several key components:

1. Neurons

• Neurons are the basic building blocks of a neural network.

• Each neuron:

o Receives input data

o Applies a threshold

o Uses an activation function to produce output

2. Connections

• Neurons are connected to each other through connections.

• These connections help pass information from one neuron to another.

 3. Weights and Biases

• Weights decide how important an input is.

• Bias helps the neuron adjust its output.

• Together, weights and biases control the behavior of the network.

4. Propagation Functions

• These functions move data through the network:

o From input layer

o Through hidden layers

o To output layer

• They help in processing information step by step.

5. Learning Rule

• The learning rule tells the network how to learn.

• It adjusts weights and biases based on errors.

• With training, the network becomes more accurate.

Layers in Neural Network Architecture

1. Input Layer: This is where the network receives its input data. Each input neuron in the layer
corresponds to a feature in the input data.

2. Hidden Layers: These layers perform most of the computational heavy lifting. A neural
network can have one or multiple hidden layers. Each layer consists of units (neurons) that
transform the inputs into something that the output layer can use.
 3. Output Layer: The final layer produces the output of the model. The format of these outputs
varies depending on the specific task like classification, regression.

Neural Network Structure

Once we decide the mathematical model of a neuron, the next step is to connect neurons together
to form a neural network.

There are two main types of neural networks based on how neurons are connected.

1. Feed-Forward Neural Networks

• In a feed-forward network, information flows only in one direction.

• Data moves:
Input layer → Hidden layer(s) → Output layer

• There are no loops or feedback connections.

• Because of this, it forms a directed acyclic graph.

Layered Structure

• Neurons are arranged in layers.

• Each neuron receives input only from the previous layer.

• These networks are simple and widely used.

Single-Layer Feed-Forward Neural Network (Perceptron)

• Also called a Perceptron Network

• Inputs are connected directly to output neurons

• There is no hidden layer

• Suitable for simple classification problems

Example:

• A perceptron network with:

o Two input neurons

o Two output neurons

2. Recurrent Neural Networks (RNN)

• In a recurrent network, output is fed back as input.

 • This creates a loop in the network.

• The network can remember past information.

• Useful for:

o Time-series data

o Speech recognition

o Sequence prediction

Multilayer Feed-Forward Neural Networks

• Also called Multi-Layer Neural Networks

• Inputs pass through one or more hidden layers before reaching the output.

• Hidden layers help the network:

o Learn complex patterns

o Solve non-linear problems

Support Vector Machine

A Support Vector Machine (SVM) is a machine learning algorithm used for

classification and regression. This finds the best line (or hyperplane) to
separate data into groups, maximizing the distance between the closest points
(support vectors) of each group. It can handle complex data using kernels to
transform it into higher dimensions. In short, SVM helps classify data
effectively.

Support Vector Machine (SVM)

1. Maximizes the Margin:

SVM focuses on finding the decision boundary that maximizes the
margin (the distance between the boundary and the closest data points
of each class). This makes it more robust to new data.

2. Handles Non-Linear Data:

SVM can handle non-linear data using the “kernel trick,” which
transforms the data into a higher-dimensional space where it becomes
easier to separate.
 3. Effective in High Dimensions:
SVM works well even when the number of features (dimensions) is much
larger than the number of samples, making it suitable for complex
datasets.

4. Robust to Overfitting:
By focusing on the points closest to the boundary (support vectors), SVM
is less likely to overfit, especially in smaller datasets.

5. Requires Tuning:
SVM requires careful tuning of parameters (like the choice of kernel and
regularization) to achieve optimal performance, which can be time-
consuming.

How Does Support Vector Machine Algorithm Work?

SVM is defined such that it is defined in terms of the support vectors only,
we don’t have to worry about other observations since the margin is made
using the points which are closest to the hyperplane (support vectors),
whereas in logistic regression the classifier is defined over all the points.
Hence SVM enjoys some natural speed-ups.

Let’s understand the working of SVM using an example. Suppose we have a

dataset that has two classes (green and blue). We want to classify that the new

data point as either blue or green.

To classify these points, we can have many decision boundaries, but the question is which is the best
and how do we find it?

NOTE: Since we are plotting the data points in a 2-dimensional graph we call this decision boundary
a straight line but if we have more dimensions, we call this decision boundary a “hyperplane”

The best hyperplane is that plane that has the maximum distance from both the classes, and this is
the main aim of SVM. This is done by finding different hyperplanes which classify the labels in the
best way then it will choose the one which is farthest from the data points or the one which has a
maximum margin.

Advantages of Support Vector Machine

1. Works well with complex data: SVM is great for datasets where the separation between
categories is not clear. It can handle both linear and non-linear data effectively.

2. Effective in high-dimensional spaces: SVM performs well even when there are more
features (dimensions) than samples, making it useful for tasks like text classification or
image recognition.

3. Avoids overfitting: SVM focuses on finding the best decision boundary (margin) between
classes, which helps in reducing the risk of overfitting, especially in high-dimensional data.

4. Versatile with kernels: By using different kernel functions (like linear, polynomial, or radial
basis function), SVM can adapt to various types of data and solve complex problems.
 5. Robust to outliers: SVM is less affected by outliers because it focuses on the support vectors
(data points closest to the margin), which helps in creating a more generalized model.

Disadvantages of Support Vector Machine

1. Slow with large datasets: SVM can be computationally expensive and slow to train,
especially when the dataset is very large.

2. Difficult to tune: Choosing the right kernel and parameters (like C and gamma) can be tricky
and often requires a lot of trial and error.

3. Not suitable for noisy data: If the dataset has too many overlapping classes or noise, SVM
may struggle to perform well because it tries to find a perfect separation.

4. Hard to interpret: Unlike some other algorithms, SVM models are not easy to interpret or
explain, especially when using non-linear kernels.

5. Memory-intensive: SVM requires storing the support vectors, which can take up a lot of
memory, making it less efficient for very large datasets.
 Clustering

Clustering is an unsupervised machine learning technique that groups similar data points together
into clusters based on their characteristics, without using any labeled data. The objective is to ensure
that data points within the same cluster are more similar to each other than to those in different
clusters, enabling the discovery of natural groupings and hidden patterns in complex datasets.

• Goal: Discover the natural grouping or structure in unlabeled data without

predefined categories.

• How: Data points are assigned to clusters based on similarity or distance measures.

• Similarity Measures: Can include Euclidean distance, cosine similarity or other

metrics depending on data type and clustering method.

• Output: Each group is assigned a cluster ID, representing shared characteristics within the
cluster.

Example:-

Customer Segmentation

Customers are categorized by using clustering algorithms according to their purchasing behavior or
interests to develop focused marketing campaigns.

Imagine you have 10M customers, and you want to develop customized or focused marketing
campaigns. It is unlikely that you will develop 10M marketing campaigns, so what do we do? We
could use clustering to group 10M customers into 25 clusters and then design 25 marketing
campaigns instead of 10M.
Types of Clustering Methods

Clustering methods can be classified on the basis of how they form clusters,

1. Centroid-based Clustering (Partitioning Methods)

Centroid-based clustering organizes data points around central prototypes called centroids, where
each cluster is represented by the mean (or medoid) of its members. The number of clusters is
specified in advance and the algorithm allocates points to the nearest centroid, making this
technique efficient for spherical and similarly sized clusters but sensitive to outliers and initialization.

Algorithms:

• K-means: Iteratively assigns points to nearest centroid and recalculates centroids to

minimize intra-cluster variance.

• K-medoids: Similar to K-means but uses actual data points (medoids) as centers, robust to
outliers.

Pros:

• Fast and scalable for large datasets.

• Simple to implement and interpret.

Cons:

• Requires pre-knowledge of kk.

• Sensitive to initialization and outliers.

• Not suitable for non-spherical clusters.

2. Density-based Clustering (Model-based Methods)

Density-based clustering defines clusters as contiguous regions of high data density separated by
areas of lower density. This approach can identify clusters of arbitrary shapes, handles noise well
and does not require predefining the number of clusters, though its effectiveness depends on
chosen density parameters.

Algorithms:

• DBSCAN (Density-Based Spatial Clustering of Applications with Noise): Groups points with
sufficient neighbors; labels sparse points as noise.

• OPTICS (Ordering Points To Identify Clustering Structure): Extends DBSCAN to handle varying
densities.

Pros:

• Handles clusters of varying shapes and sizes.

• Does not require cluster count upfront.

• Effective in noisy datasets.

Cons:

• Difficult to choose parameters like epsilon and min points.

• Less effective for varying density clusters (except OPTICS).

3. Connectivity-based Clustering (Hierarchical Clustering)

Connectivity-based (or hierarchical) clustering builds nested groupings of data by evaluating how
data points are connected to their neighbors. It creates a dendrogram a tree-like structure that
reflects relationships at various granularity levels and does not require specifying cluster numbers in
advance, but can be computationally intensive.

Approaches:

• Agglomerative (Bottom-up): Start with each point as a cluster; iteratively merge closest
clusters.

• Divisive (Top-down): Start with one cluster; iteratively split into smaller clusters.

Pros:

• Provides a full hierarchy, easy to visualize.

• No need to specify number of clusters upfront.

Cons:

• Computationally intensive for large datasets.

• Merging/splitting decisions are irreversible.

4. Distribution-based Clustering
Distribution-based clustering assumes data is generated from a mixture of probability distributions,
such as Gaussian distributions and assigns points to clusters based on statistical likelihood. This
method supports clusters with flexible shapes and overlaps, but usually requires specifying the
number of distributions.

Algorithm:

• Gaussian Mixture Model (GMM): Fits data as a weighted mixture of Gaussian distributions;
assigns data points based on likelihood.

Pros:

• Flexible cluster shapes.

• Provides probabilistic memberships.

• Suitable for overlapping clusters.

Cons:

• Requires specifying number of components.

• Computationally more expensive.

• Sensitive to initialization.

Partition methods

K-means Clustering Algorithm

• Given a dataset D of m observations, each represented by a vector in n-dimensional space,

partition methods construct a subdivision of D into a collection of non-empty subsets C = {C1,C2,

. . .,CK}, where K ≤ m. In general, the number K of clusters is predetermined and assigned as an

input to partition algorithms.

• K-means algorithm

a) During the initialization phase, K observations are arbitrarily chosen in D as the centroids of

the clusters.

b) Each observation is iteratively assigned to the cluster whose centroid is the most similar to

the observation, in the sense that it minimizes the distance from the record.

c) If no observation is assigned to a different cluster with respect to the previous iteration, the
algorithm stops.

d) For each cluster, the new centroid is computed as the mean of the values of the observations

belonging to the cluster, and then the algorithm returns to step 2.

• K-medoids algorithm

o The K-medoids algorithm, also known as partitioning around medoids, is a variant of the

K-means method. It is based on the use of medoids instead of the means of the

observations belonging to each cluster, with the purpose of mitigating the sensitivity of

the partitions generated with respect to the extreme values in the dataset.

o Given a cluster Ch, a medoid uh is the most central observation, in a sense that will be

formally defined, among those that are assigned to Ch. Once the medoid representing

each cluster has been identified, the K-medoids algorithm proceeds like the K-means

method, using medoids instead of centroids.

o Medoids are most commonly used on data when a mean or centroid cannot be defined, such

as graphs. They are also used in contexts where the centroid is not representative of the

dataset

o similar to the k-means algorithm but works when a mean or centroid is not definable.

Hierarchical methods
• Hierarchical clustering methods are based on a tree structure. Unlike partition methods, they do

not require the number of clusters to be determined in advance. Hence, they receive as input a
dataset D containing m observations and a matrix of distances dist(xi , xk) between all pairs of

observations.

• In order to evaluate the distance between two clusters, most hierarchical algorithms resort to one

of five alternative measures: minimum distance, maximum distance, mean distance, distance

between centroids, and Ward distance.

o Minimum distance. According to the criterion of minimum distance, also called the single

linkage criterion, the dissimilarity between two clusters is given by the minimum distance

among all pairs of observations such that one belongs to the first cluster and the other to

the second cluster,

o Maximum distance. According to the criterion of maximum distance, also called the
complete linkage criterion, the dissimilarity between two clusters is given by the

maximum distance among all pairs of observations such that one belongs to the first

cluster and the other to the second cluster

o Mean distance. The mean distance criterion expresses the dissimilarity between two
clusters via the mean of the distances between all pairs of observations belonging to the

two clusters,

o Distance between centroids. The criterion based on the distance between centroids
determines the dissimilarity between two clusters through the distance between the

centroids representing the two clusters

o Ward distance. The criterion of Ward distance, based on the analysis of the variance of
the Euclidean distances between the observations

o Hierarchical methods can be subdivided into two main groups: agglomerative and
divisive methods

• Agglomerative hierarchical methods

• Agglomerative methods are bottom-up techniques in which each single observation

initially represents a distinct cluster. These clusters are then aggregated during

subsequent iterations, deriving clusters of increasingly larger cardinalities. The

algorithm is stopped when a single cluster including all the observations has been

reached.

• Agglomerative algorithm
a) In the initialization phase, each observation constitutes a cluster. The distance

between clusters therefore corresponds to the matrix D of the distances between

all pairs of observations.

b) The minimum distance between the clusters is then computed, and the two
clusters Ch and Cf with the minimum distance are merged, thus deriving a new

cluster Ce. The corresponding minimum distance dist(Ch,Cf ) originating the

merger is recorded.

c) The distance between the new cluster Ce, resulting from the merger between Ch

and Cf , and the preexisting clusters is computed.

d) If all the observations are included into a single cluster, the procedure stops.

Otherwise it is repeated from step 2.

• Divisive hierarchical methods

▪ Divisive algorithms are the opposite of agglomerative methods, in that they are

based on a top-down technique, which initially places all the observations in a

single cluster. This is then subdivided into clusters of smaller size, so that the

distances between the generated subgroups are minimized. The procedure is

repeated until clusters containing a single observation are obtained, or until an

analogous stopping condition is met.

Evaluation of clustering models

• To evaluate a clustering method it is first necessary to verify that the clusters generated

correspond to an actual regular pattern in the data. It is therefore appropriate to apply other

clustering algorithms and to compare the results obtained by different methods. In this way it is

also possible to evaluate if the number of identified clusters is robust with respect to the different

techniques applied.