Module 3

Topic 1: Limitations of Linear Regression and k-NN for Spam Filtering

In the data science process, selecting the right algorithm is essential. While Linear Regression
and k-Nearest Neighbours (k-NN) are powerful tools, they are theoretically and practically
ill-suited for the specific challenges of text-based spam filtering.

Question 1: Illustrate why Linear Regression and k-Nearest Neighbors (k-NN) are poor
choices for filtering spam. (10 Marks)
1. Context of the Spam Problem Spam filtering is a binary classification problem where the
goal is to assign a label of 1 (Spam) or 0 (Ham). Text data presents a massive feature space; for
a corpus of 10,000 emails, there may be 100,000 unique words acting as features.
2. Why Linear Regression is a Poor Choice
●​ Non-Binary Output: Linear Regression is designed for modeling continuous numeric
outcomes. In a spam context, it might output values such as 0.57 or even values below

0 or above 1, which lack a direct probabilistic interpretation without an arbitrary threshold.

●​ The Matrix Inversion Problem (P>N): Mathematically, solving linear regression

involves inverting a feature matrix. When the number of features (P=100,000 words)

greatly exceeds the number of observations (N=10,000 emails), the matrix is not
invertible, making the standard mathematical solution impossible.
●​ Extreme Overfitting: Even if one attempts to limit the words used, the model is likely to
"memorize" the noise in the specific training emails rather than learning generalizable
patterns of spam.

3. Why k-Nearest Neighbors (k-NN) is a Poor Choice

●​ The Curse of Dimensionality: In a 100,000-dimensional word space, the concept of
"closeness" breaks down. Mathematically, even the "nearest" neighbors in such a vast
space are extremely far apart, making similarity-based labels unreliable.
●​ Computational and Memory Costs: k-NN is an "expensive" algorithm at runtime
because it does not "learn" a compact model. To classify a single new email, the system
must calculate the distance to every single training email in memory. For real-time
filtering, this is too slow and resource-intensive.

4. R Code Illustration (Conceptual Failure) The following R code demonstrates why using
lm() (Linear Model) is inappropriate for binary labels compared to more suitable classifiers.
# --- Conceptual failure of Linear Regression for Spam ---
# Imagine we have word counts for 'viagra' and 'meeting' and binary labels
# spam_data <- [Link](viagra=c(1, 0, 5, 0), meeting=c(0, 1, 0, 4), label=c(1, 0, 1, 0))

# Linear Regression (Inappropriate)

# Using lm() for a binary target can result in predictions outside [16]
lm_model <- lm(label ~ viagra + meeting, data = spam_data)
predict(lm_model, newdata = [Link](viagra=10, meeting=0))
# Result might be 1.5, which is not a valid probability for 'Spam'.

# --- Computational failure of k-NN ---

library(class)
# If 'train_matrix' has 100,000 columns (words), this will be extremely slow
# predicted <- knn(train = train_matrix, test = new_email, cl = labels, k = 5)

Conclusion Linear Regression fails due to its continuous output and matrix inversion issues
(P>N), while k-NN fails due to the curse of dimensionality and runtime complexity. Data
scientists instead prefer Naïve Bayes or Logistic Regression for this task.

Topic 2: The Naïve Bayes Algorithm

Question 2: Explain the concept of Naïve Bayes algorithm with relevant equations and a
suitable example. (10 Marks)
Answer:
1. Concept Overview Naïve Bayes is a probabilistic classifier based on Bayes’ Law. It is
"naïve" because it assumes that the presence of one word in an email is independent of the
presence of any other word. This simplifies the complex problem of text classification into a
simple counting exercise.
2. Key Equations
Bayes’ Law: Calculates the probability of a class c given a word x:
3. Illustrative Example: The Word "Meeting" Based on Enron email data:
●​ Priors: If there are 1,500 spam and 3,672 ham emails, P(Spam)≈0.29.
●​ Likelihoods: If "meeting" appears in 16 spam emails and 153 ham emails, we find
P(meeting∣Spam)=0.0106 and P(meeting∣Ham)=0.0416.
●​ Result: Plugging these into Bayes' Law shows that "meeting" is a strong indicator of
Ham, with a P(Spam∣meeting) of only 9%.

4. R Implementation for Naive Bayes The prescribed textbook demonstrates R implementation

for classifying text (New York Times articles) using the RTextTools package:
# Load required libraries for text classification
require(RTextTools)

# 1. Create a Document-Term Matrix (DTM) from the text body

# This tokenizes the text, removes stop words, and stems words
doc_matrix <- create_matrix(email_data$body, language="english",
removeNumbers=TRUE, removeStopwords=TRUE, stemWords=TRUE)

# 2. Create a container for training and testing

# theOrder is a randomized index for a 50/50 or 80/20 split
container <- create_container(matrix=doc_matrix, labels=email_data$Section,
trainSize=1:800, testSize=801:1000, virgin=FALSE)

# 3. Train the Naive Bayes Model

model <- train_model(container, "NB")
# 4. Classify the test data
results <- classify_model(container, model)

Topic 3: Laplace Smoothing in Naïve Bayes

In text classification, we often encounter the "zero-frequency problem." This occurs when a word
appears in the test data that was never seen in the training data for a specific class, leading to a
probability of zero that can ruin the entire calculation.

Question 3: Elaborate on the purpose of Laplace Smoothing in Naïve Bayes, and why is it
important in avoiding probabilities of 0 or 1? (10 Marks)
Answer:
1. Definition and Purpose Laplace Smoothing (also known as additive smoothing) is a
technique used to "smooth" categorical data by adding a small positive value to the frequency
counts of features. Its primary purpose is to ensure that every word in a corpus has a non-zero
probability, even if it was not observed in the training set for a particular category (Spam or Ham).

2. The Zero-Probability Problem Naïve Bayes calculates the probability of an email being spam
by multiplying the individual probabilities of every word it contains. Mathematically:

If a single word (e.g., "Viagra") never appeared in the "Ham" training set, its probability
P(Viagra∣Ham) becomes 0. Because of the product rule, the entire probability for the "Ham"
class becomes zero, regardless of how many other "Ham-like" words are in the email. Laplace
Smoothing prevents this mathematical collapse.
3. Mathematical Equation for Smoothing The smoothed estimate for the probability of a word
(θjc) is calculated as:

4. Importance of Avoiding Probabilities of 0 or 1

●​ Prevents Overconfidence: Without smoothing, a model might decide that the presence
of one specific word means there is a 100% chance of spam or a 0% chance of ham.
This is a form of overfitting where the model "memorizes" the training data rather than
learning general patterns.
 ●​ Numerical Stability: Small "pseudocounts" (like α=1/5) keep the filter from being
overzealous while still allowing it to learn from new data.
●​ Enables Log-Sum Calculations: In practice, we use the sum of logs of probabilities to
avoid tiny numbers. Since log(0) is undefined, smoothing is required to make the math
work.

5. R Code Illustration While many R libraries like RTextTools handle this internally, you can
see the logic of adding "pseudocounts" when calculating log-odds:
# Conceptual R logic for Laplace Smoothing
# n_jc = occurrences of 'word' in Spam
# n_c = total words in Spam
# alpha = 1 (pseudocount)
# beta = 2 (for binary outcome adjustment)

# Standard calculation (No Smoothing - Risk of 0)

# prob_word_spam <- n_jc / n_c

# Laplace Smoothed calculation (prevents 0)

alpha <- 1
beta <- 2
theta_jc <- (n_jc + alpha) / (n_c + beta)

# Used in log-odds calculation to avoid log(0)

# w_jc <- log(theta_jc / (1 - theta_jc))

Topic 4: Comparing Naïve Bayes to k-Nearest Neighbors (k-NN)

While both algorithms are used for supervised learning tasks like classification, they operate on
fundamentally different mathematical and computational principles.

Question 4: Compare and contrast Naïve Bayes and k-Nearest Neighbors (k-NN)
algorithms in the context of classification. (10 Marks)
Answer:
1. Classification Methodology
●​ Naïve Bayes: This is a linear classifier based on probabilistic theory (Bayes’ Law). it
calculates the probability of each class based on the frequency of features in the training
data and assigns the label with the highest probability.
 ●​ k-NN: This is a non-parametric, non-linear classifier. It does not use a formula to
"learn" a model; instead, it looks at the k most similar labeled examples in the feature
space and assigns a label based on a majority vote.

2. Training vs. Runtime Efficiency

●​ Training Phase: Naïve Bayes requires a training phase where it "learns" by counting
occurrences of features (e.g., words in an email). k-NN requires no training; it simply
stores the dataset in memory, which is why it is often called a "lazy learner".
●​ Runtime Phase: Naïve Bayes is extremely fast at runtime because it only needs to
perform simple multiplications or additions (of logs). k-NN is computationally expensive
at runtime because it must calculate the distance between the new data point and every
single point in the training set.

3. Handling High-Dimensional Data

●​ Curse of Dimensionality: k-NN performs poorly in high-dimensional spaces (like text
classification with 100,000 words) because the "nearest" neighbors become
mathematically very far apart, making distance metrics unreliable.
●​ Dimensionality Resilience: Naïve Bayes performs remarkably well with large feature
sets and high dimensionality, making it the preferred choice for tasks like spam filtering.

4. Performance and Memory

●​ Memory Usage: k-NN requires keeping the entire training dataset in memory at
runtime to calculate distances. Naïve Bayes only needs to store a compact set of weights
or probabilities (the "model"), which takes up very little space.
●​ Overfitting: k-NN is highly sensitive to noise and local variations if k is too small. Naïve
Bayes can also overfit if data is biased, but techniques like Laplace Smoothing help it
generalize better.

5. R Implementation Comparison The following code highlights the different function calls used
for these algorithms in R.
# --- k-NN Implementation (Lazy Learning) ---
library(class)
# Requires all training data (train_x) and labels (train_y) at runtime
# predicted_knn <- knn(train = train_x, test = test_x, cl = train_y, k = 5)

# --- Naïve Bayes Implementation (Model Training) ---

# Using RTextTools as discussed in the textbook
require(RTextTools)
# 1. Train a model from a container
# model_nb <- train_model(container, "NB")
# 2. Classify using the pre-trained model (Fast runtime)
# results_nb <- classify_model(container, model_nb)

Topic 5: Scraping the Web

Data science often begins with data that is not readily available in a CSV or database. Data
scientists must often "scrape" this data from the web using various tools.

Question 5: Describe the various tools and methodologies used for scraping data from
the web as part of the data science process. (10 Marks)
Answer:
1. Application Programming Interfaces (APIs) The most standard and efficient way to gather
web data is through APIs provided by websites (e.g., The New York Times API). APIs allow
developers to download data in standardized formats like JSON.
●​ Methodology: A developer registers for a "key" (a password) and writes scripts to query
the website’s database directly.

2. Yahoo! Query Language (YQL) Because different websites provide different JSON formats,
YQL is used to standardize the process. It allows data scientists to write SQL-like queries to
fetch data from various APIs, providing a single, consistent output format that is easy to parse.
3. HTML Inspection and Manual Scraping When no API is available, data scientists use tools
like the Firebug extension (or modern browser Inspect elements) to map the HTML structure of
a page.
●​ Methodology: After identifying the specific HTML tags containing the data, shell utilities
like curl, wget, grep, awk, and perl can be used to extract the text in a
"quick-and-dirty" fashion.

4. Specialized Scraping Libraries For more systematic and robust scraping, specific
programming libraries are used:
●​ Beautiful Soup: A robust Python library that is excellent for navigating and parsing
HTML, though it can be slow for very large tasks.
●​ Mechanize: A tool that allows scripts to interact with websites as if they were a browser
(e.g., clicking buttons), though it typically does not parse JavaScript.
●​ RTextTools: In R, this is used to tokenize and process the text once it has been scraped.

5. Ethics and Terms of Service A critical part of the scraping methodology is reviewing the
Terms of Service of a website's API. Many sites limit the frequency of requests (rate limiting) or
prohibit the scraping of specific types of content.
 Topic 6: Overfitting and its Prevention

Overfitting occurs when a model "memorizes" the specific noise and details of the training data
rather than learning general patterns that apply to new, unseen data.

Question 6: Explain overfitting in a real-world scenario, and what strategies can be

implemented to prevent it? (10 Marks)
Answer:
1. Conceptual Overview Overfitting is the phenomenon where a model fits the training data too
closely, capturing random fluctuations or "noise" as if they were legitimate signals. While the
model might show 100% accuracy on training data, it performs poorly on test data because it has
failed to generalize.
2. Real-World Scenario: Breast Cancer Detection In a real-world data mining competition for
breast cancer detection, a model achieved suspiciously high predictive power. Upon
investigation, it was found the model had "learned" that certain Patient IDs were assigned
sequentially by different clinics. Since some clinics treated sicker patients, the model used the ID
number as a predictor for cancer.
●​ The Overfit: This is a classic case of data leakage and overfitting. The model didn't
learn about biology; it learned an artifact of the data collection process that would not
exist for a new patient in a different clinic.

3. Strategies to Prevent Overfitting

●​ Cross-Validation: Divide the data into a training set (80%) and a test set (20%). Fit the
model on the training set and evaluate its performance on the test set. If the error on the
test set is much higher, the model is overfitting.
●​ Regularization (Penalty Terms): Impose a "prior" that coefficients should not be too
large. By adding a penalty term (like λ) to the loss function, we artificially make the model
simpler and more robust.
●​ Reducing Model Complexity: Avoid using too many features relative to the number of
observations (P>N). For algorithms like Decision Trees, "pruning" the tree to a certain
depth prevents it from creating overly specific rules for noise.
●​ Using More Data: Often, as the sample size increases, the best-performing algorithm
changes, and the risk of the model being misled by small-scale noise decreases.

Topic 7: Logistic Regression and the M6D Case Study

Logistic regression is the standard tool for binary classification (Yes/No, 1/0) because it models
the probability of an event.
Question 7: Summarize the concept of Logistic Regression with its underlying math and
describe how it is applied in the M6D Case Study. (10 Marks)
Answer:
1. Conceptual Overview Unlike Linear Regression, which can predict values above 1 or below
0, Logistic Regression uses the inverse-logit function to output a value between 0 and 1,
representing a probability.
2. Underlying Math

where α is the base rate and β is the vector of weights for features like user behavior.

Parameter Estimation: Since there is no simple formula to find α and β, we use

Maximum Likelihood Estimation (MLE) to find parameters that make the observed
data most probable. This is solved via optimization methods like Newton's Method or
Stochastic Gradient Descent.

3. Application: M6D Case Study Media 6 Degrees (M6D) uses logistic regression to solve
user-level conversion prediction (predicting if a user will click a shoe ad).
●​ Features: They take a user's browsing history and hash the URLs into strings (e.g.,
<fxyz, 123>).
●​ Matrix: They build a massive sparse matrix where each row is a user and each column
is a visited site.
●​ Goal: The model outputs the probability of a click. If the probability exceeds a threshold
(e.g., 0.75), they show the ad.

4. R Implementation In R, we use the glm (Generalized Linear Model) function:

# Logistic Regression in R
# 'click' is the binary target (0 or 1)
# 'binomial' family with 'logit' link function handles the math
fit <- glm(click ~ url_1 + url_2 + url_3,
data = training_data,
family = binomial(logit))

# Predict probability for a new user

prob <- predict(fit, newdata = new_user, type = "response")
``` [28, 29]