How do I reduce the number of data points in a series?

Question

I haven't studied statistics for over 10 years (and then just a basic course), so maybe my question is a bit hard to understand.

Anyway, what I want to do is reduce the number of data points in a series. The x-axis is number of milliseconds since start of measurement and the y-axis is the reading for that point.

Often there is thousands of data points, but I might only need a few hundreds. So my question is: How do I accurately reduce the number of data points?

What is the process called? (So I can google it) Are there any prefered algorithms (I will implement it in C#)

Hope you got some clues. Sorry for my lack of proper terminology.

---

Edit: More details comes here:

The raw data I got is heart rate data, and in the form of number of milliseconds since last beat. Before plotting the data I calculate number of milliseconds from first sample, and the bpm (beats per minute) at each data point (60000/timesincelastbeat).

I want to visualize the data, i.e. plot it in a line graph. I want to reduce the number of points in the graph from thousands to some hundreds.

One option would be to calculate the average bpm for every second in the series, or maybe every 5 seconds or so. That would have been quite easy if I knew I would have at least one sample for each of those periods (seconds of 5-seconds-intervals).

Answer 1

You have two problems: too many points and how to smooth over the remaining points.

Thinning your sample

If you have too many observations arriving in real time, you could always use simple random sampling to thin your sample. Note, for this too be true, the number of points would have to be very large.

Suppose you have N points and you only want n of them. Then generate n random numbers from a discrete uniform U(0, N-1) distribution. These would be the points you use.

If you want to do this sequentially, i.e. at each point you decide to use it or not, then just accept a point with probability p. So if you set p=0.01 you would accept (on average) 1 point in a hundred.

If your data is unevenly spread and you only want to thin dense regions of points, then just make your thinning function a bit more sophisticated. For example, instead of p, what about:

$$1-p \exp(-\lambda t)$$

where $\lambda$ is a positive number and $t$ is the time since the last observation. If the time between two points is large, i.e. large $t$, the probability of accepting a point will be one. Conversely, if two points are close together, the probability of accepting a point will be $1-p$.

You will need to experiment with values of $\lambda$ and $p$.

Smoothing

Possibly something like a simple moving average type scheme. Or you could go for something more advanced like a kernel smoother (as others suggested). You will need to be careful that you don't smooth too much, since I assume that a sudden drop should be picked up very quickly in your scenario.

There should be C# libraries available for this sort of stuff.

Conclusion

Thin if necessary, then smooth.

Answer 2

Well, I think the word you're looking for is "sampling," but I'm not sure why you want to do it. Thousands of data points isn't very many. Or are you looking just to plot a smaller number of equally-spaced points? That's usually called "binning."

Is your goal to generate a visualization? In that case, you might want to keep the raw data, plot it as a scattergraph, then overlay some sort of central tendency (regression line, spline, whatever) to communicate whatever the takehome message ought to be.

Or is your goal to numerically summarize the results in some way? In that case, you might want to explain your problem in more detail!

Answer 3

Calculating averages leads to a different dataset than simply reducing the number of data points. If one heartbeat per minute is much faster than the other heart beats you will lose the signal through your smoothing process.

If you summary 125-125-0-125-125 as 100 than the story that the data tells is different through your smoothing.

Sometimes the heart even skips beats and I believe that's an event that interesting for however wants to look at plotted heart rate data.

I would therefore propose that you calculate the distance between two points with a formula like d=sqrt((time1-time2)^2 + (bpm1-bpm2)).

You set a minimum distance in your program. Then you iterate through your data and after every point you delete all following points for which d is smaller than your minimum distance.

As the unit of time and bpm isn't the same you might want to think about how you can find a way to scale the units meaningfully. To do this task right you should speak to the doctors who in the end have to interpret your graphs and ask them what information they consider to be essential.

Answer 4

You're not providing enough information. Why do you want to reduce the data points. A few thousand is nothing these days.

Given that you want the same result each time you view the same data perhaps you want to simply bin averages. You have variable spacing on your x-axis. Maybe you're trying to make that consistent? In that case you would set a bin width of perhaps 50 msec, or 100, and then average all the points in there. Make the bin width as large as you need to reduce the data points to the size of the set you want.

binw = 50
myRTBin = ceiling(myRT / binw) * binw - binw / 2

You could then just aggregate the RTs grouped by the RT bins.

It's really a hard question to answer without a reason for why you're getting rid of data.

Answer 5

If BPM is staying the same over many samples (or changing infinitesimally in a way you aren't concerned about) you can truncate your data to a significant digit that you actually care about and then do Run Length Encoding.

For example, in R this data:

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

has this output

rle(data)
Run Length Encoding
  lengths: int [1:3] 10 15 15
  values : num [1:3] 0 1 2

Answer 6

For reducing your data points, you can use the Ramer–Douglas–Peucker algorithm which is very easy to understand and implement. The sampled signal will be very similar to the original one.