Expectation-Maximization algorithm
Expectation-Maximization algorithm can be used for the latent variables (variables that
are not directly observable and are actually inferred from the values of the other observed
variables) too in order to predict their values with the condition that the general form of
probability distribution governing those latent variables is known to us. This algorithm is
actually at the base of many unsupervised clustering algorithms in the field of machine
learning.
Algorithm:
1. Given a set of incomplete data, consider a set of starting parameters.
2. Expectation step (E – step): Using the observed available data of the dataset,
estimate (guess) the values of the missing data.
3. Maximization step (M – step): Complete data generated after the expectation
(E) step is used in order to update the parameters.
4. Repeat step 2 and step 3 until convergence.
The essence of Expectation-Maximization algorithm is to use the available observed data of
the dataset to estimate the missing data and then using that data to update the values of the
parameters. Let us understand the EM algorithm in detail.
Unit-3 NEHA UNNISA
Machine Learning Asst Prof
Initially, a set of initial values of the parameters are considered. A set of
incomplete observed data is given to the system with the assumption that the
observed data comes from a specific model.
The next step is known as “Expectation” – step or E-step. In this step, we use the
observed data in order to estimate or guess the values of the missing or
incomplete data. It is basically used to update the variables.
The next step is known as “Maximization”-step or M-step. In this step, we use
the complete data generated in the preceding “Expectation” – step in order to
update the values of the parameters. It is basically used to update the hypothesis.
Now, in the fourth step, it is checked whether the values are converging or not,
if yes, then stop otherwise repeat step-2 and step-3 i.e. “Expectation” – step and
“Maximization” – step until the convergence occurs.
Flow chart for EM algorithm –
Usage of EM algorithm –
It can be used to fill the missing data in a sample.
It can be used as the basis of unsupervised learning of clusters.
It can be used for the purpose of estimating the parameters of Hidden Markov
Model (HMM).
It can be used for discovering the values of latent variables.
Advantages of EM algorithm –
It is always guaranteed that likelihood will increase with each iteration.
The E-step and M-step are often pretty easy for many problems in terms of
implementation.
Solutions to the M-steps often exist in the closed form.
Disadvantages of EM algorithm –
It has slow convergence.
It makes convergence to the local optima only.
It requires both the probabilities, forward and backward (numerical optimization
requires only forward probability).
------------------------------------------------------------------------------------------------
Unit-3 NEHA UNNISA
Machine Learning Asst Prof
Fuzzy c-means algorithm
Fuzzy logic principles can be used to cluster multidimensional data, assigning each point
a membership in each cluster center from 0 to 100 percent.
This algorithm works by assigning membership to each data point corresponding to each
cluster center on the basis of distance between the cluster center and the data point. More the
data is near to the cluster center more is its membership towards the particular cluster center.
Clearly, summation of membership of each data point should be equal to one.
K-Means versus Fuzzy C-Means
Unit-3 NEHA UNNISA
Machine Learning Asst Prof
Steps in Fuzzy C-Means
The process flow of fuzzy c-means is enumerated below:
1. Assume a fixed number of clusters k.
2. Initialization: Randomly initialize the k-means μk associated with the clusters
and compute the probability that each data point xi is a member of a given
cluster k, P(point xi has label k|xi, k).
3. Iteration: Recalculate the centroid of the cluster as the weighted centroid given
the probabilities of membership of all data points xi:
Unit-3 NEHA UNNISA
Machine Learning Asst Prof
Termination: Iterate until convergence or until a user-specified number of iterations has been
reached (the iteration may be trapped at some local maxima or minima).
Pros and Cons
Now comes the time to evaluate the algorithm itself!
Pros
1. Gives best result for overlapped data set and comparatively better then k-means algorithm.
2. Unlike k-means where data point must exclusively belong to one cluster center here data
point is assigned membership to each cluster center as a result of which data point may belong
to more then one cluster center.
Cons
1. Apriori specification of the number of clusters.
2. With lower value of β we get the better result but at the expense of more number of
iteration.
3. Euclidean distance measures can unequally weight underlying factors.
4. The performance of the FCM algorithm depends on the selection of the initial cluster
center and/or the initial membership value.