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 clustering
In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into tw ...
s 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
Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984),
then AT&T Bell Laboratories (1984–1996)
and Bell Labs Innovations (1996–2007),
is an American industrial research and scientific development company owned by mult ...
statisticians Edward Fowlkes and
Collin Mallows
Collin may refer to:
People Surname
* Collin (surname)
* Jacques Collin de Plancy (1793–1881), French occultist, demonologist and writer
* Victor Collin de Plancy (1853–1924), French diplomat, bibliophile and art collector
* Jean-Baptiste ...
in 1983.
Preliminaries
The Fowlkes–Mallows index, when results of two clustering algorithms are used to evaluate the results, is defined as
:
where
is the number of
true positives,
is the number of
false positives
A false positive is an error in binary classification in which a test result incorrectly indicates the presence of a condition (such as a disease when the disease is not present), while a false negative is the opposite error, where the test result ...
, and
is the number of
false negatives.
is the ''true positive rate'', also called ''
sensitivity
Sensitivity may refer to:
Science and technology Natural sciences
* Sensitivity (physiology), the ability of an organism or organ to respond to external stimuli
** Sensory processing sensitivity in humans
* Sensitivity and specificity, statisti ...
'' 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
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
:
:where
is the number of
true positives,
is the number of
false positives
A false positive is an error in binary classification in which a test result incorrectly indicates the presence of a condition (such as a disease when the disease is not present), while a false negative is the opposite error, where the test result ...
, and
is the number of
false negatives.
:
is the ''true positive rate'', also called ''
sensitivity
Sensitivity may refer to:
Science and technology Natural sciences
* Sensitivity (physiology), the ability of an organism or organ to respond to external stimuli
** Sensory processing sensitivity in humans
* Sensitivity and specificity, statisti ...
'' or ''
recall'', and
is the ''positive predictive rate'', also known as ''
precision''.
:The Fowlkes–Mallows index is the
geometric mean
In mathematics, the geometric mean is a mean or average which indicates a central tendency of a set of numbers by using the product of their values (as opposed to the arithmetic mean which uses their sum). The geometric mean is defined as the ...
of
precision and recall
In pattern recognition, information retrieval, object detection and classification (machine learning), precision and recall are performance metrics that apply to data retrieved from a collection, corpus or sample space.
Precision (also called ...
.
[
]
Discussion
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
The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is financed ...
for the same data quickly approaches
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.
See also
*
F1 score
In statistical analysis of binary classification, the F-score or F-measure is a measure of a test's accuracy. It is calculated from the precision and recall of the test, where the precision is the number of true positive results divided by the ...
*
Matthews correlation coefficient
In statistics, the phi coefficient (or mean square contingency coefficient and denoted by φ or rφ) is a measure of association for two binary variables. In machine learning, it is known as the Matthews correlation coefficient (MCC) and used as a ...
*
Confusion matrix
In the field of machine learning and specifically the problem of statistical classification, a confusion matrix, also known as an error matrix, is a specific table layout that allows visualization of the performance of an algorithm, typically a ...
References
External links
Implementation of Fowlkes–Mallows indexin
R.
{{DEFAULTSORT:Fowlkes-Mallows index
Clustering criteria
Bell Labs