1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – ttnphns
    Sep 10, 2020 at 3:17
  • $\begingroup$ (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. $\endgroup$
    – ttnphns
    Sep 10, 2020 at 3:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.