Problem Statement
Consider a time series
X = {xt ; t = 1, ... , N}
where t is a time index and N is the total number of samples from a sensor. The goal is to discover items of interest, which in our case are potential underwater target trajectories. These time series are complex and often irregular, non-periodic and possibly even chaotic. Our method identifies temporal structures in the time series by first forming a reconstructed vector space from data samples, and then by using a genetic algorithm (GA) to search for optimal heterogeneous (i.e., varying dimension) pattern clusters that predict target trajectories.
Methodology
My proposed method involves three steps:
- vector space reconstruction
Given a set of Q data samples
form the vector
where xt is a column vector (and also a point in the vector space), t is an integer in the interval [(Q-1)τ +1, N] and τ is a time delay. Note that different cluster patterns may have different Q values.
- construct heterogeneous collections of temporal pattern clusters
Temporal patterns are open balls of radius δ in a (Q+1)-dimensional vector space. An objective function f maps a collection of pattern clusters C onto the real number line. This real number value orders pattern clusters according to their ability characterize target trajectories. (A trajectory is indicated whenever a point xt is within a cluster c ∈ C.)
- search for a single optimal temporal pattern cluster using a GA
The GA is a stochastic search algorithm that mimics evolutionary forces in nature to conduct searches in high-dimensional spaces. The objective function value f(C) indicates how well a collection of pattern clusters C can predict target trajectories.
In this research effort the GA must search for a collection of pattern clusters with the highest objective function value.
This research effort is funded by the Office of Naval Research.
