Machine Learning — Comprehensive Study Notes | All 15 Topics

MACHINE LEARNING
Comprehensive Study Notes
8-Mark Essay Answers with Diagrams and Examples

15 Topics Covered:
1. Decision Trees for Classification and Regression
2. Decision Trees Properties and Impurity Measures
3. Bias–Variance Trade-off and Random Forests
4. Bayes Classifier and Bayes' Rule
5. Class Conditional Independence and Naive Bayes
6. Linear Discriminants for Classification
7. Perceptron Classifier and Learning Algorithm
8. Support Vector Machines (Non-Separable, Kernel Trick)
9. Linear Models (Logistic and Linear Regression)
10. Multi-Layer Perceptrons and Backpropagation
11. Introduction to Clustering
12. Matrix Factorization and Spectral Clustering
13. Fuzzy C-Means and K-Means Clustering
14. Expectation Maximization-Based Clustering
15. Rough Clustering and Rough K-Means Algorithm

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 1

Machine Learning — Comprehensive Study Notes | All 15 Topics

1. Decision Trees for Classification and Regression

Decision Trees are one of the most intuitive and widely used supervised machine learning algorithms.
They model decisions and their possible consequences in a tree-like structure, where each internal
node represents a test on an attribute, each branch represents the outcome of the test, and each leaf
node represents a class label (classification) or a continuous value (regression). Decision trees can be
applied to both classification and regression tasks without requiring feature scaling or normalization.

Structure of a Decision Tree

A decision tree consists of:
• Root Node: The topmost node representing the entire dataset, which is split using the best
feature.
• Internal Nodes (Decision Nodes): Intermediate nodes that represent tests on features/attributes.
• Branches: Edges connecting nodes, representing the outcome of a test condition.
• Leaf Nodes (Terminal Nodes): The final nodes that provide the prediction — a class label in
classification or a numeric value in regression.

[Root: Outlook?]
/ | \
Sunny Overcast Rainy
/ | \
[Humidity?] [Play: YES] [Wind?]
/ \ / \
High Normal Strong Weak
| | | |
NO (Leaf) YES (Leaf) NO YES

Figure 1: A simple decision tree for the 'Play Tennis' classification problem.

Decision Trees for Classification

In classification, the goal is to assign each input to one of a discrete set of categories. The tree is built
by recursively splitting the training data based on feature values to maximize class purity. At each leaf
node, the majority class of the training samples that reach it is assigned as the prediction.

Example: Email Spam Classification

Input features: email length, presence of '$' symbol, number of exclamation marks, sender
reputation. The tree might first split on 'sender reputation' (trusted/unknown), then on
presence of '$', etc., ultimately predicting SPAM or NOT SPAM at each leaf.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 2

Machine Learning — Comprehensive Study Notes | All 15 Topics

The splitting criteria used in classification trees include Gini Impurity and Information Gain (Entropy). A
node is considered pure if all samples belong to the same class. The tree-building algorithm (such as
ID3, C4.5, or CART) searches for the feature and threshold that best separates the classes at each
step.

Decision Trees for Regression

In regression tasks, the output is a continuous numeric value rather than a class label. The tree
structure is identical, but the leaf nodes now store the mean (or median) of all training samples that
reach that leaf, rather than a class label. The splitting criterion changes to minimize variance or mean
squared error within each subset.

Prediction at leaf = mean(y_i) for all samples i in that leaf

MSE = (1/n) * Σ(y_i - ŷ)²

Variance Reduction = Var(parent) - [Weighted Avg of Var(children)]

Example: House Price Prediction

Features: bedrooms (1-5), location (urban/suburban/rural), area (sq ft). Root split: area >
2000 sq ft? Left branch leads to smaller houses (predicted price: $200K), right branch
further splits on location, arriving at leaf values like $450K or $600K.

Tree Building Algorithms

Algorithm Description / Key Property
ID3 Uses Information Gain (entropy-based). Handles only categorical features. Greedy
top-down approach.
C4.5 Extension of ID3; handles continuous features, missing values, and uses Gain Ratio
to avoid bias.
CART Classification and Regression Trees. Uses Gini Impurity for classification, MSE for
regression. Produces binary splits only.
CHAID Chi-square Automatic Interaction Detection. Uses chi-square tests. Supports multi-
way splits.

Stopping Criteria and Pruning

Unconstrained tree growth leads to overfitting, where the tree memorizes training data but performs
poorly on unseen data. Several stopping criteria and pruning methods are used to control tree
complexity:

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 3

Machine Learning — Comprehensive Study Notes | All 15 Topics

• Pre-pruning (Early Stopping): Stop splitting when a node has fewer than min_samples,
maximum depth is reached, or the information gain is below a threshold.
• Post-pruning (Reduced Error Pruning): Grow the full tree first, then remove sub-trees that do not
improve validation performance.
• Cost Complexity Pruning (Alpha Pruning): Used in CART; adds a complexity parameter alpha to
penalize tree size.

Advantages and Disadvantages

Decision trees offer clear advantages: they are interpretable (white-box models), require no feature
normalization, handle both numerical and categorical data, and naturally model non-linear relationships.
However, they are prone to overfitting, sensitive to small changes in data (high variance), and can be
biased toward features with more levels. These limitations are largely addressed by ensemble methods
like Random Forests.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 4

Machine Learning — Comprehensive Study Notes | All 15 Topics

2. Decision Trees Properties and Impurity Measures

The effectiveness of a decision tree depends critically on the quality of its splitting criteria — the
impurity measures. Impurity measures quantify how mixed or homogeneous a node is with respect to
the target class labels. The goal of each split is to reduce impurity as much as possible, guiding the tree
toward producing pure leaf nodes.

Key Properties of Decision Trees

• Non-parametric: No assumptions about data distribution are required.
• Greedy Algorithm: At each step, the locally optimal split is chosen — there is no backtracking.
• Recursive Partitioning: The feature space is partitioned into hyper-rectangular regions
recursively.
• Axis-aligned splits: Standard decision trees split along a single feature at a time.
• Handles mixed data: Both continuous and categorical features can be handled.

Impurity Measures
Three primary impurity measures are used in practice: Entropy (Information Gain), Gini Index, and
Classification Error. Each quantifies the degree of disorder in a node.

1. Entropy and Information Gain

Entropy, borrowed from information theory, measures the uncertainty or disorder in a set. For a node
with K classes where class k has proportion p_k:

Entropy(S) = -Σ p_k * log₂(p_k)

Information Gain(S, A) = Entropy(S) - Σ [|S_v|/|S|] * Entropy(S_v)

A node is pure (entropy = 0) if all samples belong to one class. Maximum entropy occurs when classes
are equally distributed. Information Gain measures the reduction in entropy achieved by splitting on
attribute A.

Example: Entropy Calculation

Node has 10 samples: 5 class A, 5 class B. Entropy = -(0.5 * log2(0.5)) - (0.5 * log2(0.5)) = -
(-0.5) - (-0.5) = 1.0 bits (maximum disorder). After a perfect split: 5 class A (entropy=0) and
5 class B (entropy=0). Information Gain = 1.0 - (0.5*0 + 0.5*0) = 1.0 bit (maximum gain).

2. Gini Impurity

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 5

Machine Learning — Comprehensive Study Notes | All 15 Topics

Gini Impurity, used in the CART algorithm, measures the probability that a randomly chosen sample
would be incorrectly classified if it were randomly labeled according to the class distribution. It ranges
from 0 (pure) to 0.5 (maximum impurity for binary case).

Gini(S) = 1 - Σ p_k²

Gini Gain = Gini(parent) - Σ [|S_v|/|S|] * Gini(S_v)

Example: Gini Calculation

Node: 4 samples of class A, 6 of class B (10 total). p_A = 0.4, p_B = 0.6. Gini = 1 - (0.4² +
0.6²) = 1 - (0.16 + 0.36) = 1 - 0.52 = 0.48

3. Classification Error
Classification error is the simplest impurity measure — the fraction of samples that do not belong to the
majority class:

Classification Error(S) = 1 - max_k(p_k)

Although intuitive, classification error is less sensitive to changes in class proportions than entropy or
Gini, making it a weaker criterion for building trees. It is therefore rarely used for splitting.

Comparison of Impurity Measures

Impurity
1.0 | Entropy (scaled 0.5)
0.5 | ......... Gini
0.3 | . . . . . Misclass.
0.0 |__________________________
0.0 0.25 0.5 0.75 1.0
Class Probability p

Figure 2: Comparison of impurity measures for binary classification as a function of class probability.

Measure Properties
Entropy Logarithmic; ranges 0 to log2(K); more sensitive near p=0.5; preferred by ID3,
C4.5.
Gini Quadratic; ranges 0 to 0.5 (binary); computationally cheaper; used by CART;
slightly biased toward larger partitions.
Class. Error Linear; ranges 0 to (1-1/K); too flat near extremes; rarely used for splitting.

Gain Ratio
Information Gain has a bias toward features with many distinct values (e.g., a unique ID feature would
have maximum information gain but no predictive value). C4.5 addresses this with the Gain Ratio:

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 6

Machine Learning — Comprehensive Study Notes | All 15 Topics

SplitInfo(A) = -Σ [|S_v|/|S|] * log₂(|S_v|/|S|)

GainRatio(S, A) = InformationGain(S, A) / SplitInfo(A)

SplitInfo penalizes attributes with many distinct values. Gain Ratio normalizes the information gain by
the entropy of the split, producing a more balanced criterion.

Variance Reduction for Regression Trees

For regression tasks (CART), the impurity is measured by the variance (or MSE) of the target values in
each node. The best split minimizes the weighted variance of the resulting child nodes:

Variance(S) = (1/|S|) * Σ(y_i - ȳ)²

Reduction = Var(S) - [(|S_L|/|S|)*Var(S_L) + (|S_R|/|S|)*Var(S_R)]

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 7

Machine Learning — Comprehensive Study Notes | All 15 Topics

3. Bias–Variance Trade-off and Random Forests for

Classification and Regression

The Bias-Variance trade-off is one of the most fundamental concepts in machine learning. It provides a
framework for understanding the sources of prediction error and guides the selection of model
complexity. Random Forests leverage this understanding to build powerful ensemble models that
achieve low bias and low variance simultaneously.

Bias–Variance Decomposition
For a regression model, the expected prediction error at a point x can be decomposed as:

Expected Error = Bias² + Variance + Irreducible Noise

E[(y - ŷ)²] = [E[ŷ] - f(x)]² + E[(ŷ - E[ŷ])²] + σ²

• Bias: The error from erroneous assumptions in the learning algorithm. High bias → underfitting
(model too simple).
• Variance: The error from sensitivity to small fluctuations in training data. High variance →
overfitting (model too complex).
• Irreducible Noise (σ²): The noise inherent in the data that cannot be reduced regardless of the
model.

Error Total Error

|\ /
| \ /
| \ Optimal /
| \ . . . . ./
|Bias²\ /Variance
|______\_____/_____________
Low High Model Complexity

Figure 3: Bias-Variance trade-off — as complexity increases, bias decreases but variance increases.

Example: Decision Tree Bias-Variance

A single full-depth decision tree has near-zero bias (it can perfectly fit training data) but very
high variance (small changes in training set lead to completely different trees). This is the
classic overfitting scenario.

Random Forests — Concept

Random Forests (Breiman, 2001) are an ensemble learning method that addresses the high variance
problem of individual decision trees. They construct a large number of decision trees during training

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 8

Machine Learning — Comprehensive Study Notes | All 15 Topics

and output the mode of classes (classification) or mean prediction (regression) of the individual trees.
The key insight is: averaging many high-variance, low-bias estimators reduces variance without
substantially increasing bias.

Key Mechanisms of Random Forests

1. Bootstrap Aggregating (Bagging)
Each tree is trained on a bootstrap sample — a random sample drawn with replacement from the
training data. Typically, each bootstrap sample contains about 63.2% of unique training instances (the
rest are Out-Of-Bag samples, useful for validation). Averaging predictions over many such trees
reduces variance.

ŷ_RF = (1/T) * Σ_t ŷ_t(x) (Regression)

ŷ_RF = majority_vote{ŷ_t(x)} (Classification)

2. Random Feature Subsampling

At each node split, only a random subset of features (typically sqrt(p) for classification, p/3 for
regression) is considered. This decorrelates the trees — without this, all trees would be highly
correlated (always splitting on the same dominant feature), and averaging them would not reduce
variance much.
Training Data (Bootstrap)
T1: [Row1, Row3, Row1, Row5, ...] -> Tree 1
T2: [Row2, Row5, Row2, Row1, ...] -> Tree 2
T3: [Row3, Row1, Row4, Row5, ...] -> Tree 3
... (T trees total) ...
Prediction = Average / Vote of all T trees

Figure 4: Random Forest ensemble construction using bootstrap sampling.

Random Forests for Classification

Each tree votes for a class. The final prediction is the class with the most votes. Random forests handle
high-dimensional data well, are robust to noise and outliers, and provide feature importance scores as
a useful byproduct. They are widely used in medical diagnosis, fraud detection, and remote sensing.

Random Forests for Regression

For regression, each tree predicts a continuous value, and the final prediction is the average across all
trees. The Out-Of-Bag (OOB) error can be used to estimate generalization error without a separate
validation set. Feature importance is computed by measuring the total decrease in node impurity
(variance reduction) contributed by each feature across all trees.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 9

Machine Learning — Comprehensive Study Notes | All 15 Topics

Bias-Variance Analysis of Random Forests

Model Bias Variance Typical Use
Single Deep Tree Low High Rarely used alone
Single Shallow Tree High Low Weak learner
Random Forest Low Low (reduced) Standard go-to model
Bagging (no feature Low Medium Less effective than RF
subsamp.)

Mathematically, if the individual tree variance is σ² and the correlation between trees is ρ, the variance
of the Random Forest prediction is approximately: ρσ² + (1-ρ)σ²/T. Random feature subsampling
reduces ρ, while more trees T further reduces variance, explaining the dual mechanism of Random
Forests.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 10

Machine Learning — Comprehensive Study Notes | All 15 Topics

4. Introduction to the Bayes Classifier and Bayes' Rule and

Inference

The Bayesian approach to classification is grounded in probability theory. It provides a principled

framework for incorporating prior knowledge and updating beliefs based on observed evidence. The
Bayes Classifier represents the optimal decision boundary in terms of minimizing classification error
under known probability distributions.

Bayes' Theorem
Bayes' Theorem describes how to update the probability of a hypothesis H given evidence E:

P(H | E) = P(E | H) * P(H) / P(E)

Posterior = (Likelihood * Prior) / Evidence

P(C_k | x) = P(x | C_k) * P(C_k) / P(x)

• P(C_k | x): Posterior probability of class C_k given input x.
• P(x | C_k): Class-conditional likelihood — probability of observing x given class C_k.
• P(C_k): Prior probability of class C_k (before observing x).
• P(x): Evidence — normalization constant ensuring probabilities sum to 1.

Example: Medical Diagnosis

Disease D has prior P(D) = 0.001 (1 in 1000 people have it). A test has sensitivity
P(Positive|D) = 0.99 and false positive rate P(Positive|¬D) = 0.05. Given a positive test:
P(D|Positive) = (0.99 × 0.001) / (0.99×0.001 + 0.05×0.999) = 0.00099 / 0.05094 ≈ 0.0194.
Despite high test sensitivity, only ~2% chance of disease!

The Bayes Optimal Classifier

The Bayes classifier assigns each input x to the class with the highest posterior probability. This
decision rule minimizes the probability of misclassification, making it the gold standard against which
other classifiers are compared:

ŷ = argmax_k P(C_k | x) = argmax_k P(x | C_k) * P(C_k)

The Bayes error rate is the lowest achievable error for a given classification problem. No classifier can
perform better than the Bayes classifier on average. In practice, the true class-conditional distributions
P(x | C_k) are unknown and must be estimated from data.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 11

Machine Learning — Comprehensive Study Notes | All 15 Topics

Decision Boundaries
The Bayes classifier creates a decision boundary where the posterior probabilities for two classes are
equal: P(C_1 | x) = P(C_2 | x). The nature of this boundary depends on the form of the class-conditional
distributions. If both classes are modeled as Gaussians with equal covariance, the boundary is linear
(Linear Discriminant). With unequal covariances, the boundary becomes quadratic (Quadratic
Discriminant).
Class 1 (o) Decision Class 2 (x)
o o o Boundary x x x
o o o o / x x x x
o o o / x x x
o o o / x x x x
/ <- P(C1|x)=P(C2|x)
MAP assigns left side to C1, right to C2

Bayesian Inference
Bayesian inference goes beyond point estimates. Instead of finding a single best model parameter θ, it
maintains a full posterior distribution over parameters given data D:

P(θ | D) = P(D | θ) * P(θ) / P(D)

This posterior can then be used to make predictions by integrating (marginalizing) over all possible
parameter values — the Bayesian predictive distribution. This naturally incorporates uncertainty, which
is crucial in safety-critical applications.

MAP vs. MLE Estimation

Approach Description
Maximum Likelihood (MLE) Find θ that maximizes P(D|θ). Ignores prior. Can overfit with small data.
Maximum A Posteriori Find θ that maximizes P(θ|D) ∝ P(D|θ)P(θ). Incorporates prior.
(MAP) Reduces overfitting.
Full Bayesian Integrate over all θ. Most principled but computationally expensive.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 12

Machine Learning — Comprehensive Study Notes | All 15 Topics

5. Class Conditional Independence and Naive Bayes

Classifier (NBC)

The Naive Bayes Classifier is a probabilistic classifier derived directly from Bayes' theorem. It makes a
strong (naive) assumption that all features are conditionally independent given the class label. Despite
this assumption often being violated in practice, Naive Bayes classifiers work remarkably well in many
real-world applications, particularly text classification.

Class Conditional Independence Assumption

Computing P(x | C_k) for high-dimensional x is generally intractable. If x has d features, each with m
values, there are m^d possible combinations. The class conditional independence assumption
simplifies this dramatically:

P(x | C_k) = P(x_1, x_2, ..., x_d | C_k)

Naive Bayes Assumption: = Π_{j=1}^{d} P(x_j | C_k)

Classification: ŷ = argmax_k P(C_k) * Π_{j=1}^{d} P(x_j | C_k)

This reduces the number of parameters to estimate from m^d to d*m per class, making Naive Bayes
computationally very efficient and capable of learning from small datasets.

Example: Email Spam Filter

Features: x1='FREE', x2='WINNER', x3='Click', x4='Meeting'. P(SPAM) = 0.4, P(HAM) =
0.6. P(FREE|SPAM)=0.8, P(FREE|HAM)=0.1; P(WINNER|SPAM)=0.7, P(WINNER|
HAM)=0.05. For email with 'FREE' and 'WINNER': P(SPAM|x) ∝ 0.4 × 0.8 × 0.7 = 0.224;
P(HAM|x) ∝ 0.6 × 0.1 × 0.05 = 0.003. Normalized: P(SPAM|x) = 0.224/0.227 ≈ 0.987 →
Classified as SPAM.

Types of Naive Bayes Classifiers

Type Use Case & Distribution
Gaussian NBC Continuous features. P(x_j|C_k) = Gaussian(μ_jk, σ_jk²). Used for numerical
data like sensor readings.
Multinomial NBC Count/frequency features. P(x_j|C_k) = multinomial. Common for text
classification (word counts).
Bernoulli NBC Binary features (0/1). P(x_j|C_k) = Bernoulli. Used for document classification
(word presence/absence).
Complement NBC Addresses class imbalance by training on complement of each class. Better
for imbalanced datasets.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 13

Machine Learning — Comprehensive Study Notes | All 15 Topics

Gaussian Naive Bayes

When features are continuous, the likelihood P(x_j | C_k) is modeled as a Gaussian distribution with
class-specific mean and variance:

P(x_j | C_k) = (1/√(2π σ²_jk)) * exp(-(x_j - μ_jk)² / (2σ²_jk))

Parameters estimated from training data:

μ_jk = mean of feature j in class k

σ²_jk = variance of feature j in class k

Laplace Smoothing
A major issue in Naive Bayes is the zero-frequency problem: if a feature value never appears with a
particular class in training data, the entire product becomes zero. Laplace (additive) smoothing
addresses this by adding a small count alpha (typically 1) to all feature counts:

P(x_j = v | C_k) = (count(x_j=v, C_k) + α) / (count(C_k) + α * |V|)

where |V| is the number of possible values for feature j. This ensures no probability is exactly zero.

Advantages and Limitations of NBC

• Fast training and prediction: O(n*d) training, O(K*d) prediction.
• Works well with small training data due to few parameters.
• Handles high-dimensional data and missing values gracefully.
• Limitation: Independence assumption is often violated (e.g., word co-occurrences in text).
• Despite violation, NBC often achieves competitive accuracy and excellent calibration of
posterior probabilities.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 14

Machine Learning — Comprehensive Study Notes | All 15 Topics

6. Introduction to Linear Discriminants and Linear

Discriminants for Classification

Linear discriminant methods find a linear function of the input features that best separates classes.
They are both a probabilistic model (derived from Gaussian assumptions) and a geometric method
(finding optimal hyperplanes). Linear Discriminant Analysis (LDA) is one of the oldest and most
powerful classification techniques.

Linear Discriminant Analysis (LDA)

LDA assumes that the class-conditional densities P(x | C_k) are multivariate Gaussians, all sharing the
same covariance matrix Σ but with different means μ_k. Under this assumption, the Bayes optimal
decision boundary between two classes is a linear hyperplane in feature space.

P(x | C_k) = N(x; μ_k, Σ) [shared covariance]

Log-posterior ratio (binary): log[P(C_1|x)/P(C_2|x)]

= (μ_1 - μ_2)ᵀ Σ⁻¹ x - ½(μ_1ᵀΣ⁻¹μ_1 - μ_2ᵀΣ⁻¹μ_2) +

log[P(C_1)/P(C_2)]

Decision: linear function of x → Linear boundary

Feature 2
^ * * * | Class 1: *
| * * * * | Class 2: o
| * * * | o o o
| | o o o o
| * * * | o o o
|_________Decision____________> Feature 1
Boundary (hyperplane)

Figure 5: LDA decision boundary — a linear hyperplane separating two Gaussian classes.

LDA as Dimensionality Reduction

LDA can also be used for dimensionality reduction by projecting data onto the directions that maximize
class separability. Fisher's Linear Discriminant finds the projection vector w that maximizes the ratio of
between-class scatter to within-class scatter:

Maximize: J(w) = (wᵀ S_B w) / (wᵀ S_W w)

S_B = Σ_k n_k (μ_k - μ)(μ_k - μ)ᵀ [Between-class scatter]

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 15

Machine Learning — Comprehensive Study Notes | All 15 Topics

S_W = Σ_k Σ_{x∈C_k} (x - μ_k)(x - μ_k)ᵀ [Within-class scatter]

Solution: w = S_W⁻¹ (μ_1 - μ_2)

Example: Iris Dataset Classification

Three classes: Setosa, Versicolor, Virginica; 4 features. LDA finds 2 discriminant directions
(K-1 = 2 for 3 classes). Projecting onto these 2 directions visually separates the three
species into clear clusters, capturing >99% of between-class variance.

Quadratic Discriminant Analysis (QDA)

When each class has its own covariance matrix Σ_k (relaxing LDA's shared covariance assumption),
the log-likelihood ratio becomes quadratic in x, producing a curved decision boundary. QDA has more
parameters (K separate covariance matrices) and requires more data.

QDA decision function: xᵀ A x + bᵀ x + c > 0

where A = ½(Σ₂⁻¹ - Σ₁⁻¹) — quadratic term

LDA vs QDA vs Logistic Regression

Model Key Difference
LDA Gaussian assumption, shared Σ, linear boundary. Works well when data is
truly Gaussian.
QDA Gaussian assumption, separate Σ_k, quadratic boundary. Better for non-
linearly separable classes.
Logistic Regression No distributional assumptions, directly models P(C|x). More robust to non-
Gaussian data.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 16

Machine Learning — Comprehensive Study Notes | All 15 Topics

7. Perceptron Classifier and Perceptron Learning

Algorithm

The Perceptron, proposed by Frank Rosenblatt in 1958, is one of the earliest and most foundational
machine learning algorithms. It is a binary linear classifier that models a single artificial neuron. While
limited to linearly separable problems, it introduced key concepts — threshold units, weight updates,
and error-driven learning — that became the foundation of modern neural networks.

Biological Motivation
The Perceptron was inspired by the biological neuron: dendrites receive multiple input signals, the cell
body integrates these signals, and the axon fires an output if the integrated signal exceeds a threshold.
The Perceptron models this as a weighted sum of inputs passed through a threshold (step) function.
x1 --[w1]-->\
x2 --[w2]--> [Σ + bias] --> [Step fn] --> ŷ (0 or 1)
x3 --[w3]-->/
bias --[1]->/
Activation: ŷ = 1 if (w·x + b) ≥ 0, else ŷ = 0

Figure 6: Perceptron architecture — weighted inputs summed with bias, passed through step function.

Perceptron Model
Formally, the Perceptron computes:

ŷ = sign(wᵀx + b) = sign(Σ_j w_j x_j + b)

ŷ = +1 if wᵀx + b ≥ 0

ŷ = -1 if wᵀx + b < 0

The weights w and bias b define a hyperplane in feature space. All points on one side are classified as
+1, the other as -1. The learning algorithm adjusts w and b to find a hyperplane that correctly classifies
all training examples.

Perceptron Learning Algorithm

The Perceptron learns by iterating through training examples and correcting misclassifications. The
update rule moves the decision boundary toward misclassified points:

For each training example (x_i, y_i):

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 17

Machine Learning — Comprehensive Study Notes | All 15 Topics

Compute ŷ_i = sign(wᵀx_i + b)

If ŷ_i ≠ y_i (misclassification):

w ← w + η * y_i * x_i

b ← b + η * y_i

η = learning rate (typically 0.01 to 1.0)

Example: Perceptron Update Example

Weights w = [0.5, -0.3], b = 0.1, η = 1.0. Input x = [1, 2], true label y = +1. Prediction: 0.5*1 +
(-0.3)*2 + 0.1 = 0.5 - 0.6 + 0.1 = 0.0 → sign(0) = 0 → WRONG. Update: w ← [0.5+1*1, -
0.3+1*2] = [1.5, 1.7]; b ← 0.1 + 1 = 1.1. New prediction: 1.5*1 + 1.7*2 + 1.1 = 6.4 > 0 →
CORRECT.

Perceptron Convergence Theorem

If the training data is linearly separable, the Perceptron Learning Algorithm is guaranteed to converge
to a solution with zero training error in a finite number of steps. Formally, if there exists a margin γ > 0
(the minimum distance from any training point to the true decision boundary), the algorithm converges
in at most (R/γ)² steps, where R = max||x_i||.
However, if the data is not linearly separable, the algorithm never converges and cycles indefinitely.
This limitation motivated the development of the Pocket Algorithm (keeps best weights seen so far) and
ultimately the multi-layer Perceptron.

Limitations and the XOR Problem

A single Perceptron cannot solve the XOR problem — where the classes are not linearly separable.
This was famously demonstrated by Minsky and Papert (1969), which briefly halted neural network
research. The solution — stacking multiple Perceptrons into multi-layer networks — eventually led to
the deep learning revolution.
XOR Truth Table: x1=0,x2=0->0 | x1=1,x2=1->0
x1=0,x2=1->1 | x1=1,x2=0->1
Feature space: (0,1)o o(1,1)
\ /
No single line separates
(0,0)x x(1,0)

Figure 7: XOR is not linearly separable — no single line can separate 0s from 1s.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 18

Machine Learning — Comprehensive Study Notes | All 15 Topics

8. Support Vector Machines (Linearly Non-Separable Case,

Non-linear SVM, Kernel Trick)

Support Vector Machines (SVMs) are powerful supervised learning models developed by Vapnik and
colleagues in the 1990s. While the basic hard-margin SVM requires linear separability, practical SVMs
handle non-linearly separable data through soft margins and non-linear feature mappings via the kernel
trick, making them one of the most versatile classifiers in machine learning.

Recap: Hard-Margin SVM

For linearly separable data, the hard-margin SVM finds the hyperplane with the maximum margin
between the two classes. The margin is 2/||w||, maximized by minimizing ||w||² subject to: y_i(wᵀx_i + b)
≥ 1 for all i. Support vectors are the training points closest to the boundary.

Soft-Margin SVM (Linearly Non-Separable Case)

Real data is rarely linearly separable. The soft-margin SVM (C-SVM) introduces slack variables ξ_i ≥ 0
that allow some points to be within the margin or even misclassified, while penalizing violations:

Minimize: (1/2)||w||² + C * Σ ξ_i

Subject to: y_i(wᵀx_i + b) ≥ 1 - ξ_i and ξ_i ≥ 0

C = regularization parameter (controls bias-variance trade-off)

• Large C: Strong penalty for violations → narrow margin, low training error, risk of overfitting.
• Small C: Tolerates more violations → wider margin, more regularization, risk of underfitting.
Example: Effect of C parameter
Dataset with overlapping classes (e.g., cancer diagnosis with noisy measurements).
C=0.01: Wide margin, many misclassified training points, but generalizes well. C=1000:
Narrow margin, nearly all training points correct, but may overfit to noise.

Non-linear SVM and the Kernel Trick

Many real-world classification problems are not linearly separable even with slack variables. The key
insight is to map the input x to a higher-dimensional feature space φ(x) where the data becomes
linearly separable. However, computing φ(x) explicitly for high (or infinite) dimensional spaces is
computationally intractable.
The kernel trick exploits the fact that the SVM optimization depends on data only through inner
products xᵀx'. A kernel function K(x, x') computes the inner product in the feature space without
explicitly computing φ(x):

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 19

Machine Learning — Comprehensive Study Notes | All 15 Topics

K(x, x') = φ(x)ᵀ φ(x')

The dual SVM objective only requires K(x_i, x_j) — not φ(x)
explicitly!

Decision function: f(x) = Σ_i α_i y_i K(x_i, x) + b

Common Kernel Functions

Kernel Formula / Properties
Linear K(x,x') = xᵀx'. No feature transformation. Equivalent to standard SVM.
Polynomial K(x,x') = (γxᵀx' + r)^d. Captures feature interactions of degree up to d.
RBF (Gaussian) K(x,x') = exp(-γ||x-x'||²). Maps to infinite-dim. space. Most popular kernel.
Sigmoid K(x,x') = tanh(γxᵀx' + r). Mimics neural network activation. Less common.

Original 1D space (not sep.):

x: -3 -1 0 1 3
o x x o (o=class1, x=class2 — not linearly separable)

Map φ(x) = (x, x²) to 2D:

(-3,9) (−1,1) (0,0) (1,1) (3,9)
o x x o (now linearly separable!)

Figure 8: Kernel mapping — data not separable in 1D becomes separable in 2D feature space.

SVM for Multi-class Classification

SVMs are inherently binary classifiers. Multi-class extension uses either One-vs-One (train K(K-1)/2
binary SVMs, choose class by majority vote) or One-vs-Rest (train K binary SVMs, choose class with
highest score). Modern implementations in sklearn use OvR by default.

SVM for Regression (SVR)

Support Vector Regression uses an ε-insensitive loss function — errors within ε are ignored, and only
points outside the ε-tube are penalized. This makes SVR robust to outliers and noise. The kernel trick
applies equally to SVR.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 20

Machine Learning — Comprehensive Study Notes | All 15 Topics

9. Linear Model (Logistic Regression, Linear Regression)

Linear models are a fundamental class of machine learning algorithms that model the relationship
between input features and outputs through a linear combination of parameters. Despite their simplicity,
they are widely used due to their interpretability, computational efficiency, and strong theoretical
guarantees.

Linear Regression
Linear regression models the expected value of a continuous target y as a linear function of input
features x:

y = wᵀx + b = w_0 + w_1x_1 + w_2x_2 + ... + w_d x_d + ε

Loss: MSE = (1/n) Σ(y_i - (wᵀx_i + b))²

Closed-form solution: w = (XᵀX)⁻¹ Xᵀy [Normal Equations]

• Assumptions: Linearity, independence of errors, homoscedasticity (constant variance), normality
of errors.
• Gradient Descent Update: w ← w - η * ∇_w MSE = w - η * (2/n) Xᵀ(Xw - y)
• Regularization: Ridge (L2) adds λ||w||² to prevent overfitting; Lasso (L1) adds λ||w||₁ and
promotes sparsity.
Example: Predicting Student Grades
y = hours_studied (x1), previous_grade (x2). Learned model: grade = 2.5*hours +
0.6*prev_grade + 20. Interpretation: each additional study hour adds 2.5 points.

Logistic Regression
Despite its name, logistic regression is a classification algorithm. It models the probability that an input
belongs to the positive class using the sigmoid (logistic) function, which squashes the linear
combination to the range [0,1]:

P(y=1 | x) = σ(wᵀx + b) = 1 / (1 + exp(-(wᵀx + b)))

Log-odds (logit): log[P(y=1)/P(y=0)] = wᵀx + b

Decision: ŷ = 1 if P(y=1|x) ≥ 0.5 (i.e., wᵀx + b ≥ 0)

Sigmoid σ(z) = 1/(1+e^-z)
1.0 | _______
0.5 | ___/
0.0 |_________/
|________________

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 21

Machine Learning — Comprehensive Study Notes | All 15 Topics

-5 -3 0 3 5 z = wᵀx + b

Figure 9: Sigmoid function maps any real-valued input to [0,1], interpreted as probability.

Training Logistic Regression: Maximum Likelihood

Logistic regression is trained by maximizing the log-likelihood (or equivalently minimizing the cross-
entropy loss). There is no closed-form solution, so iterative optimization (gradient descent or Newton's
method) is used:

Loss = -Σ [y_i log(ŷ_i) + (1-y_i) log(1-ŷ_i)] [Cross-entropy]

∂Loss/∂w = Xᵀ(ŷ - y) = Xᵀ(σ(Xw) - y)

Update: w ← w - η * Xᵀ(ŷ - y)

Multi-class Logistic Regression (Softmax)

For K-class classification, logistic regression generalizes to softmax regression, which models the
probability of each class simultaneously:

P(y=k | x) = exp(wₖᵀx) / Σ_j exp(wⱼᵀx) [Softmax]

Loss = -Σ_i Σ_k 1[y_i=k] * log P(y_i=k | x_i) [Cross-entropy]

Comparison: Linear vs. Logistic Regression

Property Linear Regression vs. Logistic Regression
Output Continuous value vs. Probability [0,1]
Loss MSE (Mean Squared Error) vs. Cross-entropy (log-loss)
Boundary None (predicts value) vs. Linear decision boundary
Assumptions Gaussian errors vs. Bernoulli distribution of y
Use case House prices, stock returns vs. Spam detection, disease diagnosis

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 22

Machine Learning — Comprehensive Study Notes | All 15 Topics

10. Multi-Layer Perceptrons (MLPs), Backpropagation for

Training an MLP

Multi-Layer Perceptrons (MLPs) are the foundational deep learning architecture. By stacking multiple
layers of neurons with non-linear activation functions, MLPs can approximate any continuous function
(Universal Approximation Theorem). Backpropagation is the algorithm that makes training MLPs
computationally feasible by efficiently computing gradients using the chain rule.

MLP Architecture
• Input Layer: Receives raw features. Number of neurons = number of input features.
• Hidden Layers: One or more intermediate layers applying non-linear transformations. Each
neuron computes z = Wᵀa + b and activates a = f(z).
• Output Layer: Produces final prediction. Sigmoid for binary, softmax for multi-class, linear for
regression.

Input Layer Hidden Layer 1 Hidden Layer 2 Output

x1 ---\ o --- o o ---\
x2 ----> [o] o --- o [o] [o] o --- [o] --> ŷ
x3 ---/ o --- o o ---/
bias bias bias
(d inputs) (h1 neurons) (h2 neurons) (K outputs)

Figure 10: MLP architecture with 2 hidden layers — forward pass flows left to right.

Activation Functions
Function Formula & Properties
Sigmoid σ(z) = 1/(1+e^-z). Output ∈ (0,1). Suffers vanishing gradients for deep networks.
Tanh tanh(z) = (e^z - e^-z)/(e^z + e^-z). Output ∈ (-1,1). Zero-centered; better than
sigmoid.
ReLU f(z) = max(0,z). Most popular; fast computation; solves vanishing gradient; can
'die'.
Leaky ReLU f(z) = max(0.01z, z). Fixes dying ReLU by allowing small negative gradients.
Softmax σ(z)_k = e^{z_k}/Σe^{z_j}. Multi-class output; probabilities sum to 1.

Forward Pass
In the forward pass, input is propagated layer by layer from input to output, computing the network's
prediction:

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 23

Machine Learning — Comprehensive Study Notes | All 15 Topics

For each layer l = 1, ..., L:

Z^[l] = W^[l] A^[l-1] + b^[l] [Linear combination]

A^[l] = f^[l](Z^[l]) [Apply activation]

Output: ŷ = A^[L]

Backpropagation Algorithm
Backpropagation computes the gradient of the loss with respect to all weights by applying the chain rule
backwards from output to input. This was the key algorithmic breakthrough that made training deep
networks feasible.

Loss L = CrossEntropy(ŷ, y)

Output layer error: δ^[L] = ∂L/∂Z^[L] = ŷ - y (for cross-entropy

+ softmax)

Backpropagate: δ^[l] = (W^[l+1])ᵀ δ^[l+1] ⊙ f'(Z^[l])

Gradients: ∂L/∂W^[l] = δ^[l] (A^[l-1])ᵀ

∂L/∂b^[l] = δ^[l]

Update: W^[l] ← W^[l] - η * ∂L/∂W^[l]

Example: Backprop Intuition

A 3-layer network predicts P(spam)=0.3 for a true spam email. The error signal δ flows
backward: output error → hidden layer 2 → hidden layer 1. Weights that contributed most to
the wrong prediction get the largest updates. This is exactly the chain rule: how much did
weight w_ij change the output, via all paths?

Vanishing and Exploding Gradients

In deep networks, gradients can become exponentially small (vanishing) or large (exploding) as they
are backpropagated through many layers. Vanishing gradients prevent early layers from learning.
Solutions include: ReLU activations (partial solution), batch normalization, residual connections (skip
connections in ResNets), and careful weight initialization (Xavier/He initialization).

Regularization Techniques for MLPs

• Dropout: Randomly zero out neurons during training with probability p. Forces redundant
representations. Reduces co-adaptation.
• L2 Regularization (Weight Decay): Adds λΣw² to loss. Prevents large weights. Shrinks weights
toward zero.
• Batch Normalization: Normalizes layer inputs to zero mean/unit variance. Stabilizes training,
allows higher learning rates.
• Early Stopping: Monitor validation loss during training; stop when it starts increasing.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 24

Machine Learning — Comprehensive Study Notes | All 15 Topics

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 25

Machine Learning — Comprehensive Study Notes | All 15 Topics

11. Introduction to Clustering and Types of Clustering

(Soft and Hard Clustering)

Clustering is an unsupervised learning technique that groups data points into clusters based on
similarity, without using predefined labels. It is used for exploratory data analysis, pattern discovery,
customer segmentation, anomaly detection, and as a preprocessing step for other algorithms. The
fundamental challenge is defining and measuring similarity in a meaningful way.

What is Clustering?
Formally, given a dataset X = {x_1, x_2, ..., x_n}, clustering aims to partition X into K groups (clusters)
such that:
• Intra-cluster similarity is maximized (points within a cluster are similar to each other).
• Inter-cluster dissimilarity is maximized (points in different clusters are dissimilar).

Before Clustering: After Clustering:

. . . . . . . . [C1]. . [C2]. .
. . . . . . . . . . . . . . . .
. . . . . . [C3] . . [C4].
. . . . . . . . . . . . . . .
(unstructured data) (grouped into clusters)

Hard Clustering
In hard (or crisp) clustering, each data point is assigned to exactly one cluster. The assignment is
binary: a point either belongs to cluster k or it doesn't. Hard clustering produces a deterministic partition
of the data.

Hard Assignment: u_ik ∈ {0, 1}

Σ_k u_ik = 1 (each point in exactly one cluster)

u_ik = 1 means point i belongs to cluster k

Examples: K-Means, Hierarchical Clustering, DBSCAN, Rough K-Means.

Example: K-Means Hard Clustering

Customer dataset: 3 clusters (Budget, Mid-range, Premium). Customer A (income=$30K,
spend=$500/month) → Cluster 1 (Budget). Customer B (income=$80K,
spend=$2000/month) → Cluster 2 (Mid-range). Every customer belongs to exactly one
segment.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 26

Machine Learning — Comprehensive Study Notes | All 15 Topics

Soft Clustering (Fuzzy Clustering)

In soft (fuzzy) clustering, each data point has a degree of membership (a probability or weight) in each
cluster, ranging from 0 to 1. This is more realistic for ambiguous or overlapping data where a point may
plausibly belong to multiple clusters.

Soft Assignment: u_ik ∈ [0, 1]

Σ_k u_ik = 1 (memberships sum to 1 for each point)

u_ik = 0.7 means 70% membership in cluster k

Examples: Fuzzy C-Means, Expectation Maximization (Gaussian Mixture Models), Soft K-Means.

Example: Fuzzy C-Means Example

A news article about 'Apple' (the company) and 'apple' (the fruit) might be difficult to
categorize. Soft clustering might assign: P(Technology cluster) = 0.65, P(Food cluster) =
0.35. Hard clustering forces it to one: likely Technology.

Types of Clustering Algorithms

Type Description & Examples
Partitional Divides data into K non-overlapping clusters. Examples: K-Means, K-Medoids
(PAM). Fast, scalable.
Hierarchical Builds a tree (dendrogram) of clusters. Agglomerative (bottom-up) or Divisive
(top-down). No need to specify K.
Density-based Groups points in dense regions; marks sparse regions as noise. DBSCAN,
OPTICS. Handles arbitrary shapes.
Model-based Assumes data generated from mixture of distributions. EM/GMM. Provides
probabilistic assignments.
Spectral Uses graph Laplacian eigenvectors. Handles non-convex clusters. Spectral
Clustering.
Fuzzy Allows partial membership. Fuzzy C-Means (FCM). Useful for overlapping
clusters.

Cluster Validity Measures

• Internal: Silhouette score, Davies-Bouldin index, Calinski-Harabasz index — measure quality
without ground truth.
• External: Rand index, Adjusted Rand index, Normalized Mutual Information — compare to
known ground truth labels.
• Elbow Method: Plot within-cluster sum of squares vs. K; choose K at the 'elbow' of the curve.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 27

Machine Learning — Comprehensive Study Notes | All 15 Topics

12. Matrix Factorization and Spectral Clustering

Matrix Factorization and Spectral Clustering are two advanced techniques that leverage linear algebra
for machine learning tasks. Matrix factorization decomposes data matrices to discover latent structure,
while Spectral Clustering uses eigendecomposition of graph-based representations to find clusters of
arbitrary shape.

Matrix Factorization
Matrix Factorization (MF) decomposes a matrix V ≈ WH into a product of two lower-rank matrices,
revealing latent factors that explain the observed data. It is widely used in collaborative filtering
(recommendation systems), topic modeling, and dimensionality reduction.

V ≈ W * H

V: n×m data matrix (n users, m items)

W: n×k matrix (user-factor associations)

H: k×m matrix (factor-item associations)

k << min(n,m) [low-rank approximation]

Example: Movie Recommendation (Netflix Problem)

V is a 1000×500 matrix of user-movie ratings (mostly missing). MF finds W (1000×10 user-
factor matrix) and H (10×500 factor-movie matrix). Latent factors k=10 might represent
genres (Action, Romance, Sci-fi...). Missing ratings predicted as v_ij ≈ w_iᵀ h_j. User A has
high 'Action' factor → system recommends action movies they haven't seen.

Types of Matrix Factorization

Method Key Constraints / Properties
SVD V = UΣVᵀ. Optimal low-rank approx. by Frobenius norm. Requires complete
matrix.
NMF Non-negative MF: W,H ≥ 0. Parts-based representation. Used for text/images.
Probabilistic MF Bayesian MF with Gaussian priors. Handles missing data naturally. Used in
(PMF) collaborative filtering.
Alternating Least Alternately fixes W, solves for H; then fixes H, solves for W. Handles missing
Squares data.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 28

Machine Learning — Comprehensive Study Notes | All 15 Topics

Spectral Clustering
Spectral Clustering is a graph-based clustering method that works well for clusters of arbitrary shape,
unlike K-Means which assumes spherical clusters. It transforms the data into a graph representation
and uses eigendecomposition of graph matrices to find a low-dimensional embedding where clusters
are well-separated.

Algorithm Steps
• Step 1 — Construct Similarity Graph: Build a weighted graph G=(V,E) where nodes are data
points and edge weights reflect similarity: W_ij = exp(-||x_i - x_j||² / 2σ²) (Gaussian kernel).
• Step 2 — Compute Graph Laplacian: L = D - W, where D is the diagonal degree matrix (D_ii =
Σ_j W_ij). Normalized Laplacian: L_norm = D^{-1/2} L D^{-1/2}.
• Step 3 — Eigendecomposition: Find the K smallest eigenvectors of L. Stack them as columns to
form matrix U ∈ R^{n×K}.
• Step 4 — Cluster in Embedding Space: Apply K-Means to the rows of U (the spectral
embedding).
Graph Laplacian: L = D - W

L_norm = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}WD^{-1/2}

Find eigenvectors: L u = λ u

Use K eigenvectors with smallest eigenvalues (except the zero

eigenvalue)

Original space: Spectral embedding:

Two interlocking Two clearly separated
rings (can't cluster point clouds
with K-Means) (K-Means works!)
(o)(o) o o | x x
\x/ o o | x x

Figure 11: Spectral Clustering handles non-convex clusters (like interlocking rings) by operating in
spectral embedding space.

Connection between Matrix Factorization and Spectral Clustering

There is a deep connection: spectral clustering with normalized graph Laplacian is equivalent to a form
of matrix factorization on the affinity matrix. Both approaches discover low-dimensional structure in the
data — spectral clustering for grouping, matrix factorization for latent factor discovery. Both rely on the
top-k eigenvectors/singular vectors of key matrices.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 29

Machine Learning — Comprehensive Study Notes | All 15 Topics

13. Fuzzy C-Means Clustering and K-Means Clustering

K-Means and Fuzzy C-Means (FCM) are two of the most widely used clustering algorithms. K-Means
produces hard cluster assignments, while FCM extends it to produce soft (fuzzy) membership degrees.
Both are iterative algorithms that optimize an objective function, alternating between updating cluster
centers and assignments.

K-Means Clustering
K-Means partitions n data points into K clusters by minimizing the Within-Cluster Sum of Squares
(WCSS), also called inertia:

Minimize: J = Σ_k Σ_{x∈C_k} ||x - μ_k||²

where μ_k = (1/|C_k|) Σ_{x∈C_k} x [cluster centroid]

K-Means Algorithm (Lloyd's Algorithm)

• Step 1 — Initialize: Choose K initial centroids μ_1, ..., μ_K (randomly, or via K-Means++ for
better initialization).
• Step 2 — Assignment: Assign each point to the nearest centroid: c_i = argmin_k ||x_i - μ_k||²
• Step 3 — Update: Recompute each centroid as the mean of its assigned points: μ_k = mean of
points in cluster k
• Step 4 — Repeat steps 2-3 until convergence (no change in assignments or centroids).
Example: K-Means Iteration Example
K=2, points: {1,2,3,8,9,10}. Init: μ1=1, μ2=2. Assign: C1={1}, C2={2,3,8,9,10}. Update: μ1=1,
μ2=(2+3+8+9+10)/5=6.4. Re-assign: C1={1,2,3}, C2={8,9,10}. Update: μ1=2, μ2=9. Re-
assign: same. Converged!

Iter 1: x . . + . . x x=centroid, .=data

Assign: C1. . | . . C2 |=boundary
Update: x | x new centroids
Assign: C1. | .C2 converged!

K-Means++ Initialization
Random initialization can lead to poor solutions (local optima). K-Means++ initializes centroids spread
out across the data: first centroid chosen randomly; subsequent centroids chosen with probability
proportional to squared distance from nearest existing centroid. This gives O(log K) approximation
guarantee and typically much better results.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 30

Machine Learning — Comprehensive Study Notes | All 15 Topics

Fuzzy C-Means (FCM) Clustering

FCM extends K-Means by allowing each point to have a degree of membership u_ik in each cluster,
where u_ik ∈ [0,1] and Σ_k u_ik = 1. The objective function uses a fuzziness parameter m > 1:

Minimize: J_m = Σ_i Σ_k u_ik^m * ||x_i - c_k||²

Update memberships: u_ik = 1 / Σ_j (||x_i - c_k|| / ||x_i -

c_j||)^(2/(m-1))

Update centroids: c_k = Σ_i u_ik^m * x_i / Σ_i u_ik^m

m = fuzziness parameter (m→1: hard K-Means, m→∞: all equal

memberships)

Comparison: K-Means vs. FCM

Aspect K-Means vs. Fuzzy C-Means (FCM)
Assignment Hard: each point in exactly one cluster vs. Soft: membership degrees in all clusters
Objective WCSS = Σ||x-μ||² vs. Fuzzy WCSS with u^m weights
Parameters K (number of clusters) vs. K + m (fuzziness parameter)
Convergence Faster; fewer iterations vs. Slower; requires more iterations
Robustness Sensitive to outliers (outlier joins a cluster) vs. Outliers get low membership in all
clusters
Use case Well-separated clusters, large datasets vs. Overlapping clusters, ambiguous
boundaries

Limitations of K-Means and FCM

• Must specify K (number of clusters) in advance.
• Sensitive to initial centroid placement (K-Means++) mitigates this.
• Assumes spherical/elliptical clusters (Euclidean distance).
• FCM adds fuzziness parameter m which requires tuning.
• Both can get stuck in local optima — multiple restarts recommended.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 31

Machine Learning — Comprehensive Study Notes | All 15 Topics

14. Expectation Maximization-Based Clustering

Expectation Maximization (EM) is a general-purpose iterative optimization algorithm for finding

Maximum Likelihood Estimates (MLE) when data has missing or latent variables. When applied to
Gaussian Mixture Models (GMMs), it provides a principled probabilistic framework for soft clustering.
EM alternates between two steps: the E-step (compute expected cluster assignments) and the M-step
(maximize parameters given these assignments).

Gaussian Mixture Models (GMMs)

A GMM assumes that the data is generated from a mixture of K Gaussian distributions, each with its
own mean, covariance, and mixing coefficient:

P(x) = Σ_k π_k * N(x; μ_k, Σ_k)

π_k: mixing coefficient (prior probability of cluster k)

N(x; μ_k, Σ_k): Gaussian density with mean μ_k and covariance Σ_k

Constraints: Σ_k π_k = 1, π_k ≥ 0

GMM with 3 components:
Gaussian 1 Gaussian 2 Gaussian 3
/\ /\ /\
/ \ / \ / \
___/ \______/ \______/ \___
μ1=2,σ1=0.5 μ2=6,σ2=1.0 μ3=10,σ3=0.8
π1=0.3 π2=0.5 π3=0.2

Figure 12: GMM as a weighted sum of Gaussian densities — EM learns the parameters.

The EM Algorithm for GMMs

Initialization
Initialize parameters θ = {π_k, μ_k, Σ_k} for k=1..K, typically using K-Means to get initial means.

E-Step: Compute Responsibilities

For each data point x_i and cluster k, compute the posterior probability (responsibility) r_ik — the
probability that point i belongs to cluster k given current parameters:

r_ik = π_k * N(x_i; μ_k, Σ_k) / Σ_j π_j * N(x_i; μ_j, Σ_j)

r_ik ∈ [0,1], Σ_k r_ik = 1 for each i

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 32

Machine Learning — Comprehensive Study Notes | All 15 Topics

M-Step: Update Parameters

Re-estimate all parameters using the weighted data, where weights are the responsibilities:

N_k = Σ_i r_ik [effective number of points in cluster k]

π_k^new = N_k / n

μ_k^new = (1/N_k) Σ_i r_ik * x_i

Σ_k^new = (1/N_k) Σ_i r_ik * (x_i - μ_k)(x_i - μ_k)ᵀ

Convergence
Repeat E-step and M-step until the log-likelihood converges (change < ε). The log-likelihood is
guaranteed to increase (or stay the same) at each iteration, ensuring convergence to a local maximum.

Example: EM on 1D Data
Data: {1.1, 1.3, 1.5, 5.2, 5.8, 6.1}. K=2, init: μ1=1, μ2=5. E-step: r_i1 high for {1.1,1.3,1.5},
r_i2 high for {5.2,5.8,6.1}. M-step: μ1=1.3, μ2=5.7, π1=0.5, π2=0.5. Iterate: responsibilities
sharpen → clean separation. Final: Two tight Gaussians centered at 1.3 and 5.7.

EM as Generalization of K-Means
K-Means can be seen as a special case of EM for GMMs where: all covariance matrices are spherical
and equal (Σ_k = σ²I), and the responsibilities are hard-assigned (r_ik ∈ {0,1} in the limit σ→0). The E-
step becomes nearest-centroid assignment, and the M-step becomes mean recomputation.

Advantages and Challenges of EM Clustering

Advantage Challenge / Limitation
Provides probabilistic soft Sensitive to initialization; multiple restarts needed
assignments
Can model clusters of different Computationally expensive for large n, d, K
shapes/sizes/orientations via Σ_k
Log-likelihood provides a principled Can overfit with full covariance; regularization needed
model selection criterion (AIC, BIC)
Handles missing data naturally Assumes Gaussian distributions; fails for non-Gaussian
clusters

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 33

Machine Learning — Comprehensive Study Notes | All 15 Topics

15. Rough Clustering and Rough K-Means Clustering

Algorithm

Rough Clustering is an extension of classical clustering theory that incorporates concepts from Rough
Set Theory, introduced by Zdzislaw Pawlak in 1982. It addresses a fundamental limitation of both hard
and fuzzy clustering: rough clustering explicitly represents the uncertainty about cluster membership by
maintaining three regions for each cluster — a definite core (lower approximation), a boundary region,
and the complement. Data points in the boundary region may belong to multiple clusters
simultaneously.

Rough Set Theory Foundations

Rough Set Theory provides a mathematical framework for dealing with uncertainty and imprecision. For
a cluster C, it defines:
• Lower Approximation (POS_C): The set of points that definitely belong to cluster C — points
that could not possibly belong to any other cluster given the available information.
• Upper Approximation (U_C): The set of points that possibly belong to cluster C — includes both
definite members and boundary points.
• Boundary Region (BND_C): Points in the upper approximation but not in the lower
approximation: BND_C = U_C \ POS_C. Points here have uncertain membership.
POS_C ⊆ C ⊆ U_C

BND_C = U_C \ POS_C [boundary region]

NEG_C = U \ U_C [definite non-members]

Universe U
+------------------------+
| NEG_C |
| +------------------+ |
| | BND_C (boundary) | |
| | +-----------+ | |
| | | POS_C | | |
| | | (core) | | |
| | +-----------+ | |
| +------------------+ |
+------------------------+

Figure 13: Rough set approximations — lower approx. (POS_C), boundary (BND_C), negative region
(NEG_C).

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 34

Machine Learning — Comprehensive Study Notes | All 15 Topics

Rough K-Means Clustering Algorithm

The Rough K-Means algorithm (Lingras & West, 2004) extends K-Means to incorporate rough set
theory, explicitly handling boundary objects that may belong to multiple clusters. Each cluster is
represented by both a lower and upper approximation, and a special threshold parameter controls what
constitutes the boundary region.

Key Parameters
• K: Number of clusters.
• w_lower (w_l): Weight given to lower approximation (definite members) when computing cluster
centroids.
• w_upper (w_u): Weight given to upper approximation members (boundary points).
• Threshold (T or ε): Determines when a point goes to the boundary — if its distances to the two
nearest cluster centroids are within a ratio threshold.

Rough K-Means Algorithm Steps

• Step 1 — Initialize: Choose K initial centroids μ_1, ..., μ_K (as in standard K-Means).
• Step 2 — Compute Distances: For each point x_i, compute distance to all K centroids.
• Step 3 — Assignment with Boundary Detection: For each point, let d_1 and d_2 be distances to
nearest and second-nearest centroids.

If d_1 / d_2 < T (threshold): → Boundary region (point in upper

approx. of both)

If d_1 / d_2 ≥ T: → Lower approximation of nearest

cluster

• Step 4 — Update Centroids: Centroids are updated using weighted contributions from lower and
upper approximation members:
μ_k = (w_lower * Σ_{x∈POS_k} x + w_upper * Σ_{x∈BND_k} x)

/ (w_lower * |POS_k| + w_upper * |BND_k|)

Typical: w_lower = 0.75, w_upper = 0.25

• Step 5 — Repeat Steps 2-4 until convergence.

Example: Rough K-Means Example

K=2, points: A(1), B(2), C(5), D(6), E(3.4). Centroids: μ1=2, μ2=5. T=0.85. Point E:
d(E,μ1)=1.4, d(E,μ2)=1.6. Ratio=1.4/1.6=0.875 < T=0.85? No (0.875>0.85). E → POS(C1).
Try T=0.9: 0.875<0.9 → E → BND (boundary of both C1 and C2). E contributes with weight
w_upper=0.25 to both cluster centroid updates.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 35

Machine Learning — Comprehensive Study Notes | All 15 Topics

Comparison: Hard K-Means vs. Fuzzy C-Means vs. Rough K-Means

Property K-Means / FCM / Rough K-Means
Membership type Hard (binary) / Soft (continuous [0,1]) / Three-way (core, boundary,
negative)
Boundary handling Ignored / Gradual membership / Explicit boundary region
Cluster representation Centroid only / Centroid only / Lower + Upper approximations
Uncertainty model None / Probabilistic / Set-theoretic (rough sets)
Key parameter K / K, m (fuzziness) / K, T (threshold), w_lower, w_upper
Best for Well-separated data / Overlapping smooth clusters / Indeterminate,
boundary-heavy data

Applications of Rough Clustering

• Web document clustering: Many documents cover multiple topics — boundary regions capture
cross-topical documents.
• Image segmentation: Pixels near region boundaries have uncertain segment membership.
• Medical diagnosis: Patients with symptoms overlapping multiple conditions.
• Customer profiling: Customers who fall between behavioral segments.
Rough K-Means provides a fundamentally different and philosophically richer treatment of cluster
uncertainty compared to both hard and fuzzy approaches. By explicitly representing what we do not
know (the boundary region), it provides more informative cluster descriptions and can lead to better
downstream decisions in ambiguous real-world scenarios.

Decision Trees • Bayes Classifier • SVM • Neural Networks • Clustering Page 36