Алгоритм: есть ли линейный тренд в данных?

Question

У меня постоянно поступающие данные, представленные массивом целых чисел x = [x1, ..., xn], n <1 000 000. Каждые два элемента удовлетворяют следующему условию x [i] <x [i + 1]. </p>

Мне нужно как можно быстрее обнаружить такую ​​точку останова, где линейный тренд этих данных заканчивается и трансформируется в квадратичный тренд. Данные всегда начинаются с линейного тренда ...

Я пытался вычислить

k = (x[i+1] - x[i])/ (x[i] - x[i-1]) 

но этот тест не слишком надежный ... Может быть, есть более простой и эффективный статистический тест ... В этом случае вычисление линии регрессии происходит медленно ...

Спасибо за вашу помощь ...

Answer 1

Следите за первым производным и вторым производным. То есть сохраните среднее значение и дисперсию x [i] -x [i-1]. И сохраните сумму и дисперсию (x [i + 1] -x [i]) - (x [i] -x [i-1]).

Для линейного тренда среднее значение первой производной должно быть постоянным, и если вы наблюдаете отклонение от среднего (которое вы можете рассчитать, используя дисперсию), то вы можете сказать, что что-то не так. Среднее значение второй производной должно быть 0.

Для квадратичного тренда среднее значение первой производной увеличивается. Таким образом, вы найдете много образцов с большим отклонением от среднего. Поведение второй производной аналогично поведению первой производной в линейном случае.

Алгоритм (с использованием только второй производной):

1. Для каждого входа вычислить знак (+ ve или -ve) второй производной
2. Следите за тем, сколько однородных признаков вы получили в последнее время (т. Е. Если последовательность - + - ++++, ответ 4)
3. Если длина однородных знаков больше порога (скажем, 40?), То пометьте его как начало квадратичной последовательности

Answer 2

На самом деле вы вычисляете производную функции. Возможно, вы должны использовать больше очков для его расчета, например, 5 см. трафарет из пяти точек

Answer 3

Для сверхбыстрого решения вы можете рассмотреть тест вроде:

| X[i + s] - 2 X[i] + X[i - s] | > k (X[i + s] - X[i - s])

для хорошо выбранных s и k.

Посмотрите на сюжет | X [i + s] - 2 X [i] + X [i - s] | / (X [i + s] - X [i - s]) как функция от i, для увеличения значений s.

Answer 4

Здесь вы можете использовать регрессию текущего окна.

Вычисление коэффициентов линейной регрессии по точкам W включает в себя суммы членов в форме X [i], iX [i] и X [i] ^2.Если вы сохраняете эти суммы, вы легко сдвигаетесь на одну точку, выводя слагаемые для самой левой точки и добавляя слагаемые для самой правой точки (iX [i] становится (i + 1) .X [i], ieiX [i]+ X [I]).Ваши значения данных являются целыми числами, накопления округления не будет.

При этом вы можете вычислить регрессию в постоянном времени для каждого W последовательных точек и обнаружить падение коэффициента корреляции.