Algorithms for time series knowledge mining

Fabian MörchenKDD 2006 · DOI

TL;DR

This paper introduces the Time Series Knowledge Representation (TSKR), a new hierarchical language for describing temporal patterns in time series data. They present efficient algorithms for mining these TSKR patterns, which are shown to be more effective and interpretable than traditional methods based on Allen's interval relations, especially for complex, noisy real-world data.

What Problem Does This Paper Address?

Discovering meaningful patterns in time series data is crucial for understanding complex phenomena. A common approach involves converting numerical time series into symbolic interval representations and then mining these intervals for temporal patterns. However, existing methods, primarily based on Allen's 13 interval relations (like "before," "overlaps," "during"), suffer from several drawbacks:

  • Lack of Robustness: These relations are sensitive to small changes in interval endpoints, leading to fragmented patterns for what are essentially similar temporal relationships.
  • Ambiguity: A single Allen relation can represent very different real-world scenarios, making interpretation difficult.
  • Poor Comprehensibility: Patterns often need to be expressed by listing numerous pairwise relations, which quickly becomes unwieldy and hard for humans to grasp.

The authors argue that these limitations hinder effective knowledge discovery, especially from noisy or complex data. They propose TSKR as a more expressive and robust alternative.

Methods

The core contribution lies in the Time Series Knowledge Representation (TSKR) language and the algorithms for mining it. TSKR is a hierarchical language that captures temporal concepts in increasing levels of abstraction:

  1. Tones: Represent basic duration, essentially symbolic intervals.
  2. Chords: Represent coincidence, where multiple Tones occur simultaneously.
  3. Phrases: Represent partial orders of Chords, capturing sequential relationships between coincidences.

The mining algorithms are adapted from established itemset and sequential pattern mining techniques, specifically:

  • Chord Mining: They adapt the CHARM algorithm (for closed itemset mining) to efficiently find "margin-closed" Chords. Margin-closedness is a novel concept that prunes redundant patterns by ensuring that a pattern's support is not significantly higher than its super-patterns, thus reducing the number of reported patterns while retaining essential information.
  • Phrase Mining: This involves a multi-step process:
  • Converting Chords into an "itemset interval series."
    • Mining for closed sequential patterns within this series using algorithms like CLOSPAN.
  • Grouping these sequential patterns to form "margin-closed" partial orders (Phrases), again adapting CHARM for efficiency.

A key algorithmic innovation is the concept of margin-closedness, which acts as a form of intelligent sampling and search space pruning, significantly reducing the number of patterns and improving mining speed.

Datasets

The paper evaluates their approach on a dataset from sports medicine, specifically from professional In-Line Speed Skating. This dataset consists of:

  • Kinematic data: 6-dimensional time series (angles and angular speeds of hip, knee, ankle joints) clustered into 3 states (swing, glide+push, recovery).
  • EMG data: 3 time series describing leg muscle activation (Medial Gastrocnemius, Vastus Medialis, Gluteus Maximus), discretized into Tones (low, high, very high).
  • Foot contact data: Obtained from a pressure sensor, with Tones (on/off).

The data was segmented into 19 movement cycles. The authors note that while they present experiments with this data, more experiments with video data can be found in their prior work [10]. No new benchmark datasets were introduced.

Key Insights and Ideas

  • TSKR's Hierarchical Advantage: The hierarchical structure of TSKR (Tones -> Chords -> Phrases) allows for a more natural and interpretable representation of temporal knowledge compared to flat interval relations.
  • Margin-Closedness for Pruning: The introduction of "margin-closedness" is a crucial algorithmic contribution. It effectively prunes the search space and the output set of patterns by allowing a small tolerance (controlled by parameter $\alpha$) for support differences between patterns and their super-patterns. This is key to making complex temporal pattern mining tractable.
  • Robustness to Noise: TSKR patterns, due to their hierarchical and less sensitive nature, are more robust to noise and discretization artifacts in the data than patterns based on Allen's relations.
  • Interpretability: The TSKR representation, especially Phrases, allows for a more human-understandable description of temporal phenomena, facilitating knowledge discovery by domain experts.
  • Efficiency Gains: The margin-closedness pruning significantly speeds up the mining process, reducing the number of recursive calls and overall computation.

Key Results

  • Pattern Reduction: For the skating data, TSKR with margin-closedness ( $\alpha=0.1$) yielded 18 margin-closed Chords and 15 margin-closed Phrases. In contrast, using Allen's relations with similar pruning resulted in 487 patterns.
  • Efficiency: The number of recursive calls to the mining algorithm was reduced by over 90% for $\alpha \ge 0.2$ compared to strict closed Chord mining, demonstrating significant speedup.
  • Effectiveness: The TSKR patterns were found to be more effective in capturing complex inter-muscular coordination patterns during skating, providing insights that were not readily apparent or interpretable with Allen's relations. Experts found the TSKR patterns more meaningful and useful.
  • Qualitative Findings: The paper highlights how TSKR can unfold patterns to reveal underlying Tones and numerical time series, aiding expert interpretation. For instance, a detailed Phrase revealed specific muscle activation sequences related to movement phases, which was difficult to extract using Allen's relations.

Limitations and Future Work

  • Parameter Sensitivity: The number of patterns and mining efficiency are sensitive to the chosen parameters, particularly $\alpha$ (margin-closedness threshold), $\delta$ (minimum Chord duration), and $\sup_{min}$ (minimum support). Setting these appropriately requires domain knowledge or experimentation.
  • Computational Cost of Phrases: Mining margin-closed Phrases is noted as the most computationally demanding task, as it involves a large number of closed sequential patterns.
  • Future Work: The authors suggest that margin-closedness could be beneficial in other itemset mining tasks. They also point out that while simple examples show margin-closed sequential patterns don't directly translate to margin-closed partial orders, further exploration of this relationship is warranted. The paper also mentions that more experiments with video data exist in their prior work, implying potential for further validation and application in different domains.

Summary updated

BibTeX
@inproceedings{morchen2006algorithms,
  author = {Fabian Mörchen},
  title = {{Algorithms for time series knowledge mining}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2006},
  doi = {10.1145/1150402.1150485},
}

Loading related content...

Figure