Abstract
In this work, we propose a non-parametric and robust change detection algorithm to detect multiple change points in time series data under contamination. The contamination model is sufficiently general, in that, the most common model used in the context of change detection -- Huber contamination model -- is a special case. Also, the contamination model is oblivious and arbitrary. The change detection algorithm is designed for the offline setting, where the objective is to detect changes when all data are received. We only make weak moment assumptions on the inliers (uncorrupted data) to handle a large class of distributions. The robust scan statistic in the algorithm is fashioned using mean estimators based on influence functions. We establish the consistency of the estimated change point indexes as the number of samples increases, and provide empirical evidence to support the consistency results.
Introduction
Identifying when a process changes—known as Change Point Detection (CPD)—is a fundamental task in time series analysis, critical for monitoring sensor networks, financial markets, and environmental quality. However, real-world data is rarely clean; it is often plagued by outliers, heavy-tailed distributions, and adversarial contamination. Traditional CPD methods frequently rely on assumptions of clean data or specific distributions (like Gaussian), making them fragile in practical applications.
This paper introduces RC-Cat (Robust Change Detection with Catoni), a non-parametric offline algorithm that detects multiple change points even when up to 40% of the data is corrupted. By leveraging robust mean estimators based on Catoni’s influence functions, the method remains consistent and computationally efficient without requiring strict distributional assumptions.
Methodology: The RC-Cat Algorithm
The core of the proposed approach is the robust scan statistic. Instead of a simple average, which is easily skewed by outliers, RC-Cat uses a robust mean estimator based on influence functions. These functions "soft-truncate" extreme values, ensuring they do not disproportionately impact the estimate.
The algorithm "scans" the time series using two adjacent windows of length $w$. It calculates the robust mean for both windows and evaluates the absolute difference between them. A change point is flagged if this difference—the scan statistic—is a local maximum within a defined neighborhood and exceeds a specific threshold $b$.
Key technical innovations include:
- Shifting Device: A mechanism that uses a small subset of data to "center" the rest, improving estimator accuracy for non-centered data.
- Computational Efficiency: RC-Cat achieves a complexity of $O(nw)$, significantly outperforming previous state-of-the-art methods like the ARC algorithm ($O(n^2w \log w)$).
- Full Data Utilization: Unlike methods requiring sample splitting, RC-Cat uses the entire dataset, reducing the risk of missing change points.
Experimental Evaluation
The authors validated RC-Cat using both synthetic and real-world datasets:
- Synthetic Data: Time series with heavy-tailed Student-t distributions were corrupted with Pareto distributions or adversarial spikes. RC-Cat demonstrated superior performance; for instance, under 40% corruption, its detection error was significantly lower than that of the ARC algorithm (17.7 vs 25.6 in specific settings).
- Well-log Data: In this classic benchmark of nuclear magnetic response measurements, RC-Cat successfully identified shifts despite frequent outliers.
- PM2.5 Hong Kong Data: The algorithm tracked air quality fluctuations from 2014 to 2022, distinguishing true pollution shifts from natural noise.
Key Insights and Consistency
A major contribution of this work is the formal proof of consistency (Theorem 4). The authors establish that as the number of samples increases, the probability of correctly identifying the number and location of change points approaches 1. This holds even under "weakly adversarial" noise, where an oblivious adversary can change a fraction of the data but cannot perfectly hide a change point.
The algorithm's reliance on weak moment assumptions—requiring only a bounded second moment for inliers—allows it to handle a vast class of distributions without prior knowledge of their specific forms.
Conclusion
RC-Cat provides a robust and efficient framework for offline change point detection in contaminated environments. While currently focused on univariate time series, the authors identify the extension to multivariate datasets and handling stronger adversarial models as promising directions for future research.
Summary updated