Exponentially Weighted Moving Average algorithms for Go.

Overview

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.

Issues
  • 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

    opened by IanCal 5
  • 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?

    opened by eclipseo 2
  • 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.

    opened by mend-for-github-com[bot] 1
  • 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
    

    }

    opened by aQuaYi 1
  • 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

    opened by ickymettle 1
  • 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]
    
    opened by nim-nim 0
  • 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.

    opened by eclipseo 0
  • 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.

    opened by xaprb 0
  • 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.

    opened by andig 0
  • 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
    
    opened by jweissig 0
  • 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.

    opened by pjebs 0
Releases(v1.2.0)
Owner
VividCortex
VividCortex
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

Gyuho Lee 690 Jul 26, 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

Sayi Polia 0 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

Alix Axel 75 Apr 29, 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

Jake Brukhman 31 Jun 30, 2021
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

Uladzislau Jum 0 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

Nirav Patel 0 Oct 21, 2021
Moving Averages Exercise For Golang

Moving Averages Exercise For Golang

james lapointe 0 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

Lucas Thiago Batista 0 Dec 26, 2021
Check-load - Simple cross-platform load average check

Sensu load average check Table of Contents Overview Usage examples Configuration

KOHMURA Jin 0 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

Hugo Bollon 335 Jul 19, 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

Hugo Bollon 335 Jul 19, 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

youngzy 168 Jun 30, 2022
: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

Aurélien Rainone 120 Jun 22, 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

disksing 159 Aug 2, 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:

Derek Parker 597 Jul 31, 2022
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

Algorithms to Go 565 Jul 29, 2022
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

Thomas Cyron 52 Jul 22, 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

Yi Deng 14 Apr 9, 2021
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

Anthony N. Simon 3.6k Jul 29, 2022
Selected Machine Learning algorithms for natural language processing and semantic analysis in Golang

Natural Language Processing Implementations of selected machine learning algorithms for natural language processing in golang. The primary focus for t

James Bowman 370 Jul 27, 2022
k-modes and k-prototypes clustering algorithms implementation in Go

go-cluster GO implementation of clustering algorithms: k-modes and k-prototypes. K-modes algorithm is very similar to well-known clustering algorithm

e-Xpert Solutions 31 Mar 14, 2022
Genetic Algorithms library written in Go / golang

Description Genetic Algorithms for Go/Golang Install $ go install git://github.com/thoj/go-galib.git Compiling examples: $ git clone git://github.com

Thomas Jager 192 May 26, 2022
Collaborative Filtering (CF) Algorithms in Go!

Go Recommend Recommendation algorithms (Collaborative Filtering) in Go! Background Collaborative Filtering (CF) is oftentimes used for item recommenda

Tim Kaye 189 Jul 15, 2022
Evolutionary Algorithms in Go

Evo Evo is a framework for implementing evolutionary algorithms in Go. go get github.com/cbarrick/evo Documentation https://godoc.org/github.com/cbar

Chris Barrick 112 Apr 18, 2022
Selected Machine Learning algorithms for natural language processing and semantic analysis in Golang

Natural Language Processing Implementations of selected machine learning algorithms for natural language processing in golang. The primary focus for t

James Bowman 370 Jul 27, 2022
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

Gyuho Lee 690 Jul 26, 2022
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

Algorithms to Go 9 Jan 25, 2021
Provide check digit algorithms and calculators written in Go

checkdigit About Provide check digit algorithms and calculators written by Go. Provided methods Algorithms Luhn Verhoeff Damm Calculators ISBN-10 ISBN

Osamu TONOMORI 92 Jul 24, 2022