Many modern applications of online changepoint detection require the ability to process high-frequency observations, sometimes with limited available computational resources. Online algorithms for detecting a change in mean often involve using a moving window, or specifying the expected size of change. Such choices affect which changes the algorithms have most power to detect. We introduce an algorithm, Functional Online CuSUM (FOCuS), which is equivalent to running these earlier methods simultaneously for all sizes of window, or all possible values for the size of change. Our theoretical results give tight bounds on the expected computational cost per iteration of FOCuS, with this being logarithmic in the number of observations. We show how FOCuS can be applied to a number of different change in mean scenarios, and demonstrate its practical utility through its state-of-the art performance at detecting anomalous behaviour in computer server data.
翻译:在线变更点探测的许多现代应用要求有能力处理高频观测,有时是有限的计算资源。检测平均值变化的在线算法往往涉及使用移动窗口,或说明预期变化的规模。这种选择影响到改变算法最能检测到的。我们引入了算法,即功能在线 CUSUM(FOCUS),这相当于对所有大小窗口同时运行这些早期方法,或所有可能的改变规模值。我们的理论结果对FOCuS的迭代的预期计算成本作了严格限制,因为观察数量中存在对数。我们展示了FOCUS如何应用到平均情景中的若干不同变化,并通过其最先进的功能,在检测计算机服务器数据中的异常行为时展示其实际效用。