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

时间序列挖掘●相似性山西财经大学信息管理学院常新功第三章目录•时间序列相似性定义•时间序列相似性应用场景•时间序列常见距离定义•时间序列相似性分类时间序列相似性定义•反映两条时间序列相似程度的值刻划了这两条时间序列的相似性，其概念和方法是时间序列挖掘的基础。•给定某个时间序列，要求从大型时间序列数据集合中找出与之相似的序列---静态时间序列的相似性。•实际生活中有大量以动态序列形式存在的时间序列(时间序列流)。•随着研究的深入，动态时间序列的相似性问题也日益成为新时期时间序列相似性问题研究的重要组成部分。•与传统静态数据的精确相似不同，时间序列的相似性会呈现多种变形，如振幅平移和伸缩、线性漂移、不连续、噪声、时间轴伸縮等等。针对这些相似性变形，研究者们提出了很多种相似性度量方法。时间序列相似性应用场景•1．区别多个公司发展的相似性模型；•2．在股票价格上寻找价格波动的相似运动；•3．在乐谱版权问题上确认两份乐谱是否存在相似性；•4．对具有相似销售模式的商品进行聚类；•5．查找具有相似病情的心电图；•6．对网络的异常流量预警；•7．对天气预报中灾害天气的模式提取等。时间序列常见距离定义•距离函数一般要满足如下几个条件：–非负性，即d(A,B)0–同一性：即d(A,A)=0–对称性：d(A,B)=d(B,A)–满足三角不等式：d(A,B)d(A,C)+d(C,B)，即两点间直线最短。这是一个高要求。•实际应用中，距离函数很难满足以上所有条件，这取决于数据的表示和距离的计算方法。但是，当一些约束适当放松的时候，相似性度量仍然可以有效地进行。•时间序列间的距离可用来衡量时间序列之间的差异性，以确定序列是否相似。时间序列常见距离定义•时间序列间的距离可用来衡量时间序列之间的差异性，以确定序列是否相似。(1)Minkowski距离(MinkowskiDistance)•Minkowski距离实际是一系列距离的集合，对于两时间序列和其计算方法为其中p=1时为曼哈顿距离；p=2时为欧氏距离；时间序列常见距离定义(2)欧氏距离(EuclideanDistance)•Euclidean距离是被广泛采用的时间序列相似度量，在时间序列相似性问题研究初期大量采用，它的计算方法是在实际使用中，为了防止对各段采用相同的系数，有时采用加权的欧氏距离：EuclideanDistanceMetricQCD(Q,C)niiicqCQD12,GiventwotimeseriesQ=q1…qnandC=c1…cntheirEuclideandistanceisdefinedas:欧氏距离的优缺点•Euclidean距离的优点在于：①直观而计算简便，有良好的数学背景和意义；②由于序列的一些常用变换(如傅立叶变换等)的系数有欧氏距离保持不变的性质，所以经常用于数据库的高效索引；③无参。•缺点在于：①需要计算的两序列具有相同的长度；②对于时间序列点的突变(e.g.noise)比较敏感；③Euclidean距离对序列按照时间轴进行点对点依次计算，对时间序列的错位、移位(outofphase)等比较敏感。斜率距离---欧氏距离的一个变形•设其中X和Y分别是原始时间序列数据转换而成的斜率组成的时间序列，即：时间序列常见距离定义(3)编辑距离(EditDistance)•Edit距离是计算两字符串序列的距离一种度量，它的定义是将一字符串转换为另一字符串所需的最小编辑(插入、删除、改变)步数。•将时间序列进行不同的量化和编码后形成字符串，采用编辑距离计算两字符串的距离。•Edit距离的优点是：①充分利用了字符串匹配等成熟计算方法；②容易为人所理解；③允许多对无。•缺点是：①需要将时间序列转化为相应的字符串，精度不高；②对于不同步的时间序列效果较差。时间序列常见距离定义(4)最大公共子串LCS(LongestCommonSubseries)方法•LCS是计算两时间序列间具有的公共长度子串，并以该子串的长度与这两个时间序列中较长序列的长度比值作为序列间的相似性度量。•LCS方法借用字符串匹配中的相似性度量，有其一定的可取之处。其不足是：①公共长度子串的长度可能偏小，两时间序列间可能非常相似，但是由于数值并不能完全一致，细小的偏差都会导致公共子串的长度偏小，从而影响到度量效果；②公共长度子串的获取是一个问题，虽然可以采用较为常见的动态规划的方法解决，但是由于时间序列很可能是长度很长的序列，空间开销较大。时间序列常见距离定义(5)DTW距离(DynamicTimeWarpingDistance)•DTW距离最先在语音数字处理领域得到诸多成功的应用，由Berndt和Clifford于90年代中旬引入到时间序列挖掘中，并取得了巨大的成功。•在时间序列中，需要比较两段长度可能并不相等的时间序列的相似性，在语音识别领域表现为不同人的语速不同。而且同一个单词内的不同音素的发音速度也不同，比如有的人会把‘A’这个音拖得很长，或者把‘i’发的很短。另外，不同时间序列可能仅仅存在时间轴上的位移，亦即在还原位移的情况下，两个时间序列是一致的。在这些复杂情况下，使用传统的欧几里得距离无法有效地求得两个时间序列之间的距离(或者相似性)。•对于时间序列和，定义距离矩阵：DM=(aij)m×n，其中aij=(xi-yj)2,或其它度量。在DM中寻找一条弯曲路径W＝w1,w2,…,wK,其中wi=某个aij，满足以下性质：1、有界性：max{m,n}≤K≤m+n-1；2、边界性：w1=a11,wk=amn；3、单调性和连续性：在弯曲路径中，相邻两个元素wk=aij,wk+1=ast，则0s-i1,0t-j1。单调性保证了在时间序列的每个时刻不会出现时间交叉现象：同时使达到最小的弯曲路径W＝w1,w2,…,wK,称为最佳弯曲路径。这个最小值称为时间序列X和Y动态时间弯曲距离，简记为Ddtw(X,Y)，即有：DTW伪代码实现intDTWDistance(s:array[1..n],t:array[1..m]){DTW:=array[0..n,0..m]fori:=1tonDTW[i,0]:=infinityfori:=1tomDTW[0,i]:=infinityDTW[0,0]:=0fori:=1tonforj:=1tomcost:=d(s[i],t[j])DTW[i,j]:=cost+minimum(DTW[i-1,j],DTW[i,j-1],DTW[i-1,j-1])returnDTW[n,m]}DTW的优缺点•DTW的优点在于：①克服了Euclidean距离点对必须对应的问题，允许不同步的点对应计算；②允许两时间序列具有不同长度；③对时间序列的同步问题不敏感。DTW的优缺点•缺点在于：①DTW的计算复杂度较高，对于长度分别为n和m的时间序列，准确计算DTW距离需要O(nm)的时间复杂度；②DTW并不满足距离的三角不等式(例如，DTW(111,111222)DTW(111,112)+DTW(112,111222))，在应用到依据索引的时间序列相似查询时剪枝过滤的程度有限，在使用索引查询时则可能会产生漏查。③病态弯曲问题，由于DTW允许在比较的时候两个时间序列可进行一定的非对应时刻匹配，即求取最小距离而忽略时间上的差异，这容易形成时域差异过大的情况发生。•解决办法：对于①，对比较的时间序列数据进行降维处理，进一步探索高压缩率和高效保真的降维方法；对于③，设定路径查找的带宽限制，即比较点不会超出参照点的[ti-w,ti+w]的时间范围。这种方法同时还可能降低算法的时间复杂度。通常将w选为时间序列长度的10%。LB_Keogh：一种考虑弯曲路径限制的DTW计算方法•对于弯曲路径限制为w的时间序列DTW距离计算，定义两个序列U和L，其中对于第i个元素我们有如下的上下界定义：•U和L作为在2w时间窗内，对于原时间序列的每个元素所对应的上下界，表现在图形上实际上是形成了一个带状的域将原始时间序列包裹在这个域中，如图3-4所示。此时，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([[QU].*[Q-U];[QL].*[L-Q]].^2));LB_Hust距离---对LB_Keogh距离的改进•针对LB_Keogh距离计算的非对称性•其中，Lxi和Uxi分别对应时间序列X的第i个元素在2w时间域内的最小值和最大值。Lyi和Uyi同理。距离产生方式如图3-5所示。•定理：对于长度为n的任何两个时间序列X和Y，限定弯曲路径窗口为w，即对于xi和yj点的比较，限定为j-wij+w，存在如下不等式：LB_Hust(X,Y)Keogh(X,Y)。•性质1：LB_Hust距离是对称的。即LB_Hust(X,Y)=LB_Hust(Y,X)。这可以减少距离计算的次数。•性质2：在LB_Hust距离计算方式下，时间复杂度由传统的DTW距离计算的O(nm)缩减到O(n)。时间序列常见距离定义(6)UniformScaling距离•timeseries–query,Q,lengthn–candidate,C,lengthm(mn)01002003004000100200300400CQUniformScaling•timeseries–query,Q,lengthn–candidate,C,lengthm(mn)•stretchQtolengthp(n≤p≤m):Qp–Qpj=Q┌j*n/p┐,1≤j≤p•scalingfactor,sf=p/n–maxscalingfactor,sfmax=m/n01002003004000100200300400CQ01002003004000100200300400QQp例如：•a=1:10•b=1:13•如c=b*(10/13)，则得•c=0.76923081.53846152.30769233.07692313.84615384.61538465.38461546.15384626.92307697.69230778.46153859.230769210.0000000•如c=ceiling(b*(10/13))•则c=123445677891010DTW与UniformScaling的不同•DynamicTimeWarping(DTW)–Considersonlylocaladjustmentsintime,tomatchtwotimeseries–Howeversometimesglobaladjustmentsarerequired•DTWisbeingextensivelyused•uniformscalingiscomplementary–combinationofbothtechniquesoffersrich,high-qualityresultsetDTWUniformScalingDTW与UniformScaling的不同•感觉UniformScaling不会比DTW（长度从n到m）做得更好。时间序列常见距离定义(7)Pearson系数•Pearson系数也是一种相似性度量，对于时间序列X和Y，其Pearson系数为：•Pearson系数用于线性关系时能够取得较好的效果，但是对于非线性的测试则效果不佳，而且Pearson系数对于数据中的突变数据点比较敏感。Pearson系数应用示例•在基于协同过滤的推荐系统中Pearson系数应用示例Pearson系数应用示例ThePearsoncorrelationcoefficienttakesvaluesfrom+1(strongpositivecorrelation)