Abstract
Time-series classification has attracted considerable research attention due to the various domains where time-series data are observed, ranging from medicine to econometrics. Traditionally, the focus of time-series classification has been on short time-series data composed of a unique pattern with intraclass pattern distortions and variations, while recently there have been attempts to focus on longer series composed of various local patterns. This study presents a novel method which can detect local patterns in long time-series via fitting local polynomial functions of arbitrary degrees. The coefficients of the polynomial functions are converted to symbolic words via equivolume discretizations of the coefficients' distributions. The symbolic polynomial words enable the detection of similar local patterns by assigning the same words to similar polynomials. Moreover, a histogram of the frequencies of the words is constructed from each time-series' bag of words. Each row of the histogram enables a new representation for the series and symbolize the existence of local patterns and their frequencies. Experimental evidence demonstrates outstanding results of our method compared to the state-of-art baselines, by exhibiting the best classification accuracies in all the datasets and having statistically significant improvements in the absolute majority of experiments.
Introduction
Time-series classification (TSC) is a critical task across diverse fields, including medicine and econometrics. Traditionally, TSC has focused on "short" series characterized by a single, unique pattern. In such scenarios, global alignment techniques like Dynamic Time Warping (DTW) are highly effective. However, many real-world signals—such as gait analysis or blood pressure monitoring—often consist of "long" series containing multiple local patterns that occur at varying frequencies and without a fixed global order.
Existing "Bag-of-Patterns" methods, such as those utilizing Symbolic Aggregate Approximation (SAX), attempt to address this by discretizing series into words based on local means. A significant limitation of these approaches is their reliance on piecewise constant approximations, which are often too simplistic to capture the nuanced curvature and shape of local trends. This paper introduces SymPol (Symbolic Polynomials), a method designed to capture these expressive local shapes while maintaining computational efficiency.
Methodology
The SymPol pipeline transforms a time series into a histogram representation through four primary stages:
1. Local Polynomial Fitting
A window of size $n$ slides across the time series. For each window, a polynomial of degree $d$ (e.g., cubic) is fitted to the data points. By recognizing that the relative time indices within the window are constant, the projection matrix for the least-squares fit can be pre-computed. This reduction allows the fitting process to scale linearly with the series length.
2. Equivolume Discretization
To provide robustness against noise and minor variations, the resulting polynomial coefficients are converted into symbols. SymPol employs "equivolume discretization," where thresholds are determined based on the distribution of each coefficient across the entire dataset. This ensures that each symbol in the alphabet represents an equal portion of the data's volume (quantiles).
3. Symbolic Word Construction and Histogram Representation
The discretized coefficients for each window are concatenated into a symbolic "word" (e.g., "ACBD"). The entire time series is then converted into a "bag of words" histogram, recording the frequency of each unique polynomial shape. Classification is performed using a simple Nearest Neighbor (NN) classifier with Euclidean distance on these histograms.
Experimental Results
SymPol was evaluated on four healthcare-related datasets: ECG2 (electrocardiography), GAITPD (gait analysis for Parkinson’s), RATBP (blood pressure in rats), and NESFDB (postural sway).
The method demonstrated superior accuracy across all benchmarks:
- ECG2: Achieved 100% classification accuracy.
- GAITPD: Reduced the error rate by 57% compared to the next best baseline.
- RATBP: Reduced the error rate by 29%.
SymPol maintains linear-time complexity $O(M \cdot N)$, where $M$ is the number of series and $N$ is the length. While slightly more intensive than constant-approximation methods, it is orders of magnitude faster than DTW for long series, making it practical for large-scale physiological monitoring.
Conclusion
SymPol provides a powerful framework for long time-series classification by prioritizing local curvature over global alignment. By utilizing symbolic polynomials, it captures complex shapes—such as distinguishing between concave and convex trends—that simpler piecewise constant methods miss. While the current approach discards global temporal ordering, future work may explore incorporating temporal hierarchies to preserve sequence information while maintaining the benefits of the bag-of-patterns representation.
Summary updated