Skip to article frontmatterSkip to article content

Partitional clustering

Clustering by hand

Consider this dataset.

     Sample     $X$  
  ------------ ----- 
       #1        1   
       #2        2   
       #3        5   
       #4        6

Run one iteration of K-means with two clusters initialized with centroids μ1=1\mu_1=1 and μ2=6\mu_2=6. Report the two new centroid values.

Solutions

Points #1 and #2 get assigned to cluster 1. Points #3 and #4 get assigned to cluster 2. So the new means are μ1=1.5\mu_1=1.5 and μ2=5.5\mu_2=5.5.

WSS, BSS, TSS, part I

Consider a dataset D={X1,…Xn}\mathcal{D}=\{X_1,\ldots X_n\} that has been clustered into 3 groups. Let Yi∈{1,2,3}Y_i \in \{1,2,3\} denote the cluster assignments. Recall that the TSS, BSS, and WSS are defined by the following series of formulae.

μˉ=∑i=1nXi/nμk=∑i: Yi=kXi/∣{i: Yi=k}∣k∈{1,2,3}WSS=∑i∥Xi−μYi∥2BSS=∑k=13∣{i: Yi=k}∣∥μk−μˉ∥2TSS=∑i∥Xi−μ∥2\begin{aligned} \bar \mu &= \sum_{i=1}^n X_i / n\\ \mu_k &= \sum_{i:\ Y_i=k} X_i / |\{i:\ Y_i=k\}| \qquad k \in \{1,2,3\} \\ \mathrm{WSS} &= \sum_i \Vert X_i - \mu_{Y_i}\Vert^2\\ \mathrm{BSS} &= \sum_{k=1}^3 |\{i:\ Y_i=k\}| \Vert \mu_k - \bar\mu\Vert^2\\ \mathrm{TSS} &= \sum_i \Vert X_i - \mu \Vert^2\\ \end{aligned}
(1)

Which of the following gives the relationship between WSS, BSS, and TSS?

  1. TSS = WSS + BSS

  2. WSS = TSS + BSS

  3. BSS = TSS + WSS

Solutions

First answer is correct.

WSS, BSS, TSS, part II

At each iteration of K-means clustering, which of the following occurs?

  1. TSS won’t increase (and might decrease)

  2. WSS won’t increase (and might decrease)

  3. BSS won’t increase (and might decrease)

Solutions

Second option. BSS won’t decrease (and might increase). TSS will stay the same (doesn’t depend on cluster labels).

What does Kmeans do?

Which is the most accurate description of what Kmeans clustering algorithm does?

  1. Kmeans attempts to find clusters so that all points in the same cluster are close to each other.

  2. Kmeans finds an optimal clustering, in the sense that it identifies a clustering so that the sum of distances between points within each cluster is as small as possible.

  3. Kmeans attempts to find clusters so that all points in the same cluster are far from each other.

  4. Kmeans finds an optimal clustering, in the sense that it identifies a clustering so that the sum of distances between points within each cluster is as large as possible.

Solutions

First option is correct. Kmeans is greedy, may not find anything optimal. Moreover, “sum of distances between points within each cluster” is a bit vague. It is true that Kmeans minimizes the WSS, and this can be related to a quantity involving the distances between all pairs of points in each cluster. Specifically,

WSS=∑i∥Xi−μYi∥2=12∑k∑i,j: Yi=k∥Xi−Xj∥2/∣{i: Yi=k}∣\mathrm{WSS} = \sum_i \Vert X_i -\mu_{Y_i}\Vert^2 = \frac{1}{2} \sum_k \sum_{i,j:\ Y_i=k} \Vert X_i -X_j \Vert^2 / |\{i:\ Y_i=k\}|
(2)

Silhouette

Consider a dataset D={X1,…Xn}\mathcal{D}=\{X_1,\ldots X_n\} that has been clustered into 3 groups. Let Yi∈{1,2,3}Y_i \in \{1,2,3\} denote the cluster assignments. Let Ck={i: Yi=k}C_k = \{i:\ Y_i=k\}. Recall that the Silhouette coefficient sis_i for each point is defined by the following series of formulae.

ai=∑j∈CYi\i∥Xi−Xj∥/∣CYi−1∣bi=min⁡y≠Yi∑j∈Cy∥Xi−Xj∥/∣Cy∣si=(bi−ai)/max⁡(ai,bi)\begin{aligned} a_i &= \sum_{j \in C_{Y_i} \backslash i} \Vert X_i - X_j \Vert / |C_{Y_i}-1| \\ b_i &= \min_{y \neq Y_i} \sum_{j \in C_{y}} \Vert X_i - X_j \Vert / |C_y| \\ s_i &= (b_i-a_i) / \max(a_i,b_i) \end{aligned}
(3)

Which of the following statements best describes ai,bi,sia_i,b_i,s_i?

a. −ai-a_i is a measure of cohesion, bib_i is a measure of separation, and large values of sis_i indicate the clustering is pretty good.

b. aia_i is a measure of separation, −bi-b_i is a measure of cohesion, and large values of sis_i indicate the clustering is pretty good.

c. −ai-a_i is a measure of cohesion, bib_i is a measure of separation, and large values of sis_i indicate the clustering is pretty bad.

d. aia_i is a measure of separation, −bi-b_i is a measure of cohesion, and large values of sis_i indicate the clustering is pretty bad.

Solutions

(a) is correct. Higher values of aia_i mean less cohesion (so higher values of −ai-a_i mean more cohesion). Higher values of bib_i mean more separation. We want lots of cohesion and lots of separation, so we want bi−aib_i-a_i to be large and positive.

Unsupervised learning
Hierarchical clustering
Unsupervised learning
Dimensionality reduction