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

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

人工智能

0引言1时间序列分割

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

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

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

收稿日期:2009-02-26;修订日期:2009-10-20。

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

[5]

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

为k段(k<<n),然后对各段进行特征描述并记为S,,使得S,与S尽可能相似[6]。为什么要进行时间序列分割呢?主要原因是:

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

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

1.1时间序列线性划分

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

5782010,31(3)计算机工程与设计ComputerEngineeringandDesign

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

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

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

(3)自底向上

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

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

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

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

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

时间序列的分段线性表示(piecewiselinearreconstruction,PLR)的基本思想是利用线段来近似表示时间序列从而获取时间序列的变化趋势。直观上 …… 此处隐藏：9145字，全部文档内容请下载后查看。喜欢就下载吧 ……