Exponentially Weighted Moving Average algorithms for Go.

EWMA

GoDoc build codecov

This repo provides Exponentially Weighted Moving Average algorithms, or EWMAs for short, based on our Quantifying Abnormal Behavior talk.

Exponentially Weighted Moving Average

An exponentially weighted moving average is a way to continuously compute a type of average for a series of numbers, as the numbers arrive. After a value in the series is added to the average, its weight in the average decreases exponentially over time. This biases the average towards more recent data. EWMAs are useful for several reasons, chiefly their inexpensive computational and memory cost, as well as the fact that they represent the recent central tendency of the series of values.

The EWMA algorithm requires a decay factor, alpha. The larger the alpha, the more the average is biased towards recent history. The alpha must be between 0 and 1, and is typically a fairly small number, such as 0.04. We will discuss the choice of alpha later.

The algorithm works thus, in pseudocode:

  1. Multiply the next number in the series by alpha.
  2. Multiply the current value of the average by 1 minus alpha.
  3. Add the result of steps 1 and 2, and store it as the new current value of the average.
  4. Repeat for each number in the series.

There are special-case behaviors for how to initialize the current value, and these vary between implementations. One approach is to start with the first value in the series; another is to average the first 10 or so values in the series using an arithmetic average, and then begin the incremental updating of the average. Each method has pros and cons.

It may help to look at it pictorially. Suppose the series has five numbers, and we choose alpha to be 0.50 for simplicity. Here's the series, with numbers in the neighborhood of 300.

Data Series

Now let's take the moving average of those numbers. First we set the average to the value of the first number.

EWMA Step 1

Next we multiply the next number by alpha, multiply the current value by 1-alpha, and add them to generate a new value.

EWMA Step 2

This continues until we are done.

EWMA Step N

Notice how each of the values in the series decays by half each time a new value is added, and the top of the bars in the lower portion of the image represents the size of the moving average. It is a smoothed, or low-pass, average of the original series.

For further reading, see Exponentially weighted moving average on wikipedia.

Choosing Alpha

Consider a fixed-size sliding-window moving average (not an exponentially weighted moving average) that averages over the previous N samples. What is the average age of each sample? It is N/2.

Now suppose that you wish to construct a EWMA whose samples have the same average age. The formula to compute the alpha required for this is: alpha = 2/(N+1). Proof is in the book "Production and Operations Analysis" by Steven Nahmias.

So, for example, if you have a time-series with samples once per second, and you want to get the moving average over the previous minute, you should use an alpha of .032786885. This, by the way, is the constant alpha used for this repository's SimpleEWMA.

Implementations

This repository contains two implementations of the EWMA algorithm, with different properties.

The implementations all conform to the MovingAverage interface, and the constructor returns that type.

Current implementations assume an implicit time interval of 1.0 between every sample added. That is, the passage of time is treated as though it's the same as the arrival of samples. If you need time-based decay when samples are not arriving precisely at set intervals, then this package will not support your needs at present.

SimpleEWMA

A SimpleEWMA is designed for low CPU and memory consumption. It will have different behavior than the VariableEWMA for multiple reasons. It has no warm-up period and it uses a constant decay. These properties let it use less memory. It will also behave differently when it's equal to zero, which is assumed to mean uninitialized, so if a value is likely to actually become zero over time, then any non-zero value will cause a sharp jump instead of a small change.

VariableEWMA

Unlike SimpleEWMA, this supports a custom age which must be stored, and thus uses more memory. It also has a "warmup" time when you start adding values to it. It will report a value of 0.0 until you have added the required number of samples to it. It uses some memory to store the number of samples added to it. As a result it uses a little over twice the memory of SimpleEWMA.

Usage

API Documentation

View the GoDoc generated documentation here.

package main

import "github.com/VividCortex/ewma"

func main() {
	samples := [100]float64{
		4599, 5711, 4746, 4621, 5037, 4218, 4925, 4281, 5207, 5203, 5594, 5149,
	}

	e := ewma.NewMovingAverage()  //=> Returns a SimpleEWMA if called without params
	a := ewma.NewMovingAverage(5) //=> returns a VariableEWMA with a decay of 2 / (5 + 1)

	for _, f := range samples {
		e.Add(f)
		a.Add(f)
	}

	e.Value() //=> 13.577404704631077
	a.Value() //=> 1.5806140565521463e-12
}

Contributing

We only accept pull requests for minor fixes or improvements. This includes:

  • Small bug fixes
  • Typos
  • Documentation or comments

Please open issues to discuss new features. Pull requests for new features will be rejected, so we recommend forking the repository and making changes in your fork for your use case.

License

This repository is Copyright (c) 2013 VividCortex, Inc. All rights reserved. It is licensed under the MIT license. Please see the LICENSE file for applicable license terms.

Comments
  • Initialization fix for bug in SimpleEWMA

    Initialization fix for bug in SimpleEWMA

    When the value reaches 0 after starting (trivially if the first values are 0) the EWMA is deemed uninitialized, which leads to this:

    Sequence : 0, 1 MA = 1

    when what you really want is

    Sequence : 0, 1 MA = alpha

  • Test fail on arches ppc64le and s390x

    Test fail on arches ppc64le and s390x

    Hello,

    I am in the process of packaging ewma for Fedora but I encountered problems running the tests. On both ppc64le and s390x arches, the following test fails:

    + export GOPATH=/builddir/build/BUILDROOT/golang-github-VividCortex-ewma-0-0.1.git4cc8cc5.fc27.ppc64le//usr/share/gocode:/usr/share/gocode
    + GOPATH=/builddir/build/BUILDROOT/golang-github-VividCortex-ewma-0-0.1.git4cc8cc5.fc27.ppc64le//usr/share/gocode:/usr/share/gocode
    + go test -compiler gc -ldflags '' github.com/VividCortex/ewma
    --- FAIL: TestSimpleEWMA (0.00s)
    	ewma_test.go:26: e.Value() is 4734.500946466117, wanted 4734.500946466118
    --- FAIL: TestVariableEWMA (0.00s)
    	ewma_test.go:40: e.Value() is 4734.500946466117, wanted 4734.500946466118
    FAIL
    FAIL	github.com/VividCortex/ewma	0.018s
    

    Could you identify why there is a discrepancy in the value given versus the value expected, only on these two arches while others arches test are fine?

  • Configure WhiteSource for GitHub.com

    Configure WhiteSource for GitHub.com

    Welcome to WhiteSource for GitHub.com! This is an onboarding PR to help you understand and configure settings before WhiteSource starts scanning your repository for security vulnerabilities.

    :vertical_traffic_light: WhiteSource for GitHub.com will start scanning your repository only once you merge this Pull Request. To disable WhiteSource for GitHub.com, simply close this Pull Request.


    What to Expect

    This PR contains a '.whitesource' configuration file which can be customized to your needs. If no changes were applied to this file, WhiteSource for GitHub.com will use the default configuration.

    Before merging this PR, Make sure the Issues tab is enabled. Once you merge this PR, WhiteSource for GitHub.com will scan your repository and create a GitHub Issue for every vulnerability detected in your repository.

    If you do not want a GitHub Issue to be created for each detected vulnerability, you can edit the '.whitesource' file and set the 'minSeverityLevel' parameter to 'NONE'.

    If WhiteSource Remediate Workflow Rules are set on your repository (from the WhiteSource 'Integrate' tab), WhiteSource will also generate a fix Pull Request for relevant vulnerabilities.


    :question: Got questions? Check out WhiteSource for GitHub.com docs. If you need any further assistance then you can also request help here.

  • You lost slice[WARMUP_SAMPLES] item

    You lost slice[WARMUP_SAMPLES] item

    原程序丢失了计算序列中的slice[WARMUP_SAMPLES]项。

    package main

    import ( "fmt"

    "github.com/VividCortex/ewma"
    

    )

    func main() { samples := [12]float64{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10000, 11}

    e := ewma.NewMovingAverage()  //=> Returns a SimpleEWMA if called without params
    a := ewma.NewMovingAverage(5) //=> returns a VariableEWMA with a decay of 2 / (5 + 1)
    
    for _, f := range samples {
        e.Add(f)
        a.Add(f)
    }
    
    fmt.Println(e.Value())   //606.8771523549624
    fmt.Println(a.Value())   //6.666666666666667
    

    }

  • fix off by one error in VariableEWMA.Value() return

    fix off by one error in VariableEWMA.Value() return

    Fixes an off by one issue when returning values for VariableEWMA.

    For example if WARMUP_SAMPLES == 10, e.count gets incremented postfix in VariableEWMA.Add() the conditional in VariableEWMA.Value() would return the current e.value (sum of samples seen) on the 9th iteration rather than 0.0.

    This corrects the behaviour with the 10th iteration returning the mean of first 10 samples as expected.

    Test is included that verifies all values returned during warmup period are 0.0

  • Go 1.10: ewma_test.go:39: Errorf format %d has arg e.Value() of wrong type float64

    Go 1.10: ewma_test.go:39: Errorf format %d has arg e.Value() of wrong type float64

    github.com/VividCortex/ewma 1.1.1 does not pass unit tests with Go 1.10:

    + GOPATH=/builddir/build/BUILD/ewma-1.1.1/_build:/usr/share/gocode
    + go test -buildmode pie -compiler gc -ldflags '-extldflags '\''-Wl,-z,relro  '\'''
    # github.com/VividCortex/ewma
    ./ewma_test.go:39: Errorf format %d has arg e.Value() of wrong type float64
    ./ewma_test.go:53: Errorf format %d has arg e.Value() of wrong type float64
    ./ewma_test.go:83: Errorf format %d has arg e.Value() of wrong type float64
    FAIL    github.com/VividCortex/ewma [build failed]
    
  • Fix wrong format type in Errorf

    Fix wrong format type in Errorf

    I'm encountering new errors with Golang 1.10.rc2:

    + go test -buildmode pie -compiler gc -ldflags ' -extldflags '\''-Wl,-z,relro  -specs=/usr/lib/rpm/redhat/redhat-hardened-ld '\''' github.com/VividCortex/ewma
    # github.com/VividCortex/ewma
    ../../BUILDROOT/golang-github-VividCortex-ewma-1.1.1-2.fc28.x86_64/usr/share/gocode/src/github.com/VividCortex/ewma/ewma_test.go:39: Errorf format %d has arg e.Value() of wrong type float64
    ../../BUILDROOT/golang-github-VividCortex-ewma-1.1.1-2.fc28.x86_64/usr/share/gocode/src/github.com/VividCortex/ewma/ewma_test.go:53: Errorf format %d has arg e.Value() of wrong type float64
    ../../BUILDROOT/golang-github-VividCortex-ewma-1.1.1-2.fc28.x86_64/usr/share/gocode/src/github.com/VividCortex/ewma/ewma_test.go:83: Errorf format %d has arg e.Value() of wrong type float64
    FAIL	github.com/VividCortex/ewma [build failed]
    

    It seems the Errorf statement is expecting an integer number with %d, but in all case a float64 is provided. I propose to use %v instead.

  • Allow setting the EWMA's value

    Allow setting the EWMA's value

    For some purposes, it's important to be able to set the EWMA's value directly. For example, suppose you keep track of a EWMA and then save it to a database, and later retrieve it and continue to add more values. (We do this at VividCortex.)

    We should enhance the interface with an Add(float64) function, and implement these functions in our two public implementations. The semantics of Add should be to set the value and mark the EWMA as initialized, in case it has internal tracking of whether it's "warmed up" or not.

  • Inconsistency between doc and code

    Inconsistency between doc and code

    The readme says

    So, for example, if you have a time-series with samples once per second, and you want to get the moving average over the previous minute, you should use an alpha of .032786885. This, by the way, is the constant alpha used for this repository's SimpleEWMA.

    That alpha corresponds to N = 60, 2/(N+1) = 2/61 = .032786885.

    The actual code uses 2/31: https://github.com/VividCortex/ewma/blob/487e8c9fe1e218b64696ee0219903a3a40d0dc2b/ewma.go#L8-L14

    The readme may be using N with two different meanings in the section on "Choosing Alpha", but I don't think so. I think 2/31 is incorrect.

    The comment in the code is also inconsistent with the readme. The readme talks about "N samples", whereas the code talks about "average age".

    It's certainly possible I'm misunderstanding something.

  • Use *float for SimpleEWMA

    Use *float for SimpleEWMA

    These properties let it use less memory. It will also behave differently when it's equal to zero, which is assumed to mean uninitialized, so if a value is likely to actually become zero over time, then any non-zero value will cause a sharp jump instead of a small change.

    The disadvantages for SimpleEWMA like the sensitivity for 0 values could be solved by using *float64 for storing the value internally. Could do a PR if desired.

  • Minor docs fix

    Minor docs fix

    Was testing out the example snippet here and noticed the output was not as expected for a.Value(). I'm running go1.16.5 and I assume this is correct so submitted a docs fix. I ran the example code as shown from the readme but printed it.

    Here's the code:

    package main
    
    import (
    	"fmt"
    	"github.com/VividCortex/ewma"
    )
    
    func main() {
    	samples := [100]float64{
    		4599, 5711, 4746, 4621, 5037, 4218, 4925, 4281, 5207, 5203, 5594, 5149,
    	}
    
    	e := ewma.NewMovingAverage()  //=> Returns a SimpleEWMA if called without params
    	a := ewma.NewMovingAverage(5) //=> returns a VariableEWMA with a decay of 2 / (5 + 1)
    
    	for _, f := range samples {
    		e.Add(f)
    		a.Add(f)
    	}
    
    	fmt.Println(e.Value()) //=> 13.577404704631077
    	fmt.Println(a.Value()) //=> 1.5806140565521463e-12 <- fix here
    }
    

    Here's the output that I'm getting:

    $ go run main.go
    13.577404704631077
    1.6330366675026306e-12
    
  • Is this the same as exponential smoothing?

    Is this the same as exponential smoothing?

    Before you file an issue, please consider:

    We only accept pull requests for minor fixes or improvements. This includes:

    • Small bug fixes
    • Typos
    • Documentation or comments

    Please open issues to discuss new features. Pull requests for new features will be rejected, so we recommend forking the repository and making changes in your fork for your use case.

Package goraph implements graph data structure and algorithms.
Package goraph implements graph data structure and algorithms.

goraph Package goraph implements graph data structure and algorithms. go get -v gopkg.in/gyuho/goraph.v2; I have tutorials and visualizations of grap

Dec 20, 2022
A real-time `VWAP` (volume-weighted average price) calculation engine

VWAP Overview The goal of this project is to create a real-time VWAP (volume-weighted average price) calculation engine. For this was used the coinbas

Feb 11, 2022
Weighted PageRank implementation in Go

pagerank Weighted PageRank implementation in Go Usage package main import ( "fmt" "github.com/alixaxel/pagerank" ) func main() { graph := pagera

Dec 21, 2022
Efficient moving window for high-speed data processing.

Moving Window Data Structure Copyright (c) 2012. Jake Brukhman. ([email protected]). All rights reserved. See the LICENSE file for BSD-style license. I

Sep 4, 2022
A tool for moving files into directories by file extensions
A tool for moving files into directories by file extensions

The tool for moving files into directories by file extensions Example before moving structure: moving into same extension dir result: moving into diff

Dec 6, 2021
A bin which will keep screen open by moving a mouse

Stay Awake This is a small program which will move mouse up and down to keep screen on. This stimulates like user is doing something. Motivation I had

Oct 21, 2021
Moving Averages Exercise For Golang

Moving Averages Exercise For Golang

Dec 10, 2021
An application that uses gRPC Client Streaming framework to computes average.

compute-average An API that uses Client Streaming gRPC framework to capture all integer numbers on Requests that the client sent and returns just the

Dec 26, 2021
Check-load - Simple cross-platform load average check

Sensu load average check Table of Contents Overview Usage examples Configuration

Jun 16, 2022
Golang string comparison and edit distance algorithms library, featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

Go-edlib : Edit distance and string comparison library Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Ham

Dec 20, 2022
Golang string comparison and edit distance algorithms library, featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

Go-edlib : Edit distance and string comparison library Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Ham

Dec 20, 2022
Go translations of the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Overview Go translations of the Java source code for the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin

Dec 13, 2022
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go

Region quadtrees in Go Region quadtrees and efficient neighbour finding techniques in Go Go-rquad proposes various implementations of region quadtrees

Dec 13, 2022
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

Dec 19, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Dec 27, 2022
Graph algorithms and data structures
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Jan 2, 2023
Graph algorithms written in Go

Graph Algorithms in Go This repository contains implementations of various graph algorithms written in Go. I’ve written them to learn about these algo

Dec 26, 2022
Some algorithms in go: maxflow(min-cuts or graph-cuts), edit-distance.

Algorithms In this repository, some algorithms are implemented in go language. GoDoc link: ed maxflow About Max-flow problem: A flow network is repres

Sep 8, 2022
Image processing algorithms in pure Go
Image processing algorithms in pure Go

bild A collection of parallel image processing algorithms in pure Go. The aim of this project is simplicity in use and development over absolute high

Jan 6, 2023