Automatic Change Point Detection

by Nigel Story

Contents

• 1. Introduction
  • 1.1 Challenges of Current Change Point Detection Methods
  • 1.2 Automating the Decisions
• 2. Simulating the Data
• 5. The Full Pipeline
• 6. Results
• 7. Conclusion

1. Introduction

This project introduces a novel approach to change point detection that uses machine learning methods alongside classical analytical approaches to automatically perform time-series change point detection with minimal intervention from the analyst.

1.1 Challenges of Current Change Point Detection Methods

Change point detection is an interesting challenge in machine learning and analytics in that on one hand, it's not that hard to do, but on the other, it's very challenging to automate. Existing methods aren't optimized for enterprise, production, automated settings because they either require a certain amount of foreknowledge of your time-series data or some kind of visual inspection or results to determine where change points occur. Take Facebook Prophet's implementation, which requires you to know things like a range over which to search for change points or a number of change points to detect. Then there are methods like cumulative sum differencing, which requires you to visually inspect a CUMSUM chart to determine where changes occur.

If we can solve the challenges of 1. what constitutes a change and 2. where the changes occur without the intervention of the analyst, then that opens the possibility of automating change point detection models in production systems.

1.2 Automating the Decisions

The cumulative mean differencing approach to change point detection is a straight-forward method where an analyst generates a CUMSUM chart, and the change points are easily visible as spikes or direction changes in the resulting CUMSUM series. By automating the detection of these spikes, we automate the detection of the change points; however the CUMSUM chart is full of spikes large and minute -- what constitutes a significant enough spike to constitute a change?

This is where order optimization comes in: optimizing the window size over which spike detection is deemed significant.

Through the spike detection in the CUMSUM chart and the order optimization, change point detection can be executed without any intervention from an analyst. This is acheived through an automated implementation of the elbow method, the kneedle algorithm. By starting with a small window size, or order, for spike detection, treating the change point segmented data as clusters and plotting their inertias, increasing the order, and repeating, you produce an elbow curve similar to what you would find for conducting an optimization of something like K-Means n_clusters. The kneedle algorithm simply automates the detection of where the elbow occurs.

In K-Means this elbow would occur at the optimal number of clusters; for change point detection it reveals the optimal number of regimes within the time series, which in turn tells us the optimal number of change points and the optimal number of spikes in the CUMSUM chart.

Simulating the Data

To illustrate this algorithm, we'll generate some simple time-series data with NumPy: 5 time series with differing distributions concatenated into a single series.

import numpy as np
from changepoints.change_point_detection import ChangePoints
import matplotlib.pyplot as plt

np.random.rand(42)

ts1 = np.random.random_sample(300)
ts2 = np.random.random_sample(300) + 0.5
ts3 = np.random.random_sample(300) - 0.5
ts4 = np.random.random_sample(300) + 0.3
ts5 = np.random.random_sample(300)

ts = np.concatenate([ts1, ts2, ts3, ts4, ts5])
print(ts.shape)

(1500,)

plt.plot(ts)

[<matplotlib.lines.Line2D at 0x132807d90>]

The Full Pipeline

You can find the full implementation of the algorithm in the changepoints module in this repository, but the high level steps are:

1. Generate the CUMSUM chart
2. Optimize the Order for Spike Detection
3. Extract the change point indeces and regime segments

Notice there is no step requiring the intervention of the user -- this ensures the ability of this implementation to be automated and productionalized.

The API for using the changepoints module intentionally immitates that of Sci-kit Learn: you instantiate the model object, and then run the predict method to obtain results. The difference is that the results are saved as attributes of the ChangePoints object: the change point indeces, the CUMSUM chart, and the optimized order.

Let's execute the model on our synthetic time series dataset.

cp = ChangePoints(ts)
cp.predict()

6. Results

You can see the results on our simulated data below:

cp.change_points

[np.int64(290), np.int64(599), np.int64(899), np.int64(1199)]

cp.plot_change_points()

You can see it's done a good job: the indeces of the change points are indicated by the vertical lines, and the separate regimes of the time series bound by the change points are colorized.

7. Conclusion

This project demonstrates an unsupervised way of detecting change points and regime variation in time-series data in an automated and production-suitable way. It performs strong for change points and regime shifts that are non-monotonic: those where the time-series experiences a directional change. For monotonic changes, such as an increase in slope or trend, these will not present as the "spikes" in the CUMSUM chart and so will not be detected by this algorithm.