7
$\begingroup$

I encountered the following exercise

Show that as the stiffness $\beta$ goes to $\infty$, the soft $K$-means algorithm becomes identical to the original hard $K$-means algorithm, except for the way in which means with no assigned points behave. Describe what those means do instead of sitting still.

The notation is as follows:

The point $\mathbb{x}^{(n)}$ gives a weight to the $k$-th cluster update through the responsibility $$r_k^{(n)}=\frac{\exp{(-\beta d(m^{(k)},\mathbb{x}^{(n)}))}}{\sum_i \exp{(-\beta d(m^{(i)},\mathbb{x}^{(n)}))}}$$

where $m^{(k)}$ is the $k$-th cluster point and $d(x,y) =\frac{1}{2}\sum_i (x_i-y_i)^2$. Then the update of $m^{(k)}$ is done with

$$m^{(k)}=\frac{\sum_i r_k^{(i)}\mathbb{x}^{(i)}}{\sum_i r_k^{(i)}}$$

As stiffness $\beta$ goes to $\infty$ I see how soft $K$-means becomes hard $K$-means.

The second part of the problem is asking about means which would have no assigned points in the context of hard $K$-means and thus not move. With soft $K$-means however they would move but does anyone know geometrically what they do?

$\endgroup$

2 Answers 2

2
$\begingroup$

When I look at the case where we have a single point and two clusters, it seems to me that both clusters in soft k-means will eventually be centered around the single point.

In the soft k-means, there is no such thing as an "un-assigned" cluster, so each cluster that would've been unassigned in the hard k-means will center on the nearest point.

$\endgroup$
1
$\begingroup$

Try to find a probabilistic interpretation for each $r$. Then try to express the new position as an expectation over the r's.

$\endgroup$
2
  • $\begingroup$ I am baffled at what to do. For a mean with no assigned points each $r^{(i)}$ goes to $0$ as $\beta$ goes to $\infty$. But how the new mean $m$ behaves in the limit depends on the comparative rates the $r^{(i)}$'s go to zero which depends on the other means. How to interpret all of this into some simple geometric interpretation eludes me. $\endgroup$
    – user782220
    Commented Jun 25, 2013 at 1:16
  • $\begingroup$ Write down the formula of the empirical mean. Then write down the formula from above. In what case are they equivalent? $\endgroup$
    – bayerj
    Commented Jun 25, 2013 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.