L14 - K Means, GMM, Clustering Measures

Question 1

Hierarchical clustering is a deterministic method. What does this mean?

Answer 1

We can repeat the method and get the same results. Generating the same dendrogram.

Question 1

What is the issue with Hierarchical clustering?

Answer 1

Slow -> Can hit O(N^3)

Question 2

What are ‘partition clustering methods’?

Answer 2

1. Partitions dimensional space as opposed to clustering points.
   
   2. Breaks space into K partitions that are non-overlapping
   3. Then we can compare N data-points to K clusters

Question 3

What is K-means clustering?

Answer 3

A partition clustering method

Question 4

What is the process of K-means clustering…

Answer 4

1. Input N data points and K cluster
   
   2. Choose K random data points to be the initial cluster centroids
   3. Assign every point in N to it’s nearest K centroid
   4. Recompute the centroid of each cluster to be the actual centroid
   5. Check for convergence or termination criteria
   6. Repeat 3 to 5

Question 5

What are some options for the terminations criteria?

Answer 5

1. Few or no re-assignment of data points to different clusters
   
   2. Few or no change to centroids
   3. Minimal change in sum of square errors (SSE)

Question 6

What are the pros and cons of using K-means?

Answer 6

1. Pros:
   1. Easy to understand and implement
   2. Efficient -> O(ndk*t) -> O(n) i.e Linear complexity
2. Cons:
   1. Requires a centroid to be calculable -> Not possible with categorical data
   2. Effectiveness dependent on selection of K
   3. Sensitive to outlier

Question 7

What are the limitations of K-means?

Answer 7

1. Struggles with clusters of different sizes
2. Struggles with clusters of different shapes
3. Struggles with clusters of different density
4. Results depend on starting centroids -> Same data can be clustered completely differently with different initial centroids.

Question 8

How do we overcome the limitations of K-means?

Answer 8

Pre-processing -> Eliminating outliers or standing or normalising the data.

Post processing -> Merge clusters with low SSE, Split loose clusters, Eliminate outlier clusters.

Question 9

What method can we use to choose K?

Answer 9

Elbow method -> Plot SSE for multiple values of K and find the elbow.

Question 10

Since K-means is sensitive to outliers, what clustering method can be used as an alternative?

Answer 10

GMM -> Gaussian Mixture Models

Question 11

What is GMM? What issues of K-means does it solve?

Answer 11

1. A clustering method that clusters based on probabilities
2. E.g A is 30% clusters blue and 70% cluster green
3. Solves issue in K-means regarding cluster outliers

Question 12

What are the pros and cons of GMM compared to K-means?

Answer 12

1. Pros:
   1. Convergence quicker
   2. Deals well with outliers
2. Cons:
   1. More complex
   2. More computationally expensive

Question 13

Give main differences between K-means and GMM

Answer 13

1. K-means:
   1. Minimises sum of squared distances
   2. Hard assignment
   3. Assumes spherical clustering
2. GMM:
   1. Maximises log-likelihood
   2. Soft assignment of points to clusters
   3. Assumes elliptical clusters

Question 14

How can we tell if our clustering is correct?

Answer 14

1. External validation -> Measure against externally supplied labels -> Use distance or incidence matrix
2. Internal validation -> Measure whether points that should be close/far from each other are actually so -> Use silhouette coefficient
3. Relative validation -> Compare one clustering method to another and see if they agree

Question 15

What is the silhouette coefficient? What is the best and worst values for it?

Answer 15

1. A coefficient used in internal validation method for cluster validation i.e checking distances between points are as they are expected to be,
2. Best = 1, worst = -1