基于时间序列线性拟合方法的时间序列层次聚类

王赫楠 燕燕 王甜宇 王和禹

(辽宁中医药大学信息工程学院,辽宁沈阳 110032)

基于时间序列线性拟合方法的时间序列层次聚类

王赫楠 燕燕 王甜宇 王和禹

(辽宁中医药大学信息工程学院,辽宁沈阳 110032)

本文利用一种有效的时间序列线性拟合方法。算法所选出的关键点是对时间序列的形态变化影响较大的点,将这些点依次连接实现时间序列的线性拟合。这种线性拟合算法在剔除了噪声的同时,能更精确的定位时间序列中的关键点。实验结果表明,该方法能更好的近似表示原时间序列。和已有的方法相比,该方法拟合后的时间序列和原时间序列之间的拟合误差更小。并且在该方法的基础上运用动态弯曲距离进行层次聚类得到了较好的结果。

时间序列 线性拟合 拟合误差 关键点 动态弯曲距离

1 引言

时间序列数据挖掘是数据挖掘的一个重要分支，广泛应用于医学，金融，工业等众多领域[1-2]。但由于时间序列有如下的特点，(1)时间序列的数据量巨大；(2)时间序列的噪声干扰严重；(3)时间序列的短期波动频繁。所以直接在原始时间序列上进行相似性查询[3]、分类聚类[4]、模式挖掘等操作很难得到满意的结果。因此许多研究者提出了时间序列的线性拟合表示方法，刻画时间序列主要形态而忽略那些微小的细节，从而在保持序列的主要特征不变的情况下达到简化计算量的目的。

本文详细分析了如何抽取时间序列中的关键点，利用了一种有效的线性拟合方法FPSegmentation(Feature Piecewise Segmentation)。利用非单调序列中极值点保持时间段阈值来选取关键点，这种线性拟合方法相对于以往的方法不仅将压缩率提升了，而且能更好的近似表示原时间序列，通过使用动态弯曲距离，对时间序列进行层次聚类得到了较好的结果。

2 基本概念

定义1：时间序列：时间序列是由记录值和记录时间组成的元素的有序集合，记为Q={q1=(p1，v1)，q2=(p2，v2)，…，qn=(pn，vn)}，元素qi=(pi，vi)表示时间序列在vi时刻的 记录值为pi。一般情况下，时间序列的采样间隔 v=vi-vi-1相等，可以看做v1=0，v=1，此时间序列记为时Q={q1，q2，…qn}。qi表示时间序列Q的第i个元素。

定义2：时间序列分段线性表示的拟合误差：时间序列Q={q1，q2，…qn}，通过线性分段拟合后得到的时间序列L(Q)={L(qi1，qi2)，L(qi3，qi4)，…，L(qik-1，qik)}，其中L表示连接两点的直线段。将L(Q)通过线性差值之后得到的时间序列记为Q’={q1’，q2’…，qn’}，那么该线性表示和原时间序列之间的拟合误差定义为

Fig.1 the effect of Hierarchical clustering图1 层次聚类的效果

3 特征点拟合法

特征点拟合法F P S e g m e n t a t i o n是对极值点拟合法IPSegmentation的改进。特征点拟合法所选出的关键点是对时间序列的形态变化影响较大的点，将这些点依次连接实现时间序列的线性拟合。具体实现原理如下所述：

FPSegmentation算法把时间按序列Q的起点和终点保留下来作为特征点，其它关键点需满足以下两点要求：①所选的特征值点必须是序列的极值点；②该极值点保持极值的时间段(即该点的前后极值点之间的时间段)与该序列长度的比值必须大于某个阈值M(参数M看作特征点的判断影响因子，M的取值和领域知识、序列长度以及实际的关注点有关，一般在0.01-0.1之间)。

4 基于重要点的动态弯曲距离

动态时间弯曲距离在语音处理领域得到广泛的研究，并且由Berndt和Clifford首次引入到数据挖掘领域。到现在，动态时间弯曲距离已经在医疗信号、生物学数据以及指纹识别等领域得到快速的发展。下面简要介绍动态时间弯曲距离的基本定义和常用的计算方法.

定义1.时间序列x和y之间的动态时间弯曲距离定义为：

动态时间弯曲距离可以用动态规划的方法计算，时间复杂度为O(|z|.|y|)。

我们在FPSegmentation的基础上，运用动态弯曲距离，对于时间序列进行层此聚类，得到了较好的结果，如第五节中实验所示。

5 实验结果及分析

我们使用数据集system control chart。该数据集包括600个样本，每个样本60个点，共6类，每个类都是100个样本。通过FPSegme ntation方法提取特征点，我们的聚类正确率可以达到70%以上。

图中有三种样本的时间序列分类明显错误，其它的时间序列分类结果较好，分类的正确率能够达到70%以上。

6 结语

特征点线性拟合法FPSegmentation能够更好的拟合原时间序列，拟合后的时间序列和原时间序列相比，拟合误差更小，压缩率更大。我们在FPSegmentation的基础上，利用动态弯曲距离，对拟合后的时间序列进行层次聚类得到了较好的结果。

[1]Park S,Kim S,Chu W. Segmentation-based approach for subsequence searchs in sequence databases[C]/.Proceedings of the 16th ACM Symposium on Applied Computing.New York: ACM Press,2001:248-252.

[2]肖辉,胡运发.基于分段时间弯曲距离的时间序列挖掘[J].计算机研究与发展.2005.42(1):72-78.

[3]Park K B,Fink E. Search for patterns in compressed time series[J]. International Journal of Image and Graphics,2002,2(1):89-106.

[4]D.J.Berndt,J.Clifford.Using dynamic time warping to find patterns in time series.Working Notes of the Knowledge Discovery in Databases Workshop,Seatle,WA,1994.