4

I have a list of numbers that, when plotted on a graph, clearly demonstrate trends such as rising upwards, dropping, repeating etc.. When a human sees the graph, they can easily make out what's happening. What I'm trying to do is achieve the same thing numerically and have the system detect what trends are occurring in the graph. My initial idea is to have a window that shifts along the data, and only the values within this window are used to calculate the trend. A window too small would result in small changes being exaggerated and a window too large would undermine large changes so it might be tricky finding a suitable window size which might make this approach unsuitable.

For example, if I have this set (I've added the square brackets to match the description below, but they're purely illustrative; the data is still only one set):

{[0,1,0,1,0,0],[1,1,1,1,1,1,1],[2,2,4,6,7,8,9,10,9,0],[0,1,1,0,1]}

We can easily see (especially if drawn on a graph) that it starts off relatively stable, then gets stable, starts rising, suddenly drops, then becomes relatively stable again.

What techniques and topics should I read up on to find ways of having the system detect those types of patterns efficiently? One approach would be to have rules. For example, a counter which increased everytime the number increased and decreased when the number decreased. Then, if the counter passed a high threshold, then the system should return rising. Is this rule-based approach a good way, or are there better approaches? (I prefer efficiency to accuracy, given a trade-off).

keyboardP
  • 143
  • 3
    I recommend moving this to statistics.SE. What you're describing appears to be change point detection. I'm sure the good people on that site can advise on useful CP algorithms. – Iterator Sep 26 '11 at 23:22
  • Thanks Iterator, I hadn't realised there was such a SE. I was going to post it to the maths SE one, but it seemed better suited here since it was to be programmed. – keyboardP Sep 27 '11 at 14:37
  • Looking at the answers here: Fourier Transforms, Kalman Filters, PCA, and a few random hacks. Charitably put, a few seem to have superficial familiarity with the terms, but not what they're trying to do nor how to apply it. Then again, stats.SE is also a mixed bag, but the expectations a probably a little higher when it comes to familiarity with actual application. Good luck. – Iterator Sep 27 '11 at 15:09
  • 1
    Minor continuation: for modeling within a given regime (i.e. between changes), you'll need to have some assumptions about the curves; you could try polynomials, but it's best if you keep the degree low & realistic - focus on what patterns you've seen or could expect. Detecting the changes seems to be more your focus, though. Methods for fitting local models and detecting changes are different, but naturally are related (measures of poor model fit indicates a switch may have occurred). – Iterator Sep 27 '11 at 15:12
  • Thanks very much for the help. I guess I need the best of both worlds. The main trends I need to monitor are simply rising, falling and stable so I could fit local models there. However, I need to also know at what point they stop. So, for example, the rising trend stopped on the 10th day. I'm not sure if this is also possible with model fitting methods? – keyboardP Sep 27 '11 at 20:14
  • 1
    The model fitting methods may not be necessary in that case. As a statistical problem, it appears to reduce to two hypothesis tests for whether whether 1: (dY/dT)(t) = (dY/dT)(t-1) (change point detection) and 2: a two-sided test for whether (dY/dT)(t) == 0. (Sorry to be informal in notation, but it would be easier to address on stats.SE, where LaTeX is feasible.). It may be that you only need to do test #2. – Iterator Sep 27 '11 at 21:04
  • I'll take a look into it and if I need to follow up, I'll post it to SSE. Thanks again for the help! – keyboardP Sep 27 '11 at 22:08

6 Answers6

3

A loess smoother is usually the best way to detect 'trends' similar to the ones a human would see.

Here is an example in R, using the data you posted. The red line is the loess model:

y <- c(0,1,0,1,0,0,1,1,1,1,1,1,1,2,2,4,6,7,8,9,10,9,0,0,1,1,0,1)
x <- 1:length(y)

y.loess <- loess(y ~ x, span=0.25, data.frame(x=x, y=y))
y.predict <- predict(y.loess, data.frame(x=x))

plot(x,y)
lines(x,y.predict,col='red')

enter image description here

Zach
  • 23,766
2

You can shift a window over your data and fit in each window a straight line. You can plot the resulting slope for each window which eg shows stable regions by a low slope.

http://mathbits.com/mathbits/tisection/statistics1/linefit.htm

rocksportrocker
  • 435
2

Use regression -- look for the "polynomial fitting" slide.

Principal component analysis is useful for analysing multidimensional clusters (there are dramatic examples of representing photographs of faces using only a handful of parameters, or breaking down the political axes exposed by a survey).

Once you have a polynomial you can differentiate it to find the interesting features

  • maximum slope
  • turning points and inflexion points
  • trends (in range x=a...x=b the gradient never exceeds amount N)

Regression is nice because does not require an exact fit in the same way that polynomial interpolation does -- so it's more tolerant of errors and noise -- and also you can calculate when the fit is "good enough" according to arbitrary criteria.

You can express a number of machine learning methods (perceptrons, for example) in the language of regression. The only tricky part is inverting what may be a rather large matrix, you'll need a good numerical library to get stable solutions in extreme cases.

spraff
  • 157
2

You could describe your process as a Kalman process, that is, construct a Kalman filter e.g. consisting of current value, first and second derivative and trying to track the position. The Kalman filter would give you a current velocity estimate, which is an estimator for the change.

thiton
  • 156
  • 3
  • This may be the best answer, but my guess is it's way beyond the questioner's abilities or needs. – Wayne Sep 28 '11 at 15:30
2

The answer to your question is as follows. Given that you are trying to detect the presence of local time trends this can be seen as an extension of detecting local level shifts, The literature of Intervention Detection (Not Intervention Modelling which requires a user specification) but rather the search for the points in time where the trend has changed and the magnitude of that change. Now if there are Level shifts and/or ARIMA structure required you will have to integrate all three components in your search.

IrishStat
  • 29,661
1

A quick and simple approach might be as follows; decide on an interval, calculate the mean of the values of that interval, compare it to the start and end values of the interval, and categorise the interval as ascending, descending or stable. If you desire, you can look at the standard devitation of the intervals as well, intervals with high standard deviations might indicate lots of activity and be worthy of closer examination.

Beware of sampling errors as this is not as rigorous an approach as the regression and interpolation suggestions above.