Mutual information for two soft clustering results?

Question

I understand that mutual information (MI) of two distributions $X$ and $Y$ is defined as

In the case of clustering analysis, say we are looking for two clusters out of 3 data points. We have two soft clustering algorithms and correspondingly, two cluster allocations $A$ and $B$. Let's say $$A=\{(0.1, 0.9), (0.45, 0.55),(0.8, 0.2)\};\\B=\{(0.4, 0.6), (0.35, 0.65),(0.8, 0.2)\},$$ where $A_1=(0.1, 0.9)$ simply means that the 1st data point has a probability of 0.1 to be in cluster 1 and 0.9 in cluster 2.

In this case, how may I compute MI? In particular, how do I find the distributions (2 distributions and 1 joint distribution)?

Answer 1

In my opinion, you want to use some distance or divergence measure instead of MI which is a dependence measure. Presumably, your two algorithms $A$ and $B$ are independent. By this, I mean, given the clustering problem, each algorithm does not affect the other algorithm's results in any way. Hence, $p_{AB} = p_A p_B$ implying $I(A, B) = 0$.

What you want to do is to use some measure which gives you how far the result of $A$ from $B$ and vice versa. There are many measures for that. Examples include $KL(A\|B)$, Hellinger distance, or even simply rounding the probabilities to 0 or 1 and using 0-1 loss. I am sure there are some standard distances in clustering literature which I am not so familiar with.

Perhaps have a look on this Wikipedia page in section "external evaluation". Also, check out adjusted mutual information and rand index. These two seem to be what people use to evaluate clustering results.

Answer 2

Since I don't understand what you need exactly with mutual information, let me suggest a different approach.

It seems to me that you are trying to compare the performance of two algorithms $A, B$, while you believe that $B$ is, in fact, true. It might be a good idea, then, to just use $B$ all the time. But, maybe you have some restriction that prevents you from using it (e.g. it is too computationally demanding). So you might want to consider a "cheaper" algorithm. In this case, since you are already in the realm of information theory - why not use the $KL$ divergence?

You know the distribution $p_{B}(X)$:

\begin{align} p_B(X_1 = 1) = 0.4 &\text{ , } p_B(X_1 = 0) = 0.6\\ p_B(X_2 = 1) = 0.35 &\text{ , } p_B(X_2 = 0) = 0.55\\ p_B(X_3 = 1) = 0.8 &\text{ , } p_B(X_3 = 0) = 0.2\\ \end{align}

and you also have $p_A(X)$. To compare them, you may calculate $\mathbb{KL}(p_B || p_A)$. The interpretation is that this is the information lost when approximating $p_B$ (which is the truth!!) using $p_A$ (which might be easier to calculate).

Answer 3

It is not straightforward to define the distribution of the random variable defined by a soft clustering.

Nonetheless, it is possible to compute the mutual information between two clusterings using a trick. Let $U$ be the $r \times n$ membership matrix for the soft clustering $U$, and let $V$ be the $c \times n$ membership matrix for the soft clustering $V$: $$ N = UV^T $$ defines a contingency table. The mutual information can be easily computed on a contingency table.

Generalized Information Theoretic Cluster Validity Indices for Soft Clusterings