graphite-dev team mailing list archive

[Matthew Graham <mdg149@xxxxxxxxx>]

Matthew Graham has proposed merging lp:~lapsu/graphite/holtwinters into lp:graphite.

Requested reviews:
  graphite-dev (graphite-dev)

For more details, see:
https://code.launchpad.net/~lapsu/graphite/holtwinters/+merge/63881

Holt-Winters Confidence Bands and Aberration Graph based on those confidence bands.
Applied this approach from RRDtool as render functions. http://www.usenix.org/events/lisa2000/full_papers/brutlag/brutlag_html/index.html
-- 
https://code.launchpad.net/~lapsu/graphite/holtwinters/+merge/63881
Your team graphite-dev is requested to review the proposed merge of lp:~lapsu/graphite/holtwinters into lp:graphite.

=== modified file 'webapp/content/js/composer_widgets.js'
--- webapp/content/js/composer_widgets.js	2011-06-06 08:36:15 +0000
+++ webapp/content/js/composer_widgets.js	2011-06-08 15:21:04 +0000
@@ -902,6 +902,9 @@
       menu: [
         {text: 'Moving Average', handler: applyFuncToEachWithInput('movingAverage', 'Moving average for the last ___ data points')},
         {text: 'Moving Standard Deviation', handler: applyFuncToEachWithInput('stdev', 'Moving standard deviation for the last ___ data points')},
+        {text: 'Holt-Winters Forecast', handler: this.applyFuncToEach('holtWintersForecast')},
+        {text: 'Holt-Winters Confidence Bands', handler: this.applyFuncToEach('holtWintersConfidenceBands')},
+        {text: 'Holt-Winters Aberration', handler: this.applyFuncToEach('holtWintersAberration')},
         {text: 'As Percent', handler: applyFuncToEachWithInput('asPercent', 'Please enter the value that corresponds to 100%')},
         {text: 'Difference (of 2 series)', handler: applyFuncToAll('diffSeries')},
         {text: 'Ratio (of 2 series)', handler: applyFuncToAll('divideSeries')}

=== modified file 'webapp/graphite/render/functions.py'
--- webapp/graphite/render/functions.py	2011-04-05 18:28:40 +0000
+++ webapp/graphite/render/functions.py	2011-06-08 15:21:04 +0000
@@ -529,6 +529,213 @@
   return seriesList
 
 
+def holtWintersIntercept(alpha,actual,last_season,last_intercept,last_slope):
+  return alpha * (actual - last_season) \
+          + (1 - alpha) * (last_intercept + last_slope)
+
+def holtWintersSlope(beta,intercept,last_intercept,last_slope):
+  return beta * (intercept - last_intercept) + (1 - beta) * last_slope
+
+def holtWintersSeasonal(gamma,actual,intercept,last_season):
+  return gamma * (actual - intercept) + (1 - gamma) * last_season
+
+def holtWintersDeviation(gamma,actual,prediction,last_seasonal_dev):
+  return gamma * math.fabs(actual - prediction) + (1 - gamma) * last_seasonal_dev
+
+def holtWintersAnalysis(series, bootstrap=None):
+  alpha = gamma = 0.1
+  beta = 0.0035
+  season_length = (24*60*60) / series.step
+  intercept = 0
+  slope = 0
+  pred = 0
+  intercepts = list()
+  slopes = list()
+  seasonals = list()
+  predictions = list()
+  deviations = list()
+
+  def getLastSeasonal(i):
+    j = i - season_length
+    if j >= 0:
+      return seasonals[j]
+    if bootstrap:
+      return bootstrap['seasonals'][j]
+    return 0
+
+  def getLastDeviation(i):
+    j = i - season_length
+    if j >= 0:
+      return deviations[j]
+    if bootstrap:
+      return bootstrap['deviations'][j]
+    return 0
+
+  last_seasonal = 0
+  last_seasonal_dev = 0
+  next_last_seasonal = 0
+  next_pred = None
+
+  for i,actual in enumerate(series):
+    if actual is None:
+      # missing input values break all the math
+      # do the best we can and move on
+      intercepts.append(None)
+      slopes.append(0)
+      seasonals.append(0)
+      predictions.append(next_pred)
+      deviations.append(0)
+      next_pred = None
+      continue
+
+    if i == 0:
+      if bootstrap:
+        last_intercept = bootstrap['intercepts'][-1]
+        last_slope = bootstrap['slopes'][-1]
+        prediction = bootstrap['predictions'][-1]
+      else:
+        last_intercept = actual
+        last_slope = 0
+        # seed the first prediction as the first actual
+        prediction = actual
+    else:
+      last_intercept = intercepts[-1]
+      last_slope = slopes[-1]
+      if last_intercept is None:
+        last_intercept = actual
+      prediction = next_pred
+
+    last_seasonal = getLastSeasonal(i)
+    next_last_seasonal = getLastSeasonal(i+1)
+    last_seasonal_dev = getLastDeviation(i)
+
+    intercept = holtWintersIntercept(alpha,actual,last_seasonal
+            ,last_intercept,last_slope)
+    slope = holtWintersSlope(beta,intercept,last_intercept,last_slope)
+    seasonal = holtWintersSeasonal(gamma,actual,intercept,last_seasonal)
+    next_pred = intercept + slope + next_last_seasonal
+    deviation = holtWintersDeviation(gamma,actual,prediction,last_seasonal_dev)
+
+    intercepts.append(intercept)
+    slopes.append(slope)
+    seasonals.append(seasonal)
+    predictions.append(prediction)
+    deviations.append(deviation)
+
+  # make the new forecast series
+  forecastName = "holtWintersForecast(%s)" % series.name
+  forecastSeries = TimeSeries(forecastName, series.start, series.end
+    , series.step, predictions)
+  forecastSeries.pathExpression = forecastName
+
+  # make the new deviation series
+  deviationName = "holtWintersDeviation(%s)" % series.name
+  deviationSeries = TimeSeries(deviationName, series.start, series.end
+          , series.step, deviations)
+  deviationSeries.pathExpression = deviationName
+
+  results = { 'predictions': forecastSeries
+        , 'deviations': deviationSeries
+        , 'intercepts': intercepts
+        , 'slopes': slopes
+        , 'seasonals': seasonals
+        }
+  return results
+
+def holtWintersFetchBootstrap(requestContext, seriesPath):
+  previousContext = requestContext.copy()
+  # go back 1 week to get a solid bootstrap
+  previousContext['startTime'] = requestContext['startTime'] - timedelta(7)
+  previousContext['endTime'] = requestContext['startTime']
+  bootstrapPath = "holtWintersBootstrap(%s)" % seriesPath
+  previousResults = evaluateTarget(previousContext, bootstrapPath)
+  return {'predictions': previousResults[0]
+        , 'deviations': previousResults[1]
+        , 'intercepts': previousResults[2]
+        , 'slopes': previousResults[3]
+        , 'seasonals': previousResults[4]
+        }
+
+def holtWintersBootstrap(requestContext, seriesList):
+  results = []
+  for series in seriesList:
+    bootstrap = holtWintersAnalysis(series)
+    interceptSeries = TimeSeries('intercepts', series.start, series.end
+            , series.step, bootstrap['intercepts'])
+    slopeSeries = TimeSeries('slopes', series.start, series.end
+            , series.step, bootstrap['slopes'])
+    seasonalSeries = TimeSeries('seasonals', series.start, series.end
+            , series.step, bootstrap['seasonals'])
+
+    results.append(bootstrap['predictions'])
+    results.append(bootstrap['deviations'])
+    results.append(interceptSeries)
+    results.append(slopeSeries)
+    results.append(seasonalSeries)
+  return results
+
+def holtWintersForecast(requestContext, seriesList):
+  results = []
+  for series in seriesList:
+    bootstrap = holtWintersFetchBootstrap(requestContext, series.pathExpression)
+    analysis = holtWintersAnalysis(series, bootstrap)
+    results.append(analysis['predictions'])
+    #results.append(analysis['deviations'])
+  return results
+
+def holtWintersConfidenceBands(requestContext, seriesList):
+  results = []
+  for series in seriesList:
+    bootstrap = holtWintersFetchBootstrap(requestContext, series.pathExpression)
+    analysis = holtWintersAnalysis(series, bootstrap)
+    forecast = analysis['predictions']
+    deviation = analysis['deviations']
+    seriesLength = len(series)
+    i = 0
+    upperBand = list()
+    lowerBand = list()
+    while i < seriesLength:
+      forecast_item = forecast[i]
+      deviation_item = deviation[i]
+      i = i + 1
+      if forecast_item is None or deviation_item is None:
+        upperBand.append(None)
+        lowerBand.append(None)
+      else:
+        scaled_deviation = 3 * deviation_item
+        upperBand.append(forecast_item + scaled_deviation)
+        lowerBand.append(forecast_item - scaled_deviation)
+    upperName = "holtWintersConfidenceUpper(%s)" % series.name
+    lowerName = "holtWintersConfidenceLower(%s)" % series.name
+    upperSeries = TimeSeries(upperName, series.start, series.end
+            , series.step, upperBand)
+    lowerSeries = TimeSeries(lowerName, series.start, series.end
+            , series.step, lowerBand)
+    results.append(upperSeries)
+    results.append(lowerSeries)
+  return results
+
+def holtWintersAberration(requestContext, seriesList):
+  results = []
+  for series in seriesList:
+    confidenceBands = holtWintersConfidenceBands(requestContext, [series])
+    upperBand = confidenceBands[0]
+    lowerBand = confidenceBands[1]
+    aberration = list()
+    for i, actual in enumerate(series):
+      if series[i] > upperBand[i]:
+        aberration.append(series[i] - upperBand[i])
+      elif series[i] < lowerBand[i]:
+        aberration.append(series[i] - lowerBand[i])
+      else:
+        aberration.append(0)
+
+    newName = "holtWintersAberration(%s)" % series.name
+    results.append(TimeSeries(newName, series.start, series.end
+            , series.step, aberration))
+  return results
+
+
 def drawAsInfinite(requestContext, seriesList):
   for series in seriesList:
     series.options['drawAsInfinite'] = True
@@ -745,6 +952,10 @@
   # Calculate functions
   'movingAverage' : movingAverage,
   'stdev' : stdev,
+  'holtWintersBootstrap': holtWintersBootstrap,
+  'holtWintersForecast': holtWintersForecast,
+  'holtWintersConfidenceBands': holtWintersConfidenceBands,
+  'holtWintersAberration': holtWintersAberration,
   'asPercent' : asPercent,
   'pct' : asPercent,