不等长子时间序列的相似性度量方法-分段线性表示.docx

?

?

不等长子时间序列的相似性度量方法

分段线性表示

?

?

论文导读:：时间序列是按时间顺序排列的一系列观测数据。基于形状的相似度度量效果往往不好。基于时间序列趋势转折点的分段线性表示。本文提出了不等长子时间序列的相似性度量方法。

关键词：时间序列，相似度，分段线性表示，不等长子时间序列

?

0引言

时间序列是按时间顺序排列的一系列观测数据，其观测值按固定的时间间隔采样。时间序列广泛存在于商业、经济、科学工程和社会科学等领域，例如：股票价格数据、销售数据、图像数据、影像数据、手写体数据、脑扫描数据等都可以看作是时间序列数据[1]。这些数据中隐藏着大量重要的信息，反映的大都是某个待观察过程在一定时期内的状态或表现[2]。

时间序列的相似性度量是衡量两个时间序列的相似程度的方法；它是时间序列分类、聚类、异常发现等诸多数据挖掘问题的基础，也是时间序列挖掘的核心问题之一。[3]相似性度量的好坏决定着挖掘的效果。[2]对于数值型的时序序列，有以下几种相似度的度量：基于形状的相似度、基于压缩数据的相似度、基于特征的相似度和基于模型的相似度。[4]对于大量的长度不一的时序数据，基于形状的相似度度量效果往往不好，这时，就得考虑基于特征或者基于模型的相似度。[5]基于特征的相似度计算先要从时间序列中提取特征，将时间序列变换到特征空间，采用特征空间的特征模式来表示原始时间序列。[6]。从整体来说，目前，基于特征的相似度度量还是一个有很强的领域相关性，需要较多人为干预的过程。[5]与基于特征的相似度相比分段线性表示，基于模型的相似度有一个很大的优势，那就是基于模型来计算相似度可以将预先得到的关于数据产生的知识结合进来论文格式。通常计算相似度时，对每一个时间序列建模，并用对某个序列所建模型生成另一序列的概率值来衡量这两个序列间的相似度。基于模型的方法往往需要较长的时间序列来完成较好的参数估计。[5]

对于长度不同子序列的距离度量，目前没有很成熟的算法。[5]对于来源于同一序列中的各个子序列，具有不相同的长度，可能存在在时间轴和幅值相差很大、但变化趋势却很相似的序列，为了有效地计算来源于同一序列中的各个子序列的相似度，本文提出了不等长子时间序列的相似性度量方法。

1不等长子时间序列的相似性度量方法

本方法将参与相似度计算的时间序列先进行有效分段，使每一段具有相对独立的变化趋势，然后对相对段进行相减，并取绝对值，经过以上计算后的多个绝对值相加的和就是最后得到的相似度。不具有相同分段数目的时间序列被认为是不相似的，将不参与计算。

为了对时间序列进行有效分段，本文采为文献[7]中的方法。

1.1基于时间序列趋势转折点的分段线性表示

在文献【7】中，提出了一种有效地提取序列中的趋势和压缩原始数据的方法，这种方法通过计算时间序列中波动幅度达到一定程度的极值点和波动幅度达到一定程度的相邻点非极值点来确定每一个具有相对独立变化趋势的分段端点，具有较高的精确性和高效、实现方法简便、效果直观、适应性好的优点。

算法步骤：

步骤1：对原始时间序列进行扫描，在这一过程中，记录原始时间序列的趋势转折点，即波动幅度达到一定程度的极值点和短时间大波动的非极值数据点。

步骤2：对于每一对趋势转折点进行直线插补，以这样的直线代替原来的曲线数据。

1.2不等长子时间序列的相似性度量方法

在时间序列中，序列的变化趋势主要有以下几种：上升趋势、下降趋势、平稳趋势。如图1所示。

图1趋势变化图

Fig.1Fluctuationoftendency

图中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中，如果分段数相等