排名聚合算法在少量长列表聚合中的性能比较分析

排名聚合将多个排名列表聚合成一个综合排名列表,可应用于推荐系统、链路预测、元搜索、提案评选等.当前已有工作从不同角度对不同排名聚合算法进行了综述、比较,但存在算法种类较少、数据统计特性不清晰、评价指标不够合理等局限性.不同排名聚合算法在提出时均声称优于已有算法,但是用于比较的方法不同,测试的数据不同,应用的场景不同,因此何种算法最能适应某一任务在很多情况下仍不甚清楚.本文基于Mallows模型,提出一套生成统计特性可控的不同类型的排名列表的算法,使用一个可应用于不同类型排名列表的通用评价指标,介绍9种排名聚合算法以及它们在聚合少量长列表时的表现.结果发现启发式方法虽然简单,但是在排名列表相似度较高、列表相对简单的情况下,能够接近甚至超过一些优化类方法的结果;列表中平局数量的增长会降低聚合排名的一致性并增加波动;列表数量的增加对聚合效果的影响呈现非单调性.整体而言,基于距离优化的分支定界方法 (FAST)优于其他各类算法,在不同类型的排名列表中表现非常稳定,能够很好地完成少量长列表的排名聚合.

Comparison of performance of rank aggregation algorithms in aggregating a small number of long rank lists

Rank aggregation aims to combine multiple rank lists into a single one, which has wide applications in recommender systems, link prediction, metasearch, proposal selection, and so on. Some existing studies have summarized and compared different rank aggregation algorithms. However, most of them cover only a few algorithms, the data used to test algorithms do not have a clear statistical property, and the metric used to quantify the aggregated results has certain limitations. Moreover, different algorithms all claim to be superior to existing ones when proposed, the baseline algorithms, the testing samples, and the application scenario are all different from case to case. Therefore, it is still unclear which algorithm is better for a particular task. Here we review nine rank aggregation algorithms and compare their performances in aggregating a small number of long rank lists. We assume an algorithm to generate different types of rank lists with known statistical properties and cause a more reliable metric to quantify the aggregation results. We find that despite the simplicity of heuristic algorithms, they work pretty well when the rank lists are full and have high similarities. In some cases,they can reach or even surpass the optimization-based algorithms in performance. The number of ties in the list will reduce the quality of the consensus rank and increase fluctuations. The quality of aggregated rank changes non-monotonically with the number of rank lists that need to be combined. Overall, the algorithm FAST outperforms all others in three different rank types, which can sufficiently complete the task of aggregating a small number of long rank lists.