python - 找到最大化正确多数决定数量的预测子集

Question

假设我有一个多类序列预测问题，答案正确:

gold = [1,2,1,0,2,2]

有 N 个模型给出不同的预测:

pred1 = [1,2,2,0,2,2]
pred2 = [2,2,1,1,1,1]
pred3 = [1,2,1,0,2,1]
pred4 = [1,1,0,2,1,2]
pred5 = [2,2,1,0,1,2]

我想找到预测的一个子集(例如 [pred1, pred3, pred5])，这样如果我在每个位置取最常见的项目，正确投票结果的数量就会最大化。

在实际问题中，序列长度>10000，且N>100，有什么高效的方法求子集吗？

目前我只是对子集进行随机抽样，因为我找不到确切的搜索算法(我也不知道它是否存在)。一些启发式方法可以帮助减少计算量，例如删除一致的预测，但不考虑复杂性。

如果不存在有效的答案，我还想找到一个轻松问题的解决方案:即二元预测而不是多类预测，这样最常见的预测就是多数 (>50%) 预测。

(感谢使用 Python/Numpy 原生函数的解决方案)

Answer 1

这个问题好像和"set cover problem"类似，这是 NP 完全的。这意味着您找不到完美、快速的解决方案。

第一步可能是根据它们与目标的接近程度对列表进行排序:

gold = [1,2,1,0,2,2]

preds = [
    [1,2,2,0,2,2],
    [2,2,1,1,1,1],
    [1,2,1,0,2,1],
    [1,1,0,2,1,2],
    [2,2,1,0,1,2]
]

def count_correct(pred, goal=gold):
    return sum(1 for a,b in zip(pred, goal) if a==b)

print(sorted(preds, key=count_correct, reverse=True))
# [[1, 2, 2, 0, 2, 2], [1, 2, 1, 0, 2, 1], [2, 2, 1, 0, 1, 2], [2, 2, 1, 1, 1, 1], [1, 1, 0, 2, 1, 2]]

您还可以计算预测正确的索引，并尝试寻找集合覆盖:

def correct_ids(pred, goal=gold):
    return [i for i,(a,b) in enumerate(zip(pred,goal)) if a==b]
print([correct_ids(pred) for pred in preds])
# [[0, 1, 3, 4, 5], [1, 2], [0, 1, 2, 3, 4], [0, 5], [1, 2, 3, 5]]

请注意，您的问题略有不同，因为不正确的元素在投票过程中发挥了作用。

祝你好运!