Discovery of Driving Behavior Patterns - Smart Information Systems: Computational Intelligence for Real-Life Applications - page 322

n
r i

r
n

x i = x j (12.12)

n
r (

j = i − 1 ) + 1

i = 1 ... r , j = 1 ... n

The PAA dimensionality reduction is intuitive and simple, yet has been shown
to rival more sophisticated dimensionality reduction techniques like Fourier trans-
forms and wavelets [ 15 ]. Having transformed a time series database into PAA, we
can apply our proposed recurrence plot-based time series distance measure on the
reduced representation. Since the computational complexity of our RRR distance
measure is quadratic in the length n of the time series, reducing the original time
series to r dimensions leads to a performance improvement of factor

2 . In our

( n / r )

experiments on the real-life vehicular data we use a compression rate of n 10,

which correspond to a speedup of two orders of magnitude or rather 100 times less
matrix entries to compute. However, this approach comes with the cost of missing
recurrences [ 23 ].

/ r =

12.8 Adjustment Window Condition

Another approach to reduce the computational complexity of our proposed recurrence
plot-based (RRR) time series distance measure is to constrain the number of cells
that are evaluated in the distance matrix [ 30 ]. Constraints have been successfully
applied to the Dynamic Time Warping (DTW) distance to create tight lower bounds
which allow to prune similarity calculations [ 8 , 11 ]. The two most commonly used
constraints are the Itakura Parallelogram [ 6 ] and the Sakoe-Chiba Band [ 29 ], which
both speed up calculations by a constant factor, but still lead to quadratic complexity
if the window size is a linear function of the time series.

Given the formal definition of (joint) cross recurrence (see Eqs. 12.2 and 12.4 ),
the Sakoe-Chiba Band is an adjustment window condition which corresponds to the
fact that time-axis fluctuations in usual cases never causes a too excessive timing
difference [ 29 ]:

w

| i − j |≤ w (12.13)

d

∀

x i ,

∈ R , = ... , = ...

y j i 1 N j 1 M

In general, constraints work well in domains where time series have only a small
variance, but perform poorly if time series are of events that start and stop at radically
different times [ 30 ]. Since this study considers time series that exhibit recurring
patterns at arbitrary positions, we refrain from applying constraints for the data
under study.