时间序列相似性度量方法综述.doc

时间序列相似性度量方法综述.doc时间序列相似性度量方法综述
时间序列相似性度量方法综述
【摘要】时间序列的相似性度量是时间序列数据挖掘的基础 问题，针对时间序列相似性度量问题，综述了现有的时间序列相似性 度量方法，重点介绍了各种度量方法的基本原理、优缺点，从而便于 研究者对已有算法进行改进和研究新的时间序列相似性度量方法。
【关键词】时间序列数据挖掘相似性度量
时间序列的相似性度量是时间序列数据挖掘的基础问题。两条完 全相同的时间序列几乎不存在，因此采用相似性(距离)度量来衡量 时间序列之间的相似性。由于时间序列数据的复杂性，经常发生振幅 平移和伸缩、线性漂移、不连续性、时间轴伸缩和弯曲等形变，为了 最大程度地支持上述形变，并尽量提高相似性度量的时间效率，有一 系列时间序列距离度量方法被提出和引入。
一、 明科夫斯基距离
明科夫斯基(Minkowski)距离的优点在于简单直观，易于计算。 设两长度相等的序列和，把它们看成n维空间中的两个坐标点，则两 者之间的明科夫斯基距离［2］定义为：
当q=l时为曼哈顿(Manhattan)距离，
当q=2时为欧几里德(Euclidean)距离，
其中欧几里德距离是最常用也是应用最广泛的一种距离，其计算 复杂度不高，与序列长度成线性关系，因而具有很好的伸缩性，序列 长度的增加不会造成计算复杂度的迅速提高。并且欧氏距离满足距离 三角不等式，在基于索引的查询时，可以利用距离三角不等式快速过 滤一些不符合条件的索引节点。
二、 动态时间弯曲距离
动态时间弯曲(DTW)距离在语音处理领域得到广泛的研究， Berndt和Clifford首次将DTW引入到数据挖掘领域［3］。与欧几里 德距离相比，动态时间弯曲距离不要求两条时间序列点与点之间一一
对应，允许序列点自我复制在进行对齐匹配。
动态时间弯曲（DTW）距离：设时间序列和，则X和Y的DTW距 离定义为：
式中：表示序列点和之间的距离，可以根据情况选择不同的距离 度量，通常使用明科夫斯基距离。
动态时间弯曲（DTW）距离的缺点是时间复杂度太高（），在子序 列匹配时如不进行优化甚至为（，L为子序列的长度），不适用于海 量时间序列的数据挖掘，需要专门采用某种技巧来减少其计算复杂度。
三、 最长公共子串距离
当两条时间序列在大部分时间段具有相似的形态，而只在很短的 时间范围内发生剧烈突变或间断时（即时间序列形变中的不连续性）， 欧氏距离和动态时间弯曲距离都忠实地记录了该形变的影响，这对于 那些忽略时间序列不连续性的相似性度量问题而言是不适用的。
设时间序列和，它们满足以下条件的最长公共子序列分别为和： 1）对任意，都满足；2）对任意，都有。那么时间序列和之间的相似 度定义为：
最长公共字串（LCS）距离能克服时间序列的短期突变或间断带 来的相似性问题，但无法处理振幅平移、时间轴伸缩和弯曲等形变。
四、 结束语
本文对现有常用的时间序列相似性度量方法进行综述，介绍了各 种度量方法的基本原理、优缺点，从而便于研究者对已有算法进行改 进和研究新的时间序列相似性度量方法。
参考文献：
.毛红保等，面向相似性查询的时间序列距离度量方法述评. 计算机工程与设计，2010 （19）：第4221-4224页.
.孙即祥，：国防科技大学出版社.
. B