Unsupervised Change Detection using DRE-CUSUM

Sudarshan Adiga, Ravi Tandon

Introduction

Change detection—the identification of shifts in the statistical properties of time-series data—is a fundamental task in fields ranging from cybersecurity and healthcare to video surveillance. The classical "gold standard" for this task is the Cumulative Sum (CUSUM) algorithm. However, CUSUM is inherently supervised, requiring prior knowledge of the probability distributions both before and after a change occurs. In practical scenarios, these distributions are rarely known, especially in high-dimensional data like video streams or complex sensor arrays.

Existing unsupervised methods often rely on heuristics, struggle with high dimensionality, or impose restrictive parametric assumptions. This paper introduces DRE-CUSUM (Density-Ratio Estimation based CUSUM), a non-parametric, unsupervised framework designed to detect statistical shifts without prior knowledge of underlying distributions, while providing rigorous theoretical guarantees.

The DRE-CUSUM Framework

The core innovation of DRE-CUSUM lies in its use of density-ratio estimation (DRE) to circumvent the difficulty of modeling complex high-dimensional distributions. The workflow consists of four primary steps:

  1. Arbitrary Data Splitting: The time-series is partitioned at an arbitrary point $T_{\text{split}}$, creating "left" and "right" sample sets.
  2. Density-Ratio Estimation: Instead of estimating the individual densities of these sets, the algorithm trains a model—such as a Neural Network or a Kernel-based estimator—to directly estimate the ratio of the two densities.
  3. Statistic Calculation: A cumulative sum of the log-estimated ratio is computed to form the CUSUM statistic.
  4. Verification: To ensure the detected point is a true statistical shift rather than an artifact of the initial split, the process is re-run using the candidate point as the new split.
Illustration of the arbitrary split method where the left partition becomes a mixture of distributions $P_1$ and $P_2$.

As shown in the figure above, even if the split point $T_{\text{split}}$ is chosen arbitrarily, the resulting partitions effectively capture samples from the pre-change distribution ($P_1$) and post-change distribution ($P_2$), allowing the ratio estimator to learn the statistical difference between them.

Theoretical Foundation: Independence from $T_{\text{split}}$

The mathematical "secret sauce" of this approach is Proposition 1, which proves that the expected slope of the DRE-CUSUM statistic will change sign exactly at the true change point $T^*$. Remarkably, this property holds regardless of the initial choice of $T_{\text{split}}$, provided the split captures at least some samples from both distributions.

The CUSUM statistic $S_{\text{DR}}^{T_{\text{split}}}(t)$ consistently peaks at the true change point $T^*=150$ for various arbitrary split points $T_{\text{split}}$.

This theoretical finding is visualized in the figure above. Despite varying $T_{\text{split}}$ from 50 to 450, every CUSUM curve exhibits a clear peak at the true change point $T^* = 150$. This robustness allows the algorithm to function effectively in a completely unsupervised manner.

Experimental Evaluation

The researchers evaluated DRE-CUSUM against several state-of-the-art unsupervised algorithms across synthetic and real-world datasets:

  • Synthetic Data: In 50-dimensional multivariate Gaussian tests, DRE-CUSUM achieved a 0% False Alarm Rate (FAR) and 0% Missed Detection Rate (MDR). In contrast, Bayesian Online Change Detection (BCD) suffered from a significant ~30% FAR.
  • Human Activity Recognition (HASC & USC-HAD): On accelerometer data tracking transitions between activities (e.g., walking to jogging), DRE-CUSUM maintained perfect detection rates (0% FAR/MDR), while traditional methods like "Pelt" and "Binary Segmentation" missed over 20% of changes.
  • High-Dimensional Video: By utilizing Convolutional Neural Networks (CNNs) as the density-ratio estimators, the framework was applied directly to raw video pixels. It successfully identified events like a boat entering and exiting a frame in the "2012-Dataset," demonstrating its resilience to the "curse of dimensionality."

Conclusion and Future Directions

DRE-CUSUM represents a significant advancement in unsupervised change detection by combining the statistical rigor of CUSUM with the flexibility of density-ratio estimation. Its ability to integrate with deep learning models makes it uniquely suited for modern, high-dimensional data streams.

While highly effective, future work aims to extend formal accuracy guarantees to multi-change point scenarios. Additionally, optimizing the computational cost of training ratio estimators in real-time "online" settings remains an active area of research, with sliding window generalizations offering a promising path forward.

Summary updated

BibTeX
@inproceedings{adiga2022unsupervised,
  author = {Sudarshan Adiga and Ravi Tandon},
  title = {{Unsupervised Change Detection using DRE-CUSUM}},
  booktitle = {IEEECONF},
  year = {2022},
  doi = {10.1109/ieeeconf56349.2022.10052079},
}
Figure