《时间序列挖掘相似性.ppt》由会员分享，可在线阅读，更多相关《时间序列挖掘相似性.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、时间序列挖掘相似性山西财经大学信息管理学院常新功山西财经大学信息管理学院常新功第三章目 录时间序列相似性定义时间序列相似性应用场景时间序列常见距离定义时间序列相似性分类时间序列相似性定义反映两条反映两条时间序列相似程度的序列相似程度的值刻划了刻划了这两条两条时间序序列的相似性，其概念和方法是列的相似性，其概念和方法是时间序列挖掘的基序列挖掘的基础。给定某个定某个时间序列，要求从大型序列，要求从大型时间序列数据集合中序列数据集合中找出与之相似的序列找出与之相似的序列-静静态时间序列的相似性。序列的相似性。实际生活中有大量以生活中有大量以动态序列形式存在的序列形式存在的时间序列序列(时间序列流序列
2、流)。随着研究的深入，随着研究的深入，动态时间序列的相似性序列的相似性问题也日益也日益成成为新新时期期时间序列相似性序列相似性问题研究的重要研究的重要组成部分。成部分。与与传统静静态数据的精确相似不同，数据的精确相似不同，时间序列的相似性序列的相似性会呈会呈现多种多种变形，如振幅平移和伸形，如振幅平移和伸缩、线性漂移、不性漂移、不连续、噪声、噪声、时间轴伸縮等等。伸縮等等。针对这些相似性些相似性变形，形，研究者研究者们提出了很多种相似性度量方法。提出了很多种相似性度量方法。时间序列相似性应用场景1区区别多个公司多个公司发展的相似性模型；展的相似性模型；2在股票价格上在股票价格上寻找价格波找价格
3、波动的相似运的相似运动；3在在乐谱版版权问题上确上确认两份两份乐谱是否存在相似是否存在相似性；性；4对具有相似具有相似销售模式的商品售模式的商品进行聚行聚类；5查找具有相似病情的心找具有相似病情的心电图；6对网网络的异常流量的异常流量预警；警；7对天气天气预报中灾害天气的模式提取等。中灾害天气的模式提取等。时间序列常见距离定义距离函数一般要满足如下几个条件：距离函数一般要满足如下几个条件：非负性，即非负性，即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
4、(A,B)d(A,B)d(A,C)+d(C,B)d(A,C)+d(C,B)，即两点，即两点间直线最短。这是一个高要求。间直线最短。这是一个高要求。实际应用中，距离函数很难满足以上所有条件，实际应用中，距离函数很难满足以上所有条件，这取决于数据的表示和距离的计算方法。但是，这取决于数据的表示和距离的计算方法。但是，当一些约束适当放松的时候，相似性度量仍然可当一些约束适当放松的时候，相似性度量仍然可以有效地进行。以有效地进行。时间序列间的距离可用来衡量时间序列之间的差时间序列间的距离可用来衡量时间序列之间的差异性，以确定序列是否相似。异性，以确定序列是否相似。时间序列常见距离定义时间序列序列间的距
5、离可用来衡量的距离可用来衡量时间序列之序列之间的差的差异性，以确定序列是否相似。异性，以确定序列是否相似。(1)Minkowski距离距离(MinkowskiDistance)Minkowski距离距离实际是一系列距离的集合，是一系列距离的集合，对于于两两时间序列序列和和其其计算方法算方法为其中其中p=1时为曼哈曼哈顿距离；距离；p=2时为欧氏距离；欧氏距离；时间序列常见距离定义(2)欧氏距离欧氏距离(EuclideanDistance)Euclidean距离是被广泛采用的距离是被广泛采用的时间序列相似度量，序列相似度量，在在时间序列相似性序列相似性问题研究初期大量采用，它的研究初期大量采用，
6、它的计算方法是算方法是在在实际使用中，使用中，为了防止了防止对各段采用相同的系数，各段采用相同的系数，有有时采用加采用加权的欧氏距离：的欧氏距离：EuclideanDistanceMetricQCD(Q,C)Given two time series Q=q1qn and C=c1cn their Euclidean distance is defined as:欧氏距离的优缺点Euclidean距离的距离的优优点在于：点在于：直直观观而而计算算简便，便，有良好的数学背景和意有良好的数学背景和意义；由于序列的一些常由于序列的一些常用用变换(如傅立叶如傅立叶变换变换等等)的系数有欧的系数有欧氏距
7、离保持不氏距离保持不变的性的性质，所以，所以经常用于数据常用于数据库的高效索引；的高效索引；无参。无参。缺点在于：缺点在于：需要需要计计算的两序列具有相同的算的两序列具有相同的长长度；度；对对于于时间时间序列点的突序列点的突变变(e.g.noise)比比较敏感；敏感；Euclidean距离距离对对序列按照序列按照时间轴进时间轴进行点行点对对点依点依次次计计算，算，对时间对时间序列的序列的错错位、移位位、移位(outofphase)等比等比较敏感。敏感。斜率距离-欧氏距离的一个变形设其中其中X和和Y分分别是原始是原始时间序列数据序列数据转换而成的斜率而成的斜率组成的成的时间序列，即：序列，即：时
8、间序列常见距离定义(3)编辑距离距离(EditDistance)Edit距离是距离是计算两字符串序列的距离一种度量，它算两字符串序列的距离一种度量，它的定的定义是将一字符串是将一字符串转换为另一字符串所需的最小另一字符串所需的最小编辑(插入、插入、删除、改除、改变)步数。步数。将将时间序列序列进行不同的量化和行不同的量化和编码后形成字符串，后形成字符串，采用采用编辑距离距离计算两字符串的距离。算两字符串的距离。Edit距离的距离的优点是：点是：充分利用了字符串匹配等充分利用了字符串匹配等成熟成熟计算方法；算方法；容易容易为人所理解；人所理解；允允许多多对无。无。缺点是：缺点是：需要将需要将时间
9、序列序列转化化为相相应的字符串，的字符串，精度不高；精度不高；对于不同步的于不同步的时间序列效果序列效果较差。差。时间序列常见距离定义(4)最大公共子串最大公共子串LCS(LongestCommonSubseries)方法方法LCS是是计算两算两时间序列序列间具有的公共具有的公共长度子串，并度子串，并以以该子串的子串的长度与度与这两个两个时间序列中序列中较长序列的序列的长度比度比值作作为序列序列间的相似性度量。的相似性度量。LCS方法借用字符串匹配中的相似性度量，有其一方法借用字符串匹配中的相似性度量，有其一定的可取之定的可取之处。其不足是：。其不足是：公共公共长度子串的度子串的长度可能偏小，
10、两度可能偏小，两时间序列序列间可能非常相似，但是由可能非常相似，但是由于数于数值并不能完全一致，并不能完全一致，细小的偏差都会小的偏差都会导致公共致公共子串的子串的长度偏小，从而影响到度量效果；度偏小，从而影响到度量效果；公共公共长度子串的度子串的获取是一个取是一个问题，虽然可以采用然可以采用较为常常见的的动态规划的方法解决，但是由于划的方法解决，但是由于时间序列很可序列很可能是能是长度很度很长的序列，空的序列，空间开开销较大。大。时间序列常见距离定义(5)DTW(5)DTW 距离距离(Dynamic Time Warping Distance)(Dynamic Time Warping Di
11、stance)DTW DTW 距离最先在语音数字处理领域得到诸多成功的距离最先在语音数字处理领域得到诸多成功的应用，由应用，由 Berndt Berndt 和和 CliffordClifford于于 90 90 年代中旬引年代中旬引入到时间序列挖掘中，并取得了巨大的成功。入到时间序列挖掘中，并取得了巨大的成功。在时间序列中，需要比较两段长度可能并不相等的在时间序列中，需要比较两段长度可能并不相等的时间序列的相似性，在语音识别领域表现为不同人时间序列的相似性，在语音识别领域表现为不同人的语速不同。而且同一个单词内的不同音素的发音的语速不同。而且同一个单词内的不同音素的发音速度也不同，比如有的人会
12、把速度也不同，比如有的人会把AA这个音拖得很这个音拖得很长，或者把长，或者把ii发的很短。另外，不同时间序列发的很短。另外，不同时间序列可能仅仅存在时间轴上的位移，亦即在还原位移的可能仅仅存在时间轴上的位移，亦即在还原位移的情况下，两个时间序列是一致的。在这些复杂情况情况下，两个时间序列是一致的。在这些复杂情况下，使用传统的欧几里得距离无法有效地求得两个下，使用传统的欧几里得距离无法有效地求得两个时间序列之间的距离时间序列之间的距离(或者相似性或者相似性)。对于于时间序列序列和和，定，定义距离矩距离矩阵：DM=(aij)mn，其中，其中aij=(xi-yj)2,或其它或其它度量。度量。在在DM
13、中中寻找一条弯找一条弯曲路径曲路径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,称称为最佳弯曲路径。最佳弯曲路径。这个最小个最小值称称为时间序列序列 X 和和
14、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+minimum(DTWi-1,j ,DTWi ,j-1,DTWi-1,j-1)return DTWn,mDTW的优缺点DTW的的优点在于：
15、点在于：克服了克服了Euclidean距距离点离点对必必须对应的的问题，允，允许不同步的点不同步的点对应计算；算；允允许两两时间序列具有不同序列具有不同长度；度；对时间序列的同步序列的同步问题不敏感。不敏感。DTW的优缺点缺点在于：缺点在于：DTW的的计算复算复杂度度较高，高，对于于长度分度分别为n和和m的的时间序列，准确序列，准确计算算DTW距离需要距离需要O(nm)的的时间复复杂度；度；DTW并不并不满足距离的三角不等式足距离的三角不等式(例如，例如，DTW(111,111222)DTW(111,112)+DTW(112,111222)，在，在应用到依据索引的用到依据索引的时间序列相似序列
16、相似查询时剪枝剪枝过滤的程度的程度有限，在使用索引有限，在使用索引查询时则可能会可能会产生漏生漏查。病病态弯曲弯曲问题，由于，由于DTW允允许在比在比较的的时候两个候两个时间序列可序列可进行一定的非行一定的非对应时刻匹配，即求取最小距离而忽略刻匹配，即求取最小距离而忽略时间上的差异，上的差异，这容易形成容易形成时域差异域差异过大的情况大的情况发生。生。解决解决办法：法：对于于，对比比较的的时间序列数据序列数据进行降行降维处理，理，进一步探索高一步探索高压缩率和高效保真的降率和高效保真的降维方法；方法；对于于，设定路径定路径查找的找的带宽限制，即比限制，即比较点不会超出参照点不会超出参照点的点的
17、ti-w,ti+w的的时间范范围。这种方法同种方法同时还可能降低算可能降低算法的法的时间复复杂度。度。通常将通常将w w选为时间序列长度的选为时间序列长度的10%10%。LB_Keogh：一种考：一种考虑弯曲路径限制的弯曲路径限制的DTW计算算方法方法对于弯曲路径限制为对于弯曲路径限制为 w w 的时间序列的时间序列 DTW DTW 距离计算，距离计算，定义两个序列定义两个序列 U U 和和 L L，其中对于第，其中对于第 i i 个元素我们个元素我们有如下的上下界定义：有如下的上下界定义：U U 和和 L L 作为在作为在 2w 2w 时间窗内，对于原时间序列的时间窗内，对于原时间序列的每个
18、元素所对应的上下界，表现在图形上实际上是每个元素所对应的上下界，表现在图形上实际上是形成了一个带状的域将原始时间序列包裹在这个域形成了一个带状的域将原始时间序列包裹在这个域中，如图中，如图 3-4 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实
19、现LB_Keogh=sqrt(sum(QU.*Q-U;Qn)0 100 200 300 400 0 100 200 300 400 C Q UniformScalingtimeseriesquery,Q,length ncandidate,C,length m(mn)stretchQtolengthp(npm):QpQpj=Qj*n/p,1 j pscalingfactor,sf=p/nmaxscalingfactor,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
20、Qp例如：a=1:10b=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,tomatchtwotimeseriesHow
21、eversometimesglobaladjustmentsarerequiredDTWisbeingextensivelyuseduniformscalingiscomplementarycombinationofbothtechniquesoffersrich,high-qualityresultsetDTWUniform ScalingDTW与与UniformScaling的不同的不同感觉Uniform Scaling不会比DTW（长度从n到m）做得更好。时间序列常见距离定义(7)Pearson系数系数Pearson系数也是一种相似性度量，系数也是一种相似性度量，对于于时间序列序列X和和
22、Y，其，其Pearson系数系数为：Pearson系数用于系数用于线性关系性关系时能能够取得取得较好的效果，好的效果，但是但是对于非于非线性的性的测试则效果不佳，而且效果不佳，而且Pearson系数系数对于数据中的突于数据中的突变数据点比数据点比较敏感。敏感。Pearson Pearson 系数应用示例系数应用示例在基于协同过滤的推荐系统中Pearson Pearson 系数应用示例系数应用示例Pearson Pearson 系数应用示例系数应用示例The Pearson correlation coefficient takes values from+1(strong positive c
23、orrelation)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和和SAX表示的距离表示的距离PAA distance lower-bounds the Euclidean Distance 0 20 40
24、 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 QEuclidean Distancedist()can be implemented using a table lookup.(9)马氏距离(Mahalanobisdistance)度量点与集合间的相似性TheMahalanobisdistanceisameasureofthedistancebetweenapointPandadistributionD,introduced
25、byP.C.Mahalanobisin1936TheMahalanobisdistanceofanobservationx=(x1,x2,xn)T fromasetofobservationswithmean=(1,2,n)T andcovariancematrixSisdefinedas:MahalanobisdistancecanalsobedefinedasadissimilaritymeasurebetweentworandomvectorsandofthesamedistributionwiththecovariancematrixS:Ifthecovariancematrixist
26、heidentitymatrix,theMahalanobisdistancereducestotheEuclideandistance.Ifthecovariancematrixisdiagonal,thentheresultingdistancemeasureiscalledanormalized Euclidean distance:(si是是标准差准差)直观解释考虑估计欧氏空间中的一个测试点属于一个集合考虑估计欧氏空间中的一个测试点属于一个集合的概率的问题，直观地离集合的质心越近，这个的概率的问题，直观地离集合的质心越近，这个点属于该集合的概率就越大。但是还要考虑这个点属于该集合的概率
27、就越大。但是还要考虑这个集合的分布形状，即要计算集合的标准差并比较集合的分布形状，即要计算集合的标准差并比较这个点与其相应方向的标准差值的大小。这个点与其相应方向的标准差值的大小。The Mahalanobis distance is simply the The Mahalanobis distance is simply the distance of the test point from the center distance of the test point from the center of mass divided by the width of the of mass di
28、vided by the width of the ellipsoid in the direction of the test ellipsoid in the direction of the test point.point.(9)马氏距离(Mahalanobisdistance)度量两个集合间的相似性不同的相似性度量可能给出不同的挖掘结果时间序列相似性分类Werefertodistancemeasuresthatcomparetheithpointofonetimeseriestotheithpointofanotheraslock-step measures(e.g.,Euclide
29、andistanceandtheotherLpnorms),anddistancemeasuresthatallowcomparisonofone-to-manypoints(e.g.,DTW)andone-to-many/one-to-nonepoints(e.g.,LCSS)aselastic measures.参考文献1Junkui,L,Yuanzhen,W,Xinping,L,LB_HUST:Asymmetricalboundarydistanceforclusteringtimeseries.The9thIntlConfonInformationTechnology,IEEEPress,2006.203208谢谢！