Robust periodicity detection algorithms

ABSTRACT

Periodicity detection is an important pre-processing step for many time series algorithms. It provides important information about the structural properties of a time series. Feature vectors based on periodicity can be used for clustering, classification, abnormality detection, and human motion understanding. The periodicity detection task is not difficult in case of simple and uncontaminated signal. Unfortunately, most of the real datasets exhibit one or more of the following properties: i) non-stationarity, ii) interlaced cyclic patterns and iii) data contamination, which makes the period detection extremely challenging. A seemingly straightforward solution is to develop individual specialized algorithms for handling each case separately. However, determining if a time series is non-stationary or is contaminated in itself is an extremely difficult task. In this article, we propose generic algorithms which can detect periods in complex, noisy and incomplete datasets. The algorithm leverages the frequency characterization and autocorrelation structure inherent in a time series to estimate its periodicity. We extend the methods to handle non-stationary time series by tracking the candidate periods using a Kalman filter. We also address the interesting problem of finding multiple interlaced periodicities.

REFERENCES

• 1: Michail Vlachos et al. On periodicity detection and structural periodic similarity. In SDM, 2005.
• 2: P. P. Kanjilal et al. Robust method for periodicity detection and characterization of irregular cyclical series in terms of embedded periodic components. Phys. Rev. E, 59(4):4013--4025, 1999.
• 3: Srinivasan Parthasarathy et al. Robust periodicity detection algorithms. Technical Report OSU-CISRC-3/06-TR29.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Experimentation

Keywords:
interlaced periodicity, non-stationary time series, periodicity, pre-processing, time series