从多个局部排名列表重构全局排名列表的算法实践

问题背景：多源局部排名聚合

在许多场景中，我们可能需要从多个来源获取对一组对象的排名信息。例如，在产品评审、内容评级或竞赛评分中，多位评审员（或裁判）可能只评估了部分对象，并对他们所见的子集进行了排名。这些局部排名可能存在以下挑战：

• 部分性： 每个评审员只看到并排名了总对象集中的一部分。
• 重叠性： 不同的评审员可能评估了相同的对象，导致排名数据存在重叠。
• 不一致性： 由于主观性或评审标准差异，不同评审员对同一对象的排名可能不一致，即存在“噪音”。
• 无完整性： 没有单个评审员对所有对象进行了排名。

我们的目标是，在这些限制条件下，综合所有局部排名，生成一个“最佳”的全局排名列表。

考虑一个具体示例：假设有六个物品['a', 'b', 'c', 'd', 'e', 'f']，由四位评委进行评审。每位评委只评审了三个物品，且每个物品至少被两位评委评审过。

items = ['a', 'b', 'c', 'd', 'e', 'f']

# 评委1的排名（从高到低）
j1_rank = ['a', 'c', 'e']
# 评委2的排名（从高到低）
j2_rank = ['b', 'd', 'f']
# 评委3的排名（从高到低）
j3_rank = ['a', 'b', 'c']
# 评委4的排名（从高到低）
j4_rank = ['d', 'e', 'f']

我们的任务是根据这些局部排名，推导出一个全局的、一致的排名列表。

排名聚合算法：基于位置分数的累加

解决这类问题的有效方法是采用基于位置分数的累加策略。其核心思想是为每个评委列表中的对象赋予一个分数，该分数反映其在该列表中的相对位置。然后，将所有评委对同一对象的得分累加起来，最终根据累加总分对所有对象进行排序。

MeDo

无代码AI应用开发，百度秒哒海外版

126

查看详情

算法步骤

1. 分数转换： 对于每个评委的排名列表，将列表中的每个对象转换为一个（对象，分数）对。分数可以根据对象在列表中的位置来确定。例如，如果列表有 N 个对象，排名第一的对象得 N 分，排名第二的对象得 N-1 分，依此类推，排名最后的得 1 分。这种方式确保了排名越靠前的对象获得的分数越高。
2. 分数累加： 初始化一个字典（或哈希表）来存储每个对象的总分数。遍历所有评委的排名列表，对于每个对象，将其在相应评委列表中的分数累加到该对象的总分数中。如果某个评委没有对某个对象进行排名，则该对象在该评委处的分数为零。
3. 全局排序： 根据所有对象的累加总分数进行降序排序。分数最高的对象排在全局列表的最前面。

示例代码实现 (Python)

我们将使用 collections.defaultdict 来方便地累加分数。

from collections import defaultdict

# 初始数据
items = ['a', 'b', 'c', 'd', 'e', 'f']
j1_rank = ['a', 'c', 'e']
j2_rank = ['b', 'd', 'f']
j3_rank = ['a', 'b', 'c']
j4_rank = ['d', 'e', 'f']

# 步骤1: 将每个评委的排名列表转换为字典，赋予位置分数
# 假设列表中的第一个元素排名最高，分数最高
def assign_scores(rank_list):
    """
    将排名列表转换为 (item, score) 字典。
    列表中位置越靠前，得分越高。
    """
    return dict(map(lambda x: (x, len(rank_list) - rank_list.index(x)), rank_list))

j1_scores = assign_scores(j1_rank)  # {'a': 3, 'c': 2, 'e': 1}
j2_scores = assign_scores(j2_rank)  # {'b': 3, 'd': 2, 'f': 1}
j3_scores = assign_scores(j3_rank)  # {'a': 3, 'b': 2, 'c': 1}
j4_scores = assign_scores(j4_rank)  # {'d': 3, 'e': 2, 'f': 1}

# 步骤2: 累加所有对象的总分数
total_scores = defaultdict(int)
all_judge_scores = [j1_scores, j2_scores, j3_scores, j4_scores]

for item in items:
    for judge_score_dict in all_judge_scores:
        total_scores[item] += judge_score_dict.get(item, 0) # 如果评委未排名，则得分为0

# 累加后的分数示例: {'a': 6, 'b': 5, 'c': 3, 'd': 5, 'e': 3, 'f': 2}

# 步骤3: 根据总分数进行降序排序
# 将 defaultdict 转换为普通字典，然后按值降序排序
sorted_items_by_score = dict(sorted(total_scores.items(), key=lambda item: item[1], reverse=True))

# 提取排序后的键作为最终的全局排名列表
global_ranked_list = list(sorted_items_by_score.keys())

print("最终全局排名列表:", global_ranked_list)
# 预期输出: ['a', 'b', 'd', 'c', 'e', 'f'] 或 ['a', 'b', 'c', 'd', 'e', 'f']
# 在本例中，'b'和'd'分数相同，Python的稳定排序会保留原始插入顺序或字典内部顺序。
# 如果需要特定 tie-breaking 规则，则需额外处理。

结果分析

通过上述算法，我们得到了一个综合性的全局排名。在这个示例中，['a', 'b', 'd', 'c', 'e', 'f'] 是一个可能的输出。值得注意的是，如果多个对象获得相同的总分数（例如，本例中 'b' 和 'd' 都获得了 5 分），它们的相对顺序将取决于排序算法的稳定性或后续的 tie-breaking 规则。

注意事项与扩展

1. 分数计算方式： 本教程采用的是简单的线性分数分配（N, N-1, ..., 1）。在某些情况下，可能需要更复杂的评分机制，例如对排名靠前的对象给予指数级更高的分数，以强调顶部的差异。
2. 评委权重： 如果某些评委被认为更具权威性或经验，可以为他们的排名赋予更高的权重。在分数累加阶段，可以将每个评委的分数乘以其对应的权重。
3. Tie-breaking 规则： 当多个对象获得相同的总分数时，可能需要额外的规则来打破平局。例如，可以根据对象被提及的次数、在多少个评委列表中出现过，或者根据某个特定评委的排名来决定最终顺序。
4. 鲁棒性： 这种基于分数累加的方法对“噪音”或不一致的排名具有一定的鲁棒性。单个评委的极端排名不会完全主导全局结果，因为分数会被其他评委的评估所平均。
5. 与简单计数法的区别： 有些人可能会考虑简单地统计每个对象在所有排名列表中出现的次数，然后根据出现次数排序。然而，这种方法忽略了对象在每个列表中的 位置 信息。例如，一个对象在所有列表中都排第一和在所有列表中都排最后，如果简单计数，它们可能获得相同的“出现次数”，但显然其优先级应大相径庭。本教程的方法通过引入位置分数，有效解决了这一问题，确保了排名靠前的对象获得更高的权重。

总结

从多个局部且可能存在分歧的排名列表中重构一个全局排名是一个常见的挑战。本文介绍了一种基于位置分数累加的有效算法，该算法通过为每个局部排名中的对象赋予分数，然后汇总并排序这些分数来生成最终的全局排名。这种方法不仅易于理解和实现，而且能够有效处理数据的不完整性和不一致性，提供了一个相对公平和综合的排名结果。在实际应用中，可以根据具体需求对分数分配和权重机制进行调整，以优化排名结果。

以上就是从多个局部排名列表重构全局排名列表的算法实践的详细内容，更多请关注php中文网其它相关文章！