论文部分内容阅读
【摘 要】时间序列的相似性度量是时间序列数据挖掘的基础问题，针对时间序列相似性度量问题，综述了现有的时间序列相似性度量方法，重点介绍了各种度量方法的基本原理、优缺点，从而便于研究者对已有算法进行改进和研究新的时间序列相似性度量方法。
【关键词】时间序列 数据挖掘 相似性 度量
时间序列的相似性度量是时间序列数据挖掘的基础问题。两条完全相同的时间序列几乎不存在，因此采用相似性（距离）度量来衡量时间序列之间的相似性。由于时间序列数据的复杂性，经常发生振幅平移和伸缩、线性漂移、不连续性、时间轴伸缩和弯曲等形变，为了最大程度地支持上述形变，并尽量提高相似性度量的时间效率，有一系列时间序列距离度量方法被提出和引入。
一、明科夫斯基距离
明科夫斯基（Minkowski）距离的优点在于简单直观，易于计算。设两长度相等的序列和，把它们看成n维空间中的两个坐标点，则两者之间的明科夫斯基距离[2]定义为：
当q=1时为曼哈顿（Manhattan）距离，
当q=2时为欧几里德（Euclidean）距离，
其中欧几里德距离是最常用也是应用最广泛的一种距离，其计算复杂度不高，与序列长度成线性关系，因而具有很好的伸缩性，序列长度的增加不会造成计算复杂度的迅速提高。并且欧氏距离满足距离三角不等式，在基于索引的查询时，可以利用距离三角不等式快速过滤一些不符合条件的索引节点。
二、动态时间弯曲距离
动态时间弯曲（DTW）距离在语音处理领域得到广泛的研究，Berndt和Clifford首次将DTW引入到数据挖掘领域[3]。与欧几里德距离相比，动态时间弯曲距离不要求两条时间序列点与点之间一一对应，允许序列点自我复制在进行对齐匹配。
动态时间弯曲（DTW）距离：设时间序列和，则X和Y的DTW距离定义为：
式中：表示序列点和之间的距离，可以根据情况选择不同的距离度量，通常使用明科夫斯基距离。
动态时间弯曲（DTW）距离的缺点是时间复杂度太高（），在子序列匹配时如不进行优化甚至为（，L为子序列的长度），不适用于海量时间序列的数据挖掘，需要专门采用某种技巧来减少其计算复杂度。
三、最长公共子串距离
当两条时间序列在大部分时间段具有相似的形态，而只在很短的时间范围内发生剧烈突变或间断时（即时间序列形变中的不连续性），欧氏距离和动态时间弯曲距离都忠实地记录了该形变的影响，这对于那些忽略时间序列不连续性的相似性度量问题而言是不适用的。
设时间序列和，它们满足以下条件的最长公共子序列分别为和：1）对任意，都满足；2）对任意，都有。那么时间序列和之间的相似度定义为：
最长公共字串（LCS）距离能克服时间序列的短期突变或间断带来的相似性问题，但无法处理振幅平移、时间轴伸缩和弯曲等形变。
四、结束语
本文对现有常用的时间序列相似性度量方法进行综述，介绍了各种度量方法的基本原理、优缺点，从而便于研究者对已有算法进行改进和研究新的时间序列相似性度量方法。
参考文献：
[1]. 毛红保等， 面向相似性查询的时间序列距离度量方法述评. 计算机工程与设计， 2010（19）： 第4221-4224页.
[2]. 孙即祥， 现代模式识别. 2002： 国防科技大学出版社.
[3]. Berndt， D.J. and J. Clifford， Using dynamic time warping to find patterns in time series. 1994.
[4]. Keogh， E. Fast similarity search in the presence of longitudinal scaling in
time series databases. in Tools with Artificial Intelligence， 1997. Proceedings.， Ninth IEEE International Conference on. 1997.
[5]. 江诗锋与何振峰， 一种基于权重的時间序列相似性度量. 计算机应用与软件， 2010（9）： 第116-118页.
[6]. 邵校莎莎等， 不同粒度时间序列相似性度量. 计算机应用， 2011（12）： 第3285-3287页.
[7]. 孙达辰， 孙迎燕与周广群， 不等长子时间序列的相似性度量方法. 计算机时代， 2011（5）： 第17-20页.
[8]. 丁永伟等， 基于弧度距离的时间序列相似度量. 电子与信息学报， 2011（1）： 第122-128页.
[9]. 冯玉才等， 高效时序相似搜索技术. 计算机学报， 2009（11）： 第2107-2122页.
作者简介：孙建乐（1989-），男，河南，硕士研究生，主要研究方向：智能信息处理；廖清科（1990-），男，重庆，硕士研究生，主要研究方向：智能信息处理
【关键词】时间序列 数据挖掘 相似性 度量
时间序列的相似性度量是时间序列数据挖掘的基础问题。两条完全相同的时间序列几乎不存在，因此采用相似性（距离）度量来衡量时间序列之间的相似性。由于时间序列数据的复杂性，经常发生振幅平移和伸缩、线性漂移、不连续性、时间轴伸缩和弯曲等形变，为了最大程度地支持上述形变，并尽量提高相似性度量的时间效率，有一系列时间序列距离度量方法被提出和引入。
一、明科夫斯基距离
明科夫斯基（Minkowski）距离的优点在于简单直观，易于计算。设两长度相等的序列和，把它们看成n维空间中的两个坐标点，则两者之间的明科夫斯基距离[2]定义为：
当q=1时为曼哈顿（Manhattan）距离，
当q=2时为欧几里德（Euclidean）距离，
其中欧几里德距离是最常用也是应用最广泛的一种距离，其计算复杂度不高，与序列长度成线性关系，因而具有很好的伸缩性，序列长度的增加不会造成计算复杂度的迅速提高。并且欧氏距离满足距离三角不等式，在基于索引的查询时，可以利用距离三角不等式快速过滤一些不符合条件的索引节点。
二、动态时间弯曲距离
动态时间弯曲（DTW）距离在语音处理领域得到广泛的研究，Berndt和Clifford首次将DTW引入到数据挖掘领域[3]。与欧几里德距离相比，动态时间弯曲距离不要求两条时间序列点与点之间一一对应，允许序列点自我复制在进行对齐匹配。
动态时间弯曲（DTW）距离：设时间序列和，则X和Y的DTW距离定义为：
式中：表示序列点和之间的距离，可以根据情况选择不同的距离度量，通常使用明科夫斯基距离。
动态时间弯曲（DTW）距离的缺点是时间复杂度太高（），在子序列匹配时如不进行优化甚至为（，L为子序列的长度），不适用于海量时间序列的数据挖掘，需要专门采用某种技巧来减少其计算复杂度。
三、最长公共子串距离
当两条时间序列在大部分时间段具有相似的形态，而只在很短的时间范围内发生剧烈突变或间断时（即时间序列形变中的不连续性），欧氏距离和动态时间弯曲距离都忠实地记录了该形变的影响，这对于那些忽略时间序列不连续性的相似性度量问题而言是不适用的。
设时间序列和，它们满足以下条件的最长公共子序列分别为和：1）对任意，都满足；2）对任意，都有。那么时间序列和之间的相似度定义为：
最长公共字串（LCS）距离能克服时间序列的短期突变或间断带来的相似性问题，但无法处理振幅平移、时间轴伸缩和弯曲等形变。
四、结束语
本文对现有常用的时间序列相似性度量方法进行综述，介绍了各种度量方法的基本原理、优缺点，从而便于研究者对已有算法进行改进和研究新的时间序列相似性度量方法。
参考文献：
[1]. 毛红保等， 面向相似性查询的时间序列距离度量方法述评. 计算机工程与设计， 2010（19）： 第4221-4224页.
[2]. 孙即祥， 现代模式识别. 2002： 国防科技大学出版社.
[3]. Berndt， D.J. and J. Clifford， Using dynamic time warping to find patterns in time series. 1994.
[4]. Keogh， E. Fast similarity search in the presence of longitudinal scaling in
time series databases. in Tools with Artificial Intelligence， 1997. Proceedings.， Ninth IEEE International Conference on. 1997.
[5]. 江诗锋与何振峰， 一种基于权重的時间序列相似性度量. 计算机应用与软件， 2010（9）： 第116-118页.
[6]. 邵校莎莎等， 不同粒度时间序列相似性度量. 计算机应用， 2011（12）： 第3285-3287页.
[7]. 孙达辰， 孙迎燕与周广群， 不等长子时间序列的相似性度量方法. 计算机时代， 2011（5）： 第17-20页.
[8]. 丁永伟等， 基于弧度距离的时间序列相似度量. 电子与信息学报， 2011（1）： 第122-128页.
[9]. 冯玉才等， 高效时序相似搜索技术. 计算机学报， 2009（11）： 第2107-2122页.
作者简介：孙建乐（1989-），男，河南，硕士研究生，主要研究方向：智能信息处理；廖清科（1990-），男，重庆，硕士研究生，主要研究方向：智能信息处理