（计算机软件与理论专业论文）时间序列数据挖掘中的若干问题研究.pdf

摘要 摘要 时问序列是数据挖掘中一种重要的数据类型，在现实世界许多领域中广泛存 在，如股票价格，商品销售数据，气象数据等。且随着时间推移，这类数据的存 储规模呈现爆炸式地增长。如何对这些海量时序数据进行有效的知识发现，挖掘 其内在的各种变化模式，是一个挑战性的、具有重要理论意义和实用价值的课题。 本文在分析时间序列数据特点和实际应用需求的基础上，针对时间序列的数据挖 掘中的一些关键问题进行了研究，具体包括特征模式挖掘、相似性模式查找、多 维时间相似性查找等方面，主要的工作集中于以下三个方面： 针对时间序列的特征模式问题，采用无须生成大量候选模式集的互关联后继 树挖掘算法。该方法基于重要点的序列分段化算法和相对斜率的局部符号化方法， 既减少了计算复杂度，又避免了噪声的影响。在算法实现上，根据序列特征模式 的有序性和重复性，极大地提高了挖掘效率。实验表明，这种方法的挖掘结果是 一种图形化的描述，具有明确的实际含义，便于在实际中应用。 针对时间序列相似性查找问题，采用海量全文索引技术互关联后继树索 引模型对时间序列进行挖掘。该方法基于重要点分段技术，利用分段动态弯曲距 离作为相似性度量，即保证了度量的鲁棒性，又减少了计算复杂度。研究证明文 中的方法不仅提高了结果的准确性，也体现了传统方法所没有的优势。不仅保证 查找的结果不会出现任何f 确结果的丢失和错误结果的引入，而且也显示出比传 统方法具有明显的优势。 针对多维时间序列相似性查找问题，采用了一种可应用于多维时间序列的快 速相似搜索方法。该方法将序列( 子序列) 的局部变化特性与检索结构( k d 树) 结合起 来，使得在搜索k d 树的同时实现了序列( 子序列) 的局部变化匹配，这种方法既能 体现序列( 子序列) 间的整体距离关系，又能体现它们自身的局部变化，从而极大地 提高了查询效率和正确率。实验证明了文中算法的有效性和可行性。 关键词：数据挖掘，时间序列，动态弯曲距离，s i r s t 摘要 a b s t r a c t t i m es e r i e si sak i n do fi m p o r t a n td a t ae x i s t i n gi nal o to ff i e l d s ，s u c ha ss t o c k ， b u s i n e s sd i s t r i b u t i o n ，w e a t h e r , e t c ，a n di t ss t o r a g es i z ew i l lb l o wu pw i t hp r o c e s so ft h e t i m e i ti sac h a l l e n g i n gt u s kt or e s e a r c ho nh o wt od i s c o v e r yv a l u a b l ek n o w l e d g ei n s u c h l a r g e s c a l et i m e s e r i e sd a t a b a s e ，ar e s e a r c hh a v et h e o r e t i c a l s i g n i f i c a n c ea n d p r a c t i c a li m p o r t a n c e i nt h i st h e s i s ，r e s e a r c ho ns e v e r a li m p o r t a n tt e c h n i q u e si nt i m e s e r i e sd a t am i n i n gw e r ec a r r yo u tb a s e do na n a l y s i so fc h a r a c t e r i s t i co f t i m es e r i e sd a t a ， c o n s i d e r i n gi t sp r a c t i c a la p p l i c a t i o nr e q u i r e m e n t s w h i c hi n c l u d et h r e ea s p e c t s ：f e a t u r e p a t t e r n sa n dr e l a t i o n s h i pp a t t e r n sm i n i n g ；s i m i l a r i t yp a t t e r ns e a r c h ；s i m i l a r i t ys e a r c hf o r m u l t i d i m e n s i o n a lt i m e s e r i e s a i ma tt h er e s e a r c ho fm i n i n gf e a t u r ep a t t e r n si nt i m es e r i e st r a d i t i o n a ld a t a m i n i n go ft i m es e r i e sw e r er e v i e w e dh e r e s e v e r a lt i m es e r i e ss e g m e n t sm e t h o d sw e r e c o m p a r e da n da n a l y z e di nt h i ss e c t i o n q u a l i t yo fs u b s e c t i o na l g o r i t h m i cd e t e r m i n e st h e s h a p eo ff e a t u r ep a t t e r n s ，a n di m p a c t sf i n a lp u r p o s eo fd a t am i n i n g i n t e r - r e l a t e d s u c c e s s i v et r e e s ( i r s t ) m o d e lm e t h o dw a su s e di nt h ep r o c e s so ff r e q u e n tp a t t e r n s m i n i n go ft i m es e r i e s t i m e s e r i e sa r es e g m e n t e db a s e do nc r i t i c a lp o i n t sa n d s y m b o l i z e di nt e r m so fd o m a i nk n o w l e d g ea n dr e l a t i v es l o p eo fe a c hl i n e a rs e g m e n t b a s e do n r e p e t i t i o n a n ds e q u e n t i a lo ft h ef e a t u r e p a t t e r n o f t i m e s e r i e s ，t h e c o r r e s p o n d i n ga r i t h m e t i cc a nf i n df r e q u e n tp a t t e r n sf r o mm u l t i p l et i m es e r i e sw i t h o u t g e n e r a t i o nl o t so fc a n d i d a t ep a t t e r n s ，e f f i c i e n ta n du s e f u l e x p e r i m e n t a lr e s u l tc o m e so u t a sag r a p h i c a ld e s c r i b e s ，e a s yt oa p p l yi np r a c t i c e s i m i l a rp a t t e r ns e a r c ho ft i m es e r i e sw a sr e s e a r c h e di nt h r e ea s p e c t s ：s i m i l a r i t y m e a s u r e m e n t ，s t o r a g ec o n f i g u r a t i o na n dm a t u r i t y b a s e so ni r s ti n d e xm o d e l ，s e g m e n t d y n a m i ct i m ew a r p i n g d i s t a n c ew a su s e da s m e a s u r e m e n t ，c o m b i n a t i o nw i t h s e g m e n t a t i o nt e c h n i q u eb a s e do nc r i t i c a lp o i n t s ，f e a t u r ew a se x t r a c t e df r o ma l l s u b s e q u e n c e s ，a n dt h e nt i m es e r i e sa r ec o n v e r t e di n t om e a n i n g f u ls y m b o ls e q u e n c e si n t e r m so ft h es e g m e n t sf e a t u r e sa n dm a t hc a t e g o r i z a t i o n s i m i l a r i t yp a t t e r nw a s l i 摘要 s e a r c h e di nt i m es e r i e su s i n gf u l lt e x ti n d e xt e c h n i q u e t h em e t h o di sp r o v e dn oa n y f a l s ea l a r m so rf a l s ed i s m i s s a l s a n de x p e r i m e n t ss h o wt h a ti th a sm o r ee f f i c i e n ts e a r c h a n da l l o w sd i f f e r e n tl e n g t h sm a t c h i n g ，c o m p a r e dw i t ht h ep r e v i o u sm e t h o d s m u l t i d i m e n s i o n a lt i m es e q u e n c e sa r ea ni m p o r t a n tk i n d o fd a t as t o r e di nt h e i n f o r m a t i o ns y s t e m s i m i l a r i t ys e a r c hi st h ec o r eo ft h e i ra p p l i c a t i o n s o nc o n s i d e r i n g s h a p ef e a t u r e so fm u l t i d i m e n s i o n a lt i m es e q u e n c e s ，ak i n do ff a s ts i m i l a r i t ys e a r c h m e t h o dw a su s e d ，t h es h a p ef e a t u r e so fs u b s e q u e n c e so rs u b s e q u e n c e sa r es u b t l y c o m b i n e dw i t hs p a t i a li n d e xs t r u c t u r e ( k dt r e e ) ，w h i c hm a k e si t p o s s i b l et om a t c h s h a p eo fs e q u e n c e so rs u b s e q u e n c e sw i t h o u ta n ye x t r ac o s tw h i l i n gs e a r c h i n gt h et r e e t h ee x p e r i m e n t a lr e s u l td e m o n s t r a t e st h a tt h ea l g o r i t h mi se f f e c t i v ea n de f f i c i e n t k e y w o r d ：d a t am i n i n g ，t i m es e r i e s ，t i m ew a r p i n gd i s t a n c e ，s e q u e n c e i n t e r - r e l a t e ds u c c e s s i v et r e e s i i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：雾臣! ! ! 蓦 指导教师签名： w p g 年多月g 日2 勿。占年么月驴i i 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：耄pf j 、芳 ( ) g 年石月孚日 第一章绪论 第一章绪论 1 1 课题研究的背景及意义 随着计算机软、硬件的进步，人们利用信息技术产生和搜集数据的能力大幅 度提高。数以千万计的数据库被用于商业管理、政府办公、科学研究和工程开发 等方面，收集工具的进步使人们拥有了海量的数据。面对这些数据，急需一些新 的工具和技术，解决由此带来的“数据丰富，信息贫乏”的问题，数据挖掘技术 应运而生。所谓数据挖掘( d a t am i n i n g ) i l j 就是从大量的、不完全的、有噪声的、 模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。它是利用统计学，机器学习，神经网络，数据库，网格 等各个学科领域的先进技术对大量历史数据进行分析处理，从中提出隐含的事先 未知的和有价值的知识，为人们的分析决策提供更高层次的技术支持，是知识发 现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，简称l d ) 中最核心的部分【卜5 1 。其目标是为 了满足用户需求，自动处理大量的原始数据，从中识别重要和有意义的模式，并 将其作为知识加以表达。各种类型的数据都可以作为数据挖掘的对象【2 删，而且 一些特殊类型数据在其中所占的比重越来越大，这就产生了对时间数据库、空间 数据库、多媒体数据库等面向特殊应用的数据库系统的研究。 随着计算机信息系统的同益普及，大容量存储技术的发展以及条形码等数据 获取技术的广泛应用，人们在日常事务处理和科学研究中积累了大量的各种类型 的数据。在这些保存的数据中，绝大部分都是呈现时间序列类型的数据。例如金 融证券市场中每天的股票价格变化；商场、超市的销售信息；气象预报研究中， 某一地区的每天气温与气压的读数；电力系统的用电信息；心电图中包含的信息， 以及在生物医学中，某一症状病人在每个时刻的心跳变化等等。而且时间序列也 是反映事物运动、发展、变化的一种最常见的图形化描述方式，时间序列在社会 生活的各个领域中都大量广泛存在。分析研究时间序列的重要源动力来自于这些 领域超容量数据的获得，挖掘这些海量的时间序列背后蕴涵的价值信息，揭示事 物发展变化的内部规律及相互作用关系，为正确认识事物和科学决策提供依据等 具有重要的实际意义。 第一章绪论 时间序列分析最早是传统概率统计学的一个重要研究领域，其研究目的在于 预测时间序列的未来发展情况，分析数据集合，建立数学模型，进行模式结构分 析和实证研究等，经过数十年的研究，已奠定了自己的理论基础l l 2 】。传统的时 间序列分析着重研究具有随机性的动态数据，研究方法着重于全局模型的构造。 常用的方法有自回归滑动平均( a r m a ) 等【3 1 。a r m a 方法是一种线性分析方法， 它要求常用的方法要求时间序列必须是平稳的，并要求模型所产生的时间序列与 时间预测序列的误差互不相关并呈正态分布。而对于绝大多数实际系统所产生的 时间序列( 如股市价格综合指数) 来说，这种平稳性假设以及误差的互不相关性和 正态分布往往很难满足。此外，传统时间序列分析的任务仅仅是对系统整体行为 的预测和控制。然而在实际分析中，往往需要对时间序列局部特征进行分析，如 发现经常出现变化模式，比较不同序列在某段时问内，其运动变化是否相似等等。 这些分析方法在许多应用领域中同样具有重要的意义。例如在整个证券市场中， 找出股价与相似变化的股票序列；在气象预报分析中，对于气压序列，需要找出 在一段时间内那些是经常出现变化的模式，给定一个气压序列和气温序列，找出 这两个序列之间有那些是经常出现的相互关联的变化的模式等。 显然，对于上述时间序列应用分析问题，传统的时间序列分析方法己不能适 用。为此，需要借助一些新型的方法和技术，而最近发展起来的知识发现与数据 挖掘技术为这一问题的解决提供了一条切实可行的方法和途径。因此有关时间序 列分析的研究一直以来就受到了许多研究人员的广泛关注，成为一个具有重要理 论和实用价值的热点研究课题。 本文主要将数据挖掘的思想和方法引入时间序列分析中，围绕时间序列数据 的特征模式挖掘、时间序列相似性查找、多维时间序列相似性查找等挖掘技术展 开研究，重点研究了基于互关联后继树的查找方法，进行时间序列相似性搜索， 利用相似模式进行时间序列预测等一系列关键问题。 1 2 国内外研究现状 时间序列数据挖掘研究主要包括：趋势分析、相似性搜索、与时间有关数据 的序列模式挖掘和周期模式挖掘等【4 1 。时间序列数据挖掘通常对序列的局部特征 2 第一章绪论 更感兴趣，包括相似性度量、相似查找、常见例外规则发现、概念模型提取， 序列分段、序列索引和查找、序列聚类、序列分类、时问序列关联规则等等，内 容十分丰富孓8 1 。 对于时序数据库，特别是一次无法装入内存的大型数据库，如何进行快速而 准确的相似搜索，其重点在于：如何表示时间序列、如何度量序列间的相似性以 及如何对数据库进行检索。 序列表示的主要作用是降维即解决维度的困扰( d i m e n s i o n a l i t yc u r s e ) 、提取序 列的特征等。常用的方法是：先做变换，保留能量最高的前几个参数，然后用多 维索引作为数据结构来存储。常见的变换方法有离散傅立叶变换( d i s c r e t ef o u r i e r t r a n s f o r m ，简称d f t ) f 9 1 0 】和离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m ，简称 d w t ) 1 1 ，奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，简称s v d ) 1 2 】、分段法【1 3 】 等。d f t 能将时间序列转换到频率域，取前几个较强的傅罩叶系数作为序列的 表示以达到降维的目的。d f t 适合那些自然发生的正弦信号，但不适合表示不 连续间断的信号。在d w t 方法中，h a a r 小波变换是最常用的。但由于基函数不 光滑，h a a r 小波采用阶梯状的结构近似地模拟信号。因此，仅用少数的h a a r 小 波变换系数是不能很好地近似连续函数的，所以需要保留的小波系数的数目必须 比较多。s v d 是一种依赖于数据内容的降维方法。通过计算给定数据集的特征 值和特征向量，s v d 将数据进行转换使得大多数信息集中在某些维上，取数据 在这些维上的坐标作为原数据集的压缩，它的主要缺陷是当数据改变时，特征向 量需要重新计算因此，s v d 不适合动态变化的数据库。分段法主要通过将序列 分段，取每段的特征( 例如，极值点、变化趋势等) 组成序列的特征表示。 比较两个序列的相似性一般采用距离公式求得序列间的距离，当距离越小 时，说明两个序列越相似( 除最长公共子序列以外) ，反之亦然。常用的距离公式 有：欧氏距离 9 , 1 0 】时间弯曲距离 1 3 , 1 4 1 和最长公共子序列f l o n g e s tc o m m o n s u b s e q u e n c e ) 1 5 j 等。欧式距离的主要优势在于计算复杂度低，并在正交变换下保 持距离不变。但由于欧氏距离对数值的扰动十分敏感，易受噪声和时问轴上偏移 的影响，直接在原始数据上计算欧氏距离的相似性是不合适的。常见的做法是通 过位移变换、幅度变换、去线性趋势、去噪声等方式，对原始时间序列进行预处 理，然后再计算距离，可以得到较好的结果 1 6 】。欧氏距离或类似距离的定义在某 3 第一章绪论 些应用中还是显得不够灵活因此还有基于变换的相似度度型1 7 1 。这种方法是通过 牺牲精确度来换取运算速度的，在大规模数据挖掘中有重要意义， 另一种相似度量方法是将连续值的属性离散化为符号序列，再用符号匹配方 法计算相似度。a g r a w a l 1 8 】等人定义了“u p ”、“d o w n ”、“s t a b l e ”等形状，用以表示 时间序列在某一个时刻的变化；并把连续值的属性转换成分段的离散值，距离计 算就变成了快速的匹配过程。采用相似的原理，把连续值的时间序列转换成有序 符号的序列。或者将时间序列分段，时间序列之间的相似度用一个产生式概率模 型来度量，两条时间序列的相似度是它们的分段之问的相似度之和；分段之间 的相似度由幅度相似度和变形相似度组成；这两个相似度又分别表示成指数分布 的形式。 除了时间序列之间的相似度定义，还有时间序列到一个类( c l u s t e r c l a s s c a t e g o r y l 的定义，这种定义在聚类、查询、轮廓化等方面使用较多。文献【2 l 】专 门为聚类提供了一个索引结构，时间序列先用混合高斯模型聚类并存储下来，查 询时先计算查询序列到各个聚类的相似度( 似然函数值) ，然后再在最相似的聚类 里面查询相似时间序列。关于贝叶斯聚类的文章【2 2 2 3 】里，都采用了产生式概率模 型，用期望最大算法( e m ) 【2 4 ，2 5 】迭代求出类模型和点到类的分配情况。这种方法 很容易扩展到时问序列的聚类。 对时间序列进行检索，常用的结构有：k - d 树1 1 9 1 ，r 树【2 0 l 及其改进等。r 树 是一种存储多维空间对象的平衡的动态索引结构，主要以最小边界方形 ( m i n i m u mb o u n d i n gr e c t a n g l e ，简称m b r ) 为检索对象。r 树是一种平衡多叉树， 它通过逐级缩小搜索的空间范围来定位要找的对象。r 树的改进主要体现在对结 点的m b r 覆盖区域、m b r 重叠区域和m b r 的边缘长度等方面进行优化，从而 提高查询效率。k - d 树是一种多维的二叉查找树，支持基于多关键字的二叉查找 树，同时也可以用来存储k 维空间中的数据点【2 0 1 。 由于时间序列特征的多样性，实现的方法各有差异。以下是这一方向上国内 外具有代表性的研究： a g r a w a l 2 6 j 等人提出完整的全序列匹配问题的相似性查找方法。采用离散傅 立叶变换将时域序列映射到频域上，即每个时间序列经d f t 变换后被映射为较 低维频域空间的一个点，用这种方法降低了数据的维数。然后利用r 树存储和 4 第一章绪论 索引序列的特征向量。这种方法由于d f t 变换的缺陷，即只有频域信息而没有 时域信息，因此并不能准确的判断两序列是否相似。 f a l o u t s o s ，r a n g a n a t h a n 和m a n o l o p o u l o s 对【2 6 】的方法进行扩展，使其可用 于子序列匹配问题。他们首先采用分割窗口对原始序列进行分割，得到等长度的 时间序列片段，然后在对其进行特征提取以将其映射到一低维特征空间，这一过 程将在特征空间中产生一条轨迹，采用最小边界矩形来对这些轨迹进行表示，采 用r 树依次对各个m b r 进行索引。该方法可以保证不会产生错误匹配，但可能 会产生漏匹配。该方法对查询序列有最短长度的限制f 不能短于分割窗口的宽 度) ，此外，当查询序列较长时( 超过分割窗口的长度) ，匹配序列必须先被分割然 后再合并，这显然影响了匹配的速度。 h e i k k i m a n n i l a 和p i r j or o n k a i n e n l 2 7 】对时间序列中的相似性比较问题进行了 研究，提出了一个描述时间序列问相似性的距离度量一编辑距离，该距离度量的 提出是基于以下的观察，即两个序列越相似，则将其中的一个序列变换( 通过插 入，删除等操作1 成另一个序列所要做的功就越少。他们为时问序列的匹配定义 了一系列操作( 如插入，删除，移动等) 以及一个衡量这些操作所需要的代价函数， 时间序列间的相似距离就可以定义为将一个序列变换为另一个序列所需要操作 的代价之和。然后，通过计算编辑距离来判断序列问相似问题。与动态时问弯曲 ( d t w ) 方法相似，该方法的缺陷是计算复杂度比较高。 b e l ab o l l o b a s ，g a u t a md a s1 2 8 】等人主要研究时间序列相似性问题中的异常和 伸缩问题，提出了一族确定性的和随机的算法来计算序列间的相似性，该方法利 用计算几何中完好分离几何集的一些特性，取得了较好的实验成果。 k e o g h l 2 9 】提出一种纯图像的方法来实现时间序列相似匹配问题。具体方法是 由于时间序列多为曲线或折线，因此，首先将曲线分段线性化，再根据这若干直 线段的特征( 倾角、斜率等等) 作为相似比对的对象来进行相似性查找。这种方法 可以克服有些相似度量标准在时间序列存在振幅伸缩、水平偏移、垂直偏移、不 连续等干扰时不能准确进行相似查找的弊端。 e a m o n nj k e o g h 3 0 j 提出了一个时问序列相似性匹配方法，该方法的主要贡 献在于提出了一个更为合理的时问序列线性化分段拟合算法，使得该方法对于噪 声干扰，水平偏移，振幅伸缩和水平伸缩具有良好的鲁棒性。 第一章绪论 e a m o n nj k e o g h 和m i c h a e lj p a z z a n i 2 9 3 0 】提出了一个在大时间序列数据库 中实现快速相似性搜索的索引算法q t b i n d e x i n g ，该算法首先创建一些箱子， 具有相似形态的时间子序列被放在同一个箱子中。对于每个箱子，可以很快地计 算出给定查询与箱子中最相似元素之间距离的下界。这一下界使得可以首先对最 相似的那些箱子进行搜索，从搜索空间中略去那些不相似的箱子，而不用逐一比 较箱子内的子序列。由于不必对箱子中的每一个元素进行比较，从而大大加快了 检索速度。 这些方法虽然在某些方面取一些进展，但是可能忽略了对另一方面的影响。 如在索引上有较好的查询效率，但是其在相似性度量上却有不强的鲁棒性，而采 用了较强的相似性度量( 如w t d 和相关性反馈等) ，却又减低了检索的效率。 1 3 本文的主要工作 根据前面对国内外时间序列挖掘与相似性研究现状的分析，不难发现目前的 研究在如下五个方面问题没有得到很好的解决： ( 1 ) 时问序列挖掘大部分的研究成果是基于a p r i o r i 算法，该算法最大的缺陷 就是在挖掘过程中必须生成大量的候选模式，这大大影响了挖掘效率； ( 2 ) 在挖掘的目标上，大多数是针对单个序列变化的特征模式挖掘，而对于 多个序列之间相互关联的变化模式则考虑较少； ( 3 ) 在时间序列相似性查找上，虽然目前常用的分段的方法来表示序列具有 更强的优势，但是在这种情况下如何进行海量索引却没有得到有效的解决； ( 4 ) 在相似性查找的任务上，大部分的研究也同样主要针对静态序列的查 询，而对于动态时间序列的在线模式的相似性查找的研究关注得比较少； ( 5 ) 此外，在实现技术上，大部分的时问序列分析系统只能提供某种单一的 应用分析功能，把时间序列挖掘和相似性查找分割开来，至今还没有一个集成了 挖掘功能和相似性查找功能的时问序列分析系统。 这一现状构成进一步开展时间序列挖掘与相似性查找技术研究的动机。在进 行此项研究的过程中，人们始终坚持如下几个基本观点： 时间序列的挖掘过程应该有比较好的效率； 6 第一章绪论 挖掘结果的特征模式不仅具有图形化的形式，而且还应该有明确的实际 含义； 相似性查找算法应该支持海量的数据集； 相似性度量应该支持不同长度的序列比较，而且能适应序列在水平和振 幅上的伸缩，具有较好的鲁棒性； 相似性索引查找的效率应该比顺序扫描的方法具有明显的优势，而且还 应该保证索引查找的结果不应该有任何正确结果的遗漏； 最后，对于各种时间序列分析手段不应该是孤立地存在，在实现时应该 具有功能上的集成性和开放性。 基于上述观点，本文对时间序列挖掘与相似性查找的研究目标是：时间序列 的特征模式挖掘与模式的相似性查找是现代时间序列分析中重要的两部分，挖掘 出的模式可以指导今后分析时间相似性查找的目标。 针对上述研究目标，这里将对单序列特征模式挖掘、单模式相似性查询多维 时间序列相似性查询等几项时问序列挖掘与相似性的关键技术上展开研究： 时间序列特征模式的挖掘 时问序列不仅是数据记录的形式，而且也反映了事物发展变化规律。因此从 时间序列发现知识，首先要对每个时问序列变化的特征模式进行挖掘。时问序列 特征模式是时间序列变化的高层含义概括，因此它的挖掘不仅要有视觉上的图形 描述，而且还应该有明确的实际意义。由于时间序列取值的连续性和变化的波动 性，造就了它与一般的数据挖掘不同。因此需要对它进行分段，将以实数形式表 达的时间序列转换成以相对抽象的符号形式表达的符号序列。现有的时间序列分 段方法采用固定宽度窗口来分割是序列，很难确定一个合理的窗口宽度，使得所 有的时间序列片段能够描述时间序列的变化特征，这直接影响到最终挖掘知识的 有效性和可解释性。为此，根据时问序列的变化特点和人的视觉印象出发，采用 了一种基于重要点的时间序列分段方法。该方法抽取了时问序列的整体变化趋 势，避免了序列的噪声影响，简化了挖掘的过程，而且也使得最终挖掘出来的模 式更具有实用性。 其次，针对目前基于a p r i o r i 算法挖掘效率低的情况，在研究了时间序列的 7 第一章绪论 特性后，发现其与全文序列具有相同的特性，都具有元素的有序性和变化的重复 性。因此，可利用全文序列的索引技术通过查询手段来实现时间序列的挖掘，在 此基础上，采用了基于互关联后继树的挖掘算法。这种挖掘万法最大的特点是在 挖掘过程中，无需生成大量无用的候选模式，大大提高了挖掘效率。实验也表明 这种方法与其他方法相比，挖掘过程简单，高效，而且挖掘的效果也更具有实用 性。 时间序列相似性查找 挖掘出来的时间序列模式是需要在实际分析中得以应用，这种应用就需要对 该模式进行相似性地查找。目前时间序列的相似性查找，在相似性度量上要不是 基于欧氏距离，要么就是变换方法或采用动态时间弯曲距离，事实证明欧氏距离 在水平移动和振幅伸缩上具有明显的缺陷，而动态时间弯曲距离虽然弥补了以上 缺陷，然而它在计算时间上却是效率比较低的。此外，在查找索引上，也是缺乏 海量的索引技术。 为此，本文首先采用了一种基于分段的动态时间弯曲距离作为相似性度量。 这种分段采用重要点技术，即保证了时间序列分割的准确性，也降低了动态时间 弯曲距离计算的时间复杂度。然后利用时间序列与全文序列的相似性，采用了海 量索引模型的查找方法基于互关联后继树模型的相似性查找算法。该算法先 抽取各子段的特征要素，然后利用m a t h 数据分类方法，把序列转变成字符序 列，然后利用互关联后继树建立索引。在实现查找时，算法根据查找涉及的序列 的不同状态，进行时间序列分段和符号序列相似性度量的转换，确保了查找不会 有任何正确结果的遗漏。算法分析表明这种方法比较传统的方法要快。 多维时间序列相似性查找 多维时问序列是信息系统中一类重要的数据对，相似性搜索算法的研究是关 键问题之一的一个核心。比较两个序列( 子序列) 相似度的常用方法是：将序列( 子 序列) 转换成空间中的曲线，然后计算曲线问的欧几里德距离。这种方法的主要 缺陷是它仅考虑了序列( 子序列) 问的整体距离关系，而不能体现它们自身的局部 变化。针对此问题，采用了一种新的可应用于多维时间序列的快速相似搜索方法。 第一章绪论 该方法将序列( 子序列) 的局部变化特性与检索结构( k - d 树) 结合起来，使得在搜 索k - d 树的同时实现了序列( 子序列) 的局部变化匹配，从而极大地提高了查询效 率。 本文的内容围绕时间序列挖掘与相似性查找的方法与实现技术而展开的。其 总共分六章，具体内容安排如下： 第一章：绪论。阐述了课题的背景和意义。介绍时间序列分析的任务，引出 研究相关问题，并概述了国内外最近有关的研究动态，介绍了本文的主要研究内 容。 第二章：时间序列数据挖掘。主要介绍了时间序列数据挖掘的理论基础、主 要研究内容、应用和意义。之后详细介绍了时间序列相似模式挖掘的分类及相关 技术。 第三章：时间序列特征模式挖掘。首先介绍了传统的时间序列特征模式挖掘 方法，指出了它的一些不足之处，然后结合时间序列的特点和实际应用的需要， 采用了一种基于互关联后继树模型的时间序列特征模式挖掘算法。 第四章：时间序列相似性查找。首先分析了时间序列相似性查找所面临的 主要问题与关键技术等，然后在此基础上根据时间序列与全文序列的相互联系特 征，采用了一种基于互关联后继树模型的时间序列相似性查找算法，并且对该算 法作了理论和实验上比较分析。 第五章：多维时间序列相似性搜索。对多维时间序列相似性分析常用的方法 仅考虑了序列( 子序列) 间的整体距离关系，而不能体现它们自身的局部变化的缺 陷。提出了将序列( 子序列) 的局部变化特性与检索结构( k - d 树) 结合起来的方法， 并且对该算法作了理论上比较分析。 总结和展望。对全文的工作进行了总结，并对今后的工作提出了新的研究方 向。 9 第二章时间序列数据挖掘 第二章时间序列数据挖掘 时间序列数据挖掘通过对过去历史行为的客观记录分析，揭示其内在规律， 进而完成预测未来行为等决策性工作。时间序列数据挖掘是一种特殊类型的数据 挖掘，就是要从大量的与时间有关的数据中提取人们事先不知道的、但又是潜在 有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测。时间序列 挖掘是数据挖掘中的一个重要研究分支，有着广泛的应用价值。 2 1 概述 所谓时间序y i j ( t i m es e r i e s ) 就是将某一指标在不同时间上的不同数值，按照 时间先后顺序排列而成的数列。简单地说，时间序列是指按时间顺序排列的观测 值集合。如果通过单变量随机过程获得的信息，称之为一元时间序列；如果通过 多个变量描述变化规律的，称之为多元时间序列；如果该数据序列是连续的，称 之为连续时间序列；如果数据序列是离散的，则称为离散时间序列。例如对某一 过程中的某一变量进行x ( t ) 观察测量，在一系列时y l j t 。，t ：，t 。( t 为自变量，且 f 1 t ： ， 。 3 1 2 子段聚类 假设子序列墨与s f 的距离为d ，s ，) 。利用这种距离作为全部子序列的聚类依 据对全部子序列进行聚类，把忡) 分类成尼类型c 1 ，c 2 ，g 。对于每个类型，我 们用一个符号口。来描述，然后根据时间序列中毛属于某个类c 巾) ，就用该类所对 应的符号口巾) 来替换。这样通过尼个字符集把整个时间序列s 转变为离散形式的 字符序列d ( s ) = a j o ) , 口m ) ，口m 一州) 。 事实上每个字符口。代表了一类序列的基本形状，这些基本形状图形构成希 望挖掘的模式规则。图3 1 给出了一此基本形状酐i 例子。至于序列之，间的距离计 第三章时间序列特征模式挖掘 i 。 z i 逆 八 i ； 原始序y l j = ( 1 ，2 ，1 ，2 ，1 ，2 ，3 ，2 ，3 ，4 ，3 ，4 ) 聚类后的基本图形 窗口大小= 3 ；符号化序歹t j = ( a l ，a 2 ，a l ，a 2 ，a 3 ，a l ，a 2 ，a 3 ，a l ，a 2 ) 图3 1 基于基本图形化的模式例子 算，算法采用基于欧氏距离公式。即 d ( x , y ) ：( ( x f y f ) 2 ) j ( 3 1 ) 其中，x = ( 五，x ：，x n ) ，y = ( y l , y ：，y 。) 此外还可以采用一些其他的一些 改进的距离计算公式【4 0 ，4 ，而关于聚类算法采用一种典型的贪心算法1 3 9 1 。任取 w ( s ) 中某点鸟作为中心，然后计算任意其它p 点g 与的欧氏距离d ( p ，q ) 。如果 d ( p ，q ) d ，则把p 加口所在的类中，否则创立新的一个类。如此继续，直到所有 w ( s 1 中的子序列分类完毕为止。此外，同样也可以运用其他聚类算法实现上述符 号化聚类。 3 1 3 规则模式发现 对上述符号化的时间序列采用一般意义上的序惯模式挖掘算法，如a p r i o r i 算法【2 6 】来发现时间序列基本形状模式规则。这种模式规则可以定义如下：若基 本图形a 出现，那么在t 时段内基本图形b 也会出现，记为a b 对于给定 符号化序列o ( s ) = ( a l 口：，a 。) ，图形模式a 的频繁度f ( a ) 为a 在d ( s ) 中出现 的次数，其相对频繁度为f ( a ) n 。规则a b 的信任度c 口b ) 是在t 时段 内a 之后接着出现b 的百分数，即 c ( 抽) = 等铲 ( 3 2 ) 其中f 似，b ，t ) = ila i - - a b e a i + 1 ，a i + r - 1 】。 八v n 也 幻 第三章时间序列特征模式挖掘 计算这样规则的频繁度与信任度比较简单，只要通过扫描整个序列就可以得 出。下图3 2 是算法挖掘出来的图形模式：a 多1 2b 图3 2 算法发现的频繁模式 方法讨论：该算法首先对序列进行符号化转变，通过序惯模式的挖掘思想来 发现时间序列图形化的变化模式，这与以往利用r o u g h 集理论进行时态模式的 挖掘相比，在挖掘结果上更有感性认识，具有新颖性。然而也应该看到该方法仍 然存在如下一些缺陷： 时间序列的基本图形要受到时间窗口大小的影响，这种等长度的子序列 划分很容易分割，破坏时间序列重要特征； 因为简单的欧氏距离并不能刻画时间序列的相似性，影响了聚类方法的 效果与效率； 基于a p r i o r i 算法的模式规则挖掘，由于其需要生成大量的候选模式，影 响了其在海量时间序列中