软件X 21（2023）101319原始软件出版物FLAGR：一个用于排名聚合的灵活的高性能库LeonidasAkrizia，Miltiadis Alamaniotisb，Panayiotis Bozanisaa希腊国际大学科学技术学院，塞萨洛尼基-北14公里。Moudania，Thermi，塞萨洛尼基，希腊b德克萨斯大学圣安东尼奥分校电气与计算机工程系，美国圣安东尼奥ar t i cl e i nf o文章历史记录：2022年11月8日收到2023年1月3日收到修订版，2023年保留字：排名聚合库FLAGRPyFLAGRPythonC++a b st ra ct将多个偏好列表融合为一个具有改进元素排序的聚合列表是一个研究得很好的研究领域，在生物信息学、信息检索、协同过滤和选举系统中有许多应用。尽管存在大量的秩聚集方法，但其中只有一小部分具有公开可用的实现。在本文中，我们介绍FLAGR，一个高性能，模块化，开源库排名聚合。该库包含基线和最先进算法的有效实现，这些算法接收多个排序的偏好列表并输出单个共识排序。我们还介绍了PyFLAGR，这是一个链接到FLAGR核心的库，允许从标准Python程序调用其实现。该软件包还包括一个特殊的工具，可用于评估和比较底层算法的性能。与其他解决方案相比，FLAGR在创建时考虑了灵活性：第三方研究人员和分析人员可以通过仅开发单个函数轻松地将其实现集成到库中这些功能使FLAGR和PyFLAGR成为一个有吸引力的研究平台，用于开发，比较和评估排名聚合算法。随附的用户手册（作为补充材料提供）和支持网站（https://flagr.site中提供了库组件的详细说明和有用的代码示例。版权所有©2023作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本1.0.8用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-22-00366Code Ocean compute capsuleApache许可证，2.0（Apache-2.0）使用git的代码版本控制系统使用C、C++、Python的软件代码语言、工具和服务编译要求，操作环境依赖GCC或MingW。无相关性。如果可用，链接到开发人员文档/手册https://flagr.site/问题支持电子邮件lakritidis@ihu.gr软件元数据当前软件版本1.0.8此版本可执行文件的永久链接https://github.com/lakritidis/flagrApache许可证，2.0（Apache-2.0）计算平台/操作系统Linux，Microsoft Windows安装要求依赖项无依赖项如果可用，请链接到用户手册-如果正式出版，请在参考列表中引用该出版物https://flagr.site和https://github.com/lakritidis/FLAGR/blob/main/docs/FLAGR_manual.pdf问题支持电子邮件lakritidis@ihu.gr*通讯作者。电子邮件地址：lakritidis@ihu.gr（Leonidas Akriovas），Miltos.utsa.edu（Miltiadis Alamaniotis），pbozanis@ihu.gr（PanayiotisBozanis）。https://doi.org/10.1016/j.softx.2023.1013191. 动机和意义从多个排序列表的聚合中发现知识是一个具有重大挑战性的多学科问题2352-7110/©2023作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxLeonidas Akriquis、Miltiadis Alamaniotis和Panayiotis Bozanis软件X 21（2023）1013192∈{q=联系我们秩聚合算法的目标是通过处理多个给定的输入列表来生成改进的输出列表在基因组数据分析、信息检索、推荐系统、协同过滤等众多科学应用中，经常会提出这样的目标，从一组独立的输入列表中创建一个改进的列表的挑战已经引起了众多研究者的关注。尽管这个问题很普遍，但存在的秩聚合库很少。它们中的大多数实现了过时的或简单化的方法，这些方法忽略了问题的重要方面，例如部分重叠的输入列表，和/或不相等的大小，和/或不同的重要性。这些软件包由多个独立的供应商以不同的编程语言构建，不允许研究人员可靠地评估和比较性能。实施方法的管理。作为这些缺点的补救措施，我们引入FLAGR，一个开源的，灵活的和可扩展的库，用于开发和测试- ING排名聚合算法。FLAGR被设计为结合效率、可移植性、可扩展性和平台独立性。从1.0.8版开始，该软件包实现了以下算法：两种线性组合方法：CombSUM和CombMNZ，每种方法都伴随着四种权重归一化技术：Rank，Borda，Score和Z-Score归一化[1]。Borda计数，相当于带Borda标准化的CombSUM [1，2]。三种多数主义方法：孔多塞获胜者[3]，科普兰获胜者[4]和超越方法[5]。Kemeny最优聚合（蛮力实现）。四种方法基于马尔可夫链[6]和[7]中介绍的MCT变体的原理。鲁棒秩聚合[8]。基于偏好关系图的加权方法[9]。第二种加权方法，以非常类似于聚合聚类的方式逐步合并最近的列表[10]。基于距离的加权方法称为DIBRA [11]。DI-BRA可以使用计算的权重不仅用于项目评分，而且用于修剪最弱排名者的偏好列表。最后3个算法被称为加权聚合器。他们应用探索性分析以无监督的方式自动识别专家排名。然后，他们为那些被宣布为专家的人分配更高的权重，从而提高他们提交的元素的分数。据我们所知，这些方法没有公开的实现。关于效率，实现方式利用确保高性能的鲁棒数据结构和算法。例如，聚合列表被实现为具有单独链接的散列表，以支持加速输入列表融合的快速元素搜索这样的选择允许FLAGR被用在要求-ING应用程序，涉及成千上万的非常长的首选项列表。FLAGR采用模块化架构，允许第三方程序员轻松地将自己的方法集成到库中。核心的设计通过仅实现单个功能来促进新算法的开发此函数通过其参数接收所有必要的信息以进行该库是用C++ 11.0开发的，C++ 11.0是科学和工业应用中最流行的编程语言之一。此外，FLAGR公开了一组C函数，允许将其构建为共享（SO）或动态链接库表1一个rank aggregation的例子R1R2R3LmicroSD耳机耳机耳机PowerBankmicroSDPowerBankmicroSD耳机情况情况PowerBank（DLL）。此SO/DLL随后可以导入到用其他语言开发的第三方应用程序中，包括Python，Java，R和PHP。PyFLAGR就是这种情况的一个例子：它链接到上述共享库，并允许从标准Python程序执行FLAGR实现。由于引入的库支持目前最广泛的编程语言，我们希望它们被研究社区广泛采用FLAGR的初始版本已用于支持Quad- Search，这是一个Web元搜索引擎，它从4个主要搜索引擎中提取结果以响应用户查询[12，13]。最近，该库进行了大幅扩展，以实现和评估DIBRA[11]。另一方面，PyFLAGR的创建是为了推广软件，支持Python社区，并将工具物质化，以便轻松使用和比较底层算法实现。这两个库都是在Apache 2许可证下许可的，其中包括允许免费使用，修改和重新分发。2. 软件描述排名聚合应用程序涉及一组查询Q1，q2，. . .，q N以及一组排序器Rr1，r2，. . . ，r m.每个查询q Q被提交给R中的所有排名器，排名器通过返回按重要性或相关性递减顺序排序的偏好项的排名列表来响应。秩聚合算法的目标是合并每个查询的所有偏好列表，发现重要的潜在信息，并生成具有改进的元素排序的单个输出列表L（q）。表1示出了一个示例，其中三个排名者提交他们对假设查询"你为你的智能手机购买哪些配件？''. 请注意，通过电子商务平台购买商品的用户经常会遇到类似的查询;这些答案在推荐系统中得到了广泛的利用。排名聚合方法的目的是处理提交的偏好列表并产生最流行的智能手机配件的排序L在许多情况下，算法必须满足额外的要求，例如处理长度不等的输入列表，缺少元素的列表或不同重要性的排名。FLAGR实施适当的机制，以有效地处理这些情况。2.1. 编译该软件附带两个构建脚本，包括：在Linux上构建FLAGR的典型makefile。make命令自动创建可执行文件FLAGR和共享库flagr.so。用于在Windows上构建FLAGR的批处理文件。与Linux类似，makefile.bat创建可执行文件FLAGR.exe和动态链接库flagr.dll。这两个脚本都需要GCC编译器。所有生成的二进制文件都存储在bin/Release中。···········Leonidas Akriquis、Miltiadis Alamaniotis和Panayiotis Bozanis软件X 21（2023）1013193Fig. 1. FLAGR的低级架构。矩形表示库核心的14个类。四种箭头样式的功能在传奇2.2. 软件构架2.2.1. FLAGR体系结构FLAGR核心包括14个C++类，它们根据图1的架构相互链接。1.一、输入包括一个存储要聚合的偏好列表的文件、一个一个包含每个列表元素的相关性判断的文件（称为Rels文件），以及几个用户定义的值，这些值确定算法超参数、执行模式等。Rels文件是可选的：如果提供，则内置的评估工具通过计算多个度量的值来量化聚合列表质量。输入数据由两个对象管理：InputParams和InputData。第一个存储重要的执行参数，如选定的排名聚合算法，其超参数，输入/输出文件位置等。InputParams几乎对所有FLAGR组件可见，因为它经常需要访问其内容。另一方面，InputData容纳输入首选项列表，这些列表被组织成一个Query对象数组。Query对象维护两个主要组件：第一个是Aggregator，这是一个多用途对象，它：（i）存储具有输入首选项列表（InputList）的数组，（ii）应用所选算法，以及（iii）生成输出聚合列表（称为MergedList）。Query的第二个组件是Evaluator，它是一个对象，可以通过使用用户定义的相关性来计算生成的聚合列表判断（Rels对象）。FLAGR的输出由一个CSV文件组成，该文件存储生成的聚合列表。该库为每个输入查询创建一个聚合列表;因此，如果有Q个查询，FLAGR将生成Q个聚合列表。文件中的每一行都表示按分数降序排序的聚合列表中的一项。如果提供了有效的Rels文件，评估过程将自动进行真的在这种情况下，评估器计算多个评估测量每个聚合列表，并输出第二个CSV文件，在其中写入它们的值。我们请读者参阅第3.1的补充材料，以详细描述文件组织。2.2.2. 共享/动态链接库体系结构FLAGR最强大的功能之一是它能够作为共享库进行编译，允许使用其他编程语言开发的第三方应用程序使用它。尽管这种类型的编译是特定于操作系统的，但在软件包存储库的bin/Release文件夹中有用于Windows（DLL）和Linux（SO）的预编译共享库。一个预编译的DYLIB为MacOS计划为未来版本的FLAGR。FLAGR公开了一组C函数，这些函数包装了原始的C++算法实现，并使它们能够与其他程序链接。它们本质上充当客户端代码可以链接到的动态引用。当一个公开的函数被调用时，它访问FLAGR核心并调用相应算法的实现然后，发生先前描述的过程图2描绘了这种架构。执行驱动程序使公开的功能以统一的方式执行。它的输入包括一个简单的结构，存储用户定义的参数和编排的执行流。最初，它将参数复制到InputParams对象，并调用读取输入数据文件的InputData然后，Driver依次调用InputData的aggregate（）和evaluate（）方法来执行rank aggree。分别对生成的列表进行分析和评估2.2.3. PyFLAGR架构PyFLAGR是一个构建在FLAGR之上的Python包它构成了一个第三方应用程序如何链接到公开的动态引用以访问相应算法实现的示例。所需的SO/DLL文件捆绑在主包中，允许PyFLAGR立即使用，而无需任何其他要求。PyFLAGR是Python存储库索引的成员，可以与pip包管理器：pipinstallpyflagr.该库包括一个名为RAM（秩聚合方法）的基类，以及一个派生类的集合，这些派生类的主要作用是调用FLAGR的各个公开函数。图图3说明了类的层次结构，并演示了它如何适应图2的全局体系结构。RAM执行许多重要操作，包括I/O处理、链接到FLAGR共享库、数据完整性检查等。上述派生类的实现驻留在6个模块中：线性，Majoritarian，MarkovChains，加权，Kemeny和RRA。 每个类通过调用链接共享库的相应公开函数来处理特定的等级聚合方法。注意，一个模块Leonidas Akriquis、Miltiadis Alamaniotis和Panayiotis Bozanis软件X 21（2023）1013194图二. 从第三方应用程序链接到FLAGR的共享/动态链接库。应用程序访问随后由执行驱动程序执行的公开的图3.第三章。将PyFLAGR拟合到图1的架构中。 二、本 质 上 是 一 组 处 理 属 于 同 一 类 别 的 方 法 的 类 例 如 ，Majoritarian模块包括类CondorcetWinners、CopelandWinners和OutrankingApproach，它们依次处理各自的排名聚合方法。此外，PyFLAGR提供了一个名为Comparator的特殊类，它实现了几个用于进行性能比较的工具。其输入包括具有输入首选项的数据文件列表，另一个文件与相关性的判断， 列表元素和一组待比较的秩聚合算法。在对输入数据运行算法之后，类生成各种格式的比较表（例如，CSV、LATEX等）精确度、召回率、平均精确度sion（MAP）[14]、DCG（贴现累积增益）和nDCG（标准化DCG）[15]。2.3. 软件功能2.3.1. 秩聚合引入的库实现了基线和最先进的算法，用于聚合多个偏好列表并生成改进的共识排名。这样的算法目前在生物信息学、推荐系统等领域的各种应用中被利用。这些应用经常涉及大量的数据。因此，代码已针对执行速度和内存消耗进行了仔细优化。2.3.2. 自定义算法实现FLAGR采用模块化结构，允许将新算法集成到核心中。一个名为Cus的特殊文件库编译，无需进一步操作。此外，这些自定义方法存在一个公开的函数，因此FLAGR共享库可以立即访问它们。2.3.3. 业绩评价和比较FLAGR包括一个强大的工具，用于通过计算多个完善的度量值（包括MAP、Precision、Recall、DCG和nDCG）来评估秩评估结果被写入CSV文件，随后可以转换为其他格式，或使用绘图库进行可视化。2.3.4. 结果除了允许在Python程序中使用FLAGR之外 从1.0.8版开始，PyFLAGR为MAP生成条形图，为Precision、Recall、DCG和nDCG生成比较图在内部，PyFLAGR构造了一个存储计算的评估度量的数据框架然后，使用matplotlib对DataFrame中的表格数据进行了说明3. 说明性实例在本节中，我们将展示两个示例，展示PyFLAGR在对秩聚合方法进行比较研究时的有用性这两个示例都利用数据集1，该数据集1包含由电子商店的50个顾客响应于20个给定查询而提交的1000个排序的偏好列表。每个列表包含30个元素（即产品）。为了聚合每个查询的50个首选项列表，tomMethods.cpp包含空函数体，其中pro-语法可以实现新的算法。此文件由相应的FLAGR组件预先导入，从而启用1使用RASDaGen创建，RASDaGen是一个用于排名聚合问题的开源合成数据集生成器https://github.com/lakritidis/RASDaGen。Leonidas Akriquis、Miltiadis Alamaniotis和Panayiotis Bozanis软件X 21（2023）1013195图四、1 9 种 参 与 方 法 实 现 的平均精密度的 比 较 条 形 图 。图五、 所有前5个 列表元素的精度比较条形图。流 行 的 产 品 ， 我 们 引 入 了 19 个 排 名 聚 合 方 法 到 PyFLAGR 的Comparator图图4描绘了实现的MAP [14]的比较条形图19 种参 与方式 。结 果表 明， MC3 实现 了最高 的 MAP ， 其次是DIBRA。此外，Fig. 5表示19个聚合列表的前5个位置处的平均精度值。MC 1和MC 2获得了最高的P@1，而DIBRA和DIBRA-prune在P@3、P@4和P@5方面优于所有其他方法。完 整 的 示 例 以 及 其 他 文 档 位 于 包 存 储 库 的/examples/jupyter/文件夹中。4. 影响根据相关文献，加权算法经常产生更高质量的聚合列表相比，他们的非加权同行。然而，据我们所知，这些技术还没有公开的实现相比之下，FLAGR实现了3个这样的方法[9因此，它的模块化设计，结合具体的评估工具，建立了一个强大的基础，开发和测试新的加权聚合器。Leonidas Akriquis、Miltiadis Alamaniotis和Panayiotis Bozanis软件X 21（2023）1013196可以使用FLAGR研究的其他新研究主题包括基于权重的列表修剪和丢弃。前一个主题检查是否或如何丢弃不太重要的输入列表中排名最低的元素。后者检查在汇总过程中是否应忽略整个低权重输入列表。FLAGR的主要目标之一是建立一个可靠的环境，用于开发和评估秩聚合方法。这一目标通过三个关键要素实现：(i)它的模块化设计，便于新方法的实施和集成，（ii）用于测试目的的众多竞争算法的实施，以及（iii） 它的内置评估工具，为所实施的技术提供准确的性能测量。将FLAGR编译为共享库是增加其影响力的另一个关键步骤。第三方科学和工业应用程序可以链接到该库并执行实现的方法，而无需考虑复杂的理论和实践细节。PyFLAGR构成了这种逻辑的演示。PyFLAGR还包括几个用于测试和比较排名聚合算法的高级工具，它是该领域有吸引力的研究平台。5. 结论本文介绍了FLAGR和PyFLAGR这两个灵活的秩聚合库。前者包括许多最先进算法的高效C++实现，并采用模块化架构，便于集成新方法。此外，具体化的评估工具通过使用多个良好建立的度量（如MAP、Precision、Re-call、DCG和nDCG）来提供所生成的聚合列表的质量测量。FLAGR最强大的特性之一在这种情况下，FLAGR可以由独立的程序导入，以利用现有的实现。另一方面，PyFLAGR是一个将FLAGR的算法实现导入标准Python程序的库具体来说，PyFLAGR链接到上述共享库，并提供对其公开函数的访问。它还包括健壮的可视化工具，可以生成所获得的性能测量的各种图竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作数据可用性代码和一些实验数据通过库的Github存储库公开提供。致谢作者要感谢John Burkardt允许使用ASA 063和ASA 109算法实现计算不完全β积分。附录A. 补充数据与本文相关的补充材料可以在https://doi.org/10.1016/j.softx.2023.101319上找到。引用[1]Renda ME，Straccia U. Web元数据：基于排名与分数的排名聚合方法。2003年 ACM 应 用 计 算 研 讨 会 论 文 集 。 2003 年 ， 第 841-6 页 。http://dx.doi.org/10.1145/952532.952698网站。[2]博尔达海峡关于选举的备忘录。见：1 7 8 1 年 皇 家 科 学 史 。巴黎; 1784年，1784年。[3]孔多 塞湾Essai surl' a p p l i c a t i o n d e l' a n a l y s i s à la pr o b a b i l i t éd e s d é c i s i o n s - Re n d u e s à la p l u r a l i t é d e s v o i x . 1785年巴黎[4]科普兰AH。合理的社会福利功能。Tech.代表，Mimeo，密歇根大学，美国，1951年。[5]放大图片作者：Farah M，Vanderpooten D.信息检索中等级聚合的一种超越方法。在：第30届年度国际ACM SIGIR会议上的研究和信息检索的发展。2007年，第591-8页。http://dx.doi.org/10.1145/1277741.1277843网站。[6] 吴伟杰，王伟杰，王伟杰.网络排名聚合方法第十届万维网国际会议论文集。1999，p.613-22 http://dx.doi.org/10.1145/371920.372165网站。[7][10]张晓文，张晓文. 结合微阵列实验的结果：一种等级聚合方法。Stat ApplGenet Mol Biol 2006;5（1）. http://dx.doi.org/10.2202/1544-6115.1204网站。[8]Kolde R， Laur S，Adler P，Vilo J. Robust rank aggregation for Gene listintegration and meta analysis. Bioinformatics 2012;28（4）：573-80. 网址：//dx.doi.org/10.1093/bioinformatics/btr709网站。[9]Desarkar MS，Sarkar S，Mitra P. Preference relations based unsupervisedrank aggregation for metasynchronous。专家系统应用2016;49：86网址：//dx.doi.org/10.1016/j.eswa.2015.12.005网站。[10]作者：Chatterjee S，Mukhopadhyay A，Bhattacharyya M.群体意见分析的加 权 秩 聚 类 方 法 。 基 于 知 识 的 系 统 2018;149 ： 47-60 。http://dx.doi.org/10.1016/j.knosys.2018.02.005网站。[11]Akriatsu L，Fevgas A，Bozanis P，Manolopoulos Y.基于距离的无监督专家系统应用 2022;202：117435 。http://dx.doi.org/10.1016/j.eswa.2022.117435网站。[12] Akrivel L，Katsaros D，Bozanis P.个性化元数据引擎的有效排名融合方法。收录于：第12届泛希腊信息学会议论文集。IEEE; 2008年，第39-43页。http://dx.doi.org/10.1109/PCI.2008.31。[13] Akrivel L，Katsaros D，Bozanis P.元搜索的有效排名聚合。J Syst Softw2011;84（1）：130-43. http://dx.doi.org/10.1016/j.jss.2010.09.001。[14]放大图片作者：Manning C.信息检索导论。剑桥大学出版社;2008.[15]Järvelin K，Kekäläinen J.基于累积增益的IR技术评估。ACM传输信息系统（TOIS）2002;20（4）：422-46。http://dx.doi.org/10.1145/www.example.com
我的内容管理
展开
