论文导读:：时间序列是按时间顺序排列的一系列观测数据。基于形状的相似度度量效果往往不好。基于时间序列趋势转折点的分段线性表示。本文提出了不等长子时间序列的相似性度量方法。
关键词：时间序列，相似度，分段线性表示，不等长子时间序列
0引言
时间序列是按时间顺序排列的一系列观测数据，其观测值按固定的时间间隔采样。时间序列广泛存在于商业、经济、科学工程和社会科学等领域，例如：股票价格数据、销售数据、图像数据、影像数据、手写体数据、脑扫描数据等都可以看作是时间序列数据[1]。这些数据中隐藏着大量重要的信息，反映的大都是某个待观察过程在一定时期内的状态或表现[2]。
时间序列的相似性度量是衡量两个时间序列的相似程度的方法；它是时间序列分类、聚类、异常发现等诸多数据挖掘问题的基础，也是时间序列挖掘的核心问题之一。[3]相似性度量的好坏决定着挖掘的效果。[2]对于数值型的时序序列，有以下几种相似度的度量：基于形状的相似度、基于压缩数据的相似度、基于特征的相似度和基于模型的相似度。[4]对于大量的长度不一的时序数据，基于形状的相似度度量效果往往不好，这时，就得考虑基于特征或者基于模型的相似度。[5]基于特征的相似度计算先要从时间序列中提取特征，将时间序列变换到特征空间，采用特征空间的特征模式来表示原始时间序列。[6]。从整体来说，目前，基于特征的相似度度量还是一个有很强的领域相关性，需要较多人为干预的过程。[5]与基于特征的相似度相比分段线性表示，基于模型的相似度有一个很大的优势，那就是基于模型来计算相似度可以将预先得到的关于数据产生的知识结合进来论文格式。通常计算相似度时，对每一个时间序列建模，并用对某个序列所建模型生成另一序列的概率值来衡量这两个序列间的相似度。基于模型的方法往往需要较长的时间序列来完成较好的参数估计。[5]
对于长度不同子序列的距离度量，目前没有很成熟的算法。[5]对于来源于同一序列中的各个子序列，具有不相同的长度，可能存在在时间轴和幅值相差很大、但变化趋势却很相似的序列，为了有效地计算来源于同一序列中的各个子序列的相似度，本文提出了不等长子时间序列的相似性度量方法。
1不等长子时间序列的相似性度量方法
本方法将参与相似度计算的时间序列先进行有效分段，使每一段具有相对独立的变化趋势，然后对相对段进行相减，并取绝对值，经过以上计算后的多个绝对值相加的和就是最后得到的相似度。不具有相同分段数目的时间序列被认为是不相似的，将不参与计算。
为了对时间序列进行有效分段，本文采为文献[7]中的方法。
1.1 基于时间序列趋势转折点的分段线性表示
在文献【7】中，提出了一种有效地提取序列中的趋势和压缩原始数据的方法，这种方法通过计算时间序列中波动幅度达到一定程度的极值点和波动幅度达到一定程度的相邻点非极值点来确定每一个具有相对独立变化趋势的分段端点，具有较高的精确性和高效、实现方法简便、效果直观、适应性好的优点。
算法步骤：
步骤1：对原始时间序列进行扫描，在这一过程中，记录原始时间序列的趋势转折点，即波动幅度达到一定程度的极值点和短时间大波动的非极值数据点。
步骤2：对于每一对趋势转折点进行直线插补，以这样的直线代替原来的曲线数据。
1.2不等长子时间序列的相似性度量方法
在时间序列中，序列的变化趋势主要有以下几种：上升趋势、下降趋势、平稳趋势。如图1所示。
图1趋势变化图
Fig.1Fluctuation of tendency
图中AB子序列的变化是一个上升趋势，BC子序列的变化是一个下降趋势，DE子序列的变化是一个平稳趋势，也可以是以上子相邻子序列的组合，构成其他的变化趋势。
对于两段只有上升或下降趋势的序列可以只比较它的斜率，计算公式：|k1-k’1|；
对于两段一个上升一个下降趋势的序列，可以比较两个趋势段上的斜率分段线性表示，计算公式：|k1-k’1|+|k2-k’2|；
对于两段一个上升一个下降一个上升趋势的序列，可以比较三个趋势段上的斜率，计算公式：|k1-k’1|+|k2-k’2|+|k3-k’3|；
对于参与比较的两条时间序列，使用相同的时间窗长度进行划分，时间窗长度越小，则对原序列分的越细，比较结果越准确，从而可以从多个角度反映序列的相似程度。当划分完后，一段有剩余，则将前面相同段数的相似度结果与剩余的时间序列长度相加作为最后的相似度结果。
算法 不等长子时间序列的相似性度量方法
输入 来自于同一时间序列的两段子序列S=<S1,S2>
输出 这两两段子序列的相似度
算法步骤：
步骤1 采用文献【7】中提出的方法，对输入数据进行分段线性表示，得到S1_TPLR和S2_TPLR；
步骤２ 计算每一分段的斜率，保存到S1_K和S2_K中，如果分段数相等，对应段的斜率相减，并对第一个斜率相减求绝对值，将这些绝对值相加，得到SK；如果分段数不相等，以大的分段数为基础，从第一段开始，对应段的斜率相减，并对第一个斜率相减求绝对值，将这些绝对值相加，得到SK，依次向后移动，得到多个SK，取这些SK中最小的作为最后SK）。
步骤３ 如果S1_TPLR和S2_TPLR的分段数不同，则计算出没有参与步骤２的分段在原时间序列的长度SL，否则SL为零；
步骤４ 将SK与SL相加得到最后的相似度。
2实验
2.1实验数据
人造数据：对于变化趋势完全一样、长度不同的人造时间序列数据分段线性表示，如下图所示：
图2人造时间序列图
Fig.2 Man-madetime series
经过分段后，结果如下图所示：
图3人造时间序列的趋势变化
Fig.3 Fluctuation tendency of Man-made time series
真实数据：选择来自不同领域的时间序列数据集：油田测井数据中的自然伽码数据GR，海洋温度数据Ocean。各时间序列的变化图如下：
图3 GR原序列曲线
Fig.3 Curve of Original GR Series
图4Ocean原序列曲线
Fig.4 Curve of Original Ocean Series
为了比较这两个数据集在变化趋势上的差别，分别对这两个数据集进行规范化，将原时间序列规范到[0，1]之间，规范化公式如下：
对于规范化后的时间序列，各时间序列的变化图如下：
图5 规范化后GR序列曲线
Fig.5 normative GR Series
图6 规范化后Ocean序列曲线
Fig.6 normative Ocean Series
对于这两条时间序列数据进行规范化，发现它们之间有很大的差异，作为实验数据具有代表性。
2.2实验方法、结果及分析
对于长度不同子序列的距离度量，目前没有很成熟的算法。[5]这里采用人造数据和真实数作为实验数据，从相似度的计算精度和计算效率两个方面分析本文所提出算法的性能。
（1）对人造数据的实验
为了验证本文算法的效果，将对人造时间序列数据分别在时间轴方向进行放大、在幅值上拉长、同时在时间轴方向和幅值上放大，得到不同的三条时间序列数据，这三条时间序列为AS1，AS2，AS3论文格式。利用本文提出的方法都能计算出它们的相似度，并用数值对它们在相似程度上加以区分，算法的效率由两部分决定，一是参与计算的时间序列的长度，因为它要经过分段线性表示算法；二是分段后各个段的分段数，分段数越多，计算的内容就相对多一些，但计算结果越精确。
（2）对真实数据的实验（对于两条不同的时间序列进行下列实验，并分析结果）
对于时间序列GR，随机选取其中的某一段Sub，分别对原时间序列GR和子时间序列Sub，在相同的参数下进行“基于时间序列趋势转折点的分段线性表示”，计算出这两条时间序列各个段的斜率分段线性表示，以分段后Sub的斜率组合Sub_K为参考，在分段后的GR序列中寻找与Sub_K相类似的组合。
对于时间序列GR分段后的曲线图如下：
图7Ocean的趋势变化
Fig.7 Fluctuation tendencyof Ocean Series
图中符号o为每一个分段点的端点，相邻两个o之间为一个分段，每一个分段代表了一个变化趋势。
随机选取其中的某一段Sub，分段后的曲线如下图所示：
图8Sub的趋势变化
Fig.8 Fluctuation tendencyof Sub Series
经过计算后得到的典型曲线如下所示：
图9相似子序列
Fig.9 Similar Sub-Series
最相似的两条子序列为S1_A到S1_B之间的线段和S2_A到S2_B之间的线段，这两条子序列与Sub具有完全相同的变化趋势，它们的相似度都接近于零。
本实验的实验环境：MatLab7.0，WinXP；系统参数：Pentium(R)4 CPU3.0、内存512M；所需要的时间为76秒。
在海洋温度数据Ocean时间序列数据上进行同样的实验，也获得了良好的效果。所需要的时间为97秒，原因在于，在同样的参数下，所得到的分段数较多，从而进行计算的数据就比较多。
结束语
时间序列中不等长子序列的相似性度量是时间序列挖掘任务中的一个研究热点。本文以同一时间序列中，具有不同长度的子序列数据如何进行相似度计算为研究内容，提出了不等长子时间序列的相似性度量方法。本方法在分段计算每一相对独立子序列斜率的基础之上，能够有效地获得每一段的变化趋势，进而可以不受时间序列长度的影响而完成相似度计算。在不同的数据集上进行实验，本方法都获得了良好的效果，验证了本方法具快速、准确、不受时间序列长度影响的特点。
参考文献
[1] 贾澎涛, 林卫, 何华灿. 时间序列的自适应约束分段线性表示[J]. 计算机工程与应用. 2008.44(5):10-13.
[2]黄书剑. 时序数据上的数据挖掘[J]. 软件学报. 2004.15(01):1-7.
[3]刘懿，鲍德沛，杨泽红，赵雁南，贾培发，王家钦，新型时间序列相似性度量方法研究[J] 计算机应用研究. 2007（24）.5:112-114.
[4]Keogh E, Chu S,Har Det al. Segmenting time-series: A survey and approach[C]. Last M, Kandel A,BunkeH, et al. Data Mining in Time-Series Databases, World Scientific, 2004:1:22.
[5] 陈湘涛, 李明亮, 陈玉娟.基于时间序列相似性聚类的应用研究综述[J]. 计算机工程与设计.2010.31(3):577-581.
[6]杜奕. 时间序列挖掘相关算法研究及应用[D]. 中国科学技术大学博士学位论文.2007:3
[7] 尚福华，孙达辰. 基于时间序列趋势转折点的分段线性表示[J]. 计算机应用研究. 2010.27(6):2075-2092.
[8]潘定,沈钧毅.时态数据挖掘的相似性发现技术[J].软件学报. 2007.18(2): 246-258.
[9]潘定.持续时态数据挖掘及其实现机制[M]. 北京:经济科学出版社. 2008.3.
[10]毛红保，冯卉，杨建华,刘亚军.面向相似性查询的时间序列距离度量方法述评[J]. 计算机工程与设计. 2010.31(19):4221-4224.
[11]江诗锋,何振峰.一种基于权重的时间序列相似性度量[J]. 计算机应用与软件.2010.27(9):116-118.
[12]毛红保，张凤鸣，冯卉，吕慧刚.基于参数重要度的多元时间序列相似性查询[J]. 计算机工程.2009.35(24):54-56.
|
