Nonparametric and Online Change Detection in Multivariate Datastreams using QuantTree
This addresses the problem of reliable change detection for applications requiring controlled false alarms, but it is incremental as it builds on existing nonparametric and EWMA approaches.
The paper tackles online change detection in multivariate datastreams by introducing QT-EWMA and QT-EWMA-update, nonparametric algorithms that control false alarm rates and achieve lower or comparable detection delays compared to state-of-the-art methods.
We address the problem of online change detection in multivariate datastreams, and we introduce QuantTree Exponentially Weighted Moving Average (QT-EWMA), a nonparametric change-detection algorithm that can control the expected time before a false alarm, yielding a desired Average Run Length (ARL$_0$). Controlling false alarms is crucial in many applications and is rarely guaranteed by online change-detection algorithms that can monitor multivariate datastreams without knowing the data distribution. Like many change-detection algorithms, QT-EWMA builds a model of the data distribution, in our case a QuantTree histogram, from a stationary training set. To monitor datastreams even when the training set is extremely small, we propose QT-EWMA-update, which incrementally updates the QuantTree histogram during monitoring, always keeping the ARL$_0$ under control. Our experiments, performed on synthetic and real-world datastreams, demonstrate that QT-EWMA and QT-EWMA-update control the ARL$_0$ and the false alarm rate better than state-of-the-art methods operating in similar conditions, achieving lower or comparable detection delays.