4
$\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?

$\endgroup$
  • 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 '15 at 20:47
5
$\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
$\endgroup$
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.

$\endgroup$
1
$\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
$\endgroup$
  • 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 '18 at 14:37
  • 1
    $\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 '18 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 '18 at 19:47
  • 1
    $\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 '18 at 16:24
0
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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