Kendall tau distance
Encyclopedia
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 by Maurice Kendall
.
and 
is
will be equal to 0 if the two lists are identical and 
(where 
is the list size) if one list is the reverse of the other. Often Kendall tau distance is normalized by dividing by 
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
where
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.
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
A value of 0.4 indicates a somewhat low agreement in the rankings.
Metric (mathematics)
In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by 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
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
algorithm would make to place one list in the same order as the other list. The Kendall tau distance was created by Maurice Kendall
Maurice Kendall
Sir Maurice George Kendall, FBA was a British statistician, widely known for his contribution to statistics. The Kendall tau rank correlation is named after him.-Education and early life:...
.
Definition
The Kendall tau distance between two lists and is
will be equal to 0 if the two lists are identical and (where is the list size) if one list is the reverse of the other. Often Kendall tau distance is normalized by dividing by 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
where
- P is the set of unordered pairs of distinct elements in
and 
-
= 0 if i and j are in the same order in 
and 
-
= 1 if i and j are in the opposite order in 
and 
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.
Example
Suppose we rank a group of five people by height and by weight:| Person | A | B | C | D | E |
|---|---|---|---|---|---|
| Rank by Height | 1 | 2 | 3 | 4 | 5 |
| Rank by Weight | 3 | 4 | 1 | 2 | 5 |
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.
| Pair | Height | Weight | Count |
|---|---|---|---|
| (A,B) | 1 < 2 | 3 < 4 | |
| (A,C) | 1 < 3 | 3 > 1 | X |
| (A,D) | 1 < 4 | 3 > 2 | X |
| (A,E) | 1 < 5 | 3 < 5 | |
| (B,C) | 2 < 3 | 4 > 1 | X |
| (B,D) | 2 < 4 | 4 > 2 | X |
| (B,E) | 2 < 5 | 4 < 5 | |
| (C,D) | 3 < 4 | 1 < 2 | |
| (C,E) | 3 < 5 | 1 < 5 | |
| (D,E) | 4 < 5 | 2 < 5 |
Since there are 4 pairs whose values are in opposite order, the Kendall tau distance is 4. The normalized Kendall tau distance is
A value of 0.4 indicates a somewhat low agreement in the rankings.
See also
- Kendall tau rank correlation coefficientKendall tau rank correlation coefficientIn statistics, the Kendall rank correlation coefficient, commonly referred to as Kendall's tau coefficient, is a statistic used to measure the association between two measured quantities...
- Spearman's rank correlation coefficientSpearman's rank correlation coefficientIn statistics, Spearman's rank correlation coefficient or Spearman's rho, named after Charles Spearman and often denoted by the Greek letter \rho or as r_s, is a non-parametric measure of statistical dependence between two variables. It assesses how well the relationship between two variables can...
- Kemeny-Young (`maximum likelihood') voting ruleKemeny-Young methodThe Kemeny–Young method is a voting system that uses preferential ballots and pairwise comparison counts to identify the most popular choices in an election...