A Locally Optimal Algorithm for Estimating a Generating Partition from an Observed Time Series and Its Application to...

Area of Science:

• Dynamical Systems and Time Series Analysis
• Information Theory
• Applied Mathematics

Background:

• Symbolization of discrete-time dynamical systems is crucial for characterizing system dynamics and enabling applications like time series classification and anomaly detection.
• Existing methods for estimating generating partitions, like the Hirata et al. objective function, suffer from non-convergent algorithms and heuristic nearest neighbor assignments.
• The Hirata et al. objective function, while effective, is often misinterpreted as a state-space partitioning problem, rather than a clustering problem in an infinite-dimensional space.

Purpose of the Study:

• To develop a novel, locally optimal algorithm for estimating generating partitions by minimizing the Hirata et al. objective function.
• To address the non-convergence issues of previous algorithms and provide guaranteed discrepancy descent for joint, locally optimal symbolization.
• To demonstrate the effectiveness of the new approach in improving time series symbolization and its application in anomaly detection.

Main Methods:

• Development of an iterative nearest-neighbor symbol assignment algorithm with guaranteed discrepancy descent.
• Framing generating partition estimation as a clustering problem in the space of the entire time series, rather than state-space partitioning.
• Application of the algorithm to symbolizing chaotic maps and time-series anomaly detection in a polycrystalline alloy material.

Main Results:

• The proposed algorithm achieves joint, locally optimal symbolization of the entire time series.
• Demonstrated improvement over popular methods for symbolizing chaotic maps using several performance measures.
• Successful application of the approach to time-series anomaly detection, including in a real-world material science context.

Conclusions:

• The novel algorithm provides a robust and convergent method for generating partition estimation, advancing the field of time series analysis.
• The approach offers a new perspective on lossy source coding and clustering in infinite-dimensional spaces.
• The method shows significant potential for enhancing the accuracy and reliability of time series classification and anomaly detection in diverse applications.