Week 6

Question 1

K means algo

Answer 1

If 2 mean points are equidistant from point, choose one with lower index

Question 2

K median algo

Answer 2

As image except 2.1.2 is not abs value squared

Eg for (3,4) and (4,2) manhattan dist is 3

Question 3

K means ++

Answer 3

Same as K means but to initialise mean points use

When selecting centroids 2,…, k, you are again choosing a random number each time to pick a point to use as a centroid. The probability distribution can be thought of as a number line and you are picking the number immediately to the right of the randomly generated P

Question 4

How to choose k for k means etc

Answer 4

K means score is sum of square distances of points from associated centroids

Question 5

K means and K median are examples of what kind of clustering

Answer 5

Flat

Question 6

2 types of hierarchical clustering

Answer 6

Agglomerative (bottom up)

Divisive (top down)

Question 7

Agglomerative clustering on a graph

Answer 7

Assuming each edge represents the similarity of the 2 nodes it connects

Begin with each node is a cluster

Find the single edge with largest value

Let those 2 nodes be one cluster

Repeat until k = # of clusters

Question 8

How to visualise the stages of clustering in Agglomerative

Answer 8

Question 9

Bisection K means

Answer 9

(Divisive) begin at one cluster and split using sparsest cut

Question 10

Sparsest cut

Answer 10

Question 11

Single agglomerative clustering

Answer 11

Single: edge with highest similarity

Question 12

Average linkage agglomerative clustering

Answer 12

Average: sum all edges between 2 clusters divided by # of edges between 2clusters

Question 13

Complete linkage agglomerative clustering

Answer 13

Complete linkage: minimax , combine clusters with highest least similar edge