Forest Proximities for Time Series

Ben Shaw, Jake S. Rhodes, Soukaina Filali Boubrahimi, Kevin R. Moon

Abstract

RF-GAP has recently been introduced as an improved random forest proximity measure. In this paper, we present PF-GAP, an extension of RF-GAP proximities to proximity forests, an accurate and efficient time series classification model. We use the forest proximities in connection with Multi-Dimensional Scaling (MDS) to obtain vector embeddings of univariate time series, comparing the embeddings to those obtained using various time series distance measures. We also use the forest proximities alongside Local Outlier Factors (LOF) to investigate the connection between misclassified points and outliers, comparing with nearest neighbor classifiers which use time series distance measures. We show that the forest proximities may exhibit a stronger connection between misclassified points and outliers than nearest neighbor classifiers.

Introduction

Random Forests (RF) are a cornerstone of modern machine learning, yet they often struggle when applied directly to raw time series data. To address this, Proximity Forests (PF) were developed, replacing standard feature-based splits with specialized time-series distance measures such as Dynamic Time Warping (DTW). However, a significant gap remained: the lack of a robust proximity measure to quantify similarity between sequences as perceived by the model. Traditional proximity measures in forests are frequently biased or fail to capture the underlying data geometry. This work introduces PF-GAP, a geometry-preserving proximity measure for Proximity Forests, designed to enhance supervised visualization and outlier detection.

Methodology

The proposed PF-GAP measure extends the "Geometry and Accuracy Preserving" (GAP) approach to the time series domain.

PF-GAP Algorithm

The implementation involves three key modifications to the standard Proximity Forest:

  1. Bootstrap Sampling: Unlike original PF implementations, the model utilizes bootstrap sampling to generate "Out-of-Bag" (OOB) samples, which are critical for calculating unbiased proximities.
  2. The GAP Formula: Proximity is calculated based on the frequency with which two points co-occur in the same leaf node. Crucially, the GAP measure weights this frequency by the number of training points in that leaf, ensuring the proximity reflects the learned geometry of the forest.
  3. DGAP Distance: To facilitate distance-based analysis, proximities ($P_{ij}$) are converted into a distance metric, termed DGAP distance, using the transformation $d_{ij} = (1 - P_{ij})^2$.

Evaluation Framework

The utility of DGAP is evaluated through two primary lenses:

  • Supervised Visualization: Multi-Dimensional Scaling (MDS) is employed to project high-dimensional time series into a 2D space using DGAP distances.
  • Outlier Detection: DGAP distances are integrated with the Local Outlier Factor (LOF) algorithm to identify anomalous sequences.

Experimental Evaluation

The study utilizes 64 datasets from the UCR 2018 archive, a benchmark standard for time series classification. The selection was narrowed from the full 128-dataset archive to those without missing data and where 1-Nearest Neighbor (1-NN) benchmarks could be computed efficiently to allow for a fair comparison across multiple distance measures.

Results and Discussion

The experimental results demonstrate the clear superiority of PF-GAP over traditional distance measures in identifying anomalous data points.

Outlier Detection Performance

In the outlier detection experiments, the DGAP distance achieved the highest F1 score in 89% of the datasets (57 out of 64). In the remaining 7 datasets, it tied for the top spot, never being outperformed by traditional measures such as DTW, MSM, or LCSS. This dominance is illustrated in the comprehensive results table below.

Table 1: Comparison of F1 scores for outlier detection across 64 UCR datasets using various distance measures. DGAP consistently outperforms or matches all other metrics.

Qualitative analysis via MDS visualizations reveals that PF-GAP provides significantly cleaner class separation compared to unsupervised distances like DTW. Because PF-GAP is supervised, it learns to emphasize the features most relevant for classification.

A central finding of this research is the strong link between model misclassification and outlier status. The results indicate that when a Proximity Forest misclassifies a point, that point is almost invariably flagged as a high-score outlier by PF-GAP. This suggests that misclassified points are often "anomalous" relative to their true class distribution as learned by the forest, rather than simply being near a decision boundary.

Conclusion

PF-GAP provides a powerful tool for interpreting Proximity Forests, bridging the gap between classification performance and data geometry. By providing a supervised proximity measure that accurately reflects the model's internal logic, it enables superior visualization and highly effective outlier detection. Future work will explore the sensitivity of GAP proximities to tree counts and integrate these measures into the more efficient Proximity Forest 2.0 architecture.

Summary updated

Abstract

RF-GAP has recently been introduced as an improved random forest proximity measure. In this paper, we present PF-GAP, an extension of RF-GAP proximities to proximity forests, an accurate and efficient time series classification model. We use the forest proximities in connection with Multi-Dimensional Scaling to obtain vector embeddings of univariate time series, comparing the embeddings to those obtained using various time series distance measures. We also use the forest proximities alongside Local Outlier Factors to investigate the connection between misclassified points and outliers, comparing with nearest neighbor classifiers which use time series distance measures. We show that the forest proximities may exhibit a stronger connection between misclassified points and outliers than nearest neighbor classifiers.
BibTeX
@misc{shaw2024forest,
  author = {Ben Shaw and Jake S. Rhodes and Soukaina Filali Boubrahimi and Kevin R. Moon},
  title = {{Forest Proximities for Time Series}},
  year = {2024},
  eprint = {2410.03098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.03098},
}
Figure