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

A continuación se muestra la imagen que describe su pregunta:

Para resolver este problema, hay que tener en cuenta esta matriz:

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

Así es como calculamos TP, FN, FP para Rand Index:

NOTA: En las ecuaciones anteriores, he utilizado un triángulo para mostrar el diamante en la imagen.

Por ejemplo, para el Falso Negativo, debemos elegir de la clase pero en clusters diferentes. Así, podemos elegir

• 1 X del grupo 1 y 1 X del grupo 2 = ${5 \choose 1}{1 \choose 1} = 5$
• 1 X del grupo 1 y 1 X del grupo 3 = ${5 \choose 1}{2 \choose 1} = 10$
• 1 O del grupo 1 y 1 O del grupo 2 = ${1 \choose 1}{4 \choose 1} = 4$
• 1 X del grupo 2 y 1 X del grupo 3 = ${1 \choose 1}{2 \choose 1} = 2$
• 1 $\diamond$ de los grupos 2 y 1 $\diamond$ del grupo 3 = ${1 \choose 1}{3 \choose 1} = 3$

Por último, tendremos $24$ ( $=5+10+4+2+3$ ).

Lo mismo ocurre con el resto de las ecuaciones.

La parte más difícil es TN que se puede hacer como la imagen de abajo:

Existen algunos caminos más cortos para calcular el Índice Rand, pero se trata del cálculo en profundidad y paso a paso. Finalmente, La tabla de contingencia tiene el siguiente aspecto:

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

Answer 2

Puede calcular TN y FN de la misma manera.

Basta con cambiar los papeles de etiquetas et racimos .

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

... y luego realizar los mismos cálculos.

Answer 3

PIENSO que he hecho ingeniería inversa para eliminar el falso negativo (FN). Para los verdaderos positivos, hiciste 4 grupos que eran positivos. En el grupo 1, tenías las cinco a; en el grupo 2, tenías las 4 b; en el grupo 3 tenías las 3 c Y las 2 a.

Así que para el falso negativo.

1. Empiece con las a del grupo 1; hay 5 a correctamente colocadas en el grupo 1. Tiene 1 a falsa en el grupo 2 y dos a falsas en el grupo 3. Hay una a falsa en la agrupación 2 y dos a falsas en la agrupación 3. Esto da (5 1) y (5 2). Eso da (5 1) y (5 2).
2. Entonces, por las "b". Hay 4 b's correctamente colocadas que calculaste antes. Tienes una b falsa en el grupo 1, y eso es todo. Eso te da (4 1) para las b's.
3. Entonces para los c. Tienes una c falsa en el grupo 2, con tres correctas en el grupo 3, así que hay (3 1).
4. Después, no podemos olvidarnos de ese par de a en el grupo 3 que llamamos verdadero positivo. Así que con respecto a eso, tenemos 1 a falsa en el cluster 2. Aunque hay otras "a" en el grupo 1, no podemos llamarlas "a" falsas porque hay muchas.

Por lo tanto, tienes (5 1) + (5 2) + (4 1) + (3 1) + (2 1) que es igual a 5 + 10 + 4 + 3 + 2 = 24. De ahí sale el 24, luego sólo tienes que restarlo de los 136 que ya has encontrado para obtener el verdadero neg (TN).

Answer 4

A continuación se explica cómo calcular cada una de las métricas del Índice Rand sin restar

Notas al margen para facilitar la comprensión:

1. El índice Rand se basa en la comparación de pares de elementos. La teoría sugiere que los pares de elementos similares deben colocarse en el mismo clúster, mientras que los pares de elementos disímiles deben colocarse en clústeres separados.

2. A RI no le importa la diferencia en el número de grupos. Sólo le importan los pares de elementos Verdadero/Falso.

Partiendo de este supuesto, se calcula el Índice Rand

Ok, vamos a sumergirnos aquí está nuestro ejemplo:

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

En el denominador, tenemos el total de pares posibles, que es (17 2) = 136

Ahora vamos a calcular cada métrica para entenderlo mejor:

A) Empecemos por lo fácil a , ( Verdaderos aspectos positivos o corregir similar )

Es decir, hay que encontrar todos los pares de elementos posibles en los que la predicción y la etiqueta verdadera estén juntas. En el ejemplo de la cuadrícula significa obtener la suma de los pares posibles dentro de cada celda.

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) Ahora, hagamos c ( Falso negativo o similar incorrecto )

Es decir, encontrar todos los pares que hemos colocado en grupos diferentes, pero que deberían estar juntos.

En el ejemplo de la cuadrícula significa, encontrar todos los pares posibles entre 2 celdas horizontales cualesquiera

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) Calcular d ( Falsos positivos o disímil incorrecto )

Significa encontrar todos los pares que hemos colocado juntos, pero que deberían estar en grupos diferentes.

En el ejemplo de la cuadrícula, encuentre todos los pares posibles entre 2 celdas verticales cualesquiera

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) Y, finalmente hagamos b ( Verdaderos negativos o corregir disimilares )

Es decir, encontrar todos los pares que hemos colocado en clusters diferentes, que también deberían estar en clusters diferentes. En cuadrícula, significa encontrar todos los pares posibles entre cualquier 2 celdas no verticales y no horizontales

Aquí están los números que se deben multiplicar, para entender mejor lo que quería decir:

b = 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 números:

b = 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

Y al final Rand Index es igual: (20 + 72) / 136 = 0.676