Lably
Skip to content

Kendall tau distance

Metric to compare ordering

  • 6 min read
  • 4 chapters

Related on Lably

Through Bubble sort and NumPy

Lab · Class 11Algorithm VisualizerLab · Class 8–12Algorithms & SortingLab · Class 11Python for ML — NumPy, Pandas, scikit-learnLab · Class 11–12Data Cleaning Workshop

Definition

The Kendall tau ranking distance between two lists τ1 and τ2 is Kd(τ1,τ2)=|{(i,j):i<j,[τ1(i)<τ1(j)∧τ2(i)>τ2(j)]∨[τ1(i)>τ1(j)∧τ2(i)<τ2(j)]}|. where τ1(i) and τ2(i) are the rankings of the element i in τ1 and τ2 respectively.

Kd(τ1,τ2) will be equal to 0 if the two lists are identical and 12n(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 Kd(τ1,τ2)=∑{i,j}∈P,i<jK¯i,j(τ1,τ2)

where

  • P is the set of unordered pairs of distinct elements in τ1 and τ2
  • K¯i,j(τ1,τ2) = 0 if i and j are in the same order in τ1 and τ2
  • K¯i,j(τ1,τ2) = 1 if i and j are in the opposite order in τ1 and τ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 Kn is Kd12n(n−1)=2Kdn(n−1) and therefore lies in the interval [0,1].

If Kendall tau distance function is performed as K(L1,L2) instead of K(τ1,τ2) (where τ1 and τ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.

Sign in to keep reading

3 more chapters are free with a Lably account.

More in Statistics

Mortality rateDeaths per 1,000 individuals per yearSystematic reviewComprehensive review of research literature using systematic methodsSensitivity and specificityStatistical measure of a binary classificationLongitudinal studyStudy with repeated observations over timePrevalenceNumber of disease cases in a given population at a specific timeStochasticRandomly determined process