Implementation of Holt-Winters algorithms in Python 2

holtwinters.py

#The MIT License (MIT)
#
#Copyright (c) 2015 Andre Queiroz
#
#Permission is hereby granted, free of charge, to any person obtaining a copy
#of this software and associated documentation files (the "Software"), to deal
#in the Software without restriction, including without limitation the rights
#to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
#copies of the Software, and to permit persons to whom the Software is
#furnished to do so, subject to the following conditions:
#
#The above copyright notice and this permission notice shall be included in
#all copies or substantial portions of the Software.
#
#THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
#IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
#FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
#AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
#LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
#OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
#THE SOFTWARE.
#
# Holt-Winters algorithms to forecasting
# Coded in Python 2 by: Andre Queiroz
# Description: This module contains three exponential smoothing algorithms. They are Holt's linear trend method and Holt-Winters seasonal methods (additive and multiplicative).
# References:
#  Hyndman, R. J.; Athanasopoulos, G. (2013) Forecasting: principles and practice. http://otexts.com/fpp/. Accessed on 07/03/2013.
#  Byrd, R. H.; Lu, P.; Nocedal, J. A Limited Memory Algorithm for Bound Constrained Optimization, (1995), SIAM Journal on Scientific and Statistical Computing, 16, 5, pp. 1190-1208.

from __future__ import division
from sys import exit
from math import sqrt
from numpy import array
from scipy.optimize import fmin_l_bfgs_b

def RMSE(params, *args):

	Y = args[0]
	type = args[1]
	rmse = 0

	if type == 'linear':

		alpha, beta = params
		a = [Y[0]]
		b = [Y[1] - Y[0]]
		y = [a[0] + b[0]]

		for i in range(len(Y)):

			a.append(alpha * Y[i] + (1 - alpha) * (a[i] + b[i]))
			b.append(beta * (a[i + 1] - a[i]) + (1 - beta) * b[i])
			y.append(a[i + 1] + b[i + 1])

	else:

		alpha, beta, gamma = params
		m = args[2]		
		a = [sum(Y[0:m]) / float(m)]
		b = [(sum(Y[m:2 * m]) - sum(Y[0:m])) / m ** 2]

		if type == 'additive':

			s = [Y[i] - a[0] for i in range(m)]
			y = [a[0] + b[0] + s[0]]

			for i in range(len(Y)):

				a.append(alpha * (Y[i] - s[i]) + (1 - alpha) * (a[i] + b[i]))
				b.append(beta * (a[i + 1] - a[i]) + (1 - beta) * b[i])
				s.append(gamma * (Y[i] - a[i] - b[i]) + (1 - gamma) * s[i])
				y.append(a[i + 1] + b[i + 1] + s[i + 1])

		elif type == 'multiplicative':

			s = [Y[i] / a[0] for i in range(m)]
			y = [(a[0] + b[0]) * s[0]]

			for i in range(len(Y)):

				a.append(alpha * (Y[i] / s[i]) + (1 - alpha) * (a[i] + b[i]))
				b.append(beta * (a[i + 1] - a[i]) + (1 - beta) * b[i])
				s.append(gamma * (Y[i] / (a[i] + b[i])) + (1 - gamma) * s[i])
				y.append((a[i + 1] + b[i + 1]) * s[i + 1])

		else:

			exit('Type must be either linear, additive or multiplicative')
		
	rmse = sqrt(sum([(m - n) ** 2 for m, n in zip(Y, y[:-1])]) / len(Y))

	return rmse

def linear(x, fc, alpha = None, beta = None):

	Y = x[:]

	if (alpha == None or beta == None):

		initial_values = array([0.3, 0.1])
		boundaries = [(0, 1), (0, 1)]
		type = 'linear'

		parameters = fmin_l_bfgs_b(RMSE, x0 = initial_values, args = (Y, type), bounds = boundaries, approx_grad = True)
		alpha, beta = parameters[0]

	a = [Y[0]]
	b = [Y[1] - Y[0]]
	y = [a[0] + b[0]]
	rmse = 0

	for i in range(len(Y) + fc):

		if i == len(Y):
			Y.append(a[-1] + b[-1])

		a.append(alpha * Y[i] + (1 - alpha) * (a[i] + b[i]))
		b.append(beta * (a[i + 1] - a[i]) + (1 - beta) * b[i])
		y.append(a[i + 1] + b[i + 1])

	rmse = sqrt(sum([(m - n) ** 2 for m, n in zip(Y[:-fc], y[:-fc - 1])]) / len(Y[:-fc]))

	return Y[-fc:], alpha, beta, rmse

def additive(x, m, fc, alpha = None, beta = None, gamma = None):

	Y = x[:]

	if (alpha == None or beta == None or gamma == None):

		initial_values = array([0.3, 0.1, 0.1])
		boundaries = [(0, 1), (0, 1), (0, 1)]
		type = 'additive'

		parameters = fmin_l_bfgs_b(RMSE, x0 = initial_values, args = (Y, type, m), bounds = boundaries, approx_grad = True)
		alpha, beta, gamma = parameters[0]

	a = [sum(Y[0:m]) / float(m)]
	b = [(sum(Y[m:2 * m]) - sum(Y[0:m])) / m ** 2]
	s = [Y[i] - a[0] for i in range(m)]
	y = [a[0] + b[0] + s[0]]
	rmse = 0

	for i in range(len(Y) + fc):

		if i == len(Y):
			Y.append(a[-1] + b[-1] + s[-m])

		a.append(alpha * (Y[i] - s[i]) + (1 - alpha) * (a[i] + b[i]))
		b.append(beta * (a[i + 1] - a[i]) + (1 - beta) * b[i])
		s.append(gamma * (Y[i] - a[i] - b[i]) + (1 - gamma) * s[i])
		y.append(a[i + 1] + b[i + 1] + s[i + 1])

	rmse = sqrt(sum([(m - n) ** 2 for m, n in zip(Y[:-fc], y[:-fc - 1])]) / len(Y[:-fc]))

	return Y[-fc:], alpha, beta, gamma, rmse

def multiplicative(x, m, fc, alpha = None, beta = None, gamma = None):

	Y = x[:]

	if (alpha == None or beta == None or gamma == None):

		initial_values = array([0.0, 1.0, 0.0])
		boundaries = [(0, 1), (0, 1), (0, 1)]
		type = 'multiplicative'

		parameters = fmin_l_bfgs_b(RMSE, x0 = initial_values, args = (Y, type, m), bounds = boundaries, approx_grad = True)
		alpha, beta, gamma = parameters[0]

	a = [sum(Y[0:m]) / float(m)]
	b = [(sum(Y[m:2 * m]) - sum(Y[0:m])) / m ** 2]
	s = [Y[i] / a[0] for i in range(m)]
	y = [(a[0] + b[0]) * s[0]]
	rmse = 0

	for i in range(len(Y) + fc):

		if i == len(Y):
			Y.append((a[-1] + b[-1]) * s[-m])

		a.append(alpha * (Y[i] / s[i]) + (1 - alpha) * (a[i] + b[i]))
		b.append(beta * (a[i + 1] - a[i]) + (1 - beta) * b[i])
		s.append(gamma * (Y[i] / (a[i] + b[i])) + (1 - gamma) * s[i])
		y.append((a[i + 1] + b[i + 1]) * s[i + 1])

	rmse = sqrt(sum([(m - n) ** 2 for m, n in zip(Y[:-fc], y[:-fc - 1])]) / len(Y[:-fc]))

	return Y[-fc:], alpha, beta, gamma, rmse

This looks great -- Holt Winters with Alpha, Beta, Gamma optimization taking advantage of Scipy optimzation. This seems to be the most complete Python-based Holt Winters I could find.

Have you or anyone had experience using this?

Nice implementation. Exactly what I was looking for.
Thanks mate.

Dear andrequeiroz,
Actually need more help.
Is there any java implementation of the same. ?

Thanks

A. what exactly do "x", "m", "fc" represent?
B. Can this handle unevenly spaced time points? Thanks!

After digging into the code a bit
A. "x" is a list of data values (not a numpy array), "m" is the periodicity of the data (i.e., the number of points per period--or something of this nature), "fc" is the number of points to forecast into the future.
B. The above implementation only deals in evenly spaced data. Tomas Hanzak has done some work (for his dissertation) on implementing Holt Winters for unevenly spaced data. He has implemented it in the DMITS software (contact him directly about getting a copy).

Note: there is a minor bug in the trend initialization code (which appears in multiple places) when running in python 2 -- it's doing integer division and should be doing float division. For example:

b = [(sum(Y[m:2 * m]) - sum(Y[0:m])) / m ** 2]
# easy fix, should be something like:
b = [(sum(Y[m:2 * m]) - sum(Y[0:m])) / float(m ** 2)]

Note: in the multiplicative RMSE, the formula for y is copy-paste-mistaken (line 61).
It should be

 y.append((a[i + 1] + b[i + 1])* s[i + 1])

to match the one in the actual model (line 151).
I forked it.

nice! But i want to know weather can you give a example for the newer.

Can someone explain the logic of this? This is the initialization of the trend in the cases of additive or multiplicative but the division by m squared doesn't make sense. Should it not be m_2 (m times two) instead of m_*2 (m squared)?

b = [(sum(Y[m:2 * m]) - sum(Y[0:m])) / float(m ** 2)]

For a small self-contained example of Holt-Winters on synthetic ECG data,
see https://gist.github.com/denis-bz/85795665a261c14e5c05
It's NOT based on Andre's holtwinters.py, no optimization at all, but may help understanding.

(Bytheway, from __future__ import division makes e.g. 1/2 == 0.5, not 0, so you hardly ever need float() .)

Thanks everyone for feedback. I did all the suggested corrections. :)

Nice, saved me a load of effort! I like the use of L_BFGS too.

Hi, I mentioned this implementation in a stackoverflow answer here - thanks for the code! I notice as well that there has been interest in incorporating it into statsmodels here. I was wondering about the license on your code - can you (do you want to?) license it under a free software license?

Hi @rsnape I'm glad this code has been proved itself useful. I licensed it under the MIT license, so anyone can use it or modify it according to their needs. :)

hi denis-bz

your link https://gist.github.com/denis-bz/85795665a261c14e5c05 is broken. appreciate if you can provide another. thnx in advance.

Here's Holt-Winters implemented for IPython / Jupyter notebook / pandas: https://github.com/rsvp/fecon235/blob/master/lib/yi_timeseries.py -- which uses numpy and also handles DataFrame argument. It's Python 2 and 3 compatible, so thus it will work under both Python kernels for Jupyter. We use it for financial economics, see https://git.io/fecon235 for topics which use Holt-Winters for smoothing and forecasting. Its license is BSD.

Robust parameters are discussed in: Sarah Gelper, 2007, Robust Forecasting with Exponential and Holt-Winters smoothing -- which are adopted as default parameters. However, the alpha and beta can be optimized given specific data. The tests for the modules show numerically how the various functions are validated. Error bounds are included in h-step ahead forecast().

---

2018 Addendum

The fecon235 source code was refactored in https://git.io/fecon236

Here's the specific module for Holt-Winters:
https://github.com/MathSci/fecon236/blob/master/fecon236/tsa/holtwinters.py

And the tests give some numerical examples:
https://github.com/MathSci/fecon236/blob/master/tests/test_holtwinters.py

... requires at least Python 2.7 or Python 3.4.

Hi Andre,

I believe that s[i] should be changed to s[i-m+1] in lines 69, 71, 81, 83, 149, 151, 182, 184 refer to Hyndman otext https://www.otexts.org/fpp/7/5

for a more robust initialization of the seasonal and trend components, there's seasonal

Hi Andre,

I just tried using your optimizing approach to initialize my params for additive models and unfortunately it always gives me params like alpha=1, beta=0, gamma=0. I'm guessing it happens because in this way, it fitted your training dataset perfectly. But for forecasting, since you will no longer have actual data points, you will definitely need beta and gamma to be nozeros. Have you ever thought about it?

Thanks

Y = args[0] type = args[1] rmse = 0

What does Y stand for?

I tried using your implementation for multiplicative models and passed Y=(2,3,4,5,6,3,4,5,76,7,4,3), tupl=(Y,'multiplicative',1) and multiplicative(y,4,1) however there is an indexerror= tuple index out of range for a.append(alpha * (Y[i] / s[i-m+1]) + (1 - alpha) * (a[i] + b[i]))

Am I missing something?

Hello,

I haven't tried using the code yet, but I have problem understanding why do the methods return Y[-fc]. Isn't Y just the data we have passed (with one appended value for whatever reason?) and y the prediction we are making? If that is the case, shouldn't y[-fc:] be the returned array? Any help appreciated.

@andrequeiroz Hi, i tried to use the code but i was not succesful. Could you please explain further the variables needed for each function ?
Use case: I am trying to predict the values of a raster based on the values of raster files of previous time periods.

Thanks in advance!!!

Also fmin_l_bfgs_b is deprecated according to Scipy doc

The specific optimization method interfaces below in this subsection are not recommended for use in new scripts; all of these methods are accessible via a newer, more consistent interface provided by the functions above.

Hello,
This code is great! But I have some questions, the form in code " s.append(gamma * (Y[i] / (a[i] + b[i])) + (1 - gamma) * s[i]) " , in some paper and wikipedia the form is " gamma * (Y[i] / a[i] ) + (1 - gamma) * s[i] ) ", are both forms all ok? Am I missing something?

@arturoramos, that is the average of the slope , there is y(m+1) -y(1)/m for slope, then average those need divide another m

how to implementing or load my data with this program sir? i need your help.. thx

Can anyone help in using this code to create fit and predict module which can be saved as a pickle file after fitting?