针对时间序列数据，本节将对第二类思路具体展开。一个最常用的算法叫做动态时间规整dynamic time warping (DTW) ，非常适合用于形状特征很重要的时间序列数据。DTW解决的是一对多的问题，欧氏距离的计算要求两个向量是等长的，也就是要求两组时间序列的长度是一模一样才能计算，而很多情况我们得到的时间序列都不是等长的，此时DTW就能发挥作用了。
from math import sqrt
import numpy as np
ts1 = [1, 2, 3]
ts2 = [2, 2, 2, 3, 4]
def distDTW(ts1,ts2)
DTW = {}
for i in range(len(ts1)):
DTW[(i, -1)] = np.inf
for i in range(len(ts2)):
DTW[(-1, i)] = np.inf
DTW[(-1, -1)] = 0
for i in range(len(ts1)):
for j in range(len(ts2)):
dist = (ts1[i] - ts2[j]) ** 2
DTW[(i, j)] = dist + min(DTW[(i - 1, j)], DTW[(i, j - 1)], DTW[(i - 1, j - 1)])
return sqrt(DTW[len(ts1) - 1, len(ts2) - 1])
除了DTW距离，还有几种其他的应用于时间序列的距离算法：
弗雷歇距离（Fréchet distance ）
弗雷歇距离可以理解为狗绳距离，也就是人和狗各自走过一段路所需要的最短的狗绳距离
最长公共子序列（Longest common subsequence ）
最长公共子序列主要用于非数值的时间序列，比如两个英文单词，最长的公共序列的长度也可以用于判断距离
python实战演练
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
from sklearn import preprocessing
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics.cluster import homogeneity_score
from scipy.spatial.distance import euclidean
from fastdtw import fastdtw
from tqdm import tqdm
rowlist= np.array(range(0,50))
for a in [np.array(range(100,150)),np.array(range(200,250)),np.array(range(300,350)),np.array(range(400,450))]:
rowlist=np.append(rowlist,a)
# 使用第二类聚类思路首先计算DTW距离，这一步计算量比较大，先把结果存下来，并且作为简化，只选择了部分数据送入模型
pairwise_dis = pd.DataFrame(np.zeros((250, 250)))
for index_r, r in tqdm(enumerate(rowlist)):
for index_c, c in enumerate(rowlist):
arr1 = eeg[eeg.id==r]['measurements'].values[:500]
arr2 = eeg[eeg.id==c]['measurements'].values[:500]
distance, _ = fastdtw(arr1, arr2, dist=euclidean)
pairwise_dis.iloc[index_r,index_c]=distance
