How to do piecewise linear regression with multiple unknown knots?

Question

Are there any packages to do piecewise linear regression, which can detect the multiple knots automatically? Thanks. When I use the strucchange package. I could not detect the change points. I have no idea how it detects the change points. From the plots, I could see there are several points I want it could help me to pick them out. Could anyone give an example here?

Answer 1

I have programmed this from scratch once a few years ago, and I have a Matlab file for doing piece-wise linear regression on my computer. About 1 to 4 breakpoints is computationally possible for about 20 measurements points or so. 5 or 7 break points starts to be really too much.

The pure mathematical approach as I see it is to try all possible combinations as suggested by user mbq in the question linked to in the comment below your question.

Since the fitted lines are all consecutive and adjacent (no overlaps) the combinatorics will follow Pascals triangle. If there were overlaps between used data points by the line segments I believe that the combinatorics would follow Stirling numbers of the second kind instead.

The best solution in my mind is to choose the combination of fitted lines that has the lowest standard deviation of the R^2 correlation values of the fitted lines. I will try to explain with an example. Keep in mind though that asking how many break points one should find in the data, is similar to asking the question "How long is the coast of Britain?" as in one of Benoit Mandelbrots (a mathematician) papers about fractals. And there is a trade-off between number of break points and regression depth.

Now to the example.

Suppose we have the perfect data $y$ as a function of $x$ ($x$ and $y$ are integers):

$$\begin{array}{|c|c|c|c|c|c|} \hline &x &y &R^2 line 1 &R^2 line 2 &sum of R^2 values &standard deviation of R^2 \\ \hline &1 &1 &1,000 &0,0400 &1,0400 &0,6788 \\ \hline &2 &2 &1,000 &0,0118 &1,0118 &0,6987 \\ \hline &3 &3 &1,000 &0,0004 &1,0004 &0,7067 \\ \hline &4 &4 &1,000 &0,0031 &1,0031 &0,7048 \\ \hline &5 &5 &1,000 &0,0135 &1,0135 &0,6974 \\ \hline &6 &6 &1,000 &0,0238 &1,0238 &0,6902 \\ \hline &7 &7 &1,000 &0,0277 &1,0277 &0,6874 \\ \hline &8 &8 &1,000 &0,0222 &1,0222 &0,6913 \\ \hline &9 &9 &1,000 &0,0093 &1,0093 &0,7004 \\ \hline &10 &10 &1,000 &-1,978 &1,000 &0,7071 \\ \hline &11 &9 &0,9709 &0,0271 &0,9980 &0,6673 \\ \hline &12 &8 &0,8951 &0,1139 &1,0090 &0,5523 \\ \hline &13 &7 &0,7734 &0,2558 &1,0292 &0,3659 \\ \hline &14 &6 &0,6134 &0,4321 &1,0455 &0,1281 \\ \hline &15 &5 &0,4321 &0,6134 &1,0455 &0,1282 \\ \hline &16 &4 &0,2558 &0,7733 &1,0291 &0,3659 \\ \hline &17 &3 &0,1139 &0,8951 &1,0090 &0,5523 \\ \hline &18 &2 &0,0272 &0,9708 &0,9980 &0,6672 \\ \hline &19 &1 &0 &1,000 &1,000 &0,7071 \\ \hline &20 &2 &0,0094 &1,000 &1,0094 &0,7004 \\ \hline &21 &3 &0,0222 &1,000 &1,0222 &0,6914 \\ \hline &22 &4 &0,0278 &1,000 &1,0278 &0,6874 \\ \hline &23 &5 &0,0239 &1,000 &1,0239 &0,6902 \\ \hline &24 &6 &0,0136 &1,000 &1,0136 &0,6974 \\ \hline &25 &7 &0,0032 &1,000 &1,0032 &0,7048 \\ \hline &26 &8 &0,0004 &1,000 &1,0004 &0,7068 \\ \hline &27 &9 &0,0118 &1,000 &1,0118 &0,6987 \\ \hline &28 &10 &0,04 &1,000 &1,04 &0,6788 \\ \hline \end{array}$$

These y values have the graph:

Which clearly has two break points. For the sake of argument we will calculate the R^2 correlation values (with the Excel cell formulas (European dot-comma style)):

=INDEX(LINEST(B1:$B$1;A1:$A$1;TRUE;TRUE);3;1)
=INDEX(LINEST(B1:$B$28;A1:$A$28;TRUE;TRUE);3;1)

for all possible non-overlapping combinations of two fitted lines. All the possible pairs of R^2 values have the graph:

The question is which pair of R^2 values should we choose, and how do we generalize to multiple break points as asked in the title? One choice is to pick the combination for which the sum of the R-square correlation is the highest. Plotting this we get the upper blue curve below:

The blue curve, the sum of the R-squared values, is the highest in the middle. This is more clearly visible from the table with the value $1,0455$ as the highest value. However it is my opinion that the minimum of the red curve is more accurate. That is, the minimum of the standard deviation of the R^2 values of the fitted regression lines should be the best choice.

Piece wise linear regression - Matlab - multiple break points

Answer 2

In general, it's a bit odd to want to fit something as piece-wise linear. However, if you really wish to do so, then the MARS algorithm is the most direct. It will build up a function one knot at a time; and then usually prunes back the number of knots to combat over-fitting ala decision trees. You can access the MARS algotithm in R via earth or mda. In general, it's fit with GCV which is not so far removed from the other information criterion (AIC, BIC etc.)

MARS won't really give you an "optimal" fit since the knots are grown one at a time. It really would be rather difficult to fit a truly "optimal" number of knots since the possible permutations of knot placements would quickly explode.

Generally, this is why people turn towards smoothing splines. Most smoothing splines are cubic just so you can fool a human eye into missing the discontinuities. It would be quite possible to do a linear smoothing spline however. The big advantage of smoothing splines are their single parameter to optimize. That allows you to quickly reach a truly "optimal" solution without having to search through gobs of permutations. However, if you really want to seek inflection points, and you have enough data to do so, then something like MARS would probably be your best bet.

Here's some example code for penalized linear smoothing splines in R:

require(mgcv);data(iris);
gam.test <- gam(Sepal.Length ~ s(Petal.Width,k=6,bs='ps',m=0),data=iris)
summary(gam.test);plot(gam.test);

The actual knots chosen would not necessarily correlate with any true inflection points however.

Answer 3

Would MARS be applicable? R has the package earth that implements it.

Answer 4

I think the segmented package is what you are looking for.

Answer 5

I once came across a program called Joinpoint. On their website they say it fits a joinpoint model where "several different lines are connected together at the 'joinpoints'". And further: "The user supplies the minimum and maximum number of joinpoints. The program starts with the minimum number of joinpoint (e.g. 0 joinpoints, which is a straight line) and tests whether more joinpoints are statistically significant and must be added to the model (up to that maximum number)."

The NCI uses it for trend modelling of cancer rates, maybe it fits your needs as well.

Answer 6

... first of all you must to do it by iterations, and under some informative criterion, like AIC AICc BIC Cp; because you can get an "ideal" fit, if number of knots K = number od data points N, ok. ... first put K = 0; estimate L = K + 1 regressions, calculate AICc, for instance; then assume minimal number of data points at a separate segment, say L = 3 or L = 4, ok ... put K = 1; start from L-th data as the first knot, calculate SS or MLE, ... and step by step the next data point as a knot, SS or MLE, up to the last knot at the N - L data; choose the arrangement with the best fit (SS or MLE) calculate AICc ... ... put K = 2; ... use all previous regressions (that is their SS or MLE), but step by step divide a single segment into all possible parts ... choose the arrangement with the best fit (SS or MLE) calculate AICc ... if the last AICc occurs greater then the previous one: stop the iterations ! This is an optimal solution under AICc criterion, ok