16
$\begingroup$

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).

$\endgroup$
7
  • $\begingroup$ I forgot this: The points along the x-axis come with varying spacing. $\endgroup$
    – Pete
    Jul 29, 2010 at 14:06
  • $\begingroup$ I am not sure I understand. Don't you have a y-axis? $\endgroup$
    – user28
    Jul 29, 2010 at 14:07
  • $\begingroup$ Ah, sorry. I misstyped. I have now changed it above. $\endgroup$
    – Pete
    Jul 29, 2010 at 14:11
  • $\begingroup$ I also think you need to provide a bit more information. For example, I still cannot visualize the graph. What is your goal? $\endgroup$
    – user28
    Jul 29, 2010 at 14:19
  • $\begingroup$ Ok, sorry. I have added some more details above. $\endgroup$
    – Pete
    Jul 29, 2010 at 15:11

6 Answers 6

13
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Ah, interesting, but I need it to be predictable, i.e. to have the same result each time I view the data. $\endgroup$
    – Pete
    Jul 29, 2010 at 14:18
  • $\begingroup$ In that case, generate the n indexes of the points you choose, and store those indexes. $\endgroup$ Jul 29, 2010 at 14:21
  • $\begingroup$ Or store the seed to the RNG before sampling. $\endgroup$ Jul 29, 2010 at 14:25
  • $\begingroup$ Dirk's solution regarding the seed is probably the better option. $\endgroup$ Jul 29, 2010 at 14:31
  • $\begingroup$ Calculating averages per each second is ok, but what I do when there is no data for a specific second. I guess I could do some interpolation from the seconds before and after it, but it would be great with some specific (named) method for this, so I don't try to invent something already invented. $\endgroup$
    – Pete
    Jul 29, 2010 at 16:24
11
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Yep, visualization is what I want. I have added some more info in the question. $\endgroup$
    – Pete
    Jul 29, 2010 at 15:11
  • $\begingroup$ seconding plotting raw data with a smoothing line. $\endgroup$
    – JoFrhwld
    Jul 29, 2010 at 15:43
  • $\begingroup$ thirding plotting raw data with a smoothing line --- You might want to also plot the change in BPM over time as a separate visualization. $\endgroup$
    – John
    Jul 29, 2010 at 17:52
9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting posting. I will look into that too. You are probably right. $\endgroup$
    – Pete
    Aug 2, 2010 at 7:53
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ok, sorry. I have added some more details above. $\endgroup$
    – Pete
    Jul 29, 2010 at 15:12
6
$\begingroup$

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
$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for this! Best answer on this page by far, IMHO. I'd like to ask a follow-up: I have a huge data set of x-y (time-voltage) values generated from a transient electrical event (contact bounce in a mechanical switch), and captured on my oscilloscope. I need this data as input to my SPICE circuit analysis program, but it just won't cope with half-a-million data points. A sampled/thinned data set must preserve the sequence (ref non-self-intersection in the Wiki article), and as much as possible preserve the frequency content (a la Fourier) of the original. Any thoughts? $\endgroup$
    – Seamus
    Dec 29, 2020 at 17:44
  • $\begingroup$ Here's what the data look like on the oscilloscope $\endgroup$
    – Seamus
    Dec 29, 2020 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.