Module 4
EM Algorithm for clustering
Web Ref : [Link]
[Link]
gaussian distribution
• The normal or gaussian distribution is a continuous probability distribution.
• These distributions differ in their location and scale parameters: the mean of the
distribution defines its location, and the standard deviation defines the scale.
• Note: Hence, wherever we talk about the parameters of the EM algorithm, we are
referring to the mean and standard deviation that we are defining each cluser by.
Intuition
• If we have three data points [1,2,X] are drawn from a Gaussian
distribution
G(1,1)
Best Guess for X ??
• If we have three data points [0,1,2] are drawn from a Gaussian
distribution
G(u,1) best guess for u??
General idea
• If we have three data points [1,2,X] are drawn from a Gaussian
distribution
G(u,1) best guess for [x,u] ??
Guess u = 0 then X is likely 0
Guess u =1 the x is likely 1
Converge
U = 1+2+x /3 = X
General Idea
• It starts out with placing K Gaussian distributions randomly.
• These random Gaussian distributions will have parameters (mean and standard deviation).
• Now, for each data point, we can find out the probability of being in each Gaussian
distribution.
• Once it has computed the probabilities, we can iteratively compute the parameters of the
Gaussian distributions, to find the new mean and new standard deviation, such that it fits
the assigned points better.
• We keep iterating till we reach convergence.
EM Algorithm
• Let's take an example of a few points in 1 dimension, for which we have to
perform Expectation Maximization Clustering.
• We will take 2 Gaussian distributions, such that we'll find each point to belong to
either of the 2 Gaussian distributions. Our 2 Gaussians here are shown in Blue
and Yellow. Our 2 Gaussians have the same variance in this case, and their
mean is at their respective centers.
EM Algorithm
How likely each of the points are to belong to the blue or
yellow distribution.
EM Algorithm
• Similarly, we will calculate the probability of each point for lying in the blue and
yellow distributions, and colour it according to the likeliness of blue and yellow:
EM Algorithm
• Now that we have the probability of each point
lying in the blue and yellow distributions, we
use these values, to calculate the new mean
and new variance of the 2 distributions. We
use this new mean and variance to plot our
new blue and yellow distributions.
• Quite obviously, the one 'majority' yellow point
will keep the yellow gaussian almost at it's
place, whereas the many 'majority' blue points
pull the blue gaussian towards the right
EM Algorithm
• We repeat the same procedure of using the new gaussian distributions with the
points, for our second iteration, and solve to get an updated distribution. We can
go on to solve for multiple iterations, and our final distribution would look similar
to this:
Simplified steps of EM Clustering
• Initially,we set the number of clusters K, and randomly initialize each cluster with
Gaussian distribution parameters.
• STEP 1: Expectation: We compute the probability of each data point to lie in
each cluster.
STEP 2: Maximization: Based on STEP 1, we will calculate new Gaussian
parameters for each cluster, such that we maximize the probability for the points to
be present in their respective clusters.
• Essentially, we repeat STEP 1 and STEP 2, until our parameters remain the same.
Hard vs Soft Clustering
• EM Clustering, we talk about probability of each data point to be present in either
of the clusters. It is completely possible for multiple clusters to partly share a
portion of the data point, since we are only talking about respective probabilities
of the point with respect to the clusters.
K-Means vs EM
K-Means
• Hard Clustering of a point to one particular cluster.
• Cluster is only defined by mean.
• We can only have spherical clusters
• It makes use of the L2 norm when optimizing
Expectation-Maximization
• Soft Clustering(It gives a probability of any point belonging to a cluster).
• Cluster is defined by mean and standard deviation
• We can have elliptical clusters too
• It does not depend on L2 norm, but is based on Expectation, the probability of the point belonging to a
particular cluster. This makes K-means biased towards spherical clusters.
Application
• Application
• Image segmentation
• Estimating motion models for tracking
• Hidden Markov Models
LDA
• Supervised Dimensionality Reduction Technique.
• It is used to Project the features in higher dimension space inti a lower
dimension space.
• It is used to identify a linear combination of features that best
separates classes within a dataset.
Concept LDA
• when data points belonging to two classes are plotted, if they are not linearly
separable LDA will attempt to find a projection that maximizes class separability.
• The image shows classes (black and green) that are not linearly separable. LDA finds
a new axis (red dashed line) that maximizes the distance between class means while
minimizing within-class variance, improving class separation for better classification.
LDA working
• [Link]
-analysis
/
• [Link]
-analysis-360-digitmg-6ttnc
/
Difference between LDA and PCA
Feature PCA LDA
Learning Type Unsupervised Supervised
Primary Goal Maximize Maximize class
overall data separation
variance
Data Does not use Uses class
Dependency class labels labels
Best For Data Classification,
compression, enhancing
feature class
extraction separability
when no labels
are available