# Estimating co-occurrence probabilities of pairs of sample points from different clusters

I have a problem as follows:

I have a collection of samples which I wish to cluster. The sample points are acquired in "groups/batches", and we know that samples from the same "group" cannot be clustered to the same cluster. There is also a notion that samples acquired together "occur" together. As part of a project I'm doing, I wish to exploit the co-occurence of samples from different clusters to improve the clustering.

To do that, I need to estimate the co-occurrence frequency/probability of samples from any pair of clusters. That is, if I have $k$ clusters, $c_1, c_2, \ldots, c_k$, I want to know the probability that a sample from $c_i$ will occur with sample from $c_j$. Put in another way, I want to know how likely samples from different clusters occur together.

The problem is I don't know with absolutely certainty if a sample $x$ belongs to a particular cluster, else I would already have the clustering. Hence, it is not possible to just count how many times samples from a cluster was acquired together with those from another cluster, and divide by the total number of acquisitions to produce a rough estimate.

(Note that from search I have conducted thus far this is how co-occurence of words in documents retrieval/natural language processing etc. is computed. This is, one can count how many times a pair of words, say "umbrella" and "rain", occur together i.e. in same document, in a collection of documents.)

However, suppose we have a probability for a sample belonging to each of the clusters i.e. suppose we have the distribution $P(x \text{ is from cluster } i \mid x)$, where $x$ is a sample. Is there a way to estimate the co-occurrence probabilities stated above?

I hope someone can provide me with some clues such as the terms I should search for, or the specific areas of mathematics that I should look into. Currently, I'm searching using terms along the lines of "estimating/computing co-occurrence frequency of uncertain data". I found materials relating to estimating co-occurrence matrices, in particular for natural language processing or document retrieval. However, as I have mentioned, I cannot compute a co-occurrence matrix in my case because I don't know the clusters that pairs of samples belong to.

Thanks in advance to any replies.

-