TL;DR
This paper introduces Wavelet-TSS (W-TSS), a novel algorithm that uses wavelet transformations to efficiently discover "shapelets" – maximally discriminative subsequences within time series data. W-TSS significantly speeds up the process of identifying these crucial patterns compared to existing methods, while also demonstrating improved accuracy and the ability to discover more meaningful shapelets without requiring pre-specification of their length.
What Problem Does This Paper Address?
Time series classification is a critical task in many fields, including health research, where identifying patterns in sensor data can help predict outcomes. Traditional methods often rely on global statistics or shapes, potentially missing important local patterns. Time Series Shapelets (TSS) offer a promising alternative by identifying maximally discriminative local subsequences. However, the original TSS algorithms are computationally intensive due to the exhaustive search required to find candidate shapelets. While subsequent methods have introduced efficiencies, they often suffer from limitations like losing temporal detail, missing important patterns, or being sensitive to initial parameters. This paper addresses the need for a more efficient, accurate, and flexible method for discovering time series shapelets.
Methods
The core innovation of this paper is the Wavelet-TSS (W-TSS) algorithm. W-TSS leverages the power of wavelet transformations to identify regions of high energy within time series. The process involves:
- Wavelet Transformation: Applying various wavelet functions (e.g., Morlet, Mexican Hat, Gaussian) to the time series to decompose it into time-scale representations.
- Scalogram Analysis: Generating scalograms, which visualize the energy distribution across different time scales.
- Energy Localization: Identifying regions of high energy in the scalogram, which correspond to potentially discriminative patterns in the original time series.
- Candidate Shapelet Extraction: Converting the scalogram into a binary image and extracting subsequences from the original time series that correspond to high-energy regions. A minimum length threshold is applied to filter out noise.
- Shapelet Pool Generation: Creating an initial pool of candidate shapelets from these extracted subsequences.
- Optional Filtering/Clustering: For large pools, W-TSS offers optional steps like variance-based filtering or k-means clustering to reduce the number of candidate shapelets.
- Machine Learning Integration: The final candidate shapelets are used as features (typically by calculating distances to them) for a machine learning classifier (e.g., logistic regression, gradient boosted trees) to predict the time series class.
A key advantage is that W-TSS does not require pre-specifying the length of the shapelets, unlike many existing TSS methods.
Datasets
The authors evaluated W-TSS on three datasets:
- Synthetic TRACE dataset: A benchmark dataset from the UCR Time Series Archive, designed to simulate instrumentation failures in a nuclear power plant. It features four classes with unique local patterns but variations in their timing.
- PRISMS dataset (Indoor vs. Outdoor PM2.5): Real-world data from a pediatric asthma study, measuring indoor and outdoor particulate matter (PM2.5) levels. This dataset presents more variation and poses a greater classification challenge.
- PRISMS dataset (Rescue Medication Usage): Also from the PRISMS study, this dataset uses residential indoor PM2.5 time series to predict days with vs. without rescue medication usage.
Key Insights and Ideas
- Wavelets as a powerful tool for shapelet discovery: The paper demonstrates that wavelet transforms can effectively highlight regions of interest in time series, which are highly indicative of discriminative patterns.
- Unsupervised discovery is computationally efficient: By using wavelets to identify candidate shapelets in an unsupervised manner, W-TSS drastically reduces the search space compared to brute-force methods.
- Flexibility in shapelet length: The ability of W-TSS to discover shapelets of varying lengths without prior specification is a significant advantage, allowing it to adapt to different types of patterns.
- Improved interpretability: The shapelets discovered by W-TSS often closely match iconic local patterns within the data, making the classification results more interpretable, especially in health-related applications.
- Real-world applicability: W-TSS shows promise in challenging real-world scenarios, such as distinguishing indoor vs. outdoor air pollution, even when classification is difficult.
Key Results
- Synthetic TRACE dataset: W-TSS produced a significantly smaller set of candidate shapelets (<0.2% of brute-force) and achieved perfect classification accuracy. The discovered shapelets better matched the iconic local patterns of the four classes compared to those found by learning TSS.
- PRISMS (Indoor vs. Outdoor PM2.5): W-TSS perfectly predicted indoor vs. outdoor PM2.5 daily time series. The method rapidly identified a small fraction of potential candidate shapelets, demonstrating computational efficiency.
- PRISMS (Rescue Medication Usage): While W-TSS identified patterns suggestive of indoor sources, it did not perfectly predict rescue medication usage. However, the discovered patterns were deemed of scientific interest for future investigation into the complex association between PM2.5 and asthma medication use.
- Computational Efficiency: W-TSS significantly reduced the computational load by identifying a much smaller set of candidate shapelets compared to brute-force approaches.
Limitations and Future Work
- Hyperparameter Tuning: While W-TSS reduces the need to tune shapelet length, it still requires specifying wavelet functions and scales. The authors suggest examining multiple wavelet functions and scales to inform this choice.
- Filtering/Clustering Parameters: The optional filtering and clustering steps for reducing candidate shapelets involve their own hyperparameters (e.g., number of clusters for k-means) that need to be specified.
- Supervised Filtering: The variance-based filtering method used in the PRISMS application was noted as being supervised and could potentially be replaced by more complex supervised methods.
- Future Work:
- Evaluating other time-frequency decomposition methods.
- Developing more intelligent methods for choosing scales based on time-frequency decomposition.
- Extracting multivariate patterns for complex, high-dimensional temporal data.
- Combining W-TSS with existing multivariate shapelet discovery algorithms.
- Investigating the use of W-TSS candidate shapelets as initial values for learning TSS algorithms.
Summary updated