# Clustering given pairwise probabilities that two items are in the same cluster

My problem is relatively simple to describe. I have a collection $$C$$ of $$n$$ items and an $$n\times n$$ matrix $$P$$ such that $$P_{ij}$$ is the probability that items $$c_i$$ and $$c_j$$ belong to the same cluster.

We want to find the highest-probability assignment $$\mathbf{a}$$ of items to clusters. Any number of clusters may be used. In other words, we want to maximize the function:

$$L(\mathbf{a})=\prod_{i\neq j}P_{ij}\mathbb{1}(a_i, a_j)+(1-P_{ij})(1-\mathbb{1}(a_i, a_j))$$

where $$\mathbb{1}(a_i, a_j)$$ is $$1$$ if $$a_i = a_j$$ (i.e., $$i$$ and $$j$$ are from the same cluster) and $$0$$ otherwise.

I recognize that this may be a very hard problem to solve optimally. Convex relaxations and the like are fine, too.

• I doubt that this can be solved optimally by some iterative algorithm for any large matrix, and the number of clusters or the size of clusters being not preset, too. Too many assignment variants. On the other hand, since your matrix of probabilities is just a particular instance of a similarity matrix, you can easily use a greedy, stepwise algorithm such as hierarchical clustering. Sep 10, 2020 at 3:17
• (cont.) You can choose among linkage methods. Average linkage, for example, will try to maximize the average of your similarities with a cluster being combined. But if you insist that product (geometric mean) must be maximized, you perhaps may apply that clustering on the logarithms of your probabilities. Sep 10, 2020 at 3:21