Índice Rand

Medida de similitud entre dos agrupaciones de datos

Ejemplos de agrupaciones para un conjunto de datos con los algoritmos kMeans (izquierda) y Mean shift (derecha). El índice Rand ajustado calculado para estas dos agrupaciones es ${\displaystyle ARI\approx 0.94}$

El índice Rand ^[1] o medida Rand (denominada así por William M. Rand) en estadística , y en particular en agrupamiento de datos , es una medida de la similitud entre dos agrupamientos de datos . Se puede definir una forma del índice Rand que se ajusta a la agrupación aleatoria de elementos; este es el índice Rand ajustado . El índice Rand es la precisión para determinar si un vínculo pertenece o no a un grupo.

Índice Rand

Definición

Dado un conjunto de elementos y dos particiones de a comparar, , una partición de S en r subconjuntos, y , una partición de S en s subconjuntos, defina lo siguiente: ${\displaystyle n}$ ${\displaystyle S=\{o_{1},\ldots ,o_{n}\}}$ ${\displaystyle S}$ ${\displaystyle X=\{X_{1},\ldots ,X_{r}\}}$ ${\displaystyle Y=\{Y_{1},\ldots ,Y_{s}\}}$

• ${\displaystyle a}$, el número de pares de elementos en que están en el mismo subconjunto en y en el mismo subconjunto en ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$
• ${\displaystyle b}$, el número de pares de elementos en que están en diferentes subconjuntos en y en diferentes subconjuntos en ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$
• ${\displaystyle c}$, el número de pares de elementos en que están en el mismo subconjunto en y en diferentes subconjuntos en ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$
• ${\displaystyle d}$, el número de pares de elementos en que están en diferentes subconjuntos en y en el mismo subconjunto en ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$

El índice Rand, , es: ^{[1] [2]} ${\displaystyle R}$

${\displaystyle R={\frac {a+b}{a+b+c+d}}={\frac {a+b}{n \choose 2}}}$

Intuitivamente, se puede considerar como el número de acuerdos entre y y como el número de desacuerdos entre y . ${\displaystyle a+b}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle c+d}$ ${\displaystyle X}$ ${\displaystyle Y}$

Dado que el denominador es el número total de pares, el índice de Rand representa la frecuencia de ocurrencia de acuerdos sobre el total de pares, o la probabilidad de que y coincidan en un par elegido al azar. ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle {n \choose 2}}$se calcula como . ${\displaystyle n(n-1)/2}$

De manera similar, también se puede considerar el índice Rand como una medida del porcentaje de decisiones correctas tomadas por el algoritmo. Se puede calcular utilizando la siguiente fórmula:

${\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}$

donde es el número de verdaderos positivos, es el número de verdaderos negativos , es el número de falsos positivos y es el número de falsos negativos . ${\displaystyle TP}$ ${\displaystyle TN}$ ${\displaystyle FP}$ ${\displaystyle FN}$

Propiedades

El índice Rand tiene un valor entre 0 y 1, donde 0 indica que las dos agrupaciones de datos no coinciden en ningún par de puntos y 1 indica que las agrupaciones de datos son exactamente iguales.

En términos matemáticos, a, b, c, d se definen de la siguiente manera:

• ${\displaystyle a=|S^{*}|}$, dónde ${\displaystyle S^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i},o_{j}\in Y_{l}\}}$
• ${\displaystyle b=|S^{*}|}$, dónde ${\displaystyle S^{*}=\{(o_{i},o_{j})\mid o_{i}\in X_{k_{1}},o_{j}\in X_{k_{2}},o_{i}\in Y_{l_{1}},o_{j}\in Y_{l_{2}}\}}$
• ${\displaystyle c=|S^{*}|}$, dónde ${\displaystyle S^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i}\in Y_{l_{1}},o_{j}\in Y_{l_{2}}\}}$
• ${\displaystyle d=|S^{*}|}$, dónde ${\displaystyle S^{*}=\{(o_{i},o_{j})\mid o_{i}\in X_{k_{1}},o_{j}\in X_{k_{2}},o_{i},o_{j}\in Y_{l}\}}$

Para algunos ${\displaystyle 1\leq i,j\leq n,i\neq j,1\leq k,k_{1},k_{2}\leq r,k_{1}\neq k_{2},1\leq l,l_{1},l_{2}\leq s,l_{1}\neq l_{2}}$

Relación con la precisión de la clasificación

El índice Rand también puede verse a través del prisma de la precisión de la clasificación binaria sobre los pares de elementos en . Las dos etiquetas de clase son " y están en el mismo subconjunto en y " y " y están en diferentes subconjuntos en y ". ${\displaystyle S}$ ${\displaystyle o_{i}}$ ${\displaystyle o_{j}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle o_{i}}$ ${\displaystyle o_{j}}$ ${\displaystyle X}$ ${\displaystyle Y}$

En ese contexto, es el número de pares etiquetados correctamente como pertenecientes al mismo subconjunto ( verdaderos positivos ), y es el número de pares etiquetados correctamente como pertenecientes a diferentes subconjuntos (verdaderos negativos). ${\displaystyle a}$ ${\displaystyle b}$

Índice Rand ajustado

El índice Rand ajustado es la versión corregida por azar del índice Rand. ^{[1] [2] [3]} Esta corrección por azar establece una línea base utilizando la similitud esperada de todas las comparaciones por pares entre agrupaciones especificadas por un modelo aleatorio. Tradicionalmente, el índice Rand se corregía utilizando el modelo de permutación para agrupaciones (el número y el tamaño de las agrupaciones dentro de una agrupación son fijos, y todas las agrupaciones aleatorias se generan mezclando los elementos entre las agrupaciones fijas). Sin embargo, las premisas del modelo de permutación se violan con frecuencia; en muchos escenarios de agrupación, el número de agrupaciones o la distribución del tamaño de esas agrupaciones varían drásticamente. Por ejemplo, considere que en K-means el número de agrupaciones lo fija el profesional, pero los tamaños de esas agrupaciones se infieren de los datos. Las variaciones del índice Rand ajustado dan cuenta de diferentes modelos de agrupaciones aleatorias. ^[4]

Aunque el índice Rand solo puede producir un valor entre 0 y +1, el índice Rand ajustado puede producir valores negativos si el índice es menor que el índice esperado. ^[5]

La tabla de contingencia

Dado un conjunto S de n elementos, y dos agrupaciones o particiones ( por ejemplo, clusterizaciones) de estos elementos, a saber y , la superposición entre X e Y se puede resumir en una tabla de contingencia donde cada entrada denota el número de objetos en común entre y  : . ${\displaystyle X=\{X_{1},X_{2},\ldots ,X_{r}\}}$ ${\displaystyle Y=\{Y_{1},Y_{2},\ldots ,Y_{s}\}}$ ${\displaystyle \left[n_{ij}\right]}$ ${\displaystyle n_{ij}}$ ${\displaystyle X_{i}}$ ${\displaystyle Y_{j}}$ ${\displaystyle n_{ij}=|X_{i}\cap Y_{j}|}$

${\displaystyle {\begin{array}{c|cccc|c}{{} \atop X}\!\diagdown \!^{Y}&Y_{1}&Y_{2}&\cdots &Y_{s}&{\text{sums}}\\\hline X_{1}&n_{11}&n_{12}&\cdots &n_{1s}&a_{1}\\X_{2}&n_{21}&n_{22}&\cdots &n_{2s}&a_{2}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\X_{r}&n_{r1}&n_{r2}&\cdots &n_{rs}&a_{r}\\\hline {\text{sums}}&b_{1}&b_{2}&\cdots &b_{s}&\end{array}}}$

Definición

El índice Rand ajustado original que utiliza el modelo de permutación es

${\displaystyle ARI={\frac {\left.\sum _{ij}{\binom {n_{ij}}{2}}-\left[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}\right]\right/{\binom {n}{2}}}{\left.{\frac {1}{2}}\left[\sum _{i}{\binom {a_{i}}{2}}+\sum _{j}{\binom {b_{j}}{2}}\right]-\left[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}\right]\right/{\binom {n}{2}}}}}$

¿Dónde están los valores de la tabla de contingencia? ${\displaystyle n_{ij},a_{i},b_{j}}$

Véase también

• Coeficiente de correspondencia simple

Referencias

1. WM Rand (1971). "Criterios objetivos para la evaluación de métodos de agrupamiento". Revista de la Asociación Estadounidense de Estadística . 66 (336). Asociación Estadounidense de Estadística: 846–850. doi :10.2307/2284239. JSTOR  2284239.
2. Lawrence Hubert y Phipps Arabie (1985). "Comparación de particiones". Revista de clasificación . 2 (1): 193–218. doi :10.1007/BF01908075.
3. Nguyen Xuan Vinh, Julien Epps y James Bailey (2009). "Medidas teóricas de la información para la comparación de agrupamientos: ¿es necesaria una corrección por azar?" (PDF) . ICML '09: Actas de la 26.ª Conferencia internacional anual sobre aprendizaje automático . ACM. págs. 1073–1080.PDF.
4. Alexander J Gates y Yong-Yeol Ahn (2017). "El impacto de los modelos aleatorios en la similitud de agrupamiento" (PDF) . Journal of Machine Learning Research . 18 : 1–28.
5. "Comparación de agrupamientos: una descripción general" (PDF) .

Enlaces externos

• Implementación en C++ con archivos mex de MATLAB