The Kendall tau distance or Kendall tau rank distance is a metric (distance function) that counts the number of pairwise disagreements between two ranking 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 take to place one list in the same order as the other list. The Kendall tau distance was created by Maurice Kendall.
Definition The Kendall tau ranking distance between two lists τ 1 {\displaystyle \tau _{1}} and τ 2 {\displaystyle \tau _{2}} is
K d ( τ 1 , τ 2 ) = | { ( i , j ) : i < j , [ τ 1 ( i ) < τ 1 ( j ) ∧ τ 2 ( i ) > τ 2 ( j ) ] ∨ [ τ 1 ( i ) > τ 1 ( j ) ∧ τ 2 ( i ) < τ 2 ( j ) ] } | . {\displaystyle K_{d}(\tau _{1},\tau _{2})=|\{(i,j):i<j,[\tau _{1}(i)<\tau _{1}(j)\wedge \tau _{2}(i)>\tau _{2}(j)]\vee [\tau _{1}(i)>\tau _{1}(j)\wedge \tau _{2}(i)<\tau _{2}(j)]\}|.}
where τ 1 ( i ) {\displaystyle \tau _{1}(i)} and τ 2 ( i ) {\displaystyle \tau _{2}(i)} are the rankings of the element i {\displaystyle i} in τ 1 {\displaystyle \tau _{1}} and τ 2 {\displaystyle \tau _{2}} respectively.
K d ( τ 1 , τ 2 ) {\displaystyle K_{d}(\tau _{1},\tau _{2})} will be equal to 0 if the two lists are identical and 1 2 n ( n − 1 ) {\textstyle {\frac {1}{2}}n(n-1)} (where n {\displaystyle n} is the list size) if one list is the reverse of the other. Kendall tau distance may also be defined as
K d ( τ 1 , τ 2 ) = ∑ { i , j } ∈ P , i < j K ¯ i , j ( τ 1 , τ 2 ) {\displaystyle K_{d}(\tau _{1},\tau _{2})=\sum _{\{i,j\}\in P,i<j}{\bar {K}}_{i,j}(\tau _{1},\tau _{2})}
where
P is the set of unordered pairs of distinct elements in τ 1 {\displaystyle \tau _{1}} and τ 2 {\displaystyle \tau _{2}}
K ¯ i , j ( τ 1 , τ 2 ) {\displaystyle {\bar {K}}_{i,j}(\tau _{1},\tau _{2})} = 0 if i and j are in the same order in τ 1 {\displaystyle \tau _{1}} and τ 2 {\displaystyle \tau _{2}}
… excerpt ends here. Continue reading the full article.
