Distancia tau de Kendall

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

La distancia de clasificación 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 denomina distancia de clasificación de burbujas, ya que es equivalente a la cantidad de intercambios que el algoritmo de clasificación de burbujas necesitaría 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 $tau _{1}$ y $tau _{2}$ es<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3dd2cb3cf2dd49707ada6a2a38879a97d97d203" alt="{displaystyle K_{d}(tau _{1},tau _{2})=|{(i,j):i<j,[tau _{1}(i)tau_{2}(j)]vee [tau_{1}(i)>tau_{1}(j) cuña tau _{2}(i)

donde

$tau _{1}(i)$ y $tau _{2}(i)$ son las clasificaciones del elemento $i$ en $tau _{1}$ y $tau _{2}$ respectivamente.

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

La distancia tau de Kendall también se puede definir como<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3f58b452e84b5c0a08ad7baa3113e37cf26227b2" alt="{displaystyle K_{d}(tau _{1},tau _{2})=sum _{{i,j}in P,i

donde

P es el conjunto de pares desordenados de elementos distintos en $tau _{1}$ y $tau _{2}$
${bar {K}}_{{i,j}}(tau _{1},tau _{2})$ = 0 si i y j están en el mismo orden en $tau _{1}$ y $tau _{2}$
${bar {K}}_{{i,j}}(tau _{1},tau _{2})$ = 1 si i y j están en orden opuesto en $tau _{1}$ y $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 Rankings: Una permutación (o ranking) es una matriz de N enteros donde cada uno de los 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 diferente orden en los dos clasificaciones, pero todos los demás pares están en el mismo orden.

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

Si la función de distancia tau de Kendall se realiza como $K(L1,L2)$ en lugar de $K(tau _{1},tau _{2})$ (donde $tau _{1}$ y $tau _{2}$ son las clasificaciones de $L1$ y $L2$ 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.

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

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

La distancia tau de Kendall ( $K_{d}$ ) no debe confundirse con el coeficiente de correlación de rangos tau de Kendall ( $k_c$ ) que se utiliza en las estadísticas.

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 por ${displaystyle K_{c}=1-2K_{n},K_{n}=(1-K_{c})/2}$ dónde $K_{n}$ está la distancia normalizada ${displaystyle 2K_{d}/(n(n-1))}$ ver arriba)

Todavía son conceptos fundamentalmente diferentes.

La distancia es un valor entre 0 y ${ estilo de visualización n (n-1)/2}$ . (La distancia normalizada está entre 0 y 1)

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

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

La distancia entre inversiones es ${ estilo de visualización n (n-1)/2}$ , la correlación entre inversiones es -1

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 uno clasifica un grupo de cinco personas por altura y por peso:

Persona	UN	B	C	D	mi	clasificación
Clasificar por altura	1	2	3	4	5	A>B>C>D>E
Clasificación por peso	3	4	1	2	5	C>D>A>B>E

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 cada otra persona y cuente la cantidad de veces que los valores en la lista 1 están en el orden opuesto de los valores en la lista 2.

Par	Altura	Peso	Contar
(A,B)	1 < 2	3 < 4
(C.A)	1 < 3	3 > 1	X
(ANUNCIO)	1 < 4	3 > 2	X
(A,E)	1 < 5	3 < 5
(ANTES DE CRISTO)	2 < 3	4 > 1	X
(B, D)	2 < 4	4 > 2	X
(SER)	2 < 5	4 < 5
(CD)	3 < 4	1 < 2
(C,E)	3 < 5	1 < 5
(DELAWARE)	4 < 5	2 < 5

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 ${ fracción {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  np

def  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. rejilla de malla (np. arange (n), np. arange (n)) a = np. clasificación (
      valores1) 
    b  =  np. argsort (valores2) 
    ndisordered  =  np. o_lógico (np. y_lógico (a [ i ]  <  a [ j ],  b [ i ]  >  b [ j ]),  np. y_lógico (a [ i ]  >  a [ j ],  b [ i ]  < b [ j ])). suma () 
    devuelve  desordenado  /  (n  *  (n  -  1))

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

Dadas dos clasificaciones $tau_1,tau_2$ , es posible cambiar el nombre de los elementos de tal manera que ${ estilo de visualización tau _ {1} = (1,2,3,...)}$ . Entonces, el problema de calcular la distancia tau de Kendall se reduce a calcular el número de inversiones en $tau _{2}$ —el número de pares de índices $yo, j$ tales que <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e60ff2d1b23e30fb2979e8c1536da03493f943cf" alt="yomientras tau _ {2} (j)}">. Hay varios algoritmos para calcular este número.

Un algoritmo simple basado en la ordenación por fusión requiere tiempo $O(nlog n)$ .
Un algoritmo más avanzado requiere tiempo ${displaystyle O(n{sqrt {log {n}}})}$ .

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

#incluir <stdbool.h> 

int kendallTau (x corta [], y corta [], int len ) {       
    int yo, j, v = 0;     
    booleano a, b;  

    para (i = 0; i < len; i ++) {        
        para (j = yo + 1; j < len; j ++) {          

            a = x [ yo ] < x [ j ] && y [ yo ] > y [ j ];        
            b = x [ yo ] > x [ j ] && y [ yo ] < y [ j ];        

            si (un || b)   
                v ++;

        }
    }

    volver abs (v); 
}

flotar normalizar (int kt, int len ) {     
    volver kt / (len * (len - 1) / 2.0);         
}

Contenido relacionado

Más resultados...