Rank Correlation
a rank correlation is a measure of relationship
- between different rankings of the same variable
- of between two rankings of different ordinal variables
Intuition
Two variables case:
- $X$ - basketball ranking of college teams
- $Y$ - football ranking of college teams
- is there a correlation between $X$ and $Y$?
- e.g. do colleges with good football ranks tend to have good basketball ranks?
One variable case:
- $X$ - football matches ranked by coaches
- $Y$ - football matches ranked by sportswriters
- are these rankings similar?
Correlation Coefficient
- A rank correlation coefficient shows the degree of similarity between two rankings
- so we want to calculate the distances between two rank vectors
One Variable Case
Problem
let $X = \{A, B, C, D, E \}$ - be a set of 5 objects
want to compare
- observed ranking $r(X): [E, B, A, C, D]$
- predicted ranking $r^*(X): [B, E, C, D, A]$
- need to be able to compute distance $d(r, r^*)$ between them
Running Example
|
1 |
2 |
3 |
4 |
5
|
$r$
|
$B$ |
$A$ |
$C$ |
$D$ |
$E$
|
$r^*$
|
$E$ |
$C$ |
$D$ |
$A$ |
$B$
|
given $X = \{ x_1, ..., x_N \}$
- $d_{SF}(r, r^*) = \sum_{i=1}^{N} \big| r(x_i) - r^*(x_i) \big|$
- not normalized: $d_{SF}(r, r^*) \in [0, +\infty)$
- similar to the Manhattan distance
Example:
- $d_{SF}(r, r^*) = |1 - 2| + |2 - 1| + |3 - 5| + |4 - 3| + |5 - 4| = 1 + 1 + 2 + 1 + 1 = 6$
Spearman Distance
given $X = \{ x_1, ..., x_N \}$
- $d_{S}(r, r^*) = \sum_{i=1}^{N} \big( r(x_i) - r^*(x_i) \big)^2$
- also not normalized: $d_{SF}(r, r^*) \in [0, +\infty)$
Example:
- $d_{SF}(r, r^*) = |1 - 2|^2 + |2 - 1|^2 + |3 - 5|^2 + |4 - 3|^2 + |5 - 4|^2 = 1 + 1 + 4 + 1 + 1 = 8$
Spearman's $\rho$ (Rank Correlation Coefficient)
given $X = \{ x_1, ..., x_N \}$
- $\rho_S(r, r^*) = 1 - \cfrac{6 \cdot d_S(r, r^*)}{N \cdot (N^2 - 1)}$
- normalized: $\rho_S(r, r^*) \in [-1, 1]$
- $\rho_S(r, r^*) = 1$ - identical
- $\rho_S(r, r^*) = -1$ - inverse
Example:
- $\rho_S(r, r^*) = 1 - \cfrac{6 \cdot 5}{5 \cdot (5^2 - 1)} = 0.6$
Kendall's Distance
It counts the pair-wise disagreement between two ranking lists, i.e. Inversion Count
- $d_K(r, r^*) = \Big| \big\{ (x_i, x_j) | r(x_i) < r(x_j) \land r^*(x_i) > r^*(x_j) \big\} \Big|$
- so it's the # of item pairs that are inverted in the $r$ compared to $r^*$,
- also, the ranking can be partial
- and it's not normalized
Example:
- $d_K(r, r^*) = (1+0+0+0)+(0+0+0)+(1+1)+(0)=3$
Kendall's $\tau$
It normalizes the Kendall's Distance
- $\tau_K(r, r^*) = 1 - \cfrac{4 \cdot d_k(r, r^*)}{N \cdot (N - 1)}$
- $\tau_K(r, r^*) \in [-1, 1]$
Example:
- $\tau_K(r, r^*) = 1 - \cfrac{4 \cdot 3}{5 \cdot (5 - 1)} = 0.4$
Gamma Coefficient
$\Gamma$ coefficient is based on the # of correct and incorrect rankings
- "correct":
- $d^+(r, r^*) = \big| \big\{ (x_i, x_j) \ | \ r(x_i) < r(x_j) \land r^*(x_i) < r^*(x_j) \big\} \big|$
- the number of items at the same relative position in raking
- "inverted" (as in Kendall's $\tau$)
- $d^-(r, r^*) = \big| \big\{ (x_i, x_j) \ | \ r(x_i) < r(x_j) \land r^*(x_i) > r^*(x_j) \big\} \big|$
- the number of inversions
- $\Gamma(r, r^*) = \cfrac{d^+(r, r^*) - d^-(r, r^*)}{d^+(r, r^*) + d^-(r, r^*)}$
- $\Gamma(r, r^*) \in [-1, 1]$
- it's equal to $\tau_K(r, r^*)$ if the rankings are total
Weighted Methods
The previous measures gave equal importance to all ranking positions
- i.e. differences in the first ranking positions have the same effect as for the last positions
- in many cases the closer position is to the beginning, the more important it is
- e.g. when we want to show only first 5 items, the rest after 5 are not important
Solution
- assign weight proportional to the importance
- if position is important, may assign weight s.t. they decrease with the ranking position
- $d_S(r, r^*) = \sum_{i = 1}^N w_i \cdot \big( r(x_i) - r^*(x_i) \big)^2$ with
- $w_i = \cfrac{1}{\log r(x_i) + 1}$
Can also use Multi-Criteria Decision Aid for that
- e.g. Concordance Index from ELECTRE
Links
Sources