Fast Change Point Detection for Electricity Market Analysis

Get this Project:

Fields with * are mandatory

ABSTRACT

Electricity is a vital part of our daily life; therefore it is important to avoid irregularities such as the California Electricity Crisis of 2000 and 2001. In this work, we seek to predict anomalies using advanced machine learning algorithms. These algorithms are effective, but computationally expensive, especially if we plan to apply them on hourly electricity market data covering a number of years.

To address this challenge, we significantly accelerate the computation of the Gaussian Process (GP) for time series data. In the context of a Change Point Detection (CPD) algorithm, we reduce its computational complexity from O(n5) to O(n2). Our efficient algorithm makes it possible to compute the Change Points using the hourly price data from the California Electricity Crisis. By comparing the detected Change Points with known events, we show that the Change Point Detection algorithm is indeed effective in detecting signals preceding major events.

GAUSSIAN PROCESS

Figure 2: Gaussian Process

Figure 2: Gaussian Process

Although GP is computationally expensive, its non-parametric nature and its ability to provide a confidence interval allows it to adapt better to the changes in data than a typical parametric model could, thus yielding superior predictions. Figure 2 illustrates the GP approximating the data and a 95% confidence interval.

BAYESIAN ONLINE CHANGE POINT DETECTION

The Change Point Detection (CPD) is an algorithm that detects changes in sequential data unders the assumption that the sequence data is composed of several runs. A run is best defined as the data of a specific time interval where the data fits a stochastic process without large deviations. In practice, it is not always clear how to split two consecutive runs. More generally, dividing a long sequence of data into runs in a challenging task. CPD algorithms generally work by estimating the length of the run (or run length) at every data point.

SEMI-SEPARABLE MATRICES

In this section, we describe a technique that takes advantage of the algebraic structure in the matrix K in Equation 3 to effectively reduce the cost of solving n Gaussian Processes in O(n) time. When using a GP on a 1-dimensional time series, where xt for each time t is a real number the covariance matrix K in (3), which, here, is based on the Matern function (2), has a special matrix structure. To illustrate, we assume that x1 < x2 < ··· < xn have been arranged in ascending order.

EXPERIMENTAL RESULTS

Figure 5: The time (seconds) used by the two versions of the BOCPD algorithm using GPML and our GPSS

Figure 5: The time (seconds) used by the two versions of the BOCPD algorithm using GPML and our GPSS

Figure 5 shows the time used by the two versions of the BOCPD algorithm. The test runs with different sized samples of the hourly ISO prices from 2008 to 2001. Because the GPML code uses the efficient Matlab built-in functions to solve the linear systems, the BOCPD with GPML actually can handle up to 1000 data points in a reasonable amount of time. From our tests, we see that our implementation with the faster GP can easily handle 10,000 data points even though our algorithm uses interpreted Matlab statements.

CONCLUSION

Figure 7: The ISO prices during 2001 (blue dots) with Gaussian processes from different runs separated by change points (green lines)

Figure 7: The ISO prices during 2001 (blue dots) with Gaussian processes from different runs separated by change points (green lines)

In the discussion of the Gaussian Process, we mentioned that different kernels that could be used. One direction of future work would be explore ways to accelerate Gaussian Processes using a variety of different kernels. The current implementation of the fast Gaussian Process is in Matlab scripts. We plan to rewrite the software in C or C++. This has the potential to speed up the software considerably. Another direction of our work is to incorporate additional information in the change point detection process, which requires us to extend the Gaussian Process to work with multiple dimension time.

Source: University of California
Authors: William Gu | Jaesik Choi | Ming Gu | Horst Simon | Kesheng Wu

Download Project

Get this Project:

Fields with * are mandatory

Leave a Comment

Your email address will not be published. Required fields are marked *