Kendall tau distance
   HOME

TheInfoList



OR:

The Kendall tau rank distance is a metric (distance function) that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the
bubble sort Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...
algorithm would take to place one list in the same order as the other list. The Kendall tau distance was created by
Maurice Kendall Sir Maurice George Kendall, FBA (6 September 1907 – 29 March 1983) was a prominent British statistician. The Kendall tau rank correlation is named after him. Education and early life Maurice Kendall was born in Kettering, Northampton ...
.


Definition

The Kendall tau ranking distance between two lists \tau_1 and \tau_2 is : K_d(\tau_1, \tau_2) = , \, . where * \tau_1(i) and \tau_2(i) are the rankings of the element i in \tau_1 and \tau_2 respectively. K_d(\tau_1,\tau_2) will be equal to 0 if the two lists are identical and \frac n (n-1) (where n is the list size) if one list is the reverse of the other. Kendall tau distance may also be defined as : K_d(\tau_1,\tau_2) = \sum_ \bar_(\tau_1,\tau_2) where * ''P'' is the set of unordered pairs of distinct elements in \tau_1 and \tau_2 * \bar_(\tau_1,\tau_2) = 0 if ''i'' and ''j'' are in the same order in \tau_1 and \tau_2 * \bar_(\tau_1,\tau_2) = 1 if ''i'' and ''j'' are in the opposite order in \tau_1 and \tau_2. Kendall tau distance can also be defined as the total number of discordant pairs. Kendall tau distance in Rankings: A permutation (or ranking) is an array of N integers where each of the integers between 0 and N-1 appears exactly once. The Kendall tau distance between two rankings is the number of pairs that are in different order in the two rankings. For example, the Kendall tau distance between 0 3 1 6 2 5 4 and 1 0 3 6 4 2 5 is four because the pairs 0-1, 3-1, 2-4, 5-4 are in different order in the two rankings, but all other pairs are in the same order. The normalized Kendall tau distance K_n is \frac = \frac and therefore lies in the interval ,1 If Kendall tau distance function is performed as K(L1,L2) instead of K(\tau_1,\tau_2) (where \tau_1 and \tau_2 are the rankings of L1 and L2 elements respectively), then triangular inequality is not guaranteed. The triangular inequality fails sometimes also in cases where there are repetitions in the lists. So then we are not dealing with a metric anymore. Generalised versions of Kendall tau distance have been proposed to give weights to different items and different positions in the ranking.


Comparison to Kendall tau rank correlation coefficient

The  Kendall tau distance (K_d) must not be confused with the Kendall tau rank correlation coefficient (K_c)  used in statistics. They are related by   K_c = 1 - 4 K_d /(n(n-1)) , K_d = (1 - K_c) (n(n-1))/4 Or simpler by  K_c = 1 - 2 K_n , K_n = (1-K_c)/2 where K_n is the normalised distance 2 K_d / (n(n-1)) see above) Still they are fundamentally different concepts. The distance is a value between 0 and n(n-1) /2. (The normalised distance is between 0 and 1) The correlation is between -1 and 1. The distance between equals is 0, the correlation between equals is 1. The distance between reversals is n(n-1) / 2 , the correlation between reversals is -1 For example comparing the rankings A>B>C>D and A>B>C>D the distance is 0 the correlation is 1. Comparing the rankings A>B>C>D and D>C>B>A the distance is 6 the correlation is -1 Comparing the rankings A>B>C>D and B>D>A>C the distance is 3 the correlation is 0


Example

Suppose one ranks a group of five people by height and by weight: Here person A is tallest and third-heaviest, B is the second -tallest and fourth-heaviest and so on. In order to calculate the Kendall tau distance, pair each person with every other person and count the number of times the values in list 1 are in the opposite order of the values in list 2. Since there are four pairs whose values are in opposite order, the Kendall tau distance is 4. The normalized Kendall tau distance is : \frac = 0.4. A value of 0.4 indicates that 40% of pairs differ in ordering between the two lists.


Computing the Kendall tau distance

A naive implementation in Python (using NumPy) is: import numpy as np def normalised_kendall_tau_distance(values1, values2): """Compute the Kendall tau distance.""" n = len(values1) assert len(values2)

n, "Both lists have to be of equal length" 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 < a b > b , np.logical_and(a > a b < b ).sum() return ndisordered / (n * (n - 1))
However, this requires n^2 memory, which is inefficient for large arrays. Given two rankings \tau_1,\tau_2, it is possible to rename the items such that \tau_1 = (1,2,3,...). Then, the problem of computing the Kendall tau distance reduces to computing the number of '' inversions'' in \tau_2—the number of index pairs i,j such that i while \tau_2(i) > \tau_2(j). There are several algorithms for calculating this number. * A simple algorithm based on
merge sort In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same i ...
requires time O(n \log n). * A more advanced algorithm requires time O(n\sqrt). Here is a basic C implementation. #include int kendallTau(short x[], short y[], int len) float normalize(int kt, int len)


See also

* Kendall tau rank correlation coefficient * Spearman's rank correlation coefficient * Kemeny–Young maximum-likelihood voting rule


References

* * * {{cite journal , last = Kendall , first = M. , date = 1938 , title = A New Measure of Rank Correlation , journal =
Biometrika ''Biometrika'' is a peer-reviewed scientific journal published by Oxford University Press for thBiometrika Trust The editor-in-chief is Paul Fearnhead (Lancaster University). The principal focus of this journal is theoretical statistics. It was es ...
, volume = 30 , issue = 1/2 , pages = 81–89 , doi=10.2307/2332226, jstor = 2332226


External links


Online software: computes Kendall's tau rank correlation

QuickVote
nbsp;— A website that calculates the Kendall tau distance between two interactive ranking lists and shows the pairwise disagreements between the lists. Covariance and correlation Statistical distance Comparison of assessments Permutations Distance