Particle swarm optimization for time series motif discovery

Joan Serrà, Josep Lluís Arcos

TL;DR

This paper introduces SWARMMOTIF, a novel approach to time series motif discovery that frames the problem as an "anytime multimodal optimization task." By leveraging Particle Swarm Optimization (PSO), SWARMMOTIF efficiently finds similar patterns in time series data, offering comparable results to state-of-the-art methods in significantly less time and with minimal memory.

What Problem Does This Paper Address?

Time series data is ubiquitous, from financial markets to biological signals. Identifying recurring patterns, or "motifs," within this data is crucial for understanding underlying systems, classification, and prediction. However, efficiently and flexibly discovering these motifs, especially in long time series streams, is a significant challenge. Existing methods often rely on data discretization (like SAX) which can lead to high computational costs and require careful parameter tuning, or they struggle with finding motifs of varying lengths or providing results incrementally (anytime algorithms). Furthermore, many methods are restricted to specific dissimilarity measures and lack flexibility.

Methods

The core innovation of this paper is reframing time series motif discovery as an anytime multimodal optimization task. This means the algorithm aims to find the best solutions (motifs) and can provide progressively better results over time, rather than needing to complete a full search.

The proposed algorithm, SWARMMOTIF, is based on Particle Swarm Optimization (PSO). Here's how it works:

  • PSO Foundation: PSO is a population-based metaheuristic that searches for optimal solutions by having a swarm of "particles" explore a search space. Each particle represents a potential motif candidate, and its "fitness" is determined by a dissimilarity measure between segments.
  • Anytime Nature: SWARMMOTIF is designed as an anytime algorithm. It continuously updates a set of candidate motifs, allowing users to retrieve good results at any point during its execution, even if the absolute best motifs haven't been found yet.
  • Multimodal Optimization: The search space for time series motifs is inherently multimodal (having multiple "valleys" or local optima). SWARMMOTIF uses techniques like multiple reinitializations on stagnation and "local memories" to effectively explore these complex landscapes and avoid getting stuck in suboptimal solutions.
  • Flexibility: A key advantage is its ability to use any dissimilarity measure (like Euclidean distance or Dynamic Time Warping) as its fitness function. It also naturally handles motifs of different lengths without requiring explicit segment length parameters.

Datasets

The paper evaluates SWARMMOTIF on nine diverse real-world time series datasets, chosen to represent various domains, lengths, and sampling rates. These include:

  • DOWJONES: Daily closing values of the Dow Jones average.
  • CARCOUNT: Number of cars measured on a freeway ramp.
  • INSECT: Electrical penetration graph of a beet leafhopper.
  • EEG: Electroencephalogram data from a sleeping patient.
  • FIELDRECORDING: Spectral centroid of a field recording.
  • WIND: Wind speed data.
  • POWER: Household electric power consumption.
  • EOG: Electrooculogram tracking eye movements.
  • RANDOM WALK: A synthetically generated random walk time series.

Four of these datasets (DOWJONES, INSECT, EEG, and POWER) have been used in previous motif discovery studies, providing a basis for comparison. The remaining five are introduced as new benchmarks for this task.

Key Insights and Ideas

  • Reframing Motif Discovery: The most significant insight is the successful application of an "anytime multimodal optimization" framework to time series motif discovery. This perspective unlocks new algorithmic possibilities.
  • PSO's Suitability: Particle Swarm Optimization, with its population-based exploration and ability to handle multimodal search spaces, is a surprisingly effective tool for this problem.
  • Anytime Performance is Crucial: For large time series datasets, being able to get "good enough" results quickly is often more practical than waiting for a perfect, exhaustive search. SWARMMOTIF excels here.
  • Flexibility is Key: The ability to use arbitrary dissimilarity measures and handle variable-length motifs without explicit parameterization is a major advantage over many existing methods.
  • Robustness to Parameters: The authors found that SWARMMOTIF's performance is remarkably stable across different parameter settings (topology, number of particles, stagnation threshold, constriction constant), making it largely "parameter-free" from a user's perspective.

Key Results

  • Speed: SWARMMOTIF achieves comparable motif similarities to the state-of-the-art MOEN algorithm but is 14 to over 1000 times faster across the tested datasets.
  • Accuracy: The algorithm consistently retrieves motifs whose dissimilarities are statistically indistinguishable from the true exact motifs (M*) within a short execution time.
  • Memory Efficiency: SWARMMOTIF uses minimal memory, primarily storing the time series itself and a small data structure for candidate motifs.
  • Flexibility Demonstrated: The paper shows that SWARMMOTIF can handle variable-length motifs and is robust to different dissimilarity measures.
  • Parameter Robustness: Experiments showed that most parameter choices had little to no significant impact on performance, highlighting the algorithm's stability.

Limitations and Future Work

  • Hypothesis on Particle Count: The authors hypothesize that using a smaller number of particles (κ) might lead to SWARMMOTIF's results overlapping with the true exact motifs (M*) even earlier. This is suggested as future work.
  • Exploration of Other Multimodal Algorithms: The paper suggests that multimodal optimization algorithms in general are a promising direction for time series analysis and mining.
  • Broader Applications: The authors believe their approach can be extended to other time series tasks like querying for segments of unknown length or determining optimal alignments.
  • Computational Challenges: The paper acknowledges that the search spaces for time series problems can be challenging for evolutionary computation, and they look forward to exploring these challenges further.

Summary updated

Abstract

Efficiently finding similar segments or motifs in time series data is a fundamental task that, due to the ubiquity of these data, is present in a wide range of domains and situations. Because of this, countless solutions have been devised but, to date, none of them seems to be fully satisfactory and flexible. In this article, we propose an innovative standpoint and present a solution coming from it: an anytime multimodal optimization algorithm for time series motif discovery based on particle swarms. By considering data from a variety of domains, we show that this solution is extremely competitive when compared to the state-of-the-art, obtaining comparable motifs in considerably less time using minimal memory. In addition, we show that it is robust to different implementation choices and see that it offers an unprecedented degree of flexibility with regard to the task. All these qualities make the presented solution stand out as one of the most prominent candidates for motif discovery in long time series streams. Besides, we believe the proposed standpoint can be exploited in further time series analysis and mining tasks, widening the scope of research and potentially yielding novel effective solutions.
BibTeX
@article{serra2016particle,
  author = {Joan Serrà and Josep Lluís Arcos},
  title = {{Particle swarm optimization for time series motif discovery}},
  journal = {Knowledge-Based Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=qVrrJSkPxJ},
}
Figure