Abstract:

This paper describes two novel learning algorithms for abrupt change detection in multivariate sensor data streams that can be applied when no explicit models of data distributions before and after the change are available. One of the algorithms, MB-GT, uses average Euclidean distances between pairs of data sets as the decision variable, and the other, MB-CUSUM, is a direct extension of the CUSUM algorithm to the case when the unknown probability density functions are estimated by means of kernel density estimates. The algorithms operate on a sliding memory buffer of the most recent N data readings, and consider all possible splits of that buffer into two contiguous windows before and after the change. Despite the apparent computational complexity of O(N^4) of this computation, our proposed algorithmic solutions exploit the structure present in their respective decision functions and exhibit computational complexity of only O(N^2) and memory requirement of O(N).