Hi, I looking for a piecewise linear regression algorithm that can
model a set of data points, but the breakpoint is unknown.  Also, the
number of breakpoints is unknown, too.

For example, a set of points (0, 4), (1, 6), (2, 5)
                             (3, 100), (4, 130), (5, 120)
                             (7, 30), (8, 40), (9, 35)
Will result two breakpoint, and 3 lines of different slops. 

The answer to question should provide some example, so we can
understand it better.

I found researched related to this question, but they are a bit
difficult for me to understand, and involved other advance concepts.

---

Clarification of Question by jack_333-ga on 15 Sep 2006 16:58 PDT

Answer to this question should include
1) at least 25 data points
2) the slope change direction at least 3 time
3) the code should be as detail as possible. 

thanks.

---

Request for Question Clarification by hedgie-ga on 28 Sep 2006 00:26 PDT

Jack
        The problem is not fully defined.

When you allow more breakpoints youe will get better fit (smaller total error).

So.
You need to define a cost function which you want minimized, e.g.

Cost =  Error + weight* NoP

NoP is number of breakpoints.  Also, it would help to explain more
about the application:
Do you need fully automatic solution (thousands of cases) or 'common
sense solution'  - which (as an example) would be a curve  Error(NoP)
which would allow you to pick NoP you want based on human judgement.

To provide reference to research you have is also useful. May be all yoiu need
is some help with understanding and using it....

Hedgie

---

Clarification of Question by jack_333-ga on 01 Oct 2006 09:56 PDT

Hi Hedgie, 

I don't not have a well defined cost function yet.  

Descirption of data set (what I want to test now): 
1) The current point compare to previous point is only slightly
different for most of the time.
2) If we connect the pointers together, they will form some "waves"
for most of the time.

I just doing it for research purpose, I know there is a esay way to
find a linear regression, but I never seen anyway of doing a piecewise
linear regression. 

In fact, I want to find out all the way of doing a piecewise linear regression.

Also, the reference I looked at is 

http://www.ieiit.cnr.it/~muselli/papers/wirn01c.pdf#search=%22piecewise%20linear%20regression%22

Words in this article seem too technical for me to understand right now. 

thanks, 

Jack

---

Request for Question Clarification by hedgie-ga on 02 Oct 2006 23:01 PDT

Thanks for the prompt answer  Jack,

  I did look at the article -- it is  indeed written by a mathematician and
  probably more then you need.

You did not answer this request for clarification:
" Do you need fully automatic solution (thousands of cases) or 'common
sense solution'  few cases - human judgement can be used"

 I assume that 'common sense' (engineering solution) would be acceptable.
 Article deals with the ully automatic solution (Neural Net replaces
human judgement).


   Researches (not just here at GA) shy away from questions which say


 " In fact, I want to find out all the way of doing a piecewise linear regression."

 which I suppose is trying to say 'all ways of doing'

since 'finding ALL of anything' would require infinite amount of research time
and here $100 buys only few hours.

A can suggest some ways (peeling algorithm) as an answer.Few, not 'all ways'.
You may look at my other answers  concerning algorithms and then let  me
know if I should go ahead with the answer.

Past answers:
http://answers.google.com/answers/threadview?id=706840
http://answers.google.com/answers/threadview?id=449830
http://answers.google.com/answers/threadview?id=544391
....


Hedgie

P.S.  Be carefule with 'all the way' phrase. In US english it ,ay mean
different things. You can google it :-)

Just a suggestion that others may want to take further: The problem is
to find the breaks in the different lines. Let us do this inductively.
That is, suppose that we know how to break-up the points x(1),...,
x(k) and we are looking at the k+1st point. Suppose further that the
last group to be fitted to a line is x(i),...x(k). Then we do the
following: (Assume there are at least 3 points from x(i) to x(k).)

Find the least squares fit to x(i),...,x(k). Use the parameters to
estimate y(k+1). There is an associated error (that is, standard
deviation) with the estimate as well. If the y(k+1) is several
standard deviations from this estimate, then the k+1st point is
considered to be on a different line.

[The formula for the error of the estimate of y(k+1) is s*sqrt(1 + 1/n
+ (x(k+1)-xbar)^2/Sx^2 ), where s is the standard error of the fit, n
is the number of points in this piece, xbar is the average x in this
piece, and Sx^2 is the sum of the squares of the differences of the
x's from xbar. You can look up this formula up in any good text on
linear regression.]

What would be the realworld application for this kind of stuff?

Ok if I understand your problem correctly it should be pretty simple.

Since you are looking for a linear connection between the given points.

First of all you have to calculate the slope of the lines.

The formula to do this is:  deltaY / deltaX = (Y2-Y1) / (X2-X1);

So for the given points it would be: (4-6) / (0-1) = 2

Now all you have to do: Check this value. If it's to big then you got a breakpoint.

C Pseudo Code

{
slope = (Y[NEXT] - Y[LAST]) / (X[NEXT]-X[LAST]);


}

Sorry I hit enter to fast.

So the pseudo code again:

C Pseudo Code

{
slope = (Y[NEXT] - Y[LAST]) / (X[NEXT]-X[LAST]);
if (abs(slope) > maximum_value) breakpoint(); 

}

To get a good maximum_value you can use historical data, probabilities
or what ever fits the situation the best. (That depends on your
programm)



I jope I could help you out :-)

If you got some questions on my answer please feel free to contact me.

Thanks sebastian

Hi seb1994-ga, 

can you please provided a "detailed" example please?

Yeah, what you said it is a basic concept behind this, and I am
looking for more advance way doing it.

Thanks.