Change Detection in Multivariate data streams: Online Analysis with Kernel-QuantTree
This addresses the need for reliable change detection in streaming data for applications like monitoring systems, with incremental improvements in controlling false alarms.
The paper tackles the problem of detecting changes in multivariate data streams online by proposing KQT-EWMA, a non-parametric algorithm that controls false alarms with a pre-determined Average Run Length (ARL_0) and achieves detection delays comparable to or lower than state-of-the-art methods.
We present Kernel-QuantTree Exponentially Weighted Moving Average (KQT-EWMA), a non-parametric change-detection algorithm that combines the Kernel-QuantTree (KQT) histogram and the EWMA statistic to monitor multivariate data streams online. The resulting monitoring scheme is very flexible, since histograms can be used to model any stationary distribution, and practical, since the distribution of test statistics does not depend on the distribution of datastream in stationary conditions (non-parametric monitoring). KQT-EWMA enables controlling false alarms by operating at a pre-determined Average Run Length ($ARL_0$), which measures the expected number of stationary samples to be monitored before triggering a false alarm. The latter peculiarity is in contrast with most non-parametric change-detection tests, which rarely can control the $ARL_0$ a priori. Our experiments on synthetic and real-world datasets demonstrate that KQT-EWMA can control $ARL_0$ while achieving detection delays comparable to or lower than state-of-the-art methods designed to work in the same conditions.