Подгонка кусочно-линейных данных

Что такое надежный способ размещения кусочно-линейных, но шумных данных?

Я измеряю сигнал, который состоит из нескольких почти линейных сегментов. Я хотел бы автоматически разместить несколько строк в данных, чтобы обнаружить переходы.

Набор данных состоит из нескольких тысяч точек с 1-10 сегментами, и я знаю количество сегментов.

Это пример того, что я хотел бы сделать автоматически.

Я попробовал два подхода, наивно (используя только 3 сегмента). Конечно, там были бы более причудливые методы.

RANSAC, должен быть надежным механизмом подгонки. Алгоритм легко остановить после нескольких сегментов. Однако может быть трудно обеспечить непрерывность между сегментами - как это требуется в вашем приложении - по крайней мере, с простой реализацией. В качестве доказательства концепции я создал изображение из точек данных, чтобы я мог использовать механизм RANSAC, доступный в , функции обнаружения линий Mathematica.$ImageLines$

Установите кусочно-линейную модель, используя минимизатор общего назначения. Легко обеспечить непрерывность сегментов. Интересно, что тестирование на наличие остатков и других свойств может предоставить достаточно информации для автоматического определения количества сегментов - хотя я этого не пробовал. Вот как это выглядит в Mathematica:

$x[n]$

• $x[n]$$y[n]$

  $$y[n] = \begin{cases}1, &\text{if} ~ |(x[n+1]-x[n]) - (x[n]-x[n-1])| < \epsilon,\\ 0, &\text{otherwise.}\end{cases}$$ $\epsilon$$x[n-1],x[n], x[n+1]$$(n-1, x[n-1])$$(n,x[n])$$(n,x[n])$$(n+1,x[n+1])$

• $y[n]$$1$$0$$1$$1$$\epsilon$

• $y[n]$$x[3]$$x[88]$$x[94]$$x[120]$$x[129]$$\cdots$, и так далее. Расширьте A вправо и B влево, чтобы узнать, где они пересекаются; продлить B вправо и C влево, чтобы узнать, где они пересекаются и т. д. Поздравляем, теперь у вас есть непрерывная и кусочно-линейная модель для ваших данных.

(Спустя годы) кусочно-линейные функции - это сплайны степени 1, что большинству сборщиков сплайнов может быть сказано. Например, scipy.interpolate.UnivariateSpline может быть запущен с k=1 параметром сглаживания s, с которым вам придется играть - см. scipy-interpolation-with-univariate-splines .
В Matlab посмотрите, как выбрать узлы .

Добавлено: найти оптимальные узлы нелегко, потому что может быть много локальных оптимумов. Вместо этого вы задаете UnivariateSpline цель s, сумму ошибок ^ 2 и позволяете ей определять количество узлов. После подгонки get_residual()получит фактическую сумму ошибок ^ 2 и get_knots()узлы. Небольшое изменение sможет сильно изменить узлы, особенно при высоком уровне шума - ymmv.
На графике показаны подгонки к случайной кусочно-линейной функции + шум для различных s.

Для подбора кусочных констант см. Определение шага . Можно ли это использовать для PW линейного? Не знаю; если начать с дифференциации данных с шумом, это увеличит шум, не так.

Другие тестовые функции, и / или ссылки на документы или код, будут приветствоваться. Пара ссылок:
кусочно-линейная-регрессия-с-узлами-параметрами
$\qquad$Линейные сплайны очень чувствительны к тому месту, где расположены узлы сплайны
knot-selection-for-cubic-regression-splines
$\qquad$ Это сложная проблема, и большинство людей просто выбирают узлы методом проб и ошибок.
$\qquad$ Один из подходов, который становится все более популярным, - использовать вместо этого штрафные сплайны регрессии.

optimal k lines
    = optimal k - 1 lines up to some x
    + cost of the last line x to the end
over x  (all x in theory, nearby x in practice)

Динамическое программирование очень умно, но может ли оно превзойти грубую силу + эвристику для этой задачи?
Посмотрите отличные заметки по курсу Эрика Демейна в MIT 6.006 Введение в алгоритмы, а
также сегментированную линейную регрессию Google
и синдром Джона Генри.

Возьмите производную и ищите области почти постоянного значения. Вам нужно будет создать алгоритм для поиска областей с идеальным уровнем +/- наклона, и это даст вам наклон линии для этого раздела. Возможно, вы захотите выполнить некоторое сглаживание, например скользящее среднее, перед выполнением секционной классификации. Следующим шагом будет получение y-пересечения, которое в этот момент должно быть тривиальным.

Использование трендового фильтра l1 - еще одна идея:

Бумага

Пример в Интернете