时间序列相似性度量的研究

陈为满 马佩勋

（长沙民政职业技术学院,湖南长沙 410004）

时间序列相似性度量的研究

陈为满 马佩勋

（长沙民政职业技术学院,湖南长沙 410004）

数据流上渐进、实时地进行子序列匹配成为一个极具价值和挑战性的问题。文中对已有的主要度量函数Lp-norms、DTW、LCSS、EDR和ERP等进行了分析和对比，从理论上归纳出其特性，对ERP算法进行了改进，大量的模拟和真实数据实验表明：改进的ERP算法在解决此类问题上具有高效性。

时间序列；相似性度量；数据流；子序列匹配

1.引言

随着计算机和网络技术的飞速发展，在与人们生活息息相关的各种领域中涌现出各类海量流数据，如每天股票市场的波动、气象研究中的气温、移动对象跟踪、某病人每个时刻心跳变化、从传感器网络获取各种数据等，对这些数据进行分析，可揭示事物变化、发展规律，为科学决策提供依据。对这类数据进行分析时存在着一个基本的问题：从数据流中找出与指定查询序列相似的序列，即子序列匹配（Subsequence Matching）。如何衡量两序列匹配即相似成为其中的关键问题。时间序列的相似性度量是时间序列数据挖掘研究中的一个重要问题，能反映数据中基本的相似性，这一点为时间序列的相似性检索、分类、预测等尤其可取。合理的相似性度量能提高数据挖掘的有效性和准确性。本文对已有的度量函数主要包括Lp-norms［1］、DTW［2,4,5,7］、最长公共字串（Longest Common Subsequence,LCSS）［3］、实序列编辑距离（Editdistance on real Sequence,EDR）和实补偿编辑距离（Edit Distance with Real enalty,ERP）［6］等进行了分析和比较，改进ERP算法，并通过大量的时间序列验证实验，评估了其效率，最后给出比较实验结果。……