2
$\begingroup$

I am interested in comparing ranked lists in order to find elements that are differently ranked. Suppose we have 10 lists, each ranked (and for simplicity assuming the elements overlap and only the ranking was different). What method could I apply to find elements with high ranks in list1 that consistently have low(er) ranks in all the other lists?

The background here is that each of these lists represent outputs from differential testings from experiments that cannot be directly compared to each other as confounders exist between them that are nested with the effect we want to compare. Hence, I would like to at least prioritize elements that in the given reference list ranked highly (and therefore were very significant or "important" in experiment1), but have low(er) ranks in all other experiments, suggesting that this element was "unique" to experiment 1, meriting downstream experiments with these elements.

For elements consistently ranked highly I would use RobustRankAggregation or the Rank Product calculation, but what about actually finding differences in ranked lists? Obviously one could simply take the topX elements from list 1 and calculate something like the variance for their ranks across the other lists, but I am hoping for a method that is more sophisticated. If possible links to respective implementations/packages in R would be appreciated.

$\endgroup$

2 Answers 2

1
$\begingroup$

One possible way to approach your problem is as follows: For each element, collect all the ranks that it has in all your lists, i.e., if you have $n$ lists, $m$ elements, and the rank of an element $e_i$ in list $l_k$ is $r_k(e_i)$, then the rank collection $c_i$ of an element $e_i$ is: $$ c_i := (r_1(e_i), r_2(e_i), \ldots, r_n(e_i)), \quad i=1,\ldots, m. $$

Now you are trying to find the elements $e_i$ for which there is a list $l_k$ such that $r_k(e_i)$ is consistently different from the ranks $r_s(e_i)$ of $e_i$ in the other lists $l_k, s\ne k$. This can be understood as finding an outlier in the collection $c_i$.

In general, there are many methods for finding outliers $x$ in a set $X$ and most of them assign an outlier score $os(x)$ to each $x\in X$ which is supposed to describe the amount of "outlier-ness". And the most outlying $x\in X$ is then the $x$ with the maximum outlier score. So you could assign to each element $e_i$ the maximum outlier score $mos(e_i)$ of all the ranks in $c_i$: $$ mos(e_i) := max_k\{os(r_k(e_i))\}. $$ Then, all that is left to do is to find the elements $e_i$ with the largest value of $mos(e_i)$.

You mentioned that you want to find the elements $e_i$ which are not only differently ranked in one list compared to the other lists, but also that this outlying rank is higher than that in the other lists. If this is the case, you could simply append a filter to the outlier detection which would make sure that this is indeed the case.

Back to the outlier detection and available algorithms: Many methods are possible. E.g. you could take as outlier score the z-score, the distance of a rank $r_k(e_i)$ to the mean $\mu_i := mean(c_i)$ divided by the standard deviation $\sigma_i := sd(c_i)$: $$ os_z(r_k(e_i)) := \frac{|r_k(e_i) - \mu_i|}{\sigma_i}. $$

Other outlier detection methods with implementations in R are e.g. kNN or isolation forest. Of course, if you are willing to consider python libraries, too, there is a whole collection here. Most of those are, however, overkill, given that you have only about ten lists.

$\endgroup$
2
  • $\begingroup$ This is a very clearly presented algorithm for outlier detection among the ranks for any given item in the ranked list. My only concern is that this assumes that the rankings themselves would be normally distributed (thus justifying use of a z-score outlier detection method). But, on the face, I'm not sure this is justifiable. If one item is ranked highest by most, this means you might have a set like {1, 1, ..., 1, 2}. In this case, that one 2nd ranking would have a z score of 2.8...but ¿is it an outlier? $\endgroup$
    – Gregg H
    Commented Apr 2, 2022 at 17:52
  • $\begingroup$ @GreggH I don't have to assume Gaussian distribution for any of the methods I have suggested. And measuring the distance from the mean in units of the standard deviation is a very commonly used method independent of the type of the distribution. Also, the advantage of outlier scores is that this gives the user a numeric measure and the user can then decide, using domain knowledge, what thresholds to use. Scores are always better than binary decisions. $\endgroup$
    – frank
    Commented Apr 2, 2022 at 18:59
1
$\begingroup$

My suggestion is to first confirm that there is indeed a difference in the ranking between two lists. This could be accomplished using something like Cohen's kappa-coefficient (though I would suggest a weighted kappa). This is essentially asking to build a contingency table with the items and their paired rankings. Then, this contingency table is assessed for something like an inter-rater reliability.

If you confirm that the rankings are substantively different, then you can asked which items are truly being ranked differently simply by looking at how far the items are from the diagonal of the contingency table.

Next, if you wish to do a pairwise comparison for each of your 10 rankings or so (this is probably reasonable for a relatively small number like this), you can build a list of how often and how far away from the diagonal any one item is for each of the possible pairings...but I would only use those that indicated reasonable differences for the rankings.

For packages to help with this, the psych package in R has a function for kappa calculations.

Happy to clarify as needed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.