Use of Ensembles of Fourier Spectra in Capturing Recurrent Concepts in Data Streams

Sripirakas Sakthithasan, Russel Pears, Albert Bifet, Bernhard Pfahringer

Abstract

This paper introduces a novel ensemble approach that utilizes Fourier-transformed decision trees to capture and reuse recurring patterns in non-stationary data streams. By aggregating individual "Fourier spectra" into a unified ensemble pool (EP), the proposed method achieves significant improvements in classification accuracy while reducing memory overhead by up to 55% compared to traditional methods. The approach treats machine learning models as signals, allowing for efficient storage and merging based on structural similarity.

Introduction

In the analysis of data streams—such as stock market tickers, sensor feeds, or network traffic—the underlying patterns often change over time, a phenomenon known as concept drift. However, these "concepts" often recur (e.g., seasonal shopping habits). While machine learning systems can re-learn these concepts from scratch, it is far more efficient to store and reuse past models. The primary challenge is scalability: in volatile environments, storing every unique decision tree leads to a "memory explosion." Previous research attempted to solve this by converting decision trees into compact algebraic forms using the Discrete Fourier Transform (DFT), but even individual spectra can overwhelm a system when new concepts emerge frequently.

Methodology

The authors propose the EP (Ensemble Pool) Algorithm, which moves beyond storing individual models to managing a pool of aggregated Fourier spectra. The system architecture, illustrated below, manages the transition from raw stream instances to a compressed ensemble pool.

Figure 2: The architecture of the Ensemble Pool (EP) algorithm, showing the flow from data stream instances to the Fourier Spectrum Generator and the final Ensemble Pool.

1. Fourier Encoding

Decision trees are represented as algebraic expressions using DFT. This preserves the "predictive power" of the tree in a much more compact format. For example, a standard decision tree (as seen in Figure 1) is transformed into a set of coefficients that capture its core logic.

Figure 1: A sample decision tree with features X3 and X1, which serves as the input for Fourier transformation.

2. Ensemble Aggregation

Instead of a 1-to-1 mapping of concept to spectrum, the EP algorithm merges new spectra into existing ones based on structural similarity. If a new concept is structurally similar to an existing ensemble, they are mathematically combined. The authors found that merging based on structure is more effective than merging based on performance accuracy, as the latter can lead to performance degradation.

3. Mathematical Optimizations

The paper introduces two key theorems to enhance performance:

  • Energy Thresholding: A method to calculate total spectral energy without enumerating every coefficient, allowing for aggressive but safe compression.
  • Basis Function Optimization: A technique to skip expensive operations when dealing with "wildcard" features (attributes not used in a specific branch of a tree).

Experimental Evaluation

The researchers evaluated the EP approach using both synthetic (Rotating Hyperplane) and real-world datasets (Spam, NSW Electricity, and NASA Flight Data). The ensemble approach consistently outperformed single-spectrum approaches (FCT) and standard Hoeffding Trees (CBDT):

  • Memory Efficiency: EP reduced memory consumption by an average of 41% across all datasets, reaching as high as 55% on the Electricity dataset.
  • Accuracy: On the NASA Flight dataset, EP demonstrated a 7.6% gain in accuracy over FCT in memory-constrained environments. It also showed higher tolerance to noise (20-30% levels) than its counterparts.
  • Processing Speed: Despite the overhead of merging spectra, EP was often the fastest method because its stability triggered fewer "false alarms" for concept drift, reducing the need for expensive model re-training.

Conclusion and Future Work

By treating machine learning models like signals, the EP algorithm naturally filters out noise; low-order coefficients capture core logic, while high-order coefficients (often representing overfitted noise) are discarded. While the paper demonstrates clear wins in efficiency, future work remains in leaf-node optimization and parallelization (e.g., using Apache Spark) to handle even higher-velocity streams. Additionally, the structural similarity threshold ($\alpha$) remains a key hyperparameter requiring domain-specific tuning.

Summary updated

Abstract

In this research, we apply ensembles of Fourier encoded spectra to capture and mine recurring concepts in a data stream environment. Previous research showed that compact versions of Decision Trees can be obtained by applying the Discrete Fourier Transform to accurately capture recurrent concepts in a data stream. However, in highly volatile environments where new concepts emerge often, the approach of encoding each concept in a separate spectrum is no longer viable due to memory overload and thus in this research we present an ensemble approach that addresses this problem. Our empirical results on real world data and synthetic data exhibiting varying degrees of recurrence reveal that the ensemble approach outperforms the single spectrum approach in terms of classification accuracy, memory and execution time.
BibTeX
@inproceedings{sakthithasan2015use,
  author = {Sripirakas Sakthithasan and Russel Pears and Albert Bifet and Bernhard Pfahringer},
  title = {{Use of Ensembles of Fourier Spectra in Capturing Recurrent Concepts in Data Streams}},
  booktitle = {IJCNN},
  year = {2015},
  doi = {10.1109/ijcnn.2015.7280583},
}
Figure