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

山东大学硕士学位论文 摘要 时间是现实世界的固有属性，许多数据库都存在时态语义问题，增加了时间 因素的关联规则研究是非常有意义的。增加了时间因素也使数据库变得复杂。本 章对时态事件空间给出定义，给出时态事件的一种表示方法，在关联规则挖掘方 面，扩展了普通关联规则在时态数据库中的应用，分别描述了同一对象不同属性、 不同对象同一属性之间的关联规则，给出一种不同对象同一属性之间的时态关联 规则算法，在股票时态数据库中实现了该算法，实验表明算法有效。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程。随着信息科技超乎想象的进展，许多新的计算机分析工具问世，例 如关系型数据库、模糊计算理论、基因算法则以及类神经网络等，使得从数据中 发掘宝藏成为一种系统性且可实行的程序。d a t am i n i n g 在各领域的应用非常广 泛，只要该产业拥有具分析价值与需求的数据仓储或数据库，皆可利用m i n i n g 工具进行有目的的挖掘分析。一般较常见的应用案例多发生在零售业、直效行销 界、制造业、财务金融保险、通讯业以及医疗服务等。 消费者过去的行为是其今后消费倾向的最好说明。通过收集、加工和处理涉 及消费者消费行为的大量信息，确定特定消费群体或个体的兴趣、消费习惯、消 费倾向和消费需求，进而推断出相应消费群体或个体下一步的消费行为，然后以 此为基础，对所识别出来的消费群体进行特定内容的定向营销，这与传统的不区 分消费者对象特征的大规模营销手段相比，大大节省了营销成本，提高了营销效 果，从而为企业带来更多的利润。 日常生活中通常会遇到这样的情况：超市管理人员希望得到顾客购买情况的 更多信息。比如某一时间区间内顾客购买物品的先后顺序。在企业制定决策时， 时态模式的双向关联规则对于如何决策时间因素，最大限度的增加正面效益尤为 重要。为解决这个问题，需要探索有效的基于时态数据库的数据挖掘技术。 为解决以上问题，基于时态数据关系模型和关联规则的相关概念，我们提 出一种新型的关联规则，即双向关联规则。给出了相关概念，讨论了双向关联规 则中时态数据集的存储技术，提出了相关挖掘算法，并用实例演算过程，从而论 证了算法的正确可能性。此规则可以更好地应用于时态数据库中，反映数据之间 山东大学硕士学位论文 的强关联关系。 双向关联规则主要描述数据间的前后关系，要求各事件按时间次序登记。对 企业来说，时态模式下的双关联规则可预测顾客的购买行为，促进销售量。它把 数据之间的关联性与时间联系起来，为了挖掘双向关联规则，不仅需要知道事件 是否发生，而且要确定各事件发生的先后顺序。这种挖掘方法更有利于企业有效 决策的制定。 关键词：数据挖掘；时态模型；关联规则：时态数据库 i i 山东大学硕十学位论文 a b s t r a c t d a t am i n i n gr e s e a r c h e st h ep r o c e s so fe x t r a c t i n gi m p l i c i t ，p r e v i o u s l yu n k n o w n a n dp o t e n t i a l l yu s e f u li n f o r m a t i o nf r o ml a r g eq u a n t i t i e so fd a t a w i t ht h ee x p l o s i o no f t h ec u r r e n td a t a ，l a r g ed a t a s e t si ne l e c t r o n i cf o r mt h a na ta n yt i m eh e r e t o f o r e v a r i o u s t e c h n i q u e sh a v e b e e ne m p l o y e dt oc o n v e r tt h ed a t ai n t oi n f o r m a t i o n ，i n c l u d i n g c l u s t e r i n g ，c l a s s i f i c a t i o n ，r e g r e s s i o n ，a s s o c i a t i o nr u l ei n d u c t i o n ，s e q u e n c i n gd i s c o v e r y ， a n ds of o n 1 w ep a ym o r ea t t e n t i o nt ot h et e m p o r a ld a t at oa v o i dp r o c e s s i n gh u g e d a t ai nr e a ld a t a b a s e n e wk n o w l e d g ed i s c o v e r yf r o mt e m p o r a ld a t a b a s e si sa p o p u l a r t a s ki nd a t am i n i n g t e m p o r a ld a t am i n i n gh a sb e c o m ea l li m p o r t a n tb r a n c ha n dq u i t es t u d y c i r c u m s t a n c eo fd a t am i n i n gf i e l d a tp r e s e n t ，m o s to ft h es t u d i e sa b o u ti t sa s s o c i a t i o n r u l e m i n i n gl a c ku n i t e dt h e o r e t i c a lf r a m e w o r k s ， a n dm o d e la n dc o r r e s p o n d i n g a l g o r i t h mb a s e do nt e m p o r a ld a t aa r eo n l ya p p l i e dt os o m es p e c i a ld a t et y p e w h a t s m o r e ，a l o n g 谢t hi n t r o d u c i n go ff u z z ys e ta n dr o u g hs e tt h e o r y ，h o wt oa p p l i e d u n c e r t a i n t yt h e o r yt om i n ei s n ta l s os o l v e de t c i nt h i st h e s i s ，a tf i r s t ，b ym e a n so f a n a l y s i sa n ds t u d y , a s s o c i a t i o nr u l e sm i n i n gi si d e n t i f i e da so n eo ft h ei m p o r t a n t p r o b l e m si nd a t am i n i n g l e tu sf i r s td e f i n et h ep r o b l e mf o rad a t a b a s ec o n t a i n i n ga s e to ft r a n s a c t i o n s ，w h e r ee a c ht r a n s a c t i o nc o n t a i n sas e to fi t e m s a na s s o c i a t i o nr u l e h a st h ef o r mo fw h e r ea n da r es e t so fi t e m s ，i ns u c har u l e ，w er e q u i r et h a tt h e f r e q u e n c yo ft h es e to fi t e m si sa b o v eac e r t a i nt h r e s h o l dc a l l e dt h em i n s u p t h e f r e q u e n c y ( a l s ok n o w na ss u p p o r t ) o fa s e to fi t e m si st h en u m b e ro fo c c u r r e n c e so fi n o rt h en u m b e ro ft r a n s a c t i o n si nt h a tc o n t a i n t h ec o n f i d e n c eo ft h er u l es h o u l da l s o b ea b o v ea t h r e s h o l d b yc o n f i d e n c ew em e a nt h ep r o b a b i l i t yo fg i v e n t i m ei sa l s oa l li m p o r t a n tf a c t o ri nr e a ld a t a b a s e s w es h o u l de x t r a c tu s e f u l i n f o r m a t i o nu n d e rt h es t r i c ta p p l i c a t i o no ft e m p o r a ld a t a b a s e s ow ea l s op r e s e n ta t e m p o r a lr e l a t i o nm o d e lr e s t r i c t e dw i t h i nt i m el i m i t s t h ee n t e r p r i s en e e dt oa n a l y z e t h ea m o u n to fd a t at of o r ma ne x a c te s t i m a t i o no fc u s t o m s p u r c h a s ep o w e r d u r i n ga p a r t i c u l a rp e r i o do ft i m e i i i 【l j 东大学硕士学位论文 b a s e do nt h ep o s i t i v ea s s o c i a t i o nr u l ea n dt h en o t i o no ft h et i m e m o d e l ，w e p r o p o s ean e wk i n do fo n ec a l l e db i d i r e c t i o n a la s s o c i a t i o nr u l e i td e n o t e sas t r o n g a s s o c i a t i o na m o n gd a t ai nt h et e m p o r a ld a t a b a s e k e y w o r d s ：d a t am i n i n g ；t e m p e r a im o d e i ：a s s o o i a t i o nr u i e ：t e m p e r a i d a t a b a s e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均己在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 哆应 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：缆导师签名： 岁7 7 彬 乙 ， 山东大学硕士学位论文 第一章引言 1 1 本文的研究背景与研究现状 1 1 1 数据挖掘产生的背景 近年来，随着科学技术的迅猛发展，经济和社会都取得了极大的进步。与此 同时，各个领域产生了大量的数据，如医院每天接待大流量病人，对病人病情等 信息的管理，股票市场每天的巨额交易数据。且这些不断增加如潮水般的数据在 以后仍将持续大量增长。然而，这些丰富的数据自身并不存在揭示或分析隐藏在 数据中的有用信息的作用。虽然，二十世纪数据库技术也取得了丰硕的成果，并 应用于广泛的领域。但是数据库技术作为一种基本的信息存储和管理方式，也无 法在数据中发现存在的关系和规则，不可能根据现在已有的数据预测以后的发展 趋势，更不可能找到数据之间隐藏的各种客观规律。因此，伴随着数据量的日益 增长，现实中又缺乏数据挖掘的相关工具，导致了“数据爆炸但知识贫乏”的现 象。于是，在数据库技术飞速发展的同时，数据挖掘技术应运而生，这种更加实 用的技术又一次丰富了我们的生活，简化了我们的工作。 数据挖掘 1 ( d a t am i n i n g ) 禾1 用了数据库( d a t a b a s e ) 技术、人工智能( a r t i f i c i a l i n t e l l i g e n c e ) 、机器学习( m a c h i n el e a r n i n g ) 、统计学( s t a t i s t i c s ) 、知识工程 ( 硒o w l e 电ee n g i n e e r i n g ) 、面向对象方法( 0 b j e c t - o r i e n t e dm e t h o d ) 、信息检索 ( i n f o r m a t i o nr e t r i e v a l ) 、高性能计算( h i 曲一p e r f o r m a n c ec o m p u t i n g ) 以及可视化 ( v i s u a l i z a t i o n ) 等最新技术的研究成果，把这些高深复杂的技术封装起来，使人们 不用自己掌握这些技术也能完成同样的功能，并且更专注于自己所要解决的问 题。 数据挖掘充分显示了多学科交叉研究领域的优势，正以一种全新的概念改变 着人们利用数据的方式。经过十多年的研究，产生了许多新概念和方法。特别是 近几年来，一些基本概念和方法趋于清晰，它的研究正向更深入的方向发展。 1 1 2 时态数据特点与时态数据库 传统上，大多数数据挖掘问题仅涉及静态数据。近几年来，主要关注数据动 山东大学硕士学位论文 态特性的时态数据挖掘( t e m p o r a ld a t am i n i n g ，简称t d 峋【2 】，成为学术界研究 的热点之一。时间是自然界无所不在的客观属性，在实际应用中，数据往往随时 间而变化。我们称随时间而变化的数据为时态数据。在现实生活中，时态数据随 处可见，如股市交易指数、超市销售、w e b 访问、气象观测、临床数据等。很多 数据库应用都涉及到的时态数据。这些应用不仅需要存取数据库的当前状态，也 需要存取数据库随时间变化的情况。 管理时态数据的数据库系统需要对时间语义提供三方面的支持 4 】：时间点、 时间间隔、与时间有关的关系。传统数据库管理系统在时态数据的表示上有两种 局限性。第一种局限性是：不保存数据库改变的历史。每一个数据更新操作都删 除了更新前的事实。数据库仅仅保存某个领域的当前状态，而不能保存这个领域 的历史状态。第二种局限性是：数据一进入数据库就立即生效。在很多应用中， 数据的录入时间( 即数据进入数据库的时间) 和数据可以被利用的时间是不同的。 为了克服这两种局限性，我们需要新的数据模型。既能够准确地表示时态数 据的时间语义，又能够区分随时间变化的信息和与时间无关信息并分别表示之。 时态数据库应运而生。随着数据库技术的深入发展，时态信息处理已成为电子政 务、电子商务、数据仓库等新一代数据库与信息系统的关键技术。经过2 0 多年 的研究和实践，时态数据库技术已发展成- i - 1 独特的数据库学科。但是基于时态 数据库的数据挖掘技术起步较晚，相关研究不甚成熟，在此基础上的研究更显得 任重而道远。 1 2 本文的主要研究工作和研究成果 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。在同一段时间区间内，各种事件都随 着时间的变化而变化，并且有各自的变化规律，一种事件的状态变化与另一事件 的变化在时间上是否存在关联? 两个事件同时在同一区间内发生，这两个事件是 否存在某种隐藏的规则? 关联规则发现的对象是交易序列，目标是从交易数据集 ( 如超市的购物记录) 中找出相似的交易关联规则。传统的关联规则发现不考虑 时态关系，附加时态特征的时态关联规则可以更好地描述客观规律。本文对数据 挖掘、时态数据库、关联规则等研究动态进行了概述，在有关文献的基础上，研 2 山东大学硕士学位论文 鲁曼皇曼鼍皇量1 amml 二, 皇曼鼍曼曼曼曼皇曼皇曼皇鼍鼍曼晕曼皇皇曼! 曼暑曼曼曼曼曼曼曼曼曼皇詈曼皇曼曼曼喜量基 究了时间的表示模型，时间区间之间的时态关系，研究了确定时刻到确定时间的 对应关系。 在此时间模型的基础上，提出一种双向关联规则的概念，并把这种关联规则 挖掘应用到时态数据上。本文提出了一种基于时态数据模型的双向关联规则挖掘 算法，并对实验结果进行了分析。 本文首先对数据挖掘进行了详细的概述，介绍了数据挖掘的相关概念和研究 内容、常用技术及传统数据挖掘中关联规则的经典算法。继而介绍了时态数据模 型的特点以及相关概念。介绍了基于时态数据模型的关联规则挖掘的知识。提出 一种新型的双向关联规则概念，并且在时态数据模型的基础上，分析了传统关联 规则的不完善之处。在深入分析问题原因的基础上提出适用于双向关联规则的算 法。 1 3 本文的组织结构 本文是按照下面的结构组织的： 第二章数据挖掘技术概述，介绍了数据挖掘的相关知识，重点介绍了数据挖 掘的任务、相关实现技术、相关应用及发展趋势。 第三章时态数据库综述，这部分主要包括时态数据库产生的背景、时态数据 库中关于时间的概念、时态数据库的应用开发模型以及时态数据挖掘技术。 第四章普通关联规则挖掘技术和算法，讨论了经典的关联规则挖掘算法，主 要是基于关系数据库上的关联规则的提取。在此基础上提出了时态数据库的双向 关联规则挖掘，这是本文的主体。阐述了时态关联规则的有关概念，在此基础上 提出双向关联规则的意义、概念及存储结构。重点提出了时态模型下的双向关联 规则挖掘算法。 第五章基于时态数据库的双向关联规则算法给出了实例演算。并给出算法的 实验结果，将本文提出的算法与经典算法相比较，并给出分析结果。 第六章对本文的工作做了一个总结，指出本文的不足，并对下一步的研究工 作进行展望。 3 山东大学硕士学位论文 第二章数据挖掘技术概述 2 1 数据挖掘的概念和特征 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程【7 】。还有很多和这一术语相近似的术语，如从数据库中发现知识 ( d m k d ) 数据分析、数据融合( d a t af u s i o n ) n 及决策支持等。人们把原始数据看 作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关 系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分 布在网络卜的异构型数据。发现知识的方法可以是数学的，也可以是非数学的： 可以是演绛的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、 决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门广 义的交叉学科，它汇聚了不同领域的研究者。 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检 索查询调用，而且要对这些数据进行微观到宏观的统计、分析、综合和推理，以 指导实际问题的求解，企图发现事件间的相互关联，甚至利用己有的数据对未来 的活动进行预n 5 】。例如某电话公司要求k d d 研究组，根据其拥有十多年的客 户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利 于客户的优惠政策。这样就把人们对数据的应用，从低层次的末端查询操作，提 高到为各级经营决策者提供决策支持。这种需求驱动力，比数据库查询更为强大 【4 2 】。同时需要指出的是，这里所说的知识发现，所有发现的知识都是相对的， 是有特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，最 好能用自然语言表达发现结果。因此数据挖掘的研究成果是很讲求实际的。 2 2 数据挖掘的研究内容和本质 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三 根强大的技术支柱【3 】：数据库、人工智能和数理统计。因此，k d d 大会程序委 员会曾经由这三个学科的权威人物同时来任主席。目前d m k d 的主要研究内容 4 l j i 东大学硕士学位论文 mm m m, 一 m m 曼曼曼曼曼曼鼍曼! 曼鼍曼曼曼曼曼曼曼曼 包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表 示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及 网上数据挖掘等。数据挖掘所发现的知识最常见的有以下四类【6 】： 1 广义知识( g e n e r a l i z a t i o n ) 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征 的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性 质，是对数据的概括、精炼和抽象。 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约等。 数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“o l a p ”等。 该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计数、求 和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很多聚集函 数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果将能保证快 速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。另一种广义知 识发现方法是加拿大s i m o n f r a s e r 大学提出的面向属性的归约方法。这种方法以 类s q l 语言表示数据挖掘查询，收集数据库中的相关数据集，然后在相关数据 集上应用一系列数据推广技术进行数据推广，包括属性删除、概念树提升、属性 阈值控制、计数及其他聚集函数传播等。 2 关联知识( a s s o c i a t i o n ) 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之 间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名 的关联规则发现方法是1 l a g r a w a l 提出的a p f i o f i 算法。关联规则的发现【8 】可分 为两步。第一步是迭代识别所有的频繁项目集，要求频繁项目集的支持率不低于 用户设定的最低值：第二步是从频繁项目集中构造可信度不低于用户设定的最低 值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量 最大的部分。 3 分类知识( c l a s s i f i c a t i o n & c l u s t e r i n g ) 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。 最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是 一种有指导的学习方法。该方法先根据训练子集( 又称为窗口) 形成决策树。如 山东大学硕士学位论文 果该树不能对所有对象给出正确的分类，那么选择一些例外加入到窗口中，重复 该过程一直到形成正确的决策集。最终结果是一棵树，其叶结点是类名，中间结 点是带有分枝的属性，该分枝对应该属性的某一可能值。最为典型的决策树学习 系统是i d 3 ，它采用自顶向下不回溯策略，能保证找到一个简单的树。 数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和线性辨别分析 是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最 近也有人研究使用神经网络方法在数据库中进行分类和规则提取。 4 预测型知识( p r e d i c t i o n ) 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以 认为是以时间为关键属性的关联知识。 目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析方法，这些经 典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和自 回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时间序 列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此，仅仅 通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的 预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现 存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立 新的模型。也有许多系统借助并行算法的计算优势进行时间序列预测。 5 偏差型知识( d e v i a t i o n ) 此外，还可以发现其他类型的知识，如偏差型知识( d e v i a t i o n ) 9 ，它是对差 异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据 聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着概 念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。 2 3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖 掘的目标是从数据库中发现隐含的、有意义的知识。主要有以下五类功能【1 4 】： 1 自动预测趋势和行为 6 山东大学硕士学位论文 曼皇曼皇曼量曼曼曼曼曼曼曼曼曼曼! 蔓曼曼! 曼皇曼曼曼! m mmmm - 鼍 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析 的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问 题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它 可预测的问题包括预报破产以及认定对指定事件最可能做出反应的群体。 2 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中 数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。 3 聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们 对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统 的模式识别方法和数学分类学。8 0 年代初，m c h a l s k i 提出了概念聚类技术及其 要点是 1 5 】，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某 种内涵描述，从而避免了传统技术的某些片面性。 4 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 5 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏 差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与 模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结 果与参照值之间有意义的差别。 2 4 数据挖掘的常用技术 1 6 】： 现有的关于数据挖掘研究领域主要有以下几个不同的常用技术解决方案 山东大学硕士学位论文 1 神经网络方法 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和 高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关 注。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型 网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网 络模型；以矾模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法。神经 网络方法的缺点是”黑箱”性，人们难以理解网络的学习和决策过程。 2 遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生 全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它 在数据挖掘中被加以应用。 s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具 1 7 】，利用该工具对 两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据 挖掘的有效方法之一。遗传算法的应用还体现在与神经网络、粗集等技术的结合 上。如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的 连接和隐层单元：用遗传算法和b p 算法结合训练神经网络，然后从网络提取规 则等。但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。 3 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中 找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别 适合大规模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的著名 的基于信息熵的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法；i d 3 决策树 是单变量决策树，复杂概念的表达困难；同性间的相互关系强调不够；抗噪性差。 针对上述问题，出现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计了i d 4 递增式学习算法；钟鸣，陈文伟等提出了i b l e 算法等。 4 粗集方法 粗集理论【1 8 】是一种研究不精确、不确定知识的数学工具。粗集方法有几个 优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。 山东大学硕士学位论文 粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和 新发展起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集 的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普 遍存在的【1 9 】。因此连续属性的离散化是制约粗集理论实用化的难点。现在国际 上已经研制出来了一些基于粗集的工具应用软件，如加拿大r e g i n a 大学开发的 k d d - r 、美国k a n s a s 大学开发的l e r s 等。 5 覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合 中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去， 相反则保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。 比较典型的算法有m i c h a l s k i 的a q l l 方法、洪家荣改进的a q l 5 方法以及他的a e 5 方法。 6 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性 关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析 可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用 统计( 求大量数据中的最大值、最小值、总和、平均值等) 、回归分析( 用回归方程 来表示变量间的数量关系) 、相关分析( 用相关系数来度量变量间的相关程度) 、差 异分析( 从样本统计量的值得出差异来确定总体参数之间是否存在差异) 等。 7 模糊集方法 即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和 模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度 来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础 上，提出了定性定量不确定性转换模型云模型，并形成了云理论。 采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过这些 工具所面对的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工 业标准的数据仓库和联机分析系统中去了。 9 山东大学硕士学位论文 2 5 数据挖掘的发展趋势及面临的挑战 尽管目前数据挖掘技术得到了相当的研究和应用，但是仍然面临很多挑战， 这些挑战也是数据挖掘的发展趋势。 1 算法可伸缩性 由于数据产生和收集技术的进步，数g 字节、数t 字节甚至数p 字节的数 据集越来越普遍。如果数据挖掘算法要处理这些海量数据集，则算法必须是可伸 缩的( s c a l a b l e ) 。许多数据挖掘算法使用特殊的搜索策略处理指数性搜索问题。 可伸缩可能还需要实现新的数据结构，以有效的方式访问个别记录。例如，当要 处理的数据不能放进内存时，可能需要非内存算法。使用抽样技术或开发并行和 分布算法也可以提高可伸缩程度。 2 高维性数据 现在，常常遇到具有数以百计或数以千计属性的数据集，而不是数十年前常 见的只具有少量属性的数据集。在生物信息学领域，微阵列技术的进步已经产生 了涉及数千特征的基因表达数据。具有时间或空间分量的数据集也趋向于具有很 高的维度。例如，考虑包含不同地区的温度测量的数据集。如果温度在一个相当 长的时间周期内重复地测量，则维度( 特征数) 的增长正比于测量的次数。为低 维数据开发的传统的数据分析技术通常不能很好地处理这样的高维数据。此外， 对于某些数据分析算法，随着维度( 特征数) 的增加，计算复杂性迅速增加。 3 异种数据和复杂数据 通常，传统的数据分析方法只处理包含相同类型属性的数据集，或者是连续 的，或者是分类的。随着数据挖掘在商务、科学、医学和其他领域的作用越来越 大，越来越需要能够处理异种属性的技术。近年来，已经出现了更复杂的数据对 象。这些非传统的数据类型的例子包括含有半结构化文本和超链接的w e b 页面 集、具有序列和三维结构的d n a 数据、包含地球表面不同位置上的时间序列测 量值( 温度、气压等) 的气象数据。为挖掘这种复杂对象而开发的技术应当考虑 数据中的联系，如时间和空间的自相关性、图的连通性、半结构化文本和x m l 文档中元素之间的父子联系。 4 数据的所有权与分布 有时，需要分析的数据并非存放在一个站点，或归属一个单位，而是地理上 1 0 山东大学硕士学位论文 分布在属于多个机构的资源中。这就需要开发分布式数据挖掘技术。分布式数据 挖掘算法面临的主要挑战包括：如何降低执行分布式计算所需的通信量? 如何有 效地统一从多个资源得到的数据挖掘结果? 如何处理数据安全性问题? 5 非传统的分析 传统的统计方法基于一种假设检验模式。换句话说，提出一种假设，设 计实验来收集数据，然后针对假设分析数据。但是，这一过程劳力费神。当前的 数据分析任务常常需要产生和评估数以千计的假设，因此希望自动地产生和评估 假设导致了一些数据挖掘技术的开发。此外，数据挖掘所分析的数据集通常不是 精心设计的实验的结果，并且它们通常代表数据的时机性样本( o p p o r t u n i s t i c s a m p l e ) ，而不是随机样本( r a n d o ms a m p l e ) 。而且，这些数据集常常涉及非传统 的数据类型和数据分布。 山东大学硕士学位论文 第三章时态数据库综述 3 1 时态数据库产生的背景 时间是所有现实现象的基本属性。在现实问题中，任何事件都和时间相联系 并受一定的时态关系约束，因为任何事件都是在一定的时间发生，又在一定的时 间消失。传统的数据库记载着现实世界中的各种数据，但是它仅仅能体现现实世 界中数据的当前状态，只反映了一个对象在某一个时刻的状态( 快照) ，不联系其 过去和未来。这就是人们常说得快照数据库( s n a p s h o td a t a b a s e ) 2 3 。 现代的信息流包含事件的时态信，皂, ( t e m p o r a li n f o r m a t i o n ) ，其中有时刻信息 ( i n s t a n ti n f o r m a t i o n ) ，时间区间信息( i n t e r v a li n f o r m a t i o n ) 和相对时问信息( 之前、 之后、重叠1 等等。 随着数据库技术研究的广泛深入，人们对时态信息处理的需求越来越迫切， 比如病历数据库中，发生在交叠时间的两种疾病是否存在因果关系，工资系统中 职务和工资随着时间的变化规律，从自然灾害的历史记录中寻找其规律等等。 如今，日益广泛的数据库应用要求管理事件的历史性信息和系统中元事件的 时态信息。人们迫切需要解决两个问题：一是要求管理被处理事件的历史性信息， 如与人事、财务、金融和自然灾害等有关的历史资料，从中可看出事物发展的本 质规律；二是要求管理数据库系统中元事件的时态信息，如增查，删改的时刻和 时间区间、在多用户系统中对锁定排队及资源竞争协调的时标等，这些数据有助 于提高数据库系统的可靠性和效率。因此引入时态数据库。 3 2 时态数据库的时间概念与表示 3 2 1 时间概念 时间的概念涉及到哲学、心理学、语言学、医学、人工智能、数据库管理系 统等众多的领域。从信息系统看，时间是一条没有端点，向过去和未来无限延伸 的轴线，是信息空间中新的一维。除了具有通用性、连续性、可测量性外，还有 不可逆性。时态数据库中涉及到以下三类时间1 1 0 ： 1 事务时间( t r a n s a c t i o nt i m e ) 山东大学硕士学位论文 事务时间又称“数据库时间”、“系统时间”、“逻辑时间、“历史记录时间 等。它是指事件被记入数据库的时间，是数据管理系统对数据库对象进行实际操 作( 插入、更新、删除与查询) 时记录的系统时间戳。所以事务时间反映了数据库 的实际操作时间，不能晚于当前时间，也不能指向未来时间。通常事件发生和事 件录入数据库之间有一段时间延迟，故有效时间通常小于事务时间。若二者相等， 则意味着现实世界事件亦是事务数据库本身，若有效时间大于事务时间，则意味 着系统包含未来事件的信息。 事务时间是应用独立的，用户不可以修改事务时间，沿着事务时间轴，可以 清楚查看数据库在各个事务时间点的状态和现有数据库状态变迁的历史【1 1 】。 2 有效时问( v 射i dt i m e ) 一个事实或事件的有效时间，又称“世界时间”、“物理时间”、“外界时间”、 “对象时间”等。它是一个空间实体从产生到消亡，在现实世界中所存在的时间 间隔，或该实体在现实世界中为真的时间段。如果理论模型允许目标消亡后再 生，则有效时间是多个不相交的时间区间的并。有效时间是应用依赖的，其取值 是否有效视具体应用场合而定，以对应于实际应用的需要或现实世界的变化。 有效时间可以反映过去、现在和将来，它可以用单一的时间点、单一的时间 区间来表示，也可以用时间点集合、时间区间的有限集合甚至用整个时间域来表 示。与事务时间不同，有效时间可以由用户更新。 3 用户自定义时间( u s e r - d e f i n e dt i m e ) 用户自定义时间是指用户根据自己的需要或理解定义的时间。它是一个时间 属性域，数据库管理系统将它与其他一般的属性域一样来理解和处理。与传统的 数据库管理系统一样，时态数据库管理系统不对用户自定义时间作任何特殊处 理，不需要专门的语言支持。用户定义的时间值是完全应用依赖的，由用户应 用以常规方式存取。 3 2 2 时间标记 时间标记可以仅记录事件发生的时间，亦可以映射一个事件的寿命。前者使 用较少的储存空间，不携冗余的数据或零值。但存储需要的经济性往往被反映查 询处理附加的时间加以平衡。当个事件在现实世界发生时，反映在数据库中是 某一实体的一个或多个属性值的变化。换句话说，获捕的信息是变化的信息和变 【j f 东大学硕十学位论文 化发生的时间，这意味着要查询个别状态寿命的信息，数据库必须经过若干记录 筛选，直至达到可确定此状态何时终结的记录为止。若时态查询很频繁，可以对 每一个状态贮存一套两个时间标记：“起始( s i n c e ) 和“终结( u n t i l ) ”， 以描 述指定状态的有效时间段。将时间增加到数据库中的方式有如下几种： 1 元组瞬时标记( i n s t a n t - s t a m p i n go f t u p l e s ) 每个元组含有一个时间值分量，时间值指明该元组为当前元组的开始时间。 2 元组时区标记( i n t e r v a l - s t a m p i n go f t u p l e s ) 每个元组含有两个时间值，这个连个时间值分别指明该元组为当前元组的开 始时间和结束时间。 3 元组时态元素标记( t e m p o r a l e l e m e n to f t u p l e s ) 每个元组含有一个时态元素，时态元素指明该元组为真的时间。 4 属性瞬时标记( i n s t a n t s t a m p i n go f a t t r i b u t e s ) 元组的每个属性附加一个时间值，时间值指明该属性为真的开始时间。 5 属性时区标记( i n t e r v a l s t a m p i n go f a t t r i b u t e s ) 元组的每个属性附加两个时间值，这两个时间值分别指明该属性为真的开始 时间和结束时间。 6 属性时态元素标记( t e m p o r