在paper 《Effective rank aggregation for metasearching 》中提出了一种rank aggregation的方法:QuadRank,介绍了一种对多个ranked lists进行merge的方法,我们来了解一下:
3.QuadRank
QuadSearch的缺省ranking fusion算法是一个与位置有关(positional)的方法,可以处理partial ranked list;实际上它会处理来自基于single-crawler的搜索引擎们的top-k lists。我们这样做的原因是因为以下普通并且显著的观察:
- i) 所有这些都被experts认为是“major”搜索引擎s
- ii)他们在lifetimes期间是可靠的
- ii)大多数用户和metasearch engines更偏向于他们来执行它们的搜索
假设\(r_1, r_2, \cdots, r_m\)是m个ranked lists,分别对应于每个component搜索引擎。我们假设:这些lists中的每一个list都包含了固定数目的k个items,整个过程涉及到对总共km个elements进行merge和rank。这里我们所采用的merging过程是:通过移除所有重复的elements,将m个不同的result lists合并到一个single list中。注意,该list仍是unranked,直到对list中的所有elements使用scoring函数。
两个component engines间的重合(overlapping)会随着query的不同而不同,不可预测,因此我们假设:我们最终的result list包含了N个items。在表1中我们描述了要使用的符号。
表1
在结尾我们会表述提出方法的主要思想。特别描述了QuadRank所采用的方法论,以便处理individual rankings和zone weighting,并且我们会检查URL分析的结果的意义。最终我们会讨论不同components是如何被组合到单个scoring公式中的。
3.1 处理individual rankings
每个element会接受由component engines得到的ranking,这对于一个rank aggregation方法来说是非常重要的,大多数提出的ranking算法主要基于这些rankings。相应的,我们必须设计我们的函数,来对达到较高rankings的结果进行reward。因此,对比起在更低位置的entries,具有较高rankings的entries可以被认为是:它们会与一个给定query更相关。
因此,对于每个item \(c \in S\),我们引入和评估了该quantity:
\[K(c)=\sum\limits_{i=1}^m (k+1 - r_i(c))\]…(2)
其中:
- m: 表示所使用的component engines的数目
- c: 表示在component list中的单个结果
- k: 在每个component list中的items数目
- \(r_i(c)\)是该item被分配给第i个component engine得到的ranking
在特殊情况下,item c没有被list \(r_i\)进行rank,那么我们假设:\(r_i(c)=k+1\)。很明显,一个item可以接收的最好score是km(如果它在每个component list中都排在第一位),最低的score是1 (表示只被一个component list进行rank,并且排到最后一个)
引入的score会对那些接受了多个component engines的high rankings的items进行reward,然而,两或多个结果被分配相等的K(c)值是相对常见的。例如,考虑到以下场景:两个不同的items \(c_1,c_2\),它们会接收到由4个top-10 lists \(r_1,r_2,r_3,r_4\)的rankings。
表2
在表2的示例中,它会有\(K(c_1)=K(c_2)=10\)。然而,我们会坚定认为:\(c_2\)的rank要比\(c_1\)要高。因为:
- 1.\(c_2\)在更多的input rankings中出现,相应的,根据民主对称性(democratic symmetry) Saari(2000)
- 2.\(c_2\)在超过一半的input rankings中出现,因此根据孔多塞标准(Condorcet criterion),它是一个spam entry的概率很低
为了处理这样的case,我们必须对以下结果进行reward:该结果被尽可能多的component engines认为是与一个给定query相关。如果\(n_c \leq m\)是结果c出现在各component engines的数目,那么我们引入rank-based score,它由以下等式决定:
\[R(c)=m log(n_c K(c))\]…(3)
其中m是所使用engines的总数目。注意(3)中所使用的log是为了减小在\(R_i(c)\)可以接受的不同值之间的误差。另外,尽管使用m乘以log没啥差异(因为m对于所有items是一个常数),它可以根据你的目的进行调节,以便让\(R(c)\) score分配更大的值。