Clustering

Question 1

Explain the steps taken in the K-means algorithm

Answer 1

1. Randomly generate k random centroids.
2. Check the distance from each sample to all centroids.
3. Assign the closest centroid to each sample.
4. Compute new centroids.
5. If no convergence, go back to 2.

Question 2

What are the pros and cons of k-means clustering?

Answer 2

Pros
- Relatively simple to implement
- Scale to large datasets
- Guarantee convergence (local optima)

Cons
- User has to define k
- Depends on initial values
- Cluster boundaries are equidistant to centers
- Cannot model covariances well

Question 3

What are the two types of hierarchical clustering? Define them

Answer 3

Agglomerative (bottom-up): start with all samples as clusters, then merge two cluster with smallest intergroup dissimilarity iteratively

Divisive (top-down): start with one cluster that has all data, then split cluster with largest between-group dissimilarity iteratively

Question 4

Define mixture models

Answer 4

They present p(x) as a mixture of distributions. Can then use Expectation-Maximisation (EM) to find (local) MLE estimators of parameters.

Question 5

Write the formula for “responsibility” in the context of mixture models

Answer 5

Check notes

Question 6

What is the silhouette coefficient? What is it used for?

Answer 6

s_i = (b-a) / {max(a, b)}
a: mean distance between sample i and all other points in the same class
mean distance between sample i and all other points in the next nearest cluster

Can be used to select the optimal number of clusters

Question 7

What does the rand index measure?

Answer 7

The similarity between two cluster assignments