TL;DR
This paper introduces "Time Series Chains," a novel data mining primitive that captures evolving patterns in time series data, distinct from traditional motifs. By defining and developing an algorithm to discover these chains, the authors provide a new lens for understanding dynamic systems and predicting future behavior.
What Problem Does This Paper Address?
Time series motifs, which identify repeating patterns, have been a cornerstone of time series analysis for years. However, many real-world phenomena involve patterns that aren't static but rather evolve or drift over time. Existing methods for motif discovery are not well-suited to capture this temporal evolution. The authors aim to address this gap by introducing "Time Series Chains," a new primitive that explicitly models these gradual changes within a sequence of patterns. This allows for a deeper understanding of dynamic systems and could have significant implications for prognostics and predicting future states.
Methods
The core contribution is the definition and discovery algorithm for Time Series Chains. Informally, a chain is an ordered set of subsequences where each subsequence is similar to its predecessor, but the first and last subsequences can be quite different. This captures a sense of "drifting" or "evolving" over time.
The formal definition relies on the concepts of "left nearest neighbor" (LNN) and "right nearest neighbor" (RNN) for subsequences. A time series chain is an ordered set of subsequences $T_{C_1,m}, T_{C_2,m}, \dots, T_{C_k,m}$ where $C_1 \le C_2 \le \dots \le C_k$, and for each consecutive pair $(T_{C_i,m}, T_{C_{i+1},m})$, $T_{C_{i+1},m}$ is the RNN of $T_{C_i,m}$, and $T_{C_i,m}$ is the LNN of $T_{C_{i+1},m}$.
The algorithm to find these chains involves three main steps:
- Finding Nearest Neighbors: Using an algorithm called LRSTOMP (a variant of STOMP), the left and right nearest neighbors for all subsequences in the time series are computed. This step has a time complexity of $O(n^2)$ and space complexity of $O(n)$, where $n$ is the length of the time series.
- Growing Anchored Chains: Based on the nearest neighbor information, "anchored chains" are grown from each subsequence. An anchored chain starts at a specific subsequence and extends as long as the nearest neighbor relationship holds. This step is $O(n)$ in time and space.
- Identifying the Unanchored Chain: The "unanchored time series chain" is defined as the longest anchored chain found in the time series. This is considered to represent the most general trend within the data.
The paper distinguishes between "anchored" chains (starting at a specific point) and "unanchored" chains (the longest chain overall).
Datasets
The paper evaluates the Time Series Chain discovery algorithm on several real-world datasets, including:
- An electrical power demand dataset monitoring domestic freezer usage.
- An arterial blood pressure (ABP) dataset from a patient undergoing a tilt-table test.
- X-Axis acceleration data from a Magellanic penguin.
- Gait data from an accelerometer on a mobile phone.
- Google Trends query volume for the keyword "Kohl's."
The authors emphasize that these datasets span various characteristics (stationary, trending, smooth, noisy) and lengths (from seconds to years), demonstrating the algorithm's versatility. They also provide a website for reproducible results, archiving all datasets and code.
Key Insights and Ideas
- Beyond Static Patterns: The most significant insight is the introduction of a primitive that moves beyond static, repeating motifs to capture dynamic, evolving patterns. This is crucial for understanding systems that change over time.
- Directionality as a Key Feature: The formal definition explicitly incorporates directionality, ensuring that the chain represents a progression rather than just a collection of similar patterns.
- Robustness to Noise and Sampling: The algorithm is shown to be robust to noisy and coarsely sampled data, a common challenge in real-world time series. It can still discover meaningful chains even when some links are distorted or missing.
- Broad Applicability: The case studies demonstrate that Time Series Chains can be found across diverse domains, from physiological signals to animal behavior and web search trends, suggesting their universal utility.
- Potential for Prognostics: The ability to capture evolving patterns opens doors for predicting future states or identifying critical transitions in dynamic systems.
Key Results
The paper presents qualitative results from several case studies, showcasing the discovered time series chains and their interpretations:
- Hemodynamics: A chain in arterial blood pressure data revealed a decreasing height of the dicrotic notch as a patient was tilted, correlating with changes in central venous filling.
- Penguin Behavior: A chain in penguin acceleration data was linked to the bird's dive behavior, showing a transition from a sprint to a cruise as it descended.
- Human Gait: A chain in mobile phone accelerometer data suggested an evolution from an unstable gait pattern to a more stable and symmetric one as the phone settled in the user's pocket.
- Web Query Volume: A chain in Google Trends data for "Kohl's" highlighted the increasing importance of "Cyber Monday" by showing a shift in the holiday shopping bump's timing.
While specific quantitative performance metrics (like accuracy or speedup compared to other methods) are not the primary focus, the paper demonstrates the algorithm's ability to discover meaningful patterns in large datasets.
Limitations and Future Work
- Theoretical Treatment: The authors acknowledge the need for a more theoretical treatment of the properties of time series chains.
- Adaptation to Online Problems: They plan to adapt and apply the chain discovery to online problems, such as prognostics and concept drift detection.
- Subsequence Length Parameter (m): While the paper notes that the choice of subsequence length ($m$) doesn't need to be perfectly precise, it remains a parameter that influences the discovered chains. The paper provides guidance on selecting $m$ (e.g., related to the typical period of the data) but further exploration of its impact could be beneficial.
- Unanchored Chain Uniqueness: The paper mentions that there can be more than one unanchored time series chain of the same maximum length. The current approach reports the chain with the minimum average distance between consecutive components in case of ties.
Summary updated