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:
“Of course I lie to people. But I lie altruistically—for our mutual good. The lie is the basic building block of good manners. That may seem mildly shocking to a moralist—but then what isn’t?”
—Quentin Crisp (b. 1908)
“In the information age, you don’t teach philosophy as they did after feudalism. You perform it. If Aristotle were alive today he’d have a talk show.”
—Timothy Leary (b. 1920)
“Walls have cracks and partitions ears.”
—Chinese proverb.