0

この問題はグリーディ セット カバーの問題と完全に同じではありませんが、同じ考えを共有しています。

df2 のキーのセットで構成される 1 つの列 df['s'] を持つ Pandas データフレーム df1 があるとします。

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'] の上位 6 行を見つけ、新しいデータフレームの行を値の寄与度で並べ替えたいと考えています。これを行う最速の方法は何ですか?

上記のデータセットの場合、結果データフレームの最初の 2 行は次のようになります。

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

上の 2 番目は set([16]) ではありません。set([1,16]) には既に "16" が含まれており、set([16]) からの加算値は 0 であるためです。

セットのキーの対応する値の合計によってソートされます。

アップデート：

この問題を簡単にするために、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 に答える