Kendall rank correlation coefficient explained

In statistics, the Kendall rank correlation coefficient, commonly referred to as Kendall's τ coefficient (after the Greek letter τ, tau), is a statistic used to measure the ordinal association between two measured quantities. A τ test is a non-parametric hypothesis test for statistical dependence based on the τ coefficient. It is a measure of rank correlation: the similarity of the orderings of the data when ranked by each of the quantities. It is named after Maurice Kendall, who developed it in 1938,^[1] though Gustav Fechner had proposed a similar measure in the context of time series in 1897.^[2]

Intuitively, the Kendall correlation between two variables will be high when observations have a similar (or identical for a correlation of 1) rank (i.e. relative position label of the observations within the variable: 1st, 2nd, 3rd, etc.) between the two variables, and low when observations have a dissimilar (or fully different for a correlation of −1) rank between the two variables.

Both Kendall's

\tau and Spearman's \rho can be formulated as special cases of a more general correlation coefficient. Its notions of concordance and discordance also appear in other areas of statistics, like the Rand index in cluster analysis.

Definition

Let

(x _{1,y} _{1),} ..., (x _{n,y} _{n)} be a set of observations of the joint random variables X and Y, such that all the values of (x _{i} ) and (y _{i} ) are unique. (See the section

1. Accounting for ties

for ways of handling non-unique values.) Any pair of observations (x _{i,y} _{i)} and (x _{j,y} _{j)} , where i < j , are said to be concordant if the sort order of (x _{i,x} _{j)} and (y _{i,y} _{j)} agrees: that is, if either both x _{i>x} _{j} and y _{i>y} _{j} holds or both x _{i<x} _{j} and y _{i<y} _{j} ; otherwise they are said to be discordant.

The Kendall τ coefficient is defined as:

\tau = (( numberofconcordantpairs ) - ( numberofdiscordantpairs ))/(( numberofpairs )) = 1- (2 ( numberofdiscordantpairs ))/({n \choose 2) } .

where

{n \choose 2 } = {n (n -1 ) \over 2 } is the binomial coefficient for the number of ways to choose two items from n items.

The number of discordant pairs is equal to the inversion number that permutes the y-sequence into the same order as the x-sequence.

Properties

The denominator is the total number of pair combinations, so the coefficient must be in the range −1 ≤ τ ≤ 1.

• If the agreement between the two rankings is perfect (i.e., the two rankings are the same) the coefficient has value 1.
• If the disagreement between the two rankings is perfect (i.e., one ranking is the reverse of the other) the coefficient has value −1.
• If X and Y are independent random variables and not constant, then the expectation of the coefficient is zero.
• An explicit expression for Kendall's rank coefficient is

\tau = (2)/(n(n -1 )) \sum _{i<j} sgn (x _{i-x} _{j)sgn(y} _{i-y} _{j)} .

Hypothesis test

The Kendall rank coefficient is often used as a test statistic in a statistical hypothesis test to establish whether two variables may be regarded as statistically dependent. This test is non-parametric, as it does not rely on any assumptions on the distributions of X or Y or the distribution of (X,Y).

Under the null hypothesis of independence of X and Y, the sampling distribution of τ has an expected value of zero. The precise distribution cannot be characterized in terms of common distributions, but may be calculated exactly for small samples; for larger samples, it is common to use an approximation to the normal distribution, with mean zero and variance $2(2n+5)/9n\; (n-1)$.

Theorem. If the samples are independent, then the variance of $\backslash tau\_A$ is given by $Var[\backslash tau\_A]\; =\; 2(2n+5)/9n\; (n-1)$.

Case of standard normal distributions

If $(x\_1,\; y\_1),\; (x\_2,\; y\_2),\; ...,\; (x\_n,\; y\_n)$ are IID samples from the same jointly normal distribution with a known Pearson correlation coefficient $r$, then the expectation of Kendall rank correlation has a closed-form formula.^[3]

The name is credited to Richard Greiner (1909)^[4] by P. A. P. Moran.^[5]

Accounting for ties

A pair

\{ (x _{i} ,y _{i} ),(x _{j} ,y _{j} ) \} is said to be tied if and only if x _{i} = x _{j} or y _{i} = y _{j} ; a tied pair is neither concordant nor discordant. When tied pairs arise in the data, the coefficient may be modified in a number of ways to keep it in the range [−1,&nbsp;1]:

Tau-a

The Tau-a statistic tests the strength of association of the cross tabulations. Both variables have to be ordinal. Tau-a will not make any adjustment for ties. It is defined as:

\tau _{A} = (n _{c-n} _{d})/(n _{0})

where n_c, n_d and n₀ are defined as in the next section.

Tau-b

The Tau-b statistic, unlike Tau-a, makes adjustments for ties.^[6] Values of Tau-b range from −1 (100% negative association, or perfect inversion) to +1 (100% positive association, or perfect agreement). A value of zero indicates the absence of association.

The Kendall Tau-b coefficient is defined as:

\tau _{B} = (n _{c-n} _{d})/(\sqrt{(n _{0-n} _{1)(n} _{0-n} _{2)}) }

where

\begin{align} n _{0} & = n(n -1 )/ 2 \\ n _{1} & = \sum _{i} t _{i} (t _{i-1)/2} \\ n _{2} & = \sum _{j} u _{j} (u _{j-1)/2} \\ n _{c} & = Numberofconcordantpairs \\ n _{d} & = Numberofdiscordantpairs \\ t _{i} & = Numberoftiedvaluesinthe i ^{th} groupoftiesforthefirstquantity \\ u _{j} & = Numberoftiedvaluesinthe j ^{th} groupoftiesforthesecondquantity \end{align}

A simple algorithm developed in BASIC computes Tau-b coefficient using an alternative formula.^[7]

Be aware that some statistical packages, e.g. SPSS, use alternative formulas for computational efficiency, with double the 'usual' number of concordant and discordant pairs.^[8]

Tau-c

Tau-c (also called Stuart-Kendall Tau-c)^[9] is more suitable than Tau-b for the analysis of data based on non-square (i.e. rectangular) contingency tables.^{[9] [10]} So use Tau-b if the underlying scale of both variables has the same number of possible values (before ranking) and Tau-c if they differ. For instance, one variable might be scored on a 5-point scale (very good, good, average, bad, very bad), whereas the other might be based on a finer 10-point scale.

The Kendall Tau-c coefficient is defined as:^[10]

\tau _{C} = (2 (n _{c-n} _{d)})/(n ^{2} ((m -1 ))/(m)) = \tau _{A} (n -1)/(n) (m)/(m -1)

where

\begin{align} n _{c} & = Numberofconcordantpairs \\ n _{d} & = Numberofdiscordantpairs \\ r & = Numberofrows \\ c & = Numberofcolumns \\ m & = min (r, c) \end{align}

Significance tests

When two quantities are statistically dependent, the distribution of

\tau is not easily characterizable in terms of known distributions. However, for \tau _{A} the following statistic, z _{A} , is approximately distributed as a standard normal when the variables are statistically independent:z _{A} = {n _{c} - n _{d} \over \sqrt{ (1)/(18) v _{0}} }

where

v _{0} = n(n -1 )( 2 n +5 ) .

Thus, to test whether two variables are statistically dependent, one computes

z _{A} , and finds the cumulative probability for a standard normal distribution at - |z _{A|} . For a 2-tailed test, multiply that number by two to obtain the p-value. If the p-value is below a given significance level, one rejects the null hypothesis (at that significance level) that the quantities are statistically independent.

Numerous adjustments should be added to

z _{A} when accounting for ties. The following statistic, z _{B} , has the same distribution as the \tau _{B} distribution, and is again approximately equal to a standard normal distribution when the quantities are statistically independent:z _{B} = {n _{c} - n _{d} \over \sqrt{ v } }

where

\begin{array}{ccl} v & = & (1)/(18) v _{0} - (v _{t} + v _{u)/18} + (v _{1} + v _{2)} \\ v _{0} & = & n (n -1 ) ( 2 n +5 ) \\ v _{t} & = & \sum _{i} t _{i} (t _{i-1)} ( 2 t _{i+5)\\ v} _{u} & = & \sum _{j} u _{j} (u _{j-1)(2} u _{j+5)} \\ v _{1} & = & \sum _{i} t _{i} (t _{i-1)} \sum _{j} u _{j} (u _{j-1)} / ( 2 n(n -1 )) \\ v _{2} & = & \sum _{i} t _{i} (t _{i-1)} (t _{i-2)} \sum _{j} u _{j} (u _{j-1)} (u _{j-2)} / ( 9 n (n -1 ) (n -2 )) \end{array}

This is sometimes referred to as the Mann-Kendall test.^[11]

Algorithms

The direct computation of the numerator

n _{c} - n _{d} , involves two nested iterations, as characterized by the following pseudocode: numer := 0 for i := 2..N do for j := 1..(i − 1) do numer := numer + sign(x[i] − x[j]) × sign(y[i] − y[j]) return numer

Although quick to implement, this algorithm is

O(n ^{2)} in complexity and becomes very slow on large samples. A more sophisticated algorithm^[12] built upon the Merge Sort algorithm can be used to compute the numerator in O(n ⋅ log {n}) time.

Begin by ordering your data points sorting by the first quantity,

x , and secondarily (among ties in x ) by the second quantity, y . With this initial ordering, y is not sorted, and the core of the algorithm consists of computing how many steps a Bubble Sort would take to sort this initial y . An enhanced Merge Sort algorithm, with O(n log n) complexity, can be applied to compute the number of swaps, S(y) , that would be required by a Bubble Sort to sort y _{i} . Then the numerator for \tau is computed as:n _{c-n} _{d} = n _{0} - n _{1} - n _{2} + n _{3} - 2 S(y),

where

n _{3} is computed like n _{1} and n _{2} , but with respect to the joint ties in x and y .

A Merge Sort partitions the data to be sorted,

y into two roughly equal halves, y _{left} and y _{right} , then sorts each half recursive, and then merges the two sorted halves into a fully sorted vector. The number of Bubble Sort swaps is equal to:S(y) = S(y _{left)} + S(y _{right)} + M(Y _{left,Y} _{right)}

where

Y _{left} and Y _{right} are the sorted versions of y _{left} and y _{right} , and M( ⋅ , ⋅ ) characterizes the Bubble Sort swap-equivalent for a merge operation. M( ⋅ , ⋅ ) is computed as depicted in the following pseudo-code:

function M(L[1..n], R[1..m]) is i := 1 j := 1 nSwaps := 0 while i ≤ n and j ≤ m do if R[j] < L[i] then nSwaps := nSwaps + n − i + 1 j := j + 1 else i := i + 1 return nSwapsA side effect of the above steps is that you end up with both a sorted version of

x and a sorted version of y . With these, the factors t _{i} and u _{j} used to compute \tau _{B} are easily obtained in a single linear-time pass through the sorted arrays.

Software Implementations

• R implements the test for

\tau _{B} cor.test(x, y, method = "kendall") in its "stats" package (also cor(x, y, method = "kendall") will work, but the latter does not return the p-value). All three versions of the coefficient are available in the "DescTools" package along with the confidence intervals: KendallTauA(x,y,conf.level=0.95) for \tau _{A} , KendallTauB(x,y,conf.level=0.95) for \tau _{B} , StuartTauC(x,y,conf.level=0.95) for \tau _{C} .

• For Python, the SciPy library implements the computation of

\tau _{B} in scipy.stats.kendalltau

See also

• Correlation
• Kendall tau distance
• Kendall's W
• Spearman's rank correlation coefficient
• Goodman and Kruskal's gamma
• Theil–Sen estimator
• Mann–Whitney U test - it is equivalent to Kendall's tau correlation coefficient if one of the variables is binary.

Further reading

• Book: Abdi, H. . http://www.utdallas.edu/~herve/Abdi-KendallCorrelation2007-pretty.pdf . Kendall rank correlation . N.J. . Salkind . Encyclopedia of Measurement and Statistics . Thousand Oaks (CA) . Sage. 2007 .
• Book: Daniel, Wayne W. . Kendall's tau . Applied Nonparametric Statistics . Boston . PWS-Kent . 2nd . 1990 . 978-0-534-91976-4 . 365–377 . https://books.google.com/books?id=0hPvAAAAMAAJ&pg=PA365 .
• Book: Kendall. Maurice. Gibbons. Jean Dickinson. Jean D. Gibbons. 1990. First published 1948. Rank Correlation Methods. Charles Griffin Book Series. 5th. Oxford. Oxford University Press. 978-0195208375. registration.
• Bonett . Douglas G.. Wright . Thomas A.. 2000. Sample size requirements for estimating Pearson, Kendall, and Spearman correlations. Psychometrika. 65. 1. 23–28. 10.1007/BF02294183. 120558581 .

External links

• Tied rank calculation
• Software for computing Kendall's tau on very large datasets
• Online software: computes Kendall's tau rank correlation

Notes and References

1. Kendall . M. . 1938 . A New Measure of Rank Correlation . . 30 . 1–2 . 81–89 . 10.1093/biomet/30.1-2.81 . 2332226.
2. Kruskal . W. H. . William Kruskal . 1958 . Ordinal Measures of Association . . 53 . 284 . 814–861 . 100941 . 2281954 . 10.2307/2281954.
3. Kendall . M. G. . 1949 . Rank and Product-Moment Correlation . Biometrika . 36 . 1/2 . 177–193 . 10.2307/2332540 . 2332540 . 18132091 . 0006-3444.
4. Richard Greiner, (1909), Ueber das Fehlersystem der Kollektiv-maßlehre, Zeitschrift für Mathematik und Physik, Band 57, B. G. Teubner, Leipzig, pages 121-158, 225-260, 337-373.
5. Moran . P. A. P. . 1948 . Rank Correlation and Product-Moment Correlation . Biometrika . 35 . 1/2 . 203–206 . 10.2307/2332641 . 2332641 . 18867425 . 0006-3444.
6. Book: Agresti, A. . 2010 . Analysis of Ordinal Categorical Data . Second . New York . John Wiley & Sons . 978-0-470-08289-8 .
7. An algorithm and program for calculation of Kendall's rank correlation coefficient. Alfred Brophy. Behavior Research Methods, Instruments, & Computers . 1986 . 18 . 45–46 . 10.3758/BF03200993 . 62601552 .
8. Book: IBM. IBM SPSS Statistics 24 Algorithms. 2016. IBM. 168. 31 August 2017.
9. Berry . K. J. . Johnston . J. E. . Zahran . S. . Mielke . P. W. . 2009 . Stuart's tau measure of effect size for ordinal variables: Some methodological considerations . Behavior Research Methods . 41 . 4 . 1144–1148 . 10.3758/brm.41.4.1144 . 19897822. free.
10. Stuart . A. . 1953 . The Estimation and Comparison of Strengths of Association in Contingency Tables . . 40 . 1–2 . 105–110 . 2333101 . 10.2307/2333101 .
11. Valz . Paul D. . McLeod . A. Ian . Thompson . Mary E. . February 1995 . Cumulant Generating Function and Tail Probability Approximations for Kendall's Score with Tied Rankings . The Annals of Statistics . 23 . 1 . 144–160 . 10.1214/aos/1176324460 . 0090-5364. free .
12. 10.2307/2282833 . Knight . W. . 1966 . A Computer Method for Calculating Kendall's Tau with Ungrouped Data . . 61 . 314 . 436–439 . 2282833.