anomalyzer

README

Anomalyzer

Probabilistic anomaly detection in Go.

Featured on Hacker News August 13th, 2015 and the Lytics Developer Blog.

Windows

Inspired by Etsy's Skyline package, Anomalyzer implements a suite of statistical tests that yield the probability that a given set of numeric input, typically a time series, contains anomalous behavior. Each test compares the behavior in an active window of one or more points to the behavior in a reference window of two or more points.

Specifying a number of seasons will yield a reference window length equal to that factor times the length of the active window specified. For example, an input vector of [1, 2, 3, 4, 5, 6, 7, 8, 9], and an active window length of 1 with number of seasons equal to 4, would yield an active window of [9] and a reference window of [5, 6, 7, 8].

Algorithms

Anomalyzer can implement one or more of the following algorithmic tests:

1. cdf: Compares the differences in the behavior in the active window to the cumulative distribution function of the reference window.
2. diff: Performs a bootstrap permutation test on the ranks of the differences in both windows, in the flavor of a Wilcoxon rank-sum test.
3. high rank: Performs a bootstrap permutation test on the ranks of the entries themselves in both windows. Counts how many times the permuted rank-sum is less than the original rank-sum, sensitive to increasing behavior.
4. low rank: Similarly, counts how many times the permuted rank-sum is greater than the original rank-sum, sensitive to decreasing behavior.
5. magnitude: Compares the relative magnitude of the difference between the averages of the active and the reference windows.
6. fence: Indicates that data are approaching a configurable upper and lower bound.
7. bootstrap ks: Calculates the Kolmogorov-Smirnov test over active and reference windows and compares that value to KS test scores obtained after permuting all elements in the set.

Each test yields a probability of anomalous behavior, and the probabilities are then computed over a weighted mean to determine if the overall behavior is anomalous. Since a probability is returned, the user may determine the sensitivity of the decision, and can determine the threshold for anomalous behavior for the application, whether at say 0.8 for general anomalous behavior or 0.95 for extreme anomalous behavior.

Configuration

Any of the tests can be included in the anomalyzer, and if none are supplied in the configuration, default to magnitude and cdf. Methods are supplied through the Methods value in the configuration and accepts a slice of strings for the method names.

A value for ActiveSizeis required and must be a minimum of 1. The NSeasons will default to 4 if not specified.

Magnitude

If the magnitude test is specified, a Sensitivity (between 0 and 1) can be supplied such that when the result of the magnitude test is less than that value, the weighted mean will return 0. If Sensitivity is not specified, it defaults to 0.1.

Bootstrap KS

To capture seasonality, the bootstrap ks test should consider an active window length equal to a season.

Fence

The fence test can be configured to use custom UpperBound and LowerBound values for the fences. If no lower bound is desired, set the value of LowerBound to anomalyzer.NA.

Diff & Rank

The diff, bootstrap ks, and rank tests can accept a value for the number of bootstrap samples to generate, indicated by PermCount, and defaults to 500 if not set.

Example

package main

import (
	"fmt"
	"github.com/lytics/anomalyzer"
)

func main() {
	conf := &anomalyzer.AnomalyzerConf{
		Sensitivity: 0.1,
		UpperBound:  5,
		LowerBound:  anomalyzer.NA, // ignore the lower bound
		ActiveSize:  1,
		NSeasons:    4,
		Methods:     []string{"diff", "fence", "highrank", "lowrank", "magnitude"},
	}

	// initialize with empty data or an actual slice of floats
	data := []float64{0.1, 2.05, 1.5, 2.5, 2.6, 2.55}

	anom, _ := anomalyzer.NewAnomalyzer(conf, data)

	// the push method automatically triggers a recalcuation of the
	// anomaly probability.  The recalculation can also be triggered
	// by a call to the Eval method.
	prob := anom.Push(8.0)
	fmt.Println("Anomalous Probability:", prob)
}

Documentation

Overview

Package anomalyzer implements probability-based anomaly detection.

See https://github.com/lytics/anomalyzer#readme for more information.

Example

conf := &AnomalyzerConf{
	Sensitivity: 0.1,
	UpperBound:  5,
	LowerBound:  NA, // ignore the lower bound
	ActiveSize:  1,
	NSeasons:    4,
	Methods:     []string{"diff", "fence", "highrank", "lowrank", "magnitude"},
}

// initialize with empty data or an actual slice of floats
data := []float64{0.1, 2.05, 1.5, 2.5, 2.6, 2.55}

anom, _ := NewAnomalyzer(conf, data)

// the push method automatically triggers a recalcuation of the
// anomaly probability.  The recalculation can also be triggered
// by a call to the Eval method.
prob := anom.Push(8.0)
fmt.Println("Anomalous Probability:", prob)

Index

• Constants
• Variables
• func BootstrapKsTest(vector govector.Vector, conf AnomalyzerConf) float64
• func CDFTest(vector govector.Vector, conf AnomalyzerConf) float64
• func DiffTest(vector govector.Vector, conf AnomalyzerConf) float64
• func FenceTest(vector govector.Vector, conf AnomalyzerConf) float64
• func KsStat(vector govector.Vector, conf AnomalyzerConf) float64
• func MagnitudeTest(vector govector.Vector, conf AnomalyzerConf) float64
• func RankTest(vector govector.Vector, conf AnomalyzerConf) float64
• func ReverseRankTest(vector govector.Vector, conf AnomalyzerConf) float64
• type Algorithm
• type Anomalyzer
  • func NewAnomalyzer(conf *AnomalyzerConf, data []float64) (Anomalyzer, error)
  • func (a Anomalyzer) Eval() float64
  • func (a Anomalyzer) EvalByTest() (map[string]float64, map[string]float64)
  • func (a *Anomalyzer) Push(x float64) float64
  • func (a *Anomalyzer) Update(x []float64)
• type AnomalyzerConf

Examples

• Package

Constants

const (
	NA = math.SmallestNonzeroFloat64
)

Variables

var (
	Algorithms = map[string]Algorithm{
		"magnitude": MagnitudeTest,
		"diff":      DiffTest,
		"highrank":  RankTest,
		"lowrank":   ReverseRankTest,
		"cdf":       CDFTest,
		"fence":     FenceTest,
		"ks":        BootstrapKsTest,
	}
)

Functions

func BootstrapKsTest

func BootstrapKsTest(vector govector.Vector, conf AnomalyzerConf) float64

func CDFTest

func CDFTest(vector govector.Vector, conf AnomalyzerConf) float64

Generates the cumulative distribution function using the difference in the means for the data.

func DiffTest

func DiffTest(vector govector.Vector, conf AnomalyzerConf) float64

Generates permutations of reference and active window values to determine whether or not data is anomalous. The number of permutations desired has been set to 500 but can be increased for more precision.

func FenceTest

func FenceTest(vector govector.Vector, conf AnomalyzerConf) float64

This function can be used to test whether or not data is getting close to a specified upper or lower bound.

func KsStat

func KsStat(vector govector.Vector, conf AnomalyzerConf) float64

Calculate a Kolmogorov-Smirnov test statistic.

func MagnitudeTest

func MagnitudeTest(vector govector.Vector, conf AnomalyzerConf) float64

Generates the percent difference between the means of the reference and active data. Returns a value scaled such that it lies between 0 and 1.

func RankTest

func RankTest(vector govector.Vector, conf AnomalyzerConf) float64

func ReverseRankTest

func ReverseRankTest(vector govector.Vector, conf AnomalyzerConf) float64

Types

type Algorithm

type Algorithm func(govector.Vector, AnomalyzerConf) float64

type Anomalyzer

type Anomalyzer struct {
	Conf *AnomalyzerConf
	Data govector.Vector
}

func NewAnomalyzer

func NewAnomalyzer(conf *AnomalyzerConf, data []float64) (Anomalyzer, error)

func (Anomalyzer) Eval

func (a Anomalyzer) Eval() float64

Return the weighted average of all statistical tests for anomaly detection, which yields the probability that the currently observed behavior is anomalous.

func (Anomalyzer) EvalByTest

func (a Anomalyzer) EvalByTest() (map[string]float64, map[string]float64)

Get the results and weights of each test. Useful for debugging

func (*Anomalyzer) Push

func (a *Anomalyzer) Push(x float64) float64

func (*Anomalyzer) Update

func (a *Anomalyzer) Update(x []float64)

type AnomalyzerConf

type AnomalyzerConf struct {
	Delay       bool
	Sensitivity float64
	UpperBound  float64
	LowerBound  float64
	ActiveSize  int

	NSeasons  int
	PermCount int
	Methods   []string
	// contains filtered or unexported fields
}