（计算机软件与理论专业论文）时间序列的符号化及时序关联规则挖掘.pdf

时间序列的符号化及时序关联圭! l ! 则挖掘 摘要 本文的研究是对时间序列进行符号化和时序关联规则挖掘。首先对时序 数据在国内外的研究情况进行了总结。然后详细介绍了符号化中用到的主要 技术：动态时间弯曲( d t w ) 和分割技术。在介绍d t w 的相关技术是提出了一种 启发式的d t w 算法。在介绍时序数据的分割技术时提出了一种用一个合适长 度的、基于时序数据形状( s h a p e ) 信息的、等长分割时间序列的方法：基于 统计的自适应分割方法a s a b s ( s e l f - a d a p t i v es e g m e n t i n ga l g o r i t h mb a s e d o ns t a t i s t i c ) 。为了找出窗口的一个合适移动长度，在传统方法的基础上 提出了两种计算滑动窗口移动长度的方法。通过一种改进的提高k 一均值性能 的方法对这些分割后子序列进行聚类并对其符号化。为了寻找隐藏的时序模 式，在生成2 一项集的时候，提出了一种新颖的方法，在寻找频繁2 项集的时 候提出了一种用最小置信度代替最小支持度，并且把找频繁2 项集转化为频 繁i 项集的寻找，对最后生成的时序关联规则用j - m e a s u r e 度量进行了排序。 最后对本文的结果进行了实验分析，提出了和本文相关的未来的研究方向。 关键字：时间序列时间序列符号化滑动窗口相似性聚类动态时间弯曲 k 一均值时序模式 时间序列的符号化及时序关联剐则挖掘 a b s t r a c t i nt h i st h e s i s ，o u rr e s e a r c h e sa r e s y m b o l i n gt i m e s e r i e sa n d m i n i n gt e m p o r a l a s s o c i a t i o nr u l e s a tf i r s t ，w ei n t r o d u c et h er e s e a r c ho ft h et i m es e r i e si n s u m m a r y t h e nw e i n t r o d u c et h ep r i m a r y t e c h i n i q u e si nd e t a i lt h a ts y m b o lt i m es e r i e s ， s e g m e n t a t i o n ，a n dd y m a t i c t i m ew a r p i n g w ed e v e l o pah e u r i s t i cd t w a l g o r i t h ma n d as e g m e n t i n ga l g o r i t h m ，s e l f - a d a p t i v es e g m e n t i n g a l g o r i t h mb a s e do ns t a t i s t i c ， w h i c hc a ns e g m e n tt h et i m es e r i e sw i t la r i g h tl e n g t h a n dw h i c h i sb a s e d o nt h es h a p e o ft h et i m es e r i e sa n dt h es u b s e q u e n c e sa l ee q u a l p r o p o s i n gt w om e t h o d sb a s e do n t h ec l a s s i c a la p p r o a c ht of i n do u taa p p r o p r i a t ev a l u eo f m o v i n gl e n g t h w eu s et h e d e v e l o p e dk - m e a r k sa l g o r i t h mt oc l u s t e rt h es u b s e q u e n c e s ，a n du s i n gt h er e s u l t st o s y m b o l t h et i m es e r i e s t od i s c o v e r yt h el a t e n t t e m p o r a l 户t t e r n s ，w ep r o p o s i n g an o v e l m e t h o d sw h e n g e n e r a t i n gt h e2 - i t e ms e t s w er e p l a c et h em i n i m a ls u r p o r tb ym i n i m a l c o n f i d e n c ea n dt r a n s l a t ef i n d i n gf r e q u e n t2 - i t e ms e t si n t o f i n d i n gf r e q u e n t 1 - i t e m s e t s ，w es o r tt h et e m p o r a la s s o c i a t i o n a lr u l e sw h i c hw ef i n d e do u tw i mj - m e a s u r e a t l a s t ，w eg i v et h ee x p e r i m e n t a lr e s u l t sa n d p r o p o s e t h er e s e a r c hi nf u t u r e k e y w o r d s ：t i m es e r i e s ，s y m b o l i n gt i m e s e r i e s ，s l i d i n gw i n d o w , s i m i l a r i t y ， c l u s t e r i n g ，d y n a m i ct i m ew a r p i n g ，k - m e a n s ，t e m p o r a lp a t t e r n s i j 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行 研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容 外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标 明。 本声明的法律责任由本人承担。 论文作者签名：雄 日期：巡点皇岁 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：啡 导师签名： 越日期寝鲻& ； i 时间序列的符号化及时序关联规则挖掘 引言 在现实生活中，大量数据集之中的数据都带有时间特征时态数据随处 可见遍及经济、气象、通信、医疗等等多个领域、股市每日( 或月) 指数、交 换机的每小时的业务量、某一患者的脑电波、心电图$ 口w e b 页的日访问量， 这些都是比较常见的例子。对这些时态数据进行分析，从中获取蕴含的系统 演化规律从而完成对系统的未来行为的预测，具有重要的价值和意义。 时态数据挖掘是数据挖掘研究的一个重要的组成部分，在时态数据挖掘 的过程中必须考虑数据集之中数据间存在着的时间关系时态数据挖掘的研 究是数据挖掘的较新的一个方向。目前国际上对于时态数据挖掘的研究已经 成为一个新的热点，但国内的研究还处于开始阶段。 现在数学上也在研究时间序列，不过在数学上用的是基于模型的方法， 像a r 序列、m a 序列、a r m a 序列、a r i m a 序列和基于h 哪模型的时间序列的研究， 先证明所研究的时间序列是符合哪种模型，然后利用这些模型的性质对时间 序列进行分类和预测，有时还使用线形回归的方法对时间序列进行预测。 时间序列模式挖掘是时序数据挖掘的一个重要方向，而在时态模式挖据 方面，针对数值型时态数据的研究较少，绝大多数是针对事件型和事务型的。 要想使用大多数的算法来进行时序模式挖掘，必须要对其符号化。在时间序 列符号化方面现在有很多方法，传统的方法是用变化率的方法，首先找出时 间序列中变化率的最大最小值，然后根据自己的意愿想把时间序列用多少个 不同的字符来进行符号化，就把变化率分割成多少个等长的区间段，看每个 点的变化率落在哪个区间中就用哪个字符来代替，从而完成对时间序列的符 号化。在文献【1 】中，g a u t a md a s 等人提出了用预先定义的模式来把时间序列 符号化，先把时间序列切割成等长的短时间序列，然后把切割后的短时间序 列用基于欧氏距离的时间序列聚类，然后每个类用一个符号来代替原来的时 间序列模式，从而把一个数值型的时间序列转化成字符型的序列，缺点是没 有根据时问序列本身的特性，符号化的性能太差。在文献 2 】中，j e s s i c a l i n 等人提出了p a a ( p i e c e w i s e a g g r e g a t ea p p r o x i m a t i o n ) 方法对时间序列进行 时间序列的符号化及时序关联圳则挖掘 压缩和符号化，这种方法主要是长时问序列压缩。性能也不太好。 本文的研究工作主要是采用一种基于序列形状信息的时间序列的分割 方法，把分割后的子序列的长度进行统计，得到一个合适的长度，然后把 时问序列划分为长度为，的子序列的集合。把分割得到的时间序列的子序列 用基刁：d t w ( d y n a m i ct i m ew a r p i n g ) 的聚类方法，把相似的子序列聚为一个 类，然后每个类用一个符号来代替原来的时间序列模式，从而把一个数值型 的时间序列转化成符号型的序列，并用自己改进的序列模式挖掘方法对其进 行关联规则挖掘。在最后，通过比较来显示本算法的优越性并给出符号化和 序列模式挖掘的未来研究方向。 时间序列的符号化及时序关联捌则挖掘 第一章时间序列的研究现状 一个时问序列是按等时间间隔采集的记录值，通常我们用一个向量来表 示一个时间序列。人们主要是因为以下两个原因对时间序列感兴趣： 1 、建模时间序列：对时间序列进行建立模型来探测产生时间序列的机 制。 2 、预测时间序列：预测时间序列变量的未来的值。 1 1 研究时间序列的方法 在实际的应用中产生了大量的时间序列数据，比如a t & t 公司一天就产生 三十亿条记录 6 。面对如此大的数据量，提高时间序列的有效的研究方法 面临着巨大的挑战。目前人们主要应用以下几种方法 7 ： 1 数据缩减。由于大部分的时间序列都是长时间序列。在对时间序列进 行研究的时候，由于效率的原因需要对数据进行处理，把长时间序列变为比 较短的时间序列。这不但是研究长时间序列的方法，同时也是对高维数据进 行分析的第一步。数据缩减是数据挖掘中的一个重要概念，数据缩减就是在 尽可能多地保留数据的特征的情况下把大数据集变为易处理的数据或者把 高维数据变为低维数据。时序数据缩减主要使用以下几种方法：离散傅立叶 变换( d i s c r e t ef o u r i e rt r a n s f o r m ) 、离散小波变换( d i s c r e t ew a v e l e t t r a n s f o r m ) 、奇异值分解( s i n g u l a r v a l u e d e c o m p o s i t i o n ) 和s k e t c h e s 方法。 2 索引方法。索引方法为人们检索数据提供一个快速的有效的方法，特 别是在一个大型的数据库中，数据的检索是影响性能的一个主要因素。对时 间序列进行分析，例如查找和一个时间序列具有相似形状( s h a p e ) 的时间序 列，在一个大型的时序数据库中进行这样的查找，如果没有个好的索引结 构，是比较麻烦的。在一般的关系数据库中，使用b + 一树作为索引结构，但是 这种相对简单的索引结构已不能满足大型数据库的查询需求。在大型数据库 中使用的索引结构是：k d b 树、r - 树、r t 树和r + 树。 3 时间序列变换。从时间序列中发现模式是时序数据挖掘研究的主要方 堕塑壁型竺笪! 些墨堕生茎壁型型竺塑 向之一，由于两个时间序列就是模式一样，但受振幅和时问的影响，在判断 时会把这样的时间序列判为不一样，所以要对这样的时间序列进行伸缩和平 移变换是必要的。人们主要用以下方法对时间序列进行变换：平移和伸缩 ( s h i f t i n g a n ds c a l i n g ) 、时问伸缩( t i m es c a l i n g ) 并t l 部动态时间弯由t ( l o c a l d y n a m i c t i m ew a r p i n g ) 。有时在对时间序列进行变换前要对时间序列进行标 准化处理，比如用均值方差标准化就可以对时问序列振幅不同的时间序列化 为相同的时间序列。 1 2 时间序列的研究现状 目前，国内外研究资料中对时态数据挖掘的研究主要可归纳为两类：时 态模式挖掘和相似性问题研究，时态模式挖掘包括了各种序列的模式挖掘， 时态因果和关联规则挖掘等等内容，而相似性问题研究主要是研究相似性算 法的设计以及时间序列的聚类的研究。 1 2 1 时序模式挖掘 到九十年代初人们已经对序列数据中的模式的标识进行了大量的研究 ( a i s 9 0 ，l a i 9 3 ) ，在1 9 9 6 年左右一部分人开始进行对时序模式进行研究。 从一个时序数据中挖掘时序模式有很多种方法，最早的挖掘时序模式算法是 基于1 9 9 6 年a 舯w a le ta l 提出的关联规则的算法，先找出频繁项集，然后根 据频繁项集来得出时序模式。在文献f 8 】中c b e t f i n i 他们给出了挖掘时序模式 的一种有效算法。1 9 9 8 年v g u r a l n i k 等人开发了一种用来描述序列数据中时 序模式的语言，他们还使用一种称为有效序列模式树的数据结构来标识频繁 序列模式【9 】。1 9 9 9 年r a i n s f o r d 和r o d d i c k 对事务的时序分布进行了总结。2 0 0 0 年l ie ta l 提出了挖掘周期时序模式，在文献 1 0 ，1 1 】中j h a n 他 f 开始提出在时 序数据库中挖掘局部周期模式( p a r t i a lp e r i o d i cp a t t e r n s ) 并给出了两种有效算 法。在文献 1 2 w a l i dg 觚f 她们给出了一种在时间序列数据库中增量、 在线和合并挖掘局部周期模式的有效算法。人们不但研究怎样挖掘时序模 式，还进行怎样来标识时序模式的研究，2 0 0 0 年k a m 和f u 通过学习一个短的 间隔( i r l t c r v a 【) 序列来得到一个间隔( i n t e r v a l ) 模式集，2 0 0 1 q ! c o h e n 通过统计检 4 时问序列的符号化及时序天联规则挖掘 验来标识时序模式，2 0 0 1 年r i c h a r dj p o v i n e l l i 提出了一种为了刻画和预测复 杂时间序列事件的标识时序模式的新方法 1 3 】。在一个时序数据库中定位一 个预先定义模式的问题已经得到了解决，但是从知识发现的观点来看，一个 更有趣的问题是探测一个先前未知的、频繁出现的序列模式，这样的序列模 式就叫做时问序列中的m o t i f s 1 4 。文献 1 4 】中不但提出了m o t i f s 的概念，还 给出了一种挖掘m o t i f s 的一种算法，算法中使用了平凡( t r i v a l ) 子序列的概念。 在文献 1 5 中b i l lc h i u 等人提出了挖掘时间序列中的m o t i f s 的另外一种有效 的方法。人们在对时序模式有了较好的研究之后，于2 0 0 0 年以后开始对惊奇 模式进行研究，在文献f 1 6 】中c s h a b a b i 等人首先提出了惊奇( s u r p r i s i n g ) 模式 的概念。但是在2 0 0 2 年e a m o n nk e o g h 等人开始研究在一个线形时间和空间 中寻找时间序列中惊奇( s u r p r i s i n g ) 模式，他们第一次给出了惊奇模式的较好 的定义，并给出了一个有效的挖掘惊奇模式的算法f 17 】。人们不但对常规的 时序数据进行研究，为了某些应用，人们开始对数据流( d a t as t r e a m s ) 进行 研究，于是在2 0 0 3 年w e i - g u a n gt e n g 用基于回归的方法对数据流进行序列 模式挖掘 1 8 】提出一种叫作f t p d s ( f r e q u e n tt e m p o r a lp a t t e r n s o fd a t a s t r e a m s ) 的方法。 由于时序模式的挖掘通常是在一个具有时间标志的事务数据库中进行 的，即：在一个符号型的时间序列数据库中进行挖掘，所以在进行时序模式 挖掘前要对其进行符号化。在文献f 1 】中，g a u t a md a s 等人提出了用预先定义 的模式来把时间序列符号化，2 0 0 3 年在文献 2 】中，j e s s i c al i n 等人提出了 p a a ( p i e c e w i s ea g g r e g a t ea p p r o x i m a t i o n ) 方法对时间序列进行压缩和符号 化，2 0 0 1 年在文献 1 9 】中，李宏等人使用了用斜率对时间序列符号化的方法。 然而，在进行符号化之前如果需要对时问序列进行分割，分割的方法至今还 没有一个较好的方法，一般是采用等长划分，只不过划分后的子序列有的是 重叠的而有的是不重叠的。在藿叠的子序列中重叠的程度也不一样，文献1 1 中使用的是预先定义的一个常数。 1 2 2 相似性搜索问题的研究 相似搜索是搜索和事先给定的时间序列具有相似变化模式的时间序列 时问序刘的符号化及时序关联规则挖掘 或子序列的一种操作。为了度量两个具有相同长度为n 的时阎序列，在文献 2 0 ，2 1 ，2 2 ，2 3 ，2 4 中，都是把序列映射到r n 空闯中，把每个时间序列当作r “ 空间中的一个点，然后计算两个序列之间的欧氏距离来作为两个序列之问的 相似性度量，但是这种方法只能处理具有相同长度的序列，并且两个序列即 使具有相似的形状如果振幅不同，用上述方法来判断则得出这两个序列不相 似的结论。所以，近几年在相似性搜索方面的的研究工作主要集中在以下多 种变换的基础上的相似性问题的研究，这些变换是：伸缩( s c a l i n g ) 2 1 ，2 5 ，平 移( s h i f t i n g ) 变换【2 1 ，2 5 1 ，标准化( n o r m a i z a t i o n ) 1 4 ，2 6 ，2 7 1 ，移动平均数 2 4 ，2 8 和时间弯曲( t i m ew a r p i n g ) 2 9 ，3 0 ，3 1 ，3 2 ，3 3 1 ，经过上述变换后的时间序列在进 行相似性搜索时具有较好的佳能。上面的相似性是指如果一个时间序列在时 间点上的值和另外一个时间序列的值( 或者是它们的变形) 的差值不超过一 个事先给定的常数，没有考虑到两个时间序列在结构上的相似性。但是有 时候需要考虑结构上的相似性，因为在很多系统中这种点对点的相似性度 量是不行的【3 4 ，3 5 】。所以出现了基于形状( s h a p e ) 的相似性，在文献 3 6 1 中， s a n g w o o k i l n 等人提出了基于形状( s h a p e ) 的相似搜索。在文献f 3 7 冲，l e i c h e n 等人首先提出用柱状图的方法，就是把时间序列标准化后用柱状图来表 示时间序列，通过比较相同区间内的点的个数的比率来表示两时间序列的相 似性这是一种比较新颖的方法。对时间序列的聚类研究，在这里我们就不 再多说了，因为时间序列的聚类实际上就是把常规数据的聚类方法推广到时 间序列上，最主要的还是用上面提供的方法来度量两个时间序列的相似性， 以便把相似的时间序列聚到一个类中去。 6 时问序列的符号化及时序关联规则挖掘 第二章时间序列的相似性度量 相似性度量技术是数据分析中最重要的核心技术之一。这是因为无论是数据 分类还是数据的聚类分析都要用到一个技术：怎样来确定两个数据的相似性。分 类和聚类都是想把相似的数据放在一起。本文中要通过聚类技术来对时间序列进 行符号化，也要用到相似性度量技术。下面来介绍本文中要用到的基于形状的相 似性度量d t w ( d y n a m i c t i m ew a r p i n g ) 2 1 经典的动态时间弯曲算法 设现有二时间序列q 和c ，其数据长度分别为i 1 和i n ，有 q = g l ，驰，铷 c = c l ，c 2 ， ( 1 ) 为了利用d t w 计算两个时间序列相似性度量，事先定义一距离相异矩阵。 定义l ：1 3 行m 列矩阵，矩阵中的元素为不同时间序列数据对象之间的点的 欧几里德距离，即d ( q i ，c j ) = ( q i c = i ) 2 为距离矩阵。 d m a tr i x = d ( q i a n ) d ( q 1 一 d ( q 1 ，c 1 ) 矩阵中的d ( q i ，c j ) 是= 个时间序列数据点之间的距离值，可以看作是对象 q 和对象c 之间的相异性的量化表示。当对象q 和c 越相似或越接近，其值越 接近0 ：两个对象越不相同，其值越大。这是进行聚类算法的基础。将两个时 间序列分别置于二维坐标的两轴，如图1 所示。进而可以定义弯曲路径。 定义2 ：在二个不同时间序列问的距离矩阵中，定义时间序列间相异性关 系的一组连续的矩阵元素的集合，称为弯曲路径。 w 2 w 1 ， 】2 ，w t ”f( 3 ) 其中w i = ( 1 ，1 ) ，w k = 沏，胛) 由定义2 可知，弯曲路径满足以下条件： r 一 吼 吼纰 睦o “d 时j w 序列的符吁化及时序关联蛳则挖掘 z 医| 吲 善吲 一吲 瑚 一 i - 1 。j 菇 + 1 。 彳 - f 1 匝工丑互丑e 田 1i - 1； “ - 1 3 n 图l 1 ) 有界性：i l l , m a x ( m ，n ) s k s m + n 1 ： 2 ) 边界条件：w 1 2 d _ m a t r i x ( q l ，c 1 ) 与w k = d _ m a t r i x ( q n ，c m ) ，即弯曲路径 的起止元素为距离矩阵的斜对角线上的两端元素。 3 ) 连续性：给定w k ：d m a t r i x ( q a ，c b ) - 与w k 1 = d m a t r i x ( c b ) ，必须 a a ， 1 & b - b 5 1 ，即弯曲路径中的元素是相互连续的。 4 ) 单调性：给定w k = d _ m a t r i x ( q a ，c b ) w k 1 = d _ m a t r i x ( q “c b , ) ，必须 a 。a 2 0 & b 曲2 0 ，也就是说路径宵通过点( i ，j ) 同时必须至少通过点( i 1 ， j ) ， ( i _ 1 ，j 一1 ) 或( i ，j 1 ) 中的一个，强制保证弯曲路径在时间轴上是单调 的。 对距离矩阵分析可知，弯曲路径存在多解，但是我们关心的实际上仅仅是 弯曲路径总长度最小的，在逻辑意义上，两数据相似性程度最大( 距离值最小) 的作为相似搜索的根据，如下式： 一e ：m 洫接压 式中：分母后是为了在比较不同长度的路径时有统一的标准。现在的时间序列的 相异性度量基于精度因素一般都不用欧氏距离或经典的l p 距离，而是应用上面 介绍的d t w 的各种变f f 3 8 。3 9 。 肘问序列的符号化及时序关联划则挖掘 理论上，可以利用穷举搜索法寻找满足条件的弯曲路径，但是完全穷举在 大型数据库分析中往往是不切实际的，因为路径的解很多，且与距离矩阵中的 元素数成指数关系。由动态编程理论可知，殴有点( i ，j ) 在最佳路径上，那 么从点( 1 ，1 ) 到( i ，j ) 的子路径也是局部最优解，也就是说从点( 1 ，1 ) 到 点( m ，n ) 的最佳路径可以由时间起始点( 1 ，1 ) 到终点( m ，n ) 之间的局 部最优解通过递归搜索获得。即? 吼1 ，1 ) 2 坝g l c 1 ) 欲i j ) 。d ( q i ，c j ) + m i n y ( i 一1 j 一1 ) ，y ( i - 1 j ) ，f ( i j 1 ) ) ( 4 ) 最终时间序列弯曲路径最小累加值为h m ，n ) 。从y ( m ，n ) 起沿弯曲路径按 最小累加值倒退直到起始点“l ，i ) 即可找到整个弯曲路径。从下面的图2 中，可 以看出d t w 算法和欧氏算法的差别。 a 经典的欧氏距离度量 2 ，2 改迸的动态时间弯曲算法 2 2 1 经典的d t w 算法的缺陷 图2 b d 下w 度量 虽说人们已经把d t w 成功的应用到很多领域，但是，有时候用d t w 得出的 结果却是病态的，关键是因为d t w 通过弯曲时间轴( x 轴：x - a x i s ) 来解释数 值轴的变化。另外一个问题是d t w 不能够发现两个序列的自然属性，这是因为 一个序列的属性( 例如：波峰、波谷、弯曲点、平坦点等等) 比另一个序列对 应的属性值大或小，图3 显示出了这个问题，d t w 错过了一个波峰。 9 堕塑生型塑笪兰些些堕堡茎壁塑墨堕墅旦 a 、两个同步信号( 具有相同均值和方差) ，b 、对应属性的排列，c 、d t w 对应的排列 图3 2 2 2 改进的动态时间弯曲算法 在实际的应用中，由于效率和性能的原因，与要对使动态时间弯曲做各种各 样的修改。在文献【4 0 】中，p a r ke ta l 提出了最小边界的概念，但是算法的时间复 杂度并没有得到改善。在文献【4 1 中 k i m + s 提出了用四维属性向量来表示时间序列，四维向量用序列的开始点的 值、结束点的值、最大值和最小值。最小边界是最大的差异的平方，如图4 所示。 imihdiim-m 051 0 6韵巷柏 图4 在实际应用中还需要限制弯曲路径的行走区域。为了矩阵处理方便，应该把 弯曲路径的摆动范围限制在距离矩阵的斜对角线两侧附近，如图5 中虚线所示 的范围 4 2 。因此，在不考虑区域外的距离相似因子的情况下下称这种弯曲路径 时间序列的符u 化及时序关联规则挖掘 幽5 的子集为弯曲窗口。在文献 4 3 中k e o g h 等人提出了l b _ k e c g h 最小边界距离 度量，把弯曲路径限制在一个特定的宽度内。给定一个弯曲路径w k = ( f 力k ，使 得：，- r f - ，+ r 其中r 为在一个时间序列中的点的弯曲范围，定义了一个序列 的最大边界u ( 上界) 和最小边界l ( 下界) ，其中u 和l 中的元素的u f 和l f 为下面 的定义： u i 2 m a x 内r ：g f + l i 2 m i n ( q i ，：q i ”) u 和l 代表了上界和下界，如图6 所示： b 图6 有了上界和下界就可以定义两个序列之间的距离，下面给出基于动态弯曲的 最小距离度量： l b k e o g h q ( 、) = 时问序列的符号化及时序关联删则挖= i f 【i 这个距离函数可以用像欧氏距离那样的方法来显示，图7 显示了两个序列之 间距离计算方法，图中用竖线填充部分的和就是所要求的距离： b 图7 时间序列的符号化及时序关联规则挖掘 第三章数据分割及数据处理 在对时间序列进行操作前，先在下面给出要用到的一些概念的定义。 定义3 时间序列：一个时间序列t = t l j ，t 。是一个具有m 个实值变量的有 序集合，并且m 叫作时间序列t 的长度。 时间序列可以很长，有时包含数百亿个观测点，在这里我并不对一个时间序 列的全局特性感兴趣，我只是对这些时间序列的一小部分感兴趣，这些片段叫作 该时间序列的子序列。 定义4 子序列：给定一个长为n l 的时间序列t ，t 的一个长度为n ( n m ) 的 子序列c 是t 中连续的n 的值所组成的时间序列，也就是说， c 韦，聃一1 1 p 蜘一n + 1 定义5 滑动窗口：给定一个长度为m 的时间序列t 和用户自定义的子序列 长度n ，则长度为n 的子序列可以通过使用一个大小为n 的窗口在序列t 上滑动 得到。 3 1 时间序列的分割 对时间序列进行分割，最常用的方法是等长分割方法，给定一个时间序列 s = ( x i ，x n ) 和一个窗口长度w ，将时间序列s 分割成( 【州+ 1 ) 个长度为w 的 子序列s i = ( x i i 1 ) w ，x l w ) ，1 i n w 】+ 1 ( 最后一个除外) 。而在文献【1 】中。g a u t a m d a s 等人将时间序列s 分割成( n - w + 1 ) 个子序列s i = ( x i ，x i + w 1 ) ，1 _ i n - w + 1 。而有的时 候采用的是文献 1 】中的方法的变形，相邻的两个子序列的不重叠部分的长度不 是1 ，是预先定义的一个常数v ，其中l v s w 。 上面的分割方法没有考虑到时阿序列的形状，这恰恰是时间序列中模式发现 最主要的特征，因为模式在时间序列中就是。下面给出基于时间序列形状的分割 方法。 在对基于时间序列形状的分割方法介绍前我们先了解一下人们用来抽取时 间序列形状信息的方法。人们一般通过用拟合函数和回归来抽取时间序列的形状 信息，对于这种方法我们要求满足下面的性质：原时间序列必须支持从近似函数 抽取的形状特性，并不是所有的近似技术都支持这个性质。几乎所有的函数近似 技术都是采用k 个基本函数b l ( x ) 的加权w i 组合： 时间序列的符号化及时序关联剧则挖掘 厂( x ) = w 。6 ，( x ) i = 1 为了将位图图像转化为向量图，人们已经提出了很多分割算法，但是对于时 间序列的近似用的是一个叫作在线算法，一个点一个点的读取数据并对每一个新 的点调整当前的线形分段函数，然后检查这个新的点是否满足下面的这个公式： v i ：l 厂( 船) 一y ，i s 其中f ( x ) 是这个分段函数。如果满足，则继续进行，如果不满足，这时产生 一个新的分段，这个贪婪算法并没有优化什么，仅仅是满足上面的那个公式。线 形回归的分段算法是首先定义一个可容忍的回归误差，一个点一个点的读取数据 并对每一个新的点调整当前的回归函数，直到回归误差超过了这个预先定义的误 差常数，这时候就结束，把回归函数中的点作为原时间序列的一个子序列，这时 再继续这个过程直道原时间序列都被处理。从计算的观点上看，上面的两种方法 是具有吸引力的，但是分段函数和回归函数的度数( 函数的自变量的最高幂指数) 的选择是上面两种方法的共同难点和缺陷。在1 9 8 0 年s l d a n s k y 和g o n z a l e z 提出 了解决分段问题的一个好的方法( 在这里我们称作锥形方法) ，实际上该方法的思 想和上面的一样都是使时间序列的点的子集的分段线形连接满足公式： v i ：l ，( 雨) - y , s 占 分段的过程如下：从时间序列的一个点x j 开始，在点x j + l 作一个半径为 的圆，通过点x j 作以点x j + l 为圆心，以e 为半径的圆的切线，这时得到一个以 x j 为顶点的锥形区域，依次进行下去。下图给出了这种方法的实现过程。 a 在图a 中是构造第一个锥形区域，第三个点在区域内，这时根据第三个点来 构造第二个锥形区域，这个锥形区域和上一个锥形区域的交集作为最终的锥形区 域，即为图b ，第四个点还在锥形区域内，这时要构造第三个锥形区域，把第三 个锥形区域和锥形区域的交集作为最终的锥形区域，这时地五个点已经不在这个 时间序列的符号化及时序关联规则挖掘 锥形区域内，这时算法结束，并把这五个点作为原时间序列的一个子序列。接下 来继续进行这个过程直道处理完原时间序列的所有点。虽说这个方法比上面提到 的分割算法和回归方法性能要好得多，但是这个算法也存在不足，那就是圆的半 径的选择。的选择决定了这个算法的最终性能。选择的太小，则得到的分割 太零碎，太大就不能很好的反映原时间序列的形状，所以要想使用这个算法并想 得到一个较好的分割结果，必须对采取一个选择策略。 3 2 数据的预处理 虽说已经有很多人在研究在一个大型时间序列数据瘁中予序列的匹配问题， 并且已经提出了很多有用的方法( 像动态时间弯蓝、h h m 模型，小波方法、傅 立叶方法等) ，但是很少人在研究子序列在形状上相似。两个相似的时间序列在 时间和振幅上具有不同程度的伸缩，如图8 a ，图8 b ，即使用基于形状的相似性 度量d t w 度量，这两个时间序列也是不相似的。在文献【4 3 】中，通过下面v s c a l e 图8 a ，在时间上的伸缩 图8 b 在振幅上的伸缩 变换和v - s h i f t 变换使两时间序列具有相同长度( 时间轴上的) 和最大振幅( 数值轴 上的) 。 定义6 ，给定义时间序列t 1 n - - t 1 ，t 2 ，t n ，时间序列t 的v s c a l e 变换是指 时间序列t 1 n 】满足： t 【i 】= c t i 其中c 为一实数。 定义7 ，给定义时间序列t i n l - - t 1 ，t 2 ，t 口时间序列t 的v s h i f t 变换是指 时间序列t 【l n 】满足： t i 】= t i + d 其中d 为一实数。 时间序列的符号化发时序关联舰则挖掘 由于本文中的时间序列的相似性问题是基于等氏的时间序列，所以不用考虑 到时间序列的伸缩变换，只需考虑到时间序列振幅的伸缩变换。在进行计算两个 时问序列的相似性时，为了避免这种由于振幅的不同，而把两个相似的时间序列 判为部相似，所以在计算之前，必须对时问序列进行数据处理。下面介绍常用的 数据处理的方法： 1 最小最大规范化，假定n i n a 和m a x a 分别为属性a 的最小、最大值，最 小最大规范化通过计算： v ；_ 里罢l ( n e w m a x 一月州一m i n ) + ”删一m i n _ m 矗x 一m l l l 将a 的值v 映射到区间 n e wm i n a ，n e w m a x a 中的v 2 z - $ g o g e 规范化( 或零均值规范化) ，这种方法是基于属性a 的平均值和方 差的规范化。属性a 的值v 被规范化为v ，由下式计算： 一 矿2 ( 5 ) 其中，i 是属性a 的平均值，m 为属性久欹方差，诗算公式掘t ( 假设总共 有n 个数据，属性a 的值为：x i ，x 2 ，x 。) ： 孑= 去喜船 ：击扎- a 一) 2 2 石备协， 零一均值规范化的另一形式： v v 。- _ _ 。4 ( 6 ) 其中孑的计算方法和上面公式( 6 ) 中的一样，s 。用下面的公式计算： 驴搏舻孑 公式( 6 ) 比( 5 ) 对于孤立点具有更好的鲁棒性。因为在计算平均绝对镰差时， 度量值和平均值的偏差( i x i 万j ) 没有被平方，因此，孤立点的影响在一定程度 二被减弱了，虽然，孤立点影响被减弱，但是仍然可咀发现孤立点。 3 ，j 、数定标规范化，通过移动属性a 的小数点位管进行规范化。小数点的移 1 6 时帕j 序列的符譬化及时序关联规则挖掘 动位数依赖于a 的最大绝对值，a 的值v 被规范化为v ，由下式计算 。，：三 1 0 其中，j 是使得m a x ( i v ) 8 ，v = j ( ，一8 ) 4f 公式中的，表示的是要划分成的子序列的长度，符号r 表示的意义和上面 9 时问序列的符争七及时序关联捌则挖掘 定义的相例，这个公式限制滑动窗i ：_ ： 每次移动的点的个数在窗口长度的四分之一 和三分之一之闯。 2 这种方法和上面的确定，的值时的方法一样，采用的方法是基于统计的思 想，使用的是下面的方法：首先用长度为f 的滑动窗口，在原时间序列上每次移 动1 个点，把原来的时间序列用这个长度为，的滑动窗口分割成长度为，的子序 列，一共可以得到( 聍一，+ 1 ) 个子序列，并且这些子序列用它们的第一个元素来标 识它们自己：丁t ，r z ，l ，。1 ，这些子序列在集合中的顺序就是按它们的下标的 升序顺序出现的。从n 开始，看n 和n 是否相似，如果相似则把7 1 ：去掉，再看 乃和n 是否相似，直到找到第个和n 不相似的子序列，把死以前的所有的 予序列都除掉，然后对五t 进行同样的操作，找出霸t 之后的第一令和a 不相似鹩 子序列z z ，把n 和五：之间的子序列全部除掉，然后再对五：进行同样的操作， 一直进行下去，最后得到的子序歹i j 集合中任意相邻的子序列之问都是不相似的。 然后对这些按下标的升序顺序出现的子序列进行下面的处理：计算相邻子序列下 标的差值并对其进行统计，找出一个合适的数值b ，小于b 的值的个数和总个数 的比值不超过个给定的值。这时的这个值6 就是我们所要找的值v 。 在这里我们采用第二种方法。由于我们对时间序列进行分片的目的是发现时 序关联规则，其中一个关键步骤是寻找频繁项集，这样用上面的，和v 来分割时 间序列保留了原时间序列的大多数的模式，从而保证了最后有一个较好的结果。 算法( a s a b s 谒l 述： 1 用线性回归方法对时间序列t 进行分割，用一个数r l s e q u 来依次存放子序列的起始 位置，计算l , = s q u e i + 1 s q u e i 。 2 然后统计 的每个值出现的次数，找出个最优的，( 这里的最优指的是在大部分的 子序列的长度在该值的一个较小的邻域内) 。 3 用，作为滑动窗口的长度- 在原时问序列上每次移动一个点，把原来的时间序列用 这个长度为，的滑动窗口分割成长度为，的予序列， 4 对这些子序列进行排序( 按下标进 i 舟序择序) ，采用消除相邻福似序列的方法计算 出一个较合适的窗口滑动步长的值v 。 5 瑚长度为、步长为v 的滑动窗口手巴时间序列进行分割，得到子序列集合。 时间序州的符0 化及时序关联删则挖掘 4 2 时间序列的相似性度量 从第三章中我们对各种各样的相似性度量有了一个全面的了解，我们在这里 采用的是基于时间序列形状的相似性度量方法，但是我并不是把传统的d t w 方 法或者是d t w 的改进方法搬过来用，我用的是适合本文的短序列的、改进的 d t w 方法。这主要是因为传统的度量方法的不足，本论文中使用的是改进的 d t w 方法，并且本文要计算的是比较短的时间序列，上面的l b _ k e o 曲距离并 不适合。本文所用的距离的计算方法是用下面的方法给出的。 在实际应用中不但需要限制弯曲路径的行走区域，为了矩阵处理方便，应该 把弯曲路径的摆动范围限制在距离矩阵的斜对角线两侧附近，如图5 中虚线所示 的范围 4 2 1 。还要考虑下面的问题： 由于事先定义了弯曲范围，在寻找最小路 径时得到的最小路径有可能不是最小路径，或者弯曲的范围太大。 基于上述缺陷，所以本文在寻找最短路径时采用启发式的搜索方法。在本文 章中要聚类的时间序列的长度都是相等的，在寻找最小路径时，先找一对角线图 9 a ，再找二对角线图9 b ，如果在二对角线下得到的最小路径比一对角线优，则 再找三对角线，如果在三对角线下得到的最小路径比二对角线优，则再找四对角 线，以此类推，直到下一次找到的最小路径不比上一次得到的最小路径优，则停 止，把次最后得到的最小路径作为最后结果。实际上这种方法的迭代次数太多， 图9 a 一对角线 图9 b 二对角线 我在这里使用的是给出一个初始的整数p ，我们不从一对角现线。而是直接从p 对角线开始 依次增加1 ，直到值不再减少为止。对于p 值的确定，在这里采用的是就小不就大的原则。 不然的话，就和常规的限定弯曲范围没有太大的区别了。 4 3 时间序列的符号化 在本文章中采用的是通过对分割后的子序列聚类来对时间序列进行符号化 堕坚壁型塑笪兰些丝堕堡叁壁型型丝塑一一 的，有必要对聚类有个简单的描述。 聚类分析是一种重要的人类行为，目前已应用于许多方面：模式识别、数据 压缩、市场分析等等。聚类相对于分类来说是一个无指导分类，在分类前，对于 类的标号和类的数量都是未知的，多年来对于聚类的定义来说有很多( 如【j o l l l l 6 7 ，w a l l6 8 ，e v e r 8 1 ) 。然而，大多数的定义是不精确定义，例如相似、相像等。 在 e v e r 8 1 1 中，向量被看作是，维空间中的点，聚类被描述为“空间中包含相对 高密度点的连续区域，由相对低密度点区域将其与其它相对高密度点区域分开” 在参考资料【4 4 1 中给出的聚类概念是将物理或抽象对象的集合分组成为由类似 的对象组成的多个类的过程，在同一个簇中的对象之间具有较高的相似度