Motif-based Rule Discovery for Predicting Real-valued Time Series

Yuanduo He, Xu Chu, Juguang Peng, Jingyue Gao, Yasha WangarXiv 2017 · arXiv

Introduction

Predicting real-valued time series, such as electricity consumption or financial indices, is a fundamental task in data science. Traditional approaches often rely on point-wise numerical predictions. However, in many domains, the underlying "shape" or pattern of the data provides a more robust signal for future events than specific values. Researchers from Peking University have introduced a novel framework, Motif-based Rule Discovery (MBP), which shifts the focus from raw numbers to recurring shapes, known as motifs.

The Challenge of Rule-Based Prediction

Previous attempts at rule-based time series prediction faced significant obstacles. Early methods often relied on "symbolization," converting continuous data into discrete symbols. This process frequently resulted in substantial information loss, stripping away the nuanced details necessary for accurate forecasting. More recent state-of-the-art methods attempted to discover rules by splitting subsequences into fixed antecedent and consequent parts. This approach struggled with variable time gaps between related events, leading to "noisy" rules that failed to generalize.

Methodology: The MBP Framework

The proposed MBP method addresses these issues through a three-stage pipeline:

  1. Motif-like Pattern Discovery: Instead of arbitrary segmentation, the system employs the MK algorithm to identify "motifs"—subsequences that repeat frequently. These motifs serve as the foundational building blocks for predictive rules.
  2. Heuristic Matching: This core innovation involves finding the optimal set of matches between two motifs ($m_A$ and $m_B$) across the time series. Using 0-1 integer programming, the algorithm enforces a "parallel constraint," ensuring that the temporal ordering of rule instances remains consistent (i.e., no "crossed" rules).
  3. MDL-based Scoring: Rules are ranked using the Minimum Description Length (MDL) principle. A rule is deemed high-quality if the presence of the antecedent significantly simplifies the description of the consequent.
Illustration of motif matching between two time series $T_A$ and $T_B$.

Experimental Evaluation

The MBP framework was evaluated on two large-scale energy consumption datasets: AMPds (electricity data from a single household) and UK-DALE (high-frequency power demand from five houses).

Key Results

The motif-based approach demonstrated a significant performance leap over existing methods. On the AMPds dataset, MBP outperformed the previous state-of-the-art (Y15) by an average of 23.9% based on a normalized distance metric.

Discovery of recurring motifs within a real-world time series.

Qualitative analysis revealed that MBP is particularly effective at capturing the "true" shapes of events, even when separated by noisy intervals. For instance, in the UK-DALE dataset, the system successfully identified behavioral rules, such as the use of a hair dryer being a strong predictor for the subsequent use of a hair straightener.

Conclusion and Future Directions

By focusing on recurring shapes and explicitly modeling the temporal gaps between them, the Motif-based Rule Discovery method provides a more accurate and interpretable way to predict real-valued time series. While the current work focuses on household energy data, future research will explore more diverse datasets and develop additional metrics to uncover deeper causal relationships within the discovered rules.

Summary updated

Abstract

Time series prediction is of great significance in many applications and has attracted extensive attention from the data mining community. Existing work suggests that for many problems, the shape in the current time series may correlate an upcoming shape in the same or another series. Therefore, it is a promising strategy to associate two recurring patterns as a rule's antecedent and consequent: the occurrence of the antecedent can foretell the occurrence of the consequent, and the learned shape of consequent will give accurate predictions. Earlier work employs symbolization methods, but the symbolized representation maintains too little information of the original series to mine valid rules. The state-of-the-art work, though directly manipulating the series, fails to segment the series precisely for seeking antecedents/consequents, resulting in inaccurate rules in common scenarios. In this paper, we propose a novel motif-based rule discovery method, which utilizes motif discovery to accurately extract frequently occurring consecutive subsequences, i.e. motifs, as antecedents/consequents. It then investigates the underlying relationships between motifs by matching motifs as rule candidates and ranking them based on the similarities. Experimental results on real open datasets show that the proposed approach outperforms the baseline method by 23.9%. Furthermore, it extends the applicability from single time series to multiple ones.
BibTeX
@misc{he2017motif,
  author = {Yuanduo He and Xu Chu and Juguang Peng and Jingyue Gao and Yasha Wang},
  title = {{Motif-based Rule Discovery for Predicting Real-valued Time Series}},
  year = {2017},
  eprint = {1709.04763},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.04763},
}
Figure