Мера близости для временных рядов на основе вейвлет коэффициентов

Е.В. Бурнаев, Н.Н. Оленев

Московский физико-технический институт (государственный университет)

Введение. Мера близости между данными является центральным понятием большинства data mining алгоритмов. Для ⌠сложных■ данных, таких как финансовые временные ряды, обычная мера близости типа евклидова расстояния, зачастую не применима. На рис.1. изображены обменные курсы South Africa rand и Switzerland franc по отношению к US dollar с 01.01.90 по 29.10.93, 1000 отсч╦тов. Очевидно, что подсчитанное для этих рядов евклидово расстояние значительно, хотя, если удалить тренд и провести подходящее масштабирование по оси ординат, окажется, что эти временные ряды близки.

Рис.1. Слева: обменные курсы South Africa rand и Switzerland franc vs US dollar с 01.01.90 по 29.10.93, 1000 отсч╦тов. Справа: те же обменные курсы, но с вычетом тренда и подходящим масштабированием по оси ординат.

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

Дискретное вейвлет преобразование. Пусть ═- временной ряд, ═для некоторого целого ═и . Пусть ═- матрица дискретного вейвлет преобразования размера , определенная на основе вейвлет и масштабного фильтров длины ═[1]. Вектор вейвлет и масштабных коэффициентов равен , где ═и ═- вектора длины ═и ═соответственно. Пусть , тогда ═- пропорционально среднему ряда, причем если в векторе ═обнулить , а потом сделать обратное вейвлет преобразование, то это равносильно вычитанию среднего из ряда . Коэффициент ═пропорционален разности смежных взвешенных средних длины , то есть указывает на изменение значений ряда на масштабе . Модуль ═показывает, сколько энергии ряда ═содержится в отрезке частот ═в момент времени . Для широкого класса стохастических процессов ═независимы, и распределены как , где ═- некоторая константа [1]. Коэффициент ═пропорционален взвешенному среднему длины , а его модуль показывает, сколько энергии ряда ═содержится в отрезке частот ═в момент времени . В работе будут использоваться вейвлет и масштабные фильтры Добеши 4 (). В этом случае ═не чувствительны к линейному тренду, то есть если ряд ═суть значения некоторой линейной функции, то . При подсчете вектора коэффициентов ═неявно делается предположение о возможности циклического продолжения ряда :. Если это не так, то значения ⌠граничных■ вейвлет коэффициентов будут подсчитаны неверно. Для фильтров Добеши 4 это коэффициенты , ═и .

Алгоритм подсчета мер близости между временными рядами.

• Пусть ряды ═и ═имеют одинаковую длину. Подсчитываем вейвлет коэффициенты ═и ═для ═и обнуляем ⌠граничные■ коэффициенты.
• Положим , где ═обозначает либо , либо . Вектора коэффициентов ═представляют характеристики ряда, которые, как следует из вышеприведенных свойств вейвлет коэффициентов, 1) робастны по отношению к изменению среднего ряда, тренду, масштабированию 2) независимы и нормально распределены. Длина такого вектора характеристик равна .
• Пусть ═- косинус угла между векторами характеристик. Положим ═и . Поскольку коэффициент ═характеризует изменение в значениях ряда ═на определенном масштабе в определенный момент времени, то для фильтра Добеши 4 имеет смысл определить меры близости на основе значения . Положим (добавка ═нужна на тот случай, если первое слагаемое в аргументе логарифма равно нулю) и . Преимущество ═и ═в том, что эти меры близости ограничены. Качественной разницы между , ═и , ═нет.

Тестирование мер близости. Для тестирования введенных мер близости использовались ряды обменных курсов 30 валют по отношению к US dollar, взятые с сайта Federal Reserve Statistical Release, USA c 26.02.91 по 31.12.98, 2048 отсчетов (www.federalreserve.gov/releases/h10/hist/default1999.htm). В табл.1. приведены значения мер близости ═и ═между курсом Switzerland franc и остальными обменными курсами. Также в таблице приведены результаты разбиения рядов на 10 кластеров с помощью алгоритма k-Means [2] (в столбцах указаны номера кластеров, к которым принадлежат ряды). При разбиении на кластеры использовались два типа расстояния между рядами: cs √ на основе косинуса угла и cr √ на основе коэффициента корреляции между рядами. Из табл.1 видно, что между введенными мерами близости и разбиением на кластеры, по крайней мере для первых 10 валют, существует разумное соответствие. На рис.2. изображена зависимость мер близости ═и ═между Switzerland franc и Australia dollar, Austria schilling, China yuan, Finland markka, France franc, Hong-Kong dollar от времени. Значения ═и ═оценивались в скользящем окне длиной 256 отсчетов, для подсчета использовались 401 отсчет с 01.01.90 по 15.07.91. Из рис.2. видно, что курсы валют образуют кластеры, которые зависят от времени. По всей видимости, это основная причина, из-за которой в табл.1. для последних 15-20 валют соответствие между значениями мер близости , ═и номерами кластеров, полученных с помощью алгоритма K-means, не очень хорошее.

Работа поддержана грантом РФФИ ╧ 04-07-90346, программой НШ-1843.2003.01, целевой программой Президиума РАН ╚Информатизация╩.

Табл.1. Значения мер близости ═и ═и результаты кластерного анализа.

Рис.2. Зависимость мер близости ═и ═от времени.

Литература.

1.      Vidakovic B. Statistical modeling by wavelets, Wiley, 1999.

2.      Kaufman L., Rousseeuw P.J., Finding Groups in Data: An Introduction to Cluster Analysis, Wiley, 1990.