Re: Discrete-time finite-state Markov model
- From: jim <"sjedgingN0sp"@m@xxxxxxx>
- Date: Sun, 03 Sep 2006 08:15:36 -0500
Mario wrote:
I'm working on some time series. My need is to substitute observations
with multiple lines of trend (of variable length, related to the time
series values). I have to do it by a program, because I have to work on
a lot of time series.
I read something about the use of discrete-time finite-state Markov
model to reach this objective ("Tutorial PM2 - Time series similarity
measures" of Prof Gunopulus and Das, page 52-55).
Now I'm looking for a document that describes in detail the algorithm to
be used, so I could translate it in a program.
So, what I'm exactly looking for is an algorithm for segmenting time series.
Not sure how the Markov model would help unless the data fits that model
in some way.
In general the part in your description about extracting trends consists
of low pass filtering or averaging the data so that the high frequency
fluctuations are eliminated. So a filter might be a first step in your
algorithm.
The 2 most common algorithms of fitting polylines to a curve is by
angle deviation or by chordal deviation.
To approximate a curve by angle deviation each new line segment is
allowed to change in angle by some threshold angle. So you simply keep
extending the length of the line segment until you get to a point on the
curve that causes the angle between the new segment and the last segment
to exceed some angle.
Chordal deviation works in a similar way. Each new line segment is
extended until the line deviates from the curve (usually, just a measure
of the mid point of the line segment to the curve).
A little more sophisticated method is to use both techniques. For
instance, first start with a crude representation using the angle
deviation and then with another pass thru the data subdivide segments
that don't meet the chordal deviation test.
These methods are commonly used because they are easy and fast to
implement. One draw-back is that by definition with these methods the
nodes of the polyline end up on the curve being fitted, which is not
necessarily going to produce the very best fit to that curve. Obviously,
for any particular segment, if the end points are not constrained to the
curve itself then in most cases a better fit could be found for that
particular line segment to its corresponding curve segment. But that
makes it complicated to do for all segments in connected fashion and it
seems unlikely that you would want just a bunch of unconnected lines
that approximate the data for some unspecified (or randomly chosen)
periods of time.
The issue of the node being on the curve depends on what 'curve' it is
you are fitting to. If low pass filtering was used as a first step,
then the nodes for a fitted polyline are not on what would be the
original (unfiltered) curve anyway. Thus, the simple curve fitting
techniques applied to a filtered curve can be a very simple and fast
algorithm which will produce very similar results to what can be a
complex process of fitting the connected multiple line segments in such
a way that on average the distance everywhere is as close to the
original data points as possible.
-jim
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
.
- References:
- Re: Discrete-time finite-state Markov model
- From: Andor
- Re: Discrete-time finite-state Markov model
- Prev by Date: Re: Please suggest a 6week project
- Next by Date: Re: Calculating a "partial" IFFT
- Previous by thread: Re: Discrete-time finite-state Markov model
- Next by thread: Re: The importance of the Ubiquitous Covariance Matrix
- Index(es):
Relevant Pages
|
Loading
