README.md
1# EWMA [](https://godoc.org/github.com/VividCortex/ewma) 
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
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
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
45
46This continues until we are done.
47
48
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
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}