基于时间序列相似性聚类的应用研究综述

陈湘涛，李明亮，陈玉娟：基于时间序列相似性聚类的应用研究综述2010,31(3) 577

人工智能

0引言1时间序列分割

为了对时间序列进行聚类，需要对时间序列进行分割，然

时间序列作为数据库中的一种数据形式，它广泛存在于各种大型的商业、医学、工程和社会科学等数据库中，形成规模庞大的时间序列数据库。与其它数据形式相比较，时序数据的特点有[1]：①有明显的时间先后。每个记录都必须有时间维按时间顺序进行排列，如果按关联规则的表示方法，所得的规则应体现出时间要素，一般应是先发生的事件导致后发生的事件，体现出时间关联，而不像市场货篮数据那样没有时间先后之分。②记录的属性类型可以分为3

种：一是布尔型(有或没有，0或1) ；二是类别型(月份差别，从事的职业类型等) ；三是数值型(年龄、气温等) 。③反映出序列特征。不论是上述哪种类型，应该是变量在某一时间段内连续(或采样) 的记录集，有一定的连贯性，一般有规律性可寻。随着数据库知识发现(knowledge discovery in data-base ，KDD ) 和模式识别等计算机技术的发展，出现了基于大量甚至海量数据库的数据挖掘技术，其研究目的是从大量时间序列数据中发现未知的重要模式和知识，并据此做出具有知识驱动的决策。

收稿日期：2009-02-26；修订日期：2009-10-20。

后对分割后的子序列进行聚类[2]、分类[3]、异常检测[4]、时间序列建模等

[5]

。时间序列的分割是指把长度为n 的时间序列S 分

为k 段(k

(1) 时间序列往往非常长，数据点的个数往往达到亿级，在理论上甚至是无限制的，并且在某个时间段它的特征是按照某种规律变化的，如果用每个数据点来描述往往会失去这些特征，并且有时也是不现实的；

(2) 时间序列在演变过程中，由于各种因素的影响，会表现某种局部特征，这些局部特征可以用某种模式来描述，这样我们可以忽略一些细节上变化，把握局部特征，这对时间序列数据挖掘有时不失为一种好的办法。可以极大提高数据挖掘的效率，并且不会丢失时间序列的重要特征，可以有效改善聚类结果。

1.1时间序列线性划分

线性划分作为一种简单而实用的算法在大量的序列分段

5782010,31(3) 计算机工程与设计Computer Engineering and Design

实际数据上，得到的分段数太多[14]。滑窗方法的时间复杂度为o (n*l) ，其中l 是分段的平均长度。

(2) 自顶向下(Top-Down )

首先得到计算时间序列的最粗糙的线性分段表示，即用一条线段来拟合时间序列。然后计算将该线段分割成两条拟合线段所能降低的拟合误差，选择最大拟合误差的分割点，重复上述过程，直到每个分段的误差都不超过某个指定阈值。在机器学习领域，Duda 和Harts 最早提出了该算法，称为“Iterative End-Points Fits ”。Park 等人改进T 该算法，将时间序列的极值点作为初始分割点，然后再使用经典Top-Down 算法。该算法可能会因为噪声的影响而降低性能。Lavrenko 等人在文本与序列的并发挖掘中，采用基于t-test 的方法作为分段算法停止的准则[13]自顶向下算法的时间复杂度很高，达到o (n 2) 。

(3) 自底向上

自底向上(Bottom-Up ) ：Bottom-up 算法是Top-Down 算法的逆过程。首先得到最精细的线性分段表示，既时间序列上相邻两点组成最小分段。然后计算合并两个相邻分段所产生的拟合误差，合并拟合误差最小的两个邻接分段，直到该拟合误差超过某个指定阈值。自底向上算法的时间复杂度为o (n*l) 。

在这3种序列线性划分算法中，SW 支持数据序列的在线划分，但划分效果欠佳，且无法保留历史信息：TD 和BU 算法尽管划分效果较好，但在实现过程中需要将所有序列数据读入内存，无法对实时序列数据进行在线分割。文献[10]在此基础上提出了一种基于层次聚类的时间序列在线分割算法(on-line segmentation algorithm for time series based on hierarchical clustering ，OSHC ) 。由于时间序列的有序性特征，直接利用传统的聚类算法划分数据序列没有意义，需要进行改进[15]。OSHC 算法在原有层次聚类算法的基础上考虑数据出现的时间先后关系，实现数据序列的线性划分。构造了一种存储划分信息的划分特征链表(segmentation feature list ，SF-List ) ，在扫描数据的同时保存划分序列所需信息，避免了在后续操作中反复扫描数据库，提高了运行速度，实现了历史记录的快速有效查询。实验结果表明该算法划分效果良好，运行时间与数据量呈线性关系，具有良好的可扩展性。与现有的序列划分算法SW 和TD 相比较，OSHC 算法更适用于动态递增数据流环境中的数据序列粗划分。

算法研究中得到的了广泛的应用[6]：①快速相似性查询；②对模糊查找、DTW 、SAX 等新的相似性度量函数提供了支持；③分别支持离散属性序列和连续属性序列；④对一些新的聚类分类算法也提供了支持；⑤支持奇异点检测。

逐段线性描述是一种最常用的时间序列分割方法。它使

用线性模型对序列进行分割与逐段描述，其中文献[7]对这类分割方法进行了详细的介绍。文献[8]提出了一种基于时态边缘算子的时间序列分割，文献[9]则研究了基于斜率提取边缘点的时间序列分割。

时间序列的分段线性表示(piecewise linear reconstruction ，PLR ) 的基本思想是利用线段来近似表示时间序列从而获取时间序列的变化趋势。直观上讲，PLR 表示方法就是用K 条首尾邻接的直线段来近似表示一条长度为n (n>K) 的时间序列。因此线段的数目决定了对原始时间序列的划分粒度。线段越多，线段平均长度就越短，划分越精细，越能反应时间序列的短期波动情况；线段越少，线段平均长度就越长，划分越粗略，越能反应时间序列的中长期趋势。线性分段算法的主要问题在于如何选择合适的线段数目以及如何选择合适的分段点？根据对这两个问题的不同解决方法，我们将线性分段算法分为以下两种类型[10]：

(1) 限制分段数K ：给定时间序列，产生的PLR 表示只包括[12]分别独立提出了时间序列分段聚K 个直线段。文献[11]、

集近似(piecewise aggregate approximation ，PAA ) 的PAA 方法。PAA 方法对时间序列等宽度分割，每个子段用时间序列在该子段上的平均值来表示。这种方法简单直观，能够支持任意长度的相似性查询和所有的Minkowski 度量和加权欧氏距离，而且能够用于索引提高查询的效率。Keogh 等人的实验表明将PAA 方法用于时间序列的索引，使得相似性查询的效率比DFT 表示方法提高了1-2个数量级[18]。

(2) 限制分段误差：不规定分段的数目，通过控制分段误差来选择合适的分段点。主要有两种限制分段误差的方式：①给定时间序列，产生的PLR 表示中每个分段的最大误差不超过某个用户指定的误差阈值max error ；②给定时间序列，产生的PLR 表示中所有分段的误差和不超过某个用户指定的误差阈值total error 。

根据分段误差控制的方法不同，文献[7]将这类线性分段算法分为以下3种：滑动窗口技术(sliding window ，SW ) 、自顶向下(top-down ，TD ) 和自底向上(bottom-up ，BU ) 。

(1) 滑动窗口(Sliding Window )

滑动窗口模型指分割以循环的方式进行，每次处理一个没有被最新分割包含的数据，分割不断的增长，直到超出某个界限为止。滑动窗口模型的效果通常与数据集本身有很大关系，而且滑动窗口大小本身也很难确定。

滑动窗口算法是从时间序列的第一个点开始一个新的分段，持续向后增长直到该分段与时间序列的拟合误差超出了某个指定阈值，结束该分段，然后以下一个序列点作为新分段的开始，不断重复上述过程直到时间序列末端。这类算法的优点是简单直观且支持在线分段，缺点是在某些情况下会得到很差的近似表示。Park 等人提出单调变化的分段算法，在光滑的数据集上取得了良好的效果，但是在具有大量噪音的

1.2时间窗子序列划分

时间窗子序列划分的结果直接会影响到时间序列数据挖

掘的效果。目前己有的时间序列聚类的方法，都采用相同时间窗进行子序列划分，然后对划分后的子序列进行相关分析。时间序列数据子序列划分的作用体现在：

(1) 模式聚类。对于一个时间序列变量，通过聚类算法，找到这个变量变化形态的模式类别，需要首先将这个时间序列变量按照一定的时间窗宽度和时间窗间隔，进行子序列划分，然后对划分得到的子序列进行模式聚类。

(2) 预测(如基于时间序列的神经网络预测，ARMA 模型预测，k 近邻时序预测等) 。建立根据x t-w-1，x t-w ，…,x t-1，预测x t 的模型，实际上是以w 为时间窗的宽度，对时间序列进行分割，并以该时间窗的前w-1个数，预测第w 个数。(3) 决策树分类和关联规则分析。时间序列决策树模型和

陈湘涛，李明亮，陈玉娟：基于时间序列相似性聚类的应用研究综述

关联规则模型的第一步就是要将时间序列离散化，而时间序列离散化实际上是通过聚类的方法，将序列离散成聚类得到的类别模式，因此聚类的过程也要涉及到对时间序列进行子序列划分。

(4) 相似性搜索。通过将时间序列进行子序列划分，对划分后得到的子序列进行符号化表示，然后通过搜索子序列的符号，来进行时间序列的相似性搜索。

目前时间序列聚类的方法都采用相同时间窗进行子序列划分，对划分后的子序列按照其相似性进行聚类。按照相同时间窗进行子序列划分，一方面子序列之间有大量的信息重复，造成信息冗余，如果子序列不重复，会使生成的子序列遗失关键信息点；另一方面不允许子序列形态在时间轴的收缩性。为了解决这些问题，文献[16]在BU 算法的基础上对其进行改进提出了一种新的事件序列生成算法，在此基础上提出了一种异时间窗子序列划分的方法，并给出了该方法的实现算法。按照异时间窗进行子序列划分：①避免了相同时间窗子序列划分造成的子序列之间大量的信息重复；②时间窗的单步事件滑移，子序列划分结果不会使生成的子序列遗失关键信息点；③得到的子序列长度不相同，允许了子序列形态在时间轴的收缩性，更加符合实际的情况。但是这种方法也存在着一定的缺陷：①比传统的子序列划分方法复杂，算法的复杂度高；②异时间窗子序列划分只能适用于高维时间序列，不适合于低维时间序列的子序列划分；③异时间窗子序列划分的结果是长度不同子序列，对于长度不同子序列的距离度量目前没有很成熟的算法。

2010,31(3) 579

son correlation 系数，要求时间序列都是独立的，而且所有的时间点是符合同一个概率分布的独立样本。Cosine distance 则将不同的时间序列描述为多维空间中的向量，并用他们之间的夹角来表示距离。

随着维度的增大，Lp 范式的性能会越来越差，这时点与点之间距离的对比性不复存在，也就是说一个点到它最近邻和最远邻的距离几乎相等，这种最近邻查询是不稳定的。杨凤召等在文献[19]提出了一种相似性度量函数：设X=(x 1, …, x d ) 和Y=(y 1, …, y d ) 是d 维空间中的两个点，Hsim (X, Y )

=

，该函数与Lp 范式的不同之处在于，在该函数中占

主导地位的是那些X 和Y 在其上差别较小(非常靠近) 的维，只要在某些维上X 和Y 的数据值比较接近，就会表现出一定的相似性。当然，他们的数值接近的维数越多，他们之间的相似程度也越高，这和人们判定物体相似的思维习惯也是基本一致。但是该度量函数仅仅能够处理数值数据，对混合属性数据处理就显得无能为力。

对于大量的长度不一的时序数据，基于形状的相似度度量效果往往不好，这时，就得考虑基于特征或者基于模型的相似度。

2.2基于特征的相似度

抽取特征并比较特征集合的相似度计算方法和具体的应

用领域有很大的关系。对于一些具有某些重要特征的时序数据，选取合适的特征来表示可以收到很好的效果。除了人工抽取比较重要的特征以外，取DFT 或者DWT 后得到的最大的系数作为特征，用来表示整个数据。文献[20]中提到了一种通过对时间点加上偏向最近时间的权重，从而自动选取独立于数据的系数作为特征的方法。从整体来说，目前，基于特征的相似度度量还是一个有很强的领域相关性，需要较多人为干预的过程。

2相似性度量

相似性和距离是相对的两个概念，距离是相似性的外在表现，相似性是距离度量的目的，是用来衡量两个(通常是两个，也有可能多个) 数据或实例之间关系的标准。在一定意义上，相似性和距离的表示能力是等价的，他们分别适用于一定的环境，也可以通过一定的方法相互转换。相似度度量问题是数据挖掘中的一个重要问题，是整个数据挖掘过程的基础，相似度度量的好坏决定着数据挖掘的效果[17]。

对于数值时间序列而言，相似度的度量可以分为以下几类：基于形状的(shape-based ) 相似度、基于特征的(feature-base ) 相似度、基于模型的(model-based ) 相似度、基于数据压缩的(compression-based ) 相似度[18]。

2.3基于模型的相似度

与基于特征的相似度相比，基于模型的相似度有一个很

大的优势，那就是基于模型来计算相似度可以将预先得到的关于数据产生的知识结合进来。通常计算相似度时，对每一个时间序列建模，并用对某个序列所建模型生成另一序列的概率值来衡量这两个序列间的相似度。常用的模型有的HMM ，AMRA 等，近年来对这些模型本身及使用方法的研究和改进也是一个重要的研究课题。

基于模型的方法往往需要较长的时间序列来完成较好的参数估计，对于较短的、采样不规则的时间序列，文献[22]提供了一种将形状和模型相结合的方法。文献[22]则综合了计量模型的参数估计和聚类的非参无监督分类的优点，提出了一种适合处理不等间隔时间序列的基于倒谱距离测度和自回归条件持续期(ACD ) 模型的聚类方法。这些混合模型的方法在某些应用中会收到意想不到的效果。

2.1

基于形状的相似度

欧式距离(Euclidean distance ) 是对于数值的时间序列而言

最简单却应用最广泛的基于形状的距离。此外Manhattan 的p=1和Maximum 的p=∞时的Lp 范式也是常用的距离度量。但是，直接使用这种度量也有一些共同的缺点，这些距离在对数据进行缩放或转换时容易受到影响，而且距离受噪声、特殊值以及数据是否归一化的影响也较大。因此人们开始寻找适当的转换使得这些Lp 距离能够在以上这些变化发生时保持不变，对于不同的应用来说，找到一个有意义的转换方式也是一个很重要的课题[18]。

跟Lp 距离相关的有另外两个距离定义：Correlation 和Co-sine distance 。Correlation 的定义是基于衡量线性相关性的Pear-

2.4基于压缩的相似度

基于压缩的时序数据相似度来自于生物信息学和计算理

论研究的一些结果，是一个较新的想法[18]。(compression-based dissimilarity measure ，CDM ) 的基本思想认为对相似数据的连接

5802010,31(3) 计算机工程与设计Computer Engineering and Design

4

结束语

综合国内外文献可以发现：①现在国内外对时间序列的研究尽管已经相当成熟，尤其针对低维时间序列有许多比较成熟的算法，但对于高维混合属性时间序列，由于没有一个比较成熟的相似性度量函数对此研究还不过成熟。因此研究更有效的成熟的针对高维混合属性的相似性度量函数是亟待解决的问题，也成为现有研究的一个热点；②另外在时间序列划分过程中现在一般都用等长划分，往往会丢失许多重要特征点，对挖掘结果产生一定的影响，因此不等长划分往往更符合实际，但是对于不等长序列现在还没有一个比较成熟的相似性度量函数，这也成为一个研究方向。

和压缩，应该得到比在相差较大的数据上做同样操作更高的压缩比率。Kolmogorov 复杂度是指生成所得数据的最短程序长度。基于条件Kolmogorov 复杂度，Keogh 等人定义了CDM ，并说明了其在聚类、分类、异常检测等工作上的优越性能。

[23]

2.5符号时序数据(symbolic time-series ) 的相似度

对于符号时序数据，可直接通过对符号序列的比较来计

算两个时间序列的距离，被称为Proximity-based method 。较典型的例子是计算编辑距离(edit distance ) 的方法，定义两个时间序列的距离为将其中一个转换为另一个所需要的最少转换数。

此外对符号时序数据也可以使用上文所提到的基于特征、基于模型或者基于压缩的方法，只是根据方法类型不同需要在符号数据和数值数据之间做一些转换。

2.6综合分析

通过实验发现这几类相似度各有优势，具有针对性，它们

参考文献:

[1][2][3][4]

虞健飞, 朱家元, 张恒喜. 相似时间序列挖掘方法[J ]. 计算机仿真,2003,20(9) :7-9.

李斌, 谭立湘, 章劲松, 等. 面向数据挖掘的时间序列符号化方法研究[J ]. 电路与系统学报,2000,5(2) :9-14.

覃征, 李爱国. 时间序列数据的稳健最优分割[J ]. 西安交通大学学报,2003,37(4) :338-342.

Hanlon B,Forbes C.Model selection criteria for segmented time series from a Bayesian approach to information compression [R ]. Monash University,2002. [5][6]

Hawkins D M.Fitting multiple change-point models to data [J ]. Computational Statistic &Data Analysis,2008,37(3) :323-341.Keogh E,Kasetty S.On the need for time series data mining be-nchmarks:Asurvey and empirical demonstration [C ]. Edmonton, Alberta,Canada:Proceedingsof the 8th ACM SIGKDD Interna-tional Conference on Knowledge Discovery and Data Mining, 2002:102-111.[7]

Geetika Tewari,John Snyder,Pedro V Sander,et al.Signal-specia-lized parameterization for piecewise linear reconstruction [C ]. Eurographics Symposium on Geometry Processing,2004:39-52.[8][9]

肖辉, 马海兵, 龚薇. 基于时态边缘算子的时间序列分段线性表示[J ]. 计算机工程与应用,2008,44(19) :156-159.

詹艳艳, 徐荣聪, 陈晓云. 基于斜率提取边缘点的时间序列分段线性表示方法[J ]. 计算机科学,2006,33(11) :139-142.

[10]杜奕, 卢德唐, 李道伦, 等. 基于层次聚类的时间序列在线划分算

法[J ]. 模式识别与人工智能,2007,3(20) :23-27.

[11]Keogh E,Chakrabarti K,Pazzani M J,et al.Dimensionality reduc-tion for fast similarity search in large time series databases [J ]. Knowledge and Information Systems,2008,3(3) :263-286.[12]YiB K,Faloustsos C.Fast time sequence indexing for arbitrary Lp

表1

相似度形状特征模型压缩

符号

聚类性能差好好较好较好

噪声干扰易受不易受同上同上同上

的性能比较如表1所示。

3聚类相关研究

“物以类聚，人以群分”，聚类就是根绝某种规则把集合

中的元素分成特定的几类，并且类内元素之间的相似度尽可能大，类与雷之间的相似度尽可能小，根据聚类对象可以把时间序列聚类分为以下几种：以一组时间序列集合为聚类对象进行聚类，可以称为全序列聚类(whole series clustering ) ；对某一个时间序列的若干分割即子序列进行聚类，称为子序列聚类(subseries clustering ) ；对某一个时间序列中的若干时间点进行聚类，称为时间点聚类(time point clustering ) [18]。

全序列聚类主要分为相似性度量和聚类算法选择两个方面。但由于现在的时间序列数据比较大造成维度比较高，如果直接对时间序列进行距离度量往往会影响效率，所以一般要对时间序列进行预处理，例如时间序列符号化等，但是这对距离度量有更高的要求。欧式距离和DTW 距离是常用的距离表示。常用的聚类算法有k 均值，层次聚类等。如何更合适的定义距离，更有效的利用时序数据表示中的信息，使得聚类更能反映数据的本质情况是这一方向研究的重点问题之一。文献[23]中就是一种利用基于压缩的距离表示进行聚类的例子。

子序列聚类是根据特征模式对时间序列进行分割，然后用特定的聚类算法对分割得到的子序列进行聚类。由于是在同一个时间序列的内部进行聚类，往往会采用滑动窗口的方法，因而窗口的大小以及窗口之间间隔的大小选择问题，对这种聚类的结果有着非常大的影响。但是这种方法仅限于处理等长的子序列，而对于不等长的子序列的聚类将是一个新的课题。

时间点聚类就是把时间序列中的每个数据点作为聚类对象，分成几个类别，然后找出某种联系，形成特定模式，同时时间点聚类可以用来检测出离群点，发现异常。

相似性度量函数的性能比较

处理高维数据

较差一般同上同上

同上

人为干预较少较多较少同上同上

时间复杂度O (n ) O (m*n)

2

序列长度等长无要求同上同上同上

代表函数欧式距离DTW HMM CDM ED

O (K *n) O (n 2) O (K*n)

2

陈湘涛，李明亮，陈玉娟：基于时间序列相似性聚类的应用研究综述

norms [C ].Proceeding of the 26th International Conference on Very Large Databases. San Francisco:Morgan Kautmann Pub-lishers Inc,2002:385-394.

[13]Lavrenko V ,Schmill M,Lawrie D,et al.Mining of concurrent text

and time series [C ]. Boston, MA:Proceedings of the 6th ACM SIGKDD Int'1Conference on Knowledge Discovery and Data Mining Workshop on Text Mining,2002:37-44.

[14]Park S,Kim SW,Cho J S,et al. Prefix querying:an approach for

effective subsequence matching under time warping in sequence databases [C ].Proceedings of the l0th International Conference on Information and Knowledge Management.New York:ACMPress,2002:255-262.

[15]吴江琴, 高文. 时间序列聚类算法及其在手势识别中的应用[J ].

模式识别与人工智能,2005,18(1) :1-5.

[16]国宏伟, 高学东, 王宏. 基于异时间窗划分的时间序列聚类[J ]. 计

算机工程,2007,33(21) :3-5.

[17]黄书剑. 时序数据上的数据挖掘[J ]. 软件学报,2004,15(1) :1-7.[18]Keogh E,Chu S,Hart D,et al.Segmenting time-series:A survey

2010,31(3) 581

and novel approach [C ].Last M,Kandel A,Bunke H,et al.Data Mining in Time-series Databases,World Scientific,2004:1-22.[19]杨风召, 朱扬勇. 一种有效的量化交易数据相似性搜索方法[J ].

计算机研究与发展,2004,31(2) :361-368.

[20]Zhao Y ,Zhang C,Zhang S.A recent-biased dimension reduction

technique for time-series data [C ].Ho T B,Cheung D,Liu H,et al. Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining.Springer, 2005:75-757.

[22]Gaffney S, Smyth P. Curve clustering with random effects re-gression mixtures [C ].Bishop C M,Frey B J.Proceedings of the 9th International Workshop on Artificial Intelligence and Statis-tics,2003.

[22]张小涛, 李翠玉. 基于模型的不等间隔时间序列聚类算法研究

[J ]. 计算机工程与应用,2008,44(6) :166-168.

[23]Keogh E,Lonardi S,Ratanamahatana C.Towards parameter-free

data mining [C ]. Kim W, Kohavi R, Gehrke J, et al.Proceedings of the 10th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining.ACM Press,2004:206-215.

(上接第576页)

4结束语

本文基于双树复小波变换、PCA 变换和局部累加梯度提

出了一种新的图像融合算法。PCA 变换被用来判断各源图像对融合结果的重要程度。仿真结果表明本文的融合算法要优于其它几种融合算法。当不同源图像经小波变换后的系数比较接近时，使用PCA 变换进行图像融合会出现区域色斑等现象，从而降低图像的视觉效果。在以后的研究中，将考虑用相对主元分析RPCA 变换来处理这些问题，RPCA 变换是故障检测，图像分割等邻域的有效工具。

参考文献:

[1][2]

毛士艺, 赵巍. 多传感器图像融合技术综述[J ]. 北京航空航天大学学报,2002,28(5) :512-517.

Frechette S,Ingle V K.Gradient based multifocus video image fusion [C ]. IEEE Conference on Advanced Video and Signal Based Surveillance,2005:486-492.[3]

Petrovi