Week 6

Question 1

What is the aim of cluster analysis?

Answer 1

To create a grouping of objects such that objects within a group are similar and objects in different groups are not similar.

Question 2

How is a cluster defined in K-means clustering?

Answer 2

It is a representative point, the mean of the objects that are assigned to the cluster.

Question 3

What is mu_k in K-means clustering?

Answer 3

The mean pont for the k-th cluster.

Question 4

What is z_nk in K-means clustering?

Answer 4

A binary indictaor variable that is 1 if object n is assigned to cluster k and 0 otherwise.

Question 5

What requirement leads to SIGMA_k z _nk = 1 in K-means clustering?

Answer 5

Each object has to be assigned to one and only one cluster.

Question 6

What is the equation for mu_k in K-means clustering?

Answer 6

mu_k = (SIGMA_k of z_nk x_n) / (SIGMA _n of z_nk)

Question 7

What are the four steps performed in K-means clustering?
You start with initial values for the cluster means, mu₁, …, mu_k.

Answer 7

1. For each data object x_n, find the closes cluster mean and set z_nk =1 and z_nj = 0 for all j != k.
2. Stop if all z_nk are unchanged compared to the previous iteration.
3. Update each mu_k.
4. Return to step 1.

Question 8

What is the equation for D, the total distance between objects and their cluster centers, in K-means clustering?

Answer 8

D = SIGMA _{n=1 to n} SIGMA _{k=1 to K} z_nk (x_n - mu_k)^T (x_n - mu_k)

Question 9

What solution do we use to prevent K-means clustering from only reaching a local minimum?

Answer 9

We run the algorithm from several random starting points and use the solution that gives the lowest value of D, the total distance.

Question 10

What is the problem with using D, the total distance, as a model selection criteria in K-means clustering?

Answer 10

It decreases as K increases, so more clusters lead to a better result. This shows that, just like maximum likelihood, it kinda measures complexity.

Question 11

What is clustered in feature selection?

Answer 11

Features are clustered based on their values across objects rather than clustering the objects.

Question 12

Parametric density estimation

Answer 12

When the distribution of x given a class is a single model. So when p(x|C_i) has one model.

Question 13

Semiparametric density estimation

Answer 13

When you assume a mixture of different models, so when p(x|C_i) is a mixture of densities.

Question 14

Explain the elbow plot:

Answer 14

It’s the plot with the amount of clusters (K) on the x-axis and the reduction in variation within clusters on the y-axis. There is a decrease in reduction at some point, called the elbow.

Question 15

How do you calculate Euclidian distance between two points?

Answer 15

root(x² + y²)

Question 16

Describe the formula for total distance/ reconstruction error D in K-means clustering, using words:

Answer 16

The sum of all datapoints, for each cluster k, the z of whether that datapoint is in cluster k (so 0 or 1) times the Euclidean distance between the datapoint and the mean of that cluster k.

Question 17

Entropy of a random variable

Answer 17

The average level of uncertainty or info associated with the variable’s possible outcomes.

Question 18

What is the formula for the entropy H(X) of a discrete random variable X which takes values in the set S and is distributed according to p: S -> [0,1] ?

Answer 18

H(X) = - SIGMA_{x in S} p(x) logp(x)

Question 19

MI (abbreviation)

Answer 19

Mutual information

Question 20

Mutual information (in probability theory) of two random variables

Answer 20

A measure of the mutual dependence between the two variables, so it quantifies the amount of info obtained about one random variable by observing the other random variable.

Question 21

How does statistical mixture represent each cluster?

Answer 21

As a probability density.

Question 22

How does the EM algorithm solve the fact that there’s a summation inside the logarithm likelihood?

Answer 22

It derives a lower bound on the likelihood, which can be maximized instead of the log likelihood.

Question 23

What step do you first need to take when you want to use Jensen’s inequality to lowe bound the likelihood in the EM algorithm?

Answer 23

Make the right-hand side of the log likelihood look like the log of an expectation.

Question 24

How do you obtain updates of each of the parameters in the bound B for each iteration in the EM algorithm?

Answer 24

Take the partial derivative of the bound B with respect to the relevant parameter, set to zero and solve.

Question 25

When do you specify the number of components (clusters) in the EM algorithm?

Answer 25

A priori.

Question 26

How do you go about the EM algorithm after setting the amount of components?

Answer 26

Initialise some of the parameters: randomly choose means and covariances of the mixture components and initialise pi_k by assuming a prior distribution over the components.

Question 27

What do you compute in the E-step after initiliasing the mean, covariance and pi_k in the EM algorithm?

Answer 27

q_nk

Question 28

What do you do in the EM algorithm after you’ve initialised the means, covariances, pi_k and computed q_nk?

Answer 28

Subsequently update pi_k, mu_k and SIGMA_k.

Question 29

What do the values of q_nk represent in the EM algorithm?

Answer 29

The posterior probability of the objects belonging to components.

Question 30

What are the four parameters that are updated in the EM algorithm?

Answer 30

pi_k, mu_k, SIGMA_k and q_nk.

Question 31

What does pi_k represent in the EM algorithm?

Answer 31

p(z_nk = 1)
The probability that a point is part of a certain component, a particular mixture model in the case of EM.

Question 32

What do mu_k and SIGMA_k denote in the EM algorithm?

Answer 32

The parameters of the k-th mixture model (the k-th Gaussian), so the mean and the variance.

Question 33

Give Jensen’s inequality:

Answer 33

log E_p(z) {f(z)} >= E_p(z) {log f(z) }

Question 34

What is the essence of Jensen’s inequality?

Answer 34

The log of the expected value of f(z) is always greater than or equal to the expected value of log f(z).

Question 35

In the EM algorithm, why do we divide the expression inside the summation over k in the log likelihood by a new variable q_nk?

Answer 35

Because we need to make that side of the equation look like the log of an expectation.