0

这个问题与贪心集覆盖问题并不完全相同，但它们的想法相同。

给定一个 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])，因为set([1,16])中已经包含了“16”，从set([16])中添加的值为零。

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

更新：

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

4

1 回答 1

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

您可能不喜欢这种方法，但我会指出具有数据结构的框架，如集合而不是原语，因为元素并不是特别像熊猫，因此建议对问题进行一些翻译。

于 2015-09-15T22:34:40.930 回答