10

I have noisy time series which I need to segment into those portions with a zero mean and those portions without a zero mean. Finding the boundaries as accurately as possible is important (clearly where the boundary precisely lies is a bit subjective). I think a cusum variant could be adapted to do this but as cusum is primarily about finding single changes that leaves the whole segmentation strategy completely unaddressed.

I'm sure a bunch of research has been done on this problem but have not been able to find it.

P.S. The amount of data in these time series is quite large, i.e. up to hundreds of millions of samples, and an individual sample can be a vector with a couple of hundred components, so a method that can be computed reasonably quickly is a significant factor.

P.P.S There isn't a segmentation tag, hence the classification tag.

whuber
  • 281,159
  • 54
  • 637
  • 1,101
John Robertson
  • 973
  • 3
  • 15
  • 25

2 Answers2

1

It seems that the main issue here is efficient change-point detection, as after that the mean of the segment can be found trivially with increasing accuracy in the number of samples. Once recent approach that might be interesting is Z. Harchaoui, F. Bach, and E. Moulines. Kernel change-point analysis, Advances in Neural Information Processing Systems (NIPS), 2008.

tdc
  • 7,289
  • 5
  • 32
  • 62
1

This may not be state of the art, but an intuitive method would be smoothing the data by placing weights on the observations close to each point in time. So if you want to know whether sample R has a zero mean at time T:

mu(R,T)=w1*Sample(R,T)+w2*Sample(R,T-1)+w3*Sample(R,T+1)....

Perhaps exponential weights can be a good choice, depending on the definition of where the boundry lies.

After taking care of some technical details like the definition at the start and end of each somple you can now simply test whether each mu is close enough to zero to find the points where the mean is zero.

Dennis Jaheruddin
  • 436
  • 3
  • 20