How can I cluster data drawn from distributions with known symmetries? Consider a set of data which is a mixture of samples drawn from different distributions. It is known from the underlying phenomena generating the mixture that for every distribution in the mixture there will also be the reflection of that distribution in one axis.
For example, here is some data randomly sampled from the following probability density functions:
$f(x,y) = \varphi(x-5)\varphi(y)$
$g(x,y) = \varphi(x-10)\varphi(y-5)$
$g^*(x,y) = \varphi(x-10)\varphi(y+5)$

Clustering the data straightforwardly, as sampled, results in completely independent treatment of the two clusters coming from symmetrically opposite distributions. Neither benefits from knowledge about samples in the opposite cluster, and so the clusters' centroids are not symmetric, as shown by comparing the centroid locations with their reflections:

I can force symmetrically opposite samples to be treated spatially close to each other by clustering the values found at $(x,|y|)$. This successfully combines data for the two symmetrically opposite clusters in the original data but skews the centroid of the cluster that was originally centred on the x-axis:

Alternatively I could double up the entire data set with reflected duplicates of each sample. Here, this results in symmetrical clusters which account for all relevant data points:

However this seems problematic:


*

*It has to locate every off-axis cluster twice with identical but mirrored data, which doesn't seem efficient.

*With less well-segregated data, the symmetry in the input data will not guarantee all clustering algorithms to converge on a symmetric result.


Is there a suitable way to approach data like this so the symmetry is correctly modelled?
 A: You could attack this problem using a mixture model whose components have tied/shared parameters. First, declare the number of 'underlying' components $k$. The number of actual components/clusters will then be $2k$ because each underlying component is reflected once.
If using a Gaussian mixture model (for example), the underlying/shared parameters would consist of mean vectors $\{ \mu_1, \dots, \mu_k \}$ and covariance matrices $\{ C_1, \dots, C_k \}$. Actual mixture components occur in pairs: $i$ and $i^*$ (where $i^*$ is the reflected version). Component $i$ has mean $\mu_i$, covariance matrix $C_i$, and mixture weight $w_i$. Component $i^*$ has mean $\mu_i^*$ (which is a reflected version of $\mu_i$, i.e. a particular coordinate is multiplied by $-1$), covariance matrix $C_i^*$ (which is a flipped version of $C_i$; not necessary if covariance matrices are constrained to be spherical), and mixture weight $w_i^*$. Note that the underlying means and covariance matrices are shared for each pair of components, but each component has its own weight (you could make the weights shared too, if you wanted to constrain them to be equal).
The parameters $\{ \mu_1, \dots, \mu_k \}$, $\{ C_1, \dots, C_k \}$, $\{ w_1, w_1^*, \dots, w_k, w_k^* \}$ can then be learned using your favored method (e.g. the expectation maximization algorithm). The only difference between this approach and learning a standard mixture model is that the means and covariance matrices are shared between reflected pairs.
A couple things to point out: In your example, this approach would create two clusters for the group of points lying directly on the x axis. You could either detect this after the fact, or add some kind of machinery to model these cases as part of the clustering procedure itself (more complicated). The above procedure also assumes that each pair is reflected about a known axis (giving a fixed relationship between $\mu_i$ and $\mu_i^*$, and $C_i$ and $C_i^*$). If this isn't the case, you'd have to add some machinery to infer the proper axis (e.g. treat the axis as a latent variable).
