论文__时间序列部分周期模式挖掘算法研究.pdf

硕士学位论文 时间序列部分周期模式挖掘算法研究 r e s e a r c ho ht i m es e r i e sd a t a m i n i n g a l g o r i t h m o fp a r t i a lp e r i o d i cp a t t e r n s 学科专业：系统工程 研究生：王端伟 指导教师：顾成奎副教授 天津大学管理学院 二零零八年八月 摘要 作为时间序列数据挖掘的前沿领域，时间序列周期模式挖掘研究有着重要的 理论价值和现实意义，而部分周期模式挖掘和增量挖掘是其研究的重点和难点， 为此，本文选择时间序列部分周期模式挖掘作为主要对象进行研究。 本文首先综述了时间序列数据挖掘和时间序列周期模式挖掘的研究现状，指 出研究的理论价值和现实意义。之后，给出时间序列、周期、部分周期、模式的 工长度、增量时间序列的基本概念，并重点分析了a p r i o r i 性质及基于其性质的 类a p r i o r i 算法、最大子模式命中算法和整段增量算法( e s 算法) 。这作为全文 研究的基础，贯穿于时间序列部分周期模式挖掘和增量挖掘分析的全过程。 在回顾最大子模式命中算法之后，鉴于最大子模式树的特点和不足，本文提 出一种层状链式图结构，对传统的最大子模式树算法进行了改进，利用仿真试验 对比了两算法的时间复杂度。最后，本文还利用层状链式图对增量时间序列的部 分周期模式挖掘进行了研究。基于e s 算法思想提出的层状链式图部分周期模式 增量挖掘算法，继承了层状链式图的存储特性和对频繁模式分离的优势，但是层 状链式图也有局限性。在层状链式图的增量挖掘算法应用仿真中，本文重点研究 它同非增量挖掘思想的优势及考虑置信度变化时的算法伸缩性效率。 本文创新点在于提出一种层状链式图结构，将它代替最大子模式树来存储命 中模式集。层状链式图是根据模式的三长度分层存储命中模式，它不需要按照直 接可达祖先思想创建路径的节点，因此减少了非命中模式节点的存储。同时在模 式分离时，算法通过搜索某一模式的超模式层达到减小匹配空间的目的。另外， 从理论上分析，层状链式图可以应用于增量时间序列的频繁模式挖掘，尽管在层 状链式图的更新效率不及树状结构，但是它延续了在其存储和分离频繁模式等方 面的优势。 关键词：时间序列数据，部分周期模式挖掘，最大子模式命中算法，层状 链式图，增量挖掘 a b s t r a c t a sn e wf i e l do ft i m es e r i e sd a t am i n i n g i ti sm u c hv a l u a b l et or e s e a r c ho nd a t a m i n i n go fp e r i o d i cp a t t e r n h o w e v e r , t h em i n i n go fp a r t i a lp e r i o d i cp a t t e r n sa n d i n c r e m e n t a lm i n i n gi sh a r da n di m p o r t a n ta b o u ti t ，s ot h i sp a p e rc h o o s e st h em i n i n go f p a r t i a lp e r i o d i cp a t t e r n sa st h em a i nt a s kt os t u d y f i r s t ，t h i sp a p e rs u m m a r i z e ss t a t u so ft h et i m es e r i e sd a t am i n i n ga n dp a r t i a l p e r i o d i cp a t t e r n sm i n i n gi nt i m es e r i e s t h e n ，i t a n a l y s e st h ec o n c e p t i o no ft i m e s e r i e s ，p e r i o d ，p a r t i a lp e r i o d i cp a t t e r n s ，l l e n g t h o fp a t t e r na n di n c r e m e n t a lt i m e s e r i e s a f t e rt h a t ，t h ea p r i o r - l i k eo np e r i o d i c i t y , m a x - s u b p a t t e r nh i t - s e ta l g o r i t h ma n d e n t i r e - s e g m e n t si n c r e m e n t a la l g o r i t h m ( e s ) i ss t u d i e d t h e ya r et h ef o u n d a t i o no f r e s e a r c ho na l g o r i t h mo fm i n i n gp a r t i a lp e r i o d i cp a t t e r n sa n dt h e yc a nb eu s e di nt h e w h o l ep a p e r r e v i e w i n gt h em a x s u b p a t t e r n h i t - s e ta l g o r i t h ma n di t sc h a r a c t e r , t h i sp a p e r c o m e su pac h a i n e dd a t as t r u c t u r et oi m p r o v ei t t h e ni tc o m p a r e st h et i m ec o m p l e x w i t ht h em a x - s u b p a t t e r nh i t - s e ta l g o r i t h m a f t e rt h a t ，w er e s e a r c ho ni n c r e m e n t a l m i n i n g i nt i m es e r i e sw i t hc h a i n e dd a t as t r u c t u r e ，b a s e do n e n t i r e s e g m e n t s i n c r e m e n t a la l g o r i t h m i tk e e pm u c ha d v a n t a g eo fs a v i n ga n ds e p a r a t i n gf r o mc h a i n e d d a t as t r u c t u r e ，b u ti ts t i l lh a sm u c hl i m i t a tl a s t ，w ec o m p a r ei n c r e m e n t a lm i n i n gb a s e d o nc h a i n e dd a t as t r u c t u r ew i t hn o n ei n c r e m e n t a lm i n i n g ，a tt h es a m et i m e ，w ea l s o a n y l i s et h ee f f i c i e n c yw h e nc o n f i d e n c el e v e lc h a n g e s t h ei n n o v a t i o ni st h a tw ec o m eu pac h a i n e dd a t as t r u c t u r et om a i n t a i nh i t - s e t i n s t e a do fm a x s u b p a t t e r nh i t s e tt r e e c h a i n e dd a t as t r u c t u r ek e e ph i t s e tb yi t s l - l e n g t h i td o e sn o tn e e dt oc r e a t ea n c e s t o rn o d e s ，s oi tc a nr e d u c et h es a v i n go fn o n e h i t - s e ta n dt h er o o mo f m a t c h i n gt h ep a t t e r n s a to t h e rh a n d c h a i n e dd a t as t r u c t u r e c a nb eu s e di ni n c r e m e n t a lm i n i n g i ti sn o tm u c he f f i c e n c i e rt h a nt h et r e e s t r u c t u r e ，b u ti ts t i l lk e e pt h ea d v a n t a g eo fs a v i n ga n ds e p a r a t i n gt h ef r e q u e n tp a t t e r n s k e yw o r d s t i m es e r i e sd a t a ，p a r t i a lp e r i o d i cp a t t e r n sm i n g ， m a x s u b p a t t e r nh i t s e ta l g o r i t h m ，c h a i n e dd a t as t r u c t u r e ，i n c r e m e n t a lm i n i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 一繇珈f 伊一：猡彦年厂月日 学位论文版权使用授权书 本学位论文作者完全了解苤生盘堂有关保留、使用学位论文的规定。 特授权丕鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 溉c 哥 签字日期：沙1 d 庐9 月踟 日 聊躲猩雅 签字日期! 曙年9 自 第一章绪论 1 1 研究的背景目的和意义 第一章绪论 随着信息技术的发展，人类由工业化时代逐渐步入信息化时代。数据库理论 和应用的成熟以及数据仓库技术的广泛应用，使人们在日常事务处理和科学研究 中积累了大量的各种类型的数据。这些数据涉及到科学研究、医疗保险、商业、 电信业、金融业、制造业、互联网、信息安全到政府决策等各个应用领域。如何 充分有效地管理和利用这些海量数据、发现这些数据背后隐含的规律和知识，成 为人们目前非常关注的问题。 生活中的每天都产生大量的数据，但是人们从存取的数据中所获得的信息量 十分有限，大多隐藏在数据背后的关于数据特征描述，趋势预测和对科学决策具 有重要参考价值的信息却未被发现。因此，人类目前陷入“丰富的数据”和“贫 乏的知识”并存的尴尬境地。于是，人们亟需一种能够从大量的数据中找到有用 的信息和知识的方法，从而有助于使用者及时准确地做出科学的经营决策，以适 应环境的迅速变化。同时，这种技术还应适应现实世界中数据的多样性，比如说： 海量、含噪声、不完整、动态、稀疏性、异质、非线性等n 1 ，在这些要求下，数 据挖掘技术乜儿3 1 应运而生。 数据挖掘就是利用统计、机器学习、软计算方法( 包括神经网络、粗集理论、 模糊逻辑、进化计算等) 、数据库、网格技术等各个学科领域的先进技术对大量 历史数据进行分析处理，从中提取出隐含的、事先未知的和有价值的知识，为人 们的决策分析提供更高层次的技术支持。目前数据挖掘研究已由结构化数据转向 半结构化和非结构化数据，由事务数据转向文本数据、时态数据、空间数据和多 媒体数据，由同构数据转向异构数据，由集中式数据转向分布式数据、由静态数 据挖掘转向动态数据挖掘。针对各类复杂类型数据的挖掘理论、技术及应用的研 究己成为当前挖掘研究的重点和难点口，。 时间序列( t i m e se r i e s ) 数据是指按时间顺序排列的观测值集合h 1 。这里的“时 间”具有广义坐标轴的含义，指按时间的先后顺序排列的数据，例如产品销售记 录数据、股票价格数据、水温记录数据等啼1 。时间序列是一类复杂类型数据，它 的显著特征是：对象之间保持着严格的时间顺序】。时间序列在人类社会的各个 领域中都广泛存在。 时间序列数据的剧增及客观科学决策的需要，使得人们对时间序列数据的研 第一章绪论 究有着极为重要的意义。传统时间序列分析基于2 0 世纪4 0 年代分别由n o r b o r t 、 w i e n e r 和a n d r e ik o l m o g o n o r 给出的理论为基础。尽管传统时间序列分析在各种 工程应用领域啼儿刀有着广泛的应用，但是传统时间序列分析与应用基于建模分析， 往往建模需要一定的前提条件，同时建模需要的时间序列数据在实际生活中也不 能严格满足模型的前提假设，通常表现在数据的不完整性，易变性等。这些使得 传统的方面不能很好解决现实海量，多样性，动态变化的时间序列分析问题。 对时间序列数据进行自动分析，以获得有用信息的时间序列数据挖掘的研究 就具有了非常重要意义。时间序列数据挖掘随儿钔u 伽是一种有效的分析时间序列数 据特征的智能方法，它可以从大量，含噪音，高维，高相关的时序数据中抽取隐 含知识，以供科学决策。 时间序列数据挖掘和数据挖掘的基本过程相似，但是它的研究对象一般表现 为有序性，它是一个演化的分析过程。与此同时，时间序列数据挖掘研究的数据 一般维数较高，往往含有噪音；在幅度方面存在拉伸和平移，在时间轴上存在伸 缩；另外还有线性漂移和不连续点n 。由于时间序列的海量和复杂的数据特点， 直接在原始时间序列上进行数据挖掘不但效率低下，往往难以获得满意的结果。 另一方面也由于其高维度，高相关性和大量噪音等独特结构，使得许多经典的数 据挖掘算法难以发挥作用，增加了时间序列数据挖掘算法的研究难度。目前，在 时间序列数据挖掘的研究工作中尚存在很多问题未解决。因此，对时间序列数据 挖掘理论、技术进行研究具有重要的现实意义和应用价值。 1 2 时间序列数据挖掘过程 数据挖掘是从大量的、不完全的、模糊的、随机的数据中，提取隐含在其中 的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘将人们 对数据的应用从低层次的简单查询，提升到从数据中挖掘有用的信息和知识，提 高决策水平，其主要任务包括相似性查询、模式挖掘、聚类分析、分类与预测和 异常检测等。 时间序列数据挖掘过程和数据挖掘的基本过程样，主要分为挖掘需求分 析，数据的清理，数据的筛选、数据挖掘、知识表示。因此，时间序列数据挖掘 过程可以分为以下几个步骤砼1 ：如图1 1 所示： ( 1 ) 需求分析：不同领域的用户对数据挖掘有着不同的需求，分析用户的需 求是为了确定挖掘的技术路线并使挖掘的最终结果符合用户的期望，为此需要了 解原始数据所涉及的应用领域和相关知识，掌握用户的需求和目标，并制定挖掘 计划。 第一章绪论 f 2 ) 数据清理：大型数据库或数据仓库中往往包含有大量不完整的、含噪声的 和不一致的数据，如果不对这些数据加以处理，就有可能使数据挖掘过程陷入混 乱，导致不可靠的输出。数据清理是对原始数据的初步加工，目标是识别原始数 据中的孤立点、消除噪声、填充空缺的值，并纠正数据中的不一致。 ( 3 ) 数据筛选：参与挖掘任务的数据集的规模对于挖掘过程和结果都有重要 的影响。数据太少往往不具有代表性，会影响挖掘结果的正确性：数据太多难免 包含一些与挖掘任务不相干的数据，会影响挖掘过程的效率。数据筛选就是将来 自多个数据源的数据组合在一起，根据一定的标准从中检索或分析出任务相关的 数据，并将筛选出的数据变换成适合挖掘的统一形式。 ( 4 ) 数据挖掘：这是知识发现全部过程中的基本步骤，是对海量数据进行加工 和分析的过程。从本质来说，数据挖掘的基本任务是从大规模数据集中发现有价 值的模式，如关联规则、分类模式、序列模式等等。数据挖掘是气个智能分析过 程，所使用的方法和手段涉及机器学习、神经网络、遗传算法、序列模式分析， 以及其它一些相关领域的知识。 ( 5 ) 知识表示：数据挖掘系统应当能够将所得知识直观、形象地展示给用户， 如采用表、饼图、直方图、判定树、曲线等来表示此外用户常常会发现系统将 一大堆无用的结果展示出来，只有少数有用的知识却被淹没在其中。因此系统应 该能够在将挖掘结果提交给用户之前先进行筛选。最后，数据挖掘系统还应当是 一个能够与用户交互的系统，允许用户将修正后的参数输入系统，开始新一轮的 挖掘。 图1 1 数据挖掘过程图 时间序列数据挖掘涉及多种学科的相关技术，包括数据库技术、概率与数理 统计、机器学习、数据可视化等。其中数据库技术是数据挖掘的基础，数据挖掘 则为数据库提供智能化的分析手段。目前，时间序列数据挖掘已经引起了学术界 第一章绪论 和工业界的广泛关注，成为国际上数据库和信息决策领域最前沿、最热门的研究 方向之一1 2 h 1 7 1 。 1 3 时间序列数据挖掘功能 时间序列数据挖掘( t i m es e r i e sd a t am i n i n g ，简称t s d m ) 是运用数据挖掘技 术分析具有时间序列特征的数据集从而发现背后隐含的规律和知识的一种科学 方法。从二十世纪九十年代早期开始，时间序列数据挖掘作为一个新的研究方向 出现，并成为数据挖掘领域的一个重要分支。它是旨在研究隐含在时间序列中更 深层次的知识，包括时间序列数据的拟合和变换、时间序列的相似性查询、关联 分析、时间序列模式挖掘、聚类、分类、可视化、时间序列的异常检测等研究内 容。时间序列数据挖掘的一般功能归结如下： ( 1 ) 概念描述u 明n 钔 概念描述就是用简洁的形式描述观察汇总的数据集，从而提供一类数据的概 貌，或将它与对比类相区别。一般数据的类和概念的描述可以通过数据特征化、 数据区分、数据特征化和比较等方法得到，它能满足用户以不同的粒度和不同的 角度来描述数据库中的细节数据集合的愿望。 ( 2 ) 关联分析 关联分析能寻找到数据库频繁出现的项集模式知识，常用的两种技术为序列 模式幢们瞳晗幻乜3 3 和关联规则乜4 儿2 副。关联规则描述的是在一次购物中所购买物品之间 的关联关系，而序列模式则是描述的是同一顾客在多次购物所购物之间可能存在 的关联关系，前者可用于分析客户在超市买牙刷的同时又买牙膏的可能性：后者 则可以用来分析买了电脑的顾客会在三个月内买杀毒软件的可能性。关联分析发 现的关联规则有两种形式，一是单纬关联规则，另一是多维关联规则。他们之间 的主要区别在于分析对象的属性和谓词的不同。 ( 3 ) 聚类删绷 聚类是将数据分组为多个类或簇，使得在同一个簇中的对象之间具有较高的 相似度，而在不同簇中的对象差别很大。聚类增强了人们对客观现实的认识，是 概念描述和偏差分析先决条件。聚类问题是自动发现具有相似特征的时间序列， 时间序列的聚类发现往往以相似模式匹配算法为基础，总的可以分为两大类：全 序列模式聚类和子序列聚类。全序列聚类是在一个时间序列数据集中，将相似的 时间序列组聚到一起。子序列聚类是对一个时间序列来说，用一个移动窗，在滑 动过程中，将行为相似的时间序列段聚在一起。 4 第章绪论 ( 4 ) 分类和预测乜踟 2 9 】 数据挖掘通过对数据库中的数据进行分类和预测，可以自动地提出描述重要 数据类的模型或预测未来的数据趋势，这在商业界的应用很广，包括信誉证实、 选择购物和性能预测等，一个典型的例子是市场预测问题，数据挖掘利用原有的 销售记录来预测新推出的产品的销售情况等。 分类就是根据某个训练好的模型给数据选择某种已知类型标记的过程。按照 处理对象的不同，时间序列的分类问题可以分为两种，一种是对整个时间序列分 类，即由一组时间序歹d u i i 练一个分类器来标注新的时间序列，其中每个序列只有 单独的一个标记。另一种分类问题是对时间序列中的时间点进行分类，训练集合 中每一个时间序列中的每一时间点都作一个标记，训练成的分类器会对新增的时 间序列数据中的每一个时间点进行分类。因此，分类问题可以看做是给定一个时 间序列集合，每个序列隶属于一个事先定义好的类别，作为训练集，通过一定的 分类学习算法，自动学习每个类的特征描述，用来对新的未知类别的序列进行归 类。 ( 5 ) 孤立点分析m 瑚1 数据库中的数据常有一些不符合大多数数据对象的构成规律的记录，从数据 库中检测这些异类很有意义，很多潜在的知识，如分类中的反常实例、不满足规 则的特例、观测结果与模型预测值的偏差、量值随时间的变化等，这常用于金融 银行业中检测欺诈行为，或市场分析中分析特殊消费者的消费习惯。时间序列异 常检测是时间序列数据挖掘的新兴研究领域。在通常的数据挖掘过程中一般将异 常数据忽略或者删除，但是在某些情况下，异常数据含有丰富的有价值的信息， 如电力系统运行中的异常或银行信用卡欺骗行为的监测等。 ( 6 ) 演变分析曙1 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模分析的过程。尽管这可能包含时间相关数据的特征化、区分、关 联、分类或聚类，但是这类数据分析的不同点包含时间序列数据分析、序列或周 期模式匹配和基于类似性的数据分析。例如，股票交易数据的挖掘研究可以识别 整个股票市场和特定公司的股票的演变规律，这种演变规律可以预测股票市场价 格的未来走势，有利于投资者的决策。演变分析是针对复杂数据类型提出的一种 新的挖掘技术。它包括复杂数据对象的多维分析和描述挖掘、空间数据库的挖掘、 多媒体数据库的挖掘、时序数据和序列数据的挖掘、文本数据库的挖掘、w e b 挖掘等。其中，时序数据和序列数据的挖掘包含趋势分析、相似性搜索、与时间 有关的序列模式挖掘和周期模式挖掘。 周期模式挖掘是演变分析的范畴，它是在时间序列数据库中找到呈周期性重 第一章绪论 复出现的模式。周期模式挖掘的问题可以分为三类b 刳： 1 ) 全周期模式( f u l lp e r i o d i cp a t t e r n ) ，即每一个时间点都影响着上时序上的循 环行为。如一年中的每一天都对一年中的季节循环起作用。全周期模式挖掘算法 在信号分析和统计中得到广泛研究。 2 ) 部分周期模式( p a r t i a lp e r i o d i cp a t t e r n ) ，它描述在部分时间点的时序周期。 即只有部分时间点影响时序的循环行为，如小王每天早上7 ：0 0 至l j 7 ：3 0 跑步，其 它时间则没有什么规律。股票每周三出现上升趋势。部分周期是比全周期更为松 散的形式，在现实生活中也更加常见。 3 ) 循环或周期关联规则，它是周期性出现的关联规则。如基于每天的营业记 录，若周末下午茶在3 ：0 0 5 ：0 0 ，则晚餐的最佳营业时间是7 ：0 0 9 ：0 0 。 1 4 时间序列周期模式挖掘综述 时间序列周期模式挖掘是指对时间序列数据中的具有周期性行为模式的提 取与分析，即在时间序列数据库中找出周期性重复出现的模式。周期模式可以应 用许多重要的领域。例如日常季节、潮汐、行星轨迹、能耗、交通模式、消费模 式、金融风险模式和每周特定时间的所有t v 节目。由于时间序列中周期模式大 量存在，需要人们对时间序列的周期模式提取技术进行深入的研究。 时间序列周期模式挖掘研究在国外进展比较快。最早o z d e n 等人提出循环， 周期性关联的概念，1 9 9 8 年h a n ，g o n g 等人进一步给出了时间序列部分周期模 式的概念，并描述了完全周期模式和部分周期模式的形式。完全周期可以看做是 完美周期，相当于一个完整的循环。当前时间序列周期模式挖掘研究主要集中在 时间序列完全周期口引、部分周期模式泓1 、周期性关联规则睁3 1 ，同步周期模式和异 步周期模式朝哺口刀等领域。因此，时间序列周期模式挖掘的研究大体可以归纳以 下几类： ( 1 ) 全周期模式挖掘和部分周期模式挖掘：全周期和部分周期是相对而言的， 其主要关注时间序列中每个点或者每个连续片段在整个观察的时间段中的趋势 和相互关系。全周期可以看作完美周期，部分周期模式只描述时间序列中某些点 局部的周期性特征而并非全部时间点的周期特征。 ( 2 ) 同步周期模式和异步周期模式挖掘：时间序列中由于受到噪音的影响， 时间序列的周期特性可能发生部分偏移，针对这种问题，学者提出了时间序列的 异步周期的概念，并研究异步周期模式的发现算法。y a n g 等人口7 1 提出了在阈值 区间挖掘最长子序列异步周期模式的问题。通过设置阈值来定义有效时间节和有 效时间段，例如通过r a i nr e p 、m a xd i s 的最小阈值来验证序列中有效的连续时 6 第一章绪论 间点和时间段。在有效时间节上事件必须呈现周期规律并重复出现，以体现这个 时间节的重要性和周期性。连续两个有效时间节之间距离来衡量时间段的变化及 有效性。最长有效时间段中的周期模式就是异步周期模式。同步周期模式可以看 作是异步的一个特例。 ( 3 ) 非增量的时间序列周期模式挖掘和增量时间序列周期模式挖掘：在时间 序列数据挖掘中，往往有时间序列数据段需要增加到原来的时间序列数据中，从 而融合成包含原数据的增量时间序列。增量时间序列的挖掘可以利用非增量算 法，也可以运用增量思想算法。增量挖掘是充分利用已经分析过的数据信息，在 增加需要分析的数据量时，整合新老数据两个部分的信息，从而达到把握增量时 间序列的基本特征目的。增量挖掘在时间序列数据分析中的应用中日益广泛，例 如电力数据增量，不同子公司间的数据融合，网上在线增量数据分析等。 ( 4 ) 关联规则周期性挖掘：关联规则周期性的研究也受到学术的重视，a g r a w a l 等人提出了关联规则发现方法。在周期性关联规则中，o z d e n 啼朝提出了周期侦探 算法和序列的周期关联规则挖掘方法。周期性规则一般是在周期数据段内提出项 目的关联规则，之后通过序列的周期匹配来分析规则的周期特征或非严格周期特 征。例如每天下午 7 ：0 0 8 ：3 0 会出现规则“牛奶j 面包。 目前，周期模式挖掘技术主要分为两类：一类为全周期分析技术，主要应用 快速傅立叶变换( f f t ) ，周期探测等方法。全周期分析技术已经在信号分析和统 计中得到研究；另一类为部分周期模式挖掘或周期性关联规则分析技术，主要基 于a p r i o r i 算法特性的改进算法和约束挖掘算法( m i n i n gc o n s t r a i n t ) 。在时间序列 部分周期算法研究中，由于时间序列部分周期模式在同一周期内混杂有周期性事 件与非周期性事件，因此绝大多数全周期模式的挖掘方法不适用于部分周期模式 的挖掘或者时空开销过大。例如快速傅立叶变换f f t 就不能用于部分周期模式 挖掘，因为它将时间序列视为连续不可分割的数据流。而另一些全周期模式挖掘 方法虽然可以用于部分周期模式的挖掘，但必须明确指定周期长度、模式的长度 及起始值等参数，由于应用程序必须搜索由这三个参数组合出的所有可能情况， 这样一来无疑会增大计算量。至今，有关部分周期模式和循环关联规则挖掘的大 部分研究都应用了a p r i o r i 特性启发式和采用了类a p r i o r i 挖掘方法。 基于类a p r i o r i 特性的时间序列部分周期模式挖掘算法主要有片断周期时间 序列模式挖掘算法( s e g m e n t w i s ep e r i o d i cp a t t e r n s ) 3 4 , 类a p r i o r i 时间序列部分周 期模式挖掘算法、最大子模式命中算法( m a x s u b p a t t e mh i ts e t ) 。 h a n 等人提出片断周期时间序列模式挖掘算法，它按照一个用户指定的周期 长度挖掘时间序列数据库中的周期模式。由于该算法本身所限，在其挖掘过程中， 不论是中间候选时间序列，还是最终时间序列周期模式，它们的周期都是事先由 7 第一章绪论 用户所指定的，因而不能变化。这使得该算法把一些周期模式序列切成了更小的 “碎片”，并把这些碎片同其它有用的结果混杂在一起交给用户判断，容易造成 用户的困惑。 h a n 等人在片段周期时间序列模式挖掘的基础上进一步提出几种新的算法来 挖掘部分周期模式，例如：类a p r i o r i 部分周期模式挖掘算法、最大子模式命中 算法( m a x - s u b p a t t e r nh i ts e t ) 。这些算法利用周期特有的性质，包括a p r i o r i 启发式 性质、最大子模式命中集( m a x s u b p a t t e mh i ts e t ) 属f t 3 8 】。其中最大子模式命中集 属性将时间序列模式子集存在在最大命中子模式树中，这样挖掘部分周期模式只 需要扫描两次时间序列数据库就能把时间序列中所有的频繁模式分离出来。同 时，基于a p r i o r i 特性和变通的时间序列部分周期模式挖掘算法还可以挖掘多周 期的时间序列部分周期模式。 时间序列部分周期模式挖掘算法的特点可以归结两个方面： ( 1 ) 时间序列周期模式挖掘研究是在时间序列频繁模式研究的基础上展开。频 繁序列模式挖掘算法用于发现一个序列集中频繁发生的序列模式。频繁序列模式 挖掘的核心和难点在于识别或发现序列集中存在的所有频繁模式，其中最著名的 算法就是基于a p i o r i 思想的类似a p i o r i 算法，但是该算法的计算量较大，为了 提高该算法的效率，人们提出了各种改进算法。然而频繁序列模式并没有考虑到 每个模式的发生在序列中所处的位置，即时间特性。在一些应用中，用户可能对 频繁模式不感兴趣，相反的，希望找到那些以某种规律发生的模式，以便于预测 未来发生的事件，并且更好地理解数据集的潜在特性。作为频繁模式挖掘算法的 延续，很多频繁模式挖掘算法的概念和相关算法在周期模式挖掘中仍然被广泛应 用，如频繁、置信度、a p i o r i 算法等。特别是a p i o r i 算法的核心思想广泛启迪着 改进的时间序列部分周期模式挖掘算法。 ( 2 ) 时间序列部分周期模式挖掘的改进算法中，大部分仍然采用a p i o r i 算法的 思想，首先生成周期1 模式，然后基于a p r i o r i 原理或最大子模式命中集特性， 找到所有的周期模式。其中，最大子模式命中集特性是在a p i o r i 算法的基础上， 对a p r i o r i 原理的改进，二者在复杂模式生成过程中存在差异。这些差异客观要 求构建合适的数据存储结构来优化读写数据库的开销，使得部分周期模式挖掘的 算法效率的大大提高。 综上所述，时间序列周期模式挖掘作为时间序列数据挖掘的研究前沿，其相 关算法的研究文献相对较少。目前提出的周期模式挖掘算法大多是基于a p r i o r i 原理和频繁模式挖掘算法的思想。在时间序列周期模式挖掘算法中，人们主要致 力于提出各种新的周期模式概念和相关挖掘算法。随着时间序列周期模式挖掘研 究范畴的延伸，时间序列部分周期模式挖掘研究有着更为现实理论意义。 第一章绪论 1 5 本文研究内容和创新点 1 5 1 研究内容 本文在综述时间序列周期模式挖掘的研究现状之后，给出了时间序列、周期、 部分周期、模式的l 长度、增量时间序列和增量挖掘的相关概念。在此基础上， 重点研究了时间序列部分周期模式挖掘中的a 研o r i 性质，类a p r i o r i 算法、最大 子模式命中算法和整段增量算法。基于最大子模式命中算法存在的问题，本文提 出一种层状链式图代替最大子模式树来改进其算法，并通过仿真试验对比了两算 法的性能。最后，本文基于e s 算法思想，将层状链式图结构应用于增量时间序 列的频繁模式挖掘中，并对基于层状链式图的增量挖掘算法进行了应用仿真分 析。 本文研究内容如下： 第一章，介绍了本文的选题背景意义、时间序列周期模式挖掘研究现状、研 究内容及主要创新点。 第二章，作为全文理论研究的基础，给出了时间序列、周期、部分周期、模 式的l 长度、增量时间序列等相关概念，重点研究了a p r i o r i 性质、类a p r i o r i 算法、最大子模式命中算法及其存在的不足。最后，为了研究时间序列增量挖掘， 本章还描述了时间序列增量挖掘的基本思想，重点阐述了整段增量算法过程。 第三章，回顾了最大子模式命中算法，总结分析了最大命中子模式树的特点。 鉴于其建树过程和分离频繁模式时的额外开销，本章创新性提出一种层状链式图 结构。在理论分析了层状链式图的特点和优势之后，本章描述了基于层状链式图 的部分周期模式挖掘算法。通过试验的仿真对比分析，研究得出基于层状链式图 的时间序列部分周期模式挖掘算法效率优于最大子模式命中算法。层状链式图存 储结构对整个算法的优化显著。 第四章，对时间序列部分周期模式增量挖掘的思想及注意的问题进行了分 析。基于e s 算法思想，本章还将层状链式图应用于增量时间序列的频繁模式挖 掘中，并提出了层状链式图部分周期模式增量挖掘算法。它继承了层状链式图的 存储特性和对频繁模式分离的优势，但是由于层状链式图中父子节点关系没有建 立，使得层状链式图的更新效率低于树状结构。最后，在层状链式图的增量挖掘 算法应用仿真中，重点研究它同非增量挖掘思想的优势及置信度阈值变化时的算 法伸缩性。 第五章，总结全文，并提出展望。 9 第一章绪论 1 5 2 主要创新点 围绕目前时间序列部分周期模式挖掘算法和增量挖掘算法存在的不足 之处，本文对其进行研究并提出改进的算法。 本文创新点在于提出一种层状链式图结构，将它代替最大子模式树来存 储命中模式集，以改进最大子模式命中算法。同时将层状链式图结合e s 算 法应用于增量时间序列的频繁模式挖掘。 同最大子模式树结构相比，层状链式图在存储和分离频繁模式等方面有 其独特的优势。层状链式图按照模式的工长度分层存储命中模式，它不需要 按照直接可达祖先思想创建路径的节点，因此减少了非命中模式节点的存 储。同时在模式分离时，算法通过搜索模式的超模式层达到减小匹配空间的 目的。因此，层状链式图的运用有效提高了算法在挖掘时间序列频繁模式时 的存储效率。另外，最大子模式命中算法每次从根节点开始搜索分离模式的 超模式，但是层状链式图从比分离模式j 巳长度大的每层表头开始搜索，使得 层状链式图在分离所有频繁模式时的效率优于树结构。 在增量时间序列的频繁模式挖掘中，层状链式图可以结合e s 算法进行 时间序列的增量挖掘。层状链式图尽管在图的更新方面的效率可能不及树状 结构，但是它还是延续了在其存储和分离频繁模式等方面的优势。 1 0 第二章部分周期模式挖掘基础 第二章部分周期模式挖掘基础 围绕时间序列部分周期模式挖掘，本章给出了时间序列、时间序列数据库、 周期，部分周期、模式的l 长度等相关基本概念。在此基础上，重点分析了a p r i o r i 性质，类a p r i o r i 算法及最大子模式命中算法。通过分析时间序列部分周期模式 挖掘算法实现过程及其性能，本文研究得出算法在存储效率，时间复杂度等方面 存在一些不足。最后，本文给出了增量时间序列的概念，增量挖掘的思想和时间 序列增量挖掘相关算法。作为全文时间序列部分周期模式挖掘研究的理论基础， 它贯穿于时间序列部分周期模式挖掘类a p r i o r i 算法、最大子模式命中算法、层 状链式图部分周期模式挖掘算法和时间序列部分周期模式增量挖掘分析阐述的 全过程。 2 1 时间序列概念n 1 定义2 - 1 ( 时间序列) 设t 为某个时间集，对t t ，x t 为随机变量，对于该 随机变量的全体x t ，t t ，当t 取为离散集时，如t = 礼2 ， 或t = 1 9 2 ，z ，称 l x t 是随机序列。由于随机序列k 的整数变量t 一般代表等间隔的时间增长量， 所以常称随机序列为时间序列。 定义2 - 2 ( 时间序列数据库) 时间序列数据库( t i m es e r i e sd a t a b a s e ) 是一个 记录集合妒， j ! ，t ，其中每一个记录都有一个属性集合和时间值， r j = k 。，口：，口。，t ， 。每一个属性为一个实际数值口，僚，或者为一个离散值 a i n ，这些属性有可能与时间有关，也有可能与时间无关。若该属性值与时 间有关，它就是动态属性；若该属性值与时间无关，就是静态属性。时间值t ，是 一个按照给定的分辨率变化值计量，比如说小时、天、月、年等。 定义2 3 ( 事件序列) 给定一个事件类型的集合，一个事件是一组( a ，f ) ， 其中a e 是一个事件类型，f 是一个整数，是事件发生的时间，事件类型可以 由几种特征组成，为了方便，我们在这里只考虑单一值的情况。一个发生在e 上 的事件序列s 是一个三维变量( s ，i ，e ) ，其中，s = ( ( 4 川t ) ，( 彳：，t ：) ，( 爿。，t 。) ) ， 是一个有序事件序列，a ，e ( i = 1 ，z ) ，t ，t 川( 扛l ，刀一1 ) ；i 和乙是整、 数，互是起始时间，是结束时间。t t ，t ( f = l ，z ) 。事件序列中每个事 件的发生都与时间有关。 定义2 - 4 ( 事件时间序列) 事件时间序列是指按照等时间间隔发生的事件构 成的时间序列，无需时间标志。记事件时间序列s ，s = 墨s ：s s 。，l i 刀，s i 第二章部分周期模式挖掘基础 为第i 时间间隔发生的事件。如果在每个时间点发生事件数小于等于l ，则s 为单 事件时间序列，若序列时间点内发生多个事件，记s 为多事件时间序列。 由此可见，单事件时间序列是指在一个时间点上只发生一个事件的事件时间 序列。多事件时间序列与单事件时间序列相对而言，指在一些或全部时间点上， 每个时间点发生一个以上事件的事件时间序列。 2 2 部分周期模式概念 最早，人们对周期的理解开始于循环的概念。在此之后，h a n 等人提出了部 分周期的概念。部分周期是相对完全周期而言，完全周期强调时间序列的每个点 都对周期有贡献，部分周期只是部分点对周期有贡献。 为了便于理解部分周期的概念，给出循环口3 1 ，周期模式的定义描述如下： 定义2 5 ( 循环)设任一给定的长为n 的时间序列，如果存在 p ，o 广，0 p = c o u n t ( s ) m 。即当s 是频繁，其子模式s 也是频繁的。 2 4 2 类a p r i o r i 算法的部分周期模式挖掘算法分析 对于时间序列s ，给定周期p 和最小置信度m i n c o i lf ，类a p r o i r 算法则是 在找到周期为p 的频繁1 模式之后，按照关联规则a p r i o r i 算法步骤及利用性质 2 1 找到周期为p 的所有频繁i 模式，从而挖掘出时间序列中的所有频繁模式。 算法2 1 类a p r i o r i 部分周期模式算法：类a p r i o r i 部分周期模式挖掘算法 过程描述如下： 输入：周期长度p ，最小置信度r a i nc o n f ，时间序列s 。 输出：周期长度为p 的所有频繁模式。 算法： ( 1 ) 找出周期长度为p 的频繁l j 模式互：第一次扫描数据库，将时间序列按 第二章部分周期模式挖掘基础 照周期长度分成不相交的周期段，同时每个周期段分解成周期长度为p 的若干候 选1 模式，并计算其模式在所有周期段中的计数，如果其计数不少于 r a i n c o n f x m ，其中m = 【n p 】，则把此模式从候选1 一模式集中筛选出来存储于 频繁1 模式集f 中。 ( 2 ) 找出所有的频繁模式：基于a p r i o r i 思想，找到周期为p 的所有频繁i 模 式，i 从2 到p 。当候选频繁i 一模式集为空时，立即结束。其实此过程主要分为 如下三步： 1 ) 连接步：频繁( i 1 ) - 模式和它本身连接生成i 候选模式。 2 ) 剪枝步：找出候选的i 模式在所有周期段中的计数，如果其计数不少于 r a i n c o n f m ，则筛选出来，形成频繁i 模式，存储于频繁i 模式集中。 3 ) 同理循环，i 从2 到p ，直到候选频繁i 模式集为空，从而逐步分离出目 标频繁模式。 类a p r o i r 算法时间复杂度和空间复杂度分析如下： l 、存储空间方面：在算法的第一步，通过分析m 个周期长度为p 的序列周 期段，如果序列每个位置的字符特征不同，最多需要：。l bi 存储单元；如果设 z 为每个周期第i 位置不同特征之和，则第一步总的存储单元为y , 2 。z 。 在算法的第二过程将最多分解数目如公式2 3 ： ( ：1 ) + ( ：1 ) 十+ ( ：) 2 2 旧l - ie l ， c 2 3 ， 所以类a p r i o r i 算法总的存储空间为2 垆1 。 2 、时间复杂度方面：算法主要耗时在读写数据库文件i o 开销方面，在分 离出频繁模式过程中，算法要求扫描数据库平均在两次以上，最坏高达p 次。 2 5 最大子模式命中算法 h a n 提出了最大子模式命中算法( m a x s u b p a t t e mh i t s e t a l g o r i t h m ) ，它是基于 a p r i o r i 思想的一种部分周期模式挖掘算法。最大子模式命中算法建立了命中模 式树数据存储结构并由此来分离部分周期模式。与类a p r i o r i 算法相比，挖掘算 法减少了数据库的扫描次数及候选模式的生成，效率大