时间戳

首页 > 解决方案 > 找到一组对的最大总重量

python - 找到一组对的最大总重量

问题描述

我有一组记录 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 的对。我以相同的方式继续从更新集中的下一个排名较低的对，直到没有剩下的对。

（抱歉，如果这实际上是此类问题的错误论坛。）

标签： pythonalgorithmmaximize

解决方案

一种方法是从使用基于列-行的模型（如使用数据框）切换到使用图形模型。有几个 python 库可以做到这一点，包括 NetworkX。 https://pypi.org/project/networkx/

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

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

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

推荐阅读