Calcul de l'indice Rand

J'essaie de comprendre comment calculer l'indice Rand d'un algorithme de cluster, mais je suis coincé au point de savoir comment calculer les vrais et les faux négatifs.

Pour le moment, j'utilise l'exemple du livre An Introduction into Information Retrieval (Manning, Raghavan & Schütze, 2009). À la page 359, ils expliquent comment calculer l'indice Rand. Pour cet exemple, ils utilisent trois clusters et les clusters contiennent les objets suivants.

1. aaaaab
2. abbbbc
3. aaccc

Je remplace l'objet (signes originaux en lettres, mais l'idée et le décompte restent les mêmes). Je vais donner les mots exacts du livre afin de voir de quoi ils parlent:

Nous calculons d'abord TP + FP. Les trois groupes contiennent respectivement 6, 6 et 5 points, de sorte que le nombre total de «positifs» ou de paires de documents qui se trouvent dans le même groupe est:

TP + FP = ${6 \choose 2}$ + ${6 \choose 2}$ + ${5 \choose 2}$ = 15 + 15+ 10 = 40

Parmi ceux-ci, les paires a du cluster 1, les paires b du cluster 2, les paires c du cluster 3 et la paire a du cluster 3 sont de vrais positifs:

TP = ${5 \choose 2}$ + ${4 \choose 2}$ + ${3 \choose 2}$ + ${2 \choose 2}$ = 10 + 6 + 3 + 1 = 20

Ainsi, FP = 40-20 = 20.

Jusqu'ici, les calculs sont clairs, et si je prends d'autres exemples, j'obtiens les mêmes résultats, mais quand je veux calculer le faux négatif et le vrai négatif Manning et al. énoncer ce qui suit:

FN et TN sont calculés de manière similaire, ce qui donne le tableau de contingence suivant:

Le tableau de contingence se présente comme suit:

+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+

La phrase: "FN et TN sont calculés de la même manière" n'est pas claire pour moi et je ne comprends pas de quels nombres j'ai besoin pour calculer le TN et le FN. Je peux calculer le côté droit du tableau en procédant comme suit:

TP + FP + FN + TN = = = 136${n \choose 2}$${17 \choose 2}$

Source: http://en.wikipedia.org/wiki/Rand_index

Ainsi, FN + TN = 136 - TP + FP = 136 - 40 = 96, mais cela ne m'aide pas vraiment à comprendre comment calculer les variables séparément. Surtout quand les auteurs disent: "FN et TN sont calculés de manière similaire". Je ne vois pas comment. Aussi quand je regarde d'autres exemples, ils calculent chaque cellule du tableau de contingence en regardant chaque paire.

Par exemple: http://www.otlet-institute.org/wikics/Clustering_Problems.html#toc-Subsection-4.1

Ma première question, basée sur l'exemple de Manning et al (2009), est-il possible de calculer le TN et le FN si vous ne connaissez que le TP & NP? Et si oui, à quoi ressemble un calcul similaire basé sur l'exemple donné?

Je réfléchissais à la même chose, et je l'ai résolu comme ça. Supposons que vous ayez une matrice de cooccurrence / table de contingence où les lignes sont les clusters de vérité au sol et les colonnes sont les clusters trouvés par l'algorithme de clustering.

Ainsi, pour l'exemple dans le livre, cela ressemblerait à:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Maintenant, vous pouvez très facilement calculer le TP + FP en prenant la somme par colonne et en «choisissant 2» parmi toutes ces valeurs. Donc les sommes sont [6, 6, 5] et vous faites '6 choisissez 2' + '6 choisissez 2' + '5 choisissez 2'.

Maintenant, en effet, de la même manière, vous pouvez obtenir TP + FN en prenant la somme sur les lignes (c'est-à-dire [8, 5, 4] dans l'exemple ci-dessus), appliquez 'choisissez 2' sur toutes ces valeurs, et prenez la somme de cela.

Les TP eux-mêmes peuvent être calculés en appliquant «choisir 2» à chaque cellule de la matrice et en prenant la somme de tout (en supposant que «1 choisir 2» est égal à 0).

En fait, voici du code Python qui fait exactement cela:

import numpy as np
from scipy.misc import comb

# There is a comb function for Python which does 'n choose k'                                                                                            
# only you can't apply it to an array right away                                                                                                         
# So here we vectorize it...                                                                                                                             
def myComb(a,b):
  return comb(a,b,exact=True)

vComb = np.vectorize(myComb)

def get_tp_fp_tn_fn(cooccurrence_matrix):
  tp_plus_fp = vComb(cooccurrence_matrix.sum(0, dtype=int),2).sum()
  tp_plus_fn = vComb(cooccurrence_matrix.sum(1, dtype=int),2).sum()
  tp = vComb(cooccurrence_matrix.astype(int), 2).sum()
  fp = tp_plus_fp - tp
  fn = tp_plus_fn - tp
  tn = comb(cooccurrence_matrix.sum(), 2) - tp - fp - fn

  return [tp, fp, tn, fn]

if __name__ == "__main__":
  # The co-occurrence matrix from example from                                                                                                           
  # An Introduction into Information Retrieval (Manning, Raghavan & Schutze, 2009)                                                                       
  # also available on:                                                                                                                                   
  # http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html                                                                     
  #                                                                                                                                                      
  cooccurrence_matrix = np.array([[ 5,  1,  2], [ 1,  4,  0], [ 0,  1,  3]])

  # Get the stats                                                                                                                                        
  tp, fp, tn, fn = get_tp_fp_tn_fn(cooccurrence_matrix)

  print "TP: %d, FP: %d, TN: %d, FN: %d" % (tp, fp, tn, fn)

  # Print the measures:                                                                                                                                  
  print "Rand index: %f" % (float(tp + tn) / (tp + fp + fn + tn))

  precision = float(tp) / (tp + fp)
  recall = float(tp) / (tp + fn)

  print "Precision : %f" % precision
  print "Recall    : %f" % recall
  print "F1        : %f" % ((2.0 * precision * recall) / (precision + recall))

Si je l'exécute, j'obtiens:

$ python testCode.py
TP: 20, FP: 20, TN: 72, FN: 24
Rand index: 0.676471
Precision : 0.500000
Recall    : 0.454545
F1        : 0.476190

En fait, je n'ai pas vérifié d'autres exemples que celui-ci, alors j'espère que je l'ai bien fait .... ;-)

Après avoir étudié les autres réponses de ce fil, voici mon implémentation Python, qui prend les tableaux en entrée, sklearn-style:

import numpy as np
from scipy.misc import comb

def rand_index_score(clusters, classes):

    tp_plus_fp = comb(np.bincount(clusters), 2).sum()
    tp_plus_fn = comb(np.bincount(classes), 2).sum()
    A = np.c_[(clusters, classes)]
    tp = sum(comb(np.bincount(A[A[:, 0] == i, 1]), 2).sum()
             for i in set(clusters))
    fp = tp_plus_fp - tp
    fn = tp_plus_fn - tp
    tn = comb(len(A), 2) - tp - fp - fn
    return (tp + tn) / (tp + fp + fn + tn)

In [319]: clusters
Out[319]: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

In [320]: classes
Out[320]: [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 0, 2, 2, 2, 0]

In [321]: rand_index_score(clusters, classes)
Out[321]: 0.67647058823529416

Je ne suis pas tout à fait sûr moi-même, mais voici comment j'ai fait la valeur
TN : TN = (7 2) (10 2) (4 2)

(7 2) - Cluster 1 - le test dit 'x', donc comptez ceux qui ne sont PAS x (et sont correctement clusterisés dans les clusters 2 & 3)

soit 4 'o + 3' d'(diamants) = (7 2)

(10 2) - Cluster 2, comptez ceux qui ne sont PAS des 'o' et correctement groupés dans les clusters 1 et 3,

soit 5 'x' + (2'x '+ 3'd') = (10 2)

(4 2) - Cluster 3, comptez ceux qui ne sont PAS 'x' et PAS 'd' (élément en forme de losange) qui sont correctement groupés dans les clusters 1 & 2.

soit 4 'o dans le cluster 2. = (4 2)

TN = (7 2) + (10 2) + (4 2) = 72.

Alors FN c'est:

FN = (17 2) - (TP + FP) - TN = 136 - 40 -72 = 24. ---> (17 = nombre total de documents)

Prenons l'exemple d'une autre question:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

La réponse raisonnable pour FN:

FN = (c(8,2)-c(5,2)-c(2,2))+(c(5,2)-c(4,2))+(c(4,2)-c(3,2))=24  

Explication:

• (c (8,2) -c (5,2) -c (2,2))

  choisir 2 parmi 8 pour 'x' (a) la combinaison de la même classe dans les mêmes grappes (c (5,2) pour la grappe 1 et c (2,2) pour la grappe 3),

• (c (5,2) -c (4,2))

  choisir 2 parmi 5 'o' (b) moins la combinaison de la même classe dans les mêmes grappes (c (4,2) pour la grappe 2)

• (c (4,2) -c (3,2)

  choisissez 2 parmi 4 pour '◇' (c) moins la combinaison de la même classe dans les mêmes grappes (c (3,2) pour la grappe 3)

Je l'ai dérivé comme ça.

J'ai une implémentation de ceci dans R que je vais expliquer:

TP (a dans le code) est la somme de chaque cellule, choisissez 2. Selon la question d'origine (0 ou 1, choisissez 2 équivalant à 0)

FN (b) est la somme de chaque ligne, choisissez 2, toutes additionnées, moins TP. Où chaque somme de ligne représente le nombre de documents dans chaque classe True.

La somme de ceci est tous les documents qui sont similaires et dans le même cluster (TP) plus tous les documents qui sont similaires et ne sont pas dans le même cluster (FN).

C'est donc (TP + FN) - TP = FN

FP (c) est calculé de manière similaire. La somme de chaque colonne en choisit 2, toutes additionnées, moins TP. Dans ce cas, chaque somme de colonne représente le nombre de documents dans chaque cluster.

Ainsi, la somme de tous les documents qui sont similaires et dans le même cluster (TP) ainsi que tous les documents qui ne sont pas similaires et sont dans le même cluster (FP).

C'est donc (TP + FP) - TP = FP

Avec ces 3 calculés, le calcul restant de TN est simple. La somme du tableau choisit 2, moins TP, FP & FN = TN (d)

La seule requête que j'ai avec cette méthode est sa définition de TP. En utilisant la terminologie de cette question, je ne comprends pas pourquoi les 2 a du cluster 3 sont considérés comme TP. Je l'ai trouvé ici et dans le manuel correspondant. Cependant, je comprends leur calcul en supposant que leur calcul TP est correct.

J'espère que cela t'aides

FMeasure = function (x, y, beta) 
{
  x <- as.vector(x)
  y <- as.vector(y)
  if (length(x) != length(y)) 
    stop("arguments must be vectors of the same length")
  tab <- table(x, y)
  if (all(dim(tab) == c(1, 1))) 
    return(1)
  a <- sum(choose(tab, 2))
  b <- sum(choose(rowSums(tab), 2)) - a
  c <- sum(choose(colSums(tab), 2)) - a
  d <- choose(sum(tab), 2) - a - b - c
  ## Precision
  P = a / (a + c)
  ## Recall
  R = a / (a + b)
  ##F-Measure
  Fm <- (beta^2 + 1) * P * R / (beta^2*P + R)
  return(Fm)
}

Vous pouvez calculer TN et FN de la même manière.

Changez simplement les rôles des étiquettes et des clusters .

a) 1 1 1 1 1 2 3 3
b) 1 2 2 2 2
c) 2 3 3 3 3

... puis effectuez les mêmes calculs.

Je pense que j'ai inversé l'ingénierie du faux négatif (FN). Pour les vrais positifs, vous avez fait 4 groupes qui étaient positifs. Dans le cluster 1, vous aviez les cinq a; dans le cluster 2, vous aviez les 4 b; dans le groupe 3, vous aviez les 3 c ET les 2 a.

Donc pour le faux négatif.

1. Commencez par les a du cluster 1; il y a 5 a correctement placés dans le cluster 1. Vous avez 1 faux a dans le cluster 2, et deux faux a dans le cluster 3. Cela donne (5 1) et (5 2).
2. Puis pour les b's. Il y a 4 b correctement placés que vous avez calculés plus tôt. Vous avez un faux b dans le cluster 1, et c'est tout. Cela vous donne (4 1) pour les b.
3. Alors pour les c. Vous avez un faux c dans le cluster 2, avec trois bons dans le cluster 3, donc il y a (3 1).
4. Après cela, nous ne pouvons pas oublier cette paire de a dans le cluster 3 que nous avons appelé un vrai positif. Donc, en ce qui concerne cela, nous avons 1 faux a dans le cluster 2. Même s'il y a d'autres a dans le cluster 1, nous ne pouvons pas les appeler faux a parce qu'il y en a tellement.

Par conséquent, vous avez (5 1) + (5 2) + (4 1) + (3 1) + (2 1) qui équivaut à 5 + 10 + 4 + 3 + 2 = 24. C'est de là que vient le 24, alors il suffit de soustraire cela des 136 que vous avez déjà trouvés pour obtenir le vrai neg (TN).

Voici comment calculer chaque métrique pour Rand Index sans soustraire

Notes annexes pour une meilleure compréhension:

1) L'index Rand est basé sur la comparaison de paires d'éléments. La théorie suggère que des paires d'éléments similaires devraient être placées dans le même groupe, tandis que des paires d'éléments différents devraient être placées dans des groupes distincts.

2) RI ne se soucie pas de la différence de nombre de grappes. Il se soucie juste des paires d'éléments True / False.

Sur la base de cette hypothèse, l'indice Rand est calculé

Ok, plongeons ici est notre exemple:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Au dénominateur, nous avons le total de paires possibles, qui est (17 2) = 136

Permet maintenant de calculer chaque métrique pour une meilleure compréhension:

A) Commençons par facile a , ( vrais positifs ou similaire similaire )

Cela signifie que vous devez trouver toutes les paires d'éléments possibles, où la prédiction et la véritable étiquette ont été placées ensemble. Sur l'exemple de la grille, cela signifie obtenir la somme des paires possibles dans chaque cellule.

a = (5 2) + (1 2) + (2 2) + (1 2) + (4 2) + (0 2) + (0 2) + (1 2) + (3 2) = 
  = 10 + 0 + 1 + 0 + 6 + 0 + 0 + 0 + 3 = 20

C) Maintenant, faisons c ( faux positifs ou dissemblables incorrects )

Cela signifie, trouver toutes les paires, que nous avons placées ensemble, mais qui devraient être dans des grappes différentes. Sur un exemple de grille, cela signifie, trouver toutes les paires possibles entre 2 cellules horizontales quelconques

c = 5*1 + 5*2 + 1*2 + 
  + 1*4 + 1*0 + 4*0 + 
  + 0*1 + 0*3 + 1*3 = 
  = 5 + 10 + 2 + 4 + 0 + 0 + 0 + 0 + 3 = 24

D) Calculer d ( faux négatif ou similaire incorrect ) Cela signifie, trouver toutes les paires que nous avons placées dans des grappes différentes, mais qui devraient être ensemble. Sur l'exemple de la grille, trouvez toutes les paires possibles entre 2 cellules verticales quelconques

d = 5*1 + 5*0 + 1*0 + 
  + 1*4 + 1*1 + 4*1 + 
  + 2*0 + 2*3 + 0*3 = 
  = 5 + 0 + 0 + 4 + 1 + 4 + 0 + 6 + 0 = 20

B) Et, enfin, faisons b ( Vrais négatifs ou corrects dissemblables )

Cela signifie, trouver toutes les paires que nous avons placées dans des clusters différents, qui devraient également être dans des clusters différents. Sur la grille, cela signifie trouver toutes les paires possibles entre 2 cellules non verticales et non horizontales

Voici les nombres à multiplier pour mieux comprendre ce que je voulais dire:

d = x1*o2 + x1*o3 + x1*◊2 + x1*◊3 + 
  + x2*o1 + x2*o3 + x2*◊1 + x2*◊3 + 
  + x3*o1 + x3*o2 + x3*◊1 + x3*◊2 + 
  + o1*◊2 + o1*◊3 + 
  + o2*◊1 + o2*◊3 + 
  + o3*◊1 + o3*◊2

En chiffres:

d = 5*4 + 5*0 + 5*1 + 5*3 + 
  + 1*1 + 1*0 + 1*0 + 1*3 + 
  + 2*1 + 2*4 + 2*0 + 2*1 + 
  + 1*1 + 1*3 +
  + 4*0 + 4*3 = 72

Et à la fin, l'indice Rand est égal: (20 + 72) / 136 = 0.676

Voici l'image qui décrit votre question:

Pour résoudre ce problème, vous devez considérer cette matrice:

+--------------------------------+--------------------------------------+
| TP:                            | FN:                                  |
| Same class + same cluster      | Same class + different clusters      |
+--------------------------------+--------------------------------------+
| FP:                            | TN:                                  |
| different class + same cluster | different class + different clusters |
+--------------------------------+--------------------------------------+

Voici comment nous calculons TP, FN, FP pour Rand Index:

REMARQUE: Dans les équations ci-dessus, j'ai utilisé un triangle pour montrer le diamant dans l'image.

Par exemple, pour False Negative, nous devons choisir dans la classe mais dans différents clusters. Nous pouvons donc choisir

• ${5 \choose 1}{1 \choose 1} = 5$
• 1 X du cluster 1 et 1 X du cluster 3 = ${5 \choose 1}{2 \choose 1} = 10$
• 1 O du cluster 1 et 1 O du cluster 2 = ${1 \choose 1}{4 \choose 1} = 4$
• 1 X du cluster 2 et 1 X du cluster 3 = ${1 \choose 1}{2 \choose 1} = 2$
• 1 $\diamond$ des groupes 2 et 1 $\diamond$ du cluster 3 = ${1 \choose 1}{3 \choose 1} = 3$

Enfin, nous aurons $24$ ($=5+10+4+2+3$) États.

Il en va de même pour le reste des équations.

La partie la plus difficile est TN, ce qui peut être fait comme l'image ci-dessous:

Il existe des chemins plus courts pour calculer l'indice Rand, mais c'est le calcul en profondeur et étape par étape. Enfin, le tableau de contingence se présente comme suit:

+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+