Как найти периодические события в серии времён?

#алгоритм #машинное_обучение

Есть серия timestamp'ов. Большинство из них ложатся на периодическую сетку. Но:


не все – могут быть выпадающие из сетки сэмплы (их допустимый процент - задаётся;
не всегда подряд на каждое значение сетки (процент пропусков - задаётся);
не идеально точно – допустимо небольшое отклонение (задаётся).


Задача: найти период сетки. Наверное, могут быть случаи, когда несколько вариантов
периода сеток - тогда выбираем охвативший наибольшее число сэмплов, с наибольшим периодом.
А может случиться, и что с заданными параметрами решение отсутствует.

Пример. Серия с периодом (который в задаче надо найти) = 30, в секундах:

10, 40, 72, 99, 164, 172, 190


Отклонения в +/- 4 секунды считаем допустимыми. Пропуск шага 130 – ок. Всего одно
«лишнее» значение 172, не вписывающееся в ряд – тоже ок. 

Можно было бы считать шагом сетки 10, или вообще 1, но это мелко : ) Чем больше шаг
– тем «лучше». Это мы уже о ф-ии качества говорим?

Каким способом искать решение? Не могу сообразить, как подступиться. Задача именно
для небольших наборов данных. Никаких bigdata.

Upd. Поиск наибольшего общего делителя с допустимой погрешностью – можно ещё так
сформулировать мою задачу.
    

Ответы

Ответ 1

Приведён небольшой массив данных, который в рамках задачи требуется аппроксимировать
линейной функцией.
По методу наименьших квадратов для зависимости yi = a xi + b нетрудно получить СЛАУ вида
s2a + s1b = r1,
s1a + s0b = r0,
где
s0 = sum(i0) = n,
s1 = sum(i1) = n(n-1)/2,
s2 = sum(i2) = n(n-1)(2n-1)/6,
r0 = sum(i0xi) = sum(xi),
r0 = sum(i1xi) = sum(ixi),
решение которой элементарно.

Программа:

$issue = [10, 40, 72, 99, 164, 172, 190];

function line($arr){
    $r0 = array_sum($arr);
    $r1 = 0;
    foreach($arr as $key=>$item){
        $r1 += $key*$item;
    }
    $s0 = count($arr);
    $s1 = $s0*($s0-1)/2;
    $s2 = $s1*(2*$s0-1)/3;
    $delta = $s0*$s2 - $s1*$s1;
    $delta1 = $s0*$r1 - $s1*$r0;
    $delta2 = $s2*$r0 - $s1*$r1;
    $a = $delta1/$delta;
    $b = $delta2/$delta;
    return [$a, $b];
}
list($a, $b) = line($issue);
printf("y = %.3f x + %.3f b", $a, $b);


Результат:


y = 32.000 x + 10.714 b


Ответ 2

Я бы попробовал как-то так.


Отсортируем значения, подсчитаем их последовательные разности. (Разности нужны, чтобы
от сетки вида aT + b перейти к сетке вида T. Например идеальные тестовые данные 5,
25, 45, 65 превратятся в 20, 20, 20, 20). Получаем в нашем случае:

10, 40, 72, 99, 152, 164, 190
30, 32, 27, 53,  12,  26

Предполагаем, что большинство соседних разностей находятся в окрестности «истинного»
значения периода. Кластеризуем полученные разности. Для этого установим величину r,
и объединим в группы разности по следующему принципу:


Сначала список групп пуст. Обходим список чисел по одному.
Для очередного числа, будем считать, что оно попадает в группу с точностью r, если
оно находится на расстоянии не больше r от хотя бы одного числа этой группы.
Если число не попало ни в одну группу, оно начинает новую группу.
Если число попало только в одну группу, оно к ней присоединяется.
Если число попало в несколько групп, эти группы и число сливаются в одну группу.

В конце должна получиться одна группа, содержащая, скажем, больше половины всех чисел.
Если в наибольшей группе слишком много чисел, уменьшаем r вдвое и повторяем. Если слишком
мало, увеличиваем вдвое и повторяем. Для нашего случая:


r = 1: каждое число — отдельный кластер, увеличиваем r
r = 2: кластеры [12], [26, 27], [30, 32], [52], увеличиваем r
r = 4: кластеры [12], [26, 27, 30, 32], [52]. Нашли.

Среднее арифметическое наибольшей группы и есть приближение к шагу. В нашем случае, 28.75
Далее, пробуем уточнить оценку, расставляя числа в решётке. Пусть истинный период
T, мы знаем, что T ≈ 28.75. Начнём с какого-нибудь из чисел, сформировавших «большинство».
Например, 26 — член большинства, получилось из 190 и 164, начинаем от 164.


следующее число 190, разность 26. Записываем: T ≈ 26
предыдущее число 152, разность 12, поскольку она слишком далека от целого числа периодов
(12/T ≈ 12/28.75 ≈ 0.41), выбрасываем это число из рассмотрения, оно «постороннее».
предыдущее число 99, разность 65. 65/28.75 ≈ 2.25, считаем, что 99 лежит на сетке,
записываем: 2T ≈ 65, T ≈ 32,5
предыдущее число 72, разность 27, делим на предполагаемый период, получаем 0.93,
ложится на сетку. Записываем T ≈ 27
аналогично получаем следующие оценки T ≈ 32 и T ≈ 30


Усредняем полученные приближения, получаем немного более хорошее приближение 29.5.




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