Pandemic Data Science —Why Data Scientists need Changepoint Detection
“Some things are so unexpected that no one is prepared for them. “
— Leo Rosten in Rome Wasn’t Burned in a Day
There are many challenges to running a large retail business at any time, but in these largely uncharted times of pandemic, there are a special set of challenges which should dominate the thinking of a data science team working in or with the retail industry.
Demand spikes
One of the key drivers of uncertainty with any significant societal upheaval — and obviously I include a global pandemic in that category — is the surge or collapse in demand for certain items and services. This sudden change in customer or user behaviour can have extreme consequences for any business that is used to operating at a “normal” level of activity. This is especially true if there is a large operational element to a company’s model as in the worlds of retail or logistics.
Retail companies, whether online or in physical stores, have a background operation that has to be resourced with people, stocked with goods and supplied with supporting equipment.
Any significant and unpredicted change to retail demand causes one of two problems:
- Spike demand. Empty shelves, empty warehouses, and long lead times for resupply from an overstretched supply-chain. Employees that are often asked to work large periods of overtime and resources (especially vans and delivery slots) that are fully utilised and not capable of coping with continuing demand.
- Demand drop-off. Over-full warehouses with an increased cost of storage for goods that are not being sold at retail outlets. In food retail, this will also lead to food wastage of expiring products. Employees working in replenishment, restocking and delivery may become under-utilised and then asked to work smaller shifts.
In the UK, during the first lockdown in 2020, supermarkets offering online delivery found that they did not have enough vans and therefore delivery slots to satisfy demand. This caused delivery slots to disappear for many customers for weeks and then months. Some supermarkets were savvy enough to prioritise vulnerable customers. While other supermarkets saw a loss of customers to rival stores that they may never recover.
What can we learn from this
In the event of further lockdowns and disruption, and where there is a perceived shortage of some goods, it is likely that we will see more surges in demand for may product lines (SKUs), e.g. for dry goods like pasta, tinned ingredients, baking ingredients. This variable demand disrupts resourcing of logistics, supply chain and retail operations, which in turn makes configuration of vehicles and people very difficult. It may also challenge downstream manufacturers of goods to provide sufficient capacity even if the goods can be brought to retail locations.
We clearly need techniques that can react to sudden changes quickly. We need to reach into our statistics and data science toolkit to deliver better forecasting models.
Changepoint detection in forecasts
Time series is an often-used method of representing and then analysing forecasting problems. A time series is a time-indexed plot of any data and is used to represent service demand or sales of a given product over time. A forecast of demand represents an informed guess as to how the demand curve will continue past the present day; as in the plot below of monthly air passengers between 1948 and 1962. (Box et al., 1976)
Most commercial forecasting is based on a combination of historical data— often seasonally adjusted — and data about anticipated or planned events. Thus the demand for barbecues might be modelled on historical sales to pick up that there are high sales in the summer, along with meteorological data to try and anticipate sunny barbecue-friendly weather, and a list of national holidays.
A changepoint describes a point in time when a change occurred to a statistical feature of the time series — that might be a change in the mean, invariance (noise) or in trend. For example, if the electricity usage from a small factory drops from 152kW to 96kW in the space of a few seconds at 3.10 pm, we might call that a changepoint in the electricity demand at that time.
The series below displays a significant mean jump at time 30.
The beauty of changepoints is that there does not have to be any knowledge of the underlying reason for the change — it is literally the identification that a change has happened for whatever reason. That does not mean to say that we cannot more closely focus on particular time ranges to identify possible changepoints, it just means that we do not have to be aware of all the operational complexity in a company in order to be able to identify one.
Forecasting algorithms will often rely heavily on time series data as input, to be able to produce their forecast. If a forecasting algorithm is not expecting large jumps in its historical input data, and some algorithms cope with this very poorly, then it can drive large error in the forecast. This error can last for many days or weeks before the changepoint is eventually smoothed out and accounted for by the algorithm.
Opportunity
Forecasting techniques which can spot changepoints as they occur in their historical input data are able to react more swiftly to those changes and produce dramatically better results, i.e. a forecast with a lower forecast error compared to a moving average forecast which relies on a sliding window of historical values.
There are many changepoint detection techniques out there — and I will list some for you — that have differing ability to accurately recognise when demand disruptions are occurring and allow servicing of that demand.
- Binary Segmentation (Edwards and Cavalli-Sforza), works with a process of successive division and exploration of the time series until no further changepoints that pass the statistic test emerge. It is an approximate algorithm — it does not explore all of the possible changepoints. However, it is quick with complexity O(n log n) for a time series of length n.
- Segment neighbourhood (Auger and Lawrence), uses dynamic programming iteratively to identify successive changepoints. It is an exact algorithm in that all changepoints are explored but there is a computational penalty — it having complexity O(2^n) or O(C n^2) if the number of changepoints searched for is constrained.
- PELT (Killick et al., 2012), is an online algorithm — meaning it can be used on streamed time series data. It also uses dynamic programming but has linear complexity, O(n), so long as the number of changepoints in a time series increases only linearly with the size of the time series data.
The online nature of PELT is an important distinction from the traditional approaches. The ability to run as part of a streamed data architecture is very useful when trying to make decisions in near real-time. The Binary Segmentation and Segmentation Neighbourhood approaches are suited to a batch processing model after a window of time has elapsed, which is very appropriate for retrospective analysis.
Benefits
The exact benefit case for using modern approaches in forecasting — often in combination with neural networks, decision trees or moving average approaches — will depend on the industrial use case and the nature of the operation being run.
Broadly, though, the difference between a slow-reacting moving-average style forecast and one that has an integrated changepoint detection technique might mean as much as 40–50% in terms of sales revenue for a retail operation or 10–20% in terms of quality failure (items that exceed time-taken-to-deliver threshold) for delivery of goods, for a given forecasting window. It can be that dramatic.
In both cases rolling disruption cannot be ruled out and that can be the cause of severe disruption even when the demand curve has settled down
Summary
The forecast is not the whole story of course. A good forecast needs to be plumbed into a responsive operational decision process in order to make good use of the benefits of increased forecast accuracy.
Many businesses realise they have risk exposure in their business forecast models. Typically, they respond to uncertainty and previously-observed forecast error with excess capacity — either in storage space for extra goods or in expensive assets for processing those demand spikes. In many cases, this can be achieved more efficiently by making use of a more accurate forecast that adjusts to the new normality of a post-changepoint world quickly.
About the author
Dr. Jeremy Bradley, previously Associate Professor of Computer Science at Imperial College London and is currently Chief Data Scientist at DataSparQ. He also co-hosts the DataCafé data science podcast with his friend Dr. Jason Byrne. If you would like to know more about how this or further cutting-edge research can impact your operation directly then do get in touch. We would be happy to share our learnings and see if we can help.
References
- Podcast: Bradley, J.T. and Byrne, J. “Changepoint Detection: Secret Weapon of the Data Scientist.” DataCafé 2020.
- Changepoints Overview Paper: Killick, R. and Eckley, I.E. “changepoint: An R package for changepoint analysis” (pdf via ResearchGate)
- Paper: Box, G.E.P., Jenkins, G.M., and Reinsel, G.C. (1976) “Time Series Analysis, Forecasting and Control.” Third Edition. Holden-Day. Series G
- Paper: Auger, I.E., Lawrence, C.E. (1989). “Algorithms for the Optimal Identification of Segment Neighborhoods.” Bulletin of Mathematical Biology, 51(1), 39–54.
- Paper: Edwards, A.W.F., Cavalli-Sforza, L.L. (1965). “A Method for Cluster Analysis.” Biometrics, 21(2), 362–375.
- Paper: Killick, R., Fearnhead, P., Eckley, I.A. (2012). “Optimal Detection of Changepoints with a Linear Computational Cost.” Journal of the American Statistical Association, 107(500), 1590–1598.
- R Package: changepoint: Methods for Changepoint Detection (R package via CRAN library)
- PELT algorithm paper: Killick, R., Fearnhead, P. and Eckley, I.A. “Optimal detection of changepoints with a linear computational cost”, October, 2012. (pdf via arXiv)
- Paper: Beaulieu, C., Killick, R. “Distinguishing Trends and Shifts from Memory in Climate Data” J. Climate (2018) 31 (23): 9519–9543 (paper via American Meteorological Society)
- R Package: EnvCpt: Detection of Structural Changes in Climate and Environment Time Series (R package via CRAN library)
