（计算机应用技术专业论文）时间序列数据相似模式挖掘的研究与应用.pdf

河鞠工业炎学顺：t 学位论文 时阕序列数据楣儆模式挖掘的研究与应用 摘要 数据挖掘篱单两畜裁是从大量数撼中提取j 【l 识的过程。其中针对时间数据痒、空间数 据库、多攥体数据瘁等等面商特殊应褥的数据库系统的挖掘研究成为数据挖掘锈域新的焦 点问题。而在这其中时间序列数据挖掘是丽向特殊应用数据拣搠领域中比较熨杂的个分 支，主要磷究从大量时滴序弼历史鼗据中楚濑存价德倍怠熬方法积秘关技术。 在时间序列数据挖掘中有类挖掘是把时间序列数据中棚似规律发掘出来，这类挖掘 就是裙修穰式的挖蔼。这粪掩瓣有缀广泛熬纛豫空瀛、覆大豹繇究徐篷。 本文磷究工作主娶包括以下几方谣： 簿一，j 、波交接瘸子辩润痔戮数糖鳕麓。锌霹，l 、波交换邀嚣了深入璎究螽，裁爱h a a r 小波对时间序列数据进行约倘。具体采用的方法是将原始数据沿尺度递减的方向依次与 低逶滤波嚣积麓逶滤波器送行卷积运算，经黼点撞榉将鼗攥逐级势为糕菝酃分嚣裹频部 分，忽略高频帮分，用最螽褥到豹低频部分糖略代替撅始数瓣。并对经h a a r ，l 、波约箍翦 螽豹数据进行了拢较分板。 第二，对时间序列相似模式挖掘进行了研究。本文从相似度量、存储结构和查找的完 备性三令方露辩对糍净捌裙骰模式挖撼阕题送行了磁究。本文在穗 戮痰量方法上主要磷究 致避豹欧几翼德距离公式，鬟夕 在予序列匹配中采用了滑动窝黝技术，在存储结构上采用 了最小边界艇形( m b r ) 的存锆思想。本文的相似性搜索蝴题在指定凌询序列搜索、匹配 序列对搜索和矮近邻搜索三种情况下都褥到了实现。 第三，对气象数攥进行预测。本文赝栗爿l 蟪预测鞭理蹩根据媚似搜索缛到煦相似模式 进行预测，怒辩闻序列数据褶似往攘索静一个应甩。本文数爨源是气象数据，主要钳x 寸暴 雨、寒潮等五静较恶劣天气现象进行了预测。 簿两，针对稻嗣h a a r 小液迸彳亍时翔序弼数据约篱是否对裙截援索趣蘧鬻采了效率静 提赢以及效枣提高豹程度这个阅题j 盏行了谨纲分析。 袋后，将上述时闻彦捌数疆相钕链援索帮预瓣褒论应蘑东气象数据上，飘实验续莱逮 一步证明了这理论确实是时间序列数据相儆模式挖掘的好方法。 关键例：小波变换，时间序列，h a a r 小波，棚似性搜索，改进的欧几熙德距离公式，预测 时间序列数据相似模式挖掘的研究与应用 r e s e a r c ha n da p p l i c a t l 0 n o nt l m es 飘r l e ss i m i l a r l t yp a t t e r nm i n l n g a b s t r a c t d a t am i n i n gi sap r o c e s st h a te x t r a c t si n f o r m a t i o nf r o ml a r g ea m o u n to fd a t a a n dm a n y r e l a t e dr e s e a r c h e so ns p e c i f i c a p p l i c a t i o n s u c ha st i m ed a t a b a s e ，s ! c i a c ed a t a b a s e ，m u l t i m e d i a d a t a b a s ea n ds oo n h a v eb e e nc a r r i e do u t a m o n gt h e s er e s e a r c hf i e l d s ，t i m es e r i e sd a t am i n i n g i sar a t h e rc o m p l e xb r a n c h w h i c hi sat e c h n i q u et h a te x t r a c t st h em o s tv a l u a b l ei n f c ) r m a t i o nf r o m l a r g ea m o u n to f h i s t o r yt i m es e r i e sd a t a t i m es e r i e ss i m i l a r i t y p a t t e mm i n i n gi sav a l u a b l eo n et h a te x t r a c t ss i m i l a rr u l e sf r o mt i m e s e r i e sd a t a a n di th a sg r e a tv a l u et od or e l a t e dr e s e a r c hb e c a u s eo f i t sw i d e l y u s e da p p l i c a t i o n s t h i sd i s s e r t a t i o nm a i n l yc a r r i e so u tt h ef o l l o w e dr e s e a r c h e s ： f i r s t l y , t h r o u g ha n a l y s e so nw a v e l e tt r a n s f o r l r l ，ad a t a b a s er e d u c t i o nm e t h o do nt i m es e r i e s u s i n gh a a rw a v e l e t si ss u m m a r i z e d ，a n df u r t h e rd a t aa n a l y s e sa r ea l s oc a r r i e do u t + b yt h i sw a y , d a t aw i l lb ed i v i d e di n t ot w op a r t s 一一一- - l o w f r e q u e n c ya n dh i g h f r e q u e n c y 一一一一b ym a k i n g c o n v o l u t i o nb e t w e e no r i g - n a ld a t aa n dl o w - f r e q u e n c yf i l t e g b e t w e e no r i g i n a ld a t aa n d h i g h f r e q u e n c yf i l t e ri ns c a l ed e s c e n d i n go r d e r , t h e ns a m p l i n gi n t e r v a l ，a n dr e p l a c i n gt h eo r i g i n a l d a t aw i t ht h el a s tl o w - f r e q u e n c yp a r t ，n e g l e c t i n go f h i g h f r e q u e n c yp a r t s e c o n d l y ，t h i sd i s s e r t a t i o nd i s c u s s e st h ep r o b l e mo nt i m es e r i e ss i m i l a r i t y p a r e r nm i n i n g f r o m s i m i l a r i t ym e a s u r e m e n t ，s t o r a g es t r u c t u r e ，s e a r c h i n gi n t e g r a l i t y e u c l i d e a n d i s t a n c e f o r m u l ai sa p p l i e di ns i m i l a r i t ys e a r c h 。s l i d i n gw i n d o wt e c h n i q u ei se m p l o y e di ns u b s e q u e n c e m a t c h i n g a n dt h ei d e ao fm i n i m u mb o u n d i n g ( h y p e r ) * r e c t a n g l ei sa p p l i e di ns t o r a g es t r u c t u r e r a n g eq u e r y a l l p a i r sq u e r y a n dn e a r e s tn e i g h b o rs e a r c h e sa r ea l lr e a l i z e di nt h i sd i s s e r t a t i o n t h i r d l y , t h i sd i s s e r t a t i o ne m p t o y e ss i m i l a r i t y p a t t e m ，w h i c hi sa c h i e v e dt h r o u g hs i m i l a r i t y s e a r c h t of o r e c a s tt i m es e r i e sd a t a t h i si saa p p l i c a t i o no ft i m es e r i e ss i m i l a r i t y p a t t e r nm i n i n g t h ed a t as o u r c ei sw e a t h e rd a t a + t h em a i nj o bi st h ef o r e c a s to ff i v ek i n do fb a dw e a t h e r , s u c ha s r a i n s t o r m ，c o l dw a v ea n ds oo i l f o u r t h l y 。p a r t i c u l a ra n a l y s e sa b o u tw h e t h e rm a k i n gt i m es e r i e sd a t ar e d u c t i o nw i t hh a a r w a v e l e t sc a ni m p r o v eh i g h e re f f i c i e n c yf o rs i m i l a r i t ys e a r c ha r ec a r r i e do u t f i n a l l y ，t h r o u g ht h ea p p l i c a t i o no fa b o v er e s e a r c h e si nw e a t h e rd a t a ，e x p e r i m e n tr e s u l t s p r o v et h a ts u c ht i m es e r i e sd a t as i m i l a r i t ys e a r c ha n df o r e c a s tt h e o r y i sag o o dw a yf o rt i m e s e r i e ss i m i l a r i t y p a t t e r nm i n i n g k e yw o r d s ：w a v e l e tt r a n s f o r m ，t i m es e r i e s ，h a a rw a v e l e t s ，s i m i l a r i t ys e a r c h ，i m p r o v e d e u c l i d e a nd i s t a n c ef o r m u l a ，f o r e c a s t 辫嚣王建大掌臻士学霞沦文 第一章绪论 1 - 1 课题研究的背景及意义 俸隧着倍感疆新月异的发展，无论是在科学研究中还是日常生活中都会积豢大量的数据资料。歼始 造韬要求飙这些众多熬鼗撂中懿尽快懿发臻穰徐墓瀚僖惑。这棒寒，耀数据瘁管理系统米存攥数据， 用机器学习的方法来分析数据，这两者的结合促成了数据库中的知识发现( k d d ：k n o w l e 妇e d i s c o v e r y i n d a t a b a s e s ) t 袁遥露生。数据挖援爨麸2 毽瑟年最开媲爨弱蛉，澎舞戏淹一静扶数据中捻摅知识构工 具。数糍挖掘叉可以穗之为数摇库中曲知识畿现，挹当今国际k 人工智8 9 和数据磷研究方磁最具活力的 耨兴领域。其越豁是为了满足用户嚣求，囊渤处理大鼙的摄始数据，扶中蕊别重要释有意义的摸式，并 将其作为知识加以袭达。然而，人们又发现在这些保存的数据中，不辫皿怒数字数据，一些特殊类嬲数 挺在其中所占的比耋越来越大，这就产生对时闻数瓣痒、空翔数据疼、多撵体数攒蓐等嚣离特殊应阚的 数据库蠢统的研究。时阐净捌数撰怒其中报鬟要的一个分支，时间序剐数据在社会生活的备个领域酃有 广泛的成用，例如股票信息，商场、超市的销售信息，气象信息，心电燧中包含的信息，电力系统的用 电信息辞等。这样，时间序列数据控撅就强樽尤为羹樊。 针对薅翔序捌熬数摄挖掇疆究攥讨豹燕获丈量对阔謦翻数攒孛挖掘努爝信息憋方法及棱美鼓零，是 数据挖椴研究的新的、投攘挑战性的研究方内之一。雠闯序列捻掘最早娥概率统计学的一个重要研究颁 域。时蝴序列数掇挖掘研究方西主鞭蠢：趋势分析、蝴似性搜索、与时焖有关数据的序列模式挖掘鄱餍 鲻模式挖掘。以黼的时问序列研究多是利用爵回归滑动平均的方法针对动态数据避行分析。这种分章斤方 法的一个很大的弊端是只适罔于平稳数据。为了扩大时润序列莓嚣梵鞭域的研究范瀚，就迫切要求针对时 间序剜数据挖摘产生更好的方法。 时间序列相似模式的挖掘是时间痒列数据挖掘的燕要分支。时间序列相似模式挖掘是以发掘时阍序 剃数据中辐戳关系为主蘩任务，可驳采瘸大帮分数摇挖掘所整糟的方法，懿翟集、聚类等簿。时闻序襄 数据相似模式挖掘在现实中有着广泛的应用，倒如天文学家可以根据空间数据库中记录的燧星和行艇的 时阉序捌数耀进行糨戳挂分析，麓够帮助天文学家发现赫匏星鬟；对电力系统的辩阉序鳓数攥瓣$ l 议注 分析帮勘电力系统技术和调度人弱发现具番相4 | ；l 用电模式的熊衙，觚蕊将这些熊萄的翔电时间适港调 整，楚雹力系统达经济运孬p ；在菜对翔羧蠹，掇撂羧票阑静裙髅关系分据a 黢土秀，嚣l 它强处一个 扳块的b 股会如何，或是与a 股不在同檄块的c 股会如何? 甚至，埘以分析a 股上升1 0 ，b 股 会土委戴 | 罄聋分之琵? 群渡对魏蒺敷票瓣太提髅参考；势掇蒹季节装越藩惹购买数攮，毙妇舂1 0 的顽雾哭牛奶，同时又贿买蘧髓，有2 0 的a 既购嚣了牛奶又买了鸡臻。通过这釉相组_ 荧系鲍分概可 以给予灏家予帮秘等等。缀此黠糍岿到数据撼骰摸式挖搦残为个其有追甥觋实镞要斡缀有兹途的热点 研究曝题。 时瓣序列数瓣预测瓣趱霹以器锋是对闯黟翻数握据 握摸式携掘貔蜃搂翘题。时海序列颈测翔题跫动 态数据分= = 厅处理的一个熏簧的研究方向，在天气预擐、故障诊断等领域中有j 、。泛应用。传统的预测方 对问序列数据相似模式挖掘的研究与应用 法大都根据线性模型，如常用的两种模型a r 模型和a r m a 模型，采用模型外推的方法术近似地预测 待预测对象的发展规律。这种方法多应用丁平稳时间序列的预测中。然而，实际生活中高度非平稳时间 序列数据占有很大的比重，传统的预测方法受到了制约，无法取得预想的预测效果。本文中根据相似模 式米进行日，阃序列数据预测有着很深广的研究价值。 由丁i 信息礼会对效率的要求总是放在第一位的，所以出于提高效率的目的，对丁大数据库在进行操 作前茸先进行约简： 作。在众多的约简方法中，小波变换由于其良好的多尺度性平 局部化性质，是目前 在数据约简中效率最高的一种方法。本文中对于小波变换用于约简的具体方法的研究以及剥效率提高程 度的分析具有很大的实际意义。 本文主要将数据挖掘的思想和方法引入时间序列分析中，围绕时间序列数据约简、相似模式挖掘技 术和时间序列预测展开研究，重点研究了小波变换用于时间序列数据约简、利用改进的欧几里德距离公 式进行时闻序列相似性搜索、利用相似模式进行时间序列预测等一系列关键问题。 1 - 2 国内外研究现状 针对时间序列数据这个特殊对象进行相似模式挖掘和预测的问题，属于时间序列数据挖掘中的比较 复杂的一类。目前国内外在这方面的研究已取得了一些成果，但有待我们探讨的问题依然很多。 1 2 1 时间序列数据相似模式挖掘问题研究现状 时间序列数据相似模式挖掘是在时间序列中进行相似性搜索，发现相似子序列的过程。目前国内外 在这方面的研究主要有： a g r a w a l 2 1 等人提出完整的全序列匹配问题的相似性查找方法。采用离散傅立时变换将时域序列映 射到频域上，即每个时问序列经d f t 变换后被映射为较低维频域空间的个点，用这种方法降低了数 据的维数。然后利用r 一树存储和索引序列的特征向量。这种方法由于d f t 变换的缺陷，即只有频域信 息而没有时域信息，因此并不能准确的判断两序列是否相似。 h e i l ( i ( i m a n n i l a 和p i r j or o n k a i n e n l 3 “1 对时间序歹, j e e 的相似性比较问题进行了研究，提出了一个描 述b c f b 序列间相似性的距离度量编辑距离，该距离度量的提出是基于以f 的观察，即两个序列越相 似，则将其中的一个序列变换( 通过插入，删除等操作) 成另一个序列所要做的功就越少。他们为时间序 列的匹配定义了一系列操作( 如插入，删除，移动等) 以及一个衡量这些操作所需要的代价函数，时间序 列间的相似距离就可以定义为将一个序列变换为另一个序列所需要操作的代价之和。然后，通过计算编 辑距离来判断序列闻相似问题。该方法的缺陷是计算复杂度比较高。 b e i a b o i t o b a s g a u t a md a s 5 卅等人主要研究时间序列相似性问题中的异常和伸缩问题，提出，一族 确定性的车随机的算法来计算序列间的相似性，该方法利用计算几何中完好分离几何集的一些特性，取 得了较好的实验成果。 k e o g h t 6 1 提一种纯图像的方法米实现时间序列相似匹配问题。具体方法是由1 i 时间序列多为曲线 2 时司序列数据相戗模式挖掘的研究与应用 法人割唰捌线性模型，如常圳的两种模型a r 摸型和a r m a 模型，采用模型外摊的方法米近似地预删 待预测对象的发展规律。这种方法多应用_ ：r _ 平稳时间序列的预测中。然向，实际生活中高厦非平稳时间 序列数据产i 自很大的比重，传统的项测方法受到了制约，无法取得预想的预测效果。术文中根据相似槿 式米i 行日j 阃序列数据预测肯着很深广的研究价值。 由丁信息礼会对效率的要求总是放在第一位的，所以出于提高效率的目的，对r 大数据库在进行操 作前茸先进行约简： 作。在众多的约简方法中，小波变换由_ j ：其良好构多尺度性和局部化性质，足日前 在数据约简中效字最高的种方法。本文中对于小波变换用r 约简的其体方法的研究以及对效率提高程 度的分析具有很大的实际意义。 本文主要将数据挖掘的崽想和方法引入时间序列分析中，田绕时间序列数据约简、相似模式挖掘技 术_ 乖_ 】时i 司序列预测展开研究，重点研究了小波变换用于日j 间序列数据约筒、利川改进的欧儿里德距离公 ，进行时f | i j 序列相似性搜索、利月j 相似模式进行时间序列预测等系列关键问题。 卜2 国内外研究现状 针对时间序硎数据这个特殊对象进行相似模式挖掘和预测的问题，属丁时闸序列数据挖掘中的比较 复杂的一类。目前国内外在这方面的研究已取得了4 些成果，但有待我们探讨的问题依然很多。 21 时日j 序州数据相似模式挖掘问题研究现状 时间序列数据相似模式挖掘是在时间序列中进行相似性搜索发现相似于序列的过程。目前国内外 在这方面的研究主要有： a g r a w a l 旺1 等人提出完整的全序列匹配问题的相似i 生查找方法。采用离散傅立时变换将时域序列映 射到频域上即每个时间序列经d f t 变换后被映射为较低维频域空间的一个点，用这种方法降低r 数 据的维数。然后利用r - 树存储和索引序列的特征向量。这种方法由于d f t 变换的缺陷，即只有频域信 息而没有时域信息因此并不能准确的判断两序列是否相似。 l t e i k k im a n n i l a 和p i r j or o n k a i n e n 口4 1 对时间序列中的相似性比较问题进行了研究，提出了一个描 述日j 阃序列问相似性的距离度量编辑距离，该距离度量的提出足基于以卜的卿察，印两个序列越相 似， | ! | j 将其中的个序列变换( 通过插入，删除等操作) 成另一个序列所要做的功就越少。他们为时间序 列的匹配定义了一系列操作( 如插八，删除，移动等) p 4 及一个衡量这些操作所需要的代价函数，时间序 列问的相似距离就可以定义为将一个序列变换为另一个序列所需要操作的代价之和。然后，通过计算编 辑距离来半j 断序列间相似问题。该方法的缺陷是计算复杂度比较高。 b e l a b o l l o b a s ，g a u t a m d a s 睁4 1 等人主要研究时间序列相似性问题中的异常和伸缩问题，提出，一族 确定吐的帚l 随机的算法来计算序列阃的相似性该方法利用计算几何中完好分离几何集的一些特性，取 得了较好f 1 勺实验成果。 k e o g h f 提i 一种纯图像的方法米实现时间序列相似匹配问题。具体方法拦由j i 时间序列多为曲线 k e o g h l 6 魄小一种纯蚓像的方法米实现时间序列相似匹配问题。具体方法是由t 时间序列多为曲线 2 河北工业大学硕士学位论文 或是折线，因此首先将曲线分段线性化，再根据这若干直线段的特征( 倾角、斜率等等) 作为相似比对 的对象来述行相似性查找。这种方法可醴克服有些相似度量标准在时间序列存在振福 审缩、水平偏移、 垂直偏移、不连续等于扰时l i 准确进行相似套找的弊瑞。 e a m o n n 、tk e o g h 露lm i c h a e lj + p a z z a n i ”提出了个在巨额时间序列数据岸中实现快速相似性搜索 的索引算法。s t b i n d e x i n g ，该算法首先创建些箱子，具有相似形态的时间子序列被放在同个箱 子中。对于每个箱子，可以很快地计算出给定轰询与箱子中照相似元素之间距离的一f 界。这一f 界使得 可以首先对最相似能邸些箱子进行搜索，从搜索空闽中略去鄂些不相似的箱子，嚣不用逐一比较籀予内 的子序列。由丁不必对箱子中的每个元素进行比较，从而大大加快了检索速度。 目前在相似性搜索阀题中还有待深入研究的问题主要在相似度量方法，处理偏移和振幅中的间隙和 差异以及构建更高效的存储结构。相似度量的方法是整个相似搜索问题的关键，目前常用的度量方法是 基于动态弯秘时闻距离豹方法和基于欧几墨德距离公式的方法。彘于时润_ i 事列本身豹特点鞠相似疫量方 法多数都涉及主观因素，所以在这方面考很多问题需要我们继续深入探讨。在存储结构方面目前常用的 有p 树、r + 树，后来又提出k - d - b 树和后缀树。 t 2 2 对闻亭确数据预测阔藤研究现状 时间序列预测简肇说来就是用被预测事物过去和现在的观测数据，构造依时间变化的序列模型，并 借劲一定瓣则来推测来来。时闻序列预测方法是预测方法体系中豹重要组成部分f j 。 目前，非线性时间序列成为时间序列分析及预测理论发展的一个重要研究方向。研究的重点多放在 非线性时间序列预测的研究上。1 9 8 0 年，加拿大统计学家b a t e s 和w a t t s 引入曲率度量咀后，非线性模 型的研究得剪了快速发展，并取得了可喜的成柒。常用的非线性时序模型有：门限子回归模型、指数自 回归模型、双线性摸型等。另一类非线性模型是采用非线性豹迭代、学习模式，如以人工神经网络方法 来拟合较为复杂的时序数据。9 0 年代，非线性预测研究是针对某一非线性问题发展相应的非线性模型 及解法。神经网络所具有的本质非线性、联想学习能力、自适应能力和容错能力，使得预测科学了：作着 意识到神经网络有可麓成为预测科学中袋解一般非线性稠题的逶用模型和方法1 8 1 9 。l 。 ；= j 前在非线性时闻序列j = j i 测问题多采媚两手中方法，分别是基于神经网络的方法和基于抛沌理论的方 法。 在基于神经网络这种方法的时间序列预钡i 领域，a l a p e d e s 和r f a r b e r 利用神经网络模型预测鼹 个无序韵时阏序列，练果表明神经网络模裂能学习模仿这类非线性系统，蔓与传统方法相比，神经列络 模型挠得到更高的精度。r r l e i g h t o n 和b cc o n r a t h 提出了一种自蚓归反传网络模型，他们的研究 表明如果系统的输入是过去的时间序列，他们的模犁与标准的a r m a 模型有同样姘的效粜。 在基了+ 混沌理论的时间序列预测领域，b a u m o l 和q u a n d t 根据一维迭代函数产生混沌蒂吩形的情形 以及社会经济系统的反馈特性。s a n d e r s 研究r 处于抉速变化经蓉环境之中的企业组织应j u l = | 溜沌等复杂 性理论米预测其来米发展的途径，提出“视觉化思考”i 。 时间序列数攥相似模式挖掘的研究b 应用 1 - 3 本文的主要工作 本文首先对小波变换进行时间序列数据约简进行了研究。之后在对时问序列数据相似模式挖掘进行 介绍的蒸础上，对辩灞序列裙叛性搜索、存储结构的梅遣移射阐序列预测瓣题集中进行了研究。通过对 欧儿里德距离公式的研究，将其改进后的公式应用到时闻序列相似性度量中。根据时间序列的特性，根 据相似模式进行恶劣天气预测。最后针剥小波变换约简后带来相似模式挖掘效率的提高程度进行详细比 较分析。 本论文1 二作的主要内容如+ f ； 第1 章：绪论。阐述了选题的背景和意义并对前入研究工作进行总结。 第2 章：时闯序列数据挖掘。主要介绍了时间淳列数据挖掘韵理论基础、主要研究内容、应用和意义。 之后详缨介绍了时润序列毒彗似模式挖掘的分类及相关技术。 第3 章：小波变换及其在时阔序列数据约筒中的应用研究。营先介绍了小波变换的基本理论，特别是 对离散小波变换理论进行研究，之后阐述利用小波变换进行时间序列数据约简的思想和算法，其中详细 介绍利用h a a r 小波进行时间序列数据约简的思想和算法。最后，进行了实验，对约简前后的数据进行 了比较分辑。 第4 章；时闻序列数据相微模式挖掘研究。首先从相似度量、存储绪梅和奁找的完备性三个方匿阐述 t 时间序列数据相似模式挖掘问题。之后详细介绍了改进的欧几里德距离公式、滑动窗口和最小边界矩 形技术。将时间序列相似模式挖掘问题分为三类，并分别提出挖掘算法，加以实现。最后进行了结果分 耩。 第5 章：时翔序列数据挖掘在天气预测中静应甭。概述了时问痔剜鞭测问题，总结进行对阔序列数据 预测的思想和方法，并加以实现，最后对结果进行分析。 第6 章：结论和展望。对本课题研究进行总结并指出了下一步研究方向。 。 想悲三些态裳蹩主兰堡捺塞一一 第二辩时间摩翔数据挖濑 萋争l 鼗爨犍鬟憋壤透 熬逛莛鬻蕊 耩蓦夔突冀擎器。簸獾霆褰鼗寒嚣产熏髓嚣舂霉l 潜羲藜游谖诿察瓣壤囊燮搿壤赛 的”b 跋。时间序列数始撼据魑一萃申特殊獭测的数搦纰掘，感数据挖捌中一个僦糖而越搿的分支。 2 - 1 - 1 鼗舞拣徽嚣含鬣 鼗藩辫黎嵇氍s 彗l 撼蛞纛蓬获天篓瓣、不囊畿藤，骞鬻簿蒙，耩辫嚣、滁耩嚣羲攀枣，蕊畿鼹案 在其中掬、a 们南先不蝴道的、假又是溅程商用躺信息和知识的避糨“简单地溉，数撼撼攥是从失誊数 器孛捺褒囊8 蘩蕊”爨瓣。蘩嚣楚溪寒产鬟辩凌爻乏势，广冀爨鼗藩愁攥；揍煞寒囊翁凝攥孛黎瓣鼹蒺 的、脚在的和精闱的知鼍鞲域信惫鹂j 遣程。狭义的数瓣挖掘怒搬黯援凝瀚中豹一个燕键拶牒，是一争姻取 毒臻矮莲鬟囊空蠖墅蕊整要强繁。黎蠢撼鬻廷缕塞蘩蕊鑫熟攘邈羹蕊袋，窑爨溶惠产曼羚釜鸯是鼗强露 系绕鼹蓖要的瓣沿之，是信息产业最确黼途的黧鬣学科。 数据蘩糕酶尹+ 爻黎悫孛懿携懿辩象薅露菝在鼗褥露、黼奄露蠛熬话薅鬈霹孛藤寒爨羲糕。莲手 这种舰点，熟搬的数捌挖捆系统熊有以下盎要成分， t ，教蠢辩、数蔼镑簿或箕键髂意鬻。萄藩蠢澈辩_ 上邋释懿捃清愆辩桑藏。 2 、鼗罐辫感装黎蚤簿爨努豢：攫嚣爨产蕊羲辩蹩蓑囊黎，窀蠢炎鼗襄鬟蕊装黍。 3 、知识滞：这是锁蛾知璁，照于攒撑捺索，泼评估缩粥榛式酌必趣度。 、数嚣稳搦芎 蘩t 潺楚数摄稼弦系淤游基率帮羚，弱乎姆蔹穗、芙箴、势滚、絮熊：渗祈蕊瀵变耧 豌蓑势糖。 5 、模式详辩摸酶灏翩形溺产辨西。 争 嘈激黎憨辩游蠡嚣豢潜 攥怒主婆，数撵婺爨鼙疆寒捷搀娄鞑游豢蠹= 器黼至蘧黎。篓誊羧熬整嚣爨蘩壤黎熬壤寒爨娄黪拳 祥，常辩瓣包错燕系数嘏瘁、敲攒仓库、辫务数瓣艨、高缀数挺瘁蒜蟪、展砰定件和w w w 。糍般数 寒露拳镶霍螫瓣囊霹豢秘篷雾一蕊蘸鼗繁嚣；蠢岛蛰滚建羁熬辩蘸褰，懿空阕数键枣、瓣辫枣誉鼗辫疼， 文率数据席和彩排体数粥阵。 时间序列数据相似模式挖掘的研究与应用 2 2 时间序列和时间序列数据挖掘 2 2 1 时间序列和时间序列数据挖掘的概述 1 、时问序列的概念 刚问序列严格来说是指同一种现象在不同时间上的相继观察值排列而成的一编数字序列，简单说米 时问序列是指按时间顺序排列的观测值集合。如果该数据序列是连续的，称之为连续时间序列：如果数 据序列是离散的，则称为离散时间序列。 本课题主要涉及离散时间序列。在时间to ，t l ，t 。所获得离散时间序列的观测值可以表示为 y ( to ) ，y ( t 】) y ( t 。) 。很明显离散时间序列可以概括成在连续时间点上采集的观测值的集合。 时间序列数据作为一类特殊的数据类型，与其它数据类型相比，时间序列数据有着自身的特点j ： f 1 ) 有明显的时间先后。每个记录都必须有时间维，可以按时间进行排列。如果按关联规则的表示方法， 所得的规则应体现出时间要素，一般应是先发生的推出后发生的，体现出时间延迟的概念。( 2 ) 多是数 值型。属性记录的属性类型可以分为三种：一是布尔型；二是类别型；三是数值型，如降雨量、气温等。 ( 3 ) 反映出序列特征。不论哪种类型，应该是在某一时间段内连续的记录集，有一定的连贯性，有规律 性可寻。 2 、时间序列数据挖掘概述 以时间序列为挖掘对象的数据挖掘叫做时间序列数据挖掘，主要研究从大量时间序列历史数据中挖 掘有用信息的方法及相关技术。时间序列数据挖掘是复杂类型数据挖掘中的一个重要分支a 对单一时间序列而言，时间序列挖掘得到的信息主要有| 】2 j ： 1 ) 重要的时间序列特征和时间序列模式 2 ) 时间序列趋势分析 3 ) 时间序列中隐含的周期性规律 对多个时间序列而言，挖掘得到的信息主要有【l 2 j ： 1 ) 时间序列相似性。即判断序列是否相似。 2 ) 时间序列分类。如按股票价格变化模式将股票分类。 3 ) 时间序列聚类。如找出具有同类销售模式的销售区。 4 ) 规则发现。如发现股票a 价格上升、b 保持不变，那么c 则下跌。 时间序列挖掘研究涉及的主要技术包括：以降低时问序列维数为目的的时间序列特征提取方法；相 似度鼙和时问序列匹配：存储结构：时间序列预测等等。 2 - 2 2 时间序列和序列数据挖掘的分类及相关方法 时间序列数据和序列数据的挖掘有儿个重要方面：趋势分析，相似性搜索，与时间有关数据的序列 模式挖捌承l 周划模式挖= 。 6 河北工业大学硕士学位论文 1 、趋势分析 时间序列模式根据数据随时间变化的趋势预测将来的值。这里要考虑到时间的特殊性质，像些周 期性的时间定义，姻星瓣、月、季节、年等，不同的爵子如节骰鑫可能造成的彩晌，圈期本身的汁算方 法，还有一些需要特殊考虑的地方如时间前厉的掬关性( 过去的事情对将来有多大的影响力) 等。只有充 分考虑时间冈素，利用现有数据随时间变化的一系列的值，才能更好地预测将来的俄。 如何处理时间序列数据，矧前一般有4 种主要的变化或成分用了u = 特化时间序列数据： 1 ) 妖期或初始变化：它用于反映一般变化方向，其时序图如图2 1 所示，它描述了一个点随时间 变化的情况，它反映的燕在较长时间间隔的数据变化。这种变化反映为一种趋势线或趋势曲线，在闰 21 中攫虚线表示。 2 ) 锤强变动或罐环变化：主要指摇琢性朗趋势线或曲线在长期时阉内呈摆动迹象，它可以是也 可以不是周期性的。即在等时间间隔之间，循环不需要沿着同样的模式演进。 困2 1 序数据 f i g2 1 t i m e - s e r i e sd a t a 3 ) 季节变动或季节性变化：是指同一或近似同一的模式，在连续几年的有关月份期间重复出现。 4 ) 非瓶赠或随机变化：它反映的是由于簸耄f 或偶然事俸 | 起的零星辩序变纯。 时序分析也可以指将时序分解为翦磊的4 个基本运动的分析。这样，时净变量y 可表现为：y = t * c * s * i 或y = t c + s + i ，其选择通常是凭经验的。其中t 、c 、s 、1 分别表示趋势、循环、季节性、非规则变量。 通过对趋势、循环、季节性、非规则成分的变动的系统分析时，人们可以在较合理的情况下，制定出 乏 期或短期的预测( 即预报时序) 。 2 、时序分析中的相似搜索 通常数据库的查询是要找出符合查询的精确数据，而对于时序分析中的相似搜索蹩找出与给寇查询 序列鳋接近筋数据序列。子序列匹配是找出与绘定序列攘似舱所有数据序列，两整体廖列羁配是找出彼 此间捆似的序列。进行时序数据的相似分析时，通常采用欧式距离作为相似性计算的依据。当它们之间 存在足够多的l i ：重叠的相似予序列的时序对时两序列被认为是相似的。它有几种基本方法： 1 ) 数接：变换方法，从时间域变换到频率域，这是由1 ：许多信号分析的技术需要数据来【! _ 频率域e 常见的独立1 ：数据的变换是离散缮立n 。变换( d f t ) 和离敬小渡变换( d 酣) 。 7 时间序列数据相 啦模式控搦的研究与应用 对子序列疆配辩，每序剐首先被分割为茛度为w 韵窗口“片断”。每个序列映射为特征空间中的 一个“线索”。对予序列分析时，把每个序列的线索划分为“予线索”，每个由最小边界矩掰表示。 2 ) 增强搬似搜索方法，处理偏移邪振幅中盼阅隙和差异。大郝分实际应用并不一定要求匹配的子 序列在刚司轴上完全一致，即子序列对具有同样的形状，但在序列内存在间隙或在偏移或振幅中存在著 异，我们也可以认为它们是匹配的。能够在这种差异的情况下仍能判断其相似性的，是一种改进的相 似模型，它是兔许崩户或专家对一些参数进 说明，如涝动窑羽尺寸，相叛范国的宽度，最大阉骧。匹 配片段等等。处理偏移与振幅的间隙和差异的相似搜索的执行步骤为：原子匹配( 找出所有无间隙的较 小相同窗口对) 、窗口结台( 把相同窗口结合，形成大的相似子序歹对，其中允许在原予匹配问有间隙) 、 子序列捧序。 3 ) 相似搜索的索引方法，为提高在大型数据霹中进行相似搜索的效率，人们提赉了备静索；l 的方 法。如r 一树，r i 一树等方法，它们用于存储最小边界矩形以加速相似搜索。另外。提出了k d 一8 树的方 法，它用于在高维点上提高空间相似连接的速度，还提出后缀树等。 3 、序列模式挖掘 序列模式挖掘是指挖掘相对事件或其他模式出现频率高的模式。由于很多商业交易、电传记录、天 气数据和生产过程多是事件序列数据，在针对目标市场、客户设引、气象预报等豹数据分析中，序列模 式挖掘是报考用途f 勺。 1 ) 窿列模式挖掘的情形和参数 许多有关序列模式挖撅的研究主要针对符号模式，因为数字益线模式通常属于统计时序分析中的趋 势分析和预测范畴。 对于序列模式挖掘，存在些参数，其取值如何。将严重影响挖掘效果。第一个参数是时间序列的 持续时间t 。序列模式挖掘因此是限制在特定的持续时间内的挖掘。第二个参数是事件重叠窗口w a 在 雍定时阀瘸期内出蘸的一维事件，可| 鬟撬为某一分析串一起出磷的事件。第三个参数是被发玟的模式中 时间之间的事件的间隔i n t 。 2 ) 序列模式挖捌的方法 关联规则挖掘中采用的a p r i o r i 特性可以用于序列模式的挖掘，因此，序列模式挖撅的大部分方法 都采_ = | j 了类a p t i o r i 算法的变种。另一种挖掘此类模式的方法是基于数据库投影的序列模式生长。 4 、删期分析 周期分析琏指对周期模式的挖掘，即在时序数据库中找如雯复出现的模式。 用删模式挖 的问趔可分为三类： 1 ) 挖掘全周期模式，这里每一时问点都影响( 精确或近似) 时序上的循环行为。 2 ) 挖掘部分周期模式，它描述在部分时间点的时序周期a r 瓣她工监大学磺圭学挝论文 3 ) 挖掘循环或厢期芙联规则，这种规脚楚篇期出现的时闻韵关联规到。 2 - 2 3 相似模式挖掘问艇 镫索时闾序弼褶毫鬟模式的过程又称为时闯序列耜毂佳搜索。 时间序列捅似性搜索问题可以概括为：给定搜索序列s 。待搜索序列q ，相似往度量函数s i r e 0 ， 裙似豫查拄策赂蠡n d 昏耀像瞧羧索瓣过程就是在镑攘索痔确q 孛，援出瑟窍与搜索痔戮s 鞠像的旁列 集合r ，即1 4 r = x e e ，f i n d ( s i m ( s ，x ) ，妫 ( 2 ， ， 飙( 21 ) 式我们可以漪出， 砖阀序列相似性搜索闯麓主要涉及三个方薤的f l j l 魃，鄹樱儆性度鬣、挫豢 麴存接菠臻瞄及燕找静宪餐蛙# 1 。 1 、相似性度量问题 捌织凌量煞衡量嚣个痔剜裰毫葵鲍菝攒辩标雄，蹩耪骰瞧搜索阏麓鳇基臻。但是不是任嚣条辫都裁 成为蝴议度量靛标准，鞠似度量必须满足个条件，那就是骶序列通过该相似度量计算的结果要小于等 于该辨序列真赏 莹况 = l 经同撵计舞得到豹僮。比如，我们以欧几里德距离公式为倒，两序列a ，b 的欧 几里德距离必缬小于等于序列a ，b 之间本来的蹶离，即dc e u c l i d e 。，( a ，b ) - 基于对阍序列辨膨特征鹣糖叛发攫 萋奉恿想是楚窿勰分袋线拣袭示及符号证。按绘定麴辩阀穗凄对穿疑蠡袋避嚣线髓模按，捐销游点 埘谢线段连接，根据序列榴到折线，将折线上每一髓线段用一个代表矮形状的符号表示。这样就托序剜 麓襁戳薅题饕诧或餐号阉戆裙锻霹戆了。 2 、棵似憔搜索的存储策略 瞧 二捂敷镬! 接索 耋：撞零会露淹饕丈鬟瓣诗霎；逡释葑静存赣蒙路罐强天大挺毫搜索数率。鬻跫翡多 绒数据存储结构有：v p 一树、r 树及其各葶申变化( 如r + 。树、鼢树) 、b d 树、融d b 树、g r i d 文件等1 ”j 。 h r 。 _ 粤 卜 蘅2 3 t 2 i 几种常用的多维存持嫱稳 f i g2 3 1 i 2 1 s e v e r a lc o m m o nm u l t i d i m e n s i o n a ls t o r a g es t r a c t u r e 瞄2 3 中辩一行从左至右依次是r * 树、k _ d 樾，第二舒从左到右依次逛g r i d 文译耥v 口树对空褥或 数爨嶷势裁剽缝织方式 ”1 。 ”f 面详绷介绍r + 一树。r + m 树是r 树的一种敬进结构，r 树是b 樾在察维对象存档主麴扩攫，是 i $ 平鬻挝。r 璜蠡孛簿精熹释峙络纛缀或。鼗攥对象彝麓在畸续煮，每争孛淹结煮粼饩表一令篷器嚣 域，该矩形谯空间上涌蔬了此燃点的各个下级结熙对应的矩形l ”l 。 r + 辩丰鞋对于r 誊l 渡避之箍主要巍予辩孛璜戮结纛翁方法霸蘩赢翘存臻寅姣是否育霆豢嚣巾方瑟。 其傣采说，其一，拯入糯结点豹方法基零上和r 樾是相同的，改进舟勺地方程予遇到端点发生溢出时， r + 树中会雠留距该漱出结点娥近m b r ，其他缩点由插入端法重新黼入。黧：= ，r + 一树的存储懿梅中缭 点瓣没有委黎。横对于鼗- 楗，r + 褥存销翳构中龆分戆蹩数耀空溺t 往往j l 个空瓣弱嚣考覆蓑一个m b r ， 1 i 一 堕堡矍型鏊篓塑丝壁茎笙燕壁堡! 塞星壅翌 按照r + _ 树基本原理这个m b r 会被这几个空间分为儿部分。这样在进行搜索时，只能沿着个方向进 行搜索。由于r + - 树在r - 树的基础上进行了这两点改进，使得插入、删除结点和结点的搜索过程的效 率都得到了很大的提高。 r + 一树结构分为叶结点和中间结点。叶结点项：( o l d ，r e c t ) ，代袭一个具体的m b r 。其中。o i d 表 示m b r ，r e c t 表示m b r 的坐标。中间缔点项：( p ，r e c t ) ，代表个区域。其中p 袁示指向f 级结 点的指针，r e c t 表示该结点涵盖豹区域豹坐标”1 。 r + 一树具有一f 垂的性质：( 1 ) 对中蚓绥点豹每一项，r e c t ) ，p 蜃指向的f 级结点的对应的区域当且 仅当被此r e c t 赝完全包含；( 2 ) 一个中闼结点的任何项涵盖的区域阈不重叠；( 3 ) 根结点至少有两个子 孙，除非它是叶结点；( 4 ) 所有的叶结点在同层上。 基于r + 一树相似性搜索的具体方法：每个非叶子结点均与搜索窗口q 取交集，如果该非叶子结 点与q 有交集，那么继续比较该非叶子结点相应的下一级结点是否与q 有交集，如果依然有就继续向卜- 一级比较，g _ n 日l 孑结点。然后输出时予结点中与q 相交部分豹全邦结点。在这个过程中需要说明豹一 点是如果上述的比较过程没有到达叶予结点就与q 无交粲了，那么其下面所有结点都无需再同q 比较。 在遇到这种情况时无需比较所有的结点，可以大大提高搜索效率。 下面描述r + 树搜索避程的算法f 1 6 】： s e a r c h ( w ，r o o t ) i f ( r o o ti sal e a f n o d e ) f o r ( i = 0 ；i e i r ) r e