Introduction
Change point detection (CPD) is a critical task in time-series analysis, aimed at identifying the exact moments when the underlying distribution of a signal changes. Applications range from industrial fault detection to environmental monitoring. Traditional CPD methods are often categorized into model-based approaches, which assume a specific data distribution, and model-free approaches, which compare data windows directly. However, many existing model-free methods suffer from high computational costs or struggle with high-dimensional data due to "hubness"—a phenomenon where certain points become disproportionately frequent nearest neighbors, distorting similarity metrics.
This paper, presented at AAAI-25, introduces Hub-CPD, a novel model-free algorithm that leverages hubness as a diagnostic tool rather than a nuisance. By measuring the effectiveness of hubness-suppression techniques, Hub-CPD identifies distribution shifts with high accuracy and efficiency.
Methodology: Residual Normalization and the Rayleigh Score
The core of Hub-CPD is a three-step process designed to transform time-series data into a geometric signal of change.
- Preprocessing: Raw time-series data is transformed into high-dimensional vectors using a sliding window approach (Hankel matrix).
- Residual Normalization (ResNorm): Given two datasets $D$ and $D'$ (representing "before" and "after" windows), the algorithm finds the $k$-nearest neighbors in $D'$ for each point in $D$. It calculates a local centroid and computes a residual vector, which is then normalized to unit length.
- Uniformity Testing: If $D$ and $D'$ share the same distribution, the normalized residuals should be uniformly distributed on a unit hyper-sphere. Hub-CPD uses the Rayleigh score—the norm of the mean of these vectors—to quantify this. A low score suggests uniformity (no change), while a high score indicates clustering (a distribution shift).
As shown in the figure above, when a significant difference exists between datasets ($diff=1.0$), the normalized residuals cluster, leading to a higher Rayleigh score. Conversely, when distributions are identical ($diff=0.0$), the points spread out uniformly. This process can be iterated ($r$ times) to amplify subtle differences.
Experimental Results
The authors evaluated Hub-CPD against state-of-the-art methods like RuLSIF and KL-CPD across synthetic and real-world datasets, including hydraulic system and gas sensor data.
Sensitivity and Accuracy
Hub-CPD demonstrates high sensitivity to both mean shifts ($\mu$) and variance shifts ($\sigma$). The Rayleigh score increases monotonically as the magnitude of the shift grows, providing a clear signal for detection.
In real-world tests on gas sensor data, Hub-CPD achieved a state-of-the-art average AUC of 0.952. Its performance was particularly robust on heavy-tailed distributions (e.g., t-distributions), where the local normalization step effectively mitigated the impact of outliers.
Computational Efficiency
One of the most striking advantages of Hub-CPD is its speed. In benchmarks using hydraulic system data, Hub-CPD processed the signal in approximately 0.5 seconds, whereas the popular KL-CPD method required over 212 seconds. This efficiency makes it highly suitable for real-time monitoring applications.
Conclusion and Future Work
Hub-CPD represents a paradigm shift in high-dimensional CPD by utilizing the geometry of hubness to detect distribution changes. While the method is highly effective, its performance is sensitive to hyperparameters such as the number of neighbors ($k$) and the number of iterations ($r$). Future research will focus on automating the selection of these parameters to enhance the algorithm's robustness across diverse data types.
Summary updated