（计算机软件与理论专业论文）关于时态数据关联规则挖掘的研究.pdf

山东大学硕士学位论文 摘要 数据挖掘技术自2 0 世纪9 0 年代初期开始崛起，并迅速的成为计算机理论及 应用界研究的热点。如今数据挖掘是一个多学科交叉研究领域，它融合了数据库 技术、人工智能、机器学习、统计学、信息检索、高性能计算以及可视化等最新 技术的研究成果，成功的打破了“数据丰富，知识贫乏”的局面。 在数据挖掘技术蓬勃发展的过程中，人们逐渐意识到时态数据挖掘研究的必 要性及其重要意义。因为时间是客观世界的客观属性，是数据的固有属性，在数 据挖掘的过程中忽略数据的时态语义已然暴露出很多不足。于是诸如时态数据的 模式、趋势、约束、因果关系等时态知识的挖掘得到了越来越多的研究，值得提 出的是，计算机学术界对于挖掘时态关联规则给予了尤其多的关注。 本文提出的是时态数据库中离散属性的带周期规律的关联规则发现方法。关 于时态数据周期性关联规则挖掘的研究也有不少，其中包括连续属性的周期性关 联规则提取，定制周期内时态关联规则提取等等。在这些研究成果的基础上，本 文提出的方法能够计算得到时态数据库中离散属性的周期，进而通过执行改造了 的a p r i o r i 算法挖掘周期性时态关联规则。 本文所做的主要工作概括如下： 1 在对时态数据库中的有效时间属性进行划分和标记的基础上，提出了时 态数据库中离散属性的周期计算方法，并详细描述了算法的执行步骤。 2 提出新的时间区间标记方法，通过划分和标记时态数据库的有效时间属 性，用标记集合代替时间区间，达到有效时间区间合理离散化的目的。 3 提出改进了的a 曲o r i 算法，在计算频繁项集的过程中，相匹配的项集 根据其所携带的时间区间标记的不同来分别计算支持度，从而得到带时态信息的 频繁项集。 4 计算得到带时态信息的关联规则，结合离散属性的周期，合理解释关联 规则的周期规律。 5 分析本文提出的改进了的a p r i 嘶算法在性能上有所提升的主要原因。 本文通过对时态数据库的有效时间属性进行两次划分和标记，有效的实现了 离散属性的周期计算以及时间区间的离散化，为进一步执行a 研o r i 算法奠定了 基础。另外，本文提出的改进了的a p r i o r i 算法使得计算频繁项集的迭代过程迅 山东大学硕士学位论文 速收敛，减少了扫描数据库的次数，提高了算法的执行效率。 关键词：周期性时态关联规则；离散属性；划分标记时间区间；a p r i o r i 算 法；时态数据库 i l 山东大学硕士学位论文 a b s t r a c t t h et e c h n o l o 鲥o fd a t ar n i n i i l gb e g a i lt os p 血gu pi l l 血ee a d y1 9 9 0 s ，a n dq u i c k l y 伊e wu pt ob et h ef o c u so fr e s e a r c hi n 廿l ef i e l do fc o m p u t e rt l l e 0 巧锄da p p l i c 撕0 n n o wd a t 2 l1 1 1 i n i n gi sam u l 矗m s c i p l i n a 巧r e s e a r c ha r e a 王i yu s i l l gt l l es u c c e s s 伽 p r o d u c 缸0 no fd a t a b a s et e c l l i l o l o 舒，a r t i f i c i a li n t e l l i g e n c e ，m 础n e1 e 锄i n g ，s t 撕s t i c s ， i i 面肌a l i o nr e t r i e v a l ，h i 曲一p e 渤珊a n c ec o 婶u t i n g 锄dv i s u a l i z 撕o n ，m ed a t al i l i n i n g t e c h n o l o 舒h 嬲s u c c e e d e di i lb r e a k i n gm es i t u a t i o no f i t r i c hd a t ab u tp 0 0 rk n o w l e d g e ” w i 吐lm ed e v e l o p m e n to fd a t a1 1 1 i n i n gt e c h n o l o g y ，p e o p l eb e 垂nt 0r e a l i z e 也e n e c e s s 毋a i l ds i 笋i f i c a i l c eo ft e l n p o r a ld a t ai n i n i n g t i m ei s 趾0 b je c t i v e 砌b u t eo f 血eo b j e c t i v ew o r l d 锄di ti sn l ei i l l l e r e n t 撕b m eo ft l l ed a t a i ti si n 印p r o p r i a t et l l a t w eo v e d o o k 廿l et e m p o r a ls e m a i l h c so fd a t ai nt h ed a t am i l l i n gp r o c e s s s op e o p l ep a y m o r ea i l dm o r ea t t e n 石o nt 0l i l i 血n gt e m p o r a lk n o w l e d g es u c h 硒t e m p o r a lm o d e l s ， 仃e n d s ，c o n s 仃a i n t s ，c a 吣a lr e l 撕o n s h i p sa n ds oo n e s p e c i a l l y ，n l ec o m p u t e ra c a d e r l l i a p a y st l l ei l l o s ta t t e n 矗o nt 0m 证i 1 1 9t e m p o r a la s s o c i a d o nr u l e s t h i sp a p e rp r e s e n t sam e t h o df o rl i l i n i i l gt h ep e r i o d i ct e r r l p o r a l 勰s o c i a ：t i o nr u l e so f d i s c r e t ea 嘣b u t e s 蠡o mt l l et e n l p o r a ld a t a b a s e t h e r ea r em a r l ys t u d i e so nm ep e r i o d i c 钯i n p o r a l 舔s o c i 撕o nm l e ss u c h 鹊1 1 1 i 1 1 i n gp e r i o d i ct e m p o r a l 蕊s o c i 撕o n 叫e so f c o n 矗n u o 哪a t 缸曲u t e s ，m i n i n gt e m p o r a l 嬲s o c i a 矗o nn l l e si i l 丘x e dc y d e sa n ds oo n 0 | i l 血eb 嬲i so ft 量l er e s u l t so ft l l e s es t u d i e s ，n l i sp 印e rp r o p o s e sam e t h o df o r c o m p 嘶n gt 1 1 ec y d eo ft l l ed i s c r e t ea t t r i b u t e sf r o mt l l et e n l p o f a ld a 讪笛e ，趾dt h 铋 i i l i n i n gm ep 缸o d i ct e m p o r a l 觞s o c i 撕o n 硼e sb yi n 】p l e m e n t i n gt 量l ea d a p t i v ea p r i o r i 甜g o r i 吐l m t h em a i nw o r l ( sa n da 出e v e m e n t so ft l l i sa l t i c l ea r e 1 o i lt 1 1 eb 撕s0 fd i 、r i d i n g 锄dm 枷n gt l l ev a l i dt i m ei n t e n 试s0 ft h et e r 呐r a l d a t a b a s e ，t h i sp 印e rp r e s e n t sam 甜1 0 df o rc o m p 埘n gt l l e 哆c l eo f 血ed i s c r e t e 枷b u t e s 1 1 l ed e t a i l e ds t e p so ft h em e n l o da r ed e s c 曲e di nm ep a p e r 2 t h i sp 印e rp r o p o s 懿an e wm e l o df o rm a r k i n gt h et i m ei n 钯a l s w - eu s eas i g n s e tt or 印1 a c en l et i m ei l l t e r v a lb yd i v i i i i n ga n dm a f k i l l gm ev “d 五m e 甜r i b u 钯o ft l l e t e m p o r a ld a t a b a s e t h a ti sh o w t or e a l i z em ed i s c r e 6 z 撕o no ft h ev a l i d6 m ei n t e a l s i i i 山东大学硕士学位论文 3 t h ea d a p t i v ea p r i o r ia l g o r i 也mi sp r e s e n t e di n “sp a p e r w h e nc o m p u t i n gt h e f r e q u e n ti t e m s e t s ，t 量l es i l i t e di t e m s e t sa r er e g a r d e da sd i h e r e n ti t e m s e t si ft h e yb r i n g d i a e r e n ts i g ns e t s s ot h es u p p o nd e g r e e so fs u c hi t e m s e t sa r ec a j c u l a t e dr e s p e c d v e l y t h e n 、v ec a ng e tm ef r e q u e n tt e m p o r a li t e m s e t s 4 a r e rw eg e ta l lm et e n l p o r a la s s o c i 撕o nr u l e s ，o nt t l eb a s i so f 吐l ec y c l eo f 吐l e d i s c r e t ea 竹r i b u t et h a th a sb e e nc a l c m a t e d ，、v e 西v er e a s o n a b l ee ) c p l 锄a t i o no fm em l e s 5 a n a l y s e st l l em a i nr e 弱o n sf o rt h ei m p r o v e m e n to fn l ep e r f o m a n c eo ft l l e a d a p t i v ea p t i o r ia l g o r i m mp r e s 锄t e di no u rp a p e r i nt h i sp 印e r ，、ec a l c u l a t e 也ec y c l eo ft h ed i s c r e t ea l t f i b u t e 觚dr e a l i z et l l e d i s c r 舐z 撕0 no ft h ev a l i dt i m em e r v a l sb yd i v i d i n ga n dm a d ( i n gt i 坞v a l i dt i r a t t f i b u t eo ft h et e m p o r a ld a t a b 嬲et w ot i m e s a n d 廿l e nw ec a l li m p l e m e n t l ea p r i o r i a l g o r i 缸1 m s o m e m i n gi sw o r t h yt 0b ep r e s e n t e di st h a tt l l ea u d 卸缸v ea p r i o r ia l g o r i t l l m p r o p o s e di nm i sp a p e ri sm o r ee m c i e n tb ys i g n i f i c 锄n yi m p r o v i n gm es p e e do ft l l e i t e r a l i o nc o n s t r i n g e n c ya n dr e d u c i n gn l e 缸m e so fs c a i l n i n g l ed 鼬嬲ew h c o m p u _ t i n gf r e q u e n ti t e m s e t s k e y w o r d s ：p e l i o d i ct e m p o r 址觞s o c i a t i o n1 1 l l e ；d i s c 弛t ea t t l i b u t e ；d i v i d ea n d m a r kt h et i m ei n t e r v a l s ；a p o i ia l g o r i t h m ；t e m p o r a id a t a b 翘e 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者躲氍导师虢雄 山东大学硕士学位论文 第一章绪论 1 1 本文的研究意义和背景 1 1 1 数据挖掘技术产生的背景 近年来，以数据库和信息技术的发展为技术保障，以网络技术的迅速普及为 发展通道，以计算机硬件、数据收集设备和存储介质的大量供应为物质基础，人 们的数据收集能力得到了大幅的提高，社会各行业都存储了大量的有关生产、管 理和科研的各种信息，全球范围内数据存储量正急剧增加。然而与此形成鲜明对 比的是，人们对大规模数据的理解能力并没有得到有效的提高，仅仅依靠传统的 数据检索和统计分析等方法已远远不能满足需要，以致出现了“数据丰富，知识 贫乏 的局面。为从海量的数据存储中抽取模式、找出数据变化的规律和数据之 间的关系，充分发掘数据的潜力，以指导决策和科学发现等各项工作，人们对数 据分析并使之转化为易于理解的知识的需求越来越迫切。 数据挖掘( d a t am i i l i n g ) 技术迎合了人们的需求，它是2 0 世纪9 0 年代初期新 崛起的一个活跃的研究方向。数据挖掘是一个多学科交叉研究领域，它融合了数 据库( d a t a b a s e ) 技术、人工智能( 觚f i c i a li n t e l l i g e n c e ) 、机器学习( m a c h i n e l e 锄i n g ) 、统计学( s t 撕s d c s ) 、知识工程( k n o w l e 电ee n g i i l e e 曲g ) 、面向对象方 法( o b j e c t o e n t e dm e t h o d ) 、信息检索( h l f o 期撕0 nr e t r i e v e ) 、高性能计算 ( h i 曲p e 哟彻a i l c ec o m p 嘣i o n ) 以及可视化( s u a l i z a l i o n ) 等最新技术的研究成 果。经过十多年的研究，产生了许多新概念和方法。特别是近几年来，一些基本 概念和方法趋于清晰，它的研究正向更深入的方向发展。数据挖掘被称为未来信 息处理的骨干技术之一，主要在于它以一种全新的概念改变着人们利用数据的方 式。二十世纪，数据库技术取得了丰硕的成果，并得到了广泛的应用。但是数据 库技术作为一种基本的信息存储和管理方式，无法在数据中发现存在的关系和规 则，无法根据现有的数据预测未来的发展趋势，无法找到数据之间隐藏的客观规 律。随着数据量的日益增长，由于缺乏数据挖掘工具，导致了“数据爆炸但知识 贫乏 的现象的产生。因此在数据库技术飞速发展的同时，一个更加实用的研究 数据挖掘技术应运而生。 山东大学硕士学位论文 需求总是促进发展的原动力，随着数据库技术，特别是数据仓库技术的发展 和应用，人们不再满足对数据库进行查询、检索等简单的操作，而是希望从中发 现知识，以辅助高层人员的决策，即数据挖掘。数据挖掘的任务是从大型数据库 或数据仓库中提取人们感兴趣的知识，这些知识是非平凡的、隐含的、事先未知 的、潜在有用的信息，通常是以概念、规则、规律、约束、可视化等形式来表示。 数据挖掘技术为自动和智能地把海量的数据转化为有用的信息知识提供了有力 的手段，给数据和知识之间的鸿沟架设了方便之桥。 1 1 2 时态数据挖掘技术的意义 时间是自然界无所不在的客观属性，所有信息都具有相应的时态属性。随着 数据库与信息技术的深入和发展，信息系统面临许多新的应用和新的需求，对时 态信息处理的需求越来越迫切。时态信息处理已成为许多新一代数据库与信息系 统的关键技术，特别是在电子政务、电子商务、数据仓库、数据挖掘、决策支持 系统等信息系统中扮演着日益重要的角色。其中时态数据挖掘技术起步较晚，研 究者们任重而道远。 在数据仓库中通常存放着大量的时态数据，例如，超市交易记录中的交易时 间，病历中的检查和诊断时间等。时态数据反映了事务发生发展的过程，有助于 揭示事物发展的本质规律。在数据挖掘中结合时态数据的特点可以挖掘出更有用 的信息。所以在数据挖掘中必须要考虑时间的问题，选取有效时间进行挖掘至关 重要。时态在数据挖掘应用中主要体现在规则的有效性问题上，以及时序数据挖 掘，例如证券的走势等。本文的研究聚焦在时态数据关联规则的高效提取上。 1 2 国内外相关研究综述 时态信息的处理技术实际上一直伴随着数据库技术的发展而产生和发展。时 态信息处理技术的研究和发展大致可分为三个阶段，开创与形成阶段、理论与模 型探索阶段以及应用与发展阶段【2 引。 由于时态特性是信息的客观存在，早在7 0 年代就有人关注到时态信息的应 用，在时态信息处理技术发展的开创与形成阶段，国内外许多学者、专家进行了 大量的关于时态信息的基础性研究工作。1 9 8 2 年，时态数据库正式形成。1 9 8 2 年以后，时态数据库的研究开始走向繁荣时期，时态信息处理技术的发展进入理 2 山东大学硕士学位论文 论与模型探索阶段，在此后的1 0 年中，计算机学术界对时态数据库给予了极大 的关注，发表了数以千计的论文，学术界提出了数以百计的时态数据库模型和时 态信息处理方法。此阶段，国际上一些重要大学和研究机构涌现出一大批研究学 者，形成了一批专门的时态数据库研究集体。他们做了大量的时态数据库理论研 究和时态数据模型探讨工作，结果是模型多，但是原型系统少，实际应用少。经 过2 0 世纪8 0 年代末的“百花齐放，1 9 9 4 年后人们开始进行深入的思考，如何 将时态数据模型“标准化和“产品化 是时态信息应用与发展阶段的重要目 标，而广泛应用和实践则是这个阶段的重要特征。在“标准化”方面，代表性成 果是rt s n o f 酊硒s 等人在1 9 9 4 年提出的双时态数据模型t s q l 2 ，t s q l 2 是对 s q l 9 2 语言标准的时态进行扩充，并提出将t s q l 2 的相关结构集成到s q l 3 标 准。在“产品化方面的代表性成果是瑞士t i m e c o n s u h 公司于1 9 9 8 年推出的 t i m e d b 2 o ，目前已发布b e t a 4 。t i r n e d b 是一个双时态关系数据库系统，支持平 台j a v a 、j d b c 。它基于s q l 查询语言，支持时态查询语言衄s q l 2 ( a p p l i e d t s q l 2 ) 。时态信息应用与发展阶段的另一个重要特征是“时态信息的应用”。 2 0 世纪8 0 年代中后期，由于计算机相关技术的迅速发展，特别是网络与多媒体 等技术的发展，使得应用领域的许多新需求能够实现。时态信息的应用就是一个 主要方面，其主要应用领域包括：地理信息系统、农业信息系统、电信信息系统、 电子政务、电子商务、智能决策支持系统以及数据仓库与数据挖掘等。但是由于 时态数据库理论与模型还不够成熟，时态信息产品还没有形成，所以这时期的应 用大多都是只借助时态数据库的一些概念，时态信息的管理与操作的实现还是采 用传统的数据库技术与相关应用领域的技术【2 引。 在国内，时态数据库的研究和应用也越来越受到关注，关于时态信息处理技 术的文献越来越多，相比2 0 世纪8 0 年代，2 0 世纪9 0 年代以1 0 多倍的速度增 长【2 引。 特别的，关于时态数据挖掘技术的研究最近十几年有了很大的进步。时态关 联规则的研究主要有下面几个方面： ( 1 ) 关联规则成立的时间 传统的关联规则挖掘很少考虑关联规则的时间适用性，往往是在整个时间域 上进行关联规则提取，然而每个关联规则都有其成立的某一个或某些时间区域， 如果放弃对时间的考虑，容易丢失一些有用的信息。如在购物篮分析中，假设用 山东大学硕士学位论文 户规定的最小支持度是a ，有这样的规则“牛奶j 面包 成立。假设为了提高规 则的重要性，将最小支持度提高到f ，这种情况下我们可能就得不到规则“牛奶j 面包了。因为在整个事务数据库中，( 牛奶，面包) 的支持度不够高，但是通过 分析可以发现，在早上7 ：0 0 9 ：0 0 这段时间内，这条规则的支持度是很高的。所 以如果在关联规则挖掘过程中，我们把购买时间考虑进去，就可以在保证规则的 重要性的同时，不遗漏掉任何有价值的规则。在文献 1 中提出了具有时态约束 的关联规则，其发现算法是在a p r i o r i 算法 2 上的扩展，当遍历数据库对候选项 集进行计数时，两个项目序列不仅要匹配，而且两者的相关有效时间也需要归并， 提出了时间区间的延展概念及方法、时间区间的归并概念及技术。 已有的这些研究主要是对数据库的每个元组考虑其发生时间，强调的是关联 规则成立的时间属性，以表明所发现的知识何时是有效的。在未考虑时间属性时， 所得的规则假定是永远有效的。在考虑了时间属性后，所得到的规则将可以更好 地描述客观现实情况，因而也会更有价值。 ( 2 ) 序列关联规则 类似于序列模式的研究，只关心事件发生的顺序，对于具体的发生时间并不 讨论。规则中的前件和后件分步产生。可以运用已有的序列模式研究中的方法 【6 ，7 ，1 4 】 o ( 3 ) 时态关联规则模型的建立 由于时态关联规则的挖掘是在带有时间属性的数据上进行的，因而有关时态 数据的表示也需进行研究，以便于时态关联规则模型的建立。这方面的研究不少， 但是没有统一的标准可参考，基本上都根据研究的需要定制相应的关联规则模 型，各具特点。文献 8 中给出了一个基于定制时间的关联规则模型，研究了在 定制约束时间区间内，正、负关联规则的挖掘问题。文中讨论了同时考虑正、负 关联规则时出现的矛盾规则问题以及用相关性解决这一问题的方法，提出了挖掘 正负时态关联规则的算法。但是该算法研究的时态信息单一，现实世界中有多种 多样的时态信息形式，没有给出较全面的讨论。还有一些文献，比如 9 ，1 0 ，1 1 ， 1 2 ，对有关时间表达模型的概念及性质从数学理论上进行了定义和证明，如时 态模式、时间表达式、时间量子、时间间隔等的定义及性质。仅建立了简单时态 事件模型，对部分特殊情况下的时态关联规则的挖掘思想进行了简介，但未进行 深入的算法研究。对于复杂的时态关联规则以及通用的时态关联规则模型也没有 4 山东大学硕士学位论文 进行研究。 ( 4 ) 关联规则的周期性 主要是研究了有关周期时间区域的划分。我们把长度为1 的周期划分为等间 隔的时间区域，分别计算每个时间区域中项目子集的支持度以便于计算周期关联 规则叫。这样的实现方法很简单，周期时间段是人为确定的，但在某些领域不能 充分反映数据的内在规律。如以小时为粒度来划分每天的销售事务，则像“每天 早上7 ：0 0 9 ：0 0 时间范围内买牛奶的顾客会买面包这样的规则就不能够被发现。 如果我们能够根据业务数据的实际状态，通过计算得到周期时间，那就能较好地 解决时间粒度的确定问题。不过目前这种周期挖掘技术只能在连续属性的基础上 展开。另外在某些领域，周期的获取适合由聚类来实现。可以根据事务发生的 频度利用聚类分析来实现对时间段的划分晒3 。这样，时间段的长度根据事务发生 的集中度自动求出，而不是人为主观规定，这与时态关联规则的实际意义相一致。 也可依各项目的频度来聚类，根据聚类结果把每个项目分成几个动态的时间区 域。 如上所述，目前对于带周期规律的时态关联规则的研究已经取得了一些进 展，但是尚存有不足，比如所研究的时间类型较为单一，时间周期的确定方法不 甚妥当，所研究的属性的类型不够全面等等，还有很多问题存在，还有很多方面 没有涉及。致力于这方面的研究的学者们，任重而道远。 1 3 本文的主要研究内容和结构 本论文主要研究的是时态关联规则的提取，重点讨论的是离散属性上带周期 规律的时态关联规则的挖掘，论文的内容和结构如下： 第一章绪论，主要介绍了本论文的研究意义和背景以及国内外相关研究，包 括数据挖掘、时态数据挖掘以及时态关联规则的相关研究介绍。 第二章数据挖掘技术综述，介绍了数据库知识发现的概念及过程，重点介绍 了数据挖掘的任务、相关实现技术、相关应用及发展趋势。 第三章时态数据库概述，这部分主要内容包括时态数据库的背景、时态数据 库相关的基本概念、主流的时态数据模型以及时态数据挖掘技术。 第四章普通关联规则挖掘技术和算法，讨论了经典的关联规则挖掘算法，主 要是基于关系数据库上的关联规则提取。 山东大学硕士学位论文 第五章时态数据关联规则挖掘是本文的主体，重点讨论了离散属性上的带周 期规律的时态关联规则提取，并给出了实例演算以及算法性能提升的分析证明。 另外为了顺利的引出对离散属性上周期规律挖掘的讨论，在本章开始的两节首先 介绍了相关的研究和技术，包括时间区间的延展与归并技术以及时态数据库中连 续属性的周期规律挖掘技术。 在结束语中，对本文所做的工作进行了总结和展望。 6 山东大学硕士学位论文 第二章数据挖掘技术综述 2 1 数据库知识发现与数据挖掘 数据库知识发现( k d d ) 是目前非常活跃的研究领域，其研究涉及数据库和 人工智能等多门学科。实际上，数据库管理系统是存储数据的主要手段，人工智 能，特别是机器学习是用来分析数据，挖掘数据背后的知识的主要手段，而数据 库与人工智能的结合就是数据库知识发现。可见数据库知识发现是一门交叉性学 科，融合了机器学习、数据库、模式识别、统计学等各个学科的研究成果。“数 据库知识发现”一词第一次出现是在1 9 8 9 年8 月在美国底特律召开的第1 1 届国 际人工智能联合会议的专题讨论会上。数据库知识发现比较公认的一个定义是， 数据库知识发现是非平凡的处理过程，它是从数据集中识别有效新颖的、潜在有 用的以及最终可理解的模式。数据库知识发现不仅被许多研究人员看作是数据库 系统和机器学习方面一个重要的研究课题，而且被许多工商界人士看作是一个能 带来巨大回报的重要工具。由于数据库知识发现是一个新兴的边缘学科，多学科 的相互交融与相互促进，使得数据库知识发现这一学科得到了蓬勃的发展，并且 很快有了许多成功的应用。众多的应用领域包括科学试验研究、零售行业、金融 分析领域、银行、制造业以及电信行业等。 目前虽然数据库知识发现技术得到了蓬勃发展，但现在仍然还处于初期阶 段，所以很多地方“数据库知识发现”和“数据挖掘”常被混用。相对来讲，数 据挖掘主要流行于统计、数据分析、数据库和管理信息系统领域；而数据库知识 发现则主要流行于人工智能和机器学习领域。因此较为普遍的观点认为：数据挖 掘是数据库知识发现中专门负责发现知识的核心环节；而数据库知识发现是一个 交互式、循环反复的整体过程，除了包括数据挖掘外，还包括数据的预处理和对 所发现的结果进行解释评估等诸多环节【2 0 1 。 2 2 数据库知识发现过程 数据库知识发现( k d d ) 可以分为3 个阶段：数据准备、数据挖掘、挖掘结 果的解释与评估。具体流程如下图2 1 所示2 0 】： 7 山东大学硕士学位论文 圈圈回 图2 1 数据库知识发现的过程 数据准备阶段的工作包括4 个方面，数据净化、数据集成、数据的应用变换 和数据精简。数据净化是清除数据源中不正确、不完整等不合数据挖掘质量要求 的数据。进行数据净化可以提高数据的质量，从而得到更正确的数据挖掘结果。 数据集成是在数据挖掘所应用的数据来自多个数据源的情况下，将数据进行统一 的存储，并需要消除其中的不一致性。数据的应用变换就是为了使数据适用于计 算的需要而进行的一种数据转换。数据精简是采用一定的方法对数据的数量进行 缩减，或从初始特征中找出真正有用的特征来消减数据的维数，从而提高数据挖 掘算法的效率与质量【2 0 】。 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分类、聚 类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样 的挖掘算法。通常不同数据的不同特点以及用户对数据挖掘的不同要求，会决定 在数据挖掘阶段采用什么样的算法对当前的应用最合适。 数据挖掘阶段发现出来的模式，必须经过用户或者机器的评估之后，剔除冗 余和无关的模式之后得到有效的可用的模式。同时，因为数据库知识发现最终是 面向用户的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂 的表示形式。 2 3 数据挖掘的任务 数据挖掘作为数据库知识发现的核心环节，有如下几种知识发现任务：分类 知识发现、数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依 赖模型发现、异常发现和趋势预测等。下面分别介绍这几种挖掘任务以及所用到 8 山东大学硕士学位论文 的相关技术。 2 3 1 分类知识发现 分类知识发现是数据挖掘中最常见的，目的在于根据样本数据寻求相应的分 类规则，然后根据该规则来确定某一非样本数据对象是否属于某一特定的组或 类。机器学习、专家系统、统计学和神经网络等领域的研究人员已经提出了许多 具体的分类预测方法。下面对分类流程作个简要描述： 训练：训练集 特征选取 训练 分类器 分类：新样本 特征选取 分类 判决 用于实现“训练功能的算法有：决策树( d e c i s i o nt r e e ) 、贝叶斯分类算法 ( b 巧e s i 肌c 1 邪s i 丘c 撕0 n ) 、后向传播算法( b a c kp r o p a g 撕o n ) ，k _ 最近邻近分类算 法( k n e a r e s tn e i 曲b o rc l 嬲s i f i e r s ) 、基于案例的推理( c 嬲e - b 嬲e dr e a s o n i n g ) 、遗 传算法( g e n 酣ca 1 9 0 r i t l l n l s ) 、粗糙集算法( r 0 u 曲s e t 灿g o r i t l l l n s ) 、模糊集算法 ( f u z 巧s e ta p p r o a c h e s ) 、神经网络算法( n e u r a ln e t w o r k s ) 等。 分类技术在很多领域都有应用，例如可以通过客户分类构造一个分类模型来 对银行贷款进行风险评估；当前的市场营销中很重要的一个特点是强调客户细 分。客户类别分析的功能也在于此，采用数据挖掘中的分类技术，可以将客户分 成不同的类别，比如呼叫中心设计时可以分为：呼叫频繁的客户、偶然大量呼叫 的客户、稳定呼叫的客户、其他，帮助呼叫中心寻找出这些不同种类客户之间的 特征，这样的分类模型可以让用户了解不同行为类别客户的分布特征。其他分类 应用包括文献检索和搜索引擎中的自动文本分类技术；安全领域中的基于分类技 术的入侵检测等等。 2 3 2 数据聚类 数据聚类是用于发现在数据库中未知的数据类。这种数据类划分的依据是 “物以类聚，即考察个体或数据对象间的相似性，满足相似性条件的个体或数 据对象划分在一组内，不满足相似性条件的个体或者数据对象划分在不同的组 【2 0 1 。通过聚类过程形成的每一个组称为一个类。在数据挖掘之前，对象类划分的 数量与类型均是未知的，因此在数据挖掘后一般需要对数据挖掘结果进行合理的 分析与解释，属于种无指导的学习方法。主要的聚类算法可以划分为如下几类： 9 山东大学硕士学位论文 分割的方法( p a n i t i o l l i n gm 甜l o d ) 、层次的方法( h i e r a r c l l i c a lm e t l l o d ) 、基于密度 的方法( d e n s 埘- b a s e dm e m o d ) 、基于网格的方法( g r i d - b a s e dm e m o d ) 、基于模型 的方法( m o d e l _ b a s e dm e t h o d ) 。聚类是现实世界中普遍存在的现象，在模式识别、 数据分析、图像处理、计算机视觉及模糊控制等诸多方面都有广泛的应用。 2 3 3 关联分析 关联分析( a s s o c i a t i o na 1 1 a l y s i s ) 用于发现关联规则，关联知识( 嬲s o c i 撕o n ) 反 映一个事件和其他事件之间的依赖或关联。例如“在购买个人电脑的顾客中， 9 0 也购买了打印机。 就是一条关联规则，或者说一种关联模式。关联分析的 目的就是找出数据库中隐藏的关联信息。它最早主要用于零售业交易数据分析， 以实现物品更合理的摆放，最终提高销售量。因此有时候该方法也直接称为“货 篮分析 。关联可分为简单关联、时序关联、因果关联、数量关联等。因为本文 主要研究时态数据库中关联规则的提取，因此关于关联分析的相关研究会在后面 的章节中进行更详细的说明。 2 3 4 数据总结 数据总结是将数据库中的大量相关数据从较低概念层次抽象到较高概念层 次的过程。计数、求和、求平均值、求最大值和最小值等计算都是数据总结的具 体化。由于数据库中的数据所包含的信息往往是最原始、最基本的信息，而有时 人们需要从较高的层次上浏览数据，这就要求从不同的层次上对数据进行总结以 满足需要。 2 3 5 异常发现 异常发现用于在数据库中发现数据中存在的偏差或异常。例如下列几种偏差 或异常就应引起人们的关注：不适用于任何一标准类的异常，有时这可能意味着 严重的错误或欺诈；相邻时间段内信息的异常变动，如二月份与一月份相比销售 收入骤然升高。 2 4 数据挖掘的应用 数据挖掘的应用十分广泛，各个应用领域既有相同之处，又有各自不同的独 l o 山东大学硕士学位论文 特地方。以下是数据挖掘技术的一些典型应用领域： 1 市场销售：是数据挖掘技术应用最早也是最重要的领域。主要功能是： 市场定位，消费者分析，预测销售趋势，优化营销策略，分析库存需求，识别顾 客的购买行为模式，协助货架布置，制定促销活动时间，促销商品组合以及了解 滞销和畅销商品状况等商业活动。通过收集、加工和处理涉及消费者消费行为的 大量信息，确定特定消费群体或个体的兴趣、消费习惯、消费倾向和消费需求， 进而推断出相应消费群体或个体下一步的消费行为，然后以此为基础，对所识别 出来的消费群体进行特定内容的定向营销，这与传统的不区分消费者对象特征的 大规模营销手段相比，大大节省了营销成本，提高了营销效果，从而为企业带来 更多的利润。 2 金融：金融领域也是数据挖掘技术可以一展拳脚的重要领域。主要功能 是：预测存、贷款趋势，优化存、贷款策略；抽取预测模式：监督交易活动，发 现交易规则。金融事务需要搜集和处理大量数据，对这些数据进行分析，发现其 数据模式及特征，然后可能发现某个客户、消费群体或组织的金融和商业兴趣， 并可观察金融市场的变化趋势。商业银行业务的利润和风险是共存的。为了保证 最大的利润和最小的风险，必须对账户进行科学的分析和归类，并进行信用评估。 3 h l t e m e t 的应用：研制新的更好的索引系统、利用已有索引系统或搜索引 擎开发高层次的搜索或发现系统。目前还有不少数据挖掘产品用来筛选因特网上 的新闻，保护用户不受无聊电子邮件和商业推销的干扰，很受欢迎。 4 化学、制药行业：从各种文献资料中自动抽取有关化学反应的信息，发 现新的有用的化学成分，分析和解释有利于提高产品质量、功能和增加公司利润 的重要数据。 5 遥感领域：在遥感领域，对每天从卫星上及其它方面传来的巨额数据进 行分析预测，能够有效地辅助气象预报及臭氧层监测等工作。 6 学校教育：学院分析学生历史信息，决定哪些人愿意报考哪些专业，发 送手册给他们。分析教师的学历、年龄、职称等与授课效果的关联规则，制定教 学方案，促进教学质量的提高。 7 其他应用。药房分析医师的处方，判断哪些医师愿意购买他们的产品。 广告公司分析人们购买模式，估计他们的收入和孩子数目，作为潜在的市场信息。 旅游调查局分析不同团体的旅游模式，决定不同团体之间的关联。医师分析病人 山东大学硕士学位论文 历史和当前用药情况，不仅诊断用药而且预测潜在的问题。 2 5 数据挖掘的发展趋势及面i 临的挑战 尽管目前数据挖掘技术得到了相当的研究和应用，但是仍然面临很多挑战， 这些挑战也是数据挖掘的发展趋势。 1 算法可伸缩性 由于数据产生和收集技术的进步，数g 字节、数t 字节甚至数p 字节的数 据集越来越普遍。如果数据挖掘算法要处理这些海量数据集，则算法必须是可伸 缩的( s c a l a b l e ) 。许多数据挖掘算法使用特殊的搜索策略处理指数性搜索问题。 可伸缩可能还需要实现新的数据结构，以有效的方式访问个别记录。例如，当要 处理的数据不能放进内存时，可能需要非内存算法。使用抽样技术或开发并行和 分布算法也可以提高可伸缩程度。 2 高维性数据 现在，常常遇到具有数以百计或数以千计属性的数据集，而不是数十年前常 见的只具有少量属性的数据集。在生物信息学领域，微阵列技术的进步已经产生 了涉及数千特征的基因表达数据。具有时间或空间分量的数据集也趋向于具有很 高的维度。例如，考虑包含不同地区的温度测量的数据集。如果温度在一个相当 长的时间周期内重复地测量，则维度( 特征数) 的增长正比于测量的次数。为低维 数据开发的传统的数据分析技术通常不能很好地处理这样的高维数据。此外，对 于某些数据分析算法，随着维度( 特征数) 的增加，计算复杂性迅速增加。 3 异种数据和复杂数据 通常，传统的数据分析方法只处理包含相同类型属性的数据集，或者是连续 的，或者是分类的。随着数据挖掘在商务、科学、医学和其他领域的作用越来越 大，越来越需要能够处理异种属性的技术。近年来，已经出现了更复杂的数据对 象。这些非传统类型的数据包括半结构化文本和超链接的w e b 页面集、具有序 列和三维结构的d n a 数据、包含地球表面不同位置上的时间序列测量值( 温度、 气压等) 的气象数据。为挖掘这种复杂对象而开发的技术应当考虑数据中的联系， 如时间和空间的自相关性、图的连通性、半结构化文本和x 地文档中元素之间 的父子联系。 4 数据的所有权与分布 山东大学硕士学位论文 有时，需要分析的数据并非存放在一个站点，或归属一个单位，而是地理上 分布在属于多个机构的资源中。这就需要开发分布式数据挖掘技术。分布式数据 挖掘算法面临的主要挑战包括： 1 ) 如何降低执行分布式计算所需的通信量； 2 ) 如何有效地统一从多个资源得到的数据挖掘结果； 3 ) 如何处理数据安全性问题。 5 非传统的分析 传统的统计方法基于一种假设检验模式。换句话说，提出一种假设，设 计实验来收集数据，然后针对假设分析数据。但是，这一过程劳力费神。当前的 数据分析任务常常需要产生和评估数以千计的假设，因此希望自动地产生和评估 假设导致了一些数据挖掘技术的开发。此外，数据挖掘所分析的数据集通常不是 精心设计的实验的结果，并且它们通常代表数据的时机性样本( o p p o m l i l i s t i c s a n l p l e ) ，而不是随机样本( r a n d o ms a i i l p l e ) 。而且，这些数据集常涉及非传统的 数据类型和数据分布。 山东大学硕士学位论文 3 1 时态数据库背景 第三章时态数据库概述 时间是自然界无所不在的客观属性，所有信息都具有相应的时态属性。随着 数据库与信息技术的深入和发展，信息系统面临许多新的应用和新的需求，对时 态信息处理的需求越来越迫切。时态信息处理已成为许多新一代数据库与信息系 统的关键技术，特别是在电子政务、电子商务、数据仓库、数据挖掘、决策支持