n

Confusion Matrix & Performance Metrics • Euclidean Distance: ∑i=1 (xi − yi )2 (most common
​ ​ ​ ​
4. Frequent Itemset Generation: Collect all candidates from
for numerical data) Ck that meet the minimum support threshold to form Lk .
The confusion matrix is a table used to describe the performance • Manhattan Distance, Minkowski Distance.
​ ​

of a classification model on a set of test data for which the true 3. Find k-Nearest Neighbors: Identify the 'k' training data 5. Iteration: Repeat steps 1-4 until no more frequent itemsets
values are known. points that are closest (have the smallest distances) to the can be generated.
Predicted Positive Predicted Negative new data point. 6. Rule Generation: Once all frequent itemsets are found,
Actual Positive True Positive (TP) False Negative (FN) 4. Vote/Average: generate strong association rules (A ⇒ B) that satisfy
Actual Negative False Positive (FP) True Negative (TN) • Classification: Assign the new data point to the class that minimum confidence and minimum lift thresholds.
• True Positive (TP): Correctly predicted positive.
is most frequent among its k-nearest neighbors (majority Numerical Example (Support, Confidence, Lift): Assume a
vote). dataset with 4 transactions: T1: {Milk, Bread, Diapers} T2:
• True Negative (TN): Correctly predicted negative. • Regression: Assign the new data point the average of the {Milk, Diapers, Eggs} T3: {Bread, Diapers, Beer} T4: {Milk,
• False Positive (FP): Incorrectly predicted positive (Type I values of its k-nearest neighbors. Bread, Diapers, Beer}
error). Numerical Example (KNN Classification): Given data points Min Support = 50% (2 transactions) Min Confidence = 70%
• False Negative (FN): Incorrectly predicted negative (Type II with features (X, Y) and Class labels: P1: (1, 1), Class A P2: (2, 1. Calculate Support:
error). 2), Class A P3: (3, 3), Class B P4: (4, 4), Class B New Point N:
Derived Metrics: (2.5, 2.5) Let k = 3. • Support({Milk}) = 3/4 = 75%
1. Calculate Euclidean Distances from N(2.5, 2.5): • Support({Bread}) = 3/4 = 75%
• Accuracy: Overall correctness of the model. • Support({Diapers}) = 4/4 = 100%
TP + TN • d(N , P 1) = (2.5 − 1)2 + (2.5 − 1)2 = ​

• Support({Beer}) = 2/4 = 50%

Accuracy = 1.52 + 1.52 = 2.25 + 2.25 = 4.5 ≈ 2.12 • Support({Milk, Diapers}) = 3/4 = 75%
TP + TN + FP + FN ​ ​ ​

• Support({Bread, Diapers}) = 3/4 = 75%

• Precision (Positive Predictive Value): Proportion of positive • d(N , P 2) = (2.5 − 2)2 + (2.5 − 2)2 = • Support({Milk, Bread, Diapers}) = 2/4 = 50%
identifications that were actually correct.
​

TP 0.52 + 0.52 = 0.25 + 0.25 = 0.5 ≈ 0.71

​ ​ ​
2. Generate Rules & Calculate Confidence:
Precision = • d(N , P 3) = (2.5 − 3)2 + (2.5 − 3)2 = •
TP + FP ​

Rule: {Milk, Diapers} ⇒ {Bread}

• Recall (Sensitivity/True Positive Rate): Proportion of actual (−0.5)2 + (−0.5)2 = 0.25 + 0.25 = 0.5 ≈
​ ​ ​

positives that were identified correctly. 0.71 • Support({Milk, Diapers, Bread}) = 50%
TP • Support({Milk, Diapers}) = 75%
Recall = • d(N , P 4) = (2.5 − 4)2 + (2.5 − 4)2 = • Confidence = \frac{\text{Support}(\text{Milk, Diapers,
TP + FN ​

Bread})}{\text{Support}(\text{Milk, Diapers})} =
• F1-Score: Harmonic mean of Precision and Recall. Useful (−1.5)2 + (−1.5)2 = 2.25 + 2.25 = 4.5 ≈
​ ​ ​

\frac{50%}{75%} = 66.67% (Below Min Confidence)

when there's an uneven class distribution. 2.12
Precision × Recall ⇒ Weak Rule
F1-Score = 2 × 2. Sort and Pick k=3 Neighbors: •
Precision + Recall
​

• P2 (dist 0.71, Class A) Rule: {Bread, Diapers} ⇒ {Milk}

Naïve Bayes Classifier • P3 (dist 0.71, Class B)
• P1 (dist 2.12, Class A) • Support({Milk, Bread, Diapers}) = 50%
Algorithm: Naïve Bayes is a probabilistic classifier based on • P4 (dist 2.12, Class B) • Support({Bread, Diapers}) = 75%
Bayes' theorem with a "naïve" assumption of conditional The 3 nearest neighbors are P2 (Class A), P3 (Class B), P1 • Confidence = \frac{\text{Support}(\text{Milk, Bread,
independence between features. (Class A). Diapers})}{\text{Support}(\text{Bread, Diapers})} =
P (x∣Ck )P (Ck ) 3. Vote: \frac{50%}{75%} = 66.67% (Below Min Confidence)
P (Ck ∣x) =
​ ​

P (x) • Class A: 2 votes (from P1, P2)

​

⇒ Weak Rule
Where: • Class B: 1 vote (from P3)
Since Class A has the majority vote, the new point N(2.5, •
• P (Ck ∣x): Posterior probability of class Ck given predictor x.
​ ​ 2.5) is classified as Class A. Rule: {Diapers} ⇒ {Milk}
• P (Ck ): Prior probability of class Ck .
​ ​ Supervised vs. Unsupervised Learning • Support({Milk, Diapers}) = 75%
• Support({Diapers}) = 100%
• P (x∣Ck ): Likelihood of predictor x given class Ck . Feature Supervised Learning Unsupervised
• Confidence = \frac{\text{Support}(\text{Milk,
Learning
​ ​

• P (x): Prior probability of predictor x. Goal Predict output based on Find hidden Diapers})}{\text{Support}(\text{Diapers})} =
labeled training data. patterns/structures in
unlabeled data.
\frac{75%}{100%} = 75% (Above Min Confidence) ⇒
Due to the "naïve" assumption, P (x∣Ck ) is simplified: ​

Data Labeled data (input Unlabeled data (only Strong Rule

features x and output y input features x). 3. Calculate Lift:
P (x∣Ck ) = P (x1 ∣Ck ) × P (x2 ∣Ck ) × ⋯ × P (xn ∣Ck )
• For rule {Diapers} ⇒ {Milk}:
​ ​ ​ ​ ​ ​ ​

).
The classifier predicts the class with the highest posterior Tasks Classification (discrete Clustering,
probability: output), Regression Dimensionality • Lift = \frac{\text{Confidence}(\text{Diapers}
n (continuous output). Reduction, Association \Rightarrow \text{Milk})}{\text{Support}
(\text{Milk})} = \frac{75%}{75%} = 1
class = arg max P (Ck ) ∏ P (xi ∣Ck )
Rule Mining.
​ ​ ​ ​ ​

Feedback Direct feedback (correct No direct feedback (no • Lift = 1 implies no association between Diapers and
Ck ​
answers provided). correct answers). Milk. (Note: A lift > 1 indicates positive association).
i=1 Complexity Can be complex, Often simpler data
Why "Naïve"? It assumes that all features are conditionally requires human labeling preparation, but
effort. interpretation can be K-Means Clustering
independent given the class label. In real-world scenarios, this harder.
assumption is rarely perfectly true, as features often have some Algorithms Linear Regression, K-Means, Hierarchical Algorithm Steps:
dependencies. Despite this strong simplification, Naïve Bayes Logistic Regression, Clustering, PCA, SVD, 1. Initialization:
often performs surprisingly well, especially with large datasets, Decision Trees, SVM, Apriori.
due to its simplicity and computational efficiency. Naïve Bayes, Neural • Choose the number of clusters, k .
Example: Classifying whether a fruit is an apple based on color Networks. • Randomly select k data points from the dataset as initial
(Red, Green) and shape (Round, Oval, Square). Examples Spam detection, image Customer segmentation, centroids (or use other initialization methods like K-
classification, price anomaly detection, Means++).
Color Shape Type prediction, medical topic modeling, market
Red Round Apple diagnosis. basket analysis. 2. Assignment Step (E-step):
• Assign each data point to the closest centroid. "Closest" is
Green Round Apple Overfitting vs. Underfitting typically determined by Euclidean distance.
Red Oval Not Apple • Each data point belongs to the cluster whose centroid it is
Green Square Not Apple • Overfitting: Occurs when a model learns the training data too nearest to.
To classify a new fruit (Red, Round): well, including its noise and outliers. It performs excellently on 3. Update Step (M-step):
training data but poorly on unseen test data. • Recalculate the centroids of the clusters. The new centroid
1. Calculate P (Apple) and P (Not Apple). • Avoidance: Regularization (L1/L2), early stopping, cross- for each cluster is the mean of all data points assigned to
validation, more training data, feature selection, reducing that cluster.
2. Calculate conditional probabilities like P (Red∣Apple), model complexity. 4. Iteration:
• Underfitting: Occurs when a model is too simple to capture • Repeat steps 2 and 3 until the centroids no longer change
P (Round∣Apple), etc. the underlying patterns in the training data. It performs poorly
on both training and test data. significantly, or a maximum number of iterations is
3. Apply Bayes' theorem to find P (Apple∣Red, Round) and reached, or the cluster assignments remain stable.
• Avoidance: Increasing model complexity, adding more
P (Not Apple∣Red, Round). relevant features, reducing regularization, extending training Numerical Example (2 Iterations): Given 5 data points:
duration. P1(1,1), P2(1,2), P3(4,4), P4(5,4), P5(5,5). Let k=2. Initial
4. Assign to the class with higher probability. Centroids: C1 = P1(1,1), C2 = P5(5,5).
Decision Tree vs. Random Forest Training Set vs. Test Set Iteration 1:
• Training Set: The subset of data used to train the machine 1. Assignment:
Decision Tree
• Working: A tree-like model where each internal node
learning model. The model learns patterns and relationships • d(P 1, C1) = 0, d(P 1, C2) =
from this data.
represents a test on an attribute, each branch represents an • Test Set: The subset of data used to evaluate the performance (1 − 5)2 + (1 − 5)2 = 16 + 16 = 32 ≈
outcome of the test, and each leaf node represents a class label
​ ​ ​

(classification) or a continuous value (regression). of the trained model on unseen data. It provides an unbiased 5.66 ⇒ P 1 ∈ Cluster 1
• Logic (ID3/C4.5):
evaluation of the final model fit.
• Why split? To assess the model's generalization ability. If we
1. Attribute Selection Measure: Uses metrics like evaluate on the training data, we risk incorrectly concluding the • d(P 2, C1) = (1 − 1)2 + (2 − 1)2 = 1, ​

Information Gain (ID3) or Gain Ratio (C4.5) to select model performs well due to overfitting. The test set simulates d(P 2, C2) = (1 − 5)2 + (2 − 5)2 = 16 + 9 =
the best attribute to split the data at each node. how the model will perform in the real world.
​ ​

• Entropy: Measures impurity/disorder. H(S) = 25 = 5 ⇒ P 2 ∈ Cluster 1

Support Vectors in SVM ​

− ∑ pi log2 (pi ) • d(P 3, C1) = (4 − 1)2 + (4 − 1)2 = 9 + 9 =

• Support Vectors: The data points (from the training set) that
​ ​ ​
​ ​

• Information Gain: Reduction in entropy after splitting. are closest to the decision boundary (hyperplane). They are the 18 ≈ 4.24, d(P 3, C2) = (4 − 5)2 + (4 − 5)2 =
critical elements of the dataset that, if removed, would alter the
​ ​

∣S ∣
IG(S, A) = H(S) − ∑v∈Values(A) ∣S∣v H(Sv ) position of the decision boundary. 1 + 1 = 2 ≈ 1.41 ⇒ P 3 ∈ Cluster 2
​

​ ​ ​
​ ​

• Margin: The region between the two hyperplanes that separate

2. Splitting: The dataset is split based on the chosen the two classes, defined by the support vectors. SVM aims to • d(P 4, C1) = (5 − 1)2 + (4 − 1)2 = 16 + 9 =
attribute. find the hyperplane that maximizes this margin, leading to
​ ​

3. Recursion: The process is repeated recursively for each better generalization. 25 = 5, d(P 4, C2) = (5 − 5)2 + (4 − 5)2 =
sub-tree until a stopping condition is met (e.g., all samples
​ ​

in a node belong to the same class, no more attributes, or Logistic Regression Cost Function (Log Loss) 1 ⇒ P 4 ∈ Cluster 2
max depth reached).
• Pros: Easy to understand, handle both numerical and • Why Log Loss (Binary Cross-Entropy) instead of MSE? • d(P 5, C1) = (5 − 1)2 + (5 − 1)2 = 16 + 16 =​ ​

categorical data. • Non-convexity: If we used Mean Squared Error (MSE) for 32 ≈ 5.66, d(P 5, C2) = 0 ⇒ P 5 ∈ Cluster 2
• Cons: Prone to overfitting, sensitive to small changes in data. logistic regression, the cost function would be non-convex,
​

Random Forest meaning it would have many local minima. Gradient descent • Cluster 1: {P1, P2}
• Improvement over Decision Trees: Random Forest is an would get stuck in these local minima and might not find the • Cluster 2: {P3, P4, P5}
ensemble learning method that combines multiple decision global optimum. 2. Update Centroids:
trees to produce a more robust and accurate model, addressing • Log Loss Convexity: The Log Loss function for logistic
the overfitting issue of individual trees. regression is convex, ensuring that gradient descent will • New C1 = Mean({(1,1), (1,2)}) = ((1 + 1)/2, (1 +
• Working: converge to the global minimum, leading to a more reliable
and efficient optimization process. 2)/2) = (1, 1.5)
1. Bootstrap Aggregating (Bagging): Creates multiple • Probabilistic Nature: Log Loss is derived from the
subsets of the training data by random sampling with • New C2 = Mean({(4,4), (5,4), (5,5)}) = ((4 + 5 +
replacement. Each subset is used to train a separate principle of maximum likelihood estimation and is more
decision tree. appropriate for models that output probabilities, penalizing 5)/3, (4 + 4 + 5)/3) = (14/3, 13/3) ≈ (4.67, 4.33)
2. Feature Randomness: When building each tree, instead incorrect probabilistic predictions more heavily.
of considering all features for splitting, only a random Iteration 2:
subset of features is considered at each node. This Apriori Algorithm
decorrelates the trees. Goal: To find frequent itemsets and derive association rules from
3. Voting/Averaging: transactional databases.
• Classification: The final prediction is made by taking a Steps:
majority vote of the predictions from all individual trees.
• Regression: The final prediction is the average of the 1. Join Step (Candidate Generation):
predictions from all individual trees. • Initially, generate all single itemsets (C1).
• Benefits: Reduces overfitting, improves accuracy and • From frequent (k-1)-itemsets (Lk−1 ), generate candidate ​

generalization, handles high-dimensional data, less prone to

noise. k-itemsets (Ck ) by joining Lk−1 with itself. This means
​ ​

K-Nearest Neighbor (KNN) combining two frequent (k-1)-itemsets if they share k-2
items.
Algorithmic Steps: 2. Prune Step:
1. Choose k: Select the number of neighbors (k). This is a • For each candidate k-itemset in Ck : if any (k-1)-subset of
​

hyperparameter, typically an odd number to avoid ties in this candidate is not in Lk−1 (i.e., it's infrequent), then
classification.
​

2. Calculate Distance: For a new data point, calculate its remove the candidate k-itemset from Ck . This ​

distance to all training data points. Common distance significantly reduces the number of candidates to check.
metrics include: 3. Support Counting: Scan the database to count the support
for each candidate in Ck . ​
 1. Assignment (using new centroids C1(1, 1.5) and C2(4.67, C:1) Feature Feature Selection Feature Extraction
4.33)): • From T1: A,B,C (C1 ) Methods/Examples Filter Methods, PCA, SVD, Linear
Wrapper Methods, Discriminant Analysis
​

• d(P 1, C1) = 0.5, d(P 1, C2) ≈ 4.6 ⇒ P 1 ∈ Embedded Methods. (LDA).

• From T3: A,C (C2 )
Cluster 1
​

• From T5: A,B,C (C3 )

Feature Selection Methods:
• d(P 2, C1) = 0.5, d(P 2, C2) ≈ 4.1 ⇒ P 2 ∈ • Filter Methods: Select features based on statistical measures
​

• Correct Paths: (A,B):2, (A):1 (e.g., correlation, chi-square, information gain) independently
Cluster 1 • Conditional Pattern Base for 'C': { (A,B):2, (A):1 } of the learning algorithm. Fast, but might ignore feature
• Conditional FP-Tree for 'C': dependencies.
• d(P 3, C1) ≈ 3.7, d(P 3, C2) ≈ 0.7 ⇒ P 3 ∈ • Wrapper Methods: Use a specific machine learning model to
• A:3, B:2
Cluster 2 • Frequent items in this base: A (support 3), B (support
evaluate subsets of features. They search for the best subset by
training and testing the model (e.g., Recursive Feature
• d(P 4, C1) ≈ 4.1, d(P 4, C2) ≈ 0.3 ⇒ P 4 ∈ 2) Elimination, Sequential Feature Selection). More
• Generate frequent patterns: {C,A}, {C,B}, {C,A,B} computationally intensive but often yield better performance.
Cluster 2 (all with appropriate supports) • Embedded Methods: Feature selection is integrated into the
This process is applied recursively for all items in the F-list. model training process itself. The model learns which features
• d(P 5, C1) ≈ 4.5, d(P 5, C2) ≈ 0.7 ⇒ P 5 ∈ are most important during training (e.g., Lasso Regression,
Association Rule Mining Ridge Regression, Decision Tree based feature importance).
Cluster 2
• Cluster 1: {P1, P2} • Support: Indicates how frequently an itemset appears in the Model Selection & Evaluation
• Cluster 2: {P3, P4, P5} dataset. Cross-Validation (K-Fold)
2. Update Centroids: Number of transactions containing X • Purpose: To estimate the generalization performance of a
Support(X) = model and to prevent overfitting by ensuring the model is
• New C1 = Mean({(1,1), (1,2)}) = (1, 1.5) Total number of transactions evaluated on unseen data. It also helps in hyperparameter
• New C2 = Mean({(4,4), (5,4), (5,5)}) = (4.67, 4.33) • Confidence: Measures how often items in Y appear in tuning.
transactions that contain X. • Process (K-Fold):
Since centroids did not change, the algorithm converges. Support(X ∪ Y ) 1. Divide the entire dataset into k equal-sized folds
Hierarchical Clustering Confidence(X ⇒ Y ) = (subsets).
Support(X)
​

2. For each fold i from 1 to k :

Difference between Agglomerative and Divisive: • Lift: Measures how many times more often X and Y occur • Use fold i as the test set.
• Agglomerative (Bottom-up): together than expected if they were statistically independent. • Use the remaining k-1 folds as the training set.
• Starts with each data point as a single cluster. • Lift = 1: X and Y are independent. • Train the model on the training set and evaluate its
• Iteratively merges the closest pairs of clusters until all data • Lift > 1: Positive correlation (X and Y tend to occur performance on the test set.
points are in a single cluster, or a stopping criterion is met. together). 3. The final performance metric is the average of the k
• Builds a dendrogram from leaves to root. • Lift < 1: Negative correlation (X and Y are unlikely to occur evaluation scores.
• Divisive (Top-down): together). • Benefits: Reduces bias compared to a single train-test split,
• Starts with all data points in one single cluster. Support(X ∪ Y ) provides a more robust estimate of model performance, and
• Iteratively splits the largest or most diverse cluster into Lift(X ⇒ Y ) = makes efficient use of data.
Support(X) × Support(Y )
​

smaller sub-clusters until each data point is a separate Bias-Variance Tradeoff

cluster, or a stopping criterion is met. Curse of Dimensionality • Bias: The error introduced by approximating a real-world
• Builds a dendrogram from root to leaves. problem, which may be complex, by a simplified model. High
Linkage Methods (for Agglomerative): Determine the • Problem: As the number of features (dimensions) in a dataset
bias implies the model is too simple and underfits the data (e.g.,
"distance" between two clusters. linear model fitting non-linear data).
increases, the data becomes extremely sparse. This means that • Variance: The amount that the model's performance changes
1. Single Linkage (Min Linkage): data points become increasingly distant from each other, when trained on different subsets of the training data. High
• Distance between two clusters is the minimum distance making it difficult for machine learning algorithms to find variance implies the model is too complex and overfits the data
meaningful patterns, clusters, or relationships. (e.g., high-degree polynomial fitting noisy data).
between any single data point in the first cluster and any • Consequences:
single data point in the second cluster. • Increased computational cost.
• Tradeoff: There's an inherent conflict.
• Tends to form long, "straggly" clusters (chaining effect). • Increasing model complexity generally decreases bias but
2. Complete Linkage (Max Linkage): • Models become more prone to overfitting. increases variance.
• Distance between two clusters is the maximum distance • Increased data sparsity requires exponentially more data to • Decreasing model complexity generally increases bias but
between any single data point in the first cluster and any maintain the same density. decreases variance.
single data point in the second cluster. • Distance metrics become less meaningful. • Goal: To find a balance between bias and variance that
• Tends to form compact, spherical clusters.
Clustering Methods minimizes the total error (Bias2 + Variance + Irreducible
3. Average Linkage: Error), leading to optimal model generalization.
• Distance between two clusters is the average distance • Partitioning Methods: Divide data objects into non-
between all pairs of data points from the two clusters. overlapping subsets (clusters) such that each data object is in Precision, Recall, F1-Score: Formulas and When
• A compromise between single and complete linkage, often exactly one subset. (e.g., K-Means, K-Medoids) to Use
producing more balanced clusters. • Hierarchical Methods: Create a hierarchical decomposition of
FP-Growth Algorithm the set of data objects. (e.g., Agglomerative, Divisive) • Precision: TPTP
+FP ​

• Density-based Methods: Discover clusters of arbitrary shape

based on density (regions of high density separated by regions • When to use: When the cost of False Positives is high. (e.g.,
Goal: An efficient alternative to Apriori for finding frequent Spam detection: don't want to classify legitimate email as
itemsets without candidate generation. of low density). (e.g., DBSCAN) spam).
Steps: Principal Component Analysis (PCA) • Recall: TP
1. Scan Database (First Pass): TP +FN
​

• Count the frequency of each item. Algorithm Steps: • When to use: When the cost of False Negatives is high.
• Filter out infrequent items (items with support less than 1. Standardize the Data: Scale the data to have a mean of 0 (e.g., Disease detection: don't want to miss actual positive
min_support ). and a standard deviation of 1. This ensures that features with cases).
larger scales do not dominate the principal components. Precision×Recall
• Sort the frequent items in descending order of frequency • F1-Score: 2 × Precision+Recall
2. Calculate the Covariance Matrix: Compute the covariance
​

(F-list). matrix of the standardized data. The covariance matrix • When to use: When you need a balance between Precision
2. Construct FP-Tree: shows the relationships (variance and covariance) between and Recall, especially with imbalanced classes.
• Create the root of the FP-Tree, labeled "null". all pairs of features.
• For each transaction in the database: 3. Calculate Eigenvalues and Eigenvectors: Curse of Dimensionality: How Unsupervised
• Sort the items in the transaction according to the F-list.
• Find the eigenvalues and corresponding eigenvectors of Learning Helps
• Insert the sorted transaction into the FP-Tree. Each node
the covariance matrix.
• Eigenvectors represent the principal components (new • Unsupervised learning techniques, particularly dimensionality
in the tree represents an item and stores a count. If a dimensions/axes). reduction methods like PCA (Principal Component Analysis)
node already exists, increment its count. If not, create a • Eigenvalues represent the magnitude of variance along and SVD (Singular Value Decomposition), directly address the
new node. curse of dimensionality.
• Maintain a header table that links each item to its first each principal component. • They transform high-dimensional data into a lower-
occurrence in the tree and to all subsequent occurrences 4. Sort Eigenvalues and Select Principal Components: dimensional representation while preserving as much relevant
via node links. • Sort the eigenvalues in descending order. information (variance) as possible. This reduces data sparsity,
3. Mine FP-Tree (Recursive Mining): • Choose the top k eigenvectors corresponding to the computational cost, and the risk of overfitting, making
• Start from the lowest item in the F-list. largest eigenvalues. These k eigenvectors will form the subsequent supervised learning tasks more effective.
• For each such item: a. Construct Conditional Pattern basis for the new feature subspace. The number k is the • Clustering can also help by grouping similar high-dimensional
Base: Find all paths in the FP-Tree from the root to the desired reduced dimensionality. data points, effectively abstracting away some of the sparsity.
occurrences of the current item. These paths form the 5. Project Data onto New Feature Space: Q-Learning
conditional pattern base. b. Construct Conditional FP- • Create a projection matrix (feature vector) from the
Tree: From the conditional pattern base, count the selected k eigenvectors. Algorithm and Update Rule: Q-Learning is an off-policy,
frequency of items and construct a new, smaller FP-Tree model-free reinforcement learning algorithm. Its goal is to learn
(conditional FP-Tree). c. Generate Frequent Itemsets: If • Multiply the original standardized data by this projection
the conditional FP-Tree consists of a single path, matrix to transform the data into the new k -dimensional an optimal policy by estimating the optimal action-value function,
enumerate all combinations of items on the path. subspace. Q∗ (s, a), which gives the maximum expected future reward for
Otherwise, recursively mine the conditional FP-Tree. taking action a in state s.
• Combine the item with the frequent itemsets found in its New Data = Original Data × Projection Matrix
conditional FP-Tree.
Singular Value Decomposition (SVD) Update Rule: The Q-value for a state-action pair (s, a) is
Example: Transactions: T1: {A, B, C} T2: {A, B, D} T3: {A, C, updated using the Bellman equation for optimality:
E} T4: {B, D, E} T5: {A, B, C, D} Min Support = 2 SVD is a matrix factorization technique that decomposes a matrix
1. First Pass & F-list: A into three other matrices: Q(s, a) ← Q(s, a) + α[Rt+1 + γ max
′
Q(s′ , a′ ) − Q(s, a)]
​ ​

a
• A: 4, B: 4, C: 3, D: 3, E: 2
• F-list (sorted by frequency): [A, B, C, D, E] A = U ΣV T Where:
2. FP-Tree Construction: Where: • Q(s, a): Current Q-value for state s and action a.
• Root (null) • α: Learning rate (0 to 1), determines how much new
• A: The original m × n matrix (e.g., data matrix, where m is
• T1: (A:1) -> (B:1) -> (C:1) information overrides old information.
• T2: (A:2) -> (B:2) -> (D:1) samples, n is features).
• Rt+1 : Immediate reward received after taking action a in state
• T3: (A:3) -> (C:1) -> (E:1) (now A is 3, C is 1. C for T1 • U: An m × m orthogonal matrix whose columns are the left
​

already exists, but for T3, it's a new path) s and transitioning to state s′ .
• T4: (B:1) -> (D:1) -> (E:1) (new path from root) -> this is singular vectors of A. These vectors span the column space of
incorrect, FP-Tree shares prefixes. Let's re-do FP-tree A. • γ : Discount factor (0 to 1), determines the importance of future
construction more carefully: • Σ (Sigma): An m × n diagonal matrix containing the singular rewards.
• Root (null) values of A. The singular values are non-negative and sorted in • s′ : The next state.
• T1: {A,B,C} (sorted) descending order along the diagonal. They represent the
• Root -> A(1) -> B(1) -> C(1)
"strength" or importance of each singular vector. • maxa′ Q(s′ , a′ ): The maximum Q-value for the next state s′
​

• V T : The transpose of an n × n orthogonal matrix whose

• T2: {A,B,D} (sorted) across all possible actions a′ . This is the "off-policy" aspect, as
• Root -> A(2) -> B(2) -> D(1) (B node connects to columns (rows of V T ) are the right singular vectors of A. it considers the value of the optimal future action, regardless of
previous B node, D is new) These vectors span the row space of A. the current policy.
• T3: {A,C,E} (sorted) Flowchart:
• Root -> A(3) -> C(1) -> E(1) (C node connects to A,
Interpretation:
E is new) • U: Represents the relationships between the original data points graph TD
• T4: {B,D,E} (sorted) (rows). A[Initialize Q-table with zeros] -->
• Root -> B(1) -> D(1) -> E(1) (new branch from root) • Σ: Contains the singular values, which indicate the variance B{Choose an initial state s};
• T5: {A,B,C,D} (sorted) captured by each dimension. Larger singular values correspond B --> C{Loop for each episode};
• Root -> A(4) -> B(3) -> C(2) -> D(1) (C node to more significant dimensions. C --> D{Select action a for state s};
connects to B, D is new) • V T : Represents the relationships between the original features D -- Exploration (ε-greedy) --> D1[Random
3. Mining (Example for item 'E'): (columns). The columns of V (rows of V T ) are essentially the action];
• D -- Exploitation --> D2[Action with max
Paths for 'E': (Root, A, C, E:1), (Root, B, D, E:1) principal components of the data, similar to PCA. Q-value for s];
•
SVD is used for dimensionality reduction (by setting smaller D1 & D2 --> E{Take action a, observe
singular values to zero), noise reduction, and recommendation
Conditional Pattern Base for 'E': { (A,C):1, (B,D):1 } systems. reward R and new state s'};
• E --> F{Update Q(s,a) using Bellman
Conditional FP-Tree for 'E': Feature Selection vs. Feature Extraction Equation};
• Item A: count 1 (from (A,C)) Feature Feature Selection Feature Extraction F --> G{Set s = s'};
• Item B: count 1 (from (B,D)) Goal Select a subset of Transform original G --> H{Is s a terminal state?};
relevant features from features into a new, H -- No --> C;
• Item C: count 1 (from (A,C)) the original set. smaller set of features.
• Item D: count 1 (from (B,D)) Output Features A subset of the original New, derived features H -- Yes --> C;
• All items have support 1, which is less than
features. (linear/non-linear C -- Episodes finished --> I[Optimal Q-
combinations of original table learned];
min_support (2). So no frequent patterns ending in 'E' features).
from this conditional tree. Interpretation Easier to interpret, as Harder to interpret, as
• original features are new features are
retained. abstract.
Let's try for 'C': Information Loss Potentially loses Minimizes information
• Paths for 'C': (Root, A, B, C:1), (Root, A, C:1), (Root, information from loss by compressing
A, B, C:1) -> should be (Root, A, B, C:2), (Root, A, discarded features. information.
How it learns an optimal policy: Q-learning directly Feature SARSA Q-Learning ∂zj(l) (l−1)
= ak (output of the previous neuron). By repeatedly
​

approximates the optimal action-value function, $Q^(s, a) Action a

′ ′
The next action a is
′
The next action a is
• (l)
∂wjk
​ ​

, regardlessof thepolicybeingf ollowed(off −

​

chosen based on the chosen as the greedy applying the chain rule, the error signal is efficiently distributed
current policy (e.g., ϵ- action (max Q-value) back through the network, allowing each weight to be adjusted
policy).Byiterativelyupdating Q(s, a) from s′ , regardless of proportionally to its contribution to the overall error.
greedy from s′ ). the policy used to select
usingthemaximumpossiblef utureQ − Recommender Systems
valuef romthenextstates' a.
Learning Learns the value of the Learns the optimal Recommender systems aim to predict user preferences for items
, itgraduallyconvergestothetrueoptimalQ − policy being followed. policy regardless of the and suggest items that are likely to be of interest.
exploration policy. Collaborative Filtering
[Link]^(s, a)islearned, theoptimalpolicy \pi^(s) Exploration More conservative, as it More aggressive, as it
considers the actual assumes the best • Core Idea: Recommends items to a user based on the opinions
issimplytochoosetheactionathatmaximizesQ(s, a) next action taken, which possible future action of other users (collaborators) with similar tastes or based on the
might be exploratory. will always be taken. similarity of items that the user has interacted with.
f oranygivenstates:$\pi^(s) = \arg\max_a Q^*(s, a)$$ This Convergence Converges to optimal Converges to optimal • User-based Collaborative Filtering:
greedy policy, derived from the optimal Q-values, guarantees the policy if all state-action policy even if exploring
pairs are visited non-optimal actions, • Find users similar to the target user (based on common
maximum expected cumulative reward. infinitely often and the provided all state-action ratings/interactions).
policy converges to a pairs are visited. • Recommend items that these similar users liked but the target
Bellman Equation greedy one (e.g., ϵ user has not yet seen.
The Bellman equations are a set of equations that decompose the decays). • Pros: Can recommend novel items, good for users with
value function into the immediate reward plus the discounted Risk in Cliff Walking Safer path, but might Finds optimal shortest diverse tastes.
value of future states. not be optimal (takes
longer route).
path, but might fall off
cliff during exploration. • Cons: "Cold start" for new users, scalability issues with
Bellman Equation for State Value V (s) (for a given policy π ): many users, sparsity of rating matrix.
The value of a state s under a policy π is the expected return Policy Iteration vs. Value Iteration • Item-based Collaborative Filtering:
• Find items similar to the items the target user has liked
• Policy Iteration: (based on how other users rated them).
starting from s and then following π . • Steps: • Recommend items that are similar to what the user liked in
V π (s) = Eπ [Rt+1 + γV π (St+1 )∣St = s]
​ ​ ​ ​
1. Policy Evaluation: Given a policy π , calculate the the past.
• Pros: More stable (item similarity changes less frequently
This means the value of the current state s is the expected state-value function V π (s) for all states. This typically than user preferences), better for large user bases.
immediate reward Rt+1 plus the discounted value of the next involves solving a system of linear equations or iterative • Cons: "Cold start" for new items, less diverse
​

updates. recommendations sometimes.

state St+1 (averaged over all possible next states and actions
​
2. Policy Improvement: Update the policy π by making it Content-Based Filtering
taken according to π ). greedy with respect to the current value function V π (s). • How it works: Recommends items based on the attributes of
items that the user has previously interacted with (e.g., liked,
Bellman Equation for Action Value Q(s, a) (for a given • Process: Alternates between policy evaluation and policy purchased).
improvement until the policy converges (i.e., no further 1. Item Representation: Items are described by their
policy π ): The value of taking action a in state s under a policy π improvement is possible). features/content (e.g., for a movie: genre, actors, director).
• Usually fewer iterations to converge for policy, but each 2. User Profile: A user's profile is built based on the features
is the expected return starting from s, taking action a, and then iteration is more computationally intensive. of items they have liked in the past. This often involves
following π . • Value Iteration: learning a preference function or creating a weighted
• Steps:
vector of features.
Qπ (s, a) = Eπ [Rt+1 + γQπ (St+1 , At+1 )∣St = s, At = a] 3. Recommendation: The system then recommends new
​ ​ ​ ​ ​ ​

1. Initialize V (s) for all states. items whose features match the user's profile.
This is often expanded as: • Pros: No "cold start" for new users if their preferences are
2. Repeatedly apply the Bellman optimality equation for known, can recommend novel items, provides explanations for
Q (s, a) = ∑ P (s , r∣s, a)[r + γ ∑ π(a ∣s )Q (s′ , a′ )]
π ′ ′ ′ π
recommendations.
V ∗ (s) until the value function converges.
​ ​

s′ ,r a′ • Cons: Limited to recommending items similar to what the user

Vk+1 (s) = max E[Rt+1 + γVk (St+1 )∣St = s, At = a has already liked (lack of diversity), requires rich item
Bellman Optimality Equation for State Value V ∗ (s): The
​

a
​ ​ ​ ​ ​ ​

metadata, "cold start" for new items if they lack metadata.

• Process: Directly finds the optimal value function, from Comparison:
optimal value of a state s is the maximum expected return which the optimal policy can be extracted greedily. Feature Collaborative Filtering Content-Based
achievable from s under any policy. $$V^(s) = \max_a E • Usually more iterations for value function to converge, Filtering
but each iteration is computationally simpler. Data Used User-item interaction Item attributes/features,
[R_{t+1} + \gamma V^(S_{t+1}) | S_t = s, A_t = a]$$ data (ratings, purchases) user's past interactions
Bellman Optimality Equation for Action Value Q∗ (s, a): The On-Policy vs. Off-Policy Recommendation
Basis
Similarity between Similarity between item
users or items based on attributes and user's
optimal value of taking action a in state s is the maximum • On-Policy Learning: The agent learns the value function (or shared interactions. profile.
Diversity Can recommend novel Tends to recommend
expected return achievable from s, taking action a, and then policy) for the same policy that it uses to act or explore the items outside user's past similar items, less
environment. The policy used to generate behavior is the same content. diverse.
following the optimal policy. This is the core of Q-learning. as the policy being evaluated and improved. (e.g., SARSA) Cold Start Problematic for new Problematic for new
$$Q^(s, a) = E [R_{t+1} + \gamma \max_{a'} Q^(S_{t+1}, a') | • Off-Policy Learning: The agent learns the value function (or users/items (no items (no attribute
S_t = s, A_t = a] policy) for a target policy, while following a different behavior interaction data). data); less for new users
if profile can be built.
T hisisof tenexpressedas : policy to explore the environment. This allows for learning Explainability "Users like you liked "You liked X, and Y is
about an optimal policy while still exploring non-optimal X." similar because of Z
Q^(s, a) = \sum_{s', r} P(s', r | s, a) [r + \gamma \max_{a'} Q^(s', actions. (e.g., Q-Learning) feature."
a')]$$ Optimal Policy Scalability Can be challenging with Generally good, scales
Solving a simple Maze/Gridworld problem using Bellman large datasets. with number of
updates (Value Iteration concept): Consider a 3x3 grid with ∗ items/features.
states S1-S9. S9 is a goal state with reward +100, S8 is a pit with • Definition in MDP: An optimal policy π is a policy that
reward -100. All other states have reward 0. Discount factor γ = achieves the maximum possible expected cumulative reward Perceptron & Multilayer Perceptron (MLP)
(return) from any state in a Markov Decision Process (MDP). Perceptron
0.9. Initialize V (s) = 0 for all states. • Goal: The primary goal of most reinforcement learning
algorithms is to find an optimal policy. • Structure of a Neuron: A perceptron is the simplest form of
Iteration 1 (Update V (s) based on immediate rewards only): • Property: For any given state s, an optimal policy $\pi^
an artificial neuron.
V (S9) = 100 V (S8) = −100 All other V (s) = 0 1. Inputs (x1 , x2 , … , xn ): Receive numerical inputs.
willchoosetheactiona
​ ​

2. Weights (w1 , w2 , … , wn ): Each input is multiplied by a

Iteration 2 (Using V (s) = R(s) + γ maxa V Assume (s′ )): thatleadstothehighestpossibleaction − valueQ^(s, a).
​ ​ ​

corresponding weight, representing its importance.

agent can move Up, Down, Left, Right. $\pi^(s) = \arg\max_a Q^(s, a)$$ 3. Bias (b): An additional input that is always 1 and has its
• V (S6) (assuming right leads to S9, down to S3, left to S5, up Backpropagation Algorithm own weight, allowing the activation function to be shifted.
to S9 (wall) - simplified for example) Backpropagation is the core algorithm used to train artificial 4. Weighted Sum: The weighted n inputs are summed up
• If action is Right (to S9): 0 + 0.9 × V (S9) = 0.9 × neural networks. It efficiently calculates the gradient of the loss along with the bias: z = ∑i=1 (xi wi ) + b. This is also ​ ​ ​

function with respect to the weights and biases of the network, called the net input or activation.
100 = 90 allowing for weight adjustments via gradient descent. 5. Activation Function: An activation function (e.g., step
• If action is Down (to S3): 0 + 0.9 × V (S3) = 0.9 × 0 = Steps: function for a simple perceptron) is applied to the
1. Forward Pass: weighted sum to produce the output. For a simple
0 perceptron, it's often a binary output (0 or 1).
• ... (consider all actions) • Input data x is fed into the network. • Output = step(z) where step(z) = 1 if z ≥
• V (S6) = max(90, 0, … ) = 90 • It propagates through each layer, with each neuron threshold, 0 otherwise.
performing a weighted sum of its inputs and applying an
• Similarly for other states, values will propagate from terminal activation function. Multilayer Perceptron (MLP)
states. • Output of layer l: a(l) = σ(z (l) ) = σ(W (l) a(l−1) + b(l) ) • Structure: An MLP is a feedforward neural network consisting
• V (S5) (if right to S6, down to S2, left to S4, up to S8) of:
• This continues until the final output y^ is produced by the 1. Input Layer: Receives the raw input data. No
• Right to S6: 0 + 0.9 × V (S6)= 0.9 × 90 = 81
​

output layer. computation is performed here, just data distribution.

• The loss (error) between the predicted output y ^ and the 2. One or More Hidden Layers: These layers are between
• Up to S8: 0 + 0.9 × V (S8) = 0.9 × (−100) = −90 ​
the input and output layers. Each neuron in a hidden layer
true label y is calculated (e.g., MSE or Cross-Entropy). is a perceptron-like unit with its own weights, biases, and
• V (S5) = max(81, −90, … ) = 81 activation function (often non-linear like ReLU, sigmoid,
2. Backward Pass (Error Propagation): tanh).
This iterative process continues until the values V (s) converge, • The error is propagated backward from the output layer to
3. Output Layer: Produces the final output of the network
at which point they represent the optimal state values. (e.g., class probabilities for classification, continuous
the input layer. values for regression).
• For each layer, the algorithm calculates the gradient of
Markov Property the loss with respect to the weights and biases of that
Why do we need hidden layers?
layer using the chain rule of calculus. • Non-linearity: A single-layer perceptron can only learn
Mathematical Expression: A process has the Markov property if linearly separable patterns (e.g., AND, OR gates). It cannot
the future is independent of the past given the present state. • Calculation of Error Term (δ ) for each neuron: solve problems like XOR. Hidden layers, combined with non-
P (St+1 ∣St , At , St−1 , At−1 , … , S0 , A0 ) = P (St+1 ∣St , At ) • Output Layer: δ (L) = (a(L) − y) ⊙ σ ′ (z (L) ) (for linear activation functions, allow MLPs to learn and model
non-linear and complex relationships in the data. They
​ ​ ​ ​ ​ ​ ​ ​ ​ ​

This means that the next state St+1 depends only on the current MSE and sigmoid activation) enable the network to form complex decision boundaries.
• Feature Extraction: Hidden layers act as feature extractors.
​

state St and the current action At , and not on any prior history of • Hidden Layers: δ (l) = ((W (l+1) )T δ (l+1) ) ⊙ σ ′ (z (l) )
​ ​
They learn hierarchical representations of the input data,
states or actions. • The δ term represents how much the network's output transforming raw inputs into more abstract and meaningful
Why it is important in RL? features at each successive layer. This allows the network to
changes with respect to the weighted input of a neuron in automatically discover intricate patterns without explicit
• Simplification: It greatly simplifies the problem of decision- that layer. feature engineering.
making. Instead of needing to remember and process the entire 3. Weight Update: • Increased Representational Power: With enough hidden
history of interactions, an RL agent only needs to know the • Once the gradients are calculated for all weights and layers and neurons, an MLP can approximate any continuous
current state to make an optimal decision. biases: function (Universal Approximation Theorem), making it a
• Tractability: Without the Markov property, the state space • Gradient for weights: ∂C(l) = δ (l) (a(l−1) )T
powerful model for various complex tasks.
would become infinitely large (as it would include all possible ∂W
​

ANN Numerical Example

histories), making it computationally intractable to learn • Gradient for biases: ∂C(l) = δ (l)
optimal policies. ∂b
​

• Foundation for MDPs: The Markov property is the • Weights and biases are updated using an optimization Given a neuron with inputs x1 = 0.5, x2 = 0.8. Weights w1 = ​ ​ ​

fundamental assumption of Markov Decision Processes algorithm like gradient descent: 0.3, w2 = 0.6. Bias b = 0.2. Activation function: Sigmoid
(MDPs), which are the mathematical framework for most • W (l) ← W (l) − η ∂W ∂C
​

reinforcement learning problems. It allows for the use of (l) ​

σ(z) = 1+e1 −z .
Bellman equations and dynamic programming techniques to ∂C
​

solve RL problems. • b(l) ← b(l) − η ∂b(l) where η is the learning rate.

1. Calculate Weighted Sum (z ): z = (x1 × w1 ) + (x2 ×
​

SARSA vs. Q-Learning

​ ​ ​

How weights are updated (Chain Rule Application): The chain w2 ) + b z = (0.5 × 0.3) + (0.8 × 0.6) + 0.2 z =
rule is crucial for calculating gradients layer by layer. For ​

Feature SARSA Q-Learning (l)

example, to find how a weight wjk (connecting neuron k in layer ​
0.15 + 0.48 + 0.2 z = 0.83
Policy On-Policy Off-Policy
Update Rule Q(s, a) ← Q(s, a) ← l − 1 to neuron j in layer l) affects the total loss C : 2. Calculate Output (a) using Sigmoid Activation: a =
(l) (l) 1 1 1
Q(s, a) + Q(s, a) + ∂C ∂C ∂aj ​
∂zj ​
σ(z) = 1+e−0.83 ​ e−0.83 ≈ 0.4359 a = 1+0.4359 ​ = 1.4359 ​ ≈
α[Rt+1 + α[Rt+1 + (l)
​ = (l)
​ × (l)
​ × (l)
​

0.6964
∂wjk ∂aj ∂zj ∂wjk
​ ​

γQ(s′ , a′ ) − γ maxa′ Q(s′ , a′ ) − Output of the neuron is approximately 0.6964.

​ ​ ​ ​

Each term can be computed:

​

Q(s, a)] Q(s, a)] ∂C

• (l) is related to the error propagated from subsequent layers.
Deep Learning vs. Traditional ML
∂aj
​

∂a(l) (l)
j
= σ ′ (zj ) (derivative of the activation function).
​

•
∂zj(l)
​ ​

​
Feature Traditional Machine Deep Learning (a
Learning subset of ML)
Feature Engineering Manual, domain-expert Automatic feature
driven. Requires learning through hidden
significant effort. layers.
Model Complexity Simpler algorithms Complex neural
(e.g., SVM, Decision network architectures
Trees, Logistic with many layers.
Regression).
Data Requirement Works well with Requires very large
smaller datasets. datasets for optimal
performance.
Performance with Performance tends to Performance often
Data Scale plateau after a certain scales with more data.
data size.
Computational Power Less intensive. Highly intensive (GPUs
often required for
training).
Explainability Often more Generally less
interpretable. interpretable ("black
box").
Applications Tabular data, structured Image recognition,
predictions, simpler NLP, speech
tasks. recognition, complex
pattern detection.
Similarity Measures
• Cosine Similarity:
• Measures the cosine of the angle between two non-zero
vectors in a multi-dimensional space.
• Ranges from -1 (opposite) to 1 (identical). 0 indicates
orthogonality (no similarity).
• Commonly used in text analysis (TF-IDF vectors),
recommendation systems.
• Formula for vectors A and B:
A⋅B ∑ Ai B i
Cosine Similarity(A, B) = =
​

∣∣A∣∣ ⋅ ∣∣B∣∣
​

∑ A2i ​ ​ ∑
• Pearson Correlation Coefficient:
• Measures the linear correlation between two sets of data.
• Ranges from -1 (perfect negative linear correlation) to 1
(perfect positive linear correlation). 0 indicates no linear
correlation.
• Used to measure the strength and direction of a linear
relationship between two variables.
• Common in recommendation systems (user-based
collaborative filtering).
• Formula for two variables X and Y:
cov(X, Y ) E[(X − μX )(Y − μY )]
ρX,Y = =
​ ​

​ ​ ​

σX σY ​ ​ σX σY ​ ​

Or sample version:
∑(xi − x
ˉ)(yi − yˉ)
r=
​ ​ ​

∑(xi − x
​ ˉ)2 ∑(yi − yˉ)2 ​ ​