（计算机应用技术专业论文）基于时态约束的关联规则挖掘的研究.pdf

摘要 关联规则的研究是数据挖掘中的重要研究内容之一，由于实际的 数据是随时间变化而获得的，因而有必要对其时态属性进行分析，这 样有助于揭示事物发展的本质规律，使得发现的知识更能贴近现实意 义。目前国内外对于时态数据的研究主要是进行时序分析，对时态关 联规则的研究多侧重于研究关联规则成立的时间，对于规则中各项之 间在时间上的约束未进行具体的分析，在一些领域中不能很好地进行 预测和描述。 基于这些不足，本文着重分析研究以下几方面的内容： ( 1 ) 阐述了时态关联规则挖掘的研究现状，针对所存在的不足及 亟待解决的问题引出本文所要研究的内容。 ( 2 ) 对时间进行了理论上的研究，在一定程度上对有关时间的理 论研究进行了完善。 ( 3 ) 构造了事件模型，对事件间的运算及性质进行了形式化定义 和研究。 ( 4 ) 构造了一类基于时态约束的关联规则模型，适于描述事件与 时间之间的关联、基于时域的事件与事件之间的关联。 ( 5 ) 研究了基于时态约束的关联规则挖掘的理论、算法，并进 行了数值实验。 ( 6 ) 对于该类规则的周期性挖掘的意义、算法和数值实验进行 了研究。 本文主要获得的研究成果和创新如下：1 、拓展了有关时间的理 论研究，对事件间在时间维上的约束进行了研究；2 、提出了一类基 于时态约束的关联规则挖掘算法及周期性挖掘算法。 关键词：数据挖掘时态关联规则时态约束 a b s t r a c t t h e s t u d yo f a s s o c i a t i o nr u l e si sr e g a r d e da so n eo ft h ei m p o r t a n tf i e l d si n d a t am i n i n g i np r a c t i c e ，i ti sn e c e s s a r yt oc o n s i d e ra n da n a l y s i st h et i m e a t t r i b u t eo ft h ed a t ac h a n g i n go v e rt i m e ，w h i c hi sh e l p f u lt ou n e a r t ht h e e v o l v i n gp a r e r n s o ，t h e m i n e d k n o w l e d g e w i t ht i m ei n f o r m a t i o ni st ob e m o r e m e a n i n g c u h e n t l y ，t h er e s e a r c ho ft e m p o r a ld a t ai sm a i n l y f o c u s e d o nt i m e s e r i e s a n a l y s i s m e a n w h i l e ，t h es t u d yo ft e m p o r a l a s s o c i a t i o n m l e si s m o s t l yf o rt h et i m et h em l e sh o l da n ds e l d o mf o rt h et e m p o r a l c o n s t r a i n ta m o n gt h ei t e m si nt h er u l e s t h u s ，t h e s em o d e l sm a yb en o t a b l et ob eu s e df o r p r e d i c t i o na n dd e s c r i p t i o n t h e r ee x i s t ss o m ei n a d e q u a c yi n t e m p o r a l a s s o c i a t i o nr u l e m i n i n g t h e r e f o r e ，i nt h i sp a p e r , w ew i l le x a m i n et h ep r o b l e mo fd i s c o v e r yo f a s s o c i a t i o nr u l e sb a s e do n t e m p o r a l c o n s u a i n tf r o mt h ef o l l o w i n g a s p e c t s 。t h ep r e s e n ts i t u a t i o no f t e m p o r a l a s s o c i a t i o nr u l e s m i n i n g i s e x p o u n d e d t h e n ，t h ep r o b l e m s a r ep r e s e n t e dw h i c hw ew i l lr e s e a r c ha n d a c c o u n tf o ri nt h i sp a p e r t h ec o n c e p t sa n d p r o p e r t i e sa b o u tt i m ea r es t u d i e df r o mt h ep o i n to f m a t h e m a t i c a lv i e w t h u s ，t h e t h e o r ya b o u tt i m e i s s u p p l e m e n t e dt o a c e r t a i ne x t e n t 。a ne v e n tm o d e li sc o n s t r u c t e da c c o r d i n gt ot h ea f o r e m e n t i o n e dt i m e t h e o r y a n dt h e n ，t h er e l a t i o na m o n gt h ee v e n t s i sf o r m u l i z e da n dt h e c o r r e s p o n d i n gp r o p e r t i e sa r ep r o p o s e d a na s s o c i a t i o nr u l e sb a s e do n t e m p o r a l c o n s t r a i n ta r e c o n s t r u c t e d ， w h i c h e m b o d y t h ea s s o c i a t i o nb e t w e e ne v e n t sa n dt i m ea n dt h ea s s o c i a t i o n o fi n t r a t r a n s a c t i o n s t h et h e o r ya n dc o n c r e t ea l g o r i t h mo f m i n i n g a s s o c i a t i o nr u l e sb a s e do n t e m p o r a lc o n s t r a i n ta r es t u d i e d t h ee x p e r i m e n t a lr e s u l t so nt h es t o c kd a t a a r es h o w n 。t h es i g n i f i c a n c eo f p e r i o d i c i t ya n a l y s i sf o ra s s o c i a t i o nr u l e sb a s e do n t e m p o r a l c o n s t r a i n ti sd i s c u s s e d a n dt h e n ，t h e m i n i n ga l g o r i t h m a n d e x p e r i m e n t a lr e s u l t s a r e g i v e n 。 i nt h i s p a p e r , w eo b t a i nt h ef o l l o w i n gr e s u l t s f i r s t l y , m a t h e m a t i c a l t h e o r ya b o u tt i m e i sd e v e l o p e d m e a n w h i l e ，t h ec o n s t r a i n ta m o n ge v e n t sa t t i m ed i m e n s i o ni ss t u d i e d s e c o n d l y , a l g o r i t h m s o f m i n i n g a s s o c i a t i o nr u l e s b a s e do n t e m p o r a l c o n s t r a i n ta n d p e r i o d i ct e m p o r a l r u l e sa r e p r o p o s e d k e y w o r d s ：d a t a 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 t e m p o r a l c o n s t r a i n t 湘潭大学硕士学位论文 第一章绪论 本章阐述了时态数据挖掘的研究背景以及有关的技术，分析了 其研究现状，探讨了在时态关联规则方面的研究，总结了该领域已 取得的成果，讨论了存在的不足及需要解决的问题，引出本文所要 研究的内容 1 1 时态数据挖掘概述 1 1 1 引言 随着计算机技术的发展和数据库技术的广泛应用，各行业都积 累了海量的、以不同形式存储的数据资料，要从中发现有价值的信 息或知识而达到为决策服务的目的，成为非常艰巨的任务数据挖掘 技术应运而生，让人们有能力最终认识数据的真正价值 在k d d 9 6 国际会议上，f a y y a d 、p i a t e t s k y 、s h a p i r o 和s m y t h 对数据挖掘( d a t am i n i n g ) 作了公认的最新定义数据挖掘，就是应用 一系列技术从大型数据库或数据仓库的数据中提取人们感兴趣的信 息和知识，这些知识或信息是隐含的、事先未知而潜在有用的，提 取的知识表示为概念、规则、规律、模式等形式【3 ”3 1 在实际的知识发现中，许多操作型数据均与时间有关，是随着 时间变化而获得的，我们把这种带有时间属性的数据称为时态数据 例如超市交易记录库中涉及交易的时间、病历库中有检查和诊断时 间、股票市场的每日波动情况、科学实验数据等，这些都属于时态 数据库时态数据反映了事物发生发展的过程，有助于揭示事物发展 的本质规律因而有必要在进行数据挖掘时考虑时间因素，使得发 现的知识更能贴近现实意义，这样就产生了带有时间属性的数据挖 掘研究课题 1 1 2 时态数据挖掘研究现状 时态关系数据结构是指时间属性和由时间属性决定的相应属性 之间存在的约束关系时态数据不仅表现了数据之间的时序关系，同 时也描述了不同数据之间相互转换的时间过程时态数据是在传统 的数据库基础上加上时间维，时态数据的特点决定了时态数据库中 湘潭大学硕士学位论文 2 的挖掘技术及所发现的时态知识都具有其自身的特点，挖掘研究主 要可分为以下几个方面： 1 时态关联挖掘 时态关联定义的是事件间的继发关系当某一事件或多个事件 紧接着另一事件发生时，它们之间不一定是因果关系，但可以认为 它们之间具有一定的关联性，例如股票的涨跌模式关联分析的基本 思想是计算某种度量，这种度量包括信息增益、g i n i 索引、不确定 性和相关系数等 对于关联的研究已有很多，如单维的关联、多维的关联、单层 次的关联、多层次的关联、量化的关联、基于距离的关联等等当前 的时态关联研究大多将已有的关联分析运用到时态数据中，主要考 虑该关联成立的时间范围扎”3 ，提出了一些时间区间合并、延展技 术口1 ，提出了一些时态关联挖掘的算法，大都是基于a p r i o r i 算法的 变形 文 7 ，4 9 对相同属性的相邻时态关联规则、相同属性的相连时 态关联规则的挖掘进行了研究，发现多数股票3 天内必有上涨或下 降的规则 2 周期性挖掘 周期性分析是指对周期模式的挖掘，即在时态数据中找出重复 出现的模式周期模式挖掘可视为一组分片序列为持续时间的序列 模式挖掘，分为全周期模式的挖掘、部分周期模式的挖掘及循环或 周期关联规则的挖掘全周期分析的技术如f f t ( 快速傅立叶变换) 已在信号分析和统计中得到研究，有关周期性的分析大都应用了 a p r i o r i 启发式特性和变通的a p r i o r i 挖掘方法瞪“0 “1 3 趋势性挖掘 包括长期趋势变化、循环变化、季节性变化、随机变化的分析 长期趋势反映了一般的变化方向，确定趋势常见方法是用加权移动 平均方法和最小二乘法，其时序图是在较长时间间隔上的数据变化， 反映为一种趋势曲线循环变化是指趋势曲线在长期时间间隔内呈 摆动迹象季节性变化反映的是每年都重复出现的事件随机变化 塑翌查堂堡主堂垡堡苎! 反映随机或者偶然事件引起的零星时序变化 趋势性分析主要针对连续型数值，通过对数字曲线模式利用统 计时序中的方法进行分析，以获得属性随时间变化的趋势，从而制 定出长期或短期的预测“7 ”川 4 序列模式挖掘 序列模式挖掘是指挖掘相对时间或其它模式出现频率高的模 式，目的是为了寻找一段特定时间以外的可预测行为模式其中涉及 模式匹配及相似度问题序列模式的研究对象可以是符号模式，也可 以是连续型数据的曲线模式，对于后者，需对曲线的形状进行特征 化，定义曲线间的相似度“”1 文e 3 较早地对序列模式挖掘进行了深入的研究，主要是针对购 物篮的分析，将顾客在一段时间的购买行为看成一序列给出了有关 序列的性质，相应的算法，跳跃式地产生最大序列该文的研究主要 是适用于布尔型变量的挖掘对于其它主题的序列模式挖掘，文 1 3 ，3 8 也进行了研究，大都是采用文 3 算法的变形 文 3 7 对非同步多时间序列进行了研究，对连续数值形成的曲 线进行线性化分段和矢量聚类，来将其转换成离散的多个符号序列， 以提取时间序列中的基本模式，该方法只适用于对单属性随时间波 动的模式进行研究在文 1 9 ，3 0 ，3 1 中也有相应的研究 数据挖掘中已有的挖掘方法、工具都可运用到时态挖掘中来， 主要有以下几类工具 1 基于规则和决策树的工具 采用规则发现和决策树分类技术来发现数据模式和规则，其核 心是某种归纳算法，如q u i n l a n 提出的著名的基于信息熵的i d 3 算法 和s c h l i m m e r 、f i s h e r 设计的i d 4 递增式学习算法 2 基于神经元网络的工具 具有对非线性数据的快速建模能力，挖掘过程基本上是将数据 簇聚，然后分类计算权值 3 数据可视化方法 支持多维数据的可视化，同时提供了多方向同时进行数据分析 的图形方法，扩展了传统商业图形的能力 湘潭大学硕士学位论文4 4 模糊发现方法 应用模糊逻辑进行数据查询排序 5 统计方法 这是关联分析的一类重要方法，对于简单关联都是通过统计技 术而获得的，这种方法不能区分等变性和因果关联统计分析方法 主要有相关分析和回归分析 对时态数据的挖掘，我们不仅要知道事件是否发生，而且需要 考虑所发生的具体时间 1 1 3 时态关联规则研究进展 与在普通事务数据库中进行关联规则挖掘相比，时态关联规则 能更好地反映数据中所隐藏的与时间有关的知识近几年，国内外 有许多学者就此进行了研究，而且已成为k d d 的热点之一时态关 联就是要发现事件与时间之间的关联以及基于时域的事件与事件之 间的关系等，我们将这种带有时间属性的关联规则称为时态关联规 则盼 时态关联规则的研究主要有下面几个方面： 1 ) 关联规则成立的时间 传统的关联规则挖掘很少考虑关联规则的时间适用性，然而每 个关联规则都有其成立的时间区域 如在购物篮分析中，对各个商品项目的购买时间加以考虑，得 出了在某段时间下成立的关联规则在文 2 中提出了具有时间属性 的关联规则，其发现算法是在a p r i o r i 算法上嘲的扩展，当遍历数 据库以对候选项集进行计数时，两个项目序列不仅要匹配，而且两 者的相关有效时间也需要归并，提出了时间区间的延展概念及方法、 时间区间的归并概念及技术 在文 4 中，引入了交易项目集的生命期，其支持度只在其生命 期内考察此文所介绍的时态关联规则是对一般的非时态关联规则 的扩展，这种方法主要是针对商品交易数据库进行的，它的基本思 想就是将频繁项集的搜索限制于其生命期间。这种对项目集赋予生 命期的方法可以发现一般关联规则挖掘方法所不能发现的规则 塑翌叁兰堡主兰焦堡苎! 文 2 ，4 ，5 ，6 ，9 主要是针对项目发生的时间区域来扩展项目 集，在连接操作上考虑了项目的时间属性，以决定规则的成立时间 这些研究涉及的主要是事件与时间之间的关联，考虑了一定时间段 内的阶段性关联规则，未涉及到事件之间的时态约束 已有的这些研究主要是对数据库的的每个元组考虑其发生时间， 强调的是关联规则成立的时间属性，以表明所发现的知识何时是有 效的在未考虑时间属性时，所得的规则假定是永远有效的在考虑 了时间属性后，所得到的规则将可以更好地描述客观现实情况，因而 也会更有价值 2 ) 关联规则的周期性 主要是研究了有关周期时间区域的划分我们把长度为，的周期 划分为等问隔的时问区域，分别计算每个时间区域中项目子集的支 持度以求周期关联规则“刖。这样的实现方法很简单，周期时间段是 人为确定的，但在某些领域不能充分反映数据的内在规律如以小 时为粒度来划分每天的销售事务，则像“每天早上6 ：2 0 8 ：3 0 时间 范围内买牛奶的顾客会买面包”这样的规则就不能够被发现 在某些领域，周期的获取适合由聚类来实现可以根据事务发生 的频度利用聚类分析来实现对时间段的划分删这样，时间段的长度 根据事务发生的集中度自动求出，而不是人为主观规定，这与时态 关联规则的实际意义相一致也可依各项目的频度来聚类，根据聚类 结果把每个项目分成几个动态的时间区域n ” 3 ) 序列关联规则 类似于序列模式的研究，只关心事件发生的顺序，对于具体的 发生时间并不讨论规则中的前件和后件分步产生，可以运用已有 的序列模式研究中的方法“”3 “3 。”文 2 8 ，2 9 ，4 0 提出了时间窗口 滑动、曲线相似性聚类等方法 4 ) 时态关联规则模型的建立 由于时态关联规则的挖掘是在带有时间属性的数据上进行的， 因而有关时态数据的表示也需进行研究，以便于事件和时态规则模 型建立对于这方面的深入研究还不多见，如对于时间的表示及相应 的性质从理论上进行研究还很少，而且也各有特点 塑翌奎堂堡主堂垡堕苎 ! 文 1 ，7 ，8 ，4 6 5 1 对有关时间的概念及性质从数学理论上进行 了的定义和证明，如时态型、时态因子的定义及性质，仅建立了简 单时态事件模型，对部分特殊情况下的时态关联规则的挖掘思想进 行了简介，但未深入算法的研究对于复杂的时态关联规则以及通用 的时态关联规则模型也没有进行研究文 1 ，7 ，8 ，4 6 5 1 中的有关 时间的定义较文 4 1 ，4 3 ，4 4 中的定义更具有广泛性、更直观、更易 于理解 这些模型可以描述企业当前发展的现状和规律性，也可以用来 预测，以辅助决策 1 1 4 时态关联击兄则研究中的不足 对时态关联规则研究已经很多，大多是对关联规则所成立的时 间进行研究，这种关联是同一时间或同一事务中的各项或各事件间 的关联，本质上没有对数据在时间维的关联以及在不同时间粒度间 的关联进行研究序列关联规则的研究虽然也有很多，然而注重的是 事件的发生次序，对于事件间具体的时态约束并未加以考虑，并且 多是用于购物篮分析以及单属性的连续数值在连续时间上的序列分 析 现实中的时态数据反映了事物发生发展的过程，我们往往是想 通过对历史数据的研究以为将来作预测、决策如在股票市场中、天 气数据中，以及科学实验数据中，我们更需要的是有助于预测性的 知识而现有的时态关联规则的研究主要考虑某时间区间内成立的 关联规则，或是考虑了规则成立时间的周期性，但对规则中的项目( 或 事件) 间的时态约束没进行考虑，都属于事务内( i n t r a - t r a n s a c t i o n ) 的时态关联规则诸如每年情人节前巧克力和鲜花的销量会突然上 升，对于股票市场中所需的某股票的价格连续上升了三天，那么一 周后该股票的价格会呈现上涨还是下跌? 传统的有关时态关联规则 的研究则发现不了该类预测性的知识 同时，对于对态关联规则模型中时间的表示也各有特点，对时 间的严格的数学定义及逻辑表示没进行理论上的研究，因而时态关 联规则对用户并不是很透明，缺乏可理解性 因此，我们希望对时态数据建立一种比较规范系统的模型，使 塑翌查堂堡主堂笪丝苎! 得它所描述的意义是广泛的，能够描述同事务内的时态关联规则、 同时间粒度下的事务间( i n t e r - t r a n s a c t i o n ) 的时态关联规则，以及不 同时间粒度下的时态关联规则，涉及的是多个属性多个事务间的关 联，能表达更深层次的知识 1 2 本文研究内容 针对现有的时态关联规则研究中的不足，我们对基于时态约束的 的关联规则挖掘进行了研究，本文给出了下面几个方向的研究： 1 、阐述了时态关联规则的研究现状，对现有的工作进行了总结， 指出了存在的不足 2 、细化、扩展了有关时间的严格数学定义及性质，如时态型、 时态因子、时间粒度、基时态型、相对长度等，对有关时间划分的理 论和性质进行了研究 3 、在本文的一整套有关时间的定义下，构造了事件模型及事件 间的运算定义，给出了相应的性质对事件序列所包含的时态约束进 行了形式化描述，并对时态约束间的包容关系进行了研究 4 、提出了基于时态约束的关联规则模型，对有关的支持度、置 信度的计算给出了定义，对时态关联规则的约简理论进行了探讨 5 、对本文提出的基于时态约束的关联规则给出了相应的的挖掘 算法，并以股票对象为例，对深圳的二十多只股票的近十年的数据进 行了实验，得出有意义的规则，研究了算法的性能同时又提出另一 种分段挖掘方法，定义了相应的闽值有效度来提高该类关联规则 的可信任度，并给出了实验结果 6 、对基于时态约束的关联规则的周期性挖掘进行了研究，给出 了相关阈值的定义及相应的算法也以股票为例进行了数值实验，对 算法的性能及意义进行了分析 本文的研究将数据之间的关联性与时间联系起来，寻找的是事 件之间在时间上的相关性，而且也研究了这种相关性的周期性对于 股票市场、天气变化、地质情况、医疗过程等领域还是有定的预 测及决策作用的本文中的预测不同于数学中的线性回归，不是运用 数据的拟合，而是对连续型数据进行特征离散化后再进行挖掘，这 湘潭大学硕士学位论文 样减小了数据处理的规模及难度 本文后面的内容是如下安排的： 第二章给出了与时间有关的数学概念及相关性质及事件模型的 构造，给出了基于时态约束的关联规则的模型，对相关的问题进行了 研究，初步探讨了规则约简理论 第三章给出了基于时态约束的关联规则挖掘的整个过程讨论了 时态数据趋势特征的获取，给出了相应的具体算法及优化算子，分析 了算法的可行性及时间复杂度对十多年的股票数据进行了一些实 验，通过实验结果对算法的性能进行了分析另外还提出了关联规则 的另一个度量有效度，进行了分段挖掘，给出了相应的算法及实 验结果 第四章对基于时态约束的关联规则的周期性挖掘进行了研究，介 绍了周期的获取方法，相关的阈值定义，给出了相应的挖掘算法，并 进行了实验 在总结和展望中，对本文所做的一些工作进行了总结，体现了其 实际意义，对将来所需努力的方向作了展望 湘潭大学硕士学位论文 9 第二章模型构造 本章介绍了时态型、时态因子和时态粒度等基本概念和性质，并 对其做了扩展，给出了相应的概念和性质依此构造了事件模型及事 件运算，对时态约束进行了形式化描述，给出了基于时态约束的关联 规则模型，对相关的的问题进行了研究，描述了几类具有实际意义的 关联规则，最后对规则约简理论进行了探讨 2 1 与时间有关的概念及相关性质 时间这种最基本的概念和数学中的集合、信息科学中的信息一 样难以精确地定义，我们将对时间的本质进行探讨，以便有助于时 态数据库中时间的表示及时态挖掘中时态模型的建立 在许多现实数据库中都存在时态语义的问题，而且时间的长度 对于关联规则的有效性、周期的长度以及序列模式都有影响在文【8 ， 9 1 中也有时态型的定义，但本文的时态型定义是严格的数学定义，更 具广泛性，它形式化了时间的直观概念 我们将现实中的时间看成是一条实数轴月( 也可以看作一无限集 合) ，两端无限延伸，原点为公元元年1 月1 日0 0 ：0 0 ：0 0 ( 时间单位 为无限小) ，r 上的每点t 代表时刻，称之为绝对时刻( a t t ) a b s t r a c t t i m et i c k ，每个区间【f ，f 1 ( 或半开半闭或开或闭) 表示一段时间，称之 为绝对时间( 伽) a b s t r a c tt i m ei n t e r v a l ，每个a t i 是a t t 的集合 在具体问题中，如果以秒为最小的时间单位，则2 0 0 0 年2 月2 日 0 2 ：0 3 ：5 0 就是一个绝对时刻，从2 0 0 0 年2 月2 日0 0 ：0 0 ：0 0 到2 月2 日2 3 ：5 9 ：5 9 就是一个绝对时间，也就是我们生活中指的2 0 0 0 年2 月 2 日实际上，绝对时刻与绝对时间是相对的概念，它们可以相互转 化即便是以秒为单位的一个时刻，它也是一段时间；而一天也可看 成一时刻，这主要取决于研究实际问题中时间粒度的确定 我们现实中所说的时间都是将绝对时刻转换为所需要的某种时 间单位来体现的，事件实质是在无限小的那一时间点发生的，如某 车祸是在那一无限小的时刻发生的，而我们可以说某年某月某日某 时发生了某车祸，也可以说某年某月某日发生了某车祸，还可以说 某年某月发生了某车祸，这也是时问的不确定性因此我们有必要研 湘潭人学硕士学位论文 1 0 究时间的性质 2 1 1 基本概念及性质 定义2 1 p 删设p 是从a r r rt 到a t i u ( t ) 的映射，也即r 一2 8 ， 如果口满足下列性质，则我们称卢为时态型，卢o ) 为肛的时态因子 1 ) ( 非空性) t e 肛( f ) 2 ) ( 单调性) 若t 。 f 2 且( f 1 ) n 卢( f ：) 一g ，vt u ( t 。) 和vt l z ( t ：) ， t c t ”记作o 。) c p ( f 2 ) 3 ) ( 同一性) v f 一( f ) ，( f = ( f ) 4 ) ( 有界性) vr ，p o ) ，k l t + m 口 显然，时态型p 是对时问数轴曰的一个划分，每个时态因子肛( f ) 是一个a t t 集合秒、分、小时、日、周、月和年等可以用来划分时 间数轴尼并且它们都满足上述性质，因此都是时态型，见图2 1 r iiliiii ilii ilii iiiilii liiiiii iiiii。 ill lliliiiiiil iill i i liillill iil i 7 l 周 天 月 绝对时间 图2 1 有关时态型的映射 定义2 1 2 “1v t e r ，若o ) 为单点集，称为原子时态型反之 称肛为非原子时态型口 由上述定义可得出下列性质： 性质2 1 1 若一t 2 ，则p “) n 芦( f 2 ) 一g 或者n ) 一也) 证明：依定义2 1 1 ，p 瓴) 和p 也) 是两个集合集合间有两种关 系， 即肛“) n 肛( f ：) = o 或t l ( t , ) f f l # ( t ：) 0 若肛“) n ( f ：) * 0 ， 设 u ( t 。) n 也) 一 ) ，根据定义2 1 1 中的同一性，有i t ( t 。) 一肛( ) = 肛p ：) 得证口 性质2 1 2 “4 叫有非原子时态型肛，对于一段时间口，r 】，必存在 力个实数t 1 ) 1 2 ， ) l n 且 t 2c c t ，使得i t , 丁- 】0 肛“) ，其中 i i l 湘潭大学硕士学位论文 v i ，( 1 2 ，一) ，i ，时，a ( t , ) n a ( t j ) = o 证明m ：根据定义2 1 1 中的非空性r 2 ( 0 ，可得集合 u p ( ，) i f e i t ，t 】) 覆盖口，r 1 【7 ，丁1 是一有界闭集，根据有限覆盖定理皿7 1 和性质2 1 1 可知结论成立口 性质2 1 3 v t r ，( r ) 存在上确界s u p p ( t ) 和下确界i n f u ( t ) 也且p v t , o ) ，s u p a ( t ) ，i n f ( t ) 证明：由时态型的单调性和有界性可得证口 定义2 1 3时态因子i t ( t ) 的绝对时间长度定义为： a b s l e n ( a ( t ) ) = s u p t ( t ) 一i n f , u ( t ) 。口 这里我们用“绝对”来区别于定义2 1 5 中的相对长度 显然，时间度量依赖于当前所考虑的问题的最小粒度一年可以 划分为1 2 个月，也可以划分为3 6 5 天哪种划分更适用? 在河床沉 淀物的地质数据库中，以天作时间精度最合适不过了；而在研究全 国工资情况问题中，月或年才是合适的时间精度基时态型有助于解 决这些问题，下面给出有关定义及性质 性质2 1 4有两时态型胁v ，满足对于v t r ， a b s l e n ( v ( t ) ) a b s l e n o t ( t ) ) ，则砸) 亡( ，) 或v ( t ) t 1 i t ( t ) 彩 证明：根据时态型的定义的非空性，有t v o ) ，r o ) ，可得 v ( t ) c 、a ( t ) d 由时态型的定义可知，时态因子是一集合，故存在包 含关系v ( f ) c o ) 口 性质2 1 5 v t r ，a b s l e n ( v ( t ) ) s a b s l e n ( p ( t ) ) 若3 t , r 使得 v ( ) 旺( ) ，贝u v ( o c 7 i u ( t , ) u i t ( t j ) ，r ，芒( ) 且r ，v “) 证明：由于时态是定义在一连续的集合上的，且根据其非空性， 可得v ) c a ( t , ) u a ( t a 口 定义2 1 4 设“v 是2 个时态型，且满足v tr ， a b s l e n ( v ( t ) ) a b s l e n ( 1 a ( t ) ) v t r ，对于v 的时态因子v ( f ) ，若仅存在卢的 唯一时态因子o ) 使得v ( f ) c 卢( f ，称v 是2 的一个基时态型口 湘潭大学硕士学位论文 1 2 显然，秒是分、小时、日、周、月、季度和年的基时态型，因 为每秒是完全落在某分、某时、某天的日是周、月、季度和年的基 时态型，依此类推而周不是月、季度和年的基时态型，由于时态因 子的交叠，一周可能横跨两个月例如2 0 0 3 年1 月的第五周 ( 2 0 0 3 1 2 6 _ _ 2 0 0 3 2 1 ) ，既属于一月份，又属于二月份 性质2 1 6 设v 是的基时态型，则v t r ，有v ( o c ( f ) 证明：对于v t r ，由定义2 1 4 可得，仅存在唯一的时态因子 ( r 使得v ( f ) c p ( t 9 由定义2 1 - 1 中的非空性可得t e v ( o ，贝k j t ( f 根据定义2 1 1 中的同一性可得( ，) = p ( t 9 ，因而砸) 匕( ，) 口 性质2 1 7 设，y 是2 个时态型，且v 是的一个基时态型，则 对于的任何一个时态因子( ，) ，一定存在 个实数t 2 ，使得 k t ) = u ，( ) ，其中 f 2 ，v f ，_ ， 1 2 ，耐，f _ ，i j 寸v ( t , ) n v ( t j ) = a ， t - i 同时_ 船跆疗( ( f ) ) = a b s l e n ( v ( t , ) ) f 一 证明：时态因子k t ) 是一个有限时间区间，由性质2 1 2 可知 必存在m 个实数 ，f 2 ，使得( f ) c u y ( ) ( 其中 f 2 o ， v i ，j l 2 ，叫 ，f j l 对k t , ) n k t j ) = g ) 咖( 丘) ，若v ( ) n ( d = a ，贝u 删 掉v 以) 对于剩下的v 的时态因子重新排列其下标为 ，如，此时 卢( f ) u y ( ) 且v f 1 2 ，行) ，v ( t , ) n k t ) * 0 t = l 根据已知，v 是的一个基时态型，由定义2 1 4 知 v v ( ) ( f = 1 2 埘) 有且仅有的唯一时态因子“) 使得v ( ) c “) 因此 ( d n 户( t ) g 依性质 2 1 1 有声( f ) = “) ( f - 1 2 旃) 这样 h y “) c o ) ( f = 1 2 h ) ，故u l ，瓴) 声( f ) 可以得出( ，) ：0 y ( ，) 显然彳蛐：似( ，) ) ：杰彳细妇( 呕) ) 口 f - l，t l 定义2 1 5 设a ，v 是2 个非原子时态型，且v 是z 的个基时态 湘潭大学硕士学位论文 1 3 型依性质2 1 7 有4 0 = u y ( ) ，其中t i r ， 乞 乙， i - 1 v i ，_ ， 1 2 ，力) ，i _ ，时v “) n v ( f ，) = o ，则时态因子( f ) 相对于时态型1 ， 的相对长度为h ，记作r e l e n ( t u ( t ) ) = h 口 当时间精度为天时，一个月可近似看为3 0 天，当精度为小时时， 一个月就近似看为7 2 0 小时在多时间粒度的问题中，时态因子的相 对长度的定义给时间区间的长度度量带来很大方便 定义2 1 6 “3 设，v 是2 个非原子时态型，且y 是的一个基时态 型我们有如下定义： 若的所有时态因子的绝对长度都相等，则称i j 为一个时间 粒度 若v 是一个时间粒度，则称v 为i a 的个基时间粒度 若的所有时态因子的长度可以划分为有限的几类，则称为 一个粗时间粒度( c o a r s e t i m eg r a n u l a r i t y ) 若v 是一个粗时间粒度，则称v 为f 的一个基粗时间粒度口 所有的时间粒度又是粗时间粒度根据性质2 1 2 我们可得出推 论2 1 1 推论2 1 1 【1 】任给定一个时间区间可被任意一个时间粒度的有 限个时态因子覆盖口 推论2 1 1 告诉我们，时态粒度是一个时间区间的划分，每 个时间区间都可以被等长度的时间因子度量在我们日常生活中，我 们常用的时间粒度是秒、分、小时、日和周，而月、季度和年仅是 时态型，因为它们不具有等长的绝对时间长度显然秒是分、小时、 日、周、月、季度和年的基时间粒度，小时是日、周、月、季度和 年的基时间粒度，日是周、月、季度和年的基时间粒度，但周不是 月、季度和年的基时间粒度 2 1 2 时态型的连续性 在理论上，时间是无限的、连续的，时态型是无限个时问点的 集合，而在实际应用中，我们则将时间有限化、离散化，用有限个 时态型的因子来表示时间若系统采用某种时间粒度作为最小的精 湘潭大学硕士学位论文 1 4 度，即时间的增量单位，则认为此时态型是不可再分的，此时的时 间轴不再是无限连续的，而是可数的、有限连续的 定义2 1 7 工2 8 ，若现r 且岳z ，满足 t k w 具体有这样的相关事件：在连续三天内石化股的开盘价星振荡 状态，则间隔四天后，其开盘价呈小涨状态 上述的几个事件间的蕴涵，其中最显著的特征就是事件间的时 间特征，即事件间隐藏着一种时态约束本文侧重于发现具有时态 约束的关联规则，规则中的事件间的时间距离是具体的，如在同一 天发生的事件，在某特定事件发生的三周后所发生的事件，发生时 间相隔两个月的事件等等根据上述的有关时间的定义及性质，我们 将对时态约束进行形式化的描述 有事件对 ( 4 ，e ”，v ( f ，1 ) ) ，( 4 ，p ”，v ( t ：) ) ) ，v ( t ，：) v ( t ，) ，所包含的时间 对p = v p 。) ，v ( t ：) ) ，p 所包含的约束主要是事件问在发生时问上的距 湘潭大学硕士学位论文 1 9 离a b s d i s ( p ) = s u p ( v ( t ：”i n f ( v ( t 。) ) 指两事件问的绝对距离，而我们在实 际操作中，多考虑在某时态型下事件问的相对距离 r e l e n ( a b s d i s ( p ) ) ”= k 定义2 3 2 对于同一时态型下的一事件序列v = ( 一。口”，竹。) ) ， ( 4 。，p ”，v ( t ，) ) ，( 4 ，v ( f ，) ) ) ，v ( t ，) v ( t ，) v ( t ，) ，包含的时态约 束为c o n s t r a i n t ( v ) = v o ，v ，庐，v ) ，简记为c = r e l e n ( a b s d i s ( p 1 ) ) ”， 只= v ( t ，) ，v ( r ，) ) ( ( 4 。，e ”，v o ) ，( 4 。，e 9 ，v 1 ) ，( 4 。，伊) ) 称为时态约 束为f 的相对事件序列啻，v ( t j 。) 称为该事件序列的基时间，而事件组 矿称为满足该相对序列的实例口 该定义从理论上给出了事件间时间间隔的计算，在实际挖掘中， 我们通常是考虑一段时间上的事件，因而事件间的时间间隔可通过 时间的划分来得到，在数据库中体现为记录问的间隔，在后文中具 体介绍这里我们仅给出了同时态型下发生的事件问的时态约束，有 关多粒度间的约束有待以后探讨 如事件序列1 - ( 石化股，开盘价小涨，1 9 9 6 9 1 8 ) ，( 石化股，开 盘价大涨，1 9 9 6 9 1 9 ) ，( 石化股，收盘价小跌，1 9 9 6 9 2 0 ) ，( 石化股， 最低价小涨，1 9 9 6 9 2 3 ) ，设时态型v 代表天，则该序列所包含的时 态约束为 矿，矿， ，2 ，v 5 ) 事件序列2 f ( 石化股，开盘价小 涨，1 9 9 7 6 2 9 ) ，( 石化股，开盘价大涨，1 9 9 7 6 3 0 ) ，( 石化股，收盘价 小跌，1 9 9 7 7 1 ) ，( 石化股，最低价小涨，1 9 9 7 7 4 ) 所含时态约束与 事件序列1 中的一致，而且相应的状态属性也一致 定义2 3 3 所有满足时态约束c 的事件空间为 = x 。，置。，x ) lc o n s t r a i n t ( v ) = c ，置( 4 ，2 ，i t ，t ) ) ，记为舻。 n u m ( g a ，) 为该事件空间所包含的事件组的数目口 从历史事件中挖掘规则是要用于将来的预测和决策的，例2 i 中的事件都是具体时问下发生的，是历史的，不可再现的，我们力 求这样形式化此类带有时态约束的关联规则，使其可以描述一类具 有相同时态约束的事件组中各事件之间的关联 定义2 3 4 将事件序列所包含的时态约束中的相对时问分类， 其种类数为该事件序列的长度长度为k 的事件序列记为 湘潭大学硕士学位论文 2 0 l e - e v e i lt s e q u e n c e u 如单对象事件序列 ( 4 ，e o ，v o ) ，( 4 ，e 1 ，v “) ，( 4 ，e ”，v ) ) ， v f ，：o ，i 2 肺，h f 矗，其长度为时1 对于多对象的事件序列 ( 4 。，p 。，v o ) ( 4 ，一，p ) ，( 4 ，矿，v k ) ) ， ，办，可以相等，将相对时间按吩划 分，事件序列长度为相对时间p 的种类数 ( 4 ，e o ，v o ) ，( 4 ，p 1 ，v o ) ，( 4 ，e 2 ，v 2 ) ) ，其长度为2 定义2 3 5 称事件序列v i = ( ( 4 - ，e 0 ，v b ) ，( - 4 ，p i ，沙k ，( 4 ，矿，毋) ) 包 含于事件序列v = 1 ( 4 ，e j o ，v “) ，( 4 ，e ，