View Question
Q: Looking for a piecewise linear regression algorithm (Computer Science). ( No Answer,   5 Comments )
 Question
 Subject: Looking for a piecewise linear regression algorithm (Computer Science). Category: Computers > Algorithms Asked by: jack_333-ga List Price: \$100.00 Posted: 09 Sep 2006 17:46 PDT Expires: 09 Oct 2006 17:46 PDT Question ID: 763789
 ```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 :-)```
 There is no answer at this time.

 Subject: Re: Looking for a piecewise linear regression algorithm (Computer Science). From: berkeleychocolate-ga on 11 Sep 2006 13:00 PDT
 ```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.]```
 Subject: Re: Looking for a piecewise linear regression algorithm (Computer Science). From: gorillabiscuit-ga on 13 Sep 2006 15:09 PDT
 `What would be the realworld application for this kind of stuff?`
 Subject: Re: Looking for a piecewise linear regression algorithm (Computer Science). From: seb1984-ga on 13 Sep 2006 15:31 PDT
 ```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]); }```
 Subject: Re: Looking for a piecewise linear regression algorithm (Computer Science). From: seb1984-ga on 13 Sep 2006 15:36 PDT
 ```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```
 Subject: Re: Looking for a piecewise linear regression algorithm (Computer Science). From: jack_333-ga on 15 Sep 2006 17:34 PDT
 ```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.```