4
$\begingroup$

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

enter image description here

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)?

$\endgroup$
7
  • $\begingroup$ I'm a bit confused. You need MI on what ? Is it MI(A, B) ? Wouldn't you get 0 if the two algorithms are independent (I assume so) or I missed something ? $\endgroup$
    – wij
    Jan 13, 2015 at 10:04
  • $\begingroup$ @WittawatJ. Yes, MI(A, B). Essentially, the goal is to test how good A is assuming B is the ground truth, or the other way round. $\endgroup$ Jan 14, 2015 at 2:57
  • $\begingroup$ I understand what you want to do. I just have a fundamental question. $I(A,B)=0$ if and only if $A$ and $B$ are independent. I assume the two algorithms are independent. So $I(A,B)=0$. Also, you give a marginal distributions $p_A$ and $p_B$ of cluster assignments of each algorithm. This should not be enough to construct the joint $p_{AB}$. If you say $p_{AB} = p_A p_B$, then $I(A,B)=0$. $\endgroup$
    – wij
    Jan 14, 2015 at 9:06
  • $\begingroup$ @WIJ So do you mean it is impossible to work out the MI between A and B? $\endgroup$ Jan 14, 2015 at 15:55
  • 1
    $\begingroup$ @WIJ how can you expect the algorithms to be independent? Say we have two algorithms to solve a linear system of equations - you can't expect their results to be indpendent in any reassonable way. $\endgroup$
    – Yair Daon
    Jan 15, 2015 at 14:48

3 Answers 3

2
+50
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.