Dynamic Time Warping (DTW) — это популярный метод анализа временных рядов, используемый для измерения сходства между двумя временными рядами, которые могут иметь разную длину, нелинейные искажения и разные скорости. Он был введен в 1978 году Сакоэ и Чиба для согласования речевых моделей. DTW широко используется в различных областях, включая распознавание речи, распознавание изображений, финансы и здравоохранение.
Временные ряды — это просто последовательность значений, которые записываются с течением времени, например дневные температуры или курсы акций. DTW — это метод, который позволяет нам сравнивать временные ряды, которые могут иметь разную длину, форму или скорость.
Допустим, у нас есть два временных ряда, A и B. A может быть последовательностью чисел, отражающей дневную температуру в городе, а B может быть последовательностью чисел, отражающей изменение курса акций во времени. Мы можем захотеть сравнить эти два временных ряда, чтобы увидеть, есть ли какая-либо связь между ними, или увидеть, есть ли какие-либо закономерности, которые мы можем использовать для прогнозирования.
Традиционные методы сравнения временных рядов, такие как евклидово расстояние или корреляция, предполагают, что сравниваемые временные ряды имеют одинаковую длину, форму и скорость. Однако в реальных приложениях временные ряды могут иметь разную длину, форму и скорость. DTW был разработан для решения этих проблем и предоставления надежного метода сравнения временных рядов.
DTW работает, находя оптимальное выравнивание (путь деформации) между двумя временными рядами, допуская различные скорости масштабирования времени и амплитуды. Он рассматривает все возможные пути деформации и вычисляет оптимальный путь на основе метрики расстояния, учитывающей различия между двумя временными рядами. Путь деформации находится с помощью динамического программирования, который представляет собой метод, который разбивает проблему на более мелкие подзадачи и решает их рекурсивно. Алгоритм DTW начинается с создания матрицы, в которой хранятся расстояния между каждой парой соответствующих точек в двух временных рядах. Затем алгоритм находит оптимальный путь деформации, находя путь с наименьшей стоимостью через матрицу.
Чтобы понять, как работает DTW, давайте рассмотрим пример. Предположим, у нас есть два временных ряда ежедневных цен закрытия акций за 7 дней, назовем их A и B. Цены представляют собой массив numpy, как показано ниже:
A = np.array([100, 120, 130, 135, 120, 110, 100]) B = np.array([110, 130, 140, 130, 115, 120, 110])
Мы можем визуализировать два временных ряда, используя линейный график:
На первый взгляд мы видим, что два временных ряда или цены акций имеют схожие формы и тенденции, но они не совпадают идеально. DTW может помочь нам более точно измерить сходство между этими двумя временными рядами.
Чтобы вычислить расстояние DTW между двумя временными рядами, нам сначала нужно создать матрицу расстояний, в которой хранятся расстояния между каждой парой соответствующих точек в двух временных рядах. Мы можем использовать евклидово расстояние в качестве нашей метрики расстояния, которая просто вычисляет расстояние между двумя точками в евклидовом пространстве.
Используя евклидово расстояние, матрица расстояний для нашего примера будет выглядеть так:
A = [100, 120, 130, 135, 120, 110, 100] B = [110, 130, 140, 130, 115, 120, 110] Distance matrix using Euclidean distance: |---------|------|------|------|------|------|------|------| | | 110 | 130 | 140 | 130 | 115 | 120 | 110 | |---------|------|------|------|------|------|------|------| | 100 | 10.0 | 10.0 | 40.0 | 35.0 | 20.0 | 30.0 | 10.0 | | 120 | 10.0 | 0.0 | 20.0 | 5.0 | 10.0 | 10.0 | 20.0 | | 130 | 20.0 | 0.0 | 10.0 | 5.0 | 15.0 | 10.0 | 30.0 | | 135 | 25.0 | 5.0 | 5.0 | 0.0 | 20.0 | 15.0 | 35.0 | | 120 | 20.0 | 10.0 | 20.0 | 5.0 | 5.0 | 10.0 | 20.0 | | 110 | 10.0 | 0.0 | 10.0 | 5.0 | 5.0 | 0.0 | 10.0 | | 100 | 10.0 | 10.0 | 40.0 | 35.0 | 20.0 | 30.0 | 10.0 | |---------|------|------|------|------|------|------|------| +---------------------------------------+
Чтобы вычислить расстояние между двумя значениями A[i] и B[j], мы используем формулу евклидова расстояния:
dist(A[i], B[j]) = sqrt((A[i] - B[j]) ** 2)
Затем мы заполняем матрицу расстояний, перебирая все возможные пары i и j и вычисляя расстояние между A[i] и B[j]. Например, чтобы вычислить расстояние между A[0] и B[0], мы используем формулу:
dist(A[0], B[0]) = sqrt((100 - 110) ** 2) = 10.0
Точно так же, чтобы вычислить расстояние между A[0] и B[1], мы используем формулу:
dist(A[0], B[1]) = sqrt((100 - 130) ** 2) = 30.0
Мы повторяем этот процесс для всех пар i и j, чтобы получить полную матрицу расстояний.
Вот реализация с использованием python:
import numpy as np
A = np.array([100, 120, 130, 135, 120, 110, 100])
B = np.array([110, 130, 140, 130, 115, 120, 110])
dist_matrix = np.zeros((len(A), len(B)))
for i in range(len(A)):
for j in range(len(B)):
dist_matrix[i, j] = np.sqrt((A[i] - B[j]) ** 2)
print(dist_matrix)
Выход:
[[10. 30. 40. 30. 15. 20. 10.] [10. 10. 20. 10. 5. 0. 10.] [20. 0. 10. 0. 15. 10. 20.] [25. 5. 5. 5. 20. 15. 25.] [10. 10. 20. 10. 5. 0. 10.] [ 0. 20. 30. 20. 5. 10. 0.] [10. 30. 40. 30. 15. 20. 10.]]
Следующим шагом является поиск оптимального пути деформации через эту матрицу. Путь деформации представляет собой последовательность точек, соединяющих верхний левый угол с нижним правым углом матрицы. Путь должен соответствовать трем правилам:
- Путь может двигаться только вниз, вправо или по диагонали вниз-вправо.
- Путь не может пересечь сам себя.
- Путь должен начинаться в верхнем левом углу и заканчиваться в нижнем правом углу.
Оптимальный путь деформации для нашего примера будет выглядеть так:
(1, 1) -> (2, 2) -> (3, 3) -> (4, 4) -> (5, 5) -> (6, 6) -> (7, 7)
Использование питона:
import numpy as np
# Define the two time series
A = np.array([100, 120, 130, 135, 120, 110, 100])
B = np.array([110, 130, 140, 130, 115, 120, 110])
# Calculate the distance matrix using Euclidean distance
dist_matrix = np.zeros((len(A), len(B)))
for i in range(len(A)):
for j in range(len(B)):
dist_matrix[i, j] = np.sqrt((A[i] - B[j])**2)
# Initialize the cost matrix and path matrix
cost_matrix = np.zeros((len(A), len(B)))
path_matrix = np.zeros((len(A), len(B)), dtype=int)
# Fill in the first row and first column of the cost matrix
cost_matrix[0, 0] = dist_matrix[0, 0]
for i in range(1, len(A)):
cost_matrix[i, 0] = cost_matrix[i-1, 0] + dist_matrix[i, 0]
for j in range(1, len(B)):
cost_matrix[0, j] = cost_matrix[0, j-1] + dist_matrix[0, j]
# Fill in the rest of the cost matrix and path matrix
for i in range(1, len(A)):
for j in range(1, len(B)):
min_cost = min(cost_matrix[i-1, j], cost_matrix[i, j-1], cost_matrix[i-1, j-1])
cost_matrix[i, j] = dist_matrix[i, j] + min_cost
if min_cost == cost_matrix[i-1, j]:
path_matrix[i, j] = 1
elif min_cost == cost_matrix[i, j-1]:
path_matrix[i, j] = 2
else:
path_matrix[i, j] = 3
# Follow the optimal path to get the indices of the aligned points
path = []
i = len(A)-1
j = len(B)-1
while i > 0 or j > 0:
path.append((i, j))
if path_matrix[i, j] == 1:
i -= 1
elif path_matrix[i, j] == 2:
j -= 1
else:
i -= 1
j -= 1
path.append((0, 0))
path.reverse()
# Print the aligned points
print("Optimal warping path:")
for i, j in path:
print("A[{}] = {}, B[{}] = {}".format(i, A[i], j, B[j]))
Выход:
Optimal warping path: A[0] = 100, B[0] = 110 A[1] = 120, B[1] = 130 A[2] = 130, B[2] = 140 A[3] = 135, B[3] = 130 A[4] = 120, B[4] = 115 A[5] = 110, B[5] = 120 A[6] = 100, B[6] = 110
Мы можем визуализировать оптимальный путь на матрице расстояний:
import matplotlib.pyplot as plt
# define the two time series
A = [100, 120, 130, 135, 120, 110, 100]
B = [110, 130, 140, 130, 115, 120, 110]
# define the optimal path
path = [(0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6)]
# plot the two time series and the optimal path
plt.figure(figsize=(10,5))
plt.plot(A, label='A')
plt.plot(B, label='B')
for i, j in path:
plt.plot([i,j], [A[i],B[j]], color='red')
plt.legend()
plt.show()
Это создаст график с двумя временными рядами и красной линией, соединяющей соответствующие точки в двух рядах. Результирующий график должен выглядеть следующим образом:
Как видите, путь соединяет соответствующие точки в двух сериях, принимая во внимание тот факт, что две серии имеют разную длину и форму. Это главное преимущество метода DTW перед другими мерами расстояния, которые не допускают такой гибкости.
Кластеризация временных рядов с использованием DTW и кластеризации K-средних
Одним из приложений DTW является кластеризация данных временных рядов. Кластеризация — это процесс группировки похожих точек данных вместе на основе некоторой метрики сходства. Кластеризация KMeans — один из таких популярных алгоритмов, используемых для кластеризации точек данных.
Теперь мы рассмотрим, как мы можем использовать DTW для кластеризации данных временных рядов с помощью кластеризации KMeans. Прежде чем мы углубимся в код, давайте разберемся с основными шагами, связанными с кластеризацией временных рядов с использованием кластеризации DTW и KMeans:
- Предварительно обработать данные: нам необходимо предварительно обработать данные временных рядов, преобразовав их в подходящий формат для анализа. Мы можем использовать фрейм данных Pandas для хранения данных временных рядов, где каждая строка представляет разные временные ряды.
- Вычислите матрицу расстояний DTW: нам нужно вычислить матрицу расстояний DTW между каждой парой временных рядов в наборе данных. Эта матрица даст нам расстояние между каждой парой временных рядов, которые мы можем использовать в качестве входных данных для алгоритма кластеризации KMeans.
- Кластеризация временных рядов: мы можем использовать алгоритм кластеризации KMeans для кластеризации временных рядов на основе их матрицы расстояний. Мы можем выбрать количество кластеров, которые мы хотим создать, исходя из наших требований к анализу.
- Визуализируйте кластеры: мы можем визуализировать кластеры, используя различные методы визуализации, такие как диаграммы рассеяния или линейные графики, чтобы понять закономерности в данных.
Теперь, когда мы понимаем основные шаги, связанные с кластеризацией данных временных рядов с использованием кластеризации DTW и KMeans, давайте посмотрим на код Python для реализации этого подхода:
#pip install pyts
#pip install yfinance
import pandas as pd
import numpy as np
import pyts
from pyts.metrics import dtw
from sklearn.cluster import KMeans
import yfinance as yf
import matplotlib.pyplot as plt
# Download the closing prices of the 10 stocks
tickers = ['AAPL', 'DD', 'KO', 'GOOG', 'AMD', 'NVDA', 'MMM', 'AMX', 'AMZN', 'BA', 'BP']
start_date = '2022-03-01'
end_date = '2023-03-01'
data = pd.DataFrame()
for ticker in tickers:
stock = yf.download(ticker, start=start_date, end=end_date)
data[ticker] = stock['Close']
# Compute the DTW distance matrix
distance_matrix = np.zeros((len(data), len(data)))
for i in range(len(data)):
for j in range(i+1, len(data)):
distance_matrix[i][j] = dtw(data.iloc[i], data.iloc[j])
distance_matrix[j][i] = distance_matrix[i][j]
# Perform KMeans clustering
kmeans = KMeans(n_clusters=4, random_state=0).fit(distance_matrix)
# Visualize the clusters
colors = ['red', 'green', 'blue', 'k']
fig, ax = plt.subplots(figsize=(15, 10))
for i in range(len(data)):
ax.plot(data.iloc[i], color=colors[kmeans.labels_[i]], label=f'Cluster {kmeans.labels_[i]}')
plt.show()
В этом коде мы используем библиотеку yfinance для загрузки цен закрытия 11 акций за последний год. Затем мы вычисляем матрицу расстояний DTW, используя библиотеку Pyts. Затем мы используем библиотеку Scikit-learn для кластеризации KMeans с тремя кластерами. Наконец, мы визуализируем кластеры, используя разные цвета для представления каждого кластера.
Следующий код поможет нам узнать, какая цена акций относится к какому кластеру:
#Create new Cluster column
data['cluster'] = kmeans.labels_
# Stocks in cluster 0
data[data['cluster'] == 0]
# Stocks in cluster 1
data[data['cluster'] == 1]
# Stocks in cluster 2
data[data['cluster'] == 2]
# Stocks in cluster 3
data[data['cluster'] == 3]
# Group the DataFrame by cluster and compute mean and standard deviation of closing prices
data.groupby('cluster')['AAPL', 'DD', 'KO', 'GOOG', 'AMD', 'NVDA', 'MMM', 'AMX', 'AMZN', 'BA', 'BP'].agg([np.mean])
Выход:
Выходные данные отображают средние цены закрытия каждой акции для каждого из четырех кластеров. Строки представляют разные кластеры, а столбцы — разные акции. Цифры в таблице представляют собой среднюю цену закрытия для каждой акции в каждом кластере. Эту информацию можно использовать для анализа того, какие акции имеют тенденцию двигаться вместе, а какие имеют разные модели ценовых движений. Например, мы можем видеть, что акции в кластере 2, как правило, имеют более высокие средние цены закрытия по сравнению с акциями в других кластерах. Мы также можем видеть, что акции в кластере 1, как правило, имеют более высокие средние цены для Amazon (AMZN) и Boeing (BA), в то время как акции в кластере 0, как правило, имеют более высокие средние цены для Apple (AAPL) и NVIDIA (NVDA). В целом, этот анализ может быть полезен для понимания корреляций и закономерностей в движении цен на акции и для принятия обоснованных инвестиционных решений.
Мы также можем использовать информацию из кластеризации для создания портфеля акций с похожими ценовыми движениями. Например, если бы мы хотели создать диверсифицированный портфель акций из разных отраслей, но с одинаковыми ценовыми движениями, мы могли бы выбрать акции из разных кластеров. В качестве альтернативы мы могли бы выбрать акции из одного кластера, чтобы создать портфель, более ориентированный на конкретную отрасль или рыночную тенденцию. Использование расстояния DTW в качестве метрики сходства позволяет алгоритму кластеризации фиксировать закономерности и форму ценовых движений, а не только общий тренд. Это может быть особенно полезно для акций, которые имеют схожие общие тенденции, но разные модели ценовых движений.
Результаты кластеризации также можно использовать для выявления выбросов или акций, которые не вписываются ни в один из кластеров. Эти акции могут иметь уникальные движения цен, которые не очень хорошо представлены другими акциями в наборе данных. В целом, комбинация расстояния DTW и кластеризации KMeans предоставляет полезный инструмент для анализа сходств и различий в движении цен на акции и может помочь в принятии обоснованных инвестиционных решений. Однако при интерпретации результатов важно учитывать ограничения и потенциальные смещения алгоритма кластеризации.
Использованная литература:
Сако, Х. и Чиба, С. (1978) Оптимизация алгоритма динамического программирования для распознавания произнесенных слов.
«Динамическое искажение времени: алгоритм и приложения» Имонна Кио и Чотирата Энн Ратанамахатана.
