Will Welch welch

Forecast

Holt-Winters smoother/forecaster for anomaly detection

Forecast threads a smooth curve through a noisy timeseries in a way that lets you visualize trends, cycles, and anomalies. It can be used as part of an automatic anomaly detection system for metric timeseries (that is, sequences of timestamped numerical values).

It accomplishes this using a variation of Holt-Winters forecasting -- more generally known as exponential smoothing. Forecast decomposes a noisy signal into level, trend, repetitive "seasonal" effects, and unexplained variation or noise. In this example, a "season" is a day long, and we model repeated day-over-day variation. The result is a smoothed version of the signal which may be used to forecast future values or detect unexpected variation. This approach has been successfully used for [network anomaly detection](https://www.usenix.org/legacy/event/lisa2000/full_papers/br

Robust time derivatives

In this example we use trend estimation as a robust way to estimate the rate of change of a metric at a point in time. The constant every controls the interval of data we use for each estimate, and the frequency at which we update the estimate. The trend module (which is more typically used over long intervals of time) is applied to this very short interval. The slope of the fitted trend is returned by trend.rate, and the trended change over an interval as trend.change (which is in the same units as the input field, often more convenient for alerting and display)

Try different durations for every to see its effect. The simulated cpu sends a new value every 10 seconds, so every should be at least :20s: so it has enough samples to fit a line to them. Longer windows will give smoother derivative curves.

In this example, a every between :45s: and :2m: does a good job of highlighting the big breaks in the cpu curve while ignoring the noise.

	It is a rite of passage to post one's successful build instructions for OpenCV on a Mac
	after you've tried all the other conflicting instructions out there and still failed.
	brew failed for me (was this because I could never get a happy brew doctor situation?
	I'll never know). macports? nope. build-from-source recipes? I didn't find one that
	worked for me.

	Here's what did work to build OpenCV 2.4.5 from the distribution tarball using cmake,
	on Mac OSX 10.8.4, linked to an anaconda installation rather than the system python.
	It is a mashup of various bits of advice out there. If you're already comfortable with
	build/install from source, all you need to read is the cmake invocation in step 3 and

	// timeseries anomaly detection based on a forecast confidence interval
	// A EWMA smoothed version of the timeseries is computed, and its time-varying
	// variance provides an expected range for the subsequent point in the series.
	// When the series falls outside this envelope, an event is generated.
	//
	// This is ad-hoc and difficult to tune, but demonstrates the basic
	// idea of forecast-error-based anomaly detection in a single timeseries.
	//
	sub cpu(from, to) {
	demo cdn metrics 'cpu' -from from -to to -every :m:

	// Holt forecaster, which models an unobserved
	// level and trend component in a noisy signal. The result is a smoothed
	// version of the signal which may be used to forecast future values.
	//
	// Y is the point field to smooth.
	// slevel and strend are smoothing factors, numbers ranging [0..1].
	// They determine how quickly the smoother adjusts to new values as they arrive.
	// Setting a factor to 0 freezes the feature at its initial estimate,
	// while setting a factor to 1 causes that feature to depend solely
	// on the most recent point. Setting strend to null removes that feature

	[
	{"time": "1980-09-25T14:01:00Z", "count": 182.478},
	{"time": "1980-09-25T14:02:00Z", "count": 176.231},
	{"time": "1980-09-25T14:03:00Z", "count": 183.917},
	{"time": "1980-09-25T14:04:00Z", "count": 177.798},
	{"time": "1980-09-25T14:05:00Z", "count": 165.469},
	{"time": "1980-09-25T14:06:00Z", "count": 181.878},
	{"time": "1980-09-25T14:07:00Z", "count": 184.502},
	{"time": "1980-09-25T14:08:00Z", "count": 183.303},
	{"time": "1980-09-25T14:09:00Z", "count": 177.578},

	// 4-way right outer join of a point stream of ids against tables of personal information.
	//
	// The points in the "tables" all have the same timestamp.
	// For the join, the ID in each emitter point
	// is matched against each table, and an output point is created that is the union of all
	// matching points. This demonstrates partial joins when not all tables have an entry for
	// an ID. There are no matches at all for ID 5, so that point is passed through unchanged.
	//---------------------------------------------------------------------------
	const name = [
	{time:"1970-01-01T00:00:00.000Z", "id":1, "name":"fred"},

	[
	{ "source_type": "metric", "time": "2014-01-01T00:00:00.000Z", "name": "C750.<test:runid>.live", "space": "default", "value": 10 },
	{ "source_type": "metric", "time": "2014-01-01T00:00:01.000Z", "name": "C750.<test:runid>.live", "space": "default", "value": 20 },
	{ "source_type": "metric", "time": "2014-01-01T00:00:02.000Z", "name": "C750.<test:runid>.live", "space": "default", "value": 30 },
	{ "source_type": "metric", "time": "2014-01-01T00:00:03.000Z", "name": "C750.<test:runid>.live", "space": "default", "value": 40 },
	{ "source_type": "metric", "time": "2014-01-01T00:00:04.000Z", "name": "C750.<test:runid>.live", "space": "default", "value": 50 }
	]

	// model trends in a series via linear regression.
	//
	// Exported subs:
	// fit: do a least-squares fit of a line to successive batches of points,
	// and calculate the trend's value at each point. A fit is computed for each batch.
	// ... \| fit -in 'cpu' -every :2h: -over :8h: -t0 :2014-01-01: -out 'trend';
	// fit_initial: do a least-squares fit of a line to an initial window of points,
	// and calculate this trend's value at subsequent points. A fit is computed once.
	// ... \| fit_initial -in 'cpu' -over :2h: -t0 :2014-01-01: -out 'trend';
	// fit_trailing: do a least-squares fit of a line to a moving window of points

	// simulated sources for demos and tests
	//
	// Exported subs:
	// bumpy_cpu: a 10-minute cpu metric with daily variation
	// ripple_cpu: a 10-second cpu metric with minute-variation
	//
	// Exported functions:
	//
	// Exported reducers:
	//