K-Means

Question 1

Define monothetic cluster

Answer 1

Members have some common property

Question 2

Define polythetic cluster

Answer 2

Cluster members are similar to each other

Question 3

Define hard clustering

Answer 3

Clusters do not overlap

Question 4

Define soft clustering

Answer 4

Clusters may overlap

Question 5

Define flat clustering

Answer 5

set of clusters without any explicit structure that would relate clusters to each other

Question 6

Define hierarchical clustering

Answer 6

Produces a hierarchy of clusters

Question 7

K-D trees, monothetich or polythetic?

Answer 7

Monothetic, few cuts describe each member of the region

Question 8

K-D trees, hard or soft boundaries?

Answer 8

Hard

Question 9

K-D trees, flat or hierarchical?

Answer 9

Hierarchical, we can cut the tree at any depth

Question 10

K-means, monothetic or polythetic?

Answer 10

Polythetic

Question 11

K-means, hard or soft boundaries?

Answer 11

Hard

Question 12

K-means, flat or hierarchical?

Answer 12

Flat

Question 13

Gaussian mixtures, monothetic or polythetic?

Answer 13

Polythetic

Question 14

Gaussian mixtures, hard or soft boundaries?

Answer 14

Soft

Question 15

Gaussian mixtures, flat or hierarchical?

Answer 15

Flat

Question 16

Agglomerative clustering, monothetic or polythetic?

Answer 16

Polythetic

Question 17

Agglomerative clustering, hard or soft boundaries?

Answer 17

Hard

Question 18

Agglomerative clustering, flat or hierarchical?

Answer 18

Hierarchical

Question 19

What are some common use cases for K-means? (2)

Answer 19

• Discovering classes (unsupervised)
• Dimensionality reduction

Question 20

How can k-means be used for dimensionality reduction?

Answer 20

Run k-means, replace features with a cluster number

Question 21

K-means clustering algorithm

Answer 21

1. Place centroids c₁, …, c_k randomly
2. Repeat until convergence
   
   1. For each point x_i
      
      1. _​Find the nearest centroid c_j
      2. Assign point x_i to cluster j
   2. For each cluster, make the centroid c_j closest to all the data points in the cluster (for euclidian distances this is the mean)

Question 22

What does it mean that K-means converges to a local minimum?

Answer 22

Different starting points can produce difference clusters

Question 23

Whats the variance for K-means?

Answer 23

Sum of distance to every points centroid

Question 24

What is a scree plot?

Answer 24

Question 25

How can you pick a good value of K for k-means? (2)

Answer 25

• class labels may suggest a value (digits recognition - 10 digits)
• optimize V visually from a scree plot (where mountain ends and rubble begins)

Question 26

How can we extrinsicly excaulate a clustering algorithm?

Answer 26

Use it as part of another problem (e.g. removing outliers for digit recognition), and see if it helped

Question 27

How can we intrinsicly evaluate a clustering algorithm (with reference clusters)?

Answer 27

• Align reference clusters R_j with system produced clusters C_i
• Measure the accuracy

Question 28

How do we measure the accuracy in intrinsic clustering evaluation (with reference clusters)?

Answer 28

The sum of the overlapping instances in each pair of system and reference clusters over the number of training instances

Question 29

How can we align a reference cluster with a system cluster?

Answer 29

• Pick the pair of reference and system clusters with the maximum overlap
• Greedly reassign clusters until each reference cluster has a unique system cluster

Question 30

How can we intrinsicly evaluate clusters with humans?

Answer 30

• Sample pairs
• Ask humans if they should be in the same cluster
• Count errors and compute accuracy

Question 31

What is the advantage of intrinsic evaluation with humans vs reference clusters?

Answer 31

• Does not require cluster alignment strategy
• Can handle overlapping classes

Question 32

How can we use K-Means as part of image recognition?

Answer 32

• Split image into regions
• Compute statistics of regions
• Use K-Means to cluster regions
• Put clusters together like bag-of-words { 4 * “C27”, 15 * “C44”, … }
• Use any algorithm on the flat representation

Question 33

What does K-Means minimize?

Answer 33

the aggregate intra-cluster distance