Перечисление мотивов временных рядов всех длин

Мотивы временных рядов представляют собой повторяющиеся паттерны в длинных и зашумлённых временных рядах. Обычно мотивы используют для понимания динамики источника, поскольку повторяющиеся паттерны с высокой степенью сходства служат убедительным свидетельством отсутствия шума. В последнее время мотивы временных рядов также применяются как признаки для кластеризации, суммаризации, обнаружения правил и сжатия данных. Для всех этих задач желательно иметь множество высококачественных мотивов различной длины, что приводит к задаче перечисления мотивов в широком диапазоне длин. Существующие алгоритмы находят мотивы заданной длины. Тривиальный способ перечисления мотивов заключается в запуске одного из таких алгоритмов для всего диапазона длин. Однако такой перебор параметров вычислительно неприемлем для больших реальных наборов данных. В этой статье мы описываем точный алгоритм MOEN для перечисления мотивов. Этот алгоритм на порядок быстрее наивного алгоритма. Он устраняет необходимость повторно находить один и тот же мотив для разных длин и настраивать несколько параметров, зависящих от данных. Ускорение достигается за счёт использования новой границы для функции сходства при изменении длины; кроме того, в отличие от других алгоритмов обнаружения мотивов, алгоритм использует только линейный объём памяти. Мы описываем три тематических исследования в области энтомологии и распознавания активности, в которых MOEN перечисляет несколько высококачественных мотивов.