(Solved): Problem 3. K-means clustering can be viewed as an optimization problem that a ...

???????

Problem 3. K-means clustering can be viewed as an optimization problem that attempts to minimize some objective function. For the given objectives, determine the update rule for the centroid, \( c_{k} \) of the \( k \)-th cluster \( C_{k} \). In other word, find the optimal \( c_{k} \) that minimizes the objective function. The data \( x \) contains \( p \) features. (a) Show that setting the objective to the sum of the squared Euclidean distances of points from the center of their clusters, \[ \sum_{k=1}^{K} \sum_{x \in C_{k}} \sum_{i=1}^{p}\left(c_{k i}-x_{i}\right)^{2} \] results in an update rule where the optimal centroid is the mean of the points in the cluster. (b) Show that setting the objective to the sum of the Manhattan distances of points from the center of their clusters, \[ \sum_{k=1}^{K} \sum_{x \in C_{k}} \sum_{i=1}^{p}\left|c_{k i}-x_{i}\right| \] results in an update rule where the optimal centroid is the median of the points in the cluster.