Distancia tau de Kendall

Métrica para comparar pedidos

La distancia de clasificación tau de Kendall es una métrica (función de distancia) que cuenta la cantidad de desacuerdos por pares entre dos listas de clasificación. Cuanto mayor sea la distancia, más disímiles serán las dos listas. La distancia tau de Kendall también se denomina distancia de ordenamiento de burbuja , ya que es equivalente a la cantidad de intercambios que necesitaría el algoritmo de ordenamiento de burbuja para colocar una lista en el mismo orden que la otra. La distancia tau de Kendall fue creada por Maurice Kendall .

Definición

La distancia de clasificación tau de Kendall entre dos listas y es donde y son las clasificaciones del elemento en y respectivamente. ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}}$ $${\displaystyle K_{d}(\tau _{1},\tau _{2})=|\{(i,j):i<j,[\tau _{1}(i)<\tau _{1}(j)\wedge \tau _{2}(i)>\tau _{2}(j)]\vee [\tau _{1}(i)>\tau _{1}(j)\wedge \tau _{2}(i)<\tau _{2}(j)]\}|.}$$ ${\displaystyle \tau _{1}(i)}$ ${\displaystyle \tau _{2}(i)}$ ${\displaystyle i}$ ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}}$

${\displaystyle K_{d}(\tau _{1},\tau _{2})}$será igual a 0 si las dos listas son idénticas y (donde es el tamaño de la lista) si una lista es la inversa de la otra. ${\textstyle {\frac {1}{2}}n(n-1)}$ ${\displaystyle n}$

La distancia tau de Kendall también puede definirse como $${\displaystyle K_{d}(\tau _{1},\tau _{2})=\sum _{\{i,j\}\in P,i<j}{\bar {K}}_{i,j}(\tau _{1},\tau _{2})}$$

dónde

• P es el conjunto de pares desordenados de elementos distintos en y ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}}$
• ${\displaystyle {\bar {K}}_{i,j}(\tau _{1},\tau _{2})}$= 0 si i y j están en el mismo orden en y ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}}$
• ${\displaystyle {\bar {K}}_{i,j}(\tau _{1},\tau _{2})}$= 1 si i y j están en el orden opuesto en y ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}.}$

La distancia tau de Kendall también se puede definir como el número total de pares discordantes .

Distancia tau de Kendall en clasificaciones: Una permutación (o clasificación) es una matriz de N números enteros donde cada uno de los números enteros entre 0 y N-1 aparece exactamente una vez.

La distancia tau de Kendall entre dos clasificaciones es el número de pares que están en orden diferente en las dos clasificaciones. Por ejemplo, la distancia tau de Kendall entre 0 3 1 6 2 5 4 y 1 0 3 6 4 2 5 es cuatro porque los pares 0-1, 3-1, 2-4, 5-4 están en orden diferente en las dos clasificaciones, pero todos los demás pares están en el mismo orden. ^[1]

La distancia tau de Kendall normalizada es y, por lo tanto, se encuentra en el intervalo [0,1]. ${\displaystyle K_{n}}$ ${\displaystyle {\frac {K_{d}}{{\frac {1}{2}}n(n-1)}}={\frac {2K_{d}}{n(n-1)}}}$

Si la función de distancia tau de Kendall se ejecuta como en lugar de (donde y son las clasificaciones de los elementos y respectivamente), entonces no se garantiza la desigualdad triangular. La desigualdad triangular falla a veces también en casos en los que hay repeticiones en las listas. Por lo tanto, ya no estamos tratando con una métrica. ${\displaystyle K(L1,L2)}$ ${\displaystyle K(\tau _{1},\tau _{2})}$ ${\displaystyle \tau _{1}}$ ${\displaystyle \tau _{2}}$ ${\displaystyle L1}$ ${\displaystyle L2}$

Se han propuesto versiones generalizadas de la distancia tau de Kendall para dar peso a diferentes elementos y diferentes posiciones en la clasificación. ^[2]

Comparación con el coeficiente de correlación de rango tau de Kendall

La distancia tau de Kendall ( ) no debe confundirse con el coeficiente de correlación de rango tau de Kendall ( ) utilizado en estadística. ${\displaystyle K_{d}}$ ${\displaystyle K_{c}}$

Están relacionados por   , ${\displaystyle K_{c}=1-4K_{d}/(n(n-1))}$ ${\displaystyle K_{d}=(1-K_{c})(n(n-1))/4}$

O más simple,   donde la distancia normalizada se ve arriba) ${\displaystyle K_{c}=1-2K_{n},K_{n}=(1-K_{c})/2}$ ${\displaystyle K_{n}}$ ${\displaystyle 2K_{d}/(n(n-1))}$

La distancia es un valor entre 0 y . (La distancia normalizada está entre 0 y 1) ${\displaystyle n(n-1)/2}$

La correlación está entre -1 y 1.

La distancia entre iguales es 0, la correlación entre iguales es 1.

La distancia entre reversiones es , la correlación entre reversiones es -1 ${\displaystyle n(n-1)/2}$

Por ejemplo, comparando las clasificaciones A>B>C>D y A>B>C>D la distancia es 0 y la correlación es 1.

Comparando las clasificaciones A>B>C>D y D>C>B>A la distancia es 6 la correlación es -1

Comparando las clasificaciones A>B>C>D y B>D>A>C la distancia es 3 la correlación es 0

Ejemplo

Supongamos que se clasifica a un grupo de cinco personas por altura y peso:

Aquí la persona A es la más alta y la tercera más pesada, B es la segunda más alta y la cuarta más pesada, y así sucesivamente.

Para calcular la distancia tau de Kendall entre estas dos clasificaciones, empareje a cada persona con todas las demás personas y cuente la cantidad de veces que los valores de la lista 1 están en el orden opuesto a los valores de la lista 2.

Dado que hay cuatro pares cuyos valores están en orden opuesto, la distancia tau de Kendall es 4. La distancia tau de Kendall normalizada es

${\displaystyle {\frac {4}{5(5-1)/2}}=0.4.}$

Un valor de 0,4 indica que el 40% de los pares difieren en el orden entre las dos listas.

Cálculo de la distancia tau de Kendall

Una implementación ingenua en Python (usando NumPy ) es:

importar  numpy  como  npdef  normalised_kendall_tau_distance ( values1 ,  values2 ): " " " Calcula la distancia tau de Kendall.""" n = len ( values1 ) assert len ( values2 ) == n , "Ambas listas deben tener la misma longitud" i , j = np.meshgrid ( np.arange ( n ) , np.arange ( n ) ) a = np.argsort ( values1 ) b = np.argsort ( values2 ) ndisordered = np.logical_or ( np.logical_and ( a [ i ] < a [ j ] , b [ i ] > b [ j ] ) , np.logical_and ( a [ i ] > a [ j ] , b [ i ] < b [ j ] ) ) . suma () devuelve desordenado / ( n * ( n - 1 ))                                          

Sin embargo, esto requiere memoria, lo cual es ineficiente para matrices grandes. ${\displaystyle n^{2}}$

Dados dos rankings , es posible cambiar el nombre de los elementos de manera que . Entonces, el problema de calcular la distancia tau de Kendall se reduce a calcular la cantidad de inversiones en —la cantidad de pares de índices de manera que mientras . Existen varios algoritmos para calcular este número. ${\displaystyle \tau _{1},\tau _{2}}$ ${\displaystyle \tau _{1}=(1,2,3,...)}$ ${\displaystyle \tau _{2}}$ ${\displaystyle i,j}$ ${\displaystyle i<j}$ ${\displaystyle \tau _{2}(i)>\tau _{2}(j)}$

• Un algoritmo simple basado en la ordenación por fusión requiere tiempo . ^[3] ${\displaystyle O(n\log n)}$
• Un algoritmo más avanzado requiere tiempo . ^[4] ${\displaystyle O(n{\sqrt {\log {n}}})}$

Aquí hay una implementación básica en C.

#include <stdbool.h> int kendallTau ( corto x [], corto y [], int len ​​) { int i , j , v = 0 ; bool a , b ;                 para ( i = 0 ; i < len ; i ++ ) { para ( j = i + 1 ; j < len ; j ++ ) {                    a = x [ i ] < x [ j ] && y [ i ] > y [ j ]; b = x [ i ] > x [ j ] && y [ i ] < y [ j ];                  si ( a || b ) v ++ ;     } }  devuelve abs ( v ); } flotante normalizar ( int kt , int len ​​) { devolver kt / ( len * ( len - 1 ) / 2.0 ); }               

Véase también

• Coeficiente de correlación de rango tau de Kendall
• Coeficiente de correlación de rangos de Spearman
• Regla de votación de máxima verosimilitud de Kemeny-Young

Referencias

1. "Ordenamiento de aplicaciones".
2. Ravi Kumar y Sergei Vassilvitskii (2010). Distancias generalizadas entre clasificaciones (PDF) .
3. Ionescu, Vlad. "Cálculo del número de "inversiones" en una permutación". Desbordamiento de pila . Consultado el 24 de febrero de 2017 .
4. Chan, Timothy M.; Pătraşcu, Mihai (2010). "Inversiones de conteo, conteo de rango ortogonal fuera de línea y problemas relacionados". Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos . pág. 161. CiteSeerX 10.1.1.208.2715 . doi :10.1137/1.9781611973075.15. ISBN  978-0-89871-701-3.

• Fagin, R.; Kumar, R.; Sivakumar, D. (2003). "Comparación de las listas de los k mejores". Revista SIAM de Matemáticas Discretas . 17 (1): 134–160. CiteSeerX  10.1.1.86.3234 . doi :10.1137/S0895480102412856. S2CID  6249357.
• Kendall, M. (1948). Métodos de correlación de rangos . Charles Griffin & Company Limited.
• Kendall, M. (1938). "Una nueva medida de correlación de rangos". Biometrika . 30 (1/2): 81–89. doi :10.2307/2332226. JSTOR  2332226.

Enlaces externos

• Software en línea: calcula la correlación del rango tau de Kendall
• QuickVote: un sitio web que calcula la distancia tau de Kendall entre dos listas de clasificación interactivas y muestra los desacuerdos por pares entre las listas.