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

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

${\displaystyle FM={\sqrt {PPV\cdot TPR}}={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}}$

where ${\displaystyle TP}$ is the number of true positives, ${\displaystyle FP}$ is the number of false positives, and ${\displaystyle FN}$ is the number of false negatives. ${\displaystyle TPR}$ is the true positive rate, also called sensitivity or recall, and ${\displaystyle PPV}$ 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 ${\displaystyle n}$ objects labeled ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$. The trees ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$ can be cut to produce ${\displaystyle k=2,\ldots ,n-1}$ 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 ${\displaystyle k}$, the following table can then be created

${\displaystyle M=\qquad (i=1,\ldots ,k{\text{ and }}j=1,\ldots ,k)}$

where ${\displaystyle m_{i,j}}$ is of objects common between the ${\displaystyle i}$th cluster of ${\displaystyle A_{1}}$ and ${\displaystyle j}$th cluster of ${\displaystyle A_{2}}$. The Fowlkes–Mallows index for the specific value of ${\displaystyle k}$ is then defined as

${\displaystyle B_{k}={\frac {T_{k}}{\sqrt {P_{k}Q_{k}}}}}$

where

${\displaystyle T_{k}=\sum _{i=1}^{k}\sum _{j=1}^{k}m_{i,j}^{2}-n}$

${\displaystyle P_{k}=\sum _{i=1}^{k}(\sum _{j=1}^{k}m_{i,j})^{2}-n}$

${\displaystyle Q_{k}=\sum _{j=1}^{k}(\sum _{i=1}^{k}m_{i,j})^{2}-n}$

${\displaystyle B_{k}}$ can then be calculated for every value of ${\displaystyle k}$ and the similarity between the two clusterings can be shown by plotting ${\displaystyle B_{k}}$ versus ${\displaystyle k}$. For each ${\displaystyle k}$ we have ${\displaystyle 0\leq B_{k}\leq 1}$.

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

${\displaystyle TP}$ as the number of pairs of points that are present in the same cluster in both ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$.

${\displaystyle FP}$ as the number of pairs of points that are present in the same cluster in ${\displaystyle A_{1}}$ but not in ${\displaystyle A_{2}}$.

${\displaystyle FN}$ as the number of pairs of points that are present in the same cluster in ${\displaystyle A_{2}}$ but not in ${\displaystyle A_{1}}$.

${\displaystyle TN}$ as the number of pairs of points that are in different clusters in both ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$.

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

${\displaystyle TP+FP+FN+TN=n(n-<!--\; -\; -->1)/2}$Zdroj:https://en.wikipedia.org?pojem=Fowlkes–Mallows_index
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---