Fowlkes–Mallows index

(Redirected from Fowlkes–Mallows Index)

The Fowlkes–Mallows index is an external evaluation method that is used to determine the similarity between two clusterings (clusters obtained after a clustering algorithm), and also a metric to measure confusion matrices. This measure of similarity could be either between two hierarchical clusterings or a clustering and a benchmark classification. A higher value for the Fowlkes–Mallows index indicates a greater similarity between the clusters and the benchmark classifications. It was invented by Bell Labs statisticians Edward Fowlkes and Collin Mallows in 1983.[1]

Preliminaries

edit

The Fowlkes–Mallows index, when results of two clustering algorithms are used to evaluate the results, is defined as[2]

 

where   is the number of true positives,   is the number of false positives, and   is the number of false negatives.   is the true positive rate, also called sensitivity or recall, and   is the positive predictive rate, also known as precision.

The minimum possible value of the Fowlkes–Mallows index is 0, which corresponds to the worst binary classification possible, where all the elements have been misclassified. And the maximum possible value of the Fowlkes–Mallows index is 1, which corresponds to the best binary classification possible, where all the elements have been perfectly classified.

Definition

edit

Consider two hierarchical clusterings of   objects labeled   and  . The trees   and   can be cut to produce   clusters for each tree (by either selecting clusters at a particular height of the tree or setting different strength of the hierarchical clustering). For each value of  , the following table can then be created

 

where   is of objects common between the  th cluster of   and  th cluster of  . The Fowlkes–Mallows index for the specific value of   is then defined as

 

where

 
 
 

  can then be calculated for every value of   and the similarity between the two clusterings can be shown by plotting   versus  . For each   we have  .

Fowlkes–Mallows index can also be defined based on the number of points that are common or uncommon in the two hierarchical clusterings. If we define

  as the number of pairs of points that are present in the same cluster in both   and  .
  as the number of pairs of points that are present in the same cluster in   but not in  .
  as the number of pairs of points that are present in the same cluster in   but not in  .
  as the number of pairs of points that are in different clusters in both   and  .

It can be shown that the four counts have the following property

 

and that the Fowlkes–Mallows index for two clusterings can be defined as[3]

 
where   is the number of true positives,   is the number of false positives, and   is the number of false negatives.
  is the true positive rate, also called sensitivity or recall, and   is the positive predictive rate, also known as precision.
The Fowlkes–Mallows index is the geometric mean of precision and recall.[4]

Discussion

edit

Since the index is directly proportional to the number of true positives, a higher index means greater similarity between the two clusterings used to determine the index. One basic way to test the validity of this index is to compare two clusterings that are unrelated to each other. Fowlkes and Mallows showed that on using two unrelated clusterings, the value of this index approaches zero as the number of total data points chosen for clustering increase; whereas the value for the Rand index for the same data quickly approaches  [1] making Fowlkes–Mallows index a much more accurate representation for unrelated data. This index also performs well if noise is added to an existing dataset and their similarity compared. Fowlkes and Mallows showed that the value of the index decreases as the component of the noise increases. The index also showed similarity even when the noisy dataset had a different number of clusters than the clusters of the original dataset. Thus making it a reliable tool for measuring similarity between two clusters.

Further reading

edit
  • Chicco, Davide; Jurman, Giuseppe (2023). "A statistical comparison between Matthews correlation coefficient (MCC), prevalence threshold, and Fowlkes–Mallows index". Journal of Biomedical Informatics. 144 (104426): 1–7. doi:10.1016/j.jbi.2023.104426. hdl:10281/430040. PMID 37352899. S2CID 259240662.

See also

edit

References

edit
  1. ^ a b Fowlkes, E. B.; Mallows, C. L. (1 September 1983). "A Method for Comparing Two Hierarchical Clusterings". Journal of the American Statistical Association. 78 (383): 553. doi:10.2307/2288117.
  2. ^ Halkidi, Maria; Batistakis, Yannis; Vazirgiannis, Michalis (1 January 2001). "On Clustering Validation Techniques". Journal of Intelligent Information Systems. 17 (2/3): 107–145. doi:10.1023/A:1012801612483.
  3. ^ MEILA, M (1 May 2007). "Comparing clusterings—an information based distance". Journal of Multivariate Analysis. 98 (5): 873–895. doi:10.1016/j.jmva.2006.11.013.
  4. ^ Tharwat A (August 2018). "Classification assessment methods". Applied Computing and Informatics. doi:10.1016/j.aci.2018.08.003.
edit