Оценка сходства временных рядов на основе моделей

В настоящей работе рассмотрено расстояние между временными рядами, основанное не на данных, а на моделях временных рядов. С помощью метода Монте–Карло, показано, что данное расстояние более устойчиво к выбросам и дает более точные результаты для более длинных временных рядов (при больших T)....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автор:	Книгницкая, Т.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Назва видання:	Проблемы управления и информатики
Теми:	Методы обработки и защиты информации
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/180823
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Оценка сходства временных рядов на основе моделей / Т.В. Книгницкая // Проблемы управления и информатики. — 2019. — № 4. — С. 94-104. — Бібліогр.: 40 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-180823
record_format	dspace
spelling	irk-123456789-1808232021-10-21T01:26:43Z Оценка сходства временных рядов на основе моделей Книгницкая, Т.В. Методы обработки и защиты информации В настоящей работе рассмотрено расстояние между временными рядами, основанное не на данных, а на моделях временных рядов. С помощью метода Монте–Карло, показано, что данное расстояние более устойчиво к выбросам и дает более точные результаты для более длинных временных рядов (при больших T). Визначення міри відстані між часовими рядами є відправною точкою для багатьох завдань інтелектуального аналізу даних, таких як кластеризація та класифікація. Кластеризація є основним методом навчання без вчителя, який використовується для розбиття даних на групи на основі внутрішніх і апріорних невідомих характеристик, властивих даним. При розбитті даних на кластери виникає потреба правильного вибору метрики подібності між об’єктами. Описано основні існуючі алгоритми пошуку відстані між часовими рядами, які добре описують дану проблему для малих часових рядів та за відсутності викидів. Викиди, властиві реальним процесам, призводять до неправильної кластеризації, а отже, до прийняття неправильних рішень. Запропоновано розглянути відстань між часовими рядами у вигляді відстані між моделями (ARIMA) даних часових рядів. За наявності великої кількості викидів класичні методи лінійно збільшують відстані між часовими рядами, в той же час запропонована у статті відстань за моделями поводить себе як логарифмічна функція. Показано, що при зростанні кількості вимірювань відносні похибки для всіх класичних методів залишаються майже незмінними. Відносна похибка для оцінки відстані за моделями значно менша та спадає при зростанні кількості вимірювань. Основним досягненням статті є визначення відстані між часовими рядами, яка ґрунтується на понятті моделі, і порівняння цієї відстані з відповідними класичними найбільш вживаними методами. Використовуючи метод Монте–Карло, показано, що запропонована відстань більш стійка до викидів і дає більш точні результати для часових рядів з великою кількістю спостережень. Крім того, складність алгоритму обчислення відстані на основі моделей менша за аналогічну обчислювальну складність існуючих алгоритмів (DTW, ERP, Евкліда). Немає сумнівів, що використання моделей є одним з найбільш зручних інструментів дослідження подібності процесів. Крім того, для аналізу з врахуванням даного алгоритму зручно використовувати усереднені еволюції і граничні еволюції в схемі дифузійної апроксимації. Також за рахунок стійкості до викидів граничних еволюцій введену відстань можна використовувати при кластеризації для побудови більш стійких до шумів кластерів. Determining the measure of the distance between time series is the starting point for many data mining tasks such as clustering and classification. Clustering is the main method of teaching without a teacher, which is used to divide data into groups based on the internal and a priori unknown characteristics inherent in the data. When dividing data into clusters, the need arises to select the similarity metric between objects. The paper describes the main existing algorithms for the “distance” searching between time series, which well describe this problem for small time series and under the absence of outliers. Outliers inherent in real processes lead to improper clustering, and, consequently, to wrong decisions making. It is proposed to consider the distance between time series in the form of the distance between models (ARIMA) of these time series. In the presence of a large number of outliers, classical methods linearly increase the distances between time series, while the distance proposed in the article according to the models behaves as a logarithmic function. It is shown that with an increase in the number of measurements, the relative errors for all classical methods remain almost unchanged. At the same time, the relative error for estimating the distance by the models is much smaller and decreases with an increase in the number of measurements. The main achievement of the article is the determination of the distance between time series, based on the concept of a model, and the comparison of this distance with the corresponding classical methods most commonly used. Using the Monte Carlo method, it has been shown that the proposed distance is more resistant to outliers and gives more accurate results for time series with a large number of observations. In addition, the complexity of the algorithm for calculating distances based on models is less than the analogous computational complexity of existing algorithms (DTW, ERP, Euclidean distance). There is no doubt that the use of models is one of the most convenient tools for studying the similarity of processes. In addition, for analysis taking into account this algorithm, it is convenient to use the averaged evolutions and the limiting evolutions in the diffusion approximation scheme. Also, due to the resistance to outliers of limiting evolutions, the entered distance can be used in clustering to build more noise-resistant clusters. 2019 Article Оценка сходства временных рядов на основе моделей / Т.В. Книгницкая // Проблемы управления и информатики. — 2019. — № 4. — С. 94-104. — Бібліогр.: 40 назв. — рос. 0572-2691 http://dspace.nbuv.gov.ua/handle/123456789/180823 519.2 ru Проблемы управления и информатики Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки и защиты информации Методы обработки и защиты информации
spellingShingle	Методы обработки и защиты информации Методы обработки и защиты информации Книгницкая, Т.В. Оценка сходства временных рядов на основе моделей Проблемы управления и информатики
description	В настоящей работе рассмотрено расстояние между временными рядами, основанное не на данных, а на моделях временных рядов. С помощью метода Монте–Карло, показано, что данное расстояние более устойчиво к выбросам и дает более точные результаты для более длинных временных рядов (при больших T).
format	Article
author	Книгницкая, Т.В.
author_facet	Книгницкая, Т.В.
author_sort	Книгницкая, Т.В.
title	Оценка сходства временных рядов на основе моделей
title_short	Оценка сходства временных рядов на основе моделей
title_full	Оценка сходства временных рядов на основе моделей
title_fullStr	Оценка сходства временных рядов на основе моделей
title_full_unstemmed	Оценка сходства временных рядов на основе моделей
title_sort	оценка сходства временных рядов на основе моделей
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Методы обработки и защиты информации
url	http://dspace.nbuv.gov.ua/handle/123456789/180823
citation_txt	Оценка сходства временных рядов на основе моделей / Т.В. Книгницкая // Проблемы управления и информатики. — 2019. — № 4. — С. 94-104. — Бібліогр.: 40 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT knignickaâtv ocenkashodstvavremennyhrâdovnaosnovemodelej
first_indexed	2025-07-15T21:09:26Z
last_indexed	2025-07-15T21:09:26Z
_version_	1837748736536608768
fulltext	© Т.В. КНИГНИЦКАЯ, 2019 94 ISSN 0572-2691 МЕТОДЫ ОБРАБОТКИ И ЗАЩИТЫ ИНФОРМАЦИИ УДК 519.2 Т.В. Книгницкая ОЦЕНКА СХОДСТВА ВРЕМЕННЫХ РЯДОВ НА ОСНОВЕ МОДЕЛЕЙ Ключевые слова: расстояние между временными рядами по моделям, класте- ризация, кластер, временной ряд, модель временного ряда, DTW, ERP. Введение Большинство задач, основанных на временных рядах как на математических моделях, посвящено подбору оптимальных моделей для временных рядов. Наряду с этой проблемой за счет развития машинного обучения Big Data и теории слу- чайных процессов все больше внимания уделяется кластеризации временных ря- дов [1]. Решение данной проблемы чаще всего проводят двумя методами. 1. Наивный — рассматривают временной ряд как точку в TR , где T — дли- на временного ряда. При этом кластеризация временного ряда превращается в кластеризацию точек в TR [2]. 2. Кластеризация на основе параметров модели. Для всех временных рядов выбирается одна «базовая» модель, например [3–5]. Следующий шаг — пред- положение о распределении основных параметров модели и вычисления апо- стериорных оценок параметров временных рядов. На основе данных параметров и проводится кластеризация. Недостаток первого метода очевиден, поскольку он не учитывает особенно- сти модели временного ряда — наличие корреляции между временными рядами, наличие детерминированных компонент (тренда, сезонной компоненты), вид ав- токорреляционной функции, спектральную плотность и др. Основной недостаток второго метода, как вероятностного метода, заключается в том, что модель времен- ного ряда фиксированная и выбор начального распределения параметров выбирает- ся с точки зрения простоты вычисления апостериорного распределения. Хотя вто- рая проблема для второго алгоритма достаточно легко решается с помощью алго- ритмов Метрополиса–Гaстинга [1], Гиббса [6], однако для небольших временных рядов неудачный подбор начального распределения параметров приводит к плохо- му приближению апостериорного распределения. Кроме того, методика данного метода основывается на разбиении временного ряда на три основные части: ,tttt cspx  (1) где tx — значение временного ряда, tp — полиномиальный тренд, ts — значе- ние сезонной компоненты, tc — случайная составляющая временного ряда, для которой определяется модель временного ряда. Аналогичное разбиение будет ис- пользоваться и в данной работе. Следует отметить, что разбиение ряда на компо- ненты (1) прослеживается также и во многих других моделях случайных процес- сов — семимартингалы, полумартингалы и тому подобное. https://teacode.com/online/udc/51/519.2.html Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 95 В настоящей работе рассматриваются стационарные временные ряды: мате- матическое ожидание и дисперсия не меняются со временем — постоянные вели- чины; ковариация зависит только от расстояния между измерениями временного ряда и не зависит от их значений. Если же входные временные ряды нестационар- ны, с помощью взятия дифференциальных разниц их приводят к стационарным временным рядам [7]. 1. Обзор исследований Способы оценки сходства данных временных рядов представляют интерес для специалистов по анализу данных, поскольку временные ряды являются одни- ми из наиболее широко применяемых математических моделей для описания ре- альных явлений. Одна из критических исследовательских проблем анализа вре- менных рядов — выбор функции расстояния для определения понятия сходства между двумя временными рядами. Рассматривая непрерывные функции, приходим к выводу, что наиболее рас- пространенной метрикой для временных рядов является евклидово расстояние: ,))((  yxyxdE  инвариантное при рассмотрении изменений в порядке представления временных рядов. Это означает, что евклидово расстояние в принципе неприменимо для нахождения расстояний в случае многомерных временных рядов и не учитывает корреляцию между наблюдениями, что является существенным недостатком. Для сравнения данных временных рядов, где тренды и эволюции должны учитывать- ся, или, если форма временного ряда описывается последовательностью функций, актуальным является соотношение Пирсона: , ))(())(( ))(( 1)(    yyyyxxxx yxyx yxdC    которое также широко используются, хотя не лишено искажений и проблем [8]. Расстояние Махаланобиса )()(),( 1   yxCyxyxdM  можно рассматривать как эволюционное евклидово расстояние, которое учитывает корреляцию данных. Это расстояние использует матрицу ковариации входных век- торов C для «взвешивания» особенностей временного ряда. Расстояние Махала- нобиса [9] обычно успешно работает с большими наборами данных с уменьшенны- ми характеристиками. Более детальное описание расстояний можно найти в [10]. В последних исследованиях по этой тематике разработана серия методов для нахождения расстояний между многомерными временными рядами, которые можно разделить на два класса. Первый класс включает функции, основанные на нормах 1L и 2L [11]. Примерами функций этого класса является динамическая трансформация времени (Dynamic Time Warping distance — DTW) [12] и коррек- тировка расстояния со штрафом (Edit Distance with Real Penalty — ERP) [4]. Второй класс функций расстояний включает в себя методы, которые вычис- ляют оценку сходства за порогом соответствия  . Примерами этого класса функ- ций является самая длинная общая подпоследовательность (Longest Common Subsequence — LCSS) [13] и корректировка расстояния в реальной последова- тельности (Edit Distance on Real Sequence — EDR) [14]. Предыдущие исследова- ния [15, 16] показали, что этот второй класс методов является лучшим при нали- чии шумов и смещения по времени. 96 ISSN 0572-2691 Динамическая трансформация времени (DTW) специально предназначена для сравнения временных рядов [17]. Применение DTW позволяет провести нелиней- ное отображение двух векторов, минимизируя расстояние между ними. Расстоя- ние DTW может использоваться для векторов разной длины: ]...,,,[ 21 nxxxX  и ]....,,,[ 21 nyyyY  . С помощью DTW определяется матрица расходов С размерно- сти mn , которая содержит расстояния (обычно евклидовы) между двумя точка- ми: ix и iy . Временная трансформация ,...,,, 21 KwwwW  где  Knm ),(max ,1 nm формируются набором матричных компонент на следующих условиях:  граничные условия: )1,1(1 Cw  и );,( mnCwK   условия монотонности: дано ),( baCwk  и ),,(1 baCwk  aa  и ;bb   условие величины шага: дано ),( baCwk  и ),,(1 baCwk  1 aa и .1bb Существует много способов, обеспечивающих выполнение указанных усло- вий. Один из них — расстояние DTW, с помощью которого минимизируется зна- чение временной трансформации во временном ряду: .min),( 1    K k Kw wyxd  (2) Основным недостатком (2) остается расчет пути минимальной стоимости. К тому же расстояние DTW не может рассматриваться как метрика, потому что оно не удовлетворяет неравенству треугольника. Обзор показателей метрик расстояний для кластеризации временных рядов можно найти в [18]. Другой важный способ нахождения расстояний — косинус измерения [5], что хорошо подходит для моделей с разной или переменной дли- ной или методы сходства Жаккара и Танимото [19], которые также интуитивно можно понимать как комбинацию евклидовых расстояний и корреляций. Итак, рассмотрим временной ряд X , который определяется последователь- ностью реальных значений (измерений), где каждое значение ix взято в конкрет- ный момент времени, т.е. ]....,,,[ 21 nxxxX  Имея последовательность X , кото- рая описывает временной ряд, можно нормировать временной ряд, используя среднее  и стандартное отклонение  : ....,,,)(Norm 21              nxxx X Нормализация рекомендуется для того, чтобы расстояние между двумя времен- ными рядами было инвариантно для масштабирования амплитуды и смещения временных рядов. Проблема использования 1L -нормы для временных рядов, как указано выше, заключается в том, что она требует, чтобы временные ряды были одинаковой длины и не имели локального сдвига по времени. Если необходимо найти рассто- яние между двумя временными рядами разной длины, то можно добавить измере- ния в качестве пропущенных значений (gaps) во временном ряду с меньшей дли- ной или удалить значение в более длинном временном ряду. Тем самым исчезнет проблема равенства длин и локального сдвига по времени. Рассмотрим расстояние корректировки строки:        случае,противномв1 ,пропущенноилиесли,1 ,если,0 ),( ii ii ii xy xy xydist (3) где iy , ix — элементы строк. Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 97 При переходе от последовательностей до временных рядов сложность заклю- чается в том, что элементы iy и ix являются не символами, а реальными значе- ниями. Для анализа временных рядов необходимо учитывать корреляции между значениями ряда. Расстояние EDR позволяет учесть реальные значения посред- ством введения параметра  , который будем называть порогом:      случае.противномв1 ,если,0 ),( ii iiedr xy xydist (4) Сформулируем недостатки расстояния EDR: каждая разница между элемен- тами временных рядов равна единице (второй случай в формуле (4)); использова- ние порога  . Этой проблемы не существует для расстояния DTW, так как ис- пользуется 1L -норма между двумя непропущенными элементами. Расстояние DTW [20] отличается от EDR двумя основными моментами, ко- торые описываются следующей формулой:             пропущено.если, пропущено,если, пропущены,не,если, ),( 1 1 iii iii iiii iidtw yyx xxy xyxy xydist (5) Основная причина, почему DTW не удовлетворяет неравенству треугольни- ка, заключается в том, что когда необходимо интерполировать пропущенное из- мерение, повторяется (копируется) предыдущий элемент. Таким образом, как по- казано во втором и третьем случаях формулы (5), разница между элементом и пропущенным значением зависит от 1iy или 1ix . Рассмотрим расстояние ERP, так как оно использует «штраф» между двумя не пропущенными значениями и постоянной величиной вычисления расстояний для пропущенных значений. Таким образом, метод ERP использует следующую формулу для вычисления расстояния:           пропущено,если, пропущено,если, пропущены,не,если, ),( ii ii iiii iierp ygx xgy xyxy xydist (6) где g — некоторая константа, «штраф» за пропущенное значение или усреднен- ное значение соседних значений временного ряда. Константа g может быть вы- брана как среднее двух или нескольких соседних значений временного ряда. Спе- циалист по анализу данных с помощью анализа графика временного ряда может сделать вывод, сколько значений необходимо рассмотреть для заполнения про- пущенных измерений. Основываясь на формуле (6), расстояние ERP между двумя временными ря- дами определяется формулой (9) и обозначается ).,( XYERP Тщательное сравне- ние формул (7)–(9) показывает, что расстояние ERP можно рассматривать как комбинацию 1L -нормы и EDR. Сложность алгоритмов DTW и ERP составляет ),(NMO где N и M — дли- ны двух входных последовательностей. Без потери общности, предполагая, что MN  , сложность алгоритма составляет ).( 2NO Алгоритмы имеют ту же слож- ность при рассмотрении многомерных временных рядов в пространстве. 98 ISSN 0572-2691 ))},(Re,(),),((Re)),(Re),((Remin{ [38];èíà÷å),( ,0èëè0åñëè, ,0åñëè,0 ),( 11 XstYDTWXYstDTWXstYstDTWA Axydist mn nm XYDTW dtw             (7) ; ),())(Re,( ),,()),((Re ),,())(Re),((Re min èíà÷å; ,0),(åñëè)),(Re),((Re ,0åñëè, ,0åñëè, ),( 1 1 11 11                            xgapdistXstYEDR gapydistXYstEDR xydistXstYstEDR B B xydistXstYstEDR nm mn XYEDR edr edr edr edr (8)                               ).,())(Re,( ),,()),((Re ),,()(Re),(Re min ;èíà÷å ,0åñëè, ,0åñëè, ),( 1 1 11 1 1 xgapdistXstYERP gapydistXYstERP xydistXstYstERP Ñ C ngy mgx XYERP erp erp erp i m i n (9) 2. Алгоритм поиска оптимальных моделей Как отмечалось выше, важную роль в исследовании временных рядов играет кластеризация временных рядов. В качестве меры сходства при кластеризации яв- ляется следующая мера [21]: ,),( 1 2 )...,,( 1 1      m k ji Gjik m MMd n GGHM k (10) где ),( ji MMd — расстояние между моделями временных рядов i и .j Данное расстояние, как основной объект работы, вычислим ниже. Итак, главной пробле- мой для определения меры сходства )...,,( 1 mGGHM является определение рас- стояния между временными рядами ).,( ji MMd 2.1. Постановка задачи. Рассмотрим N временных рядов, функционирование которых отслеживается в течение T периодов, т.е. данные имеют следующий вид:               NTN T T xx xx xx ... ......... ... ... 1 212 111 . (11) Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 99 Базовой моделью временного ряда, как указывалось выше, является ),( qpARMA -модель: ,...)( 0 p pLL  ,...)( 0 q qLL  причем 100  ; L — лаговый оператор. Таким образом, наряду с работой [21], где определялась одна модель для всех временных рядов, в данном случае нужно проверить N total QPN ))1)(1((  (12) моделей, что обычно не представляется возможным при большом количестве мо- делей, т.е. при больших QP, и N . Учитывая вычислительную сложность по- ставленной задачи, в настоящей работе предложен алгоритм поиска расстояния между двумя временными рядами, основываясь на их моделях, с использованием только ),( QPARMA для всех временных рядов. В большинстве работ «расстояние» между моделями, которое характеризует временные ряды 1x и 2x , определяется следующим образом: ,)(),( 1 2 2121    T t tt xxMMd т.е. рассматривается 2L -норма. Данная мера позаимствована из наивного подхода и не учитывает моделей, согласно которым функционируют временные ряды. Для определения расстояния между моделями используется понятие )(MA представления [7]. Согласно утверждению разд. 1 [22] произвольный стационарный временной ряд tx , задан- ный с помощью ),( qpARMA модели (4), однозначно можно записать в виде )(MA -представления: ,)( ~ )( tLtx  (13) где ... ~ ... ~ )( ~ 1  k k LLLL , (14) причем для модели, которая задает стационарный временной ряд: . ~ 2 1    k k Используя представление (14) для ),( qpARMA -модели, определим расстоя- ние между моделями 1M и 2M следующим образом: 21 1 21 ~~ ),( kk k MMd     . (15) Для моделирования предыдущей формулы на примере следует отметить, что ряд 21 1 ~~ kk k    сходимый. Поэтому можно пренебречь элементами ряда после неко- торого K . Данное расстояние будет интерпретироваться именно как расстояние между моделями, а не как расстояние между данными. 100 ISSN 0572-2691 2.2. Сравнение расстояний. Для сравнения расстояний между временными рядами в настоящей работе используется метод Монте–Карло [23]. В качестве моделей для сравнения рассмотрим 1L -расстояние, DTW- и ERP-методы. Основ- ные характеристики, которые обуславливают смену расстояний и правильность определения моделей временного ряда, — наличие выбросов, структурное изме- нение временного ряда [24] и длина временного ряда. В следующих вычислениях будет исследоваться влияние наличия выбросов и длины временного ряда на по- грешность в вычислении между временными рядами. Рассмотрим влияние наличия аутлайеров на расстояние между временными рядами и расстояниями между их моделями. Для этого рассмотрим генерацию двух временных рядов с 150T исследованиями, первый из которых моделиру- ется ),( qpARMA моделью, второй — это тот же временной ряд, в котором % значений заменены выбросами. В качестве оригинального временного ряда взята )1,2(ARMA модель: .1,04,03,0 121   ttttt xxx Из рис. 1 видно, что при наличии большого количества выбросов, классиче- ские методы линейно увеличивают расстояния между временными рядами, в то же время расстояние по моделям ведет себя как логарифмическая функция. При этом следует заметить, что при моделировании рассмотрены небольшие выбросы, которые незначительно выходят за пределы интервала ).5,1,5,1( 11 IQRQIQRQ  При больших выбросах разница между временными рядами будет расти линейно с коэффициентом, равным средней величине выброса. Рис. 1 Наряду с данной зависимостью рассмотрим также зависимость расстояний от величины временного ряда, т.е. от величины T (рис. 2). Под выбросом будем понимать значение, выходящее за пределы интервала  1,5,11( QIQRQ IQR5,1 , где 1313 ,, QQQQIQR  — 1- и 2-й квартили выборки. 1 2 3 4 Алгоритмы: 1 — по моделям, 2 — DTW, 3 — Евклида, 4 — ERP 0 10 20 30 40 Процент выбросов О тн о си те л ь н ая п о гр еш н о ст ь 0 0,5 1 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 101 Рис. 2 Таким образом, из рисунка следует, что при больших T расстояния меж- ду временными рядами для одинаковых стационарных моделей практически постоянны для всех методов, однако для оценки расстояния по моделям эта константа значительно меньше, чем соответствующая константа для всех дру- гих методов. Заключение В настоящей работе рассмотрено расстояние между временными рядами, основанное не на данных, а на моделях временных рядов. С помощью метода Монте–Карло, показано, что данное расстояние более устойчиво к выбросам и дает более точные результаты для более длинных временных рядов (при больших T ). Кроме того, сложность алгоритма вычисления данного расстоя- ния для N временных рядов составляет )( 2NTO , в то же время аналогичная сложность для алгоритмов DTW, ERP, EDR составляет )( 22 NTO . Несом- ненно, использование моделей — один из наиболее удобных инструментов ис- следования сходства процессов. Кроме того, для анализа удобно использовать усредненные эволюции и предельные эволюции в схеме диффузионной ап- проксимации [25]. Также за счет устойчивости к выбросам данное расстояние можно использовать при каутеризации для построения более устойчивых к шумам кластеров. Т.В. Кнігніцька ОЦІНКА ПОДІБНОСТІ ЧАСОВИХ РЯДІВ НА ОСНОВІ МОДЕЛЕЙ Визначення міри відстані між часовими рядами є відправною точкою для багатьох завдань інтелектуального аналізу даних, таких як кластеризація та класифікація. Кластеризація є основним методом навчання без вчителя, 1 2 3 4 Алгоритмы: 1 — по моделям, 2 — ERP, 3 — Евклида, 4 — DTW 500 1000 1500 2000 Количество исследований О тн о си те л ь н ая п о гр еш н о ст ь 0,6 1 0,8 1,2 1,4 102 ISSN 0572-2691 який використовується для розбиття даних на групи на основі внутрішніх і апріорних невідомих характеристик, властивих даним. При розбитті даних на кластери виникає потреба правильного вибору метрики подібності між об’єктами. Описано основні існуючі алгоритми пошуку відстані між часо- вими рядами, які добре описують дану проблему для малих часових рядів та за відсутності викидів. Викиди, властиві реальним процесам, призводять до неправильної кластеризації, а отже, до прийняття неправильних рішень. Запропоновано розглянути відстань між часовими рядами у вигляді відста- ні між моделями (ARIMA) даних часових рядів. За наявності великої кіль- кості викидів класичні методи лінійно збільшують відстані між часовими рядами, в той же час запропонована у статті відстань за моделями поводить себе як логарифмічна функція. Показано, що при зростанні кількості вимі- рювань відносні похибки для всіх класичних методів залишаються майже незмінними. Відносна похибка для оцінки відстані за моделями значно менша та спадає при зростанні кількості вимірювань. Основним досягненням стат- ті є визначення відстані між часовими рядами, яка ґрунтується на понятті моделі, і порівняння цієї відстані з відповідними класичними найбільш вживаними методами. Використовуючи метод Монте–Карло, показано, що запропонована відстань більш стійка до викидів і дає більш точні результати для часових рядів з великою кількістю спостережень. Крім того, складність алгоритму обчислення відстані на основі моделей менша за аналогічну об- числювальну складність існуючих алгоритмів (DTW, ERP, Евкліда). Немає сумнівів, що використання моделей є одним з найбільш зручних інструмен- тів дослідження подібності процесів. Крім того, для аналізу з врахуванням даного алгоритму зручно використовувати усереднені еволюції і граничні еволюції в схемі дифузійної апроксимації. Також за рахунок стійкості до викидів граничних еволюцій введену відстань можна використовувати при кластеризації для побудови більш стійких до шумів кластерів. Ключові слова: відстань між часовими рядами за моделями, кластеризація, кластер, часовий ряд, модель часового ряду, DTW, ERP. T.V. Knignitskaya ESTIMATE OF TIME SERIES SIMILARITY BASED ON MODELS Determining the measure of the distance between time series is the starting point for many data mining tasks such as clustering and classification. Clustering is the main method of teaching without a teacher, which is used to divide data into groups based on the internal and a priori unknown characteristics inherent in the data. When dividing data into clusters, the need arises to select the similarity metric between objects. The paper describes the main existing algorithms for the “distance” searching between time series, which well describe this problem for small time series and under the absence of outliers. Outliers inherent in real pro- cesses lead to improper clustering, and, consequently, to wrong decisions ma- king. It is proposed to consider the distance between time series in the form of the distance between models (ARIMA) of these time series. In the presence of a large number of outliers, classical methods linearly increase the distances be- tween time series, while the distance proposed in the article according to the models behaves as a logarithmic function. It is shown that with an increase in the number of measurements, the relative errors for all classical methods remain almost unchanged. At the same time, the relative error for estimating the di s- tance by the models is much smaller and decreases with an increase in the num- ber of measurements. The main achievement of the article is the determination of the distance between time series, based on the concept of a model, and the comparison of this distance with the corresponding classical methods most commonly used. Using the Monte Carlo method, it has been shown that the pro- posed distance is more resistant to outliers and gives more accurate results for Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 4 103 time series with a large number of observations. In addition, the complexity of the algorithm for calculating distances based on models is less than the analo- gous computational complexity of existing algorithms (DTW, ERP, Euclidean distance). There is no doubt that the use of models is one of the most convenient tools for studying the similarity of processes. In addition, for analysis taking into account this algorithm, it is convenient to use the averaged evolutions and the limiting evolutions in the diffusion approximation scheme. Also, due to the re- sistance to outliers of limiting evolutions, the entered distance can be used in clustering to build more noise-resistant clusters. Keywords: distance between time series by models, clustering, cluster, time series, time series model, DTW, ERP. 1. Aue A., Horváth L. Structural breaks in time series. Journal of Time Series Analysis. 2013. 34, N 1. P. 1–16. 2. Keogh E., Zhu Q., Hu B., Hao Y., Xi X., Wei L. Ratanamahatana CA: The UCR Time series classification/clustering homepage, 2011. 3. Akaike H. Time series analysis and control through parametric models. Applied Time Series Analysis. New York : Academic Press, 1978. 4. Shapiro S.S., Francia R.S. An approximate analysis of variance test for normality. J. Amer. Stat. Assoc. 1972. 67. P. 215–216. 5. Magidson J., Vermunt J.K. Latent class factor and cluster models, bi-plots and related graphical displays. In Sociological Methodology. Cambridge: Blackwell. 2001. 6. Liao T.W. Clustering of time series data — A survey. Pattern Recognit. 2005. P. 1857–1874. 7. Канторович Г.Г. Анализ времянных рядов (курс лекций). Экономический журнал ВШЭ. 2003. 1(202). P. 85–116. 8. Rodgers J.L., Nicewander W.A. Thirteen ways to look at the correlation coefficient. Am. Stat. 1988. 42. P. 59–66. 9. Maesschalck R.D., Jouan-Rimbaud D., Massart D. The mahalanobis distance. Chemom. Intell. Lab. Syst. 2000. 50. P. 1–18. 10. Félix Iglesias, Wolfgang Kastner. Analysis of similarity measures in times series clustering for the discovery of building energy patterns. Energies.2013. 6(2). P. 579–597. 11. Yam Khoon. L1, L2, Kalman filter and time series analysis in deformation analysis, Singapore. 12. Berndt D.J., Clifford J. Using dynamic time warping to find patterns in time series. In AAAI-94 Workshop on Knowledge Discovery in Databases. 1994. P. 359–370. 13. Vlachos M., Kollios G., Gunopulos D. Discovering similar multidimensional trajectories. ICDE. 2002. P. 673–684. 14. Stramer O., Brockwell P.J., Tweedie R.L. Existence and stability of continuous time threshold ARMA processes. Statistica Sinica. 1995. 15. Lei Chen, Raymond Ng. On the Marriage of Lp-norms and Edit Distance. In VLDB. 2004. P. 792–803. 16. Lei Chen, M. Tamer Özsu, Vincent Oria. Robust and fast similarity search for moving object tra- jectories. In SIGMOD. 2005. P. 491–502. 17. Pole A., West M., Harrison J. Applied Bayesian Forecasting and Time Series Analysis. Chapman and Hall. New York. 1994. 18. Yildirim Ilker. Bayesian inference: Gibbs sampling. Department of Brain and Cognitive Sciences, University of Rochester. August, 2012. P. 1–6. 19. Lipkus A. A proof of the triangle inequality for the Tanimoto distance. J. Math. Chem. 1999. 26. P. 263–265. 20. Usue Mori, Mendiburu A., Lozano J. Distance measures for time series in R: The TSdist Package. The R Journal. 2016. 8(2). P. 451–459. 21. Luis E. Nieto-Barajas, Alberto Contreras-Crist. A Bayesian nonparametric approach for time se- ries clustering. Bayesian Analysis. 2014. 9. P. 147–170. 22. Brockwell P.J., Davis R.A. Introduction to time series and forecasting. NY : Springer, 2012. P. 500. 23. Dick J., Kuo F.Y., Peters G.W., Sloan I. Monte Carlo and quasi-Monte Carlo methods 2012. NY : Springer, 2014. http://www.mdpi.com/search?authors=F%C3%A9lix%20Iglesias&orcid= http://www.mdpi.com/search?authors=Wolfgang%20Kastner&orcid=0000-0001-5420-404X https://www.semanticscholar.org/author/Lei-Chen/37833805 https://www.semanticscholar.org/author/M.-Tamer-%C3%96zsu/1705151 https://www.semanticscholar.org/author/Vincent-Oria/1693176 https://www.researchgate.net/journal/2073-4859_The_R_Journal 104 ISSN 0572-2691 24. Casini A. Structural breaks in time series. Oxford Research Encyclopedia of Economics and Finance. 2017. P. 1–38. 25. Tsarkov Ye.F., Yasinsky V.K., Malyk I.V. Stability in impulsive systems with Markov perturba- tions in averaging scheme. 2. Averaging principle for impulsive Markov systems and stability analysis based on averaged equations. Cybernetics and Systems Analysis. 2011. 47. P. 44–54. 26. Argiento R., Cremaschi A., Guglielmi A. A Bayesian nonparametric mixture model for cluster analysis. Technical report QuadernoImati CNR. Milano: 3-MI, 2012. 27. Berndt D.J., Clifford J. A dynamic programming approach. In Advances in Knowledge Discovery and Data Mining. 1996. P. 229–248. 28. Brockwell P.J. Continuous-time ARMA processes. Handbook of Statistics. Elsevier: Amsterdam. 2001. 19. P. 249–276. 29. Brockwell P.J. On continuous time threshold ARMA processes. Journal of Statistical Planning and Inference. 1994. 39, N 2. P. 291–303. 30. Davis R.A., Dunsmuir W.T. Maximum likelihood estimation for MA(1) processes with a root on or near the unit circle. Econometric Theory. 1996. 12. P. 1–29. 31. Fox E., Sudderth E.B., Jordan M.I. & Willsky A.S. bayesian nonparametric inference of switching dynamic linear models. IEEE Transactions on Signal Processing. 2011. 59. P. 1569-1585. 32. Ghosh A., Mukhopadhyay S., Roy S., Bhattacharya S. Bayesian inference in nonparametric dy- namic state-space models, 2012. 33. Gray H.L., Kelley G.D. & McIntire D.D. A new approach to ARMA modeling. Comm. Stat. 1978. B7. P. 1–77. 34. Grunwald G.K., Hyndman R.J., Hamza K. Some properties and generalizations of nonnegative Bayesian time series models. Technical Report, Statistics Dept., 1994. 35. Huang A. Similarity measures for text document clustering. In Proceedings of the 6th New Zea- land Computer Science Research. Student Conference, Christchurch, New Zealand, 14–18 April, 2008. P. 49–56. 36. Keogh E. Exact indexing of dynamic time warping. In Proceedings of the 28th International Con- ference on Very Large Data Bases, Hong Kong, China, 20–23 August 2002. P. 406–417. 37. Lijoi A., Mena,R.H. Controlling the reinforcement in Bayesian nonparametric mixture models. Journal of the Royal Statistical Society. 2007, Series B 69. P. 715–740. 38. Navarro D., Perfors A. The Metropolis-Hastings algorithm. COMPSCI 3016: Computational Cognitive Science, 2012. 39. Pitman J., Yor M. The two-parameter Poisson-Dirichlet distribution derived from a stable subor- dinator. The Annals of Probability. 1997. 25. P. 855–900. 40. Zhou C., Wakefield J. A Bayesian mixture model for partitioning gene expression data. Biomet- rics. 2006. 62. P. 515–525. Получено 10.04.2018 После доработки 10.04.2018 https://link.springer.com/journal/10559 https://www.sciencedirect.com/science/journal/03783758 https://www.sciencedirect.com/science/journal/03783758 https://www.sciencedirect.com/science/journal/03783758/39/2

Оценка сходства временных рядов на основе моделей

Репозитарії

Схожі ресурси