1# EWMA [![GoDoc](https://godoc.org/github.com/VividCortex/ewma?status.svg)](https://godoc.org/github.com/VividCortex/ewma) ![Build Status](https://circleci.com/gh/VividCortex/moving_average.png?circle-token=1459fa37f9ca0e50cef05d1963146d96d47ea523) 2 3This repo provides Exponentially Weighted Moving Average algorithms, or EWMAs for short, [based on our 4Quantifying Abnormal Behavior talk](https://vividcortex.com/blog/2013/07/23/a-fast-go-library-for-exponential-moving-averages/). 5 6### Exponentially Weighted Moving Average 7 8An exponentially weighted moving average is a way to continuously compute a type of 9average for a series of numbers, as the numbers arrive. After a value in the series is 10added to the average, its weight in the average decreases exponentially over time. This 11biases the average towards more recent data. EWMAs are useful for several reasons, chiefly 12their inexpensive computational and memory cost, as well as the fact that they represent 13the recent central tendency of the series of values. 14 15The EWMA algorithm requires a decay factor, alpha. The larger the alpha, the more the average 16is biased towards recent history. The alpha must be between 0 and 1, and is typically 17a fairly small number, such as 0.04. We will discuss the choice of alpha later. 18 19The algorithm works thus, in pseudocode: 20 211. Multiply the next number in the series by alpha. 222. Multiply the current value of the average by 1 minus alpha. 233. Add the result of steps 1 and 2, and store it as the new current value of the average. 244. Repeat for each number in the series. 25 26There are special-case behaviors for how to initialize the current value, and these vary 27between implementations. One approach is to start with the first value in the series; 28another is to average the first 10 or so values in the series using an arithmetic average, 29and then begin the incremental updating of the average. Each method has pros and cons. 30 31It may help to look at it pictorially. Suppose the series has five numbers, and we choose 32alpha to be 0.50 for simplicity. Here's the series, with numbers in the neighborhood of 300. 33 34![Data Series](https://user-images.githubusercontent.com/279875/28242350-463289a2-6977-11e7-88ca-fd778ccef1f0.png) 35 36Now let's take the moving average of those numbers. First we set the average to the value 37of the first number. 38 39![EWMA Step 1](https://user-images.githubusercontent.com/279875/28242353-464c96bc-6977-11e7-9981-dc4e0789c7ba.png) 40 41Next we multiply the next number by alpha, multiply the current value by 1-alpha, and add 42them to generate a new value. 43 44![EWMA Step 2](https://user-images.githubusercontent.com/279875/28242351-464abefa-6977-11e7-95d0-43900f29bef2.png) 45 46This continues until we are done. 47 48![EWMA Step N](https://user-images.githubusercontent.com/279875/28242352-464c58f0-6977-11e7-8cd0-e01e4efaac7f.png) 49 50Notice how each of the values in the series decays by half each time a new value 51is added, and the top of the bars in the lower portion of the image represents the 52size of the moving average. It is a smoothed, or low-pass, average of the original 53series. 54 55For further reading, see [Exponentially weighted moving average](http://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) on wikipedia. 56 57### Choosing Alpha 58 59Consider a fixed-size sliding-window moving average (not an exponentially weighted moving average) 60that averages over the previous N samples. What is the average age of each sample? It is N/2. 61 62Now suppose that you wish to construct a EWMA whose samples have the same average age. The formula 63to compute the alpha required for this is: alpha = 2/(N+1). Proof is in the book 64"Production and Operations Analysis" by Steven Nahmias. 65 66So, for example, if you have a time-series with samples once per second, and you want to get the 67moving average over the previous minute, you should use an alpha of .032786885. This, by the way, 68is the constant alpha used for this repository's SimpleEWMA. 69 70### Implementations 71 72This repository contains two implementations of the EWMA algorithm, with different properties. 73 74The implementations all conform to the MovingAverage interface, and the constructor returns 75that type. 76 77Current implementations assume an implicit time interval of 1.0 between every sample added. 78That is, the passage of time is treated as though it's the same as the arrival of samples. 79If you need time-based decay when samples are not arriving precisely at set intervals, then 80this package will not support your needs at present. 81 82#### SimpleEWMA 83 84A SimpleEWMA is designed for low CPU and memory consumption. It **will** have different behavior than the VariableEWMA 85for multiple reasons. It has no warm-up period and it uses a constant 86decay. These properties let it use less memory. It will also behave 87differently when it's equal to zero, which is assumed to mean 88uninitialized, so if a value is likely to actually become zero over time, 89then any non-zero value will cause a sharp jump instead of a small change. 90 91#### VariableEWMA 92 93Unlike SimpleEWMA, this supports a custom age which must be stored, and thus uses more memory. 94It also has a "warmup" time when you start adding values to it. It will report a value of 0.0 95until you have added the required number of samples to it. It uses some memory to store the 96number of samples added to it. As a result it uses a little over twice the memory of SimpleEWMA. 97 98## Usage 99 100### API Documentation 101 102View the GoDoc generated documentation [here](http://godoc.org/github.com/VividCortex/ewma). 103 104```go 105package main 106import "github.com/VividCortex/ewma" 107 108func main() { 109 samples := [100]float64{ 110 4599, 5711, 4746, 4621, 5037, 4218, 4925, 4281, 5207, 5203, 5594, 5149, 111 } 112 113 e := ewma.NewMovingAverage() //=> Returns a SimpleEWMA if called without params 114 a := ewma.NewMovingAverage(5) //=> returns a VariableEWMA with a decay of 2 / (5 + 1) 115 116 for _, f := range samples { 117 e.Add(f) 118 a.Add(f) 119 } 120 121 e.Value() //=> 13.577404704631077 122 a.Value() //=> 1.5806140565521463e-12 123} 124``` 125 126## Contributing 127 128We only accept pull requests for minor fixes or improvements. This includes: 129 130* Small bug fixes 131* Typos 132* Documentation or comments 133 134Please open issues to discuss new features. Pull requests for new features will be rejected, 135so we recommend forking the repository and making changes in your fork for your use case. 136 137## License 138 139This repository is Copyright (c) 2013 VividCortex, Inc. All rights reserved. 140It is licensed under the MIT license. Please see the LICENSE file for applicable license terms. 141