Path: news.mathworks.com!newsfeed-00.mathworks.com!newscon02.news.prodigy.net!prodigy.net!border1.nntp.dca.giganews.com!nntp.giganews.com!postnews.google.com!n2g2000hse.googlegroups.com!not-for-mail
From:  dave@autobox.com
Newsgroups: comp.soft-sys.matlab,sci.math,sci.stat.math,sci.stat.consult,sci.stat.edu
Subject: Re: How to detect turning points in curves...
Date: Fri, 13 Jul 2007 05:30:39 -0700
Organization: http://groups.google.com
Lines: 133
Message-ID: <1184329839.101091.223770@n2g2000hse.googlegroups.com>
References: <f76kg0$ic0$1@news.Stanford.EDU>
NNTP-Posting-Host: 68.80.205.23
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
X-Trace: posting.google.com 1184329839 32665 127.0.0.1 (13 Jul 2007 12:30:39 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Fri, 13 Jul 2007 12:30:39 +0000 (UTC)
In-Reply-To: <f77ojr$r32$1@news.Stanford.EDU>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.0.3705),gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: n2g2000hse.googlegroups.com; posting-host=68.80.205.23;
Bytes: 6065
Xref: news.mathworks.com comp.soft-sys.matlab:418915 sci.math:1030812 sci.stat.math:78250 sci.stat.consult:58918 sci.stat.edu:48364



On Jul 13, 7:42 am, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote in message
>
> news:MfHli.6345$rL1.6014@newssvr19.news.prodigy.net...
>
>
>
>
>
>
>
> > <AWinest...@gmail.com> wrote in message
> >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
> >> On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >>> <AWinest...@gmail.com> wrote in message
>
> >>>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> >>> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >>> >> How to detect turning points in curves
>
> >>> >> Hi all,
>
> >>> >> If you take a look at the following plot,
>
> >>> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> >>> >> You will agree with me that there are two turning points.
>
> >>> >> But is there a systematic way to let computer detect the turning
> >>> >> points
> >>> >> automatically and programmatically?
>
> >>> >> Please be advised that the second turn isn't neccessarily turning
> >>> >> down,
> >>> >> it
> >>> >> can also possibly go up...
>
> >>> >> And in real-world applications, the turn can be more smooth and
> >>> >> round,
> >>> >> but
> >>> >> still, naked eyes should be able to find the turning points easily.
>
> >>> >> My program has to do a classification:
>
> >>> >> All the good curves should first go down, and then either make no
> >>> >> turns;
> >>> >> or
> >>> >> make a turn, and stay vertically flat and slightly up, going from the
> >>> >> left
> >>> >> to the right.
>
> >>> >> There should be no second turn (up or down). If there is the second
> >>> >> turn,
> >>> >> then that's the bad curves.
>
> >>> >> My program needs to decern the good curves from bad curves.
>
> >>> >> I cranked a few algorithms but they don't work well. Are there
> >>> >> systematic
> >>> >> methods of handling this?
>
> >>> >> Thanks a lot!
>
> >>> > My browser wouldn't show your image, but here's a
> >>> > thought.  If your points are sampled at equal intervals,
> >>> > you can do a Fourier transform, use the analytic expression
> >>> > of the derivative term by term and the Fourier coefficients
> >>> > to calculate the derivative of the Fourier representation
> >>> > of your "function", and find the zeros of the derivative
> >>> > and take those as the turning points.  FWIW.
>
> >>> How? Could you please elaborate?- Hide quoted text -
>
> >>> - Show quoted text -
>
> >> This is a brief summary.  Hopefully it doesn't insult your
> >> intelligence and isn't too sketchy.
>
> >> Under certain conditions on F,
> >> F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> >>            b1 sin(kx) + b2 sin(2kx) + ...
> >> Using a discrete Fourier Transform (preferably using the Fast
> >> Fourier Transform algorithm if you have very many data points),
> >> you can calculate a discrete set of a's and b's the cause F to
> >> agree with your function at the x values for which you have F
> >> values.  Then F' is given by
> >> F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> >>         kb1 cos(kx) + 2kb2 cos(2kx) + ...
> >> Set F'(x) = 0 and solve for x's that satisfy this equation.
> >> These should approximate the turning point.
>
> >> I don't know if it will work for your application, or how
> >> practrical it will be.
>
> > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT)
> > and specifically used for detecting "changes" like this.
>
> I admit that I've never heard about that... how to do that? Could you please
> elaborate?
>
> Thanks!- Hide quoted text -
>
> - Show quoted text -

Detecting "turning points" requires a model. Intervention Detection
methods compute the probability of observing what you observed "BEFORE
YOU OBSERVED IT" ... Thus if that probability ( for the last observed
poinr ) is small ...say less than some critical value ..one can
conclude (ceterus paribus) that an anomaly has been observed.

Going forward ...

1. download and install the freeware time series analysis and
forecasting ackage called FREEFORE from http://www.autobox.com/freef.exe

2. provide it with a history set of values (recordings) and examine
whether or not the LAST POINT is found to be anomolous.

3. step though time 1 period by period and continue the evaluation of
whether FREEFORE reports that an INTERVENTION has occurred at the most
recent point.

hth

dave reilly
automatic forecasting systems
http://www.autobox.com
215-675-0652