Data Mining - Complete Notes

Unit III & Unit IV

UNIT III: CLASSIFICATION AND

PREDICTION
1. Issues Regarding Classification and Prediction
What is Classification?
Classification is the process of finding a model (or function) that describes and distinguishes data
classes. The goal is to predict the class label of unknown data.

Example: Predicting whether an email is "spam" or "not spam" based on its features.

What is Prediction?

Prediction is similar to classification but deals with predicting continuous values rather than discrete
class labels.

Example: Predicting house prices based on size, location, and age.

Key Issues:

1. Data Quality Issues

Missing values in the dataset
Noisy data (incorrect or inconsistent values)
Imbalanced datasets (one class has much more data than others)
2. Model Selection
Choosing the right algorithm for your data
Balancing model complexity and accuracy
3. Overfitting and Underfitting
Overfitting: Model learns training data too well, performs poorly on new data
Underfitting: Model is too simple, doesn't capture patterns properly
4. Evaluation Metrics
Accuracy: Percentage of correctly classified instances
Precision: How many predicted positives are actually positive
Recall: How many actual positives were identified
F1-Score: Balance between precision and recall
5. Scalability
 Can the algorithm handle large datasets efficiently?

2. Decision Tree
What is a Decision Tree?

A tree-like model where internal nodes represent tests on attributes, branches represent outcomes,
and leaf nodes represent class labels.

How It Works:

1. Start with all training data at the root

2. Choose the best attribute to split the data
3. Create branches for each possible value
4. Repeat recursively for each branch
5. Stop when all data in a node belongs to the same class or no more attributes remain

Example:

Outlook
/ | \
Sunny Overcast Rainy
/ | \
Humidity [Yes] Windy
/ \ / \
High Normal True False
/ \ / \
[No] [Yes] [No] [Yes]

Key Concepts:

Information Gain: Measures how much information an attribute gives us about the class

Higher information gain = better attribute to split on

Gini Index: Measures impurity of a dataset

Lower Gini index = better split

Entropy: Measures randomness/disorder in the data

Entropy = 0: All data belongs to one class (pure)

Entropy = 1: Data is equally distributed among classes

Advantages:
Easy to understand and interpret
Can handle both numerical and categorical data
Requires little data preparation

Disadvantages:

Prone to overfitting
Can be unstable (small changes in data can change tree structure)
Biased towards attributes with more levels

3. Bayesian Classification
What is Bayesian Classification?
A statistical approach based on Bayes' Theorem that calculates the probability of a data point
belonging to each class.

Bayes' Theorem:

P(C|X) = [P(X|C) × P(C)] / P(X)

Where:
- P(C|X) = Probability of class C given data X (posterior probability)
- P(X|C) = Probability of data X given class C (likelihood)
- P(C) = Probability of class C (prior probability)
- P(X) = Probability of data X

Naive Bayes Classifier:

Why "Naive"? It assumes all attributes are independent of each other (which is rarely true in
reality, but works well in practice).
Example:

Problem: Predict if a person will play tennis based on weather conditions.

Given data:

Outlook = Sunny
Temperature = Cool
Humidity = High
Windy = True

Calculate:

1. P(Play=Yes | conditions)
2. P(Play=No | conditions)

The class with higher probability is the prediction.

Advantages:

Fast and efficient

Works well with small datasets
Handles missing values well
Good for text classification (spam detection)

Disadvantages:

Independence assumption is often unrealistic

Can't learn relationships between features

4. Classification by Backpropagation
What is Backpropagation?

An algorithm used to train neural networks by adjusting weights to minimize prediction errors.

The Process:

1. Forward Pass:

Input data flows through the network

Each neuron calculates a weighted sum and applies activation function
Output is generated

2. Error Calculation:

Compare predicted output with actual output

 Calculate error using a loss function

3. Backward Pass:

Error is propagated backward through the network

Weights are adjusted to reduce error
This uses gradient descent optimization

4. Repeat:

Process continues for multiple iterations (epochs)

Weights keep updating until error is minimized

Simple Analogy:
Think of learning to throw a ball into a basket:

First throw (forward pass) - you throw and see where it lands
Check error - see how far off you were
Adjust your throw (backpropagation) - throw with more/less force, different angle
Keep practicing until you consistently hit the basket

5. Multilayer Feed-Forward Neural Network

Structure:

Input Layer:

Receives input features

One node per feature

Hidden Layer(s):

Process information from input layer

Can have multiple hidden layers
Each node applies weights and activation function

Output Layer:

Produces final prediction

One node per class (for classification)

Architecture Example:
 Input Layer Hidden Layer 1 Hidden Layer 2 Output Layer
(3) (4) (4) (2)

O O O O
O / \ / \ /
O O O O O O
/ \ / \ / \ / \
O O O O O

How Data Flows:

1. Input features enter the input layer
2. Weighted connections carry data to hidden layer
3. Hidden layer neurons process data using activation functions
4. Output is passed to next layer
5. Final layer produces prediction

Activation Functions:

Sigmoid: Outputs between 0 and 1

Used for binary classification

ReLU (Rectified Linear Unit): Outputs max(0, x)

Most popular for hidden layers

Fast and efficient

Tanh: Outputs between -1 and 1

Centers data around zero

Softmax: Used in output layer for multi-class classification

Converts outputs to probabilities that sum to 1

6. Back Propagation Algorithm

Step-by-Step Process:
Step 1: Initialize

Set random small weights for all connections

 Choose learning rate (α) - typically 0.01 to 0.5

Step 2: Forward Propagation

For each layer l:

activation[l] = weighted_sum(activation[l-1], weights[l]) + bias[l]
activation[l] = activation_function(activation[l])

Step 3: Calculate Output Error

Error = (Predicted_Output - Actual_Output)²

Step 4: Backward Propagation

For each layer (from output to input):

Calculate gradient of error with respect to weights
Update weights:
new_weight = old_weight - (learning_rate × gradient)

Step 5: Repeat

Go through all training examples

Repeat for multiple epochs
Monitor error - it should decrease over time

Key Parameters:
Learning Rate (α):

Too high: May overshoot optimal weights, unstable learning

Too low: Learning is very slow
Typical values: 0.01 to 0.3
Momentum:

Helps accelerate learning

Prevents getting stuck in local minima

Number of Hidden Layers:

More layers = more complex patterns

But also more prone to overfitting

Number of Neurons:

More neurons = more capacity to learn

But increases computation time

Stopping Criteria:
Maximum epochs reached
Error falls below threshold
Validation error starts increasing (early stopping)

7. K-Nearest Neighbor (KNN) Classifiers

What is KNN?

A simple, instance-based learning algorithm that classifies new data based on similarity to existing
data.

How It Works:
Step 1: Choose K (number of neighbors)

K = 1: Classify based on closest neighbor

K = 5: Classify based on 5 closest neighbors

Step 2: Calculate distance from new point to all training points

Usually uses Euclidean distance

Distance = √[(x₂-x₁)² + (y₂-y₁)²]

Step 3: Find K nearest neighbors

Step 4: Count class labels of K neighbors

Step 5: Assign the most common class

Example:

Given: K = 3
New data point: ?

Training data:
Red class: • (2,3), • (3,4), • (4,5)
Blue class: ◦ (7,8), ◦ (8,9)

Calculate distances from ? to all points

Find 3 nearest: 2 Red, 1 Blue
Prediction: Red (majority vote)

Distance Metrics:

Euclidean Distance:

d = √Σ(xi - yi)²

Most common, measures straight-line distance

Manhattan Distance:

d = Σ|xi - yi|

Sum of absolute differences

Minkowski Distance: Generalization of both above

Choosing K:

Small K (e.g., K=1):

Sensitive to noise
More complex decision boundary
Prone to overfitting

Large K (e.g., K=20):

Smoother decision boundary

Less sensitive to noise
May underfit

Rule of Thumb: K = √n (where n = number of training samples)

Always use odd K for binary classification (avoids ties)

Advantages:

Simple and easy to implement

No training phase (lazy learning)
Naturally handles multi-class problems
Effective with small datasets

Disadvantages:

Slow for large datasets (must compute all distances)

Sensitive to irrelevant features
Requires feature scaling
Memory intensive (stores all training data)

Optimization Techniques:

KD-Tree:

Organizes data in tree structure

Faster nearest neighbor search

Ball Tree:

Another tree-based structure

Better for high-dimensional data
8. Genetic Algorithm
What is a Genetic Algorithm?

An optimization technique inspired by natural evolution and genetics. Used to find optimal solutions
by simulating evolution.

Core Concepts:

Population: Set of potential solutions Chromosome: A single solution (encoded as a string/array)

Gene: A single element in the chromosome Fitness: How good a solution is

How It Works:

Step 1: Initialize Population

Create random set of solutions

Each solution is a "chromosome"

Example:

If optimizing weights for neural network:

Chromosome 1: [0.5, 0.3, 0.8, 0.2]
Chromosome 2: [0.1, 0.7, 0.4, 0.9]
Chromosome 3: [0.6, 0.2, 0.5, 0.7]

Step 2: Evaluate Fitness

Test each solution

Assign fitness score
Higher fitness = better solution

Step 3: Selection

Choose best solutions to reproduce

Selection methods:
Roulette Wheel: Probability proportional to fitness
Tournament: Pick best from random subset
Rank-based: Based on ranking, not absolute fitness

Step 4: Crossover (Reproduction)

Combine two parent chromosomes

 Create offspring

Single-point Crossover:

Parent 1: [0.5, 0.3, | 0.8, 0.2]

Parent 2: [0.1, 0.7, | 0.4, 0.9]

Offspring 1: [0.5, 0.3, 0.4, 0.9]

Offspring 2: [0.1, 0.7, 0.8, 0.2]

Two-point Crossover:

Parent 1: [0.5, | 0.3, 0.8, | 0.2]

Parent 2: [0.1, | 0.7, 0.4, | 0.9]

Offspring: [0.5, 0.7, 0.4, 0.2]

Step 5: Mutation

Randomly change some genes

Maintains diversity
Prevents getting stuck in local optima

Example:

Before: [0.5, 0.3, 0.8, 0.2]

After: [0.5, 0.3, 0.1, 0.2] (third gene mutated)

Step 6: Replace Population

New generation replaces old one

Keep some best solutions (elitism)
Step 7: Repeat

Continue until:
Maximum generations reached
Fitness threshold achieved
No improvement for several generations

Parameters:
Population Size: 50-200 typically Crossover Rate: 60-95% (probability of crossover) Mutation
Rate: 0.5-5% (low probability) Generations: 100-1000 or until convergence

Applications in Classification:

1. Feature Selection: Find optimal subset of features

2. Parameter Tuning: Optimize hyperparameters
3. Rule Discovery: Evolve classification rules
4. Neural Network Optimization: Optimize network weights

Advantages:
Can handle complex optimization problems
Doesn't require gradient information
Explores multiple solutions simultaneously
Good for non-linear problems

Disadvantages:

Computationally expensive
No guarantee of optimal solution
Many parameters to tune
Can converge prematurely

UNIT IV: CLUSTER ANALYSIS

1. Introduction to Cluster Analysis
What is Clustering?
Clustering is the process of grouping similar objects together without predefined labels. Unlike
classification, clustering is unsupervised learning (no training labels).

Goal: Maximize similarity within clusters and minimize similarity between clusters.
Real-World Examples:

Customer segmentation in marketing

Document categorization
Image segmentation
Gene expression analysis
Social network analysis

Key Concepts:

Similarity/Dissimilarity:

How alike are two objects?

Measured using distance metrics

Intra-cluster Distance: Distance between objects in same cluster (should be small)

Inter-cluster Distance: Distance between different clusters (should be large)

2. Data Types in Cluster Analysis

Types of Attributes:

1. Numerical (Quantitative)

Interval-Scaled:

Values with meaningful differences

No true zero point
Example: Temperature (20°C, 30°C)

Ratio-Scaled:

Has meaningful zero point

Can do all arithmetic operations
Example: Height, weight, age

2. Categorical (Qualitative)

Nominal:

No order or ranking
Example: Colors (red, blue, green), Gender (male, female)

Ordinal:

Has order but no meaningful distance

Example: Size (small, medium, large), Ratings (poor, fair, good)
3. Binary

Only two states

Example: True/False, Yes/No, 0/1

Symmetric Binary: Both outcomes equally important

Example: Gender (male/female)

Asymmetric Binary: One outcome more important

Example: Disease (present/absent) - presence is more significant

Distance Measures:
For Numerical Data:

Euclidean Distance:

d(x,y) = √[(x₁-y₁)² + (x₂-y₂)² + ... + (xₙ-yₙ)²]

Manhattan Distance:

d(x,y) = |x₁-y₁| + |x₂-y₂| + ... + |xₙ-yₙ|

Minkowski Distance:

d(x,y) = (Σ|xi-yi|ᵖ)^(1/p)

When p=1: Manhattan, p=2: Euclidean

For Categorical Data:

Simple Matching:
 Similarity = (Number of matching attributes) / (Total attributes)

Jaccard Coefficient (for binary):

J(A,B) = |A ∩ B| / |A ∪ B|

3. Categories of Clustering Methods

1. Partitioning Methods

Divide data into K non-overlapping partitions

Each partition is a cluster
Examples: K-Means, K-Medoids

2. Hierarchical Methods

Create tree-like structure of clusters

Can be agglomerative (bottom-up) or divisive (top-down)
Examples: AGNES, DIANA, CURE, Chameleon

3. Density-Based Methods
Clusters are dense regions separated by sparse regions
Can find arbitrary-shaped clusters
Examples: DBSCAN, OPTICS

4. Grid-Based Methods

Divide space into grid cells

Cluster grid cells instead of individual points
Examples: STING, CLIQUE

5. Model-Based Methods
Assume data follows certain statistical distribution
Find best fit model for each cluster
 Examples: Gaussian Mixture Models, EM algorithm

4. Partitioning Methods
K-Means Algorithm

How It Works:

Step 1: Choose K (number of clusters)

Step 2: Initialize

Randomly select K points as initial centroids

Or use K-Means++ for better initialization

Step 3: Assignment Step

For each data point:

Calculate distance to all centroids
Assign to nearest centroid

Step 4: Update Step

For each cluster:

Calculate mean of all points in cluster
Move centroid to this mean position

Step 5: Repeat

Repeat Steps 3-4 until:

Centroids stop moving
Maximum iterations reached
Assignments stop changing

Example:
 Data points: (1,1), (2,1), (4,3), (5,4)
K=2

Iteration 1:
Initial centroids: C1=(1,1), C2=(2,1)
Assign points to nearest centroid
Update centroids: C1=(1.5,1), C2=(4.5,3.5)

Iteration 2:
Reassign points based on new centroids
Update centroids again

Continue until convergence...

Choosing K:
Elbow Method:

Plot K vs. Within-Cluster Sum of Squares (WCSS)

Look for "elbow" point where improvement slows

Silhouette Score:

Measures how similar point is to its cluster vs. other clusters

Score ranges from -1 to 1
Higher is better

Advantages:

Simple and fast

Efficient for large datasets
Easy to implement

Disadvantages:
Must specify K in advance
Sensitive to initial centroids
Assumes spherical clusters
Sensitive to outliers
Only finds convex clusters
K-Medoids (PAM - Partitioning Around Medoids)

Difference from K-Means:

Uses actual data points as cluster centers (medoids)

Not the mean position

Advantages over K-Means:

More robust to outliers

Works with any distance metric
Medoids are interpretable (actual data points)

Disadvantage:

More computationally expensive than K-Means

5. Hierarchical Clustering
Two Approaches:
Agglomerative (Bottom-Up):

Start with each point as its own cluster

Repeatedly merge closest clusters
Continue until one cluster remains

Divisive (Top-Down):

Start with all points in one cluster

Repeatedly split clusters
Continue until each point is its own cluster

Agglomerative Process:

Step 1: Each point is a cluster

Step 2: Calculate distance between all cluster pairs

Step 3: Merge two closest clusters

Step 4: Update distance matrix

Step 5: Repeat Steps 3-4 until one cluster

Linkage Methods (How to measure cluster distance):

Single Linkage (MIN):

 d(Ci, Cj) = minimum distance between any two points
one from Ci and one from Cj

Can produce long, chain-like clusters

Sensitive to noise

Complete Linkage (MAX):

d(Ci, Cj) = maximum distance between any two points

Produces compact clusters

Less sensitive to outliers

Average Linkage:

d(Ci, Cj) = average distance between all pairs

Compromise between single and complete

Most commonly used

Centroid Linkage:

d(Ci, Cj) = distance between centroids

Dendrogram:
A tree diagram showing cluster merging:
 _____|_____
| |
___|___ ___|___
| | | |
P1 P2 P3 P4

To get K clusters, cut the dendrogram at height that gives K branches.

6. CURE (Clustering Using Representatives)

Key Innovation:

Uses multiple representative points per cluster instead of single centroid.

How It Works:

Step 1: Sample

Take random sample from dataset

Partition sample using hierarchical clustering

Step 2: Choose Representatives

For each cluster, select c well-scattered points

These are the "representative points"

Step 3: Shrink Representatives

Move representatives toward cluster centroid

Shrinking factor α (typically 0.2-0.3)

New position = representative + α × (centroid - representative)

Step 4: Merge Clusters

Distance between clusters = minimum distance between representatives

 Merge closest clusters

Step 5: Repeat

Update representatives
Continue merging

Why CURE is Better:

Handles Arbitrary Shapes:

Multiple representatives capture cluster shape

Not limited to spherical clusters

Robust to Outliers:

Shrinking reduces impact of outliers

Scalability:

Random sampling makes it efficient for large datasets

Parameters:

c: Number of representatives per cluster (typically 10-20)

α: Shrink factor (0.2-0.4)
Sample size (5-10% of data)

7. Chameleon
Key Idea:
Considers both interconnectivity and closeness when merging clusters.

Two-Phase Approach:

Phase 1: Graph Partitioning

Construct K-nearest neighbor graph

Each point connected to K nearest neighbors
Use graph partitioning to create initial small clusters

Phase 2: Agglomerative Merging

Merge clusters based on:

Relative Interconnectivity (RI)
Relative Closeness (RC)
Key Metrics:

Absolute Interconnectivity:

Sum of edge weights between two clusters

Relative Interconnectivity:

RI(Ci, Cj) = |EC(Ci, Cj)| / [(|EC(Ci)| + |EC(Cj)|) / 2]

Where:
- EC(Ci, Cj) = edges connecting Ci and Cj
- EC(Ci) = internal edges in Ci

Relative Closeness:

RC(Ci, Cj) = SEC(Ci, Cj) / [(SEC(Ci) + SEC(Cj)) / 2]

Where:
- SEC = average edge weight

Merging Criterion:

Merge if: RI(Ci, Cj) > threshold_RI AND RC(Ci, Cj) > threshold_RC

Advantages:

Finds arbitrary-shaped clusters

Handles clusters of different sizes and densities
More sophisticated than CURE
Disadvantages:

Computationally expensive
Many parameters to tune
Complex to implement

8. Density-Based Methods - DBSCAN

DBSCAN: Density-Based Spatial Clustering of Applications with Noise

Core Concepts:

ε (Epsilon): Radius of neighborhood around a point

MinPts: Minimum number of points to form dense region

Core Point: Point with at least MinPts neighbors within ε distance

Border Point: Not a core point, but in neighborhood of core point

Noise Point: Neither core nor border point

Algorithm:
Step 1: For each point P

Find all points within ε distance (ε-neighborhood)

If neighborhood has ≥ MinPts points, P is core point

Step 2: Connect core points

If two core points are within ε distance, they're in same cluster

Step 3: Add border points

Assign border points to nearest core point's cluster

Step 4: Label remaining points as noise

Example:
 Given: ε = 1, MinPts = 3

Points: • • • • ••
••• ••

Cluster 1: Dense region (left)

Cluster 2: Dense region (right)
Noise: Single point in middle

Advantages:
Discovers clusters of arbitrary shapes
Handles noise well
Doesn't require K as input
Robust to outliers

Disadvantages:

Struggles with varying density clusters

Sensitive to ε and MinPts parameters
Not suitable for high-dimensional data

Choosing Parameters:
ε:

Plot K-distance graph (distance to Kth nearest neighbor)

Look for "knee" point
This is optimal ε

MinPts:

Rule of thumb: MinPts ≥ dimensions + 1

Typically: 4-10 for 2D data

9. OPTICS (Ordering Points To Identify Clustering Structure)

Key Improvement over DBSCAN:

Doesn't require explicit ε parameter. Instead, creates ordering that can be analyzed for different ε
values.
Core Concepts:

Core Distance: Minimum ε needed for point to be core point

Reachability Distance:

reachability_distance(p, q) = max(core_distance(p), distance(p, q))

How It Works:

Step 1: Start with arbitrary point

Step 2: Find all neighbors within max_ε

Step 3: Calculate reachability distances

Step 4: Process point with smallest reachability distance

Step 5: Update reachability distances for unprocessed neighbors

Step 6: Repeat until all points processed

Output:

Reachability Plot: Shows cluster structure

X-axis: Points in processing order

Y-axis: Reachability distance
Valleys indicate clusters

Reachability Distance
| ___ ___
| | | | |
|___| |________| |___
Cluster1 Cluster2
Advantages:

Works with varying density clusters

No need to specify ε precisely
Single run gives information for multiple ε values
Visual cluster analysis through reachability plot

Disadvantages:

More complex than DBSCAN

Still requires MaxEps parameter
Computationally more expensive

10. Grid-Based Methods - STING

STING: Statistical Information Grid

Key Concept:
Divide spatial area into hierarchical rectangular grid cells.

Grid Structure:

Level 0 (coarsest): [--------]

|
Level 1: [----][----]
| |
Level 2 (finest): [-][-] [-][-]

What Each Cell Stores:

Statistical Information:

Count: Number of points

Mean: Average values
Standard deviation
Minimum and maximum values
Distribution type (normal, uniform, etc.)
How It Works:

Step 1: Build Grid Hierarchy

Create multi-level grid structure

Each cell in level i corresponds to 4 cells in level i+1 (for 2D)

Step 2: Calculate Statistics

For finest level: directly from data

For higher levels: aggregate from children cells

Step 3: Query Processing

Start from top level

Identify relevant cells
Drill down to relevant regions

Step 4: Remove Irrelevant Cells

Use statistical tests to eliminate cells that don't meet query criteria

Step 5: Find Cluster Regions

Identify connected regions at finest level

Advantages:

Very fast query processing

Independent of data order
Easy to implement
Handles large datasets efficiently

Disadvantages:

Quality depends on grid granularity

Can't detect clusters at different resolutions well
Sensitive to grid orientation
All cluster boundaries are horizontal or vertical

11. CLIQUE (Clustering In QUEst)

Key Innovation:

Finds clusters in high-dimensional subspaces automatically.

Core Concept:

If a unit (grid cell) is dense in k-dimensional space, it must be dense in (k-1)-dimensional

projections.

How It Works:

Step 1: Partition Each Dimension

Divide each dimension into ξ equal intervals

Creates grid structure

Step 2: Identify Dense Units (1D)

A unit is dense if it contains ≥ τ points

τ is density threshold

Step 3: Generate Candidate Units (2D)

Combine pairs of 1D dense units

Only if they share dimensions

Step 4: Prune

Keep only candidates where both 1D projections are dense

Step 5: Repeat

Increase dimensionality
Continue until no dense units found

Step 6: Generate Clusters

Connected dense units form clusters

Example:
 Given: 2D data, ξ=4 intervals, τ=3 points

Dimension X: [--][--][--][--]
Dimension Y: [--][--][--][--]

Find dense cells in X and Y

Combine to find dense 2D regions
These form clusters

Advantages:
Automatically finds subspace clusters
Handles high-dimensional data
Scales linearly with dataset size
Insensitive to data order

Disadvantages:

Grid-based, so limited by grid structure

Many parameters to tune (ξ, τ)
May miss clusters at boundaries
Exponential in dimensionality (though pruned efficiently)

12. Model-Based Methods

Core Idea:
Assume data is generated by mixture of probability distributions. Find parameters that best fit the
data.

Gaussian Mixture Model (GMM)

Assumption: Each cluster follows Gaussian (normal) distribution.

Parameters for each cluster:

Mean (μ): Center of cluster

Covariance (Σ): Shape and orientation
Weight (π): Proportion of data in cluster

Overall Model:
 P(x) = Σ πk × N(x | μk, Σk)

Where:
- K is number of clusters
- N is Gaussian distribution

EM Algorithm (Expectation-Maximization)
Used to find GMM parameters

Step 1: Initialize

Random initial values for μ, Σ, π

Step 2: E-Step (Expectation)

Calculate probability each point belongs to each cluster

P(cluster k | point xi) = πk × N(xi | μk, Σk) / Σ [πj × N(xi | μj, Σj)]

Step 3: M-Step (Maximization)

Update parameters based on probabilities

Update mean:

μk = Σ [P(k|xi) × xi] / Σ P(k|xi)

Update covariance:
 Σk = Σ [P(k|xi) × (xi - μk)(xi - μk)ᵀ] / Σ P(k|xi)

Update weight:

πk = (Σ P(k|xi)) / N

Step 4: Repeat

Alternate E-step and M-step

Continue until convergence (parameters stop changing)

Convergence Criteria:
Log-likelihood improvement < threshold
Maximum iterations reached
Parameter change < threshold

Example Iteration:

Initial: 3 clusters with random μ, Σ, π

E-Step: Calculate membership probabilities

Point (2,3): P(C1)=0.7, P(C2)=0.2, P(C3)=0.1
Point (5,6): P(C1)=0.1, P(C2)=0.8, P(C3)=0.1
...

M-Step: Update parameters

μ1 = weighted average of points likely in C1
Similar for μ2, μ3, and all Σ, π

Repeat until parameters stabilize

Types of Covariance:

Full Covariance:

Each cluster has its own shape and orientation

Most flexible, most parameters

Diagonal Covariance:

Axes aligned with coordinate system

Faster computation

Spherical Covariance:

Circular/spherical clusters
Simplest, like K-Means

Advantages:

Soft clustering (probabilistic membership)

Statistically principled
Can estimate cluster confidence
Handles overlapping clusters well

Disadvantages:

Assumes Gaussian distribution

Sensitive to initialization
May converge to local optima
Requires number of clusters as input
Computationally intensive

Other Model-Based Methods:

1. Mixture of Multinomial Distributions

For categorical data

Used in text clustering

2. Hidden Markov Models (HMM)

For sequential data

Time-series clustering

3. Bayesian Networks

Captures dependencies between variables

Complex but powerful
Comparison of Clustering Methods
Summary Table:

Method Shape of Clusters Handles Noise Complexity Requires K

K-Means Spherical Poor Low Yes
DBSCAN Arbitrary Good Medium No
CURE Arbitrary Good Medium Yes
STING Grid-aligned Fair Low No
GMM Elliptical Fair High Yes

When to Use What:

K-Means:

Large datasets
Roughly spherical clusters
Speed is priority
Clear separation between clusters

DBSCAN:

Arbitrary-shaped clusters
Many outliers/noise points
Don't know K in advance
Uniform density

Hierarchical (CURE/Chameleon):

Need cluster hierarchy

Small to medium datasets
Arbitrary shapes
Want to explore different K values

Grid-Based (STING/CLIQUE):

Very large datasets

Fast results needed
Spatial data
High-dimensional data (CLIQUE)

Model-Based (GMM):

Need probability estimates

Overlapping clusters
Elliptical clusters
Statistical inference required
Best Practices for Clustering
1. Data Preprocessing:

Normalization:

Scale features to same range

Prevents features with large ranges from dominating

Missing Values:

Impute or remove
Can affect distance calculations significantly

Outlier Treatment:

Identify and handle outliers

Can use robust methods or remove extreme values

2. Feature Selection:

Remove Irrelevant Features:

High-dimensional data can suffer from "curse of dimensionality"

Use PCA or feature selection techniques

Create Meaningful Features:

Domain knowledge helps

Feature engineering can improve results

3. Choosing the Right Method:

Consider:

Dataset size
Expected cluster shapes
Presence of noise
Need for interpretability
Computational resources

4. Validation:

Internal Measures:

Silhouette Score: -1 to 1, higher is better

Davies-Bouldin Index: Lower is better
Dunn Index: Higher is better
External Measures (if labels available):

Adjusted Rand Index (ARI)

Normalized Mutual Information (NMI)
Fowlkes-Mallows Index

Silhouette Score Formula:

s(i) = [b(i) - a(i)] / max{a(i), b(i)}

Where:
- a(i) = average distance to points in same cluster
- b(i) = average distance to points in nearest cluster

5. Interpretation:
Analyze Clusters:

What characteristics define each cluster?

Are clusters meaningful for the domain?
What distinguishes one cluster from another?

Visualization:

2D/3D plots (use dimensionality reduction if needed)

Heatmaps showing cluster characteristics
Dendrograms for hierarchical methods

Common Pitfalls and Solutions

Problem 1: Curse of Dimensionality

Issue: In high dimensions, all points appear equally distant

Solutions:

Use subspace clustering (CLIQUE)

Apply dimensionality reduction (PCA, t-SNE)
Use feature selection
Problem 2: Varying Density Clusters

Issue: DBSCAN fails with clusters of different densities

Solutions:

Use OPTICS instead

Try hierarchical methods
Use local density measures

Problem 3: Scalability

Issue: Method too slow for large datasets

Solutions:

Use sampling
Grid-based methods
Parallel/distributed implementations
Mini-batch K-Means

Problem 4: Choosing K

Issue: Don't know optimal number of clusters

Solutions:

Elbow method
Silhouette analysis
Gap statistic
Try density-based methods (don't require K)

Problem 5: Initialization Sensitivity

Issue: Results vary with different starting points

Solutions:

Run multiple times with different seeds

Use K-Means++ initialization
Use deterministic initialization
Consider hierarchical clustering for initialization
Practical Applications
1. Customer Segmentation

Method: K-Means or GMM Features: Demographics, purchase history, behavior Use: Targeted
marketing, personalized recommendations

2. Image Segmentation

Method: K-Means on pixel colors Features: RGB values, texture, position Use: Object detection,
medical imaging

3. Document Clustering

Method: K-Means or hierarchical Features: TF-IDF vectors, word embeddings Use: Topic
discovery, information organization

4. Anomaly Detection

Method: DBSCAN or Isolation Forest Features: Transaction amounts, patterns, timing Use: Fraud
detection, network security

5. Gene Expression Analysis

Method: Hierarchical clustering Features: Gene expression levels Use: Disease classification, drug
discovery

6. Social Network Analysis

Method: Community detection (variant of clustering) Features: Connection patterns, interactions

Use: Influence analysis, recommendation systems

Key Formulas Summary

Distance Metrics:
 Euclidean: d = √(Σ(xi - yi)²)

Manhattan: d = Σ|xi - yi|

Cosine Similarity: sim = (x·y) / (||x|| ||y||)

Jaccard: J = |A∩B| / |A∪B|

Evaluation Metrics:

Silhouette Score: s(i) = (b(i) - a(i)) / max{a(i), b(i)}

Davies-Bouldin Index: DB = (1/K) Σ max((σi + σj) / d(ci,cj))

Within-Cluster SS: WCSS = ΣΣ ||xi - μk||²

Algorithm Specifics:

K-Means Update: μk = (1/|Ck|) Σ xi

DBSCAN Core Point: |Nε(p)| ≥ MinPts

GMM Probability: P(x) = Σ πk × N(x|μk,Σk)

Exam Tips and Important Points

Unit III - Classification:
Must Know:
 Decision tree construction process (information gain, Gini index)
Bayes theorem and Naive Bayes assumptions
Backpropagation steps (forward pass, error calculation, backward pass)
KNN working with example
Genetic algorithm steps (selection, crossover, mutation)

Common Exam Questions:

Calculate information gain for decision tree split

Apply Bayes theorem to classify new instance
Explain overfitting and how to prevent it
Compare different classification methods
Trace backpropagation for simple neural network

Unit IV - Clustering:
Must Know:

Difference between clustering and classification

Distance metrics for different data types
K-Means algorithm steps with example
DBSCAN concepts (core, border, noise points)
Hierarchical clustering linkage methods
Difference between partitioning, hierarchical, and density-based methods

Common Exam Questions:

Perform K-Means clustering on given data

Identify core/border/noise points in DBSCAN
Compare DBSCAN and K-Means
Explain curse of dimensionality
Calculate silhouette score or other validation metrics
Draw dendrogram for hierarchical clustering

Important Diagrams to Remember:

Decision tree structure

Neural network architecture
K-Means iterations
DBSCAN point types visualization
Dendrogram
Grid structure for STING/CLIQUE

Key Comparisons:
Classification vs. Clustering
K-Means vs. K-Medoids
DBSCAN vs. OPTICS
Agglomerative vs. Divisive hierarchical clustering
 Supervised vs. Unsupervised learning

Quick Revision Checklist

Classification (Unit III):

☐ Issues in classification (overfitting, evaluation metrics) ☐ Decision tree construction ☐

Information gain and Gini index ☐ Bayes theorem and Naive Bayes ☐ Neural network structure ☐
Backpropagation algorithm ☐ KNN working and distance metrics ☐ Genetic algorithm components

Clustering (Unit IV):

☐ Data types and distance measures ☐ Categories of clustering methods ☐ K-Means algorithm ☐
Hierarchical clustering methods ☐ CURE algorithm ☐ Chameleon algorithm ☐ DBSCAN (core,
border, noise) ☐ OPTICS reachability plot ☐ STING grid structure ☐ CLIQUE subspace clustering
☐ GMM and EM algorithm ☐ Cluster validation metrics

End of Notes

Remember: Practice numerical examples for each algorithm. Understanding the "why" behind each
method is as important as knowing "how" they work. Good luck with your studies!