7
$\begingroup$

ranking i: {3, 1, 2}

ranking j: {2, 1, 3}

I am referring to the Wikipedia page here, and to calculate the Kendall distance, I just need to count the number of times the values in ranking i are in the opposite order of the values in ranking j.

3 < 1 in ranking i, but 3 > 1 in ranking j

3 < 2 in ranking i, but 3 > 2 in ranking j

1 < 2 in ranking i, but 1 > 2 in ranking j

There are 3 switches, so the Kendall distance is 3. However when I call a function to calculate the Kendall's distance in R, it returns 1. What's the correct Kendall's distance between these 2 rankings?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The wiki says the distance is the total number of discordant pairs of observations (that is, it is Q in the formula of Gamma or Kendall's tau). Consider the pairs of observations (columns): i(3>1) and j(2>1) = concordant; i(1<2) and j(1<3) = concordant; i(3>2) but j(2<3) = discordant. One discordant pair. $\endgroup$
    – ttnphns
    Aug 24, 2015 at 20:47
  • 1
    $\begingroup$ If it's [3,1,2] vs [2,1,3] the number of discordant pairs here is 3 out of 3. If you use Python's scipy Kendall’s tau function to calculate the correlation coefficient you'll get -1. The coefficient is defined as the ratio of concordant pairs minus the discordant pairs, in this case it's 0/3 - 3/3 Unless you're looking at it as indices and values, (let's say indices are letters) than: ranking i: a-3, b-1, c-2 = b-1, c-2, a-3 ranking j: a-2, b-1, c-3 = b-1, a-2, c-3 In that case the distance is 1. So perhaps the function in R looks at it this way $\endgroup$
    – Oleg
    Apr 8, 2020 at 3:55

4 Answers 4

Reset to default
4
$\begingroup$

The Kendall tau distance in your case is, indeed, 1.

See the following python code:

import itertools

def kendallTau(A, B):
    pairs = itertools.combinations(range(0, len(A)), 2)

    distance = 0

    for x, y in pairs:
        a = A[x] - A[y]
        b = B[x] - B[y]

        # if discordant (different signs)
        if (a * b < 0):
            distance += 1

    return distance


ranking_i = [3, 1, 2]
ranking_j = [2, 1, 3]
assert kendallTau(ranking_i, ranking_j) == 1
Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ that wrong, the distance is 3. See other answers $\endgroup$
    – Cohensius
    Mar 31, 2020 at 9:20
  • $\begingroup$ The function works ok, there's just confusion between orderings and ranks. The ordered list of objects 3 > 1 > 2 posed in the original question translates to assigned ranks of [2, 3, 1] (i.e. object 3 is ranked first, object 1 second, and object 2 third). Likewise, the list 2 > 1 > 3 takes assigned ranks of [2, 1, 3]. This answer assumes the ordered lists ('rankings') provided are themselves ranks assigned to objects (e.g. assuming in 'ranking i' that object 1 is ranked third, object 2 first, etc). Setting ranking_i = [2, 3, 1] and ranking_j = [2, 1, 3] yields the correct distance (3). $\endgroup$
    – awhug
    Sep 10, 2020 at 9:53
8
$\begingroup$

The wrong answer got accepted! The correct answer is 3.

From Wikipedia: Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list.

import itertools

def kendall_tau_distance(order_a, order_b):
    pairs = itertools.combinations(range(1, len(order_a)+1), 2)
    distance = 0
    for x, y in pairs:
        a = order_a.index(x) - order_a.index(y)
        b = order_b.index(x) - order_b.index(y)
        if a * b < 0:
            distance += 1
    return distance

print kendall_tau_distance([3,1,2], [2,1,3])
3
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I think you need to look again at the comment under the original question for the definition of Kendall distance. $\endgroup$
    – mdewey
    Jan 25, 2018 at 14:37
  • 3
    $\begingroup$ I think that the definition of Kendall tau distance in the comment under the original question is wrong. its not whats is in en.wikipedia.org/wiki/Kendall_tau_distance The Kendall tau rank distance between two rank orders is the total number of rank disagreements over all unordered pairs. $\endgroup$
    – Cohensius
    Jan 25, 2018 at 16:20
  • $\begingroup$ @Cohensius It clearly says in the mathematical definition of $K(\tau_1 \tau_2)$ that you have to index the lists, also, in OP's question, you only need one single swap to make one list the same as the other (you swap indexes 1 and 3). $\endgroup$
    – Ash
    May 4, 2018 at 19:47
  • 2
    $\begingroup$ ...counts the number of pairwise disagreements between two ranking lists: in the OP example: in ranking i: 3<1 while in ranking j: 1<3 in ranking i: 1<2 while in ranking j: 2<1 in ranking i: 3<2 while in ranking j: 2<3 Thats 3 pairwise disagreements $\endgroup$
    – Cohensius
    May 6, 2018 at 16:24
  • 3
    $\begingroup$ @Ash the swaps need to be between adjacent items, so 3 is correct $\endgroup$
    – wjchulme
    Jul 17, 2019 at 14:31
1
$\begingroup$

The Kendall tau distance in this instance is 3. It is also known as Kemeny distance. See here and here.

In some fields rankings are also allowed to have ties, therefore the Kemeny could be considered as a distance of 6 instead of 3. That's a confusion that arises quite often. But in your situation it is 3 because ties are not allowed.

Improve this answer
$\endgroup$
1
$\begingroup$

Kendell tau distance is the number of swaps which needs to be done for making the two lists the same. It can also be considered as a variant of Insertion Sort, where each swap adds +1 to Kendell distance.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You don't answer the OP question. What's the correct Kendall's distance between these 2 rankings? $\endgroup$
    – Cohensius
    Mar 31, 2020 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.