1
\$\begingroup\$

I'm trying to calculate a time weighted average of a feature (feat) based on previous rows by date for a given class. Below is a sample output:

+------------+-------+------+---------------------+
|    date    | class | feat | time_weight_av_feat |
+------------+-------+------+---------------------+
| 11/11/2000 |     2 |    9 |          3.98144991 |
| 10/06/2000 |     2 |    3 |         4.520009579 |
| 17/03/2000 |     2 |    7 |                   2 |
| 01/03/2000 |     2 |    2 |                 NaN |
| 11/07/2000 |     1 |    2 |         2.730337656 |
| 08/05/2000 |     1 |    4 |          2.03150533 |
| 04/03/2000 |     1 |    3 |                   1 |
| 01/01/2000 |     1 |    1 |                 NaN |
+------------+-------+------+---------------------+

time_weight_av_feat is calculated for each row by assigning a time weighted value to each of the previous rows for a given class. These are then multiplied by the feat for that row and summed. This total is this divided by a sum of the time weighted values to produce an average.

My current code is as follows:

import datetime as dt
import pandas as pd
import numpy as np
from tqdm import tqdm

pd.options.mode.chained_assignment = None

df = pd.DataFrame(
    {
        'date': (
            dt.datetime(2000, 1, 1), dt.datetime(2000, 3, 4),
            dt.datetime(2000, 5, 8), dt.datetime(2000, 7, 11),
            dt.datetime(2000, 3, 1), dt.datetime(2000, 3, 17),
            dt.datetime(2000, 6, 10), dt.datetime(2000, 11, 11),
        ),
        'class': (1, 1, 1, 1, 2, 2, 2, 2),
        'feat': (1, 3, 4, 2, 2, 7, 3, 9),
    }
)

df_sorted = df.sort_values("date", ascending=False)
classes = list(pd.unique(df_sorted["class"]))
discount_constant = 0.999
dfs = []
for _, c in enumerate(tqdm(classes), 1):
    df_class = df_sorted[df_sorted["class"] == c]
    df_class.reset_index(drop=True, inplace=True)
    for idx, row in df_class.iterrows():
        df_prev = df_class.iloc[idx + 1:].copy()
        df_prev["days_diff"] = [int((row["date"] - d).days) for d in df_prev["date"]]
        df_prev["time_weight"] = discount_constant ** df_prev["days_diff"]
        sum_time_weight_feat = (df_prev["feat"] * df_prev["time_weight"]).sum()
        sum_time_weight = df_prev["time_weight"].sum()
        df_class.at[idx, "time_weight_av_feat"] = sum_time_weight_feat / sum_time_weight
    dfs.append(df_class)

This works fine. However, if I scale up to a data frame of 1.5m rows:

def random_dates(start, end, n): 

    divide_by = 24*60*60*10**9

    start_u = start.value // divide_by
    end_u = end.value // divide_by

    return pd.to_datetime(np.random.randint(start_u, end_u, n), unit="D") 

num_rows = 15000000
start = pd.to_datetime('1990-01-01')
end = pd.to_datetime('2021-01-01')
dates = random_dates(start, end, num_rows)

classes = np.random.randint(1, 80000, num_rows)
feats = np.random.randint(1, 10, num_rows)

df = pd.DataFrame({'date': dates, "class": classes, "feat": feats})

Then the forecast is 10 hrs+ and I now get a RuntimeWarning.

I've now read enough about replacing for loops with numpy vectorisation to thoroughly confuse myself. Would anyone be able to get me onto the right path?


Edit:

As the answer by Reinderien suggested moving the time_weight_av_feat backwards by one date to avoid the NaNs I thought it would be useful to explain the context of the real use case.

Each of the rows in the data frame is actually a sports match with class being a player ID and feat being a performance metric that was recorded after the match was played. time_weight_av_feat, along with lots of other similar variants is fed into a model that predicts the outcome of the match. As such, it is key that the time_weight_av_feat for a row does not include the feat for that row in its calculation.

If the easiest way to write the code is to move the time_weight_av_feat backwards by one date then this is simple enough to handle as I'll just move all the time_weight_av_feat forward again before submitting them to the predictive model. However, I thought I'd mention it...

\$\endgroup\$
4
  • \$\begingroup\$ for loops and iterrows are the death of Pandas performance. Please comment on the difference between this and the vectorised proposal I offered in my answer to your previous question. \$\endgroup\$
    – Reinderien
    Dec 11, 2021 at 3:27
  • 1
    \$\begingroup\$ Hi again :) The reason for the post is that I made a mistake in my last question. In that question the date differences are calculated between each previous match. I actually need the date differences to be based off the current row (vs each of the previous rows). I've tried having a go at adapting your answer (thank you!) but I think the change is too big for me to re-solution. I've also added in a feat column to more closely replicate my use case... \$\endgroup\$
    – Jossy
    Dec 11, 2021 at 4:04
  • \$\begingroup\$ Why are there NaNs? \$\endgroup\$
    – Reinderien
    Dec 11, 2021 at 4:15
  • \$\begingroup\$ That seems to happen only on the small sample dataset. I think it's because there are no previous matches for those rows so an average for previous rows can't be calculated. In the larger dataset I get a RuntimeWarning for the earliest row by date per class and Pandas sets the average to zero. Not sure why it works differently! \$\endgroup\$
    – Jossy
    Dec 11, 2021 at 4:29

1 Answer 1

1
\$\begingroup\$

I still don't think that your NaNs are appropriate, but since you sound determined: my proposed code includes them.

Importantly: your two loops

for idx, row in df_class.iterrows():

and

[int((row["date"] - d).days) for d in df_prev["date"]]

imply an O(n²) time complexity. There is a mathematically equivalent implementation which is to apply a discrete differential over the date series, and update your sums in O(n) time. Unfortunately I see no easy way to vectorise that part.

The following suggested code shows a simpler and probably faster way to express your geometric weighted expanding mean.

from datetime import datetime
import pandas as pd
import numpy as np

DISCOUNT = 1e-3
ONE_DAY = pd.to_timedelta(1, 'd')


def geomean(df: pd.DataFrame) -> pd.Series:
    # Change the first value in the group's weight from a negative
    # value produced by diff() crossing a group boundary to 0.
    df.weight.iloc[0] = 0
    weight_sum = 0
    feat_sum = 0

    # Target numpy array: same length as the group dataframe; uninitialised
    means = np.empty_like(df.feat.values, dtype=np.float64)
    means[0] = float('NaN')

    # Co-evolve the weight and feature sums based on pre-calculated weights
    # This is an O(n) calculation equivalent to the full-form O(n²) calculation
    # In its current form it will be difficult (impossible?) to vectorise.
    for index, row in enumerate(df.iloc[:-1].itertuples()):
        weight_sum = weight_sum*row.weight + 1
        feat_sum = feat_sum*row.weight + row.feat
        means[index + 1] = feat_sum / weight_sum

    return pd.Series(name='mean', data=means, index=df.index)


def grouped_geomean(df: pd.DataFrame) -> pd.Series:
    sorted = df.sort_values(by=['class', 'date'])

    # Calculate weight based on discrete differential over date column as fractional days
    sorted['weight'] = (1 - DISCOUNT)**(sorted.date.diff() / ONE_DAY)

    # apply() here is non-vectorised. droplevel() is required to drop the outer index
    # which is the class number.
    return sorted.groupby('class').apply(geomean).droplevel(0)


def test() -> None:
    df = pd.DataFrame(
        {
            'date': (
                datetime(2000, 1,  1), datetime(2000,  3,  4),
                datetime(2000, 5,  8), datetime(2000,  7, 11),
                datetime(2000, 3,  1), datetime(2000,  3, 17),
                datetime(2000, 6, 10), datetime(2000, 11, 11),
            ),
            'class': (1, 1, 1, 1, 2, 2, 2, 2),
            'feat':  (1, 3, 4, 2, 2, 7, 3, 9),
        }
    )

    feat_mean = grouped_geomean(df)

    assert np.all(np.isclose(
        feat_mean[1:4], (1.000000, 2.031505, 2.730338),
    ))
    assert np.all(np.isclose(
        feat_mean[5:8], (2.000000, 4.520010, 3.981450),
    ))


if __name__ == '__main__':
    test()
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Ok this is bloody brilliant :) It's reduced the time from 10hrs+ to a little under 2 minutes and given me a heap of understanding about how to use apply() with groupby(). The trick with incrementally summing the weights based on the differences is also really clever. However, there is an issue with the assumption that the NaNs aren't appropriate - I've updated my question to explain why. I'm just trying to work out if the best solution is to leave the code as is and shift everything forward at the end or if I tweak the itertuples for loop... \$\endgroup\$
    – Jossy
    Dec 12, 2021 at 2:18
  • \$\begingroup\$ @Jossy So be it; edited. \$\endgroup\$
    – Reinderien
    Dec 12, 2021 at 4:47
  • \$\begingroup\$ Quick question... if I change the class_ column to be all the same number then the code errors with ValueError: Cannot remove 1 levels from an index with 1 levels: at least one level must be left.. It looks like in this instance grouped_geomean returns a dataframe instead of a series. Any way to force it to return a series? \$\endgroup\$
    – Jossy
    Dec 14, 2021 at 4:46
  • \$\begingroup\$ Also spotted another issue if feat is ever NaN - all the future means are "NaN" :(. There are quite frequently blank fields as there aren't stats for every game. Looks like adding df["feat"] = df["feat"].fillna(0) before the itertuples loop fixes this... \$\endgroup\$
    – Jossy
    Dec 14, 2021 at 5:44
  • \$\begingroup\$ Regarding the one-levels - it's talking about a multi-level index. You can check the index to see if it's multi-level, and if it isn't, don't attempt to drop the outer level. \$\endgroup\$
    – Reinderien
    Dec 14, 2021 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.