第三章时间序列挖掘相似性

1、时间序列挖掘相似性山西财经大学信息管理学院常新功山西财经大学信息管理学院常新功第三章目 录 时间序列相似性定义 时间序列相似性应用场景 时间序列常见距离定义 时间序列相似性分类时间序列相似性定义 反映两条时间序列相似程度的值刻划了这两条时间序反映两条时间序列相似程度的值刻划了这两条时间序列的相似性，其概念和方法是时间序列挖掘的基础。列的相似性，其概念和方法是时间序列挖掘的基础。 给定某个时间序列，要求从大型时间序列数据集合中给定某个时间序列，要求从大型时间序列数据集合中找出与之相似的序列找出与之相似的序列-静态时间序列的相似性。静态时间序列的相似性。 实际生活中有大量以动态序列形式存在的时间序

2、列实际生活中有大量以动态序列形式存在的时间序列(时间序列流时间序列流)。 随着研究的深入，动态时间序列的相似性问题也日益随着研究的深入，动态时间序列的相似性问题也日益成为新时期时间序列相似性问题研究的重要组成部分。成为新时期时间序列相似性问题研究的重要组成部分。 与传统静态数据的精确相似不同，时间序列的相似性与传统静态数据的精确相似不同，时间序列的相似性会呈现多种变形，如振幅平移和伸缩、线性漂移、不会呈现多种变形，如振幅平移和伸缩、线性漂移、不连续、噪声、时间轴伸縮等等。针对这些相似性变形，连续、噪声、时间轴伸縮等等。针对这些相似性变形，研究者们提出了很多种相似性度量方法。研究者们提出了很多种

3、相似性度量方法。时间序列相似性应用场景 1区别多个公司发展的相似性模型；区别多个公司发展的相似性模型； 2在股票价格上寻找价格波动的相似运动；在股票价格上寻找价格波动的相似运动； 3在乐谱版权问题上确认两份乐谱是否存在相似在乐谱版权问题上确认两份乐谱是否存在相似性；性； 4对具有相似销售模式的商品进行聚类；对具有相似销售模式的商品进行聚类； 5查找具有相似病情的心电图；查找具有相似病情的心电图； 6对网络的异常流量预警；对网络的异常流量预警； 7对天气预报中灾害天气的模式提取等。对天气预报中灾害天气的模式提取等。时间序列常见距离定义 距离函数一般要满足如下几个条件：距离函数一般要满足如下几个条

4、件： 非负性，即非负性，即d(A,B)d(A,B) 0 0 同一性：即同一性：即 d(A,A)=d(A,A)= 0 0 对称性：对称性： d(A,B)= d(B,A)d(A,B)= d(B,A) 满足三角不等式：满足三角不等式：d(A, B)d(A, B) d(A,C)+d(C,B) d(A,C)+d(C,B)，即两点，即两点间直线最短。这是一个高要求。间直线最短。这是一个高要求。 实际应用中，距离函数很难满足以上所有条件，实际应用中，距离函数很难满足以上所有条件，这取决于数据的表示和距离的计算方法。但是，这取决于数据的表示和距离的计算方法。但是，当一些约束适当放松的时候，相似性度量仍然可当一

5、些约束适当放松的时候，相似性度量仍然可以有效地进行。以有效地进行。 时间序列间的距离可用来衡量时间序列之间的差时间序列间的距离可用来衡量时间序列之间的差异性，以确定序列是否相似。异性，以确定序列是否相似。时间序列常见距离定义 时间序列间的距离可用来衡量时间序列之间的差时间序列间的距离可用来衡量时间序列之间的差异性，以确定序列是否相似。异性，以确定序列是否相似。(1)Minkowski 距离距离(Minkowski Distance) Minkowski 距离实际是一系列距离的集合，对于距离实际是一系列距离的集合，对于两时间序列两时间序列 和和 其计算方法其计算方法为为其中其中p=1时为曼哈顿距

6、离；时为曼哈顿距离；p=2时为欧氏距离；时为欧氏距离；时间序列常见距离定义(2)欧氏距离欧氏距离(Euclidean Distance) Euclidean 距离是被广泛采用的时间序列相似度量，距离是被广泛采用的时间序列相似度量，在时间序列相似性问题研究初期大量采用，它的在时间序列相似性问题研究初期大量采用，它的计算方法是计算方法是在实际使用中，为了防止对各段采用相同的系数，在实际使用中，为了防止对各段采用相同的系数，有时采用加权的欧氏距离：有时采用加权的欧氏距离：QCD(Q,C)niiicqCQD12,Given two time series Q = q1qn and C = c1cn t

7、heir Euclidean distance is defined as:欧氏距离的优缺点 Euclidean 距离的优点在于：直观距离的优点在于：直观而计算简便，而计算简便，有良好的数学背景和意义；由于序列的一些常有良好的数学背景和意义；由于序列的一些常用变换用变换(如傅立叶变换等如傅立叶变换等)的系数有欧的系数有欧氏距离保持氏距离保持不变的性质，所以经常用于数据库的高效索引；不变的性质，所以经常用于数据库的高效索引；无参。无参。 缺点在于：需要计算的两序列具有相同的长度；缺点在于：需要计算的两序列具有相同的长度；对于时间序列点的突变对于时间序列点的突变(e.g. noise)比较敏感；比

8、较敏感；Euclidean 距离对序列按照时间轴进行点对点依距离对序列按照时间轴进行点对点依次计算，对时间序列的错位、移位次计算，对时间序列的错位、移位(out of phase)等比较敏感。等比较敏感。斜率距离-欧氏距离的一个变形 设设 其中其中 X 和和Y 分别分别是原始时间序列数据转换而成的斜率组成的时间是原始时间序列数据转换而成的斜率组成的时间序列，即：序列，即：时间序列常见距离定义(3)编辑距离编辑距离(Edit Distance) Edit 距离是计算两字符串序列的距离一种度量，它距离是计算两字符串序列的距离一种度量，它的定义是将一字符串转换为另一字符串所需的最的定义是将一字符串转

9、换为另一字符串所需的最小编辑小编辑(插入、删除、改变插入、删除、改变)步数。步数。 将时间序列进行不同的量化和编码后形成字符串，将时间序列进行不同的量化和编码后形成字符串，采用编辑距离计算两字符串的距离。采用编辑距离计算两字符串的距离。 Edit 距离的优点是：充分利用了字符串匹配等成距离的优点是：充分利用了字符串匹配等成熟计算方法；容易为人所理解；熟计算方法；容易为人所理解； 允许多对无。允许多对无。 缺点是：需要将时间序列转化为相应的字符串，缺点是：需要将时间序列转化为相应的字符串，精度不高；对于不同步的时间序列效果较差。精度不高；对于不同步的时间序列效果较差。时间序列常见距离定义(4)最

10、大公共子串最大公共子串 LCS(Longest Common Subseries)方法方法 LCS是计算两时间序列间具有的公共长度子串，并是计算两时间序列间具有的公共长度子串，并以该子串的长度与这两个时间序列中较长序列的以该子串的长度与这两个时间序列中较长序列的长度比值作为序列间的相似性度量。长度比值作为序列间的相似性度量。 LCS 方法借用字符串匹配中的相似性度量，有其一方法借用字符串匹配中的相似性度量，有其一定的可取之处。其不足是：公共长度子串的长定的可取之处。其不足是：公共长度子串的长度可能偏小，两时间序列间可能非常相似，但是度可能偏小，两时间序列间可能非常相似，但是由于数值并不能完全一

11、致，细小的偏差都会导致由于数值并不能完全一致，细小的偏差都会导致公共子串的长度偏小，从而影响到度量效果；公共子串的长度偏小，从而影响到度量效果；公共长度子串的获取是一个问题，虽然可以采用公共长度子串的获取是一个问题，虽然可以采用较为常见的动态规划的方法解决，但是由于时间较为常见的动态规划的方法解决，但是由于时间序列很可能是长度很长的序列，空间开销较大。序列很可能是长度很长的序列，空间开销较大。时间序列常见距离定义(5)DTW (5)DTW 距离距离(Dynamic Time Warping Distance)(Dynamic Time Warping Distance) DTW DTW 距离最

12、先在语音数字处理领域得到诸多成功距离最先在语音数字处理领域得到诸多成功的应用，由的应用，由 Berndt Berndt 和和 CliffordClifford于于 90 90 年代中旬年代中旬引入到时间序列挖掘中，并取得了巨大的成功。引入到时间序列挖掘中，并取得了巨大的成功。 在时间序列中，需要比较两段长度可能并不相等在时间序列中，需要比较两段长度可能并不相等的时间序列的相似性，在语音识别领域表现为不的时间序列的相似性，在语音识别领域表现为不同人的语速不同。而且同一个单词内的不同音素同人的语速不同。而且同一个单词内的不同音素的发音速度也不同，比如有的人会把的发音速度也不同，比如有的人会把AA这

13、个音这个音拖得很长，或者把拖得很长，或者把ii发的很短。另外，不同时发的很短。另外，不同时间序列可能仅仅存在时间轴上的位移，亦即在还间序列可能仅仅存在时间轴上的位移，亦即在还原位移的情况下，两个时间序列是一致的。在这原位移的情况下，两个时间序列是一致的。在这些复杂情况下，使用传统的欧几里得距离无法有些复杂情况下，使用传统的欧几里得距离无法有效地求得两个时间序列之间的距离效地求得两个时间序列之间的距离( (或者相似性或者相似性) )。 对于时间序列对于时间序列 和和 ，定，定义距离矩阵：义距离矩阵：DM=(aij) mn ，其中，其中aij=(xi-yj)2, 或其它或其它度量。度量。在在DM中

14、寻找一条弯中寻找一条弯曲路径曲路径Ww1,w2, wK, 其中其中wi=某个某个aij ，满足以下性质：满足以下性质：1、有界性：、有界性： maxm , n Km+n-1；2、边界性：、边界性：w1=a11,wk=amn ；3、单调性和连续性：、单调性和连续性：在弯曲路径中，相邻在弯曲路径中，相邻两个元素两个元素wk=aij,wk+1=ast ，则，则0 s-i 1, 0 t-j 1。单调性保证了在时间序列的每个时刻不会出现时间单调性保证了在时间序列的每个时刻不会出现时间交叉现象：交叉现象：同时使同时使 达到最小的弯曲路径达到最小的弯曲路径Ww1,w2, wK, 称为最佳弯曲路径。这个最小值

15、称为时间序列称为最佳弯曲路径。这个最小值称为时间序列 X 和和Y 动态时间弯曲距离，简记为动态时间弯曲距离，简记为 Ddtw(X,Y)，即有：，即有：DTW伪代码实现int DTWDistance(s: array 1.n, t: array 1.m) DTW := array 0.n, 0.m for i := 1 to n DTWi, 0 := infinity for i := 1 to m DTW0, i := infinity DTW0, 0 := 0 for i := 1 to n for j := 1 to m cost:= d(si, tj) DTWi, j := cost +

16、 minimum(DTWi-1, j , DTWi , j-1, DTWi-1, j-1) return DTWn, mDTW的优缺点 DTW 的优点在于：克服了的优点在于：克服了 Euclidean 距离距离点对必须对应的问题，允许不同步的点对点对必须对应的问题，允许不同步的点对应计算；允许两时间序列具有不同长度；应计算；允许两时间序列具有不同长度；对时间序列的同步问题不敏感。对时间序列的同步问题不敏感。DTW的优缺点 缺点在于：缺点在于：DTW 的计算复杂度较高，对于长度分别为的计算复杂度较高，对于长度分别为n和和m 的时间序列，准确计算的时间序列，准确计算DTW 距离需要距离需要 O (

17、 nm )的的时间复杂度；时间复杂度；DTW 并不满足距离的三角不等式并不满足距离的三角不等式(例如，例如，DTW(111,111222)DTW(111,112)+DTW(112,111222)，在，在应用到依据索引的时间序列相似查询时剪枝过滤的程度应用到依据索引的时间序列相似查询时剪枝过滤的程度有限，在使用索引查询时则可能会产生漏查。有限，在使用索引查询时则可能会产生漏查。 病态弯病态弯曲问题，由于曲问题，由于 DTW允许在比较的时候两个时间序列可进允许在比较的时候两个时间序列可进行一定的非对应时刻匹配，即求取最小距离而忽略时间行一定的非对应时刻匹配，即求取最小距离而忽略时间上的差异，这容易

18、形成时域差异过大的情况发生。上的差异，这容易形成时域差异过大的情况发生。 解决办法：对于，对比较的时间序列数据进行降维处解决办法：对于，对比较的时间序列数据进行降维处理，进一步探索高压缩率和高效保真的降维方法；对于理，进一步探索高压缩率和高效保真的降维方法；对于，设定路径查找的带宽限制，即比较点不会超出参照，设定路径查找的带宽限制，即比较点不会超出参照点的点的ti-w,ti+w的时间范围。这种方法同时的时间范围。这种方法同时 还可能降低还可能降低算法的时间复杂度。算法的时间复杂度。通常将通常将w w选为时间序列长度的选为时间序列长度的10%10%。 LB_Keogh：一种考虑弯曲路径限制的：一

19、种考虑弯曲路径限制的DTW 计算计算方法方法 对于弯曲路径限制为对于弯曲路径限制为 w w 的时间序列的时间序列 DTW DTW 距离计算，距离计算，定义两个序列定义两个序列 U U 和和 L L，其中对于第，其中对于第 i i 个元素我们个元素我们有如下的上下界定义：有如下的上下界定义： U U 和和 L L 作为在作为在 2w 2w 时间窗内，对于原时间序列的时间窗内，对于原时间序列的每个元素所对应的上下界，表现在图形上实际上是每个元素所对应的上下界，表现在图形上实际上是形成了一个带状的域将原始时间序列包裹在这个域形成了一个带状的域将原始时间序列包裹在这个域中，如图中，如图 3-4 3-4

20、 所示。所示。此时，此时， LB_Keogh距离定义为：距离定义为： 定理：对于长度为 n 的任何两个时间序列 X 和 Y，限定弯曲路径窗口为w，即对于 xi和 yj点的比较，限定为 j-w i j+w，存在如下不等式：LB_Keogh(X,Y) DTW(X,Y)。 性质：性质：LB_Keogh 距离不是对称的。即距离不是对称的。即 LB_Keogh(X,Y) LB_Keogh(Y,X)。LB_Keogh的的Matlab实现实现LB_Keogh=sqrt(sum(Q U.* Q-U; Q n) 0 100 200 300 400 0 100 200 300 400 C Q Uniform Sc

21、aling time series query, Q, length n candidate, C, length m (mn) stretch Q to length p (npm): Qp Qpj = Qj*n/p, 1 j p scaling factor, sf = p/n max scaling factor, sfmax= m/n 0 100 200 300 400 0 100 200 300 400 C Q 0 100 200 300 400 0 100 200 300 400 Q Qp例如： a=1:10 b=1:13 如如c=b*(10/13)，则得，则得 c=0.76923

22、08 1.5384615 2.3076923 3.0769231 3.8461538 4.6153846 5.3846154 6.1538462 6.9230769 7.6923077 8.4615385 9.2307692 10.0000000 如如 c=ceiling(b*(10/13) 则则 c= 1 2 3 4 4 5 6 7 7 8 9 10 10DTW与与Uniform Scaling的不同的不同 Dynamic Time Warping (DTW) Considers only local adjustments in time, to match two time series

23、 However sometimes global adjustments are required DTW is being extensively used uniform scaling is complementary combination of both techniques offers rich, high-quality result setDTWUniform ScalingDTW与与Uniform Scaling的不同的不同 感觉Uniform Scaling不会比DTW（长度从n到m）做得更好。时间序列常见距离定义(7)Pearson 系数系数 Pearson 系数也是

24、一种相似性度量，对于时间序列系数也是一种相似性度量，对于时间序列 X 和和Y ，其，其 Pearson 系数为：系数为： Pearson 系数用于线性关系时能够取得较好的效果，系数用于线性关系时能够取得较好的效果，但是对于非线性的测试则效果不佳，而且但是对于非线性的测试则效果不佳，而且 Pearson 系数对于数据中的突变数据点比较敏感。系数对于数据中的突变数据点比较敏感。Pearson Pearson 系数应用示例系数应用示例 在基于协同过滤的推荐系统中Pearson Pearson 系数应用示例系数应用示例Pearson Pearson 系数应用示例系数应用示例The Pearson co

25、rrelation coefficient takes values from +1 (strong positive correlation) to 1 (strong negative correlation). The similarities to the other users, User2 to User4, are 0.70, 0.00, and 0.79, respectively.Pearson Pearson 系数应用示例系数应用示例Pearson Pearson 系数还有另外一个杰出的性质系数还有另外一个杰出的性质Pearson 系数适合做增量计算 (8)基于基于PAA和

26、和SAX表示的距离表示的距离PAA distance lower-bounds the Euclidean Distance 0 20 40 60 80 100 120 -1.5 -1 -0.5 0 0.5 1 1.5 C Q 0 20 40 60 80 100 120 -1.5 -1 -0.5 0 0.5 1 1.5C Q = baabccbc C = babcacca QniiicqCQD12,Euclidean DistancewiiiwncqCQDR12),(wiiiwncqdistCQMINDIST12) ,(),(dist() can be implemented using a

27、table lookup.(9)马氏距离(Mahalanobis distance) 度量点与集合间的相似性 The Mahalanobis distance is a measure of the distance between a point P and a distribution D, introduced by P. C. Mahalanobis in 1936 The Mahalanobis distance of an observation x=(x1,x2,xn)T from a set of observations with mean =(1,2,n)T and cov

28、ariance matrix S is defined as: Mahalanobis distance can also be defined as a dissimilarity measure between two random vectors and of the same distribution with the covariance matrix S: If the covariance matrix is the identity matrix, the Mahalanobis distance reduces to the Euclidean distance. If th

29、e covariance matrix is diagonal, then the resulting distance measure is called a normalized Euclidean distance: (si是标准差是标准差)直观解释 考虑估计欧氏空间中的一个测试点属于一个集合考虑估计欧氏空间中的一个测试点属于一个集合的概率的问题，直观地离集合的质心越近，这个的概率的问题，直观地离集合的质心越近，这个点属于该集合的概率就越大。但是还要考虑这个点属于该集合的概率就越大。但是还要考虑这个集合的分布形状，即要计算集合的标准差并比较集合的分布形状，即要计算集合的标准差并比较这个点与其相应方向的标准差值的大小。这个点与其相应方向的标准差值的大小。 The Mahalanobis distance is simply the The Mahalanobis distance is si