Clustering

Question 1

What is a Centroid

Answer 1

The mean vector of all items assigned to a given cluster (i.e. the mean of their feature vectors)

Question 2

What are partitioning methods (Clustering)

Answer 2

Clustering methods that partition a dataset into a predefined number of clusters

Question 3

Steps of Lloyd’s Algorithm for k-means clustering

Answer 3

1. randomly select k initial cluster centroids
2. assign every item to its nearest centroid
3. recompute the centroids
4. Repeat from step 2 until no reassignments occur

Question 4

What are the limitations of k-Means, in particular Lloyd’s algorithm

Answer 4

• must specify number of cluster k
• Lloyd’s algorithm is highly sensitive to choice of initial clusters
• assumes spherical shaped clusters
• unable to handle outliers and noise

Question 5

Advantages of k-Means

Answer 5

• fast, easy to implement the heuristics
• “good enough” in a wide variety of tasks and domains

Question 6

What is a common strategy for tackling cluster initialisation in k-Means

Answer 6

run the algorithm multiple times, select the solution(s) that scores well according to some validation measure

Question 7

Explain how the centroids are initialised in the k-means++

Answer 7

1. select first centroid uniformly at random
2. Repeat k - 1 times:

• pick a point with probability proportional to the shortest distanced centroid
• add point to Centroids

Question 8

What is the intuition for k-means++ initialisation

Answer 8

The cluster centroids are initialised by favouring points that are farther away from existing centroids, resulting in the centroids being spread out across the dataset.

Question 9

What is cluster validation

Answer 9

Measures for automatically producing a quantitative evaluation of the quality of a clustering

Question 10

What is the Silhouette Measure

Answer 10

Validation measure which quantifies degree to which each item belongs in its assigned cluster, relative to the other clusters

Question 11

How to calculate the silhouette width

Answer 11

a = average distance to all other items in same cluster
b = average distance to all other items in nearest competing cluster
silhouette width = (b-a) / max(a, b)

Question 12

How to compute the average silhouette width (ASW)

Answer 12

calculate overall score for a clustering by averaging the silhouette widths for all items

Question 13

Brief description of Agglomerative Hierarchical Clustering

Answer 13

Begin with each item assigned to its own cluster. Apply a bottom-up strategy where, at each step, the most similar pair of clusters are merged

Question 14

Brief description of Divisive Hierarchical Clustering

Answer 14

Begin with a single cluster containing all items. Apply a top-down strategy where, at each step, a chosen cluster is split into two sub-clusters

Question 15

AGNES algorithm

Answer 15

Inputs: Distance matrix, Cluster Metric
1. Assign every item to its own cluster (leaf nodes)
2. Find the closest pair of clusters and merge them
3. Compute distances between the new cluster and each of the remaining cluster
4. Repeat from step 2 until there is one cluster (root node)

Question 16

Define the three Cluster Metrics (Linkage)

Answer 16

Single Linkage: define cluster distance as the smallest pairwise distance between items from each cluster
Complete Linkage: define cluster distance as the largest pairwise distance between items from each cluster
Average Linkage: define cluster distance as the average of all pairwise distances between items from each cluster

Question 17

Divisive Algorithms Template

Answer 17

1. Start with all items in a single cluster
2. Repeat until all items are in their own cluster

• choose an existing cluster to split using some splitting criterion
• replace the chosen cluster into two sub-clusters

Question 18

Advantages of Hierarchical Clustering

Answer 18

• Allows for multiple levels of granularity, both broad clusters and niche clusters.
• No requirement to select the “correct” value for number of clusters in advance.

Question 19

Disadvantages of Hierarchical Clustering

Answer 19

• Poor decisions made early in the clustering process can greatly influence the quality of the final clustering.
• Once a merging or splitting decision has been made, there exists no facility to rectify a mistake at a later stage.
• More computationally expensive than partitional methods, particularly for AGNES

Question 20

What constitutes high quality clusters

Answer 20

high intra-cluster similarity and low inter-cluster similarity

Question 21

in K-means, the global optimum may be found using what techniques?

Answer 21

• deterministic annealing
• genetic algorithms

Question 22

What is a Medoid

Answer 22

A point in the cluster, whose dissimilarities with all the other points in the cluster are minimum

Question 23

what is the basic idea of Partitioning Around Medoids (PAM)

Answer 23

start from an initial set of medoids and iteratively replace a medoid by a non-medoid if it reduces the total distance of the resulting clustering