Classification of samples into two groups

Question

I'm having problems finding what is the right perspective on the following problem.

I have a set of (univariate) samples:

$$S_1 = \{X^1_1,\ldots ,X^1_{n_1}\},$$ $$S_2 = \{X^2_1,\ldots ,X^2_{n_2}\},$$ $$\vdots$$ $$S_m =\{X^m_1,\ldots ,X^m_{n_m}\} $$

The sample $S_k$ was a random sample either from the distribution $F_\alpha$ or from $F_\beta$. I know that the means of those distributions are $\alpha$ and $\beta$ and that $\alpha \neq \beta$, but I don't know the values of $\alpha$ or $\beta$.

I'm looking for a procedure that could help me decide for each $S_k$ if it came from $F_\alpha$ or $F_\beta$.

Any help is really appreciated.

Answer 1

You could approach this as a constrained clustering problem. First, toss all data points into one big set. The goal would then be to assign each data point to one of two clusters, with the constraint that all points from the same sample must be assigned to the same cluster. This type of constraint is commonly called a must-link constraint.

If you want to approach the problem probabilistically, you could cluster using a mixture model. This could be a good approach if you know the form of the distributions that generated the data. To learn the model parameters and cluster assignments, you'd use a variant of the expectation maximization algorithm, modified to handle must-link constraints. Here's a paper that describes how to do this for Gaussian mixture models:

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

An alternative would be to use a constrained version of k-means. This paper describes a version of Llyod's algorithm that has been modified to handle constraints:

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

Constrained versions of hierarchical agglomerative clustering also exist, e.g. as described here and in this paper:

Davidson and Ravi (2005). Agglomerative hierarchical clustering with constraints: Theoretical and empirical results.