Cálculo del índice Rand

Question

Estoy tratando de averiguar cómo calcular el Índice Rand de un algoritmo de cluster, pero estoy atascado en el punto de cómo calcular los verdaderos y falsos negativos.

De momento estoy utilizando el ejemplo del libro An Introduction into Information Retrieval (Manning, Raghavan & Schütze, 2009). En la página 359 hablan de cómo calcular el índice de Rand. Para este ejemplo utilizan tres clusters y los clusters contienen los siguientes objetos.

1. a a a a a b
2. a b b b b c
3. a a c c c

Sustituyo el objeto (signos originales por letras, pero la idea y el recuento siguen siendo los mismos). Doy las palabras exactas del libro para ver de qué hablan:

Primero calculamos TP +FP. Los tres clusters contienen 6, 6 y 5 puntos, respectivamente, por lo que el número total de "positivos" o pares de documentos que se encuentran en el mismo cluster es:

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

De ellos, los pares a en el clúster 1, los pares b en el clúster 2, los pares c en el clúster 3, y el par a del grupo 3 son verdaderos positivos:

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

Por tanto, FP = 40 20 = 20.

Hasta aquí los cálculos son claros, y si tomo otros ejemplos obtengo los mismos resultados, pero cuando quiero calcular el falso negativo y el verdadero negativo Manning et al. afirman lo siguiente:

FN y TN se calculan de forma similar, lo que da como resultado la siguiente tabla de contingencia:

La tabla de contingencia tiene el siguiente aspecto:

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

La sentencia: "FN y TN se calculan de forma similar" no me queda clara y no entiendo qué números necesito para calcular el TN y el FN. Puedo calcular el lado derecho de la tabla haciendo lo siguiente:

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

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

Por lo tanto, FN + TN = 136 - TP + FP = 136 - 40 = 96, pero esto no me ayuda a calcular las variables por separado. Sobre todo cuando los autores dicen "FN y TN se calculan de forma similar". No veo cómo. Además, cuando miro otros ejemplos, calculan cada celda de la tabla de contingencia mirando cada par.

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

Mi primera pregunta, basada en el ejemplo de Manning et al (2009), ¿es posible calcular el TN y el FN si sólo se conocen el TP y el NP? Y si es así, ¿cómo es el cálculo similar basado en el ejemplo dado?

Answer 1

Estaba reflexionando sobre lo mismo, y lo resolví así. Supongamos que tenemos una matriz de co-ocurrencias/tabla de contingencia en la que las filas son los clusters de la verdad y las columnas son los clusters encontrados por el algoritmo de clustering.

Así, para el ejemplo del libro, quedaría así:

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

Ahora, puedes calcular muy fácilmente el TP + FP tomando la suma por columna y 'elegir 2' sobre todos esos valores. Así que las sumas son [6, 6, 5] y haces '6 elige 2' + '6 elige 2' + '5 elige 2'.

Ahora, de hecho, de manera similar, puede obtener TP + FN tomando la suma sobre las filas (por lo tanto, que es [8, 5, 4] en el ejemplo anterior), aplicar "elegir 2" sobre todos los valores, y tomar la suma de eso.

Los TP en sí se pueden calcular aplicando 'elige 2' a cada celda de la matriz y tomando la suma de todo (asumiendo que '1 elige 2' es 0).

De hecho, aquí hay algo de código Python que hace exactamente eso:

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 lo ejecuto obtengo:

$ 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 realidad no he comprobado más ejemplos que éste, así que espero haberlo hecho bien.... ;-)

Answer 2

Después de haber estudiado las otras respuestas en este hilo, aquí está mi implementación en Python, que toma arrays como entradas, sklearn -estilo:

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

Answer 3

Yo no estoy muy seguro, pero así es como hice el valor TN:
TN=(7 2) (10 2) (4 2)

(7 2) - Grupo 1 - la prueba dice "x", así que cuenta los que NO son x (y están correctamente agrupados en los grupos 2 y 3)

es decir, 4 "o" + 3 "d" (diamantes) =(7 2)

(10 2) - Agrupación 2, contar las que NO son "o" y están correctamente agrupadas en las agrupaciones 1 y 3,

es decir, 5'x' +(2'x'+ 3'd') = (10 2)

(4 2) - Agrupación 3, contar los que NO son "x" y NO son "d" (elemento en forma de diamante) que están correctamente agrupados en las agrupaciones 1 y 2.

es decir, 4 "o" en el grupo 2. =(4 2)

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

Entonces FN es :

FN = (17 2) - (TP+FP) - TN = 136 - 40 -72 = 24. ---> (17= número total de documentos)

Answer 4

Tomando el ejemplo de otra pregunta:

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

La respuesta razonable para FN:

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

Explicación:

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

  elija 2 de 8 para "x"(a) la combinación de la misma clase en los mismos conglomerados ( c(5,2) para el conglomerado 1 y c(2,2) para el conglomerado 3 ),

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

  elija 2 de 5 'o'(b) menos la combinación de la misma clase en los mismos clusters ( c(4,2) para el cluster 2 )

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

  elija 2 de 4 para '◇'(c) menos la combinación de la misma clase en los mismos clusters ( c(3,2) para el cluster 3 )

Lo derivé así.

Answer 5

Tengo una implementación de esto en R que explicaré:

TP (a en el código) es la suma de cada celda elige 2. Según la pregunta original (0 o 1 elija 2 igual a 0)

FN (b) es la suma de cada fila elija 2, todo sumado, menos TP. Donde la suma de cada fila representa el número de documentos de cada clase True.

La suma de todo esto son todos los documentos que son similares y están en el mismo cluster (TP) más todos los documentos que son similares y no están en el mismo cluster (FN).

Así que esto es (TP + FN) - TP = FN

FP (c) se calcula de forma similar. La suma de cada columna elige 2, todo sumado, menos TP. En este caso la suma de cada columna representa el número de documentos en cada cluster.

Por tanto, la suma de todo esto son todos los documentos que son similares y están en el mismo clúster (TP) más todos los documentos que no son similares y están en el mismo clúster (FP).

Así que esto es (TP + FP) - TP = FP

Con estos 3 cálculos, el resto del cálculo de TN es sencillo. La suma de la tabla elige 2, menos TP, FP & FN = TN (d)

La única duda que tengo con este método es su definición de TP. Usando la terminología de esta pregunta, no entiendo por qué las 2 a's del cluster 3 se consideran TP. He encontrado esto tanto aquí como en el libro de texto relacionado. Sin embargo entiendo su cálculo con la suposición de que su cálculo TP es correcto.

Espero que esto ayude

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)
}