Fowlkes–Mallows index

Fowlkes –Mallows-indexet är en extern utvärderingsmetod som används för att bestämma likheten mellan två klustringar (kluster erhållna efter en klustringsalgoritm ), och även ett mått för att mäta förvirringsmatriser . Detta mått på likhet kan vara antingen mellan två hierarkiska klustringar eller en klustring och en benchmark-klassificering. Ett högre värde för Fowlkes–Mallows-indexet indikerar en större likhet mellan klustren och benchmark-klassificeringarna. Det uppfanns av Bell Labs statistiker Edward Fowlkes och Collin Mallows 1983.

Förberedelser

Fowlkes –Mallows-indexet , när resultat av två klustringsalgoritmer används för att utvärdera resultaten, definieras som

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

där $TP$ är antalet sanna positiva , $FP$ är antalet falska positiva , och $FN$ antalet falskt negativa . $TPR$ är den sanna positiva frekvensen , även kallad sensitivitet eller återkallelse , och $PPV$ är den positiva prediktiva frekvensen , även känd som precision .

Minsta möjliga värde för Fowlkes–Mallows-indexet är 0, vilket motsvarar den sämsta möjliga binära klassificeringen, där alla element har blivit felklassificerade. Och det högsta möjliga värdet på Fowlkes–Mallows-indexet är 1, vilket motsvarar den bästa möjliga binära klassificeringen, där alla element har klassificerats perfekt.

Definition

Betrakta två hierarkiska klustringar av $n$ objekt märkta $A_{1}$ och $A_{2}$ . Träden $A_{1}$ och $A_{2}$ kan kapas till $k=2,\ldots ,n-1$ kluster för varje träd (genom att antingen välja kluster på en viss höjd av trädet eller ställa in olika styrka på den hierarkiska klustringen). För varje värde på $k$ kan följande tabell skapas

M=[m_{i,j}]\qquad (i=1,\ldots ,k{ \text{ och }}j=1,\ldots ,k)

där $m_{i,j}$ är av objekt som är gemensamma mellan ${\displaystyle i}:$ e klustret av $A_{1}$ och $j$ :e klustret av $A_{2}$ . Fowlkes –Mallows-indexet för det specifika värdet av $k$ definieras sedan som

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

var

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

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

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

$B_{k}$ kan sedan beräknas för varje värde av $k$ och likheten mellan de två klustringarna kan visas genom att plotta $B_{k}$ mot ${\ displaystil k}$ . För varje $k$ har vi $0\leq B_{k}\leq 1$ .

Fowlkes–Mallows index kan också definieras baserat på antalet punkter som är vanliga eller ovanliga i de två hierarkiska klustringarna. Om vi definierar

TP

som antalet par av punkter som finns i samma kluster i både

A_{1}

och

A_{2}

.

FP

som antalet par av punkter som finns i samma kluster i

A_{1}

men inte i

A_{2}

.

FN

som antalet par av punkter som finns i samma kluster i

A_{2}

men inte i

A_{1}

.

TN

som antalet par av punkter som finns i olika kluster i både

A_{1}

och

A_{2}

.

Det kan visas att de fyra räkningarna har följande egenskap

\displaystyle TP+FP+FN+TN=n(n-1)/2}

och att Fowlkes–Mallows-indexet för två klustringar kan definieras som

cdot {\frac {TP}{TP+FN}}}}}

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

där

TP

är antalet sanna positiva ,

FP

är talet av falska positiva , och

FN

är antalet falska negativa .

TPR

är den sanna positiva frekvensen , även kallad sensitivitet eller återkallelse , och

PPV

är den positiva prediktiva frekvensen , även känd som precision .

Fowlkes–Mallows-indexet är det geometriska medelvärdet av precision och återkallelse .

Diskussion

Eftersom indexet är direkt proportionellt mot antalet sanna positiva, betyder ett högre index större likhet mellan de två klustringarna som används för att bestämma indexet. Ett grundläggande sätt att testa giltigheten av detta index är att jämföra två klustringar som inte är relaterade till varandra. Fowlkes och Mallows visade att vid användning av två icke-relaterade klustringar, närmar sig värdet av detta index noll när antalet totala datapunkter som valts för klustring ökar; medan värdet för Randindex för samma data snabbt närmar sig $1$ vilket gör Fowlkes–Mallows index till en mycket mer exakt representation för orelaterade data. Detta index fungerar också bra om brus läggs till en befintlig datauppsättning och deras likhet jämförs. Fowlkes och Mallows visade att indexvärdet minskar när komponenten av bruset ökar. Indexet visade också likhet även när den bullriga datamängden hade ett annat antal kluster än klustren i den ursprungliga datamängden. Detta gör det till ett pålitligt verktyg för att mäta likhet mellan två kluster.

Se även

externa länkar

Implementering av Fowlkes–Mallows index i R .