处理Kemeny秩聚合中平局的高效启发式算法

《Operations Research Perspectives》：Efficient heuristics for handling ties in Kemeny rank aggregation

　　

研究人员提出了两种允许平局排名的Kemeny秩聚合（Kemeny rank aggregation）新型启发式算法。针对弱排序搜索空间从严格排序的n!增长至约(1/2)(1/ln2)n+1n!这一组合爆炸挑战，核心方法论贡献在于一种每次仅对小规模对象子集进行操作、同时隐式探索更大平局排名搜索空间并构造含平局共识排序的框架。第一种算法BridgeSubiteration将秩聚合分解为子迭代（subiterations），获取局部最优排序，并通过run-off与bridging模块构造共识排序。第二种算法GreedyReposition引入一种新颖的重定位算子（repositioning operator），系统性生成相邻平局排名并执行局部最优秩调整。基于上述算法，研究人员进一步开发了FUR与SIgFUR的扩展版本。在模拟与真实数据集上的大量计算实验（含消融研究与参数敏感性分析）表明，所提算法在共识排序质量上持续优于现有方法，且在对象数达数千时仍保持计算可行。研究人员给出了n=400对象在普通计算机上半小时内得到共识排序的示例。

研究背景方面，秩聚合（rank aggregation）是社会选择中的核心问题，旨在将多准则下的候选对象排序整合为单一排序。基于序数偏好的距离方法中，Kemeny方法因理论公平性与公理性优势被广泛应用于社会选择、垃圾检测、出行匹配、致癌基因识别、特征选择及自然语言处理等领域。当输入排序不少于4个时，寻找最小化Kemeny距离（Kemeny distance）的共识排序（consensus ranking）是NP难问题。现有方法分精确法、近似法与启发式三类；Badal与Das提出的FUR与SIgFUR借助子迭代收敛（Subiterative Convergence）在严格排序空间高效运行，其R包RankAggSIgFUR可处理n=400对象。然而现实评判中常出现对象间偏好冲突（如A?B与B?A并存），Cook等指出此时弱排序（weak ranking）与平局（ties，记作A～B）更自然。n对象严格排序空间为n!，弱排序空间约为(1/2)(1/ln2)ⁿ⁺¹n!，组合规模剧增使既有严格排序启发式不再直接适用。为此，研究人员开展允许平局的Kemeny秩聚合启发式研究，成果发表于《Operations Research Perspectives》。

关键技术方法上，研究人员构建两类启发式。其一是BridgeSubiteration：将聚合拆为子迭代，在子集上求局部最优，再经run-off（逐步淘汰合并候选层）与bridging（桥接不同子结果中的平局块）组装含平局共识。其二是GreedyReposition：定义重定位算子，对当前平局排序做邻域系统生成，贪心选取使总Kemeny距离下降的调整；并将二者嵌入FUR与SIgFUR形成扩展版。实验采用模拟数据及真实数据队列，开展消融与参数敏感性分析，以Kemeny距离与运行时间为评价指标。

研究结果部分，第一章引言（Introduction）指出Kemeny聚合NP难及严格排序启发式局限，明确平局弱排序空间组合膨胀问题，引出子集操作隐式探索框架。第二章Kemeny秩聚合（Kemeny rank aggregation）形式化定义：基于Kendall得分矩阵a_ij∈{+1,?1,0}，其中i?j取+1、j?i取?1、i～j取0；两排序间Kemeny距离为得分矩阵差异的成对计数。第三、四章分别给出BridgeSubiteration与GreedyReposition构造与伪代码，证明子集局部最优经run-off与bridging可逼近全局含平局共识，重定位算子保证邻域搜索单调不增距离。第五章将新模块嫁接到FUR与SIgFUR，形成tied-ranking扩展。第六章计算实验（含模拟与真实数据、消融、参数分析）显示：扩展FUR/SIgFUR在n达数千时共识Kemeny距离低于原版及QUICK、FAST、DECoR、PSOPR等基线，运行时间仍处可行区；n=400案例普通机器半小时出解。第七章结论指出允许平局的启发式在质量与效率上兼顾，未来可结合参数化惩罚与集成多准则决策框架。

讨论与结论翻译：研究人员得出结论，所提BridgeSubiteration与GreedyReposition及衍生FUR/SIgFUR扩展，在允许输出平局的前提下，以多项式有界的计算代价持续产出更低Kemeny距离的共识排序；run-off与bridging概念及repositioning算子是处理tied ranking搜索空间的有效新机制；该工作填补了已有严格排序启发式不支持弱排序的空白，为大规模对象（n数千）共识排序提供实用路径，并具有在社会选择、机器学习排序融合等场景的推广意义。