Moving averages, line smoothing, etc.

[mbostock]

I’m not 100% sure this belongs as a curve (or as a data transformation), but it seems like a reasonable place to put it. In theory if you used a smooth curve, the input data array to the line or area generator wouldn’t even need to be sorted by x-value: the smoother could buffer all the points and then compute the smooth curve on lineEnd.

[mbostock]

A kernel regression is another possibility, as in this kernel density estimation example. That implementation is O(n^2), but I suspect you could make it O(n lg n), or even O(n) if you assume that data is already sorted on x, and then implement a single-pass, fixed-window incremental algorithm.

[mbostock]

LOESS is another option.

[mbostock]

And here’s a simple test case:

With a smooth curve in R:

[curran]

Yes! When I first saw this visualization I thought of trying to implement a gaussian KDE for use with D3.

[mbostock]

I couldn’t resist taking a crack at it. Here’s the slow O(n^2) implementation of kernel smoothing:

Things that would be nice:

• [ ] Make it faster than O(n^2) by tracking a fixed window of input points (in x ± bandwidth).
• [ ] Support kernels besides Epanechnikov.
• [ ] Remove the scale factor 0.75 from the default Epanechnikov kernel, since it has no effect.
• [ ] Maybe pick a default bandwidth of 20 (fast)? Or Silverman’s rule of thumb (slow; global)?
• [ ] Maybe pick a default precision of 10 (distance in pixels between computed spline control points)?
• [x] Remove dependency on d3_scale.

[mbostock]

I’m going back to working on API documentation if anyone else wants to make a better implementation…

[curran]

Doing a little research, here's a list of common kernel functions

• [ ] Uniform
• [ ] Triangular
• [x] Epanechnikov
• [ ] Quartic
• [ ] Triweight
• [ ] Tricube
• [ ] Gaussian
• [ ] Cosine
• [ ] Logistic
• [ ] Silverman

Also, here's a formula for bandwidth estimation using "Silverman's rule of thumb".

[mbostock]

See also science.js, which implements bandwidth estimators and various kernels.

[e-n-f]

My fit above, by the way, is the sum of two gaussian PDFs, plus the sum of the same gaussians for x-24 and x+24, all raised to a power, for no good reason other than that it looked about right. I'd love to know a better way than eyeballing it and then applying general curve fitting to guess the components of things that look like the sum of gaussians.

[mbostock]

See also ggplot2’s stat_smooth, which uses LOESS and GAM (generalized additive models). And ggplot2 has a geom_smooth which can smooth using a ribbon, showing an upper and lower bound on the smoothed model. That might be a nice curve type for an area shape.

[curran]

Here's the Loess + D3 example from science.js by @jasondavies . I made a bl.ock to study it:

It looks like the API expects loess(xValuesArray, yValuesArray) and returns an array of smoothed Y values.

[mbostock]

Since the kernel operates in pixel space, I bet it would be reasonable to just have stupid defaults for the bandwidth (±20px) and precision (control points every 10px). Though certainly it would be nice if Silverman’s rule of thumb were easy to implement if you wanted a better default value, albeit at the cost of a global computation.

[curran]

Here's an example that adds a LOESS curve to your tweet example using science.js:

I made this to try to understand the science.js LOESS implementation. Here are a few things I learned:

• It was necessary to sort the data by time. I thought it would be sorted by time already (based on the order from the CSV file), but somehow it doesn't work without first sorting by time.
• The loess function accepts arrays of values in data space, and surprisingly it works with dates.
• The loess function returns an arrays of smoothed Y values that is the same length as the original arrays. I would have hoped that the length of the returned array is configurable, but it looks like in this implementation it is not.

[mbostock]

I think it might be a good idea to do smoothing as a pre-processing step in data space rather than doing it internally as a curve:

• Data space seems like a more natural fit when specifying kernel bandwidth.
• You might want to compute a smooth fit once before interactively redrawing (e.g., pan & zoom).
• You might want to access points in the computed smooth fit for display (e.g., hover tooltip).

I’m imagining something that has a x and y accessors and other configuration (e.g., kernel and bandwidth) and then computes the smooth curve, generating an array of [[x1, y1], [x2, y2], …] points in data space. Those can then be passed to a line generator, likely with an x and y accessor that apply scales to transform to screen space.

(I’m slightly tempted to have it return [[x1, x2, x3, …], [y1, y2, y3, …]] because that’s a more more efficient representation, but it would make implementing the accessors a little bit more awkward, so it feels like premature optimization.)

[tomgp]

+1 on the idea that this should be a data space operation.

[mbostock]

Probably should create a d3-smooth module for smoothing functions.

[muonsw]

Hope you don't mind me commenting but I found my way to this after looking at the issues on science.js.

I'm sure things have moved on since December, but I implemented a kernel smoothing function for use with D3 a while back. It cuts off the calculation for each point once the calculated weight goes below a defined threshold (with relation to the weight at the point that is being smoothed).

• It looks like it scales linearly but there is a trade-off in accuracy. So for the twitter data in question it’s about an order of magnitude quicker (depending on the bandwidth) but gives a line that can be up to 0.03% different.
• It assumes that data is sorted on the x-coordinate and hence that the calculation can be cut off.
• It assumes that the kernel function will always decrease beyond the cut-off point.

I'm fairly new to JavaScript so I'm sure that it’s not the best implementation. Anyway, I've created a gist if it’s of any interest (or use).

[nealstewart]

@mbostock Any more recent thoughts in this area? I need some line smoothing for a time series of continuous data in my application, and would love to contribute something.

[Fil]

d3-regression implements loess https://github.com/HarryStevens/d3-regression

[mbostock]

Here’s a simple moving average implementation:

https://observablehq.com/@d3/moving-average

[mbostock]

This feels more appropriate to do in data space rather than geometrically, so I don’t think d3-shape is the right place for this. Still interested in seeing progress here, though.