Smoothing time series data

Question

I am building an android application that records accelerometer data during sleep, so as to analyze sleep trends and optionally wake the user near a desired time during light sleep.

I have already built the component that collects and stores data, as well as the alarm. I still need to tackle the beast of displaying and saving sleep data in a really meaningful and clear way, one that preferably also lends itself to analysis.

A couple of pictures say two thousand words: (I can only post one link due to low rep)

Here's the unfiltered data, the sum of movement, collected at 30 second intervals

And the same data, smoothed by my own manifestation of moving average smoothing

edit) both charts reflect calibration- there is a minimum 'noise' filter and maximum cutoff filter, as well as a alarm trigger level (the white line)

Unfortunately, neither of these are optimal solutions- the first is a little hard to understand for the average user, and the second, which is easier to understand, hides a lot of what is really going on. In particular the averaging removes the detail of spikes in movement- and I think those can be meaningful.

So why are these charts so important? These time-series are displayed throughout the night as feedback to the user, and will be stored for reviewing/analysis later. The smoothing will ideally lower memory cost (both RAM and storage), and make rendering faster on these resource-starved phones/devices.

Clearly there is a better way to smooth the data- I have some vague ideas, such as using linear regression to figure out 'sharp' changes in movement and modifying my moving average smoothing according. I really need some more guidance and input before I dive headfirst into something that could be solved more optimally.

Thanks!

Answer 1

First up, the requirements for compression and analysis/presentation are not necessarily the same -- indeed, for analysis you might want to keep all the raw data and have the ability to slice and dice it in various ways. And what works best for you will depend very much on what you want to get out of it. But there are a number of standard tricks that you could try:

• Use differences rather than raw data
• Use thresholding to remove low-level noise. (Combine with differencing to ignore small changes.)
• Use variance over some time window rather than average, to capture activity level rather than movement
• Change the time base from fixed intervals to variable length runs and accumulate into a single data point sequences of changes for which some criterion holds (eg, differences in same direction, up to some threshold)
• Transform data from real values to ordinal (eg low, medium, high); you could also do this on time bins rather than individual samples -- eg, activity level for each 5 minute stretch
• Use an appropriate convolution kernel* to smooth more subtly than your moving average or pick out features of interest such as sharp changes.
• Use an FFT library to calculate a power spectrum

The last may be a bit expensive for your purposes, but would probably give you some very useful presentation options, in terms of "sleep rhythms" and such. (I know next to nothing about Android, but it's conceivable that some/many/all handsets might have built in DSP hardware that you can take advantage of.)

---

* Given how central convolution is to digital signal processing, it's surprisingly difficult to find an accessible intro online. Or at least in 3 minutes of googling. Suggestions welcome!

Answer 2

There are many nonparametric smoothing algorithms including splines and loess. But they will smooth out the sudden changes too. So will low-pass filters. I think you might need a wavelet-based smoother which allows the sudden jumps but still smooths the noise.

Check out Percival and Walden (2000) and the associated R package. Although you want a java solution, the algorithms in the R package are open-source and you might be able to translate them.

Answer 3

This is somewhat tangential to what you're asking, but it may be worth taking a look at the Kalman filter.

Answer 4

Savitzky-Golay smoothing could be a good answer. It's an extremely efficient implementation of least squares smoothing over a sliding time window (a convolution over that data) that comes down to just multiplying the data in each time window by fixed constants. You can fit values, derivatives, second derivatives, and higher.

You choose how spiky you allow the results to be, based on the size of the sliding time window and the degree of the polynomial fit on that time window. That was originally developed for chromatography, where peaks are an essential part of the results. One desirable property of SG smoothing is that the locations of the peaks are preserved. For instance, a 5 to 11 point window with a cubic curve fit cuts noise but still preserves peaks.

There's a good article in Wikipedia, although it's referred to as Savitzky-Golay filter (doing slight violence to normal terminology from systems control theory and time series analysis, as well as the original paper, where it's correctly called smoothing). Also be aware that there is (an argument over) an error in the Wikipedia article for formulas for second derivative estimates -- see the Talk section for that article. EDIT: The Wikipedia article was fixed