How to identify breaking points in a numeric array in MATLAB

Question

Good afternoon guys, I have this new question, I hope that you can help me again:

I have a vector, which you can find in the next link:

https://drive.google.com/file/d/0B4WGV21GqSL5Y09GU240N3F1YkU/edit?usp=sharing

The vector plotted looks like this:

As you can see, there's some parts in the graph where the data has a behavior almost linear. This is what i'm talking about:

What I need is to find those breaking points based in the linearity of some parts in the data. And you probably ask yourself, what happens when the part of the data is not linear, well, the algorithm won't take that part.

I hope that you can help me, thanks.

Answer 1

What you're trying to do is called Piecewise Linear Time Series Segmentation.

There is a lot of methods to solve this problem which differ by their complexity and accuracy.

Here is the simplest one, called sliding window segmentation:

function [breaks vals] = segment( data, max_error )
    breaks = [];
    vals = [];
    left = 1;
    for right = 2:length(data)
        err = linear_regresion(data(left:right));
        if max(abs(err)) > max_error
            breaks(end+1) = right-1;
            vals(end+1) = data(right-1);
            left = right;
        end
    end
end

function err = linear_regresion( data )
    n = length(data);
    x = (1:n)' - (n+1)/2;
    y = data - mean(data);
    k = sum(x.*y) ./ sum(x.^2);
    err = y - k*x;
end

linear_regresion here is an implementation of simple linear regression algorithm.

In my example I used maximum absolute error as a stopping criteria, but you may replace it with any other fitting function, e.g. mean squared error.

Here is an example of segmenting your data with max_error = 0.04:

You can find more about this and other segmentation techniques in this survey paper.