Home > R, Strategy, Trading Strategies > Time Series Matching with Dynamic Time Warping

Time Series Matching with Dynamic Time Warping

THIS IS NOT INVESTMENT ADVICE. The information is provided for informational purposes only.

In the Time Series Matching post, I used one to one mapping to the compute distance between the query(current pattern) and reference(historical time series). Following chart visualizes this concept. The distance is the sum of vertical lines.

An alternative way to map one time series to another is Dynamic Time Warping(DTW). DTW algorithm looks for minimum distance mapping between query and reference. Following chart visualizes one to many mapping possible with DTW.

To check if there a difference between simple one to one mapping and DTW, I will search for time series matches that are similar to the most recent 90 days of SPY in the last 10 years of history. Following code loads historical prices from Yahoo Fiance, setups the problem and computes Euclidean distance for the historical rolling window using the Systematic Investor Toolbox:

###############################################################################
# Load Systematic Investor Toolbox (SIT)
# http://systematicinvestor.wordpress.com/systematic-investor-toolbox/
###############################################################################
con = gzcon(url('http://www.systematicportfolio.com/sit.gz', 'rb'))
    source(con)
close(con)

	#*****************************************************************
	# Load historical data
	#****************************************************************** 
	load.packages('quantmod')	
	tickers = 'SPY'

	data = getSymbols(tickers, src = 'yahoo', from = '1950-01-01', auto.assign = F)

	#*****************************************************************
	# Euclidean distance, one to one mapping
	#****************************************************************** 
	obj = bt.matching.find(Cl(data), normalize.fn = normalize.mean, dist.fn = 'dist.euclidean', plot=T)

	matches = bt.matching.overlay(obj, plot.index=1:90, plot=T)

	layout(1:2)
	matches = bt.matching.overlay(obj, plot=T, layout=T)
	bt.matching.overlay.table(obj, matches, plot=T, layout=T)

Next, let’ examine the top 10 matches using Dynamic Time Warping distance. I will use the Dynamic Time Warping implementation from dtw package.

	#*****************************************************************
	# Dynamic time warping distance	
	#****************************************************************** 
	# http://en.wikipedia.org/wiki/Dynamic_time_warping
	# http://dtw.r-forge.r-project.org/
	#****************************************************************** 
	load.packages('dtw')

	obj = bt.matching.find(Cl(data), normalize.fn = normalize.mean, dist.fn = 'dist.DTW', plot=T)

	matches = bt.matching.overlay(obj, plot.index=1:90, plot=T)

	layout(1:2)
	matches = bt.matching.overlay(obj, plot=T, layout=T)
	bt.matching.overlay.table(obj, matches, plot=T, layout=T)

Both algorithms produced very similar matches and very similar predictions. I would use these predictions as an educated guess to market action going forward. So far, it looks like the market will not be going up in full throttle in the next 22 days.

To view the complete source code for this example, please have a look at the bt.matching.dtw.test() function in bt.test.r at github.

About these ads
Categories: R, Strategy, Trading Strategies
  1. Andrej Spiess
    January 21, 2012 at 9:36 am

    Hi,

    in this paper

    http://www.cs.rutgers.edu/~mlittman/courses/statai03/DDTW-2001.pdf

    the author’s describe using DTW on the derivative curve, making it less susceptible to differences in magnitude of the oroginal curves.
    Might be worth a try?

    Greets,
    Andrej

    • January 23, 2012 at 2:10 am

      Andrej,

      Thank you for pointing me to the Derivative Dynamic Time Warping. I like the concept and it is easy to model. Here is a small example of Derivative Dynamic Time Warping, in case you want to experiment:

      ###############################################################################
      # Load Systematic Investor Toolbox (SIT)
      # http://systematicinvestor.wordpress.com/systematic-investor-toolbox/
      ###############################################################################
      con = gzcon(url('http://www.systematicportfolio.com/sit.gz', 'rb'))
          source(con)
      close(con)
      
      	#*****************************************************************
      	# Load historical data
      	#****************************************************************** 
      	load.packages('quantmod')	
      	tickers = 'SPY'
      
      	data = getSymbols(tickers, src = 'yahoo', from = '1950-01-01', auto.assign = F)	
      
      	#*****************************************************************
      	# Setup DTW
      	#****************************************************************** 
      	load.packages('dtw')
      	
      	query = as.vector(coredata(last(Cl(data['2011::2011']), 60)))
      	reference = as.vector(coredata(last(Cl(data['2010::2010']), 60)))	
      	
      	#*****************************************************************
      	# Dynamic Time Warping 	
      	#****************************************************************** 
      	alignment = dtw(query, reference, keep=TRUE)
      
      	# plot
      	plot(alignment,main='DTW Alignment', type='two',off=20)
      	
      	#*****************************************************************
      	# Derivative Dynamic Time Warping by E.J. Keogh and M.J. Pazzani
      	# http://www.cs.rutgers.edu/~mlittman/courses/statai03/DDTW-2001.pdf
      	#****************************************************************** 
      	derivative.est <- function(x) {
      		x = as.vector(x)
      		n = len(x)
      		d = (( x - mlag(x) ) + ( mlag(x,-1)- mlag(x) ) / 2) / 2
      		d[1] = d[2]
      		d[n] = d[(n-1)]
      		d
      	}
      	
      	alignment0 = dtw(derivative.est(query), derivative.est(reference), keep=TRUE)
      	alignment$index1 = alignment0$index1
      	alignment$index2 = alignment0$index2
      
      	# plot	
      	plot(alignment,main='Derivative DTW Alignment', type='two',off=20)
      

  2. Pete
    January 23, 2012 at 3:17 am

    Interesting concept, and it might just work because a lot of traders will be subconsciously looking for patterns.

    Just something worth a try;
    1) Look at shorter time horizons (e.g. 5-10 days)
    2) Look at the profitability of trading on similar patterns in the past. I recall there being a paper that showed that trading strategies involving bollinger bands performed significantly better the more times the bands had acted as ‘support’ & ‘resistance’ levels in the recent past. A similar effect could be here; where traders have learnt to sport some patterns as ‘signals’ so that they’re much more likely to act on them than others.

    Let me know if you have any thoughts, I’ve added it to the list of things to try once my workstation is back from repairs. Thanks for the post and keep them coming!

  1. May 22, 2012 at 3:28 am
  2. October 13, 2013 at 9:32 pm
  3. August 15, 2014 at 7:53 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 240 other followers

%d bloggers like this: