Data Science Tawqeer ul Islam

Data Science Notes

1. What is Data Science?
Definition:
Data Science is an interdisciplinary field that uses scientific methods, processes,
algorithms, and systems to extract knowledge and insights from data in various forms,
both structured and unstructured. It combines domain expertise, programming skills, and
knowledge of mathematics and statistics to turn raw data into actionable insights.
Core Components:
• Statistics & Mathematics: Forms the theoretical foundation for models and analysis.
• Computer Science & Programming: Provides tools for data manipulation, storage,
and algorithm implementation (e.g., Python, R, SQL).
• Domain Expertise: Crucial for understanding the context of the data, formulating
relevant questions, and interpreting results meaningfully.
Goals of Data Science:
• Discovery: Finding hidden patterns, trends, and correlations in data.
• Prediction: Forecasting future outcomes or behaviors based on historical data.
• Prescription: Recommending actions to achieve desired outcomes.
• Automation: Developing systems that can make decisions or perform tasks based on
data.
• Insight Generation: Providing clear, understandable explanations of data-driven
findings to stakeholders.
Example: Analyzing customer purchase history (data) using statistical models and machine
learning algorithms (processes) to predict which products a customer is likely to buy next
(insight) and then using this to personalize marketing campaigns (action).

2. Applications of Data Science

Data Science has applications across numerous industries:
1. Healthcare:
o Disease Prediction & Diagnosis: Identifying patterns in patient data to predict
disease outbreaks or assist in early diagnosis (e.g., cancer detection from medical
images).
o Drug Discovery: Analyzing biological data to accelerate the development of new
drugs.
o Personalized Medicine: Tailoring treatments based on individual genetic makeup and
lifestyle.

1
Data Science Tawqeer ul Islam

o Example: Using machine learning on patient records to predict the likelihood of

hospital readmission.
2. Finance & Banking:
o Fraud Detection: Identifying unusual transaction patterns to detect fraudulent
activities.
o Algorithmic Trading: Using algorithms to make high-speed trading decisions.
o Credit Scoring & Risk Assessment: Evaluating loan applications and predicting
default risk.
o Example: Banks use data science to analyze transaction data in real-time to flag
suspicious activities.
3. E-commerce & Retail:
o Recommendation Systems: Suggesting products to customers based on their
browsing and purchase history (e.g., Amazon, Netflix).
o Customer Segmentation: Grouping customers based on behavior for targeted
marketing.
o Price Optimization: Dynamically adjusting prices based on demand, competition, and
other factors.
o Inventory Management: Predicting demand to optimize stock levels.
o Example: An e-commerce site recommending "products you might also like."
4. Transportation & Logistics:
o Route Optimization: Finding the most efficient routes for delivery vehicles (e.g.,
UPS, FedEx).
o Demand Forecasting: Predicting travel demand for airlines or ride-sharing services.
o Predictive Maintenance: Analyzing sensor data from vehicles to predict when
maintenance is needed.
o Example: Google Maps optimizing routes based on real-time traffic data.
5. Marketing & Advertising:
o Targeted Advertising: Showing ads to specific demographics or interest groups.
o Sentiment Analysis: Analyzing social media posts to understand public opinion about
a brand or product.
o Customer Churn Prediction: Identifying customers likely to stop using a service.
o Example: Facebook showing ads based on user likes and online behavior.
6. Manufacturing:
o Predictive Maintenance: Using sensor data from machinery to predict failures and
schedule maintenance.
o Quality Control: Identifying defects in products using image recognition.

2
Data Science Tawqeer ul Islam

o Supply Chain Optimization: Improving efficiency and reducing costs in the supply
chain.
o Example: A factory using sensor data to predict when a machine part will fail,
allowing for proactive replacement.
7. Social Media:
o Content Recommendation: Suggesting posts, friends, or groups.
o Fake News Detection: Identifying and flagging misinformation.
o Influence Analysis: Identifying key influencers within a network.
o Example: Twitter suggesting accounts to follow.

3. Data Lifecycle
The data lifecycle describes the sequence of stages that data goes through from its initial
generation or acquisition to its eventual archival or deletion. While variations exist, a
common framework includes:
Phases of the Data Lifecycle:
1. Data Acquisition (or Generation/Collection):
o Description: The process of gathering raw data from various sources. This is the
starting point.
o Activities: Identifying data sources, collecting data (e.g., through sensors, surveys,
web scraping, APIs, databases).
o Considerations: Data relevance, quality, volume, velocity, variety, cost of
acquisition.
o Example: Collecting Twitter data via its API for sentiment analysis; extracting sales
records from a company's CRM.
2. Data Cleaning (or Preprocessing/Preparation):
o Description: Transforming raw data into a clean, usable, and understandable
format. This is often the most time-consuming phase.
o Activities:
▪ Handling Missing Values: Imputation (mean, median, mode, regression) or
deletion.
▪ Handling Outliers: Detection (Z-score, IQR) and treatment (removal,
transformation, capping).
▪ Data Transformation: Normalization, standardization, log transformation.
▪ Data Type Conversion: Ensuring data is in the correct format (e.g., string to
numeric).
▪ Removing Duplicates: Identifying and deleting redundant records.

3
Data Science Tawqeer ul Islam

▪ Handling Inconsistent Data: Correcting typos, standardizing formats (e.g.,

"USA", "U.S.A.", "United States" to "USA").
o Goal: Improve data quality for accurate analysis.
o Example: For a customer dataset, converting all state abbreviations to a standard
2-letter format, filling missing age values with the median age.
3. Data Analysis (or Processing/Modeling):
o Description: Applying statistical techniques, machine learning algorithms, and other
analytical methods to extract insights, find patterns, and build predictive models.
o Types of Analysis:
▪ Descriptive Analysis: What happened? (e.g., mean, median, mode, standard
deviation, visualizations).
▪ Diagnostic Analysis: Why did it happen? (e.g., drill-downs, data discovery,
correlations).
▪ Predictive Analysis: What will happen? (e.g., regression, classification, time
series forecasting).
▪ Prescriptive Analysis: What should be done about it? (e.g., optimization,
simulation, A/B testing).
o Activities: Exploratory Data Analysis (EDA), feature engineering, model selection,
model training, model evaluation.
o Example: Building a logistic regression model to predict customer churn based on
their usage patterns and demographic data.
4. Data Interpretation (or Communication/Visualization):
o Description: Making sense of the analysis results and communicating them
effectively to stakeholders, often non-technical ones.
o Activities:
▪ Summarizing Findings: Creating concise summaries of key insights.
▪ Data Visualization: Using charts, graphs, dashboards (e.g., using Tableau,
Matplotlib, Seaborn) to present findings visually.
▪ Storytelling with Data: Crafting a narrative around the data to make it
compelling and actionable.
▪ Generating Reports: Documenting the process, findings, and recommendations.
o Goal: Translate complex findings into actionable business intelligence.
o Example: Presenting a bar chart showing the leading causes of customer churn and
recommending specific retention strategies to the marketing team.
5. (Often included) Data Storage & Management:
o Description: Storing data securely and efficiently throughout its lifecycle, making it
accessible for analysis and compliant with regulations.

4
Data Science Tawqeer ul Islam

o Activities: Choosing storage solutions (databases, data lakes, data warehouses),

implementing data governance policies, ensuring data security and privacy.
o Example: Storing processed customer data in a data warehouse for ongoing business
intelligence reporting.
6. (Often included) Data Archival/Destruction:
o Description: Deciding what to do with data once it's no longer actively needed.
o Activities: Archiving data for long-term retention (if required for compliance or
historical purposes) or securely destroying data that is no longer needed or legally
permitted to be kept.
o Example: Archiving old transaction records after 7 years as per financial
regulations.

4. Ethical Considerations in Data Science

Ethical considerations are paramount in data science to ensure fairness, accountability,
and respect for individuals.
1. Bias and Fairness:
o Issue: Algorithms can inherit or amplify biases present in the data or created by
the model designers. This can lead to discriminatory outcomes (e.g., biased hiring
tools, unfair loan applications).
o Types of Bias: Sampling bias, measurement bias, algorithmic bias, prejudice bias.
o Mitigation: Using diverse and representative datasets, bias detection tools,
fairness-aware machine learning algorithms, regular audits.
o Example: A facial recognition system trained primarily on one demographic group
performing poorly on other groups.
2. Privacy and Confidentiality:
o Issue: Collection, storage, and use of personal data raise significant privacy
concerns. Data breaches can expose sensitive information.
o Mitigation: Data anonymization, pseudonymization, encryption, differential
privacy, secure data storage, access controls, adhering to regulations like GDPR,
CCPA.
o Example: Ensuring customer PII (Personally Identifiable Information) is encrypted
and access is restricted.
3. Transparency and Explainability (Interpretability):
o Issue: "Black box" models (e.g., complex deep learning networks) can make
decisions that are difficult to understand or explain, making it hard to identify
errors or biases.
o Mitigation: Using simpler, interpretable models where possible (e.g., decision
trees, linear regression), developing techniques for model explanation (e.g., LIME,
SHAP), providing clear documentation.

5
Data Science Tawqeer ul Islam

o Example: A bank needing to explain to a customer why their loan application was
rejected by an AI model.
4. Accountability and Responsibility:
o Issue: Who is responsible when an AI system makes a harmful decision or error?
The developer, the user, the organization?
o Mitigation: Establishing clear lines of responsibility, robust testing and validation
processes, human oversight for critical decisions, mechanisms for redress.
o Example: Determining accountability if a self-driving car causes an accident due
to an algorithmic flaw.
5. Data Security:
o Issue: Protecting data from unauthorized access, use, disclosure, alteration, or
destruction.
o Mitigation: Implementing strong security measures (firewalls, intrusion detection
systems, encryption), regular security audits, employee training on data security
best practices.
o Example: Preventing hackers from accessing a database containing sensitive
medical records.
6. Informed Consent:
o Issue: Ensuring individuals understand how their data will be collected, used, and
shared, and that they willingly agree to it.
o Mitigation: Clear and concise privacy policies, explicit consent mechanisms,
allowing users to opt-out or control their data.
o Example: A mobile app clearly stating how location data will be used and asking
for user permission before collecting it.
7. Potential for Misuse:
o Issue: Data science tools and findings can be used for malicious purposes (e.g.,
surveillance, manipulation, spreading disinformation).
o Mitigation: Ethical guidelines for developers and practitioners, promoting
responsible innovation, public awareness and education.
o Example: Using AI to create deepfakes for spreading false information.

5. Relation to Data Mining, Machine Learning, Big Data, and Statistics

Data Science is an umbrella term that encompasses and heavily relies on these related
fields.

Feature Data Science Data Machine Big Data Statistics

Mining Learning
Primary Extract Discover Enable Manage, Collect,
Goal actionable novel, systems to process, analyze,

6
Data Science Tawqeer ul Islam

knowledge & interesting, learn from and analyze interpret,

insights from and useful data without massive, and present
data to solve patterns in explicit complex data to
complex large programming datasets draw
problems. datasets. to make that conclusions
predictions or traditional and make
decisions. tools can't inferences.
handle.
Focus End-to-end Pattern Algorithm Volume, Inference,
process: discovery, development, Velocity, hypothesis
problem association model Variety, testing,
formulation, rules, training, Veracity, experiment
data clustering, prediction, Value of al design,
acquisition, classificatio classification, data; probability,
cleaning, n within automation. infrastructu modeling
analysis, existing re and relationship
modeling, data. tools. s.
interpretation,
deployment.
Techniqu Integrates Association Supervised Distributed Hypothesis
es techniques from rule learning computing testing,
all other fields mining, (regression, (Hadoop, regression
listed here, plus clustering classification), Spark), analysis,
domain (k-means), unsupervised NoSQL ANOVA,
expertise. classificatio learning databases, time series
n (decision (clustering), stream analysis,
trees), reinforcement processing. probability
anomaly learning. distribution
detection. s.
Output Insights, Patterns, Predictive Scalable Statistical
predictions, rules, models, data models,
recommendatio segments, intelligent processing significance
ns, automated anomalies. agents, pipelines, tests,
systems, data learned large-scale confidence
products. representatio data intervals,
ns. storage and data
retrieval. summaries.
Example A team building Identifying Developing an Storing and Designing a
Role a items algorithm that processing clinical trial
recommendatio frequently predicts stock petabytes to test the
n engine for bought prices. of sensor efficacy of
Netflix, from together in data from a new drug.
data collection a IoT devices.
to deployment supermarke
and monitoring. t.
Relationship Summary:
• Data Science uses Statistics for its theoretical underpinnings and analytical
methods.

7
Data Science Tawqeer ul Islam

• Data Science employs Machine Learning algorithms to build predictive and

descriptive models.
• Data Science often involves Data Mining techniques as part of its exploratory
analysis and pattern discovery phase.
• Data Science frequently deals with Big Data, requiring specialized tools and
techniques to handle large, complex datasets.
Essentially, Data Science is the broader discipline that applies principles from these (and
other) fields to solve real-world problems using data.

6. Data Sources and Types

A. Data Sources:
Where data originates from.
1. Primary Data Sources:
o Definition: Data collected firsthand by the researcher or organization for a
specific purpose. It is original and directly sourced.
o Examples:
▪ Surveys conducted by a company to gauge customer satisfaction.
▪ Interviews conducted for qualitative research.
▪ Observations recorded during an experiment.
▪ Data collected from sensors (e.g., IoT devices).
o Pros: Specific to the need, high control over quality, up-to-date.
o Cons: Time-consuming, expensive, can be resource-intensive.
2. Secondary Data Sources:
o Definition: Data that has already been collected by someone else for a different
purpose but can be reused.
o Examples:
▪ Government census data (e.g., U.S. Census Bureau).
▪ Published research papers and journals.
▪ Publicly available datasets (e.g., Kaggle, UCI Machine Learning Repository).
▪ Company internal databases (e.g., sales records, employee data collected for
operational purposes).
▪ Websites, social media data.
o Pros: Less expensive, quicker to obtain, can provide a broader context.
o Cons: May not perfectly fit the research question, quality can be variable, data
might be outdated, potential biases.

8
Data Science Tawqeer ul Islam

3. Tertiary Data Sources: (Less common in direct data science input, more for
background)
o Definition: Collections or summaries of primary and secondary sources.
o Examples: Encyclopedias, almanacs, literature reviews, indexes.
o Use: Primarily for finding primary or secondary sources, or for general
understanding.
B. Data Types:
How data is structured and its nature.
I. Based on Structure:
1. Structured Data:
o Definition: Highly organized data that conforms to a predefined data model or
schema. Typically stored in relational databases (SQL) in tables with rows and
columns.
o Characteristics: Easily searchable, manageable, and analyzable using traditional
tools.
o Examples:
▪ Relational database tables (e.g., customer information with fields
like CustomerID, Name, Address, Email).
▪ Spreadsheets (e.g., Excel files).
▪ CSV files.
o Pros: Easy to query and analyze, mature tools available.
o Cons: Rigid schema, less flexible for evolving data needs.
2. Unstructured Data:
o Definition: Data that does not have a predefined format or organization. It's often
qualitative and does not fit neatly into rows and columns.
o Characteristics: Difficult to process and analyze using traditional methods; requires
specialized techniques like NLP, image processing.
o Examples:
▪ Text documents (e.g., emails, articles, social media posts, PDF files).
▪ Images (e.g., JPEGs, PNGs).
▪ Audio files (e.g., MP3s, WAVs).
▪ Video files (e.g., MP4s, MOVs).
o Pros: Rich source of information, highly flexible.
o Cons: Difficult and resource-intensive to process and analyze, requires advanced
tools.

9
Data Science Tawqeer ul Islam

3. Semi-structured Data:
o Definition: Data that does not conform to the rigid structure of relational databases
but contains tags or markers to separate semantic elements and enforce hierarchies
of records and fields. It has some organizational properties but is not as strictly
defined as structured data.
o Characteristics: Easier to process than unstructured data but more flexible than
structured data.
o Examples:
▪ JSON (JavaScript Object Notation) files.
▪ XML (eXtensible Markup Language) files.
▪ NoSQL databases (some types, e.g., document databases like MongoDB).
▪ Log files.
o Pros: More flexible than structured data, easier to parse than unstructured data.
o Cons: Querying can be more complex than structured data.
Comparison Table: Structured vs. Unstructured vs. Semi-structured Data

Feature Structured Data Unstructured Data Semi-structured

Data
Format Predefined schema, No predefined format Self-describing,
tabular tags/markers
Storage Relational Databases Files, NoSQL (some XML, JSON, NoSQL
(SQL) types) (some types)
Ease of Easy Difficult Moderate
Search
Analysis Straightforward with Requires advanced Requires specific
traditional tools techniques (NLP, CV) parsers
Flexibility Low High Moderate
Examples Excel sheets, SQL Text, images, audio, JSON, XML, email
databases video headers

II. Based on Nature (Measurement Scales - often associated with Statistical data types):
1. Qualitative Data (Categorical Data):
o Definition: Describes qualities or characteristics. It cannot be measured numerically
but can be categorized.
o Types:
▪ Nominal Data: Categories without any intrinsic order or ranking.
▪ Examples: Gender (Male, Female, Other), Colors (Red, Blue, Green),
Marital Status (Single, Married, Divorced).
▪ Operations: Counting, frequency, mode.

10
Data Science Tawqeer ul Islam

▪ Ordinal Data: Categories with a meaningful order or ranking, but the

differences between categories are not necessarily equal or measurable.
▪ Examples: Education Level (High School, Bachelor's, Master's, PhD),
Customer Satisfaction (Very Unsatisfied, Unsatisfied, Neutral, Satisfied,
Very Satisfied), Size (Small, Medium, Large).
▪ Operations: Counting, frequency, mode, median, rank correlation.
2. Quantitative Data (Numerical Data):
o Definition: Represents amounts or quantities that can be measured numerically.
o Types:
▪ Discrete Data: Numerical data that can only take specific, distinct values
(often integers). Usually a result of counting.
▪ Examples: Number of children in a family, number of cars sold, number of
students in a class.
▪ Continuous Data: Numerical data that can take any value within a given range.
Usually a result of measurement.
▪ Examples: Height, weight, temperature, time, income.
▪ Measurement Scales within Quantitative Data:
▪ Interval Data: Ordered data where the differences between values are
meaningful and consistent, but there is no true zero point (zero is
arbitrary). Ratios are not meaningful.
▪ Examples: Temperature in Celsius or Fahrenheit (0°C doesn't mean no
temperature), IQ scores, Calendar years (Year 0 is arbitrary).
▪ Operations: Addition, subtraction, mean, median, mode, standard
deviation.
▪ Ratio Data: Ordered data with meaningful and consistent differences
between values, AND a true zero point (zero means the absence of the
quantity). Ratios are meaningful.
▪ Examples: Height, weight, age, income, number of items,
temperature in Kelvin (0K is absolute zero).
▪ Operations: All arithmetic operations (addition, subtraction,
multiplication, division), geometric mean, coefficient of variation.

7. Data Collection Methods

The specific techniques used to gather data.
1. Surveys & Questionnaires:
o Description: Collecting data by asking a set of predefined questions to a sample of
individuals. Can be online, paper-based, or telephonic.

11
Data Science Tawqeer ul Islam

o Types:
▪ Closed-ended questions: Provide predefined answer choices (e.g., multiple-
choice, Likert scale). Easier to analyze.
▪ Open-ended questions: Allow respondents to answer in their own words.
Provide richer, qualitative insights but harder to analyze.
o Pros: Can collect data from a large sample, relatively inexpensive (especially
online), can gather both quantitative and qualitative data.
o Cons: Potential for response bias, low response rates, poorly designed questions
can lead to misleading data.
o Example: A company sending out an online survey to customers to gather feedback
on a new product.
2. Interviews:
o Description: Collecting data through direct verbal interaction with individuals.
Can be structured (predefined questions), semi-structured (guiding questions with
flexibility), or unstructured (conversational).
o Pros: Allows for in-depth information, clarification of responses, can capture non-
verbal cues.
o Cons: Time-consuming, expensive, potential for interviewer bias, results can be
hard to generalize.
o Example: Conducting one-on-one interviews with subject matter experts to
understand industry challenges.
3. Observations:
o Description: Collecting data by systematically watching and recording behaviors,
events, or characteristics in their natural setting or a controlled environment.
o Types: Participant (researcher is involved) vs. Non-participant (researcher is
detached), Covert vs. Overt.
o Pros: Provides direct information about behavior, captures context, can reveal
unstated needs.
o Cons: Potential for observer bias (Hawthorne effect if overt), can be time-
consuming, ethical concerns if covert.
o Example: A retail store observing how shoppers navigate aisles to optimize store
layout.
4. Experiments:
o Description: Collecting data by manipulating one or more independent variables
and observing the effect on a dependent variable, while controlling for other
extraneous variables.
o Key Elements: Control group, treatment group, randomization.
o Pros: Can establish cause-and-effect relationships, high level of control.

12
Data Science Tawqeer ul Islam

o Cons: Can be artificial (not reflecting real-world conditions), expensive, ethical

concerns in some cases.
o Example: A/B testing different website layouts to see which one leads to higher
conversion rates.
5. Existing Data / Secondary Data Analysis:
o Description: Using data that has already been collected by others (see Data
Sources).
o Methods: Extracting data from databases, APIs, public datasets, company records.
o Pros: Cost-effective, time-saving, access to large datasets.
o Cons: Data may not be a perfect fit, quality issues, lack of control over collection.
o Example: Analyzing publicly available government health statistics to study
disease trends.
6. Web Scraping:
o Description: Automatically extracting large amounts of data from websites using
scripts or software tools.
o Pros: Can collect vast amounts of publicly available online data.
o Cons: Ethical and legal concerns ([Link], terms of service), website structures
can change, requires technical skills.
o Example: Scraping product prices and reviews from e-commerce websites for
competitive analysis.
7. APIs (Application Programming Interfaces):
o Description: Accessing data from web services or applications through a defined
interface provided by the data owner.
o Pros: Structured data access, often real-time, more reliable and ethical than
scraping (when used as intended).
o Cons: Data availability depends on the API provider, rate limits, may require
authentication.
o Example: Using the Twitter API to collect tweets related to a specific hashtag.
8. Sensors & IoT Devices:
o Description: Collecting data automatically from physical sensors embedded in
devices or the environment.
o Pros: Real-time data, continuous monitoring, can capture data not easily
obtainable by humans.
o Cons: Can generate massive volumes of data (Big Data challenges), data quality
can be affected by sensor malfunction, privacy concerns.
o Example: Smartwatches collecting health data (heart rate, steps); industrial
sensors monitoring machine performance.

13
Data Science Tawqeer ul Islam

8. Data Cleaning and Preprocessing Techniques

This is a critical step in the data lifecycle to ensure data quality and suitability for
analysis.
Steps in Data Preprocessing
1. Handling the Missing Values
2. Data Transformation
3. Feature Engineering
4. Splitting the data into Training and Testing Sets
5. Handling the Data Imbalance
6. Removing the Duplicate Data
1. Handling Missing Data:
o Problem: Values are absent for one or more variables/observations.
o Techniques:
▪ Deletion:
▪ Listwise Deletion: Remove entire rows with any missing values. (Use if
missing data is random and a small portion of the dataset).
▪ Pairwise Deletion: For correlation/covariance, use all available data for
each pair of variables.
▪ Column Deletion: Remove entire columns if they have too many missing
values and are not critical.
▪ Imputation: Filling in missing values.
▪ Mean/Median/Mode Imputation: Replace missing numerical values with the
mean or median of the column; replace missing categorical values with the
mode.
▪ Pros: Simple, fast.
▪ Cons: Reduces variance, distorts distributions and relationships
between variables.
▪ Regression Imputation: Predict missing values using a regression model
based on other variables.
▪ Pros: More accurate than simple imputation, preserves relationships.
▪ Cons: Can be complex, assumes linear relationships.
▪ K-Nearest Neighbors (KNN) Imputation: Impute missing values using values
from the k-most similar complete records.
▪ Pros: Can handle both numerical and categorical data, non-
parametric.

14
Data Science Tawqeer ul Islam

▪ Cons: Computationally expensive for large datasets, sensitive to k.

▪ Multiple Imputation (e.g., MICE): Create multiple complete datasets by
imputing missing values multiple times, run analysis on each, and pool
results.
▪ Pros: Accounts for uncertainty in imputation, generally provides
robust results.
▪ Cons: Complex to implement and interpret.
▪ Using Algorithms that Support Missing Values: Some algorithms (e.g., certain
tree-based models like XGBoost) can handle missing values internally.
o Example: If 'Age' has a few missing values in a customer dataset, impute them with
the median age.
2. Handling Outliers:
o Problem: Data points that are significantly different from other observations. Can
be due to errors or genuine extreme values.
o Detection Techniques:
▪ Visualization: Box plots, scatter plots.
▪ Statistical Methods: Z-score (for normally distributed data, values beyond +/- 3
standard deviations), Interquartile Range (IQR) rule (values outside Q1 - 1.5IQR
or Q3 + 1.5IQR).
o Treatment Techniques:
▪ Removal: Delete outlier observations (use with caution, only if known to be
errors).
▪ Transformation: Apply mathematical transformations (e.g., log, square root) to
reduce skewness and impact of outliers.
▪ Capping/Winsorization: Replace outliers with the nearest "acceptable" value
(e.g., 95th percentile value).
▪ Imputation: Treat as missing data and impute.
▪ Separate Analysis: Analyze outliers as a distinct group if they represent a
meaningful phenomenon.
o Example: In a dataset of house prices, a price of $10 million in a neighborhood
where most houses are 300k -500k might be an outlier. If it's a data entry error,
correct it; if genuine, decide how to treat it (e.g., cap or analyze separately).
3. Data Transformation:
o Goal: Change the scale, distribution, or format of data to make it suitable for
algorithms.
o Techniques:
▪ Normalization (Min-Max Scaling): Rescales features to a fixed range, typically
[0, 1]. Formula: X_norm = (X - X_min) / (X_max - X_min).

15
Data Science Tawqeer ul Islam

▪ Use: When algorithms don't assume a specific distribution (e.g., KNN, Neural
Networks).
▪ Standardization (Z-score Normalization): Rescales features to have zero mean
and unit variance. Formula: X_std = (X - mean(X)) / std_dev(X).
▪ Use: When algorithms assume data is centered around zero and has a
standard deviation of 1 (e.g., PCA, SVM, Logistic Regression).
▪ Log Transformation: Apply log(X) to reduce right skewness and the effect of
outliers.
▪ Binning/Discretization: Convert continuous variables into categorical bins
(e.g., age groups from age).
o Example: Standardizing 'Income' and 'Age' features before applying a K-Means
clustering algorithm.
4. Encoding Categorical Data:
o Problem: Most machine learning algorithms require numerical input.
o Techniques:
▪ Label Encoding: Assigns a unique integer to each category.
▪ Use: For ordinal data where order matters (e.g., Small=0, Medium=1,
Large=2).
▪ Caution: Can mislead algorithms into assuming an ordinal relationship for
nominal data.
▪ One-Hot Encoding (Dummy Variables): Creates new binary (0/1) columns for
each category.
▪ Use: For nominal data where no order exists (e.g., Color: Red -> [1,0,0],
Green -> [0,1,0], Blue -> [0,0,1]).
▪ Caution: Can lead to high dimensionality if many unique categories (curse of
dimensionality).
▪ Frequency Encoding: Replace categories with their frequencies in the dataset.
▪ Target Encoding (Mean Encoding): Replace categories with the mean of the
target variable for that category. (Risk of overfitting, often requires
regularization).
o Example: One-hot encoding a 'City' column (London, Paris, New York) into three new
binary columns.
5. Handling Duplicate Data:
o Problem: Identical or near-identical records can skew analysis and model training.
o Techniques: Identify and remove duplicate rows. For near-duplicates (e.g., slight
variations in addresses), techniques like fuzzy matching might be needed.
o Example: Removing a customer record that appears twice with the exact same
information.

16
Data Science Tawqeer ul Islam

6. Handling Inconsistent Data & Typos:

o Problem: Different representations for the same concept (e.g., "USA", "U.S.A.",
"United States") or misspellings.
o Techniques:
▪ Standardization: Define a standard format (e.g., all state names to 2-letter
codes).
▪ String Matching/Fuzzy Logic: Identify similar strings.
▪ Manual Correction: For smaller datasets or critical fields.
o Example: Converting all entries like "NY", "NewYork", "N.Y." in a 'State' column to
"NY".
7. Feature Scaling (already covered in Data Transformation -
Normalization/Standardization):
o Ensuring features are on a similar scale is crucial for distance-based algorithms
(e.g., KNN, SVM, K-Means) and gradient descent-based algorithms (e.g., Neural
Networks, Linear Regression) to prevent features with larger values from
dominating.
8. Feature Engineering (often considered part of preprocessing or modeling):
o Description: Creating new features from existing ones to improve model
performance.
o Techniques:
▪ Combining features: e.g., creating total_rooms = bedrooms + bathrooms.
▪ Decomposing features: e.g., extracting day, month, year from a date column.
▪ Creating interaction terms: e.g., age * income.
▪ Polynomial features: e.g., age^2.
o Example: From a 'timestamp' feature, engineering new features like 'hour_of_day'
or 'day_of_week'.

17
Data Science Tawqeer ul Islam

Statistics: Mean / Median /Mode/ Variance /Standard Deviation

Mean / Median /Mode/ Variance /Standard Deviation are all very basic but very important
concept of statistics used in data science. Almost all the machine learning algorithm uses
these concepts in data preprocessing steps. These concepts are part of descriptive
statistics where we basically used to describe and understand the data for features in
Machine learning
Mean : Mean is also known as average of all the numbers in the data set which is
calculated by below equation.

Lets say we have below heights of persons.

heights=[168,170,150,160,182,140,175,191,152,150]

Median: Median is mid value in this ordered data set.

18
Data Science Tawqeer ul Islam

Arrange the data in the increasing order and then find the mid value.

If we have even number of values in the data set then median is sum of mid two numbers
divided by 2

In we have odd number in the data set like below we have 9 heights the median will be
5th number value.

19
Data Science Tawqeer ul Islam

Mode: Mode is the number which occur most often in the data set. Here 150 is occurring
twice so this is our mode.

Variance: Variance is the numerical values that describe the variability of the observations
from its arithmetic mean and denoted by sigma-squared(σ2 )
Variance measure how far individuals in the group are spread out, in the set of data from
the mean.

Where
Xi : Elements in the data set
µ : the population mean
Step 1: This formula says that take each element from dataset(population) and subtract
from mean of data set. Later sum all the values.
Step 2: Take the sum in Step 1 and divide by total number of elements.
Square in the above formula will nullify the effect of negative sign(-).

20
Data Science Tawqeer ul Islam

Standard Deviation: It is a measure of dispersion of observation within dataset relative to

their mean. It is square root of the variance and denoted by Sigma (σ) .
Standard deviation is expressed in the same unit as the values in the dataset so it measure
how much observations of the data set differs from its mean.

21
Data Science Tawqeer ul Islam

Data Visualization Techniques

Data visualization is the graphical representation of information and data. By using visual
elements like charts, graphs, and maps, data visualization tools provide an accessible way
to see and understand trends, outliers, and patterns in data. It's a crucial step in the data
science lifecycle, bridging the gap between raw data and actionable insights. Effective
visualization helps in exploratory data analysis (EDA), communicating findings, and making
data-driven decisions.
1. Histograms
• Definition: Displays numerical data distribution using bars (usually touching)
representing frequency in "bins" (ranges).
• Shows: Distribution shape (normal, skewed, bimodal), central tendency, spread,
potential outliers, frequency per bin.
• Use: For a single numerical variable, to understand its distribution.
• Read: X-axis (variable/bins), Y-axis (frequency/%), bar height (frequency). Bin
width is critical.
• Variations: Density Plot (KDE - smoothed), Frequency Polygon.
• Pros: Simple, shows distribution shape well, good for large N, identifies modes.
• Cons: Sensitive to bin width, hides intra-bin detail, not ideal for comparing
multiple groups directly.
• Example: Distribution of student exam scores.

2. Boxplots (Box and Whisker Plots)

• Definition: Displays numerical data distribution via five-number summary (min, Q1,
median, Q3, max) and highlights outliers.
• Shows: Median, spread (Interquartile Range - IQR), skewness, outliers. Excellent
for comparing distributions across groups.
• Use: Quick summary, identify outliers, compare groups, for skewed data.
• Read: Box (IQR: Q1 to Q3), line in box (median), whiskers (range, typically
1.5*IQR), individual points (outliers).
• Variations: Notched Box Plot (median confidence), Violin Plot (shows density).
• Pros: Concise summary, great for group comparison, robust to outliers, shows
skewness.
• Cons: Can hide multimodality, oversimplifies detailed distribution shape.
• Example: Comparing salary distributions across different company departments.

22
Data Science Tawqeer ul Islam

3. Scatterplots
• Definition: Uses dots to show the relationship between two numerical variables
(one on X-axis, one on Y-axis).
• Shows: Relationship type (positive, negative, none), strength, form (linear, non-
linear), clusters, outliers.
• Use: Exploring relationships between two numerical variables, identifying
correlations.
• Read: Position of dots indicates paired values. Pattern of dots reveals relationship.
• Variations: Scatterplot Matrix (all pairs), Bubble Chart (size for 3rd variable),
color/shape for categorical variable, regression line.
• Pros: Clear relationship display, identifies patterns/outliers, can encode 3rd/4th
variable.
• Cons: Overplotting with large N, correlation ≠ causation, mainly for two primary
variables.
• Example: Relationship between hours studied and exam scores.

4. Time Series Plots (Line Charts for Time)

• Definition: Displays data points over sequential time intervals (X-axis: time, Y-axis:
variable value), typically connected by lines.
• Shows: Trends (long-term change), seasonality (repeating patterns), cycles (longer
fluctuations), anomalies.
• Use: For time-ordered data, identifying temporal patterns, forecasting.
• Read: Follow the line to see how the variable changes over time.
• Variations: Multiple series, Area Chart, Seasonal Subseries Plot, ACF/PACF plots.
• Pros: Excellent for time-based patterns, intuitive, handles multiple series.
• Cons: Clutter with too many series, scale choice impacts interpretation, Y-axis
starting point can mislead.
• Example: Monthly company sales over several years.

5. Spatial Data Visualization (Maps)

• Definition: Visual representation of geographic/spatial data on maps.
• Shows: Geographic distribution, spatial patterns (clusters, hot spots), geographic
relationships, movement/flow.
• Use: When data has a location component, to answer "where" questions.

23
Data Science Tawqeer ul Islam

• Types/Techniques:
o Choropleth Maps: Areas shaded by variable value (e.g., population density
by state).
o Point Maps: Dots/symbols at coordinates representing events/features
(e.g., earthquake locations).
o Heatmaps (on Maps): Color intensity for density/magnitude in geographic
space (e.g., crime hot spots).
o Flow Maps: Lines/arrows showing movement between locations (e.g.,
migration routes).
o Contour Maps: Lines connecting points of equal value (e.g., elevation).
o Cartograms: Area distorted by a data variable (e.g., country size by
population).
• Pros: Intuitive for geo-data, powerful for spatial patterns, conveys much
information.
• Cons: Can be complex to create, choropleth issues (color choice, MAUP), map
projection distortions, overplotting.
• Example: Mapping disease cases by county to identify high-risk areas.

Visulaization in Matplotlib
Matplotlib is a powerful plotting library in Python used to create a wide variety of static,
animated, and interactive visualizations. It is especially well-known for its flexibility and
ability to produce publication-quality plots.
• Library Type: Data visualization
• Primary Module: pyplot
• Key Features:
o Supports line plots, scatter plots, bar charts, histograms, pie charts, and
more.
o Allows customization of plots, including colors, labels, and styles.
o Integrates with other Python libraries like NumPy and Pandas for data
handling.

2. Basic Usage
Matplotlib’s primary module is pyplot, usually imported as plt:

import [Link] as plt

3. Simple Plot Example
import [Link] as plt

# Basic data
x = [1, 2, 3, 4]
y = [10, 20, 25, 30]

# Create plot

24
Data Science Tawqeer ul Islam

[Link](x, y)

# Add title and labels

[Link]('Basic Plot')
[Link]('X-axis Label')
[Link]('Y-axis Label')

# Show the plot

[Link]()

4. Common Plot Types

• Line Plot: Default plot type, used to visualize trends over continuous data.

[Link](x, y)
• Scatter Plot: Useful for showing relationships between two variables.

[Link](x, y)

• Bar Chart: Used for categorical data.

[Link](x, y)

25
Data Science Tawqeer ul Islam

• Histogram: Shows the distribution of a set of data.

[Link](y, bins=10)

• Pie Chart: Represents data as proportions of a whole.

[Link]([10, 20, 30], labels=['A', 'B', 'C'])

• Box Plot: A Box Plot (a.k.a. Box-and-Whisker Plot) is used to display the distribution of a
dataset based on:
o Median (Q2)
o First Quartile (Q1, 25th percentile)
o Third Quartile (Q3, 75th percentile)
o Interquartile Range (IQR = Q3 - Q1)
o Outliers (points outside 1.5 * IQR range)
[Link](y, vert=True, patch_artist=True,
boxprops=dict(facecolor='lightblue'))

1️. Median (Q2)

• Definition: The middle value of an ordered dataset (50th percentile).

26
Data Science Tawqeer ul Islam

• How to calculate:
o If odd number of elements → Middle value.
o If even number of elements → Average of the two middle values.
• In a Box Plot: Represented by the horizontal line inside the box.
Example:
Data: [2, 4, 7, 10, 15]
Median = 7 (middle value)

2️. First Quartile (Q1, 25th percentile)

• Definition: The median of the lower half of the dataset (excluding Q2).
• Represents: The value below which 25% of the data falls.
• In a Box Plot: The lower edge of the box.
Example:
Data: [2, 4, 7, 10, 15]
Lower half: [2, 4]
Q1 = Median of [2, 4] = 3

3️. Third Quartile (Q3, 75th percentile)

• Definition: The median of the upper half of the dataset (excluding Q2).
• Represents: The value below which 75% of the data falls.
• In a Box Plot: The upper edge of the box.
Example:
Data: [2, 4, 7, 10, 15]
Upper half: [10, 15]
Q3 = Median of [10, 15] = 12.5

4️. Interquartile Range (IQR)

• Definition: The range between Q1 and Q3 (middle 50% of the data).
• Formula: IQR=Q3−Q1
• Significance: Helps detect outliers and measure data spread.
Example:
Q1 = 3, Q3 = 12.5
IQR = 12.5 - 3 = 9.5

5️. Outliers (Points Outside 1.5 * IQR Range)

• Definition: Extreme values that fall far from the rest of the data.
• Formula for Outlier Range:
o Lower Bound = Q1−1.5×IQR
o Upper Bound = Q3+1.5×IQR
• Points beyond this range are considered outliers and shown as dots in a box plot.
Example:
Q1 = 3, Q3 = 12.5, IQR = 9.5
Lower Bound = 3 - (1.5 * 9.5) = -11.25
Upper Bound = 12.5 + (1.5 * 9.5) = 26.75
Any data point < -11.25 or > 26.75 is an outlier.

Hex Bin: A Hexbin Plot (Hexagonal Binning Plot) is useful for visualizing the density of points in a
2D space.
• Instead of scatter plots, where overlapping points are hard to interpret, Hexbin groups data into
hexagonal bins.
• The color intensity represents the density (number of points in each bin).

27
Data Science Tawqeer ul Islam

5. Customization
Matplotlib allows deep customization of almost every aspect of a plot.

a. Titles, Labels, and Legends

• Title: [Link]('Title')
• X/Y Axis Labels: [Link]('X Axis'), [Link]('Y Axis')
• Legend: [Link](['Series 1', 'Series 2'])

b. Grid, Ticks, and Limits

• Grid: [Link](True)
• Ticks: Control the markers on the x and y axes.

[Link]([1, 2, 3, 4])
[Link]([10, 20, 30])
• Axis Limits: Set the range of the axes.

[Link]([0, 5])
[Link]([0, 35])
c. Line Style, Colors, and Markers
• Change line style, color, and marker:

[Link](x, y, color='red', linestyle='--', marker='o')

6. Saving Figures
Matplotlib allows saving figures to various formats, such as PNG, JPG, PDF, etc.

[Link]('[Link]')
7. Working with Multiple Figures
You can create and manage multiple figures simultaneously:

# Create figure 1
[Link](1)
[Link](x, y)

# Create figure 2
[Link](2)
[Link](y, x)

Example:
import [Link] as plt
# Basic data

28
Data Science Tawqeer ul Islam

x = [1, 2, 3, 4, 5, 6]
y = [10, 20, 25, 30, 45, 43]

# Create figure and axis

[Link](figsize=(8, 5)) # Set figure size

# Create plot with customizations

[Link](x, y, marker="o", linestyle="--", linewidth=2, markersize=8,
color="darkblue", label="Data Trend")

# Add title and labels with font styling

[Link]("Customized Line Plot", fontsize=14, fontweight="bold",
color="darkred")
[Link]("X-axis Label", fontsize=12, fontweight="bold",
color="darkgreen")
[Link]("Y-axis Label", fontsize=12, fontweight="bold",
color="darkgreen")

# Add grid with custom styling

[Link](True, linestyle=":", linewidth=0.7, alpha=0.8)

# Add x and y axis limits

[Link](0, 7)
[Link](0, 50)

# Customize tick marks

[Link](fontsize=10, fontweight="bold", color="purple",
rotation=0)
[Link](fontsize=10, fontweight="bold", color="purple")

# Add annotations
for i, txt in enumerate(y):
[Link](txt, (x[i], y[i]), textcoords="offset points",
xytext=(0, 10), ha="center", fontsize=10, color="black")

# Add legend
[Link](loc="upper left", fontsize=10, edgecolor="black")

# Show the plot

[Link]()
Customizations Added:

• Figure size

• Line style: Dashed (--), color: Dark blue, marker: Circles (o)

• Title and labels: Custom font size, color, bold styling

• Grid: Dotted (:) with transparency (alpha)

• Axis limits

• Tick styling: Custom colors and font size

29
Data Science Tawqeer ul Islam

• Annotations: Display data points on the graph

• Legend placement and styling

30
Data Science Tawqeer ul Islam

Machine Learning Fundamentals

1. Introduction to Machine Learning
• Definition: Machine Learning (ML) is a field of artificial intelligence that gives
computers the ability to learn from data without being explicitly programmed. It
focuses on building systems that can learn from experience (data) to improve
performance on a specific task.
• Core Idea: Instead of writing code with specific instructions to perform a task, you
provide an ML algorithm with data, and it builds its own logic or model to perform
the task.
• Goal: To enable machines to learn patterns, make decisions, or predictions based
on data.
• Key Aspects:
o Data: ML heavily relies on data (training data) to learn. The quality and
quantity of data are crucial.
o Model: The output of the learning process is a model, which is a
mathematical representation of the patterns learned from the data.
o Task: The specific problem the ML system is designed to solve (e.g.,
classifying images, predicting prices).
o Performance Measure: A metric used to evaluate how well the model
performs the task (e.g., accuracy, error rate).
• Applications: Spam filtering, image recognition, recommendation systems, fraud
detection, medical diagnosis, autonomous vehicles, etc.
2. Supervised vs. Unsupervised Learning
These are the two primary types of machine learning based on the nature of the data used
for training.
• Supervised Learning:
o Definition: Learning from a dataset that includes labeled examples,
meaning each data point has an associated output value (the "label" or
"target").
o Core Concept: The algorithm learns a mapping from input features (X) to
the known output labels (y).
o Goal: To predict the output label for new, unseen data points.
o Data: Pairs of (input, output) - (x, y).
o Tasks:
▪ Classification: Predicting a discrete, categorical label (e.g.,
spam/not spam, disease/no disease, image category).

31
Data Science Tawqeer ul Islam

▪ Regression: Predicting a continuous numerical value (e.g., house

price, stock price, temperature).
o Algorithm Examples: Linear Regression, Logistic Regression, Decision Trees,
Support Vector Machines, K-Nearest Neighbors (for classification and
regression), Neural Networks.
• Unsupervised Learning:
o Definition: Learning from a dataset that does not have labeled examples.
The algorithm must find patterns, structures, or relationships within the
data on its own.
o Core Concept: The algorithm explores the input data (X) to discover
inherent groupings, structures, or underlying distributions.
o Goal: To understand the data's structure or to reduce its complexity.
o Data: Only input features (x).
o Tasks:
▪ Clustering: Grouping data points into clusters based on similarity
(e.g., customer segmentation).
▪ Dimensionality Reduction: Reducing the number of features while
preserving important information (e.g., PCA).
▪ Association Rule Mining: Discovering rules that describe
relationships between variables (e.g., market basket analysis -
"people who buy milk also buy bread").
o Algorithm Examples: K-Means Clustering, Hierarchical Clustering, DBSCAN,
Principal Component Analysis (PCA), Association Rule learners (like Apriori).
3. Classification vs. Regression
These are the two main types of tasks within Supervised Learning.
• Classification:
o Definition: A supervised learning task where the goal is to predict a
discrete class label for an input data point.
o Output: A category (e.g., 'Cat', 'Dog', 'Spam', 'Not Spam', 'Type A', 'Type B').
o Types:
▪ Binary Classification: Two possible output classes (e.g., Yes/No, 0/1,
Spam/Not Spam).
▪ Multi-class Classification: More than two output classes (e.g.,
identifying digits 0-9, classifying types of animals).
▪ Multi-label Classification: Assigning multiple labels to a single
instance (e.g., an image containing both 'dog' and 'cat').
o Evaluation: Accuracy, Precision, Recall, F1-Score, Confusion Matrix,
ROC/AUC.

32
Data Science Tawqeer ul Islam

o Algorithm Examples: Logistic Regression, SVM, Decision Trees, K-NN, Naive

Bayes, Neural Networks.
• Regression:
o Definition: A supervised learning task where the goal is to predict a
continuous numerical value for an input data point.
o Output: A real number (e.g., 150000, 3.14, 98.6, 55.2).
o Evaluation: Mean Squared Error (MSE), Root Mean Squared Error (RMSE),
Mean Absolute Error (MAE), R-squared.
o Algorithm Examples: Linear Regression, Polynomial Regression, Decision
Trees (for regression), K-NN (for regression), Support Vector Regression
(SVR), Neural Networks.
4. Decision Trees
• Definition: A supervised learning algorithm that uses a tree-like structure to model
decisions and their possible consequences. It can be used for both classification
and regression tasks.
• Core Concept: The tree consists of nodes representing features, branches
representing decisions based on feature values, and leaves representing the final
predicted outcome (class or value).
• How it Works (Classification):
1. Start with the entire dataset at the root node.
2. Select the "best" feature to split the data based on a splitting criterion. The
goal is to create subsets of data that are as "pure" as possible with respect
to the class labels.
3. Create child nodes for each possible outcome of the split.
4. Recursively repeat steps 2 and 3 for each child node until a stopping
condition is met (e.g., all data points in a node belong to the same class,
maximum depth is reached, minimum number of samples per leaf).
5. Leaf nodes are assigned the majority class of the data points they contain.
6. To classify a new instance, traverse the tree from the root, following the
branches based on the instance's feature values, until a leaf node is
reached. The instance is assigned the class of that leaf node.
• Splitting Criteria (for Classification): Measure the impurity of a node or the
information gained by splitting.
o Gini Impurity: Measures how often a randomly chosen element from the set
would be incorrectly labeled if it were randomly labeled according to the
distribution of labels in the subset. A Gini impurity of 0 means the node is
pure (all data points belong to the same class).
▪ Mathematics: Gini(S) = 1 - Σ (pi)2, where pi is the proportion of
instances belonging to class i in set S.

33
Data Science Tawqeer ul Islam

▪ Gini Gain (for a split):

Gain = Gini(Parent) - Σ [(|Childi| / |Parent|) * Gini(Childi)].
Maximize Gini Gain.
o Entropy: Measures the randomness or disorder in the class labels. A pure
node has entropy 0.
▪ Mathematics:
Entropy(S) = - Σ [pi * log2(pi)],
where pi is the proportion of instances belonging to class i in set S.
(If pi = 0, pi *log2(pi) is considered 0).
▪ Information Gain (for a split):
Gain = Entropy(Parent) - Σ [(|Childi| / |Parent|) * Entropy(Childi)].
Maximize Information Gain. Information Gain is the reduction in entropy
after a split.
• How it Works (Regression): Similar tree structure, but the splitting criterion aims
to minimize the variance within each node (e.g., minimizing Mean Squared Error).
Leaf nodes store the average target value of the data points they contain.
• Advantages:
o Easy to understand and interpret (can visualize the tree).
o Requires little data preparation (no feature scaling needed).
o Can handle both numerical and categorical data.
• Disadvantages:
o Can easily overfit the training data (complex trees). Pruning is needed to
mitigate this.
o Can be unstable; small changes in data can lead to a very different tree.
o Building an optimal decision tree is NP-complete; greedy algorithms are
used (like CART or C4.5).
• Numerical Example (Gini Impurity):
o Suppose a node has 10 data points: 6 'Yes' and 4 'No'.
o p(Yes) = 6/10 = 0.6, p(No) = 4/10 = 0.4
o Gini Impurity = 1 - (0.6)2 - (0.4)2 = 1 - 0.36 - 0.16 = 1 - 0.52 = 0.48.

• Play Tennis Problem: ID3 Decision Tree Solution

1. Introduction
The "Play Tennis" problem is a classic example dataset used to illustrate concepts in
machine learning, particularly decision tree algorithms like ID3, C4.5, and CART. The goal

34
Data Science Tawqeer ul Islam

is to predict whether someone will play tennis on a given day based on four weather
attributes.
The ID3 (Iterative Dichotomiser 3) algorithm, developed by Ross Quinlan, is a fundamental
decision tree learning algorithm. It uses the concept of Information Gain to greedily select
the best attribute for splitting the data at each node of the tree.
2. The Dataset
The dataset consists of 14 instances, each representing a day. There are four input
attributes (Outlook, Temperature, Humidity, Wind) and one target attribute (Play), which
is a binary classification (Yes or No).

Day Outlook Temperature Humidity Wind Play

D1 Sunny Hot High Weak No
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Strong No
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No
Summary of the Target Variable 'Play':
• Total Instances: 14
• Play = Yes: 9 instances
• Play = No: 5 instances
3. ID3 Algorithm and Information Gain
ID3 builds the tree top-down, starting from the root node. At each node, it selects the
attribute that best splits the data into subsets that are as "pure" as possible with respect
to the class labels. "Purity" is measured using Entropy, and the reduction in entropy
achieved by splitting on an attribute is called Information Gain.
• Entropy: Measures the impurity or randomness of a set of examples. For a set S
containing instances from c classes, the entropy is:

where pi is the proportion of instances in S that belong to class i. Entropy is 0 for a

perfectly pure set (all instances belong to the same class) and maximum when classes are
equally distributed.
• Information Gain: The gain in information (reduction in entropy) achieved by
splitting a set S on an attribute A.

35
Data Science Tawqeer ul Islam

where Values(A) is the set of unique values for attribute A, Sv is the subset of S where
attribute A has value v, ∣Sv∣ is the number of instances in Sv, and ∣S∣ is the total number of
instances in S. The ID3 algorithm selects the attribute with the highest Information Gain at
each step.
4. Building the Decision Tree: Step-by-Step
We start with the entire dataset (S) at the root node.
Step 1: Calculate the Entropy of the Root Node (Entropy of the 'Play' attribute)
Total instances = 14
Play = Yes: 9
Play = No: 5
P(Yes)=9/14≈0.643
P(No)=5/14≈0.357

So, the initial impurity of the dataset is approximately 0.938 bits.

Step 2: Calculate Information Gain for each Attribute
We calculate the Information Gain for splitting on each of the four attributes (Outlook,
Temperature, Humidity, Wind).
Attribute: Outlook
Values: Sunny, Overcast, Rain
1. Outlook = Sunny:
o Instances: 5 (D1, D2, D8, D9, D11)
o Play = Yes: 2 (D9, D11)
o Play = No: 3 (D1, D2, D8)

2. Outlook = Overcast:
o Instances: 4 (D3, D7, D12, D13)
o Play = Yes: 4 (D3, D7, D12, D13)

36
Data Science Tawqeer ul Islam

o Play = No: 0

o
(Perfectly pure)
3. Outlook = Rain:
o Instances: 5 (D4, D5, D6, D10, D14)
Rain instances are D4, D5, D6, D10, D14. Among these, Yes are D4, D5 (2
instances). No are D6, D10, D14 (3 instances).
o Play = Yes: 2
o Play = No: 3

(Same as Sunny)
Now calculate the weighted average entropy for Outlook:

Calculate Gain(S, Outlook):

Attribute: Temperature
Values: Hot, Mild, Cool
1. Temperature = Hot: Instances: 4 (D1, D2, D3, D13). Play: Yes=2, No=2.

2. Entropy =
Temperature = Mild: Instances: 6 (D4, D8, D10, D11, D12, D14).
o Play: Yes=4, No=2

3. Temperature = Cool: Instances: 4 (D5, D6, D7, D9). Play: Yes=3 (D5, D7, D9), No=1
(D6).

37
Data Science Tawqeer ul Islam

Attribute: Humidity
Values: High, Normal
1. Humidity = High: Instances: 7 (D1, D2, D3, D4, D8, D12, D14). Play: Yes=3 (D3, D4,
D12), No=4 (D1, D2, D8, D14).

2. Humidity = Normal: Instances: 7. Yes: D5, D7, D9, D11, D13 (5 instances). No: D6,
D10 (2 instances).

Attribute: Wind
Values: Weak, Strong
1. Wind = Weak: Instances: 8 (D1, D3, D4, D5, D8, D9, D12, D13). Play: Yes=6 (D3, D4,
D5, D9, D12, D13), No=2 (D1, D8).

2. Wind = Strong: Instances: 6 Yes (D7, D11), No (D2, D6, D10, D14). Total 6 instances.
Yes=2, No=4.

Step 3: Select the Best Attribute for the Root Node

Compare the Information Gains:
• Gain(S, Outlook) ≈ 0.244
• Gain(S, Temperature) ≈ 0.027
• Gain(S, Humidity) ≈ 0.015
• Gain(S, Wind) ≈ 0.082
Outlook provides the highest Information Gain (0.244). Therefore, Outlook is selected as
the root node to split the data.
Step 4: Create Child Nodes and Partition the Data
The root node splits into three branches based on the values of Outlook: Sunny, Overcast,
and Rain. The dataset is partitioned accordingly:

38
Data Science Tawqeer ul Islam

• Branch: Outlook = Sunny (5 instances: D1, D2, D8, D9, D11)

• Branch: Outlook = Overcast (4 instances: D3, D7, D12, D13)
• Branch: Outlook = Rain (5 instances: D4, D5, D6, D10, D14)
Step 5: Recursively Build the Tree on Child Nodes
Now we apply the ID3 algorithm to each child node subset.
• Branch: Outlook = Overcast
o Subset: {D3, D7, D12, D13}
o Play: All 4 instances are 'Yes'.
o This subset is perfectly pure (Entropy = 0). This branch terminates in a leaf
node labeled "Yes".
• Branch: Outlook = Sunny
o Subset
SSunny : {D1, D2, D8, D9, D11} (3 No, 2 Yes)
o Entropy(SSunny) = 0.971 (calculated previously). This node is not pure.
o Remaining Attributes: Temperature, Humidity, Wind. We need to calculate
Information Gain for each on this subset.
o Data for Sunny subset:
(Sunny, Hot, High, Weak, No) - D1
(Sunny, Hot, High, Strong, No) - D2
(Sunny, Mild, High, Weak, No) - D8
(Sunny, Cool, Normal, Weak, Yes) - D9
(Sunny, Mild, Normal, Strong, Yes) - D11
o Gain on Temperature for SSunny:
▪ Hot (2 instances: D1, D2): 2 No, 0 Yes. Entropy = 0.
▪ Mild (2 instances: D8, D11): 1 No, 1 Yes. Entropy = 1.
▪ Cool (1 instance: D9): 0 No, 1 Yes. Entropy = 0.
▪ Weighted Entropy = (2/5)*0 + (2/5)*1 + (1/5)*0 = 0.4
▪ Gain(SSunny, Temp) = 0.971−0.4=0.5710.971−0.4=0.571
o Gain on Humidity for SSunny:
▪ High (3 instances: D1, D2, D8): 3 No, 0 Yes. Entropy = 0.
▪ Normal (2 instances: D9, D11): 0 No, 2 Yes. Entropy = 0.
▪ Weighted Entropy = (3/5)*0 + (2/5)*0 = 0
▪ Gain(SSunny, Humidity) = 0.971−0=0.9710.971−0=0.971
o Gain on Wind for SSunny:

39
Data Science Tawqeer ul Islam

▪ Weak (3 instances: D1, D8, D9): 2 No, 1 Yes.

▪ Strong (2 instances: D2, D11): 1 No, 1 Yes. Entropy = 1.

▪ Weighted Entropy = (3/5)*0.918 + (2/5)*1
≈0.551+0.4=0.951≈0.551+0.4=0.951
▪ Gain (SSunny, Wind) = 0.971−0.951=0.020.971−0.951=0.02
o Comparing gains for SSunny: Temp (0.571), Humidity (0.971), Wind
(0.02). Humidity has the highest gain (0.971).
o Split the Sunny branch on Humidity.
o Child nodes for Humidity: High and Normal.
▪ Humidity = High (in Sunny subset): {D1, D2, D8}. All 3 instances are
'No'. Pure. Leaf node "No".
▪ Humidity = Normal (in Sunny subset): {D9, D11}. All 2 instances are
'Yes'. Pure. Leaf node "Yes".
o The Sunny branch is now complete with leaf nodes.
• Branch: Outlook = Rain
o Subset SRain: {D4, D5, D6, D10, D14} (2 Yes, 3 No)
o Entropy(SRain) = 0.971 (calculated previously). This node is not pure.
o Remaining Attributes: Temperature, Humidity, Wind.
o Data for Rain subset:
(Rain, Mild, High, Weak, Yes) - D4
(Rain, Cool, Normal, Weak, Yes) - D5
(Rain, Cool, Normal, Strong, No) - D6
(Rain, Mild, Normal, Strong, No) - D10
(Rain, Mild, High, Strong, No) - D14
o Gain on Temperature for SRain:
▪ Mild (3 instances: D4, D10, D14): 1 Yes, 2 No.

▪ Cool (2 instances: D5, D6): 1 Yes, 1 No. Entropy = 1.

▪ Weighted Entropy = (3/5)*0.918 + (2/5)*1
≈0.551+0.4=0.951≈0.551+0.4=0.951
▪ Gain(SRain, Temp) = 0.971−0.951=0.020.971−0.951=0.02
o Gain on Humidity for SRain:
▪ High (2 instances: D4, D14): 1 Yes, 1 No. Entropy = 1.
▪ Normal (3 instances: D5, D6, D10): 1 Yes, 2 No.

40
Data Science Tawqeer ul Islam

Entropy ≈0.918≈0.918
▪ Weighted Entropy = (2/5)*1 + (3/5)*0.918
≈0.4+0.551=0.951≈0.4+0.551=0.951
▪ Gain(SRain, Humidity) = 0.971−0.951=0.020.971−0.951=0.02
o Gain on Wind for SRain:
▪ Weak (2 instances: D4, D5): 2 Yes, 0 No. Entropy = 0.
▪ Strong (3 instances: D6, D10, D14): 0 Yes, 3 No. Entropy = 0.
▪ Weighted Entropy = (2/5)*0 + (3/5)*0 = 0
▪ Gain(SRain, Wind) = 0.971−0=0.9710.971−0=0.971
o Comparing gains for
SRain : Temp (0.02), Humidity (0.02), Wind (0.971). Wind has the highest gain (0.971).
o Split the Rain branch on Wind.
o Child nodes for Wind: Weak and Strong.
▪ Wind = Weak (in Rain subset): {D4, D5}. All 2 instances are 'Yes'.
Pure. Leaf node "Yes".
▪ Wind = Strong (in Rain subset): {D6, D10, D14}. All 3 instances are
'No'. Pure. Leaf node "No".
o The Rain branch is now complete with leaf nodes.
6. The Final Decision Tree
Based on the steps above, the final ID3 decision tree for the Play Tennis problem is:

41
Data Science Tawqeer ul Islam

5. Rule Learners
• Definition: Machine learning algorithms that learn symbolic rules (often in the form
of IF-THEN statements) from data.
• Core Concept: Represent knowledge and make predictions using a set of logical
rules. These rules are typically easy for humans to understand.
• How it Works:
o From Decision Trees: Rules can be extracted directly from a trained decision tree
by traversing each path from the root to a leaf node. Each path corresponds to a
rule where the conditions are the tests at the internal nodes and the conclusion is
the class label at the leaf.
o Direct Rule Learning (e.g., Sequential Covering algorithms like Ripper, PART):
1. Learn a rule that covers a subset of the data.
2. Remove the data points covered by the rule.
3. Repeat until no or few data points remain, or a stopping criterion is met.
4. Post-process/prune the learned rules to improve performance and readability.
• Advantages:
o Highly interpretable (rules are easy to read).
o Can explicitly represent discovered patterns.
o Can handle symbolic data well.
• Disadvantages:
o Rule sets can become large and complex for high-dimensional data.
o May struggle with complex non-linear relationships compared to other methods.
• Example Problem: Learning rules to diagnose a medical condition based on
symptoms (e.g., IF (Fever is High) AND (Cough is Severe) THEN Class is Pneumonia).
• Numerical: (Rule learners primarily involve symbolic logic and counting
support/confidence, less direct numerical computation compared to other
algorithms' core mechanics). Example is more about the rule structure.
6. Linear Regression
• Definition: A supervised learning algorithm used for regression tasks. It models the
relationship between a dependent variable (target) and one or more independent
variables (features) by fitting a linear equation to the observed data.
• Core Concept: Assumes a linear relationship exists between the input features and
the target variable. The goal is to find the coefficients (weights) of this linear
equation that best fit the data.
• Mathematics:

42
Data Science Tawqeer ul Islam

o Simple Linear Regression (one feature): y = b₀ + b₁ * x₁ + ε

▪ y: dependent variable (target)
▪ x₁: independent variable (feature)
▪ b₀: intercept (bias term)
▪ b₁: coefficient (weight) for x₁
▪ ε: error term (residual)
o Multiple Linear Regression (multiple features): y = b₀ + b₁ * x₁ + b₂ * x₂ + ... + bₙ *
xₙ + ε
▪ In vector form: y = Xw + ε (where w includes the intercept b₀ and weights b₁,
..., bₙ)
o Goal: Find the weights w that minimize the difference between the predicted
values (ŷ) and the actual values (y). This difference is measured by a loss function,
commonly the Mean Squared Error (MSE).
o Loss Function (MSE): J(w) = (1/m) * Σ (yᵢ - ŷᵢ)² = (1/m) * Σ (yᵢ - (b₀ + Σ bⱼ * xᵢⱼ))²
▪ m: number of training examples
o Minimization: The weights can be found using different methods:
▪ Ordinary Least Squares (OLS): A closed-form solution that directly calculates the
weights.
▪ Mathematics (Matrix form): w = (XᵀX)⁻¹ Xᵀy
▪ Requires that XᵀX is invertible.

▪ Gradient Descent: An iterative optimization algorithm that gradually adjusts the

weights in the direction that reduces the loss function.
▪ Mathematics: w = w - α * ∇J(w)
▪ α: learning rate
▪ ∇J(w): gradient of the loss function with respect to w (vector of partial
derivatives). The partial derivative w.r.t. wj is: (2/m) * Σ (ŷᵢ - yᵢ) * xᵢⱼ

43
Data Science Tawqeer ul Islam

To update B0 and B1, we take gradients from the cost function. To find these gradients,
we take partial derivatives for B0 and B1.

• Assumptions:
o Linearity: Linear relationship between features and target.
o Independence: Observations are independent.
o Homoscedasticity: Constant variance of errors.
o Normality: Errors are normally distributed (important for statistical inference, less
critical for prediction alone).
o No Multicollinearity: Features are not highly correlated with each other.
• Advantages:
o Simple and interpretable.
o Computationally efficient.
o Provides insights into the relationships between variables (magnitude and sign of
coefficients).
• Disadvantages:

44
Data Science Tawqeer ul Islam

o Assumes linearity, which may not hold in real-world data.

o Sensitive to outliers.
o Doesn't perform well with highly non-linear data.
• Example Problem: Predicting a student's final exam score based on the number of
hours they studied.
• Numerical Example (Simple Linear Regression & MSE):
o Data points (x, y): (1, 2), (2, 4), (3, 5)
o Assume a simple model y = 1 + 1*x
o Predictions:
▪ For (1, 2): ŷ = 1 + 1*1 = 2. Error = 2 - 2 = 0. Squared Error = 0.
▪ For (2, 4): ŷ = 1 + 1*2 = 3. Error = 4 - 3 = 1. Squared Error = 1.
▪ For (3, 5): ŷ = 1 + 1*3 = 4. Error = 5 - 4 = 1. Squared Error = 1.
o MSE = (0 + 1 + 1) / 3 = 2/3 ≈ 0.67. (The goal is to find weights that minimize this
value).
7. Logistic Regression
• Definition: A supervised learning algorithm used for binary classification (though
extendable to multi-class). It models the probability that an instance belongs to a
particular class. Despite the name "regression," it's a classification algorithm.
• Core Concept: Uses a sigmoid function (or logistic function) to map the output of a
linear equation to a probability value between 0 and 1. This probability is then
used to classify the instance.

• Mathematics:
o Linear Model Output (Log-Odds): z = b₀ + b₁ * x₁ + ... + bₙ * xₙ = wᵀx (in vector
form, including bias)
o Sigmoid Function:

45
Data Science Tawqeer ul Islam

▪ This function squashes any real-valued input z to a value between 0 and 1.

o Probability Estimate: p(y=1 | x) = σ(wᵀx)
▪ The probability that the instance belongs to the positive class (y=1).
▪ p(y=0 | x) = 1 - p(y=1 | x)
o Classification Decision: If p(y=1 | x) ≥ 0.5, predict Class 1; otherwise, predict Class
0. The threshold can be adjusted.
o Goal: Find the weights w that maximize the likelihood of observing the training
data. This is equivalent to minimizing the Log Loss (also known as Binary Cross-
Entropy).
o Loss Function (Log Loss / Binary Cross-Entropy):
▪ J(w) = -(1/m) * Σ [yᵢ * log(ŷᵢ) + (1 - yᵢ) * log(1 - ŷᵢ)]
▪ yᵢ: actual label (0 or 1)
▪ ŷᵢ: predicted probability p(y=1 | xᵢ)
▪ This function heavily penalizes confident wrong predictions.
o Minimization: Typically done using Gradient Descent or other optimization
algorithms (like L-BFGS).
• Advantages:
o Simple and interpretable (coefficients indicate the influence of features on the log-
odds).
o Outputs probabilities, which can be useful.
o Computationally efficient.
o A good baseline model for classification.
• Disadvantages:
o Assumes a linear relationship between features and the log-odds of the outcome.
o May not perform well with highly non-linear relationships.
o Can be sensitive to outliers.
• Example Problem: Predicting whether a student will pass or fail an exam based on
study hours.
• Numerical Example (Sigmoid & Prediction):
o Assume model: z = -1 + 2*x (where x is hours studied)

46
Data Science Tawqeer ul Islam

o If student studies x = 0.7 hours: z = -1 + 2*0.7 = -1 + 1.4 = 0.4

o Predicted probability: p(Pass | x=0.7) = σ(0.4) = 1 / (1 + e⁻⁰.⁴) ≈ 1 / (1 + 0.67) ≈ 1 /
1.67 ≈ 0.6
o Since 0.6 > 0.5, predict Pass.
Loss Functions for Regression
• Definition: A function that quantifies the error between the predicted values (ŷ)
and the actual target values (y) in a regression task. The goal of the regression
model training is to minimize this loss function.
• Mean Squared Error (MSE):
o Definition: The average of the squared differences between the actual and
predicted values.
o Formula: MSE = (1/n) * Σ (yᵢ - ŷᵢ)²
▪ n: number of data points
▪ yᵢ: actual value for point i
▪ ŷᵢ: predicted value for point i
o Interpretation: Measures the average squared error. Squaring the errors makes
larger errors more significant than smaller ones.
o Use Case: Very common. Good for penalizing large errors.
o Sensitivity: Sensitive to outliers due to the squaring term.
• Root Mean Squared Error (RMSE):
o Definition: The square root of the MSE.
o Formula: RMSE = √[ (1/n) * Σ (yᵢ - ŷᵢ)² ] = √MSE
o Interpretation: Represents the standard deviation of the prediction errors
(residuals). It's in the same units as the target variable, making it easier to
interpret than MSE.
o Use Case: Widely used. Easier to compare with the scale of the target variable.
o Sensitivity: Still sensitive to outliers.
• Mean Absolute Error (MAE):
o Definition: The average of the absolute differences between the actual and
predicted values.
o Formula: MAE = (1/n) * Σ |yᵢ - ŷᵢ|
o Interpretation: Measures the average magnitude of errors without considering
their direction.
o Use Case: More robust to outliers than MSE/RMSE because it doesn't square the
errors. Useful when outliers should not heavily influence the error metric.
• R-squared (Coefficient of Determination):

47
Data Science Tawqeer ul Islam

o Definition: A statistical measure representing the proportion of the variance in

the dependent variable that is predictable from the independent variables.
o Formula: R² = 1 - (SSR / SST)
▪ SSR (Sum of Squared Residuals) = Σ (yᵢ - ŷᵢ)² (This is the error that the model
could not explain)
▪ SST (Total Sum of Squares) = Σ (yᵢ - ȳ)² (Total variance in the dependent
variable, where ȳ is the mean of y)

o Interpretation:
▪ Ranges typically from 0 to 1 for a linear model fitted by OLS.
▪ R² = 0 means the model explains none of the variance (prediction is no
better than predicting the mean).
▪ R² = 1 means the model explains all the variance (perfect fit).
▪ R² < 0 is possible if the model fits the data worse than simply predicting the
mean (e.g., using non-linear models or inappropriate features).
o Use Case: Provides a measure of goodness-of-fit. Indicates how well the model
fits the data compared to a baseline model that just predicts the mean.
• Numerical Example (MSE, MAE, R-squared):
o Actual y: {2, 4, 5}
o Predicted ŷ: {2.1, 3.8, 4.9}
o Mean of y (ȳ) = (2 + 4 + 5) / 3 = 11/3 ≈ 3.67

o Errors (y - ŷ): { -0.1, 0.2, 0.1}

o Squared Errors (y - ŷ)²: { 0.01, 0.04, 0.01}
o Absolute Errors |y - ŷ|: {0.1, 0.2, 0.1}
o (y - ȳ)²: { (2-3.67)², (4-3.67)², (5-3.67)² } ≈ { (-1.67)², (0.33)², (1.33)² } ≈ { 2.79,
0.11, 1.77}
o MSE = (0.01 + 0.04 + 0.01) / 3 = 0.06 / 3 = 0.02
o MAE = (0.1 + 0.2 + 0.1) / 3 = 0.4 / 3 ≈ 0.13
o SSR = 0.01 + 0.04 + 0.01 = 0.06
o SST = 2.79 + 0.11 + 1.77 = 4.67
o R² = 1 - (0.06 / 4.67) ≈ 1 - 0.0128 ≈ 0.9872 (or 98.72%) - The model explains
about 98.7% of the variance in y.

8. Nearest Neighbour Learning (k-NN)

• Definition: A simple, non-parametric, lazy supervised learning algorithm that can
be used for both classification and regression.

48
Data Science Tawqeer ul Islam

• Core Concept: An instance is classified or its value is predicted based on the

majority class or average value of its 'k' nearest neighbours in the training data.
• How it Works:
1. Store the entire training dataset. (This is why it's "lazy" - no explicit training
phase to build a model).
2. When a new, unseen data point arrives, calculate the distance between this point
and every point in the training dataset.
3. Identify the 'k' training points that are closest to the new point (its k nearest
neighbours).
4. For Classification: Assign the new point the class that is most frequent among its
k neighbours (majority vote).
5. For Regression: Assign the new point the average (or weighted average) of the
target values of its k neighbours.
• Parameters:
o k: The number of neighbours to consider. Choosing the right 'k' is important
(often determined via cross-validation). Small k is sensitive to noise; large k can
smooth out predictions but neighbours might be far away.
o Distance Metric: How to measure the distance between points. Common choices:
▪ Euclidean Distance: sqrt( Σ (xᵢ - yᵢ)² ) - standard straight-line distance.
▪ Manhattan Distance: Σ |xᵢ - yᵢ| - sum of absolute differences (taxicab
distance).
▪ Others: Minkowski, cosine similarity (for text data).
• Advantages:
o Simple to understand and implement.
o No training time (or very fast training time).
o Can learn complex decision boundaries.
o Non-parametric (makes no assumptions about the underlying data
distribution).
• Disadvantages:
o Prediction can be slow for large datasets (requires calculating distances to all
training points).
o Requires storing the entire training dataset.
o Sensitive to the scale of features (features with larger ranges can dominate
distance calculations - requires feature scaling).
o Sensitive to noisy data and outliers (especially for small k).
o Choosing the optimal 'k' can be difficult.

49
Data Science Tawqeer ul Islam

• Example Problem (Classification): Classify a new fruit (by weight and color
intensity) based on its k nearest known fruits (apple, orange, banana).
• Numerical Example (Euclidean Distance & Classification):
o Training Data: (x, y, Class) -> (1, 1, A), (2, 2, A), (5, 5, B), (6, 6, B)

x y Class
1 1 A
2 2 A
5 5 B
6 6 B

o New Point: (3, 3)

o Calculate Euclidean distances:
▪ To (1, 1): sqrt((3-1)² + (3-1)²) = sqrt(2² + 2²) = sqrt(8) ≈ 2.83
▪ To (2, 2): sqrt((3-2)² + (3-2)²) = sqrt(1² + 1²) = sqrt(2) ≈ 1.41
▪ To (5, 5): sqrt((3-5)² + (3-5)²) = sqrt((-2)² + (-2)²) = sqrt(8) ≈ 2.83
▪ To (6, 6): sqrt((3-6)² + (3-6)²) = sqrt((-3)² + (-3)²) = sqrt(18) ≈ 4.24
o If k=1: Nearest neighbour is (2, 2) with Class A. Predict A.
o If k=3: 3 nearest neighbours are (2, 2) [dist 1.41], (1, 1) [dist 2.83], (5, 5) [dist
2.83]. Two are Class A, one is Class B. Predict A (majority vote).
9. Support Vector Machines (SVM)
• Definition: A supervised learning algorithm that can be used for both classification
and regression. It's particularly effective for classification.
• Core Concept: Finds the optimal hyperplane that separates different classes in the
feature space with the largest possible margin.

• Mathematics & Concepts:

o Hyperplane: A decision boundary in the feature space. In 2D, it's a line; in
3D, it's a plane; in higher dimensions, it's a hyperplane. Equation: wᵀx + b =
0, where w is the normal vector to the hyperplane, and b is the bias.

50
Data Science Tawqeer ul Islam

o Margin: The distance between the hyperplane and the closest data points
from each class. These closest points are called Support Vectors.

o Goal (Linearly Separable Data - Hard Margin SVM): Find w and b such that
wᵀxᵢ + b ≥ +1 for data points xᵢ of class +1, and wᵀxⱼ + b ≤ -1 for data points
xⱼ of class -1. The region between wᵀx + b = +1 and wᵀx + b = -1 is the
margin. The width of the margin is 2 / ||w||. To maximize the margin, we
need to minimize ||w||² subject to the constraints. This is a convex
optimization problem.
o Goal (Non-Linearly Separable Data - Soft Margin SVM): Most real-world
data is not perfectly separable. Soft Margin SVM allows for some
misclassifications or points within the margin by introducing slack variables
(ξᵢ). The optimization problem then involves minimizing ||w||² + C * Σ ξᵢ,
where C is a regularization parameter (cost) that controls the trade-off
between maximizing the margin and minimizing misclassifications. A smaller
C allows more errors (wider margin); a larger C penalizes errors more
strictly (narrower margin).

o Kernel Trick: To handle non-linearly separable data, SVM uses kernel

functions. The kernel function calculates the dot product of data points in a
higher-dimensional "feature space" without explicitly transforming the data
into that space. This allows finding linear separators in the higher
dimension, which correspond to non-linear separators in the original
dimension.

▪ Common Kernels:
▪ Linear Kernel: K(xᵢ, xⱼ) = xᵢᵀxⱼ (original linear SVM)
▪ Polynomial Kernel: K(xᵢ, xⱼ) = (γ * xᵢᵀxⱼ + r)ᵈ

51
Data Science Tawqeer ul Islam

▪ Radial Basis Function (RBF) / Gaussian Kernel: K(xᵢ, xⱼ) = exp(-γ * ||xᵢ -
xⱼ||²) - very common, can map data into infinite dimensions. γ is a
parameter controlling the influence of single training examples.
• Advantages:
o Effective in high-dimensional spaces.
o Memory efficient, as it uses a subset of training points (support vectors) in
the decision function.
o Can handle non-linear relationships using kernels.
o Robust to outliers (due to soft margin).
• Disadvantages:
o Choice of kernel and parameters (C, γ, degree) significantly affects
performance.
o Training can be slow for large datasets (computationally intensive quadratic
programming problem).
o Difficulty in interpreting the model (especially with non-linear kernels).
o Doesn't directly provide probabilities (though extensions exist).
• Example Problem: Classifying emails as spam or not spam based on word
frequencies. Separating different types of cancer cells based on gene expression
data.
• SVM for Regression (SVR)
While SVM is commonly used for classification, it can also be used for regression. Instead of
finding a boundary between two classes, SVM in regression (called Support Vector Regression
(SVR)) tries to fit a line that predicts continuous values and stays within a certain margin of error.

Clustering
• Description: Clustering is an unsupervised machine learning task that involves
grouping a set of data points into subsets (clusters) such that points within the
same cluster are more similar to each other than to points in other clusters.
• Goal: To discover hidden patterns, structures, or natural groupings in data that
does not have predefined labels.
• Core Idea: Grouping objects based on their similarity, often measured using
distance metrics.
• Application: Customer segmentation, document analysis, image analysis, anomaly
detection.
Types of Clustering:
Different methods exist based on how they define clusters or the approach they take:
1. Partitioning Clustering (e.g., K-Means, K-Medoids):

52
Data Science Tawqeer ul Islam

o Divides data into a pre-specified number (K) of non-overlapping clusters. Each

data point belongs to exactly one cluster.
o Works by iteratively assigning points to the nearest cluster centroid and updating
centroid positions.
2. Hierarchical Clustering:
o Builds a hierarchy of clusters, represented as a tree (dendrogram).
o Agglomerative (Bottom-Up): Starts with each point as a separate cluster and
merges the closest clusters iteratively.
o Divisive (Top-Down): Starts with all points in one cluster and recursively splits
clusters.
o Does not require specifying the number of clusters beforehand (clusters are
determined by cutting the dendrogram).

53
Data Science Tawqeer ul Islam

3. Density-Based Clustering (e.g., DBSCAN, OPTICS):

o Identifies clusters as regions of high data point density separated by regions of low
density.
o Can find arbitrarily shaped clusters and is good at identifying outliers (noise
points).
o Requires parameters defining the neighbourhood size and the minimum number of
points in a dense region.

10. K-Means Clustering

• Definition: An unsupervised learning algorithm used for clustering data into a pre-
defined number of clusters, K.
• Core Concept: Partitions data points into K clusters such that each data point
belongs to the cluster with the nearest mean (centroid). The algorithm iteratively
refines the cluster assignments and centroid positions.
• Mathematics & Algorithm:
1. Initialization: Choose K, the number of clusters. Randomly initialize K
cluster centroids (μ₁, μ₂, ..., μκ). These can be random data points or
random positions in the feature space.
2. Assignment Step (E-step - Expectation): Assign each data point xᵢ to the
cluster k whose centroid μκ is closest (using a distance metric, typically
Euclidean distance).
▪ Cluster_Assignment(xᵢ) = argmin_κ ||xᵢ - μκ||²
3. Update Step (M-step - Maximization): Re-calculate the centroid of each
cluster κ as the mean of all data points assigned to that cluster.
▪ μκ = (1 / |Cκ|) * Σ_{xᵢ ∈ Cκ} xᵢ , where Cκ is the set of points
assigned to cluster κ, and |Cκ| is the number of points in cluster κ.
4. Repeat: Repeat steps 2 and 3 until the centroids no longer change
significantly, or a maximum number of iterations is reached.

54
Data Science Tawqeer ul Islam

o Goal: Minimize the within-cluster sum of squares (inertia), which is the sum
of squared distances between each point and its assigned centroid.
▪ Mathematics: Inertia = Σ_{κ=1 to K} Σ_{xᵢ ∈ Cκ} ||xᵢ - μκ||²
• Parameters:
o K: The number of clusters. This must be specified beforehand. Determining
the optimal K can be done using methods like the elbow method or
silhouette analysis.
o Initialization: The initial positions of centroids can affect the final
clustering (K-Means can converge to a local optimum). Running the
algorithm multiple times with different random initializations and choosing
the best result (lowest inertia) is common practice (e.g., K-Means++
initialization).
• Advantages:
o Relatively simple to understand and implement.
o Fast and computationally efficient, especially for large datasets (faster than
hierarchical clustering).
o Scales well to large numbers of samples.
• Disadvantages:
o Requires specifying K beforehand.
o Sensitive to initial centroid positions.
o Assumes clusters are spherical and equally sized, and have similar density.
o Sensitive to outliers.
o Can struggle with clusters of different shapes or densities, or non-convex
shapes.
• Example Problem: Segmenting customers based on purchasing behavior. Grouping
documents based on content similarity.
• Numerical Example:
o Data points (x, y): (1, 1), (1.5, 2), (3, 4), (5, 7), (3.5, 5), (4.5, 5), (3.5, 4.5)
o Let K=2.
o Assume Initial Centroids: μ₁ = (1, 1), μ₂ = (5, 7)
Given:
• Data points (P):
o P1: (1, 1)
o P2: (1.5, 2)
o P3: (3, 4)
o P4: (5, 7)
o P5: (3.5, 5)

55
Data Science Tawqeer ul Islam

o P6: (4.5, 5)
o P7: (3.5, 4.5)
• Number of clusters (K) = 2
• Initial Centroids:
o μ₁ = (1, 1)
o μ₂ = (5, 7)
We will use the Euclidean distance to measure the distance between points and centroids:
Distance = √((x₂ - x₁)² + (y₂ - y₁)²).
For simplicity in comparison, we can often use squared Euclidean distance, as it preserves
the order of distances.

Iteration 1
1. Assignment Step: Assign each data point to the nearest centroid.
• P1 (1, 1):
o Distance to μ₁ (1,1) = √((1-1)² + (1-1)²) = √(0² + 0²) = 0
o Distance to μ₂ (5,7) = √((5-1)² + (7-1)²) = √(4² + 6²) = √(16 + 36) = √52 ≈ 7.21
o P1 is closer to μ₁. Assign P1 to Cluster 1.
• P2 (1.5, 2):

o Distance to μ₁ (1,1) = √((1.5-1)² + (2-1)²) = √(0.5² + 1²) = √(0.25 + 1) = √1.25 ≈ 1.12

o Distance to μ₂ (5,7) = √((5-1.5)² + (7-2)²) = √(3.5² + 5²) = √(12.25 + 25) = √37.25 ≈
6.10
o P2 is closer to μ₁. Assign P2 to Cluster 1.
• P3 (3, 4):

o Distance to μ₁ (1,1) = √((3-1)² + (4-1)²) = √(2² + 3²) = √(4 + 9) = √13 ≈ 3.61

o Distance to μ₂ (5,7) = √((5-3)² + (7-4)²) = √(2² + 3²) = √(4 + 9) = √13 ≈ 3.61
o P3 is equidistant. By convention, we can assign it to the cluster with the lower
index. Assign P3 to Cluster 1.
• P4 (5, 7):
o Distance to μ₁ (1,1) = √((5-1)² + (7-1)²) = √(4² + 6²) = √52 ≈ 7.21
o Distance to μ₂ (5,7) = √((5-5)² + (7-7)²) = √(0² + 0²) = 0
o P4 is closer to μ₂. Assign P4 to Cluster 2.
• P5 (3.5, 5):

o Distance to μ₁ (1,1) = √((3.5-1)² + (5-1)²) = √(2.5² + 4²) = √(6.25 + 16) = √22.25 ≈

4.72
o Distance to μ₂ (5,7) = √((5-3.5)² + (7-5)²) = √(1.5² + 2²) = √(2.25 + 4) = √6.25 = 2.5
o P5 is closer to μ₂. Assign P5 to Cluster 2.
• P6 (4.5, 5):

o Distance to μ₁ (1,1) = √((4.5-1)² + (5-1)²) = √(3.5² + 4²) = √(12.25 + 16) = √28.25 ≈

5.32
o Distance to μ₂ (5,7) = √((5-4.5)² + (7-5)²) = √(0.5² + 2²) = √(0.25 + 4) = √4.25 ≈ 2.06
o P6 is closer to μ₂. Assign P6 to Cluster 2.
• P7 (3.5, 4.5):

56
Data Science Tawqeer ul Islam

o Distance to μ₁ (1,1) = √((3.5-1)² + (4.5-1)²) = √(2.5² + 3.5²) = √(6.25 + 12.25) =

√18.5 ≈ 4.30
o Distance to μ₂ (5,7) = √((5-3.5)² + (7-4.5)²) = √(1.5² + 2.5²) = √(2.25 + 6.25) = √8.5
≈ 2.92
o P7 is closer to μ₂. Assign P7 to Cluster 2.
Cluster Assignments after Iteration 1:
• Cluster 1: {P1(1,1), P2(1.5,2), P3(3,4)}
• Cluster 2: {P4(5,7), P5(3.5,5), P6(4.5,5), P7(3.5,4.5)}

2. Update Step: Recalculate the centroids based on the mean of the points in each
cluster.
• New Centroid μ₁:
o μ₁_x = (1 + 1.5 + 3) / 3 = 5.5 / 3 ≈ 1.833
o μ₁_y = (1 + 2 + 4) / 3 = 7 / 3 ≈ 2.333
o μ₁_new = (1.833, 2.333)
• New Centroid μ₂:
o μ₂_x = (5 + 3.5 + 4.5 + 3.5) / 4 = 16.5 / 4 = 4.125
o μ₂_y = (7 + 5 + 5 + 4.5) / 4 = 21.5 / 4 = 5.375
o μ₂_new = (4.125, 5.375)
The centroids have changed. We proceed to the next iteration.

57
Data Science Tawqeer ul Islam

Iteration 2
Current Centroids: μ₁ = (1.833, 2.333), μ₂ = (4.125, 5.375)
1. Assignment Step:
• P1 (1, 1):
o Dist to μ₁ = √((1-1.833)² + (1-2.333)²) = √((-0.833)² + (-1.333)²) = √(0.694 +
1.777) = √2.471 ≈ 1.57
o Dist to μ₂ = √((1-4.125)² + (1-5.375)²) = √((-3.125)² + (-4.375)²) = √(9.766 +
19.141) = √28.907 ≈ 5.38
o Assign P1 to Cluster 1.
• P2 (1.5, 2):
o Dist to μ₁ = √((1.5-1.833)² + (2-2.333)²) = √((-0.333)² + (-0.333)²) = √(0.111
+ 0.111) = √0.222 ≈ 0.47
o Dist to μ₂ = √((1.5-4.125)² + (2-5.375)²) = √((-2.625)² + (-3.375)²) = √(6.891
+ 11.391) = √18.282 ≈ 4.28
o Assign P2 to Cluster 1.
• P3 (3, 4):
o Dist to μ₁ = √((3-1.833)² + (4-2.333)²) = √((1.167)² + (1.667)²) = √(1.362 +
2.779) = √4.141 ≈ 2.03
o Dist to μ₂ = √((3-4.125)² + (4-5.375)²) = √((-1.125)² + (-1.375)²) = √(1.266 +
1.891) = √3.157 ≈ 1.78
o Assign P3 to Cluster 2. (Assignment changed from Iteration 1)
• P4 (5, 7):
o Dist to μ₁ = √((5-1.833)² + (7-2.333)²) = √((3.167)² + (4.667)²) = √(10.03 +
21.78) = √31.81 ≈ 5.64
o Dist to μ₂ = √((5-4.125)² + (7-5.375)²) = √((0.875)² + (1.625)²) = √(0.766 +
2.641) = √3.407 ≈ 1.85
o Assign P4 to Cluster 2.
• P5 (3.5, 5):
o Dist to μ₁ = √((3.5-1.833)² + (5-2.333)²) = √((1.667)² + (2.667)²) = √(2.779 +
7.113) = √9.892 ≈ 3.14
o Dist to μ₂ = √((3.5-4.125)² + (5-5.375)²) = √((-0.625)² + (-0.375)²) = √(0.391
+ 0.141) = √0.532 ≈ 0.73
o Assign P5 to Cluster 2.
• P6 (4.5, 5):
o Dist to μ₁ = √((4.5-1.833)² + (5-2.333)²) = √((2.667)² + (2.667)²) = √(7.113 +
7.113) = √14.226 ≈ 3.77
o Dist to μ₂ = √((4.5-4.125)² + (5-5.375)²) = √((0.375)² + (-0.375)²) = √(0.141 +
0.141) = √0.282 ≈ 0.53
o Assign P6 to Cluster 2.
• P7 (3.5, 4.5):
o Dist to μ₁ = √((3.5-1.833)² + (4.5-2.333)²) = √((1.667)² + (2.167)²) = √(2.779
+ 4.696) = √7.475 ≈ 2.73

58
Data Science Tawqeer ul Islam

o Dist to μ₂ = √((3.5-4.125)² + (4.5-5.375)²) = √((-0.625)² + (-0.875)²) =

√(0.391 + 0.766) = √1.157 ≈ 1.08
o Assign P7 to Cluster 2.
Cluster Assignments after Iteration 2:
• Cluster 1: {P1(1,1), P2(1.5,2)}
• Cluster 2: {P3(3,4), P4(5,7), P5(3.5,5), P6(4.5,5), P7(3.5,4.5)}
2. Update Step:
• New Centroid μ₁:
o μ₁_x = (1 + 1.5) / 2 = 2.5 / 2 = 1.25
o μ₁_y = (1 + 2) / 2 = 3 / 2 = 1.5
o μ₁_new = (1.25, 1.5)
• New Centroid μ₂:
o μ₂_x = (3 + 5 + 3.5 + 4.5 + 3.5) / 5 = 19.5 / 5 = 3.9
o μ₂_y = (4 + 7 + 5 + 5 + 4.5) / 5 = 25.5 / 5 = 5.1
o μ₂_new = (3.9, 5.1)
The centroids have changed. We proceed to the next iteration.

Iteration 3
Current Centroids: μ₁ = (1.25, 1.5), μ₂ = (3.9, 5.1)
1. Assignment Step:
• P1 (1, 1):
o Dist to μ₁ = √((1-1.25)² + (1-1.5)²) = √((-0.25)² + (-0.5)²) = √(0.0625 + 0.25)
= √0.3125 ≈ 0.56
o Dist to μ₂ = √((1-3.9)² + (1-5.1)²) = √((-2.9)² + (-4.1)²) = √(8.41 + 16.81) =
√25.22 ≈ 5.02
o Assign P1 to Cluster 1.
• P2 (1.5, 2):
o Dist to μ₁ = √((1.5-1.25)² + (2-1.5)²) = √((0.25)² + (0.5)²) = √(0.0625 + 0.25)
= √0.3125 ≈ 0.56
o Dist to μ₂ = √((1.5-3.9)² + (2-5.1)²) = √((-2.4)² + (-3.1)²) = √(5.76 + 9.61) =
√15.37 ≈ 3.92
o Assign P2 to Cluster 1.
• P3 (3, 4):
o Dist to μ₁ = √((3-1.25)² + (4-1.5)²) = √((1.75)² + (2.5)²) = √(3.0625 + 6.25) =
√9.3125 ≈ 3.05
o Dist to μ₂ = √((3-3.9)² + (4-5.1)²) = √((-0.9)² + (-1.1)²) = √(0.81 + 1.21) =
√2.02 ≈ 1.42
o Assign P3 to Cluster 2.
• P4 (5, 7):
o Dist to μ₁ = √((5-1.25)² + (7-1.5)²) = √((3.75)² + (5.5)²) = √(14.0625 + 30.25)
= √44.3125 ≈ 6.66
o Dist to μ₂ = √((5-3.9)² + (7-5.1)²) = √((1.1)² + (1.9)²) = √(1.21 + 3.61) = √4.82
≈ 2.20

59
Data Science Tawqeer ul Islam

o Assign P4 to Cluster 2.
• P5 (3.5, 5):
o Dist to μ₁ = √((3.5-1.25)² + (5-1.5)²) = √((2.25)² + (3.5)²) = √(5.0625 + 12.25)
= √17.3125 ≈ 4.16
o Dist to μ₂ = √((3.5-3.9)² + (5-5.1)²) = √((-0.4)² + (-0.1)²) = √(0.16 + 0.01) =
√0.17 ≈ 0.41
o Assign P5 to Cluster 2.
• P6 (4.5, 5):
o Dist to μ₁ = √((4.5-1.25)² + (5-1.5)²) = √((3.25)² + (3.5)²) = √(10.5625 +
12.25) = √22.8125 ≈ 4.78
o Dist to μ₂ = √((4.5-3.9)² + (5-5.1)²) = √((0.6)² + (-0.1)²) = √(0.36 + 0.01) =
√0.37 ≈ 0.61
o Assign P6 to Cluster 2.
• P7 (3.5, 4.5):
o Dist to μ₁ = √((3.5-1.25)² + (4.5-1.5)²) = √((2.25)² + (3)²) = √(5.0625 + 9) =
√14.0625 ≈ 3.75
o Dist to μ₂ = √((3.5-3.9)² + (4.5-5.1)²) = √((-0.4)² + (-0.6)²) = √(0.16 + 0.36) =
√0.52 ≈ 0.72
o Assign P7 to Cluster 2.
Cluster Assignments after Iteration 3:
• Cluster 1: {P1(1,1), P2(1.5,2)}
• Cluster 2: {P3(3,4), P4(5,7), P5(3.5,5), P6(4.5,5), P7(3.5,4.5)}
2. Update Step:
• New Centroid μ₁:
o μ₁_x = (1 + 1.5) / 2 = 1.25
o μ₁_y = (1 + 2) / 2 = 1.5
o μ₁_new = (1.25, 1.5)
• New Centroid μ₂:
o μ₂_x = (3 + 5 + 3.5 + 4.5 + 3.5) / 5 = 19.5 / 5 = 3.9
o μ₂_y = (4 + 7 + 5 + 5 + 4.5) / 5 = 25.5 / 5 = 5.1
o μ₂_new = (3.9, 5.1)
The centroids are the same as in the previous iteration:
μ₁ = (1.25, 1.5)
μ₂ = (3.9, 5.1)
The cluster assignments are also the same as in the previous iteration.
Therefore, the K-Means algorithm has converged.

Final Result:
• Cluster 1:
o Points: {P1(1,1), P2(1.5,2)}
o Centroid (μ₁): (1.25, 1.5)
• Cluster 2:
o Points: {P3(3,4), P4(5,7), P5(3.5,5), P6(4.5,5), P7(3.5,4.5)}

60
Data Science Tawqeer ul Islam

o Centroid (μ₂): (3.9, 5.1)

11. Hierarchical Clustering

• Definition: An unsupervised learning algorithm that builds a hierarchy of clusters.
Unlike K-Means, it doesn't require specifying the number of clusters beforehand.
• Core Concept: Creates nested clusters arranged in a tree-like structure called a
dendrogram.
• Types:
o Agglomerative (Bottom-Up): Starts with each data point as its own cluster and
iteratively merges the closest pairs of clusters until only one cluster remains (or
a stopping condition is met).
o Divisive (Top-Down): Starts with all data points in one cluster and recursively
splits clusters until each data point is its own cluster. (Agglomerative is more
common).
• How Agglomerative Clustering Works:
1. Start with N clusters, where each data point is a cluster.
2. Calculate the similarity or distance between all pairs of clusters.
3. Merge the two closest clusters based on a chosen linkage criterion.
4. Repeat steps 2 and 3 until only one cluster remains.
5. The process can be visualized with a dendrogram, where the y-axis represents the
distance (or dissimilarity) at which clusters were merged. Cutting the dendrogram at a
certain height determines the number of clusters.

61
Data Science Tawqeer ul Islam

• Linkage Criteria (How to measure distance between clusters):

o Single Linkage: Distance between the closest two points in the different clusters
(min distance). Can create long, "straggly" clusters (chaining effect).
o Complete Linkage: Distance between the farthest two points in the different
clusters (max distance). Tends to produce more compact, spherical clusters.
o Average Linkage: Average distance between all pairs of points from the different
clusters.
o Ward's Method: Minimizes the variance of the clusters being merged. Tends to
produce equally sized clusters.
• Parameters:
o Linkage Criterion: Must be chosen.
o Number of Clusters (post-hoc): Determined by cutting the dendrogram at a
chosen height or by deciding on the number of clusters visually from the
dendrogram.
o Distance Metric: (e.g., Euclidean, Manhattan).
• Advantages:
o Does not require specifying the number of clusters beforehand.
o Provides a visual representation of the cluster structure (dendrogram).
o Can reveal relationships between clusters at different levels of granularity.
• Disadvantages:
o Can be computationally expensive (O(n² log n) or O(n³)) and memory-intensive
(O(n²)) for large datasets (n is number of data points).
o Difficult to handle large datasets.
o Choosing the linkage criterion and the cutoff height can be subjective.

62
Data Science Tawqeer ul Islam

o Once a merge is made, it cannot be undone.

• Example Problem: Grouping genes with similar expression patterns. Creating
taxonomic trees in biology. Clustering cities based on geographical distance.
• Numerical Example (Agglomerative, Single Linkage):
o Data points (1D): {1, 3, 6, 7, 10}
o Initial clusters: {{1}, {3}, {6}, {7}, {10}}
o Distances: |3-1|=2, |6-3|=3, |7-6|=1, |10-7|=3, etc.
o Smallest distance is 1 between {6} and {7}. Merge them.
o Clusters: {{1}, {3}, {6, 7}, {10}}
o Distances:
▪ d({1}, {3}) = 2
▪ d({3}, {6, 7}) = min(|3-6|, |3-7|) = min(3, 4) = 3 (Single Linkage)
▪ d({6, 7}, {10}) = min(|6-10|, |7-10|) = min(4, 3) = 3 (Single Linkage)
▪ d({1}, {6, 7}) = min(|1-6|, |1-7|) = min(5, 6) = 5
▪ d({3}, {10}) = |3-10| = 7
▪ d({1}, {10}) = |1-10| = 9
o Smallest distance is 2 between {1} and {3}. Merge them.
o Clusters: {{1, 3}, {6, 7}, {10}}
o ... and so on. The merges would be {1,3} (dist 2), then {6,7} (dist 1 was done
first), then merge {6,7} and {10} (dist 3), then merge {1,3} and {6,7,10}. The
distances at merge height define the dendrogram y-axis.

12. DBSCAN
• Definition: A density-based unsupervised learning algorithm for clustering. It
groups together points that are closely packed together, marking points in low-
density regions as outliers.
• Core Concept: Clusters are defined as areas of high density separated by areas of
low density. It can find arbitrarily shaped clusters and is robust to noise.
• Key Concepts & Algorithm:
o ε (epsilon): A radius defining the neighbourhood around a point.
o MinPts: The minimum number of points required to form a dense region.
o Core Point: A point P is a core point if at least MinPts points (including P
itself) are within a distance ε of P.

63
Data Science Tawqeer ul Islam

o Border Point: A point Q is a border point if it is not a core point but is

within a distance ε of a core point.
o Noise Point (Outlier): A point R is a noise point if it is neither a core point
nor a border point.
o Directly Reachable: A point Q is directly reachable from a core point P if Q
is within distance ε of P.
o Density-Reachability: A point Q is density-reachable from a point P if there
is a path of core points P₁, ..., Pn with P₁=P and Pn=Q, such that Pᵢ₊₁ is
directly reachable from Pᵢ.
o Density-Connectivity: Two points P and Q are density-connected if there is
a core point O such that both P and Q are density-reachable from O.

• How it Works:
1. Arbitrarily pick an unvisited point.
2. If the point is a core point (has at least MinPts neighbours within ε):
▪ Start a new cluster with this point.

64
Data Science Tawqeer ul Islam

▪ Expand the cluster by adding all density-reachable points. This

involves visiting neighbours' neighbours if they are core points.
▪ Continue expanding until no more points can be added to the current
cluster.
3. If the point is not a core point (but has neighbours): Mark it as a border point (it
might be added to a cluster if visited from a core point).
4. If the point has fewer than MinPts neighbours within ε: Mark it as noise/outlier
initially. These points will remain noise unless they are within ε of a core point discovered
later (then they become border points).
5. Repeat steps 1-4 for all unvisited points.
• Parameters:
o ε (epsilon): Crucial for defining the neighbourhood size.
o MinPts: Crucial for defining the density threshold.
o These parameters are sensitive and often require tuning. A common
heuristic for estimating ε is using a k-distance plot (plotting distance to the
k-th nearest neighbour for each point, where k=MinPts).
• Advantages:
o Can find clusters of arbitrary shape.
o Can identify outliers (noise points).
o Does not require specifying the number of clusters beforehand.
o More robust to noise than K-Means.
• Disadvantages:
o Sensitive to the choice of ε and MinPts.
o Difficulty in handling datasets with varying densities (a single ε, MinPts pair
won't work well).
o Can struggle with high-dimensional data (distance metrics become less
meaningful).
o Border points can sometimes belong to different clusters depending on the
order they are processed (though standard implementations handle this).
• Example Problem: Finding clusters of stores in a city map. Identifying unusual
patterns in spatial data (e.g., crime hotspots).
• Numerical Example (Identifying points based on ε, MinPts):
o Data points in 1D: {1, 2, 3, 10, 11, 12, 20}
o Let ε = 2, MinPts = 3
o Consider point 2:
▪ Neighbours within distance ε=2: Points at 1, 2, 3. (Count = 3)

65
Data Science Tawqeer ul Islam

▪ Since Count (3) ≥ MinPts (3), point 2 is a Core Point.

o Consider point 10:
▪ Neighbours within distance ε=2: Points at 10, 11, 12. (Count = 3)
▪ Since Count (3) ≥ MinPts (3), point 10 is a Core Point.
o Consider point 1:
▪ Neighbours within distance ε=2: Points at 1, 2, 3. (Count = 3)
▪ Point 1 is a Core Point.
o Consider point 3:
▪ Neighbours within distance ε=2: Points at 1, 2, 3. (Count = 3)
▪ Point 3 is a Core Point.
o Consider point 11:
▪ Neighbours within distance ε=2: Points at 10, 11, 12. (Count = 3)
▪ Point 11 is a Core Point.
o Consider point 12:
▪ Neighbours within distance ε=2: Points at 10, 11, 12. (Count = 3)
▪ Point 12 is a Core Point.
o Consider point 20:
▪ Neighbours within distance ε=2: Point at 20. (Count = 1)
▪ Since Count (1) < MinPts (3), point 20 is not a core point.
▪ Is it within ε of a core point? Yes, it's within 2 of no core point. (It
would need to be within 2 of 12, but 12-20 = -8, distance 8). No core
points are within distance 2 of 20.
▪ Point 20 is a Noise Point.
o Clusters formed:
▪ From core point 1: reach 2, 3 (all core). Cluster 1 = {1, 2, 3}.
▪ From core point 10: reach 11, 12 (all core). Cluster 2 = {10, 11, 12}.
▪ Point 20 remains noise.

Measuring Performance of a Model

Importance of Performance Measurement
• Evaluate Effectiveness: Determine how well a model performs its intended task.
• Compare Models: Choose the best model among different algorithms or variations
of the same algorithm.

66
Data Science Tawqeer ul Islam

• Hyperparameter Tuning: Optimize model parameters to maximize performance.

• Understand Model Weaknesses: Identify where and why a model fails.
• Communicate Results: Quantify model performance for stakeholders.
• Avoid Overfitting: Ensure the model generalizes well to unseen data (typically
evaluated on separate test/validation sets).
Performance Metrics for Classification (Binary Classification Focus)
Most metrics are derived from the Confusion Matrix.
• Confusion Matrix:
o Definition: A table used to summarize the performance of a classification
algorithm, showing the counts of correct and incorrect predictions for each class.
o Core Concept: Breaks down predictions into four outcomes based on the actual
class and the predicted class.
o Components (for binary classification, typically positive and negative classes):
▪ True Positive (TP): Model predicted Positive, Actual is Positive. (Correctly
identified positive cases).
▪ True Negative (TN): Model predicted Negative, Actual is Negative.
(Correctly identified negative cases).
▪ False Positive (FP): Model predicted Positive, Actual is Negative. (Type I
Error - predicting positive when it's negative). Also called False Alarm.
▪ False Negative (FN): Model predicted Negative, Actual is Positive. (Type II
Error - predicting negative when it's positive). Also called Miss.
o Structure:
o Actual Class
o -----------------------
o Predicted | Positive | Negative
o Class |-----------------------
o Positive | TP | FP
o Negative | FN | TN

o Totals:
▪ Total Actual Positives = TP + FN
▪ Total Actual Negatives = FP + TN
▪ Total Predicted Positives = TP + FP
▪ Total Predicted Negatives = FN + TN
▪ Total Instances = TP + TN + FP + FN

67
Data Science Tawqeer ul Islam

• Accuracy:
o Definition: The ratio of correctly predicted instances to the total number of
instances.
o Formula: Accuracy = (TP + TN) / (TP + TN + FP + FN)
o Interpretation: Overall correctness.
o Use Case: Suitable for balanced datasets (where the number of instances in each
class is roughly equal).
o Limitations: Can be misleading for imbalanced datasets. If 95% of emails are
non-spam, a model that always predicts "non-spam" achieves 95% accuracy but is
useless.
• Precision (Positive Predictive Value):
o Definition: Of all instances predicted as Positive, how many were actually
Positive? Measures the exactness or quality of the positive predictions.
o Formula: Precision = TP / (TP + FP)
o Interpretation: Avoids false alarms. High precision means when the model
predicts positive, it is very likely correct.
o Use Case: When the cost of a False Positive is high (e.g., recommending a
harmful drug, marking a non-spam email as spam, wrongly arresting an innocent
person).
• Recall (Sensitivity, True Positive Rate):
o Definition: Of all instances that were actually Positive, how many were correctly
predicted as Positive? Measures the completeness or coverage of the positive
class.
o Formula: Recall = TP / (TP + FN)
o Interpretation: Avoids missing positive cases. High recall means the model finds
most of the positive instances.
o Use Case: When the cost of a False Negative is high (e.g., failing to detect a
disease, missing a fraudulent transaction, failing to detect an incoming missile).
• Specificity (True Negative Rate):
o Definition: Of all instances that were actually Negative, how many were
correctly predicted as Negative?
o Formula: Specificity = TN / (TN + FP)
o Interpretation: Correctly identifies negative cases.
o Note: Related to False Positive Rate (FPR = FP / (FP + TN) = 1 - Specificity).
• F1-Score:
o Definition: The harmonic mean of Precision and Recall. Provides a single score
that balances both metrics.

68
Data Science Tawqeer ul Islam

o Formula: F1 = 2 * (Precision * Recall) / (Precision + Recall)

o Interpretation: Gives equal weight to Precision and Recall. Ranges from 0 to 1,
where 1 is perfect.
o Use Case: When you need to balance Precision and Recall, especially useful for
imbalanced datasets where Accuracy is not informative. The harmonic mean
penalizes extreme values (e.g., very high precision and very low recall).
• ROC Curve (Receiver Operating Characteristic Curve):
o Definition: A graphical plot that illustrates the performance of a binary classifier
system as its discrimination threshold is varied.
o Core Concept: Plots the True Positive Rate (Recall) on the y-axis against the
False Positive Rate (FPR) on the x-axis at various threshold settings.
▪ TPR = TP / (TP + FN) (same as Recall)
▪ FPR = FP / (FP + TN)
o Interpretation:
▪ The curve shows the trade-off between sensitivity (TPR) and specificity (1-
FPR).
▪ A point in the bottom-left corner (0, 0) represents a classifier that predicts
all instances as negative (TPR=0, FPR=0).
▪ A point in the top-right corner (1, 1) represents a classifier that predicts all
instances as positive (TPR=1, FPR=1).
▪ The diagonal line from (0, 0) to (1, 1) represents a random classifier.
▪ A good classifier's curve is above the diagonal line, ideally bending towards
the top-left corner (high TPR, low FPR).
o How it's generated: Many classification models (like Logistic Regression, SVM
with probability estimates) output a probability score. By varying the threshold
for classifying as positive (e.g., predict positive if probability > 0.1, > 0.2, ..., >
0.9), you get different pairs of (FPR, TPR) which are then plotted.
• AUC ROC (Area Under the ROC Curve):
o Definition: A single scalar value that summarizes the overall performance of a
binary classifier across all possible thresholds. It's the area under the ROC curve.
o Interpretation:
▪ Ranges from 0 to 1.
▪ AUC = 0.5 indicates performance no better than random guessing.
▪ AUC = 1.0 indicates a perfect classifier.
▪ Higher AUC means better overall performance.

69
Data Science Tawqeer ul Islam

▪ Represents the probability that a randomly chosen positive instance will be

ranked higher (given a higher probability score) than a randomly chosen
negative instance.
o Use Case: Useful for comparing different models, regardless of the chosen
classification threshold.
• Precision-Recall Curve:
o Definition: A plot of Precision (y-axis) versus Recall (x-axis) at various threshold
settings.
o Core Concept: Focuses specifically on the performance on the positive class.
o Interpretation:
▪ A good classifier's curve is in the top-right corner (high Precision and high
Recall).
▪ The curve shows the trade-off: often, increasing Recall (finding more
positives) leads to decreasing Precision (more false alarms).
o Use Case: Especially recommended for highly imbalanced datasets, where the
positive class is rare. In such cases, the ROC curve can be misleadingly optimistic
because the FPR (denominator includes TN, which is large) remains low even for
poor models. The Precision-Recall curve provides a more informative view of
performance on the minority (positive) class.
• Numerical Example (Confusion Matrix & Metrics):
o Suppose a model made the following predictions on 100 instances:
▪ Actual Positive: 20, Actual Negative: 80
▪ Predicted Positive: 15, Predicted Negative: 85
▪ TP = 10 (correctly predicted positive)
▪ FP = 5 (predicted positive, but actually negative)
▪ FN = 10 (predicted negative, but actually positive)
▪ TN = 75 (correctly predicted negative)
o Confusion Matrix:
Actual
P N
Pred. P 10 5
Pred. N 10 75

o Calculate Metrics:
▪ Accuracy = (10 + 75) / (10 + 5 + 10 + 75) = 85 / 100 = 0.85 (or 85%)
▪ Precision = 10 / (10 + 5) = 10 / 15 ≈ 0.67 (or 67%) - Of those predicted
positive, 67% were correct.

70
Data Science Tawqeer ul Islam

▪ Recall = 10 / (10 + 10) = 10 / 20 = 0.50 (or 50%) - Of the actual positives,

50% were found.
▪ Specificity = 75 / (5 + 75) = 75 / 80 = 0.9375 (or 93.75%) - Of the actual
negatives, 93.75% were found.
▪ FPR = 5 / (5 + 75) = 5 / 80 = 0.0625 (or 6.25%)
▪ F1 = 2 * (0.67 * 0.50) / (0.67 + 0.50) = 2 * 0.335 / 1.17 ≈ 0.57
Interpretation of Results
Beyond calculating metrics, understanding their context and reliability is crucial.
• Confidence Interval for Accuracy:
o Concept: When you report a model's accuracy based on a test set, it's a single
estimate based on a sample of data. The true accuracy on the entire population
of possible data might be different. A confidence interval provides a range
around your sample accuracy within which the true population accuracy is likely
to fall (with a certain level of confidence, typically 95%).
o Interpretation: A 95% confidence interval for accuracy [0.82, 0.88] means that if
you were to repeat the process of training and testing the model on many
different random samples of data, 95% of the resulting confidence intervals
would contain the true accuracy of the model on the underlying data
distribution. It indicates the uncertainty around your point estimate of accuracy.
A wider interval means more uncertainty (e.g., smaller test set).
o Mathematics (Basic Idea - Normal Approximation for large samples): For a large
number of test instances (N) and observed accuracy (p), a confidence interval
can be approximated using the standard error: CI = p ± Z * sqrt(p*(1-p)/N), where
Z is the Z-score corresponding to the desired confidence level (e.g., 1.96 for
95%). More sophisticated methods like the Wilson Score Interval are preferred,
especially for smaller N or accuracies close to 0 or 1, as they handle edge cases
better and don't assume normality as strictly.
o Use Case: Provides a more robust assessment of performance than just a single
accuracy number. Helps understand the variability of the metric.
• Hypothesis Tests for Comparing Models and Algorithms:
o Concept: When you have two models or algorithms and want to determine if one
performs significantly better than the other, you can use statistical hypothesis
tests. These tests help you decide if the observed difference in performance
metrics (like accuracy, F1-score, MSE) is genuinely due to the algorithms'
capabilities or simply due to random chance or variability in the data split.
o Why use them? A small observed difference might not be statistically significant,
and concluding that one model is "better" would be misleading. Hypothesis tests
provide a framework to make principled comparisons.
o General Process:
1. Formulate Hypotheses:

71
Data Science Tawqeer ul Islam

▪ Null Hypothesis (H₀): There is no significant difference in performance

between the two models/algorithms.
▪ Alternative Hypothesis (H₁): There is a significant difference in
performance (often, one is better than the other - one-sided test, or they
are just different - two-sided test).
2. Choose a Significance Level (α): Typically 0.05 (5%). This is the probability of
rejecting the null hypothesis when it is actually true (Type I error).
3. Select an Appropriate Test: The choice depends on the data, the
performance metric, and how the models were evaluated (e.g., on the same
test set, different folds in cross-validation).
▪ Paired t-test: Suitable for comparing two models' performance metric
(e.g., accuracy, MSE) when both models are evaluated on the same test
set or the same cross-validation folds. Tests the mean difference of the
metric across pairs of evaluations.
▪ McNemar's Test: Specifically for comparing two classification models on
the same test set. It looks at the counts of instances where one model is
correct and the other is incorrect. Focuses on disagreements between the
models.
▪ Cross-validation based tests: More sophisticated tests exist for comparing
models evaluated using k-fold cross-validation (e.g., Dietterich's 5x2cv
paired t-test, Nadeau and Bengio's corrected t-test) to account for the
dependence between folds.
4. Calculate Test Statistic: Compute a value based on the observed data and the
chosen test.
5. Determine p-value: The probability of observing a test statistic as extreme
as, or more extreme than, the one calculated from your data, assuming the
null hypothesis is true.
6. Make a Decision:
▪ If p-value ≤ α: Reject the null hypothesis. Conclude that there is a
statistically significant difference in performance.
▪ If p-value > α: Fail to reject the null hypothesis. Conclude that there is
not enough evidence to say there is a statistically significant difference
(the observed difference could be due to chance).
o Use Case: Provides statistical rigor to model comparison, preventing over-
interpretation of small performance differences.

Probabilistic Models
1. Introduction to Probability
• Core Concept: Probability is the mathematical framework for quantifying
uncertainty. It deals with the likelihood of events occurring.

72
Data Science Tawqeer ul Islam

• Key Definitions:
o Experiment: A process that produces an outcome (e.g., flipping a coin, rolling a
die, drawing a card).
o Outcome: A single possible result of an experiment (e.g., Heads, rolling a 3,
drawing the King of Hearts).
o Sample Space (Ω or S): The set of all possible outcomes of an experiment (e.g.,
{Heads, Tails} for a coin flip; {1, 2, 3, 4, 5, 6} for a die roll).
o Event (E): A subset of the sample space. A collection of one or more outcomes
(e.g., rolling an even number {2, 4, 6}, drawing a red card).
• Probability of an Event P(E):
o Assuming equally likely outcomes: P(E) = (Number of outcomes in E) / (Total
number of outcomes in Ω).
o Properties:
▪ 0 ≤ P(E) ≤ 1
▪ P(Ω) = 1 (Probability of the sample space - something must happen)
▪ P(∅) = 0 (Probability of the empty set - nothing happens)
o If A and B are mutually exclusive events (cannot happen at the same time): P(A
or B) = P(A ∪ B) = P(A) + P(B)
o For any two events A and B: P(A or B) = P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
• Types of Probability:
o Marginal Probability: The probability of a single event occurring, regardless of
any other events (e.g., P(drawing a King) from a deck).
o Joint Probability: The probability of two or more events occurring together
(e.g., P(drawing a King AND an Ace) with replacement, or P(drawing a King AND a
Heart) from a single draw). Denoted P(A and B) or P(A ∩ B).
o Conditional Probability: The probability of an event A occurring given that
another event B has already occurred. Denoted P(A | B).
• Probability Rules:
o Product Rule: Relates joint probability and conditional probability.
▪ P(A and B) = P(A | B) * P(B)
▪ P(A and B) = P(B | A) * P(A)
o Sum Rule (Law of Total Probability): If {B₁, B₂, ..., Bₙ} is a partition of the
sample space (mutually exclusive and exhaustive events), then P(A) = Σᵢ P(A | Bᵢ)
* P(Bᵢ). This is used to calculate the marginal probability of A by summing over all
possible conditions Bᵢ.
• Independence:

73
Data Science Tawqeer ul Islam

o Two events A and B are independent if the occurrence of one does not affect the
probability of the other.
o Mathematically:
▪ P(A | B) = P(A)
▪ P(B | A) = P(B)
▪ Equivalently, P(A and B) = P(A) * P(B) (This is often the definition
used).
• Example Problem: Drawing cards from a standard 52-card deck.
o Ω = 52 cards.
o Event A = Drawing a King. P(A) = 4/52 = 1/13.
o Event B = Drawing a Heart. P(B) = 13/52 = 1/4.
o Event A and B = Drawing the King of Hearts. P(A and B) = 1/52.
o Are A and B independent? P(A)P(B) = (1/13)(1/4) = 1/52. Yes, they are
independent in a standard deck (knowing it's a Heart doesn't change the
probability it's a King, among all cards).
o P(A | B) = P(King | Heart) = Probability of drawing a King given you drew a Heart.
There is 1 King of Hearts among 13 Hearts. So, P(A | B) = 1/13. This equals P(A),
confirming independence.
2. Rule of Bayes and Conditional Independence
• Bayes' Rule (Bayes' Theorem):
o Definition: A fundamental theorem in probability that describes how to
update the probability of a hypothesis based on new evidence.
o Formula:
P(A | B) = [ P(B | A) * P(A) ] / P(B)
o Terms:
▪ P(A | B): Posterior Probability - The probability of hypothesis A being true
given evidence B. This is what we want to find.
▪ P(B | A): Likelihood - The probability of observing evidence B given that
hypothesis A is true.
▪ P(A): Prior Probability - The initial probability of hypothesis A being true
before observing the evidence B.
▪ P(B): Evidence (or Marginal Likelihood) - The probability of observing
evidence B, regardless of the hypothesis. This acts as a normalizing
constant.
o Calculating Evidence P(B): Using the Law of Total Probability. If A and ¬A
(not A) are the only two possibilities for the hypothesis:
P(B) = P(B | A) * P(A) + P(B | ¬A) * P(¬A)

74
Data Science Tawqeer ul Islam

So, Bayes' Rule can also be written as:

P(A | B) = [ P(B | A) * P(A) ] / [ P(B | A) * P(A) + P(B | ¬A) * P(¬A) ]
o Concept: Bayes' Rule shows how to revise a prior belief (P(A)) into a
posterior belief (P(A|B)) after taking into account new evidence (B).
• Example Problem (Bayes' Rule): Medical Diagnosis
o Hypothesis A: Patient has a specific disease.
o Evidence B: Patient tests positive for the disease.
o Let's say:
▪ P(A) = 0.01 (1% prevalence of the disease in the population - Prior)
▪ P(B | A) = 0.95 (95% sensitivity of the test - Likelihood)
▪ P(B | ¬A) = 0.10 (10% false positive rate - Probability of testing positive
given no disease)
o We want to find P(A | B): Probability the patient actually has the disease
given they tested positive (Posterior).
o First, calculate P(B) = P(B | A) * P(A) + P(B | ¬A) * P(¬A)
▪ P(¬A) = 1 - P(A) = 1 - 0.01 = 0.99
▪ P(B) = (0.95 * 0.01) + (0.10 * 0.99) = 0.0095 + 0.099 = 0.1085
o Now apply Bayes' Rule:
P(A | B) = [ P(B | A) * P(A) ] / P(B) = (0.95 * 0.01) / 0.1085 = 0.0095 / 0.1085
≈ 0.0875
o Interpretation: Even with a positive test, the probability of actually having
the disease is only about 8.75%. This is because the disease is rare (low
prior probability), and the false positive rate is relatively high compared to
the disease prevalence.
• Conditional Independence:
o Definition: Two events A and B are conditionally independent given a third
event C if the probability of A occurring depends only on C, and not
additionally on B. In other words, if we know C, knowing B provides no
additional information about A.
o Mathematically: P(A and B | C) = P(A | C) * P(B | C)
o Equivalent Form: P(A | B and C) = P(A | C)
o Contrast with Marginal Independence: A and B might be dependent overall
(P(A and B) ≠ P(A)P(B)), but become independent once we condition on C.
Conversely, they might be marginally independent but become dependent
when conditioned on C (this is called explaining away, important in BBNs).
o Importance in ML: Conditional independence assumptions simplify the
computation of joint probabilities. This is the core assumption behind Naive
Bayes.

75
Data Science Tawqeer ul Islam

o Example:
▪ Event A: Person has a cough.
▪ Event B: Person has a fever.
▪ Event C: Person has the flu.
▪ A and B are not marginally independent (cough and fever are correlated).
P(Cough and Fever) ≠ P(Cough)P(Fever).
▪ However, A and B might be conditionally independent given C. P(Cough
and Fever | Flu) ≈ P(Cough | Flu) * P(Fever | Flu). If you know someone
has the flu, knowing they have a fever might not give you much additional
information about whether they have a cough, beyond what the flu itself
tells you.
3. Naive Bayes Classifier
• Definition: A probabilistic supervised learning algorithm used for classification. It's
based on Bayes' Rule and assumes naive conditional independence between
features given the class label.
• Core Concept: For a given instance with features x₁, x₂, ..., xₙ, it calculates the
probability that it belongs to each class Ck using Bayes' Theorem and picks the class
with the highest probability.
• Mathematics:
o We want to find P(Ck | x₁, x₂, ..., xₙ) for each class Ck.
o Using Bayes' Rule:
P(Ck | x₁, ..., xₙ) = [ P(x₁, ..., xₙ | Ck) * P(Ck) ] / P(x₁, ..., xₙ)
o Since the denominator P(x₁, ..., xₙ) is the same for all classes, we only need to
compare the numerator:
P(Ck | x₁, ..., xₙ) ∝ P(x₁, ..., xₙ | Ck) * P(Ck)
o The Naive Assumption: Features x₁, ..., xₙ are conditionally independent given
the class Ck.
P(x₁, ..., xₙ | Ck) = P(x₁ | Ck) * P(x₂ | Ck) * ... * P(xₙ | Ck)
o Classification Rule:
Classify x₁, ..., xₙ into the class Ck that maximizes:
P(Ck) * P(x₁ | Ck) * P(x₂ | Ck) * ... * P(xₙ | Ck)
o Training: The model learns by estimating the required probabilities from the
training data:
▪ Prior Probability P(Ck): Calculated as the frequency of class Ck in the
training data. P(Ck) = (Number of instances of class Ck) / (Total number of
instances).
▪ Conditional Probability P(xᵢ | Ck): Calculated as the frequency of feature
value xᵢ occurring among instances of class Ck. P(xᵢ | Ck) = (Count of
instances with feature xᵢ in class Ck) / (Count of instances in class Ck).

76
Data Science Tawqeer ul Islam

o Handling Zero Probabilities: If a feature value xᵢ does not appear with a class
Ck in the training data, P(xᵢ | Ck) would be 0. This would make the entire
product 0, regardless of other probabilities. Laplace Smoothing (Add-k
Smoothing) is used to prevent this by adding a small number (k, usually 1) to
the counts.
P(xᵢ | Ck) = (Count(xᵢ and Ck) + k) / (Count(Ck) + k * |Vocabulary|)
▪ k=1 is Add-one smoothing. |Vocabulary| is the number of possible values
for feature xᵢ.
• Advantages:
o Simple and fast to train and predict.
o Requires relatively little training data to estimate parameters.
o Works well with high-dimensional data (like text classification).
o Surprisingly effective in practice despite the strong assumption.
• Disadvantages:
o The naive independence assumption is rarely true in real-world data.
o While it often performs well as a classifier, the probability estimates it
produces may be inaccurate.
• Example Problem: Spam classification. Features are the words in an email. Classes
are "Spam" and "Not Spam".
• Numerical Example (Text Classification - Spam/Not Spam):
o Training Data:
▪ "Buy pharmaceuticals now" (Spam)
▪ "Buy painkillers" (Spam)
▪ "Nigeria pharmaceuticals" (Spam)
▪ "Nigeria now" (Not Spam)
o Vocabulary: {buy, pharmaceuticals, now, painkillers, Nigeria}
o Classes: Spam, Not Spam. P(Spam) = 3/4, P(Not Spam) = 1/4.
o Conditional Probabilities (using Laplace smoothing k=1):
▪ Count(Spam) = 3. Vocab Size = 5. Denominator = 3 + 1*5 = 8.
▪ Count(Not Spam) = 1. Vocab Size = 5. Denominator = 1 + 1*5 = 6.
▪ P(buy | Spam) = (Count("buy" in Spam) + 1) / 8 = (2 + 1) / 8 = 3/8
▪ P(pharmaceuticals | Spam) = (Count("pharmaceuticals" in Spam) + 1) / 8 =
(2 + 1) / 8 = 3/8
▪ P(now | Spam) = (Count("now" in Spam) + 1) / 8 = (1 + 1) / 8 = 2/8
▪ P(painkillers | Spam) = (Count("painkillers" in Spam) + 1) / 8 = (1 + 1) / 8
= 2/8

77
Data Science Tawqeer ul Islam

▪ P(Nigeria | Spam) = (Count("Nigeria" in Spam) + 1) / 8 = (1 + 1) / 8 = 2/8

▪ P(buy | Not Spam) = (Count("buy" in Not Spam) + 1) / 6 = (0 + 1) / 6 = 1/6
▪ P(pharmaceuticals | Not Spam) = (Count("pharmaceuticals" in Not Spam) +
1) / 6 = (0 + 1) / 6 = 1/6
▪ P(now | Not Spam) = (Count("now" in Not Spam) + 1) / 6 = (1 + 1) / 6 =
2/6
▪ P(painkillers | Not Spam) = (Count("painkillers" in Not Spam) + 1) / 6 = (0
+ 1) / 6 = 1/6
▪ P(Nigeria | Not Spam) = (Count("Nigeria" in Not Spam) + 1) / 6 = (1 + 1) / 6
= 2/6
o Test Sentence: "buy now"
o Calculate numerator for each class:
▪ P(Spam) * P(buy | Spam) * P(now | Spam) = (3/4) * (3/8) * (2/8) = 18 / 256
▪ P(Not Spam) * P(buy | Not Spam) * P(now | Not Spam) = (1/4) * (1/6) *
(2/6) = 2 / 144
o Compare: (18/256) vs (2/144). 18/256 ≈ 0.0703, 2/144 ≈ 0.0139.
o Since 0.0703 > 0.0139, the classifier predicts "Spam".
4. Bayesian Belief Networks (BBNs) / Directed Acyclic Graphs (DAGs)
• Definition: A probabilistic graphical model that represents a set of variables and
their conditional dependencies via a Directed Acyclic Graph (DAG). It combines
graph theory with probability theory.
• Core Concept: The structure of the network (the nodes and directed edges)
defines the conditional independence relationships between the variables. Each
node has an associated Conditional Probability Table (CPT) that quantifies the
probability of that variable taking on each of its values, given the values of its
parent nodes.
• Components:
o Nodes: Represent random variables (can be discrete or continuous).
o Directed Edges (Arrows): Represent direct probabilistic dependencies. An edge
from node A to node B means that A directly influences B, or that B is
conditionally dependent on A. There are no cycles (Acyclic).
o Conditional Probability Tables (CPTs): For each node X, the CPT lists the
probability distribution of X given all possible combinations of values of its
parent nodes. Nodes with no parents (root nodes) have a CPT that is just their
marginal probability distribution P(X).
• Mathematics: Representing the Joint Probability Distribution:
o The structure of the BBN allows us to write the joint probability distribution
over all variables X₁, ..., Xn as a product of the conditional probabilities of

78
Data Science Tawqeer ul Islam

each variable given its parents in the graph:

P(X₁, ..., Xn) = Πᵢ P(Xi | Parents(Xi))
o This factorization is a consequence of the conditional independence
relationships encoded by the graph. Variables are conditionally independent of
their non-descendants given their parents (the "local Markov property").
• Building a BBN (Conceptual Steps):
1. Identify Variables: Determine the relevant variables for the problem.
2. Define Structure (DAG): Determine the direct dependencies between variables and
draw the directed edges. This requires domain knowledge or learning algorithms. Ensure
it's acyclic.
3. Define CPTs: For each variable, specify the conditional probability distribution
given its parents. This is often based on data, expert knowledge, or a combination.
• Inference (Answering Queries): The main purpose of a BBN is to perform
probabilistic inference – answering questions about the probabilities of variables
given some observed evidence (values of other variables).
o Query: P(Query Variables | Evidence Variables = observed values).
o Example Queries: What is the probability of disease X given symptoms Y and Z?
If the alarm sounds and there is a report of a burglary, what is the probability of
an earthquake?
o Inference Methods:
▪ Exact Inference: Calculates probabilities precisely (e.g., Variable
Elimination, Junction Tree Algorithm). Can be computationally expensive
(#P-hard in the worst case, feasible for sparse/structured networks).
▪ Approximate Inference: Uses sampling or other approximation techniques
when exact inference is intractable (e.g., Markov Chain Monte Carlo,
Variational Inference).
• Advantages:
o Provides a clear and intuitive graphical representation of dependencies.
o Can handle complex dependencies and uncertainty.
o Allows for causal reasoning (though interpreting correlation as causation
requires careful model design).
o Can naturally handle missing data during inference.
o Can be updated with new evidence using Bayes' rule within the network
structure.
• Disadvantages:
o Building the structure and defining CPTs can require significant domain
expertise or data.
o Inference can be computationally complex, especially for large or densely
connected networks.

79
Data Science Tawqeer ul Islam

• Example Network (Alarm Network):

o Variables: Burglary (B), Earthquake (E), Alarm (A), JohnCalls (J), MaryCalls (M)
o Structure:
▪ B -> A
▪ E -> A
▪ A -> J
▪ A -> M
▪ (Burglary and Earthquake cause Alarm. Alarm causes John and Mary to call).
Burglary and Earthquake are independent of each other. JohnCalls is
independent of MaryCalls given Alarm.
o CPTs needed:
▪ P(B)
▪ P(E)
▪ P(A | B, E) - needs probabilities for all 4 combinations of B and E values
(T,T), (T,F), (F,T), (F,F)
▪ P(J | A) - needs probabilities for A (T, F)
▪ P(M | A) - needs probabilities for A (T, F)
o Example CPT entry for P(A | B, E): P(A=True | B=True, E=False) = 0.94 (High
probability the alarm sounds if there's a burglary but no earthquake).
o Query Example: P(Burglary=True | JohnCalls=True, MaryCalls=True) - What's the
probability of a burglary given both John and Mary called? This is an inference
task calculated using the network structure and CPTs, applying Bayes' Rule
implicitly.

80
Data Science Tawqeer ul Islam

Association Rule Mining

Definition:
Association Rule Mining is an unsupervised machine learning technique used to discover
interesting relationships or associations among a set of items in a dataset. The goal is to
find rules that describe how often items occur together. These rules are typically expressed
in the form "IF {antecedent} THEN {consequent}", meaning that if the antecedent items are
present, then the consequent items are also likely to be present.
Core Concepts:
1. Itemset:
o A collection of one or more items.
o Example: {Milk, Bread, Diapers}
o An itemset containing k items is called a k-itemset.
2. Transaction:
o A single instance of a group of items occurring together.
o Example: In market basket analysis, a transaction is the set of items bought
by a customer in one shopping trip.
3. Support (supp(X)):
o An indication of how frequently an itemset X appears in the dataset.
o Formula: supp(X) = (Number of transactions containing X) / (Total number
of transactions)
o Interpretation: The probability that a transaction contains itemset X.
o Example: If {Milk, Bread} appears in 300 out of 1000 transactions, then
supp({Milk, Bread}) = 300/1000 = 0.3 or 30%.
4. Frequent Itemset:
o An itemset whose support is greater than or equal to a user-defined
minimum support threshold (min_sup).
o Finding frequent itemsets is a key step in association rule mining.
5. Association Rule:
o An implication of the form X → Y, where X and Y are itemsets, and X ∩ Y = ∅
(X and Y are disjoint).
o X is called the antecedent (or LHS - Left Hand Side).
o Y is called the consequent (or RHS - Right Hand Side).
o Example: {Milk, Bread} → {Butter}
6. Confidence (conf(X → Y)):

81
Data Science Tawqeer ul Islam

o Measures how often items in Y appear in transactions that contain X. It's the
conditional probability of finding Y given X.
o Formula: conf(X → Y) = supp(X ∪ Y) / supp(X)
▪ supp(X ∪ Y) is the support of the itemset containing all items in both
X and Y.
▪ supp(X) is the support of the antecedent X.
o Interpretation: The probability of finding itemset Y in a transaction, given
that the transaction also contains itemset X.
o Example: If supp({Milk, Bread, Butter}) = 0.2 and supp({Milk, Bread}) = 0.3,
then conf({Milk, Bread} → {Butter}) = 0.2 / 0.3 ≈ 0.67 or 67%. This means
that 67% of the transactions that contain Milk and Bread also contain Butter.
7. Lift (lift(X → Y)):
o Measures how much more likely Y is to be purchased when X is purchased,
compared to the likelihood of Y being purchased independently.
o Formula: lift(X → Y) = supp(X ∪ Y) / (supp(X) * supp(Y))
▪ Alternatively, lift(X → Y) = conf(X → Y) / supp(Y)
o Interpretation:
▪ lift(X → Y) = 1: X and Y are independent; no association.
▪ lift(X → Y) > 1: X and Y are positively correlated; the presence of X
increases the likelihood of Y.
▪ lift(X → Y) < 1: X and Y are negatively correlated; the presence of X
decreases the likelihood of Y.
o Example: If conf({Milk, Bread} → {Butter}) = 0.67 and supp({Butter}) = 0.4,
then lift({Milk, Bread} → {Butter}) = 0.67 / 0.4 = 1.675. This suggests a
positive association.
8. Minimum Support (min_sup) and Minimum Confidence (min_conf):
o User-defined thresholds used to filter out uninteresting itemsets and rules.
o Only itemsets with support ≥ min_sup are considered frequent.
o Only rules with confidence ≥ min_conf (and derived from frequent itemsets)
are considered interesting.
Goal of Association Rule Mining:
To find all association rules X → Y such that:
1. supp(X ∪ Y) ≥ min_sup
2. conf(X → Y) ≥ min_conf
Process:
Association rule mining is typically a two-step process:

82
Data Science Tawqeer ul Islam

1. Frequent Itemset Generation: Find all itemsets whose support is greater than or
equal to min_sup. This is the most computationally intensive step.
2. Rule Generation: From the frequent itemsets found in step 1, generate association
rules that satisfy the min_conf threshold.

Apriori Algorithm
The Apriori algorithm is a classic algorithm for mining frequent itemsets and learning
association rules. It uses a "bottom-up" approach, where frequent subsets are extended
one item at a time (candidate generation), and groups of candidates are tested against
the data.
Key Property (Apriori Property / Anti-Monotonicity of Support):
• "All non-empty subsets of a frequent itemset must also be frequent."
• Conversely, "If an itemset is infrequent, then all its supersets must also be
infrequent."
• This property is crucial for pruning the search space. If a candidate (k)-itemset is
found to be infrequent, we don't need to consider any of its (k+1)-itemset
supersets.
Steps of the Apriori Algorithm:
1. Initialization (k=1):
o Scan the transaction database to count the support of each individual item
(1-itemsets).
o Identify frequent 1-itemsets (L₁) by comparing their support to min_sup.
2. Iterative Frequent Itemset Generation (for k > 1):
Repeat for k = 2, 3, ... until no more frequent k-itemsets can be found:
o a. Candidate Generation (Cₖ):
▪ Generate candidate k-itemsets from frequent (k-1)-itemsets (Lₖ₋₁).
▪ This is typically done by joining Lₖ₋₁ with itself:
▪ Two frequent (k-1)-itemsets are joined if they share (k-2)
common items. For example, to generate 3-itemsets, join
two 2-itemsets {I1, I2} and {I1, I3} to form {I1, I2, I3}.
▪ Pruning (using Apriori property): After generating candidates,
prune any candidate k-itemset if any of its (k-1)-subsets are not in
Lₖ₋₁ (i.e., not frequent).
o b. Support Counting:
▪ Scan the transaction database. For each transaction, determine
which of the candidate k-itemsets (Cₖ) are contained in it.
▪ Increment the support count for these candidates.

83
Data Science Tawqeer ul Islam

o c. Frequent Itemset Identification (Lₖ):

▪ Identify frequent k-itemsets (Lₖ) from Cₖ by selecting those whose
support count meets or exceeds min_sup * Total_Transactions.
3. Rule Generation:
o Once all frequent itemsets (L = L₁ ∪ L₂ ∪ ... ∪ Lₘₐₓ) are found, generate
association rules from them.
o For each frequent itemset f ∈ L (where f has at least 2 items):
▪ Generate all possible non-empty proper subsets s of f.
▪ For each such subset s, form a rule s → (f - s).
▪ Calculate the confidence of this rule: conf(s → (f - s)) = supp(f) /
supp(s).
▪ If the confidence ≥ min_conf, then keep the rule.
o Efficient Rule Generation: Rule generation can also leverage an Apriori-like
property: If a rule X → (Y - X) does not satisfy the confidence threshold,
then any rule X' → (Y - X') where X' is a subset of X also will not satisfy the
confidence threshold (for fixed Y). This allows for pruning during rule
generation. More commonly, for a frequent itemset I, if a rule (I-S) -> S is
low confidence, then any rule (I-S') -> S' where S' is a subset of S will also be
low confidence.

Example of Apriori Algorithm:

Apriori Algorithm Numerical example

Transaction ID Items
T1 I1, I3, I4
T2 I2, I3, I5, I6
T3 I1, I2, I3, I5

84
Data Science Tawqeer ul Islam

T4 I2, I5
T5 I1, I3, I5
The above dataset for the apriori algorithm numerical example contains five transactions
having transaction IDs T1, T2, T3, T4, and T5. In the transactions, it contains six different
items namely I1, I2, I3, I4, I5, and I6. Let us now use the apriori algorithm to find
association rules from the above dataset. For our numerical example, we will use the
minimum support count of 2 and minimum confidence of 75 percent.
To help us calculate the support of the itemsets, we will create a matrix representing the
presence of items in a transaction as shown below.

I1 I2 I3 I4 I5 I6
T1 1 0 1 1 0 0
T2 0 1 1 0 1 1
T3 1 1 1 0 1 0
T4 0 1 0 0 1 0
T5 1 0 1 0 1 0
Transaction Matrix
The above matrix contains Items on the horizontal axis and transaction IDs on the vertical
axis. If an item is present in a transaction, the corresponding cell is set to 1. Otherwise, it
is set to 0. We will use this matrix to calculate the support count of itemsets as it is easier
to scan this matrix compared to the transaction dataset.
To calculate the support count of any given itemset using the above matrix, we will
find the number of rows in which all the items in the given itemset are set to 1.
Create Frequent Itemsets With One Item
The Apriori algorithm starts by creating candidate itemsets with one item. For this, let us
calculate the support count of each item.

Itemset Support Count

{I1} 3
{I2} 3
{I3} 4
{I4} 1
{I5} 4
{I6} 1
Candidate Itemsets with one item
The above table contains the support count of candidate itemsets with one item. Here,
you can observe that the itemsets {I4} and {I6} have support count 1 which is less than the
minimum support count 2. Hence, we will omit these itemsets from the above table. After
this, we will get the table containing frequent itemsets with a single item as shown below.

Itemset Support Count

{I1} 3
{I2} 3
{I3} 4
{I5} 4
Frequent itemsets with one item

85
Data Science Tawqeer ul Islam

Now that we have created frequent itemsets containing a single item, we will move to
calculate the frequent itemsets with two items.
Create Frequent Itemsets With Two Items
To create frequent itemsets with two items, we will first create the candidate itemset
with two items. For this, we will join all the frequent itemsets with one item with each
other. After joining, we will get the following itemsets.
{I1,I2}, {I1,I3}, {I1,I5},{I2,I3},{I2,I5}, and {I3,I5}
After creating the itemsets with two items, we need to prune the itemsets having subsets
that are not frequent itemsets. As the {I1}, {I2}, {I3}, and {I5} all are frequent itemsets, no
itemsets will be removed from the above list while pruning.
As the next step, we will calculate the support count of each itemset having two items to
create the candidate itemset. The result is tabulated below.

Itemset Support Count

{I1,I2} 1
{I1,I3} 3
{I1,I5} 2
{I2,I3} 2
{I2,I5} 3
{I3,I5} 3
Candidate itemsets with two items
In the above candidate itemset, you can observe that the itemset {I1, I2} has the support
count 1 which is less than the minimum support count. Hence, we will remove the above
itemset from the table and obtain the table containing frequent itemsets with two items
as shown below.

Itemset Support Count

{I1,I3} 3
{I1,I5} 2
{I2,I3} 2
{I2,I5} 3
{I3,I5} 3
Frequent itemsets with two items
Now, we have calculated frequent itemsets with two items. Let us calculate the frequent
itemsets with three items.
Calculate Frequent Itemsets With Three Items
To calculate the frequent itemsets with three items, we first need to calculate the
candidate set. For this, let us first join the frequent itemsets with two items and create
itemsets with three items as shown below.
{I1, I3, I5}, {I1, I2, I3}, {I1, I2, I5}, {I2, I3, I5}
On the above itemsets, we will perform pruning to remove any itemset that has a subset
that is not a frequent itemset. For this, we will create subsets of 2 items for each itemset
and check if they are frequent itemsets or not. All the subsets of the above itemsets are
tabulated below.

86
Data Science Tawqeer ul Islam

Itemset Subsets All the subsets are frequent itemsets?

{I1, I3, I5} {I1, I3},{I1, I5},{I3, I5} Yes
{I1, I2, I3} {I1, I2}, {I1, I3}, {I2, I3} No
{I1, I2, I5} {I1, I2},{I1, I5},{I2, I5} No
{I2, I3, I5} {I2, I3}, {I2, I5}, {I3, I5} Yes
Pruning itemsets with three items
In the table, you can observe that the itemset {I1,I2 , I3} and {I1, I2, I5} contain the itemset
{I1, I2} which is not a frequent itemset. Hence, we will prune the itemsets {I1, I2, I3} and
{I1, I2, I5}. After this, we will get the itemsets {I1, I3, I5} and {I2, I3, I5} as candidate itemsets
for the itemsets having three items. Let us calculate their support count.

Itemset Support Count

{I2, I3, I5} 2

{I1, I3, I5} 2
Candidate itemsets with three items
In the above table, both itemsets have a support count of 2 which is equal to the minimum
support count. Hence, both itemsets will be considered frequent itemsets.

Itemset Support Count

{I2, I3, I5} 2
{I1, I3, I5} 2
Frequent itemsets with three items
Calculate Frequent Itemsets With Four Items
Now, we will calculate the frequent itemsets with four items. For this, we will first join
the items in the frequent itemsets with three items to create itemsets with four items. We
will get only one itemset as shown below.
{I1, I2, I3, I5}
The above itemset has four subsets with three elements i.e. {I2, I3, I5},{I1, I3, I5}, {I1, I2,
I5}, {I1, I2, I3}. In these itemsets, {I1, I2, I5} and {I1, I2, I3} are not frequent itemsets.
Hence, we will prune the itemset {I1, I2, I3, I5}. Thus, we have no candidate set for
itemsets with 4 items. Hence, the process of frequent itemset generation stops here.
Now, let us tabulate all the frequent itemsets created in this numerical example on the
apriori algorithm.

Itemset Support Count

{I1} 3
{I2} 3
{I3} 4
{I5} 4
{I1,I3} 3
{I1,I5} 2
{I2,I3} 2
{I2,I5} 3
{I3,I5} 3
{I2, I3, I5} 2

87
Data Science Tawqeer ul Islam

{I1, I3, I5} 2

Frequent itemsets in the dataset
The above table contains all the frequent itemsets in the given transaction data. We will
now create association rules using the frequent itemsets.
Generate Association Rules From Frequent Itemsets
To create association rules from the frequent itemsets, we will select each itemset. Then,
we will select a subset from the itemset and make it an antecedent of the association
rule. We will make the rest of the items as the consequent of the association rule. All the
association rules that can be generated from the frequent itemsets are shown in the
following table.

Itemset Association Rules

{I1} x
{I2} x
{I3} x
{I5} x
{I1,I3} {I1}->{I3}, {I3}->{I1}
{I1,I5} {I1}->{I5}, {I5}->{I1}
{I2,I3} {I2}->{I3}, {I3}->{I2}
{I2,I5} {I2}->{I5}, {I5}->{I2}
{I3,I5} {I3}->{I5}, {I5}->{I3}
{I2, I3, I5} {I2}->{I3, I5}, {I3}->{I2, I5}, {I5}->{I2, I3}, {I2, I3}->{I5}, {I2, I5}->{I3}, {I3, I5}->{I2}
{I1, I3, I5} {I1}->{I3, I5}, {I3}->{I1, I5}, {I5}->{I1, I3}, {I1, I3}->{I5}, {I1, I5}->{I3}, {I3, I5}->{I1}
Association rules
You can observe that we got 23 association rules from the frequent itemsets. Now, we will
calculate the confidence of each association rule to find the most important association
rules. I have already discussed how to calculate the confidence of a given association rule
above. The confidence of each rule is tabulated below.

Association Rule Confidence

{I1}->{I3} 100%
{I3}->{I1} 75%
{I2}->{I3} 66.67%
{I3}->{I2} 50%
{I1}->{I5} 66.67%
{I5}->{I1} 50%
{I2}->{I5} 100%
{I5}->{I2} 75%
{I3}->{I5} 75%
{I5}->{I3} 75%
{I2}->{I3, I5} 66.67%
{I3}->{I2, I5} 50%
{I5}->{I2, I3} 50%
{I2, I3}->{I5} 100%

88
Data Science Tawqeer ul Islam

{I2, I5}->{I3} 66.67%

{I3, I5}->{I2} 66.67%
{I1}->{I3, I5}, 66.67%
{I3}->{I1, I5}, 50%
{I5}->{I1, I3}, 50%
{I1, I3}->{I5}, 66.67%
{I1, I5}->{I3}, 100%
{I3, I5}->{I1}, 66.67%
Association rules with confidence
In the above table, we have calculated the confidence of all the association rules. Now,
we have put the minimum threshold of confidence as 75%. Hence, we will delete all the
association rules having the confidence of less than 75%. Finally, we will get the following
association rules.
Confidence({I1}->{I3}) = Percentage of transactions which contain I1, then there is I3 also
in that transaction.
= Support (I1 U I3) / Support (I1)
= 3/3 = 1 = 100%

Association Rule Confidence

{I1}->{I3} 100%
{I3}->{I1} 75%
{I2}->{I5} 100%
{I5}->{I2} 75%
{I3}->{I5} 75%
{I5}->{I3} 75%
{I2, I3}->{I5} 100%
{I1, I5}->{I3}, 100%
Association rules with confidence of more than 75%
Thus, we have calculated the association rules with their confidence using the apriori
algorithm numerical example.

Advantages of Apriori:
• Relatively simple and easy to understand.
• Uses the Apriori property effectively to prune a vast number of candidate itemsets.
Disadvantages of Apriori:
• Multiple Database Scans: Requires scanning the database multiple times (once for
each iteration k). This can be very costly for large databases.
• Large Number of Candidates: Can generate a huge number of candidate itemsets,
especially for dense datasets or low min_sup values, even with pruning. The "join"
and "prune" steps for candidate generation can be computationally intensive.
• Inefficient for long frequent patterns.

89
Data Science Tawqeer ul Islam

Improvements and Alternatives:

• FP-Growth (Frequent Pattern Growth): A more efficient algorithm that avoids
candidate generation and uses a compact tree structure (FP-tree) to store frequent
itemset information. Requires only two database scans.
• Eclat: Uses a vertical data format and intersection-based approach.
• Techniques to reduce database scans or optimize candidate generation.

90