使用Pandas进行分组后加权随机选择

Question

使用Pandas进行分组后加权随机选择

4

我有一个有趣的性能优化问题，它目前是我们应用程序中的瓶颈。

给定一个带有非唯一时间戳索引、id和权重列（事件）的DataFrame，以及时间戳序列（观测值），我必须为每个观测值分配一个随机事件id，该事件在给定时间戳发生，考虑权重。时间戳被夹紧到最近的一分钟，并可以视为从某个起始日期开始的几分钟数。

测试数据生成：

import pandas as pd
import numpy as np
import random

from datetime import datetime as dt, timedelta as td

# typical date range is one month
start = dt(2020, 2, 1, 0, 0, 0)
end = dt(2020, 3, 1, 0, 0, 0)

# generate one event per minute
index = pd.date_range(start, end, freq='1min')
N = len(index)
events = pd.DataFrame({'id': np.arange(N), 'weight': np.random.random(N)}, index=index)

# generate some random events to simulate index duplicates
random_minutes = pd.to_datetime([start + td(minutes=random.randint(0, N)) for m in range(3*N)])
random_events = pd.DataFrame({'id': np.arange(3*N), 'weight': np.random.random(3*N)}, index=random_minutes)
events = pd.concat([events, random_events])

# observations, usually order or two orders of magnitude more records than events
observations = pd.Series([start + td(minutes=random.randint(0, N)) for m in range(10*N)])

样本数据点

>>> print(events.sort_index().to_string())
                     id    weight
2020-02-09 01:00:00   0  0.384927
2020-02-09 01:00:00  15  0.991314
2020-02-09 01:00:00  17  0.098999
2020-02-09 01:01:00   1  0.813859
2020-02-09 01:01:00   2  0.922601
2020-02-09 01:01:00   1  0.738795
2020-02-09 01:02:00   2  0.898842
2020-02-09 01:02:00  13  0.621904
2020-02-09 01:03:00  12  0.075857
2020-02-09 01:03:00   3  0.135762
2020-02-09 01:03:00   9  0.398885
...

>>> print(observations.sort_values().to_string())
12   2020-02-09 01:00:00
9    2020-02-09 01:00:00
44   2020-02-09 01:00:00
31   2020-02-09 01:01:00
53   2020-02-09 01:02:00
3    2020-02-09 01:02:00
6    2020-02-09 01:03:00

我目前使用的最快方案是按索引groupby事件，为每个组返回记住样本的函数。很难正确地将其向量化，因为每个组的记录数量可能会不同，并且我必须根据权重返回ID。

%%timeit

from functools import partial

# create a per-minute random function returning id according to weights
randomizers = events.groupby(level=0).apply(
    lambda s: partial(
        np.random.choice, 
        s.id.values, 
        p=s.weight.values/s.weight.sum()
    )
)

# for each observation, find random generator and call it
selections = randomizers.loc[observations].apply(lambda f: f())

14.7 s ± 49.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

我的问题是，有没有更好、更快的方法来做我需要做的事情？我面临的主要问题如下：

每分钟可能会有多个事件，每个事件都有ID和概率。
每分钟的事件数量是随机的，一分钟可能有1个事件，另一个可能有20个事件。
对于每个观察结果，我需要分别选择一个随机选项。

有什么建议吗？我正在考虑使用Numba，但也许还有一些聪明的解决方案？

- Valar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- luciole75w · Accepted Answer

我可以提出两个建议来提高性能。

首先，在groupby.apply中访问id/weight列会创建新的series，这是很耗费时间的。如果按日期对事件数据进行排序，那么您就可以通过切片原始ndarrays更有效地提取所需的输入。

另一个问题是关于RNG。函数random.choice相当高级，在每次重新计算权重的累积分布函数时，它还显示了一些严重的开销，可能是为了彻底检查输入而不确定。无论如何，如果您将此函数分解成小步骤（cdf、随机数生成、反向cdf、值映射），您就可以保持简单并预计算更多内容，节省一些时间。两种方法都会产生相同的输出，如果RNG使用相同的种子重置（当然要处理相同的输入顺序）。

使用参考代码，我得到与您相同的时间。通过这两个更改，处理速度约快8倍，效果不错。

%%timeit -n 1 -r 5

sevents = events.sort_index()    # ensure that get_loc below will not return a mask (slow)
seiv = sevents.id.values
sewv = sevents.weight.values

def randomizer(t):
    s = sevents.index.get_loc(t[0])    # either a slice (because of sort) or a scalar
    v = seiv[s]

    if isinstance(s, slice):
        w = sewv[s]
        cw = w.cumsum()    # cumulative weight (i.e. cdf)
        cw /= cw[-1]
        return lambda: v[np.searchsorted(cw, np.random.rand() + 1e-35)]    # inverse cdf
    else:
        return lambda: v    # only one event with this time

# create a per-minute random function returning id according to weights
randomizers = sevents.index.unique().to_frame().apply(randomizer, axis='columns', raw=True)

# for each observation, find random generator and call it
selections = randomizers.loc[observations].apply(lambda f: f())

 1.67 s ± 12.4 ms per loop (mean ± std. dev. of 5 runs, 1 loop each)