找到一组对的最大总重量

Question

我有一组记录 ID 对，对于每一对，这些记录实际上属于彼此的相应概率。每对都是唯一的，但任何给定的 ID 都可能属于多个配对。

例如：

import pandas as pd

df = pd.DataFrame(
    {'ID_1': [1,1,1,2],
    'ID_2': [2,4,3,3],
    'w': [0.5,0.5,0.6,0.7]}
)

df
   ID_1  ID_2    w
0     1     2  0.5
1     1     4  0.5
2     1     3  0.6
3     2     3  0.7

（请注意，由于问题的外部因素，并非每个 ID 都必须分配给每个其他 ID。可以包括这些对并给它们概率 0。）我怎样才能找到每个 ID 分配给另一个 ID 不超过一次的对集（但允许根本不分配一个 ID），以使属于彼此的对的总体可能性最大化。

我要执行此操作的数据框非常大，因此将其设置为最大似然问题似乎有点过头了。我不是计算机科学家，但我认为可能有一种算法可以解决这个问题 - 在 python.

中最佳实现

我现在做的是一种贪婪的方式，这可能不一定会导致最优解。我从排名最高的一对开始。我将其放入最终集合并删除所有涉及该集合中任何 ID 的对。我以相同的方式从更新的集合中继续下一个排名较低的对，直到没有对为止。

（如果这实际上是此类问题的错误论坛，我们深表歉意。）

Answer 1

一种方法是从使用基于数据框的列-行模型切换到使用 Graph 模型。有几个 python 库可以执行此操作，包括 NetworkX。 https://pypi.org/project/networkx/

想法是你的每一对都成为图中的节点，然后为边分配权重。一旦你有了这个数据结构，你就可以获取任何给定的节点并找到最高权重的边。您可以执行各种基于边权重的路径算法。

还有另一个 python 库：https://github.com/pgmpy/pgmpy 它建立在 networkx 上，甚至可以感知概率。它可能更贴近您的需要。

对于这种查询，图形库比尝试使用行-列数据结构更有效。

找到一组对的最大总重量

Find maximum total weight over set of pairs

python

algorithm

maximize