使用 Pandas 进行贪婪集覆盖的最快方法是什么？

Question

这道题和贪心集覆盖问题不完全一样，但是思路一致

给定一个 Pandas 数据帧 df1，其一列 df['s'] 由 df2 的一组键组成：

import numpy as np
import pandas as pd
>>> df = pd.DataFrame(np.array([set([1,3,5]), set([1,3,5,6]), set([2,3,4,12]), set([1,3,7]), set([1,15,11]), set([1,16]), set([16])]),columns=['s'])
>>> df
                    s
0      set([1, 3, 5])
1   set([1, 3, 5, 6])
2  set([12, 2, 3, 4])
3      set([1, 3, 7])
4    set([1, 11, 15])
5        set([1, 16])
6           set([16])
        ...

>>> df2 = pd.DataFrame(np.array([[1,2,3,3,3,6,4,8,9,10,11,12,13,14,15,16,5,7],[2.,1.,3.,2.,1.,2.,3.,1.,1.,1.,1.,1.,1.,1.,1.,16.,1.,1.]]).T,columns=['key', 'value'])
>>> df2
    key  value
0     1      2
1     2      1
2     3      3
3     3      2
4     3      1
5     6      2
6     4      3
7     8      1
8     9      1
9    10      1
10   11      1
11   12      1
12   13      1
13   14      1
14   15      1
15   16     16
16    5      1
17    7      1

    ...

上面的数据框 df2 可以包含重复键。我们选择最后一个。例如，为上面的键“3”选择值“1.0”。

我想找到 df['s'] 的前六行，它们可以最大程度地求和它们对应键的值，并根据它们的价值贡献对新数据帧的行进行排序。最快的方法是什么？

对于上面给定的数据集，结果数据框的前两行应该是

df3:
    set([1,16])
    set([12,2,3,4])
    ...

上面第二个不是set([16])，因为"16"已经包含在set([1,16])中了，加上set([16])的值为零。

按集合中键对应值的总和排序。

更新时间：

为了简化这个问题，我们假设 df2 只包含唯一键。并且可以根据安德鲁的技巧轻松修复它。

Answer 1

假设您没有太多键，您可以将集合列表表示为一个稀疏矩阵，每个键有一列。

In [29]: df = pd.DataFrame([{1:1,3:1,5:1}, {1:1,3:1,5:1,6:1}, {2:1,3:1,4:1,12:1}, {1:1,3:1,7:1}, {1:1,15:1,11:1}, {9:1}, {16:1}]).fillna(0)

In [30]: df
Out[30]: 
   1   2   3   4   5   6   7   9   11  12  15  16
0   1   0   1   0   1   0   0   0   0   0   0   0
1   1   0   1   0   1   1   0   0   0   0   0   0
2   0   1   1   1   0   0   0   0   0   1   0   0
3   1   0   1   0   0   0   1   0   0   0   0   0
4   1   0   0   0   0   0   0   0   1   0   1   0
5   0   0   0   0   0   0   0   1   0   0   0   0
6   0   0   0   0   0   0   0   0   0   0   0   1

然后将您的权重表示为系列，按键索引：

In [37]: weights = df2.drop_duplicates('key', keep='last').set_index('key')['value']

然后对你的集合进行加权和求和：

In [40]: totals = (df * weights).sum(axis=1)

In [41]: totals
Out[41]: 
0     4
1     6
2     6
3     4
4     4
5     1
6    16
dtype: float64

然后只找到前 6 行：

In [55]: top6 = totals.order(ascending=False).head(6)

In [56]: top6
Out[56]: 
6    16
2     6
1     6
4     4
3     4
0     4
dtype: float64

您可以使用索引返回稀疏矩阵来恢复这些集合是：

In [58]: df.ix[top6.index]
Out[58]: 
   1   2   3   4   5   6   7   9   11  12  15  16
6   0   0   0   0   0   0   0   0   0   0   0   1
2   0   1   1   1   0   0   0   0   0   1   0   0
1   1   0   1   0   1   1   0   0   0   0   0   0
4   1   0   0   0   0   0   0   0   1   0   1   0
3   1   0   1   0   0   0   1   0   0   0   0   0
0   1   0   1   0   1   0   0   0   0   0   0   0

您可能不喜欢这种方法，但我要指出的是，具有像集合这样的数据结构框架而不是基元，因为元素不是特别 pandas-ish，因此建议对问题进行一些翻译。

使用 Pandas 进行贪婪集覆盖的最快方法是什么？

What is the fastest way to do greedy set cover with Pandas?

python

numpy

set-cover

pandas