Mutual Information of Two Partitions
Given a set S of N elements, consider two partitions of S, namely with R clusters, and with C clusters. It is presumed here that the partitions are so-called hard clusters, the partitions are pairwise disjoint:
for all, and complete:
The mutual information of cluster overlap between U and V can be summarized in the form of an RxC contingency table, where denotes the number of objects that are common to clusters and . That is,
Suppose an object is picked at random from S; the probability that the object falls into cluster is:
The entropy associated with the partitioning U is:
H(U) is non-negative and takes the value 0 only when there is no uncertainty determining an object's cluster membership, i.e., when there is only one cluster. Similarly, the entropy of the clustering V can be calculated as:
where . The mutual information (MI) between two partitions:
where P(i,j) denotes the probability that a point belongs to both the cluster in U and cluster in V:
MI is a non-negative quantity upper bounded by the entropies H(U) and H(V). It quantifies the information shared by the two clusterings and thus can be employed as a clustering similarity measure.
Read more about this topic: Adjusted Mutual Information
Famous quotes containing the words mutual, information and/or partitions:
“I describe family values as responsibility towards others, increase of tolerance, compromise, support, flexibility. And essentially the things I call the silent song of life—the continuous process of mutual accommodation without which life is impossible.”
—Salvador Minuchin (20th century)
“The real, then, is that which, sooner or later, information and reasoning would finally result in, and which is therefore independent of the vagaries of me and you. Thus, the very origin of the conception of reality shows that this conception essentially involves the notion of a COMMUNITY, without definite limits, and capable of a definite increase of knowledge.”
—Charles Sanders Peirce (1839–1914)
“Great wits are sure to madness near allied,
And thin partitions do their bounds divide.”
—John Dryden (1631–1700)