distancia kendall tau

Métrica para comparar pedidos

La distancia de rango tau de Kendall es una métrica (función de distancia) que cuenta el número de desacuerdos por pares entre dos listas de clasificación. Cuanto mayor es la distancia, más diferentes son las dos listas. La distancia tau de Kendall también se llama distancia de clasificación de burbujas, ya que es equivalente al número de intercambios que necesitaría el algoritmo de clasificación de burbujas para colocar una lista en el mismo orden que la otra lista. 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 ${\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 (dónde está 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 se puede definir 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 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 diferente orden 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 los 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 realiza como en lugar de (donde y son las clasificaciones de y elementos respectivamente), entonces no se garantiza la desigualdad triangular. La desigualdad triangular falla a veces también en los casos en que hay repeticiones en las listas. Entonces 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 ponderaciones 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 está la distancia normalizada ( ver 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, al comparar 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 clasificamos 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, empareje a cada persona con todas las demás y cuente el número de veces que los valores de la lista 1 están en el orden opuesto a los valores de la lista 2.

Como 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.

Calcular la distancia tau de Kendall

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

importar  numpy  como  npdef  normalised_kendall_tau_distance ( valores1 ,  valores2 ): """Calcular la distancia tau de Kendall.""" n = len ( valores1 ) afirmar len ( valores2 ) == n , "Ambas listas deben tener la misma longitud" i , j = np . meshgrid ( np . arange ( n ), np . arange ( n )) a = np . argsort ( valores1 ) b = np . argsort ( valores2 ) desordenado = np . logic_or ( np . logic_and ( a [ i ] < a [ j ], b [ i ] > b [ j ]), np . logic_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}}$

Dadas dos clasificaciones , 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 el número de inversiones en —el número de pares de índices tales que while . 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 clasificació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 de C.

#incluir <stdbool.h> int kendallTau ( x corto [], y corto [], int len ) { int i , j , v = 0 ; booleano 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 ++ ;     } }  devolver abdominales ( v ); } float normalize ( int kt , int len ) { return kt / ( len * ( len - 1 ) / 2.0 ); }               

Ver también

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

Referencias

1. "Clasificación de aplicaciones".
2. Ravi Kumar y Sergei Vassilvitskii (2010). Distancias Generalizadas entre Rankings (PDF) .
3. Ionescu, Vlad. "calcular el 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). "Conteo de inversiones, conteo de rangos ortogonales sin conexión y problemas relacionados". Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos . pag. 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 k listas principales". Revista SIAM de Matemática Discreta . 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 de 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.