- Kendall tau distance
The Kendall tau distance is a metric that counts the number of pairwise disagreements between two 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 algorithm would make to place one list in the same order as the other list. The Kendall tau distance was created byMaurice Kendall .Definition
The Kendall tau distance between two lists au_1 and au_2 is
: K( au_1, au_2) = |(i,j): i < j, ( au_1(i) < au_1(j) wedge au_2(i) > au_2(j) ) vee ( au_1(i) > au_1(j) wedge au_2(i) < au_2(j) )|.
K( au_1, au_2) will be equal to 0 if the two lists are identical and n(n-1)/2 (where n is the list size) if one list is the reverse of the other. Often Kendall tau distance is normalized by dividing by n(n-1)/2 so a value of 1 indicates maximum disagreement. The normalized Kendall tau distance therefore lies in the interval [0,1] .
Kendall tau distance may also be defined as
: K( au_1, au_2) = egin{matrix} sum_{{i,j}in P} ar{K}_{i,j}( au_1, au_2) end{matrix}
where
* "P" is the set of unordered pairs of distinct elements in au_1 and au_2
* ar{K}_{i,j}( au_1, au_2) = 0 if "i" and "j" are in the same order in au_1 and au_2
* ar{K}_{i,j}( au_1, au_2) = 1 if "i" and "j" are in the opposite order in au_1 and au_2Kendall tau distance can also be defined as the total number of
discordant pairs .Example
Suppose we rank a group of five people by height and by weight:
Here person A is tallest and third-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 4 pairs whose values are in opposite order, the Kendall tau distance is 4. The normalized Kendall tau distance is
: frac{4}{5(5 - 1)/2} = 0.4.
A value of 0.4 indicates a somewhat low agreement in the rankings.
See also
*
Bubble sort
*Kendall's tau
*Spearman's rank correlation coefficient References
*
* Kendall, M. (1948) "Rank Correlation Methods", Charles Griffin & Company Limited
* Kendall, M. (1938) "A New Measure of Rank Correlation", Biometrica, 30, 81-89.
External links
* [http://rsscse.org.uk/ts/bts/noether/text.html Why Kendall tau?]
* [http://www.wessa.net/rwasp_kendall.wasp Online software: computes Kendall's tau rank correlation]
Wikimedia Foundation. 2010.