2. (k-means clustering [6pt]) This exercise is related to Problem 2 of Homework 1: durint lectures, we have considered the clustering problem with equal weights for each sample. In this problem, we will re-weigh each sample 2, with a weight w, 20 to represent the importance (significance) of each sample. (a) [2pt] Write down the weighted k-means clustering problem. There are two variables: the centers c,, Vj = 1,...,k and the partition S,. The objective function is the sum of the weighted squared Euclidean distance from each sample to its corresponding cluster center. Answer: 2 (b) [2pt] Consider the first step of the k-means heuristics algorithm. In this step, we consider c as fixed, and we optimize over the partition variables. What is the optimal partition? Answer: S = (c) [2pt] Consider the second step of the k-means heuristics algorithm. In this step, we consider S as fixed, and we optimize over the locations of the centers c,. What are the optimal centers? Answer: cj=