Question 1

For the Lloyd's algorithm, what would be the correct relationship among the following three quantities? (1) $\sum_{i=1}^{n} ||x_i - \mu^t_{z_i^{t+1}}||^2$,\ (2) $\sum_{i=1}^{n} ||x_i - \mu^t_{z_i^t}||^2$,\ (3) $\sum_{i=1}^{n} ||x_i - \mu^{t+1}_{z_i^{t+1}}||^2$ where $\mu^t_{z_i^t}$ and $\mu^{t+1}_{z_i^{t+1}}$ refer to means of cluster $z_i$ in iterations, $t$ and $t+1$ respectively, and $\mu^t_{z_i^{t+1}}$ refer to the mean of the cluster $z_i$ where $x_i$ is going to move in the next iteration, i.e., $(t+1)$-th iteration. Figure from the original question paper Figure from the original question paper