Abstract
The problem of frequent and anomalous patterns discovery in time series has received a lot of attention in the past decade. Addressing the common limitation of existing techniques, which require a pattern length to be known in advance, we recently proposed grammar-based algorithms for efficient discovery of variable length frequent and rare patterns. In this paper we present GrammarViz 2.0, an interactive tool that, based on our previous work, implements algorithms for grammar-driven mining and visualization of variable length time series patterns.
Introduction
A significant challenge in time series mining is the discovery of motifs (frequent patterns) and discords (anomalies). Traditional approaches often rely on a fixed window length, requiring users to know the exact duration of the pattern they are searching for. This is often impractical, as real-world events—such as cardiac arrhythmias or sensor failures—vary in duration. GrammarViz 2.0 addresses this by enabling variable-length pattern discovery without prior knowledge of the pattern's shape or duration.
Methodology: From Data to Grammar
GrammarViz 2.0 utilizes a three-phase workflow to transform raw numerical data into a searchable grammar:
- Discretization via SAX: Raw time series data is converted into a symbolic string using Symbolic Aggregate Approximation (SAX). This process involves normalizing the data and mapping segments to an alphabet based on their average values.
- Grammar Induction with Sequitur: The tool applies the Sequitur algorithm to the SAX string. Sequitur is a linear-time algorithm that compresses strings by building a context-free grammar. It creates "rules" for repeating sequences of symbols.
- Pattern Discovery:
- Motifs: Rules frequently utilized in the grammar represent recurrent patterns.
- Discords: Rules with low frequency, or regions with low "rule density," indicate potential anomalies.
Because grammar rules can be hierarchical (where one rule contains another), the system naturally captures patterns across multiple scales and lengths.
Key Features and Insights
GrammarViz 2.0 treats time series data as a language. Just as common words form frequent rules in linguistics, common physical motions or signals become frequent rules in the generated grammar.
A standout feature is the Rule Density Plot. By visualizing how many grammar rules cover specific points in time, the tool makes anomalies visually apparent as "light" spots where the grammar failed to identify common structures. Furthermore, the tool is highly interactive, allowing users to adjust SAX parameters—such as alphabet and PAA size—and observe real-time updates to the grammar and pattern discovery results.
Evaluation and Results
The effectiveness of GrammarViz 2.0 is demonstrated using ECG (Electrocardiogram) datasets. In these examples, the tool successfully identifies motifs of varying lengths without manual window-size tuning.
Crucially, the tool can highlight subtle anomalies, such as the ST wave discord, which are often overlooked by standard threshold-based detection methods. Leveraging the linear-time efficiency of Sequitur, the tool remains highly responsive even when processing large datasets.
Limitations and Future Directions
While GrammarViz 2.0 removes the requirement for fixed window lengths, it remains sensitive to SAX parameters. Selecting an inappropriate "resolution" during discretization can obscure certain patterns. Future work includes the development of mSequitur, an extension introducing a "merging operator" to recognize slight variations of the same pattern, further improving data reduction and generalization.
Summary updated