如何根据时间戳范围和平均组大小最大化对数据帧中的行进行分组？

Question

我有一个数据框：

prod_id                    timestamp1                 timestamp2
1                          2023-12-02                 2023-12-01    
2                          2023-12-05                 2023-12-01    
3                          2023-12-06                 2023-12-01    
4                          2023-12-07                 2023-12-01    
5                          2023-12-08                 2023-12-01
6                          2023-12-08                 2023-12-02
7                          2023-10-10                 2023-09-02
8                          2023-12-11                 2023-12-22 
9                          2023-12-12                 2023-12-24

我想按时间戳范围对 prod_id（创建新参数 group_id）进行分组。 timestamp1 的日期分布不得超过 3 天（因此 group_id 内的 max 和 min 之间的差异不得超过 3 天）。同样，时间戳2的日期分布不得超过3天（因此group_id内的max和min之间的差异不得大于3天）。我需要最大化每个 group_id 的 prod_id 的平均数量。所以这里期望的结果必须是：

prod_id   timestamp1      timestamp2          group_id
1          2023-12-02    2023-12-01               1
2          2023-12-05    2023-12-01               2
3          2023-12-06    2023-12-01               2
4          2023-12-07    2023-12-01               2
5          2023-12-08    2023-12-01               2
6          2023-12-08    2023-12-02               2
7          2023-10-10    2023-09-02               3
8          2023-12-11    2023-12-22               4
9          2023-12-12    2023-12-24               4

正如您所见，prod_id 位于 group_id 2 中，因为它会创建比位于 group_id 1 中更大的 group_id，即使根据条件它可能位于 group_id 1 中。所以这种分组最大化了每个 group_id 的 prod_id 的平均数量。

如何做？我写了这个，但它没有算法最大化每个 group_id 的 prod_id 的平均数量：

df['timestamp1'] = pd.to_datetime(df['timestamp1'])
df['timestamp2'] = pd.to_datetime(df['timestamp2'])
df_sorted = df.sort_values(by=['timestamp1', 'timestamp2'])

group_id = 1
df_sorted['group_id'] = 0

while not df_sorted.empty:
    group_start = df_sorted.iloc[0]
    valid_rows_t1 = df_sorted[(df_sorted['timestamp1'] <= group_start['timestamp1'] + pd.Timedelta(days=30))]
    valid_rows_t2 = valid_rows_t1[(valid_rows_t1['timestamp2'] >= valid_rows_t1['timestamp2'].min()) &
                                  (valid_rows_t1['timestamp2'] <= valid_rows_t1['timestamp2'].min() + pd.Timedelta(days=30))]
    df_sorted.loc[valid_rows_t2.index, 'group_id'] = group_id
    df_sorted = df_sorted.drop(valid_rows_t2.index)
    group_id += 1

这是创建数据框的代码：

# Create the dataframe
data = {
    'prod_id': [1, 2, 3, 4, 5, 6, 7, 8, 9],
    'timestamp1': ['2023-12-02', '2023-12-05', '2023-12-06', '2023-12-07', '2023-12-08', '2023-12-08', '2023-10-10', '2023-12-11', '2023-12-12'],
    'timestamp2': ['2023-12-01', '2023-12-01', '2023-12-01', '2023-12-01', '2023-12-01', '2023-12-02', '2023-09-02', '2023-12-22', '2023-12-24']
}
df = pd.DataFrame(data)

Answer 1

我相信贪婪的解决方案将最小化组的数量，这相当于最小化每组产品的平均数量，因为该平均值等于

P/g

，

P

是产品的总数（无论它们如何分配）到组），

g

是组数。

假设我们给出任意解，其中两个连续组由 g_i 和 g_i+1 给出。这些组由以下产品组成。

g_i = [p_f,...,p_j]

和

g_i+1 = [p_j+1,...,p_k]

假设现在产品 p_j+1 可以移动到组 g_i 并满足该组的日期要求。此外，将该产品移出组 g_i+1 不会违反该组的日期要求。

如果组 g_i+1 仅包含一个乘积 p_j+1，则将该乘积移动到前一组将使组数减少 1，从而改进解决方案；否则，组数将保持不变，因此每组的平均产品数不会改变。

这意味着，只要日期要求允许，将一组中的第一个产品转移到前一组不会使解决方案变得更糟。通过连续执行此操作，直到没有其他产品可以如此移动，我们获得了通过采用贪心算法获得的解决方案：将尽可能多的产品添加到组 1 中，直到日期要求阻止下一个产品 p_j+1不再被添加，此时 p_j+1 成为第 2 组的第一个产品，依此类推。

对于问题中给出的示例，贪婪算法将产生以下结果。

prod_id   timestamp1      timestamp2          group_id
1          2023-12-02    2023-12-01               1
2          2023-12-05    2023-12-01               1
3          2023-12-06    2023-12-01               2
4          2023-12-07    2023-12-01               2
5          2023-12-08    2023-12-01               2
6          2023-12-08    2023-12-02               2
7          2023-10-10    2023-09-02               3
8          2023-12-11    2023-12-22               4
9          2023-12-12    2023-12-24               4

这与问题中给出的“所需解决方案”仅在一个方面有所不同，产品#2 分配给第一组而不是第二组，但两种解决方案每组的产品平均数量相同，

(2+4+1+2)/4 #=> 9/4

与

(1+5+1+2)/4 #=> 9/4

。