Description

1. [10 points] K-Means
(a) Mention if K-Means is a supervised or an un-supervised method.
Your answer: K-Means is un-supervised method.
(b) Assume that you are trying to cluster data points xi for i ∈ {1,2…D} into K clusters each with center µk where k ∈ {1,2,…K}. The objective function for doing this clustering involves minimizig the euclidean distance between the points and the cluster centers. It is given by

How do you ensure hard assignemnt of one data point to one and only one cluster at a given time? Note: By hard assignment we mean that your are 100 % sure that a point either belongs or not belongs to a cluster.
Your answer: rik ∈ {0,1} This will make any data point xi belong to (rik = 1) or not belong to (rik = 0) centroid µk
, if ||xi − µk||2 < ||xi − µl||2,∀l 6= k
r
, otherwise
(c) What changes must you do in your answer of part b, to make the hard assingment into a soft assignment? Note: By soft assignment we mean that your are sure that a point either belongs or not belongs to a cluster with some probability.
Your answer: rik ∈ [0,1] This will make ith line of matrix R the probability vector of data point xi considering a Softmax Function.

where the parameter β > 0 is called stiffness parameter.
(d) Looking at the following plot, what is the best choice for number of clusters?

Your answer: The number of clusters should be 5 because it is the elbow of the plot.
(e) Would K-Means be an effecient algorithm to cluster the following data? Explain your answer in a couple of lines.

Your answer: No. Assume the first two initial centers we initialize both on the outer circle but one is on the right, the other is on the left. After running K-Means algorithm, we will get two cluster which contains both inner and outer semi-circle respectively. It is not what we expected.
2