3
$\begingroup$

I have two lists of recommendations: that is, two different algorithms have assigned ranks to the same list of objects. I would like to know if they're similar. I specifically care more about recommendations near the top of the list than near the bottom, so e.g. it matters a lot more that item 1 is the same in both lists than that item 427 is the same in both lists. The standard methods I know about (Kendall, Spearman, etc.) all assume that all rankings are equally meaningful, which is just not true.

The most meaningful transformation that comes to mind is taking the ratio of ranks: we can then say e.g. that the two rankings are similar if $0.9 \cdot \text{Rank}_1 < \text{Rank}_2 < 1.1 \cdot \text{Rank}_1$ always (or typically). Is this a well-studied transformation? Can someone suggest statistical properties it would have?

$\endgroup$
  • 2
    $\begingroup$ $Rank_2>0$ and $\alpha>1$, then $Rank_2<\alpha Rank_2$ trivially. Do you mean $Rank_2<\alpha Rank_1$ ? $\endgroup$ – Acccumulation Oct 12 '18 at 23:27
  • $\begingroup$ I corrected the typo, please check $\endgroup$ – kjetil b halvorsen Oct 14 '18 at 12:24
1
$\begingroup$

Some ideas, not really a complete answer. Let $n$ be the number of objects, objects indexed by $i$. I denote the two sets of rankings by $R_1, R_2$, the ranks of object $i$ is then $R_{1i}, R_{2i}$. I will redefine your condition in a more symmetrical way (note that there is a misprint in your inequality, can you correct?): $$ \alpha^{-1} \le \frac{R_1}{R_2}\le \alpha $$ for some $\alpha > 1$. This is equivalent to $\alpha^{-1} \le \frac{R_2}{R_1}\le \alpha$, showing symmetry.

Then you can fix some $\alpha$, for instance your value $\alpha=1.1$ and count up the number of times the condition holds. That is still not a metric, for full equality it equals $n$, so instead you can subtract it from $n$. Maybe that works, you would have to experiment. It is symmetric and zero for full equality, to be a metric you will have to check the triangle inequality. Anyhow this will give more weight to the higher rankings (assuming you assign ranks from 1 upwards to $n$ for the best).

But there are many possibilities. For each $i$, we can find the smallest value of $\alpha$ so that the inequality holds (and then subtract 1), define that as $$ \alpha_i = \max\{\frac{R_{1i}}{R_{2i}}, \frac{R_{2i}}{R_{1i}} \}-1 $$ The smallest possible value of $\alpha_i$ is zero, so for full equality the sum of the $\alpha_i$'s is zero. But, we would probably expect this to be dominated by the lower rankings, so to give larger weights to the upper end, start ranking from the top, so best is ranked 1. Again you would need to experiment.

Generally, rankings can be seen as permutations, so you could look into metrics on permutations. One good account is in chaper 6 of Persi Diaconis: Group Representations in Probability and Statistics. But, as many such metrics cannot be written as a sum over $i$, it is not obvious how to make weighted versions. But Spearman's Rank correlation is one such metric, and it should be possible to make a weighted version of that.

There is many posts here about comparisons of rankings, you could look through this list.

EDIT

Spearman's rank correlation can be seen as Pearson correlation on the ranks of the data, so can be calculated as such. The Pearson correlation (and certainly other correlations) can be generalized to weighted correlation, see Wikipedia. Then you only need to decide on which weight function to use.

For example, say you have ranked $n$ objects and are interested mostly in the top $k$ rankings. Then you could define $$ w_i =\begin{cases} 1, & \max\{R_{1i},R_{2i}\}\ge n-k+1 \\ 0 & \text{other cases} \end{cases} $$ or maybe some smoother version.

And yes, this is certainly not a new problem. R has the function cov.wt which you can use. And Wikipedia: Spearman correlation has the phrase ... should also not be used in cases where the data set is truncated; that is, when the Spearman correlation coefficient is desired for the top X records (whether by pre-change rank or post-change rank, or both), ... showing prior interest! The following papers should interest you: Weighted rank correlation and more sensitive to agreements in top rankings.

$\endgroup$
  • $\begingroup$ Isn't it equivalent to $\alpha \leq \frac {R_2}{R_1} \leq \alpha ^{-1}$? $\endgroup$ – Acccumulation Oct 12 '18 at 23:19
  • $\begingroup$ Well, I said $\alpha > 1$, so your inequality seems impossible ... $\endgroup$ – kjetil b halvorsen Oct 12 '18 at 23:21
  • $\begingroup$ In what condition is my inequality impossible, but $\alpha ^{-1} \leq \frac {R_1}{R_2} \leq \alpha$ is possible? Come to think of it, what does $ \frac {R_1}{R_2}$ even mean? $\endgroup$ – Acccumulation Oct 12 '18 at 23:26
  • $\begingroup$ The indices should be $1i$ etc, the value of rankings for object $i$. $\endgroup$ – kjetil b halvorsen Oct 12 '18 at 23:33
  • 1
    $\begingroup$ The challenge I have with most approaches to comparing rankings is that I'm not interested in "do the two criteria order the items differently" so much as in "will they produce more or less the same top recommendations". While I can't be alone in being interested in that as a criterion, it doesn't seem to be a common thing in statistics. In particular, the permutation approach is almost certainly not the right direction, because I pointedly don't want to have a metric that would be invariant under passing both rankings through the same permutation. $\endgroup$ – Elena Yudovina Oct 14 '18 at 1:29
2
$\begingroup$

I can't comment on the ratio of ranks, but I do know of a method that could help you with your initial problem. The irreproducible discovery rate (IDR) is a statistical method originally created to deal with genomics data. The input is a two different rankings of the same set of objects. In the original case, these were signal peaks from DNA sequencing experiments, but you could put in any two lists of ranks. The algorithm posits two underlying distributions: a correlated one to describe the shared signals at the top of the list and an uncorrelated one to describe the remaining noise. If you see lots of items with low IDR, it indicates there is a substantial correlated component at the top of the list, so maybe you could try this to answer your question.

$\endgroup$
  • $\begingroup$ Thank you! This definitely looks promising, I haven't read the paper in enough details yet to say if it's exactly what I need $\endgroup$ – Elena Yudovina Oct 12 '18 at 21:41

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.