（计算机应用技术专业论文）时态数据挖掘技术的研究与应用.pdf

中山大学硕士学位论文 时春数据挖掘技术的研究与应用 摘要 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取 出隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。在 现实世界中，很多数据均是时态数据。与在普通事务数据库中进行数据挖掘相比， 时态数据挖掘能更好地反映数据中所隐藏的与时间有关的知识。时态数据挖掘作 为数据挖掘的一个重要分支，引起了人们极大的兴趣。有关这方面的研究才起步 不久，还存在许多问题亟待解决。 本文在研究了国内外现有的时态数据挖掘相关理论的基础上，对时态数据挖 掘的相关技术和发展状况进行了分析，讨论了时态关联规则挖掘的相关概念、性 质和一个算法，建立了一个基于时态数据库的挖掘框架，并在此基础上实现了一 个零售行业的时态数据挖掘系统。最后通过实例研究，表明所建立的系统能够有 效率地挖掘到用户感兴趣的时态知识。 关键词：数据挖掘，时态数据库，时态关联规则，t d m f 2 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 a b s t r a c t d a t am i n i n gi st h ep r o c e s so fa b s t r a c t i n gu n a w a r e ，p o t e n t i a la n d u s e f u li n f o r m a t i o na n dk n o w l e d g ef r o mp l e n t i f u l ，i n c o m p l e t e ，n o i s y ，f u z z y a n ds t o c h a s t i cd a t a i nt h er e a lw o r l d ，al o to fd a t aa r eo f t e nt e m p o r a l d a t a t e m p o r a ld a t am i n i n gc a ng e tm o r eu s e f u lt e m p o r a lk n o w l e d g ef r o m d a t a b a s et h a nc o m m o nd a t am i n i n g t h e r e f o r e ，t e m p o r a ld a t am i n i n gb e c o m e s av e r yi n t e r e s t i n gb r a n c ho fd a t am i n i n g t h es t u d yo ft e m p o r a ld a t am i n i n g i sa ti t se a r l ys t a g e ，a n dm a n yp r o b l e m ss t i l le x i s ti nt h ef i e l dt h a t n e e d e dt ob es o l v e d o nt h eb a s i so fr e s e a r c ho nt h ee x i s t i n gt h e o r ya b o u tt e m p o r a ld a t a m i n i n g ，t h ep a p e rh a sa n a l y z e dt h et e c h n o l o g i e sc o n c e r n e da n dab r i e f h i s t o r yo ft h ef i e l d ，d i s c u s s e dt h ec o n c e p t sa n dt h ep r o p e r t i e sa n da a l g o r i t h ma b o u tm i n i n gt e m p o r a la s s o c i a t i o nr u l e s ，a n dd e v e l o p e dad a t a m i n i n gf r a m e w o r kw h i c hf o u n d e do nt e m p o r a ld a t a b a s e ，a n dr e a l i z e da t e m p o r a ld a t am i n i n gs y s t e mi nr e t a i l i n gb a s e do nt h ef r a m e w o r k f i n a l l y ， t h ep e r f o r m a n c es t u d ys h o w st h a tt h es y s t e mi se f f i c i e n tt om i n eu s e f u l i n t e r e s t i n gi n f o r m a t i o n k e yw o r d s ：d a t am i n i n g ，t e m p o r a ld a t a b a s e ，t e m p o r a la s s o c i a t i o nr u l e s t 删f 3 中山大学磺士学位论文 时态数据挖掘技术的研究与应用 第一章引言 1 1 时态数据挖掘技术产生的背景 随着数据库技术的发展和数据库应用的普及，数据库的数量越来越多，数据 库的规模越来越大，从而出现了所谓“数据丰富，知识贫乏”的问题：同时人们 也不满足对数据库进行查询、检索等简单地操作，希望从中发现知识，来辅助高 层人员的决策。于是，出现了一个新的数据库研究课题一数据挖掘。它在人工 智能领域中又称为数据库中的知识发现( k d d k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) 。数据挖掘是指从大型数据库或数据集的数据中提取人们感兴趣的知 识。这些知识是非平凡的、隐含的、事先未知的、潜在有用的信息，通常是以概 念、规则、规律、模式、约束、可视化等形式来表示。 在现实世界中，时间无所不有，无处不在，很多信息都是随着时间变化的。 这种随着时间变化的信息称为时态信息( t e m p o r a li n f o r m a t i o n ) ，用于记录时 态信息的数据就是时态数据( t e m p o r a ld a t a ) 3 2 。时态数据反映了事物发生 发展的过程，有助于揭示事物发展的本质规律。作为处理时态数据的时态数据库 已经得到广泛研究和应用，关于时态数据的挖掘研究也引起了越来越多学者的关 注。 时态数据挖掘是数据挖掘方面的一个重要的扩展，它不仅可以挖掘有关状态 方面的信息而且可以挖掘行为方面的信息，揭示出时间上的相关关系，其中的部 分时态关系可以进一步转化为因果关系。在挖掘技术中引入时间使我们可以对事 件进行捧序，从而发现因果关系。如果忽略了时态属性或仅仅把它作为普通的数 值属性来进行处理的话是很难发现这种关系的。与只挖掘在一个时间点上的事物 的状态相比，时态挖掘可以挖掘出事物的行为特征，这样可以帮助我们理解“为 什么”的问题，而不是简单的。是什么”的问题。 1 2 国内外研究现状 1 2 1 时态数据挖掘现状 6 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 我们把在时态数据中进行时态知识发现的过程称为时态数据挖掘。近年来， 时态数据挖掘研究主要有以下几个方面“1 。 1 、趋势分析 在处理时序数据时，目前一般有4 种主要的变化。 a 、趋势( 长期) 变化：它用于反映一般的变化方向，其时序图是在较长时 间间隔上的数据变化。这种变化反映为一种趋势线或趋势曲线。 b 、循环变化：主要是指循环性，即趋势线或曲线在长期时间内呈摆动迹象。 它可以是也可以不是周期性的。即在等时间间隔之间，循环不需要沿着同样的模 式演进。 c 、季节性变化：它反映的是每年都重复出现的事件，如春节前过年物资的 销售会突然增加很多。换句话说，季节性交动是指同一或近似同一的模式，在连 续几年的有关月份期间重复出现。 d 、随机性变化：它反映的是随机或者偶然事件引起的零星时序变化。如火 灾、瘟疫或劳工纠纷等。 通过对趋势、循环、季节和随机性成分的变动的系统分析，使人们可以在较 合理的情况下，制定出长期或短期的预测。文献 2 对计算机网络信息安全进行 了趋势分析，并将趋势进行了分类：内因和外因趋势、时态趋势、空间趋势、关 联趋势和混合趋势。 2 、相似性搜索 相似性搜索指的是找出与查询序列相似的时态数据序列( 子模式匹配) 3 ， 或彼此相似的序列( 全模式匹配) 4 。在对金融市场的分析( 如股票数据分析) ， 医疗诊断分析，和科学与工程数据库分析等领域中，时态数据中的相似性搜索大 有用武之地。在具有时态约束的数据库中进行相似搜索，通常使用欧氏空间距离 作为相似性计算的依据。两种常用的数据转换有：离散傅立叶转换( d f t ) 5 和离 散小波转换( d w t ) 6 。 3 、与时间有关的序列模式挖掘 许多有关序列模式挖掘的研究主要针对于符号模式( s y m b o l i cp a t t e r n ) 。 如时间序列的持续时间，被发现的模式中时间之间的间隔等。序列模式挖掘的方 法主要是a p r i o r i 算法，也有基于数据库投影的序列模式生长技术等。对序列模 7 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 式挖摘，存在一些参数，其取值如何将严重影响挖掘结果。第一个参数是时间序 列的持续时间t ；第二个参数是时间重叠窗口( e v e n tf o l d i n gw i n d o w ) w ：第三 个参数是被发现的模式中时间之阃的间隔。 4 、周期分析 周期分析是指对周期模式的挖掘，即在时序数据库中找出重复出现的模式。 周期模式挖掘的问题可分为三类： a 、挖掘全周期模式。 b 、挖掘部分周期模式。 c 、挖掘循环或周期关联规则。 有关部分周期模式或周期关联规则挖掘的研究 7 儿8 3 9 应用了a p r i o r i 特征启发式或采用了变通的a w i o r i 方法。 1 2 2 时态关联规则挖掘现状 与在普通事务数据库中进行关联规则挖掘相比，时态关联规则( 定义见4 3 i ) 能更好地反映数据中所隐藏的与时间有关的知识。近几年，国内外有许多学者就 此进行了研究，而且已成为l ( d d 的热点之一。时态关联规则的研究主要有下面 几个方面 5 0 ： l 、关联规则成立的时间 传统的关联规受i j 挖掘很少考虑关联规则的时间适甩性，然而每个关联规贝l j 都 有其成立的时间区域。如在购物篮分析中，对各个商品项目的购买时闻加以考虑， 得出了在某段时间下成立的关联规则。在文献 9 中提出了具有时间属性的关联 规则，其发现算法是在a p r i o r i 算法上的扩展，当遍历数据库以对候选项集进 行计数时，两个项目序列不仅要匹配，而且两者的相关有效时间也需要归并，提 出了时间区间的延展概念及方法、时间区间的归并概念及技术。 在文i t 0 】中，引入了交易项目集的生命期，其支持度只在其生命期内考察。 此文所介绍的时态关联规则是对一般的非时态关联规则的扩展。这种方法主要是 针对商品交易数据库进行的，它的基本思想就是将频繁项集的搜索限制于其生命 期间。这种对项目集赋予生命期的方法可以发现一般关联规则挖掘方法所不能发 现的规则。 8 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 文 9 1 0 1 1 1 2 1 3 主要是针对项目发生的时间区域来扩展项目集，在 连接操作上考虑了项目的时间属性，以决定规则的成立时间。这些研究涉及的主 要是事件与时问之间的关联，考虑了一定时间段内的阶段性关联规则，未涉及到 事件之间的时态约束。已有的这些研究主要是对数据库的每个元组考虑其发生时 间，强调的是关联规则成立的时间属性，以表明所发现的知识何时是有效的。在未 考虑时间属性时，所得的规则假定是永远有效的。在考虑了时间属性后，所得到的 规则将可以更好地描述客观现实情况，因而也会更有价值。 2 、关联规则的周期性 主要是研究有关周期时间区域的划分。文献 1 4 把长度为l 的周期划分为等 间隔的时间区域，分别计算每个时间区域中项目子集的支持度以求周期关联规 则。这样的实现方法很简单，周期时间段是人为确定的，但在某些领域不能充分 反映数据的内在规律。如以小时为粒度来划分每天的销售事务，则像“每天早上 6 ：2 0 一8 ：3 0 时间范围内买牛奶的顾客会买面包”这样的规则就不能够被发现。 在某些领域，周期的获取适合由聚类来实现可以根据事务发生的频度利用聚类 分析来实现对时间段的划分 1 3 。这样，时间段的长度根据事务发生的集中度自 动求出，而不是人为主观规定，这与时态关联规则的实际意义相一致也可依各 项目的频度来聚类。根据聚类结果把每个项目分成几个动态的时间区域 1 5 。 3 、时态关联规则模型的建立 由于时态关联规则的挖掘是在带有时问属性的数据上进行的，因而有关时态 数据的表示也需进行研究，以便于事件和时态规则模型建立。文 1 6 2 4 对有关 时间的概念及性质从数学理论上进行了的定义和证明，如时态型、时态因子的定 义及性质，仅建立了简单时态事件模型，对部分特殊情况下的时态关联规则的挖 掘思想进行了简介，但未深入算法的研究。对于复杂的时态关联规则以及通用的 时态关联规则模型也没有进行研究。文 1 6 - 2 4 中的有关时间的定义较文 2 5 2 7 】 中的定义更具有广泛性、更直观、更易于理解。 这些模型可以描述企业当前发展的现状和规律性，也可以用来预测，以辅助 决策。 9 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 1 3 本文的工作 与在普通事务数据库中进行数据挖掘相比，时态数据挖掘能更好地反映数据 中所隐藏的与时间有关的知识。时态数据挖掘已经成为一个非常重要的研究课 题。本文具体对以下几个方面进行了研究： 1 、论述了时态数据挖掘的研究现状，以及时态关联规则挖掘的研究进展。 2 、研究了时态数据挖掘特别是时态关联规则挖掘的相关概念、性质，给出 了挖掘算法的形式化描述。 3 、建立了一个时态数据挖掘框架，并在此基础上构造了一个用于零售业的 时态数据挖掘系统。 4 、通过实例研究，表明所建立的系统能够有效率地挖掘到用户感兴趣的时 态知识。 下面介绍本文各章节的具体内容安排： 第章，绪论，简要介绍了论文的背景，当前的研究现状进展，以及论文的 主要工作。 第二章，数据挖掘，主要论述了数据挖掘的基本理论，包括数据挖掘的定义， 功能，数据挖掘的一般过程，队及数据挖掘的常用技术。 第三章，时态数据库，主要论述了时态数据库技术的起源和发展，时态数据 库中的基本概念，时态数据库的分类，另外简单介绍了一种时态数据库产品 ( t i 舱d b ) 。 第四章，时态关联规则挖掘算法，讨论了关于时态关联规则挖掘的基本概念 与性质，以及相应的挖掘算法，并且结出了算法的形式化描述。 第五章，基于t d k l f 的时态数据挖掘系统，阐述了时态数据挖掘框架( t d m f ) ， 并对基于t d k i f 建立的时态数据挖掘系统进行了论述，在本章节末给出了一个应 用实例及其结果分析。 在结束语中，对本文所做的一些工作进行了总结和展望。 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 2 1 数据挖掘的起源 第二章数据挖掘 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千千万 万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，这一势头仍 将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时 代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹 没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据真正成为一个公 司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大 量的数据可能成为包袱，甚至成为垃圾。需要是发明之母，因此，面对人们被数 据淹没，人们却饥饿于知识的挑战，数据挖掘和知识发现( d 呶d ) 技术应运而生， 并得以蓬勃发展，越来越显示出其强大的生命力。 从商业数据到商业信息的进化过程中，每一步前进都是建立在上一步的基础 上的( 见表2 1 ) 。从表中我们可以看到，第四步进化是革命性的，因为从用户 的角度来看，这一阶段的数据库技术已经可以快速地回答商业上的很多问题了。 从表中还可以清晰的看到，数据挖掘的应运而生是历史必然的选择，它符合人类 社会认识事物的客观发展规律，仅从这一点上来讲，处予流行中的数据挖掘的前 景还是非常乐观的。 表2 - 1 数据挖掘的起源 进化阶段商业问题 支持技术 产品厂家 产品特点 数据搜集 “过去五计算机、i b m 、c d c提供历史 ( 6 0 年代)年中我的总收磁带和磁盘性的、静态的 入是多少? ”数据信息 数据访问 “在纽约 关系数据 o r a c l e 、 在记录级 ( 8 0 年代)的分部去年三库( r d b m s ) ，s y b a s e 、提供历史性 月的销售额是结构化查询语i n f o r m i x 、i b m 、 的、动态数据 多少? ”言( s q l ) ，o d b cm i c r o s o f t 信息 数据仓“在纽约联机分析p i l o t、 在各种层 中山太学硕士学位论文时卷数据挖掘技术的研究与应用 库；决策支持的分部去年三 处理( 0 l a p ) 、c o m s h a r e、次上提供回溯 ( 9 0 年代)月的销售额是多维数据库、a r b o r 、c o g n o s 、的、动态的数 多少? 洛杉矾 数据仓库 m i c r o s t r a t e g y据信息 据此可得出什 么结论? ” 数据挖掘“下个月高级算 p i l o t 、 提供预测 ( 正在流洛杉矶的销售 法、多处理器 l o c k h e e d 、i b m 、 性的信息 行)会怎么样? 为计算机、海量s 6 i 、其他初创 什么? ”数据库公司 2 2 数据挖掘的定义 数据挖掘从产生至今已有多种定义，其中得到公认的是：数据挖掘( d a t a m i n in g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中， 提取出隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好 几层含义：数据源必须是真实的、大量的、含噪声的：发现的是用户感兴趣的知 识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识， 仅支持特定的发现问题。何为知识? 从广义上理解，数据、信息也是知识的表现 形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看 作是形成知识的源泉。原始数据可以是结构他的，如关系数据库中的数据；也可 以是半结构化的如文本、图形和图像数据；甚至是分布在网络上的异构型数据。 发现知识的方法可以是数学的，也可以是非数学的i 可以是演绎的也可以是归 纳的发现的知识可以被用于信息管理，查询优化。抉策支持和过程控制等，还 可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的 应月j 从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需 求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理 统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这 一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发 1 2 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有 发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要 能够易于被用户理解，最好能用自然语言表达所发现的结果。 数据挖掘其实也是一类深层次的数据分析方法。数据分析本身已经有很多年 的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时 计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在， 由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再 是为了分析的目的而收集的，而是由于商业运作而产生。分析这些数据也不再是 单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利 润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值 的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高 竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。 2 3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖 掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下几类功能。 l 、自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析 的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问 题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它 可预测的闻题包括预报破产以及认定对指定事侔最可能做出反应的群体。 2 、关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之闻存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中 数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有置信度 和支持度。 3 、相关性分析 数据中许多属性可能与分类和预测任务不相关。例如：记录银行贷款申请是 1 3 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 星期几提出的数据可能与申请的成功不相关。此外，其他的属性可能是冗余的。 因此，可以进行相关性分析，删除学习过程中不相关的或冗余的属性。在机器学 习中，这一过程称为特征选择。 4 、聚类分析 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们 对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括了划 分方法，层次的方法，基于密度的方法和基于模型的方法。还有一些聚类算法继 承了多种聚类方法的思想。 5 、概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 共性，它将大的任务相关的数据集从较低的概念层抽象到较高的概念层。这里有 两种主要的方法：数据立方体( 或o l a p ) 方法和面向属性的归纳方法。生成区 别性描述的方法很多，如判定树方法、遗传算法等。 6 、偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏 差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与 模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结 果与参照值之间有意义的差别。 2 4 数据挖掘的过程 数据挖掘过程是多个步骤相互连接、反复进行人机交互的过程。 ( 1 ) 数据清理：清除噪声或不一致数据 ( 2 ) 数据集成：多种数据源可以组合在一起 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据 ( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作 ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式 “ 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识 2 5 数据挖掘的常用技术 1 、人工神经网络 仿照生理神经网络结构的非线形预测模型，通过学习进行模式识别。粗略的 说，神经网络是一组连接的神经单元，其中每个连接都与一个权相联。在学习阶 段，通过调整神经网络的权，使得能够预测输入样本的正确类标号来学习。由于 单元之间的连接，神经网络学习又称连接者学习。它的优点包括对噪声数据的高 承受力，以及它对未经训练的数据分类模型的能力。 2 、判定树 “什么是判定树? ”判定树( d e c i s i o nt r e e ) 是一个类似于流程图的树结构。 它和算法与数据结构中的二叉判定树的概念很类似。其中每个内部节点表示在一 个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或类分布。 树的最顶层界定就是根节点。 3 、遗传算法 基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计方法的优 化技术。根据适者生存的原则，形成由当前群体中最合适的规则组成新的群体， 以及这些规则的后代。典型情况下，规则的适合度( f i t n e s s ) 用它对训练样本集 的分类准确率评估。后代通过使用诸如交叉和变异等遗传操作来刨建。 4 、最近邻算法 将数据集合中每一个记录进行分类的方法。最i l 缶近分类是基于要求的或懒散 的学习法，即它存放所有的训练样本，并且直到新的( 未标记的) 样本需要分类 时才建立分类。它也可用于预测，即返回给定的位置样本的实数值预测。 5 、a p r i o r i 算法 它是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这 样的事实：算法使用频繁硬集性质的先验知识。它用一种称作逐层搜索的迭代方 法，k 一项集用于探索( k + 1 ) 一项集。首先找出频繁卜项集的集合。然后利用前者 找出2 - 项集的集合，如此迭代，直到不能找出频繁k 一项集。最后由频繁项集产 生关联规则。 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 6 、频繁模式增长( f p - 增长) 和上面的方法相比，它是一种不产生候选的挖掘频繁项集的方法。它构造一 个高度压缩的数据结构( f p 一增长) ，压缩原来的事物数据库。它聚焦于频繁模式 增长，避免了高代价的候选产生，获得更好的效率。 采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过这些 工具所面对的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工 业标准的数据仓库和联机分析系统中去了。 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 第三章时态数据库 时间是自然界无所不在的客观属性，所有信息都具有相应的时态属性。随着 数据库与信息技术的深入发展，信息系统面临着许多新的应用和新的需求，对时 态信息处理的需求越来越迫切。时态信息处理已成为许多新一代数据库与信息系 统的关键技术，特别是在电子政务、电子商务、数据仓库等信息系统中扮演着日 益重要的角色。 传统的数据管理系统( 层次、网状和关系数据库) 对时态数据未作专门的处理 和对待，而只作为一般的属性值、作为用户定义时间进行存储和管理。因此，传 统数据库只反映了个对象的发展全过程中在某一个时刻的状态( 快照) ，不能很 好地反映、存储其过去和未来。随着数据库的广泛应用，人们从两个方面提出了 管理时态信息的要求： ( 1 ) 要求管理被处理事件的历史性信息，例如：与自然灾害( 地震、气象、水 文、洪涝等) 有关的历史资料，人事、财务、金融方面的历史资料，这些数据反 映了事物发展的本质规律 ( 2 ) 要求管理数据库系统中元事件的时态信息，例如：数据库被查删改的时 刻、时间区间，多用户系统中对镇定排队以及资源竞争协调的时标等这些数据 有助于提高数据库系统的可靠性和效率。 为了解决这些问题，时态数据库也就应运而生。 3 1 时态数据库技术的发展 关于时态数据库的起源与发展，国际时态数据库权威学者t a n s e l 等在1 9 9 3 年共同主编的“t e m p o r a ld a t a b a s e s ：t h e o r y ，d e s i g n ，a n di m p l e m e n t a t i o n ” 收集了此前时态数据库几乎所有的重要成果 2 8 。唐常杰对时态数据库技术前 2 0 年的发展做了系统回顾 2 9 3 0 。汤庸等在e 3 1 中将时态信息处理技术的起 源与发展分为三个时期： i 、开创期( 1 9 8 2 年以前) ： 加州大学洛杉矾分校b e n z v i 和纽约大学的c l i f f o r d 在1 9 8 2 年的博士论 文是时态数据库技术开创期的两个标志性成果。 1 7 中山大学硕士学位论文时态数据挖掘技术的研究与应用 2 、发展期( 1 9 8 3 1 9 9 3 年) ： 这个时期标志性成果是t a n s e l 等在1 9 9 3 年共同编辑出版的“t e m p o r a l d a t a b a s e s ：t h e o r y ，d e s i g n ，a n di m p l e m e n t a t i o n ”该书被称为“世界第一 本关于时态数据库专著”。该书对此前国际时态数据库技术的研究给出了全面的 总结。 3 、应用期( 1 9 9 3 年至今) ： 1 9 9 4 年后，时态模型没有新的突破，人们开始进入“思索”阶段，如何将 时态数据模型“标准化”和“产品化”是这个时期重要特征。 3 2 时态数据库的基本概念口2 1 时态数据在计算机系统中一般保存在数据库中，这种记录时态数据反映时态 信息的数据库就是时态数据库( t e m p o r a ld a t a b a s e ) 。另外，从对事务时间和有 效时间的支持的角度来说，通常将支持事务时间和有效时间的数据库称为时态数 据库。下面介绍有效时间、事务时间等时态数据库中的基本概念。 3 2 1 三种基本时间 ( 1 ) 有效时间( v a l i dt i m e ) ：它是指被管理对象的生命周期，也即一个事实 在现实世界中为真的时期。可替换的名字有现实世界时间( r e a l 一, o r l dt i m e ) ， 逻辑时间( 1 0 9 i c a lt i m e ) ，数据时间( d a t at i m e ) 。 ( 2 ) 事务时间( t r a n s a c t i o nt i m e ) ：是指数据库本身被查删改的时阅，也即 一个数据库事实被存放在某个数据库中的整个时间期。可替换它的名字有：注艇 时间( r e g i s t r a t i o nt i m e ) ，外在时间，物理时间( p h y s i c a lt i m e ) ，数据库时间 ( d a t a b a s eti m e ) 。 ( 3 ) 用户定义时间( u s e r d e f i n e dt i m e ) ：即用户根据某种需要定义的时间， 与有效时间和事务时间无关。 3 2 2 两个时问维 时态数据库里面对时间问题最为重视的即是事务时间和有效时间，这两种时 捕 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 间对时态属性的支持构成了时态数据库里面最为绚丽的环节。这里所提到的时间 维就是指有效时间维和事务时间维。传统的关系数据库有两维，其一是属性维， 其二是元组维，分别为横向维和纵向维，现在加上两个时间维，这样时态数据库 变成了四维结构。 3 2 3 几种时态元素 前面提到了两种时间维：有效时间维和事务时间维，这两种时间维在数据库 需要用时态元素来表示。时态元素( t e m p o r a le l e m e n t ) 可以是时间点、时间点 的集合、时间区间或时间区间的集合。 1 、时间点( t i m ep o i n t ) ：是时间轴上的固定点。例如：e p s o nc 4 0 打印机 在2 0 0 3 年5 月2 日销售了一台。这种类型是时态领域中最基本的类型，其它类 型可以通过时间点来实现或者在某种程度上通过时间点来模拟。除了时间点类型 之外，大多数的数据库管理系统并没有提供其它类型的时态数据类型。 2 、时间区间( p e r i o d ) ：是指一段时间，有固定的起止时间点。例如2 0 0 0 年7 月至2 0 0 3 年7 月就是一个时间区间的例子。在商业上广泛应用的d b b l s 和 s q l 9 2 标准中不支持这种据类型。但是我们可以通过他们支持的时间点来模拟这 种类型。方法是用一对时间点( t l ，t 2 ) 来表示，前者t 1 表明区间的开始，后者 t 2 表明区间的结束。 3 、时间跨度( t i m es p a n ) ：是指持续的一段时间，表示时间的长度。例如， “两年半”，“2 4 小时”。在数据库系统内，一般用一个整数表示时间跨度。时间 跨度也表示一段时间，但与时润区间不同的是，时间跨度没有时间起点，也没有 时阔终点。 3 3 时态数据库的分类口司 按表示时态信息的方式和能力对数据库进行分类，可以将数据库分成基本的 四个类型。它们是快照数据库( s n a p s h o td a t a b a s e ) ，回滚数据库( r o l l b a c k d a t a b a s e ) ，历史数据库( h i s t o r i c a ld a t a b a s e ) 和双时态数据库( b i t e m p o r a l d a t a b a s e ) 。 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 3 3 1 快照数据库 快照数据库以在特定的时刻的瞬间快照来建立模型，来考虑现实世界，尽管 现实世界是变化的，快照数据库只是反应了某一个瞬间的情况，但快照数据库确 实可以解决很多实际问题，它是我们用的时间最长的一种数据库技术，我们传统 的数据库都是这种数据库。 快照数据库由一些元组组成，每个元组就是一个静态的关系，但是此元组并 不反应其状态的变迁历史。数据库的状态变迁由事务实现，一旦事务提交，其状 态变迁就立即生效，原来的数据库状态也就完全被丢失和遗忘，相应的，现实世 界的状态也样被丢失和遗忘。快照数据库只能进行当前数据库状态的查询和更 改及删除工作，它不能够进行与时间相关的任何工作，不能进行含有时间因素的 推理，不能进行以往历史数据的查询；而且，它更改的历史数据全部丢失，等等。 所有这些都反映了快照数据库的天生弊病，这是由快照数据库的建库机理决定 的。 3 3 2 回滚数据库 回滚数据库支持事务时间，它按事务时间进行编址，它保存了所有状态演变 中过去的状态。这种数据库由回滚关系组成。 一个回滚关系是一个三维结构，可当作是一个按时问编址的瞬象的序列。这 个三维结构是这样的：x 轴是属性轴，y 轴是元组轴，z 轴是时间轴，表示事务 时间。当在z 轴上作垂直切割，每一个时间点都对应于一个二维的快照数据库， 当然我们所取的时间的点一定是数据库中的事务时间点，也就是在那一点有数据 库的建立、修改、和删除及数据库的定期重写( 里面可能没有数据及有效时间的 变更) 工作。 回滚数据库保持了数据变迁的历史，每个事务都产生一个新的静态关系附着 在时间轴的前面，即使是数据库毫无交迁。这样就会产生很多的冗余。 回滚数据库的不足之处是较为显然的：首先它记录的是数据库活动的历史， 而不是现实世界变化的历史，现实世界中元组的属性已经随着时间变化了，但是 2 0 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 因为数据库的事务时间没有改变，那么此时，元组的时变属性的改变在数据库中 根本没有得到体现出来。其次，过去元组的错误决不可以更正，而只能查看，当 我们发现元组有错误的时候，如果此事务已经提交的话，我们就无能为力了，我 们所能做的工作只能是等待下次系统的事务时间进行新的改动，但是，改动的只 是提交前的数据库，以前的状态绝不能再改变。最后，回滚数据库的冗余太多。 在前一个事务时间内提交的数据，即使在下一个事务时间没有数据的改变或者改 变甚小也是需要进行所有的数据的重新输入及储存，这种冗余是较大的，特别是 在时变较小的情况下。 3 3 3 历史数据库 历史数据库与回滚数据库类似，不过它支持有效时间，不支持回滚时间。 历史数据库记录的是数据库中的一个个元组的有效时问段的状态，丽不是象 回滚数据库记录的一个个“历史的”快照状态。历史数据库也是一个三维结构， 只不过用有效时间维代替事务时间维。 历史数据库建模现实世界在有效时间点的事件或现实世界状态变化的经历。 历史数据库允许任意修改( 包括以前的状态) ，因此，以前元组的错误可以修改， 而回滚数据库则不允许这样做，但是，历史数据库修改后以前的状态不再保留。 历史数据库和前两种数据库的比较：历史数据库可以象快照数据库一样任意 修改以前的状态，历史数据库也象快照数据库一样使得被修改的状态不再保留。 这使得历史数据库不可以象回滚数据库一样进行以前的某一个状态的查询，历史 数据库所查询的状态只是当前的状态。历史数据库还有一项是最为独特的，历史 数据库能够进行有关未来问题的推理，这是快照数据库和回滚数据库所决不可以 的。历史数据库记录的是现实世界的真实变化情况，它是以元组的有效时间来表 达的，对它的操作需要有更为高级的语言的支持，而不是象快照数据库和回滚数 据库的较为简单的语言。 历史数据库从某种程度上应该是可以称为时态数据库的，而前两种数据库系 统在时态上面的支持简直是太有限了，快照数据库就不用说了，就回滚数据库， 也难以称得上是纯粹的时态数据库，充其量，回滚数据库只能是用快照的办法进 行时态问题的处理，只是稍加了一些形式上的改进而已。 2 1 中山大学硕士学位论文 时志数据挖掘技术的研究与应用 回滚数据库和历史数据库的结合，对两种时态属性的支持将产生真正的时态 数据库，它应该是支持事务时问和有效时间的，这就是我们下面要说的数据库一 一双时态数据库。 3 3 4 双时态数据库 回滚数据库和历史数据库各具优点，通过设计种数据库，使它即支持事务 时间又支持有效时间，这就是双时态数据库。双时态数据库由时态关系组成。一 个时态关系是一个四维结构。其中两维是属性和元组，另外两维是事务时间和有 效时间，一个时态关系可以看成是一个历史关系的序列。对时态关系的一个回滚 操作则是选取了一个特定的历史关系，可对该历史关系进行查询。而每一个事务 则引起一个新的历史关系的建立。 双时态数据库集成了前三种类型数据库的功能特性，储存了数据库和现实世 界两者发展的历史。时态关系的一种实现方法就是组合回滚数据库和历史数据库 成为新的数据库。 下面，我们利用图3 1 进行说明。 属性 图3 一l 双肘态数据库的四维结构 只要在事务维中任意截取事务时间点就可以找到相应的元组的有效时间段， 不同的事务时间点对应不同的有效时间段( 一般是这样的，当然也有有效时间段 2 2 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 是一样的不同事务时间点，如事务时间点t 。和t ：的有效时间段是一样的) 。我 们可以看出，在事务时间轴上，取不同的时间点，就产生不同的历史数据库，我 们可以对上图中的对应于四个事务时间点t 。，t 2 ，t 3 ，l 的历史数据库进行查询 操作；当然上图中所示的只是一个元组的四个历史数据库中的有效时间片断组 合，对于其他元组的情况可以类似的进行推理，而后，这些元组组合到一起即是 形成了四个不同的历史数据库。所以，这四个历史数据库也可以当成是快照历史 数据库，说是快照，是因为这四个数据库分别是四个事务时间的快照；说是历史 数据库，是因为，每个数据库里面是历史数据库属性的，在里面记载的是现实元 组的真实变化的时间，而非数据库状态变化的时间，我们可以在这四个数据库里 面进行增加、修改、删除及查询的工作。 回滚数据库对以前的元组是不可以进行改动的，只能对它进行以后事务时间 时的属性改动；但是，双时态数据库就不是这样了，我们可以在当前时间对以前 的事务时间t l 时的该元组属性或有效时间进行改动，例如我们可以在t 。时间对 t 。时的历史快照数据库进行修改，比如，我们可以改变有效时间，t ，t ：和t 。 为t 、和t 。 这就使得在t - 时的快照历史数据库中的元组属性( 时间属性) 得到了改变。 而这在以前的回滚数据库中这是根本不可能的。 双时态数据库综合了回滚数据库和历史数据库的优良特性，它即保存了数据 库变迁的历史，又保存了现实世界的真实的数据属性。这种数据库，才是真正的 对数据时态属性支持的数据库，以前的回滚数据库很难称得上是纯粹的时态数据 库。当然，双时态数据库是以牺牲大容量的储存空间为代价的。 3 4t i m e d b 介绍嘲锄 t i m e d b 是a n d r e a ss t e i n e r 开发的一个双时态关系数据库管理系统 ( b i t e m p o r a lr e l a t i o n a ld b l l s ) ，支持时态查询语言a t s q l 2 规范。a t s q l 2 基 本模型源于rs n o d g r a s s 的t s q l 2 语言，结合丹麦a a l b o r g 大学的m i c h a e l b o e h l e n 提出的c h r o n o l o g 模型和瑞士a n d r e a ss t e i n e r 的b it e m d o r a l c h r o n o s q l 模型【5 0 。通过使用t i m e d b 能够存储和处理不仅是单状态的数据库， 还有多状态的数据库。根据在时态数据库中的研究表明，在商业数据库中我们总 中山大学硕士学位论文时态数据挖掘技术的研究与应用 可以通过一种方法来存储数据合法的时间间隔，查询和更新这样的数据并使它们 保持数据的致性是一件非常繁琐的事情，如果你使用时态d b m s 就能消除这些 缺陷。t i m e d b 本身不是一个时态的d b m s ，而是一个商业d b m s 的前端构件，通过 将a t s q l 2 语句转换成标准的s q l 语句，t i m e d b 能在非时态的d b m s 上支持时态 功能。这种方式的好处是当新的时态数据加入时，原d b m s 中现存的数据库及其 上的应用程序还可以照常使用。新的时态应用程序通过t i m e d b 来接入数据库， 如图3 2 描述； 图3 - 2t i m e d b 的设计思想 中山大学硕士学位论文 时态数据挖掘技术的研究与应用 4 1 时态数据 第四章对时态数据的挖掘 在现实世界数据库中存在多种类型的时态数据，这些类型还将因不同的具体 应用