Piecewise regression: When one line simply isn’t enough
Piecewise regression models a timeseries with multiple linear segments when one line is insufficient. Datadog’s approach automatically detects both breakpoints and the number of segments, while avoiding a brute-force search of all possible partitions. It starts with an intentionally overfit model and greedily merges neighboring segments until the increase in error indicates that further merging would lose important structure. ## Objectives - **Automated breakpoint detection** - The algorithm identifies where one linear trend changes into another. - This is necessary for running hundreds of regressions per second without manual input. - **Automated segment-count selection** - The number of segments is not specified in advance. - The method must distinguish between data best represented by one line and data requiring several. - **No continuity requirement** - Adjacent regression lines do not need to meet at their shared breakpoint. - This allows the model to represent discontinuous changes in the data. ## Challenges - **Large search space** - A timeseries can be partitioned in exponentially many ways. - Although dynamic programming is more efficient than brute force, it remains too slow for Datadog’s performance requirements. - A greedy heuristic is used to eliminate large portions of the search space quickly. - **Balancing fit and simplicity** - More segments generally reduce the sum of squared errors. - Using one segment per point could produce nearly zero error but would provide little useful information for interpolation or extrapolation. - The goal is therefore to find the fewest segments that model the data accurately. ## Greedy Merging Algorithm - Begin with approximately **n/2 segments** for a timeseries containing *n* observations. - Fit each segment using ordinary least squares regression. - Repeatedly examine every pair of neighboring segments: - Calculate the increase in total squared error if the pair were merged. - Merge the pair producing the smallest error increase. - Continue merging until only one segment remains. - Record the segmentation state immediately before a merge appears to go too far. - If no merge triggers the stopping rule, select one large segment; otherwise, return the last recorded segmentation. ## Stopping Criteria - A merge becomes a potential stopping point when its increase in total squared error exceeds that of every earlier merge. - To avoid stopping prematurely on data that is fundamentally linear, the increase must also be less than **3% of the total error from a single-line regression**. - The 3% threshold is heuristic but was found to work well in practice. - For data generated from one noisy linear trend, error increases gradually as segments are merged, so no merge qualifies as an adequate stopping point and the algorithm ultimately selects one segment. The method provides a practical compromise between exhaustive optimization and model quality: greedy merging makes automated regression fast, while the error-based stopping rule limits overfitting and preserves meaningful changes in trend.
Read original(opens in new tab)