Unnatural clustering with known clusters shapes and optimization criteria

Question

My question is similar to this question Clustering with shape prior, but with additional information.

The second answer suggests a mixture model approach to this problem, which is something like Expectation Maximization with user-defined mixture model for clusters instead of default Gaussian.My question is that suppose we have an additional optimization criteria with respect to clustering (for e.g. the total area of the clusters should be minimum), where can this point be introduced in the approach. Is proper similarity measure the only way to ensure the desired optimization ? If yes, Which part of EM algorithm can be modified to take this into account, I mean which part in EM algorithm emulates the function of distance metric in k-means. And is there any implementation of EM that let's us specify the mixture model. Is expectation-maximization the only way to achieve this model based clustering ? Any references would be very helpful.

Answer 1

Yes, there are extensible implementations of EM, which allow you to specify the distributions to model.

Overall, I would however suggest that you study EM clustering in detail, because trying to solve it by distance won't do the trick - just like k-means doesn't reliably work with other distance functions.

What you need for EM are two steps:

• Expectation-step (E-step)
• Maximization-step (M-step)

Both need to optimize the same objective, otherwise you are busted. In k-means, the E-step is nearest-centroid assignment, and M-step is computing the mean. The mean minimizes least-squares, and using squared Euclidean distance in the E-step minimizes the same quantity, thus it must converge. It is a popular mistake to put a different distance function into k-means, without also replacing the mean function with an optimum center estimation adequate for the new distance function. This yields suboptimal results - and maybe worse, it can also lead to non-convergence.

If you want to include constraints or other side information, you should add this into both steps... so when reassigning data, assign such that it satisfies your constraints. When recomputing the cluster models, make sure the resulting models improve towards your constraints.

If you can prove that both steps improve the objective functions, then the algorithm must converge, and won't get stuck in a circular loop.