一定要区分全部式列表（full list）和top-k列表

全部元素的列表，ranking mechanism 和rank lists 可以完全等价
top-k 列表并非如此，需要区分ranking mechanism 和rank lists 两个术语。

组合的分类分为三种：分布式， 启发式和随机优化（distributional based, heuristic, and stochastic optimization algorithms）

1 Thurstone’s model

1.1 Full lists

多个列表假设符合多变量正太分布： mean = (u1, u2,...., ut) and 方差为T X T的方差-协方差矩阵
所以每一对列表，都符合二变量正太分布：

image.png

Thurstone's评分对每一对元素：

image.png

1.2 Top-k list

只能获得最显著的一部分数据（在生命领域非常常见），

image.png

从该过程的描述中，可以看出排名列表中的信息以成对的方式使用，导致潜在的信息丢失。 正态性、独立性和单变量方差的假设也可能不切实际。 此外，如果 L 太小，由于频率的概率估计很差，这将不是一个合理的方法。
所以 Thurston 的方法对于许多短列表的问题更合理，因为它最初是为这个设计的。 除了消费者对产品的排名问题外，在生物信息学中，瑟斯顿（Thurstone）的方法可能会找到其应用。 Fishel 等人解决了寻找可重现的真实生物标志物的问题。 可能是这样的一个例子，但需要进一步的研究来探索这个方向。
但是如果示例是少数几个较长列表的类型，则Thurstone的方法不适用。

2 启发式算法（HEURISTIC ALGORITHMS）

包括了Borda 和Markov chain的方法

2.1 Borda法

在 Borda 提出的原始方法中，聚合排名是基于全排名列表的算术平均值计算的。 许多其他聚合函数和修改已经被提出和使用，并且适用于 top-k 列表。 有趣的是，目前一些国家仍在使用Borda方法的变体。

2.1.1 Full list

常用的四种：术平均值（ARM）、中位数（MED）、几何平均值（GEO）、L2范数。

image.png

当p=1时，就为算数平均值
使用Borda评分排名。

2.1.2 Top-k list

首先求出所以list的所有元素作为公共空间。
例如，品尝者 3 的前 3 种口味是 (1, 3, 5)，因此，口味 1、3 和 5 分别获得了 1、2 和 3 的等级。 风味 2（香草）在 S 中，但未被品尝者 3 排名，因此 k3 + 1 = 3 + 1 = 4 的排名分配给风味 2。

2.2 Markov Chain 链

马尔可夫链方法为 Borda 方法提供了一种更优雅但不太直观的替代方法，特别是用于从 top-k 列表中查找聚合排名。另一方面，Borda 的方法整体处理所有排名列表，而基于马尔可夫链的方法仅使用成对排名信息。
为了理解马尔可夫链方法，重要的是要注意关于 top-k 来自的底层空间的假设是至关重要的，因为显然相同的构建马尔可夫链的算法可能会导致不同的结果在不同的假设下。
这个想法是构建遍历马尔可夫链的转移矩阵，使其平稳分布将更大的概率分配给排名更高的状态。 因此，平稳分布将决定项目的总排名。 关于成对排名的信息，即在同一列表中，状态 v 的排名高于状态 u，将用于构建从状态 u 到 v 的转移概率。 根据一个目标，有多种分配这种概率的方法是可能的。

2.2.1 MC1

image.png

MC1：下一个状态是由所有状态的集合统一生成的，所有状态有至少一个基本等级排列为与当前状态一样高。适合top-k列表

2.2.2 MC2

image.png

MC2：下一个状态是由所有状态的集合统一生成的，这些状态至少被基本等级的一半排序为与当前状态一样高（majorityrule natur）。

2.2.3 MC3

image.png

MC3：这种过渡矩阵构造的总体思路是，链条将以某种概率移动到一个状态，该概率与将新状态排列为高于当前状态的列表的数量成正比。
鉴于每种数据类型的独特功能，MC3可能更适合多平台组学问题

3 随机优化法（STOCHASTIC OPTIMIZATION METHODS）

聚合 top-k 列表的优化标准通常基于输入列表和聚合排名之间不一致的一些度量。
一个特别理想的标准是它符合通用的 Kemeny 准则。 符合广义的Kemeny准则的一种宽泛表述是合计排名与输入列表之间的距离的加权和。 因此，一个特定的汇总列表是否比另一个更好，取决于选择的距离度量。 下面，在提出随机优化算法之前，我们详细说明了一类优化标准和距离度量。

3.1 优化标准

通用的 Kemeny 准。

image.png

K（）wei Kendall tau距离。但是实际中，不是这样简单的比较两个列表

image.png

w=（w1,w2,...wl）为权重，这个可以根据SNP排名对其重要性进行加权。

d() 可以是Kendall’s criterion or the Spearman。

3.2 距离的计算

3.2.1 Kendall’s Tau

Full list：

image.png

top-K:

image.png
image.png

3.2.2 Spearman’s Footrule Distance

Full list：

image.png

top-K:

3.3 Stochastic Optimization

因为随机法计算从（2）来看， 会非常花费时间，
可以使用cross entropy Monte Carlo (CEMC)法。
CEMC可以使用多种算法进行相同的任务。根据使用的距离衡量，可以分为the Kendall’s distance
(CEK) or the Superman’s distance (CES)。

Order Explicit Algorithm (OEA）算法，多次运行导致不同的聚合列表具有相同的优化标准值，这意味着存在多种模式，最终选出最优方法。（公式没理解）

image.png

参考综述：
Shili Lin.2010. Rank aggregation methods. https://doi.org/10.1002/wics.111