I am having a situation where my data points consist of $r$ groups, that we want to force the observations within a group to be in the same cluster, with $n_r$ observations in each group. So the idea is to force the algorithm so that the within-group observations stay in the same cluster. I have altered the EM algorithm to achieve this, but I am wondering if anybody has every encountered such a problem? I couldn't find any literature that addresses this type of clustering. I appreciate if someone can provide me with a guideline/articles about this problem.

  • $\begingroup$ The problem sounds like classification, rather than clustering. en.wikipedia.org/wiki/Statistical_classification $\endgroup$
    – user20160
    Jul 11, 2016 at 1:46
  • 1
    $\begingroup$ I believe that this sort of constraint will look quite different with different clustering algorithms. My user-developed program for hierarchical clustering for SPSS does it. On early steps, it builds the clusters forcibly so each cluster consists of the objects demanded, the groups. Then it goes on combining these groups the usual hierarchical way. $\endgroup$
    – ttnphns
    Jul 11, 2016 at 5:53
  • $\begingroup$ @ttnphns Thanks. As I mentioned, I was able to modify EM for achieving this, but I would like to do some literature review, or compare my results to others. I can't find any literature. Do you know of any? $\endgroup$
    – H_A
    Jul 11, 2016 at 15:29
  • $\begingroup$ @user20160 It is rather a clustering problem. However, instead of assigning a single observation to a cluster, a group/block of observations should be assigned to a cluster. $\endgroup$
    – H_A
    Jul 11, 2016 at 16:08
  • $\begingroup$ I retract the comment about classification (had interpreted the question to mean a one-to-one mapping between groups and clusters). Sounds instead like you may be looking for 'constrained clustering' / 'constraint-based clustering'. If you want points in the same group to always be in the same cluster (but possibly allow multiple groups to share the same cluster), this is commonly called a 'must-link constraint'. $\endgroup$
    – user20160
    Jul 11, 2016 at 18:42

2 Answers 2


As per comments, the problem is similar to constrained clustering with must-link constraints. In the constrained clustering problem, points with must-link constraints must be assigned to the same cluster.

If your component models give point estimates and you have hard assignments of points to models, then you might approach the problem similarly to k-means with must-link constraints. For example:

Wagstaff et al. (2001). Constrained K-means Clustering with Background Knowledge.

Here's a blog post describing a similar method for mixture of regression models.

If your component models give conditional probabilities and you have weighted assignments, you might approach the problem similarly to Gaussian mixture models with must-link constraints. Your modified EM algorithm sounds like the right track. A paper describing this approach:

Shental et al. (2003). Computing gaussian mixture models with EM using side-information


From a logical point of view, I'd say you want to cluster the groups, not the group members?

Doing this with k-means is peobably equivalent to clustering the group averages. With EM the situation is a bit more complicated, but roughly it should be equivalent to making each group a Gaussian, then clustering the Gaussians using EM.

I would also try hierarchical clustering. Define a similarity function of groups akin to the linkage criterions: minimum distance between group members? average?

$$d(G,H):=\frac{1}{|G||H|}\sum_{g\in G}\sum_{h\in H} d(g,h)$$

and then run AGNES on the resulting matrix.


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.