（控制理论与控制工程专业论文）数据库中数据挖掘理论方法及应用研究.pdf

湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 墨鼍广 日期：工毕年- z 月一) 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 日期：i o 畔年a 2 月i ) 日 日期：2 吣牛年，1 月lj 日 博士学位论文 摘要 数据挖掘是目前数据库和信息决策领域最前沿的研究方向之一。本文研究数 据库中数据挖掘，主要包括以下内容： 1 介绍了数据库和数据挖掘技术的发展动态，讨论了数据挖掘技术的研究现 状、存在的不足和发展方向。分析了海量数据库产生的原因和特点。讨论了适于 在海量数据库中进行数据挖掘的算法的基本特征，即算法应该具有线性计算复杂 度o ( n ) 。 2 对挖掘关联规则的算法进行了研究。首先，我们分析了a p r i o r i 算法的某些 不足；随后，我们提出了一种基于a p r i o r i 的改进算法，新算法在某些场合能减少 扫描数据库的次数，提高了算法的效率；随后，我们又提出了一种基于事务树的 高效算法，用该算法挖掘频繁项目集只需要一次扫描事务数据库，不需要产生候 选项目集，该算法的速度大约是a p r i o r i 算法的1 0 倍；最后，我们提出了一种用 v i s u a lf o x p r o 实现a p r i o r i 算法的方法。 3 对关联规则的衡量标准进行了研究，指出了原衡量标准和若干改进方法的不 足。目前，关联规则常用的衡量标准是支持度和置信度，如果按现有标准来生成 关联规则，可能会发现大量冗余的、虚假的关联规则；为了减少关联规则挖掘中 的无效关联规则，我们分析了产生问题的根源，提出了三种改进方法，即在关联 规则的衡量标准中增加影响度、相对置信度或有效度标准，并分别定义了影响度、 相对置信度和有效度。根据影响度、相对置信度或有效度的大小，将强关联规则 分为正关联规则、无效关联规则和负关联规则。一般来说，只有正关联规则才是 有效的关联规则，有时，它们只占强关联规则总数的- - d , 部分。此外，我们提供 了用新衡量标准进行关联规则挖掘的改进算法，并进行了实验。实验表明，我们 提出的方法能明显减少无效的关联规则。 4 对目前比较优秀的各种分类算法进行了介绍、分析和比较。综合提出了分 类算法的评价标准。随后，我们讨论了s p r i n t 算法。针对s p r i n t 算法的不足， 提出了二种处理离散属性的新方法。这些方法能明显减少求最优分割点的运算量， 提高算法的执行速度。最后，我们提出了一种基于抽样的快速数据分类算法。该 算法既是可伸缩的，也可并行化。实验表明，该算法的速度是s p r i n t 算法的1 0 - 5 0 倍。 5 介绍、，析和比较了各种常用的聚类方法，综合提m 了聚类算法的评价标 准和今后的研，e 方向。随后，在分析b i r c h 算法不足的堆础上，提出了一种基 于抽样的疑炎? f 法。测试结果表明，咳算法在聚类速度方面明显优 。b i r c h 算 数据库中数据挖掘理论方法及应用研究 法。 6 为了提高数据挖掘的效率，提出了采用约束和多维技术的方法进行数据挖 掘。分析了数据挖掘中可能的约束类型，用关联规则挖掘讨论了哪些约束可运用 于数据挖掘过程中。设计出了一个采用约束与多维技术的数据挖掘系统结构。 7 讨论了数据挖掘技术在电力系统中应用，重点研究了最优潮流问题的高效算 法。我们根据电力系统的特点，把无功界约束与一般非线性不等式约束分开来考 虑，提出了一类投影渐近半光滑n e w t o n 型算法，实验表明，我们提出的算法具 有良好的计算性能。 关键词：数据库：数据挖掘：关联规则；分类；聚类；算法 博十学位论文 a b s t r a c t d a t am i n i n gi so n eo ft h em o s tf r o n t i e rr e s e a r c hd i r e c t i o n so fd a t a b a s ea n d i n f o r m a t i o nd e c i s i o nf i e l d w es t u d yt h ed a t am i n i n gi nd a t a b a s e s t h ea r t i c i l em a i n l y i n c l u d e st h ef o l l o w i n gc o n t e n t s ： 1w es t u d yt h ed e v e l o p m e n to fd a t a b a s ea n dd a t a m i n i n gt e c h n o l o g y ，a n d d i s c u s st h e i rr e s e a r c h ，l a c k sa n dt r e n d s t h ec a u s ea n df e a t u r e so fv e r yl a r g ed a t a b a s e a r ea n a l y z e d t h em a i nf e a t u r e so ft h ea l g o r i t h m sw h i c hf i tt om i n i n gi nv e r yl a r g e d a t a b a s ea r ed i s c u s s e d t h u si ti se s s e n t i a lt h a ta l ld a t am i n i n ga l g o r i t h m sh a v e n e a r - l i n e a rt i m ec o m p l e x i t yw i t hd a t as i z eo ( n ) 2t h ea l g o r i t h ma p r i o r ii nm i n i n ga s s o c i a t i o nr u l e si ss t u d i e d f i r s t ，w ep o i n to u t t h ed e f e c t t h e np r e s e n ta ni m p r o v e da l g o r i t h m c o m p a r e dt ot h eo r i g i n a la l g o r i t h m ， t h en e wa l g o r i t h mc a nr e d u c et h en u m b e ro fd a t a b a s es c a n s i tc a ni m p r o v et h e e f f i c i e n to ft h ea l g o r i t h md r a m a t i c a l l yi ns o m ec a s e s n e x t ，w ep r e s e n taf a s t a l g o r i t h mf o rm i n i n ga s s o c i a t i o nr u l e sb a s e do nat r a n s a c t i o nt r e e t h ea l g o r i t h mi s v e r ye f f i c i e n ts i n c ei t s c a n st r a n s a c t i o nd a t a b a s eo n l yo n et i m ea n dm i n e sf r e q u e n t i t e m s e t sw i t h o u tc a n d i d a t eg e n e r a t i o n t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e a l g o r i t h mi sa b o u t1 0t i m e sf a s t e rt h a nt h a to ft h ea p r i o r ia l g o r i t h m f i n a l l y ，w e o f f e r e dam e t h o df o ri m p l e m e n t a t i o no fa p r i o r ia l g o r i t h mb yv i s u a lf o x p r o 3t h ej u d g m e n tc r i t e r i ao fa s s o c i a t i o nr u l e sa r es t u d i e d t h ep r e s e n tj u d g m e n t c r i t e r i ao fa s s o c i a t i o nr u l e sa r eas u p p o r ta n dac o n f i d e n c e i ft h ea s s o c i a t i o nr u l e s a r eg e n e r a t e da c c o r d i n gt ot h ec r i t e r i a ，al o to ft h e ma r ei n v a l i da n df a l s e i no r d e rt o r e d u c ei n v a l i da s s o c i a t i o nr u l e s ，w ea n a l y z e dt h er e a s o n ，p r e s e n t e dt h r e ei m p r o v e d m e t h o d s t h a ti s ，t oa d de f f e c t ，r e l a t i v ec o n f i d e n c eo rv a l i d i t yi nt h ej u d g m e n tc r i t e r i a a c c o r d i n gt ot h ev a l u eo ft h e m ，a s s o c i a t i o nr u l e sa r ec l a s s i f i e di n t op o s i t i v e ，i n v a l i d a n dn e g a t i v ea s s o c i a t i o nr u l e s i ng e n e r a l ，o n l yp o s i t i v ea s s o c i a t i o nr u l e sa r ev a l i d ， w h i c ho n l yc o v e ras m a l lp r o p o r t i o no fa l ls t r o n ga s s o c i a t i o nr u l e s i na d d i t i o n ，a n a l g o r i t h mo fn e wj u d g m e n tc r i t e r i ai nm i n i n ga s s o c i a t i o nr u l e si sp r e s e n t e da n dt e s t e d t h et e s tr e s u l t ss h o wt h a tt h em e t h o d sc a no b v i o u s l yr e d u c ei n v a l i da s s o c i a t i o nr u l e s 4w ep u tf o r w a r ds t a n d a r d sa c c o r d i n gt ow h i c hw ec a ne v a l u a t ec l a s s i f i e r sb y a n a l y z i n ga n dc o m p a r i n gw i t h av a r i e t yo ft y p i c a lc l a s s i f i e r s n e x t ，w ed i s c u s s s p r i n ta l g o r i t h m ，a n dp r e s e n tt w on e wm e t h o d st op r o c e s sc a t e g o r i c a la t t r i b u t e s w i t ht h eh e l po fm e t h o d s ，t h es p r i n ta l g o r i t h mc a nr e d u c ei t so p e r a t i o n sf o rf i n d i n d 数据库中数据挖掘理论方法及应_ j 研究 t h eo p t i m a ls p l i t t i n gp o i n t ，a n dg e tm o r ee f f i c i e n t f i n a l l y , w ep r e s e n taf a s td a t a c l a s s i f i c a t i o n a l g o r i t h mb a s e do ns a m p l i n g t h ea l g o r i t h mi s b o t hs c a l a b l ea n d p a r a l l e l t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi s f r o m1 0t o5 0t i m e s f a s t e rt h a nt h a to ft h es p r i n ta l g o r i t h m 5w ep u tf o r w a r ds t a n d a r d sa c c o r d i n gt ow h i c hw ec a ne v a l u a t et h ec l u s t e r i n g m e t h o da n dt h et r e n d sb ya n a l y z i n ga n dc o m p a r i n gw i t hav a r i e t yo ft y p i c a l c l u s t e r i n g n e x t ，b a s e d o nt h ea n a l y s i so fd e f i c i e n c yo fb i r c ha l g o r i t h m ，w e p r o p o s ean e wc l u s t e r i n ga l g o r i t h mb a s e do ns a m p l i n g t h ee x p e r i m e n t a l r e s u l t s s h o wt h a tt h es p e e do ft h ea l g o r i t h mi so b v i o u s l yf a s t e rt h a nt h a to ft h eb i r c h a l g o r i t h m 6i no r d e rt oi m p r o v et h ee f f i c i e n c yo fd a t am i n i n g w es u g g e s tt h a tc o n s t r a i n t a n dm u l t i d i m e n s i o n a lt e c h n i q u e ss h o u l db ea p p l i e di nd a t am i n i n g t h i sp a p e r i n t r o d u c e st h et y p e so fc o n s t r a i n ti nd a t am i n i n g ，a n dd i s c u s s e sw h a tk i n d o f c o n s t r a i n t sc a nb ea p p l i e di nm i n i n ga s s o c i a t i o nr u l e s a n dw ed e s i g nt h ed a t am i n i n g s y s t e ma r c h i t e c t u r e 7w ed i s c u s sd a t am i n i n ga p p l i c a t i o ni np o w e rs y s t e m w es t u d yt h e f a s t a l g o r i t h mf o ro p t i m a lp o w e rf l o w c o n s i d e r i n gt h a tt h e r ee x i s tp l e n t i f u lb o u n d a r y c o n s t r a i n t so fr e a c t i v ep o w e ri no p fp r o b l e m s ，w et r e a tt h eg e n e r a li n e q u a l i t y c o n s t r a i n t sa n dt h eb o u n d a r yc o n s t r a i n t ss e p a r a t e l y w ep r e s e n tan e wm e t h o df o r s o l v i n go p t i m a lp o w e rf l o w ( o p f ) 一ap r o j e c t e da s y m p t o t i c a l l ys e m i s m o o t hn e w t o n a l g o r i t h m t h en u m e r i c a le x a m p l e so fs o m es t a n d a r dt e s t e di e e es y s t e m ss h o wt h a t t h en e wa l g o r i t h mh a sn i c ec o n v e r g e n tp e r f o r m a n c ea n dc o m p u t i n ge f f e c t k e yw o r d s ：d a t a b a s e ；d a t am i n i n g ；a s s o c i a t i o nr u l e s ；c l a s s i f i c a t i o n ；c l u s t e r i n g ； a l g o r i t h m 博士学位论文 1 1 数据库技术及其发展 第1 章绪论 1 1 1 数据库技术及其三个发展阶段 数据库技术是研究如何科学地组织和存贮数据，如何高效地检索数据和进行 数据处理的一门学科，它是数据管理的最新技术，是计算机科学的重要分支。数 据模型是数据库系统的核心和基础。数据模型的发展经历了格式化数据模型( 包 括层次数据模型和网状数据模型) 、关系数据模型两个阶段，正在走向面向对象的 数据模型等非传统数据模型的阶段。按照数据模型的进展，数据库技术可以相应 地分为三个发展阶段1 。3 1 。 ( 1 ) 第一代数据库系统。从2 0 世纪5 0 年代中期开始，计算机应用由科学研 究部门扩展到了企业、行政等部门，数据处理很快上升为计算机应用的重要方面， 到6 0 年代，磁盘技术取得了发展，计算机用于管理的规模更加庞大，数据量急剧 增长，为了提高效率，人们提出了数据库的概念。第一代数据库系统指层次和网 状数据库系统，其代表是：1 9 6 9 年i b m 公司研制的层次模型数据库管理系统 i m s ( i n f o r m a t i o nm a n a g e m e n ts y s t e m ) ；美国数据库系统语言协会 c o d a s y l ( c o n f e r e n c e o nd a t a s y s t e ml a n g u a g e l 下属的数据库任务组 d b t g ( d a t ab a s et a s kg r o u p ) 于6 0 年代末7 0 年代初提出的d b t g 报告，所提议 的方法是基于网状结构的，它是网状数据库的典型代表。它们标志着数据管理技 术进入了数据库系统阶段。 支持层次和网状这两种格式化数据模型的数据库系统称为第一代数据库系 统。层次模型数据库是数据库的先驱，而网状模型数据库则是数据库概念、方法、 技术的奠基。两者的区分是以数据模型为基础，它们的结构都可以用图来表示。 层次模型对应于有根定向有序树，而网状模型对应的是有向图。因此，这两种数 据模型可以统称为格式化数据模型。其中层次模型是网状模型的特例。 ( 2 ) 第二代数据库系统。数据库最有意义的成就是关系数据库的发展。1 9 7 0 年i b m 公司s a nj o s e 研究室的研究员e f c o d d 发表了题为“大型共享数据库数 据的关系模型”的论文，提出了数据库的关系模型，开创了数据库关系方法和关 系数据理论研究的新纪元，在其后的1 0 年中，他又发表了一系列文章，奠定了关 系数据库的理论基础。关系数据模型一提出，便立即受到数据库界的重视，但是 也有相当多的人认为天系数据模型仅仅是理想化的模型，尤其担心关系数据库的 数据库中数据挖掘理论方法及戍削圳f 究 性能难以被用户接受。1 9 7 4 年，数据库界开展了一场分别以e f c o d d 和c b a c h m a n 为首的支持和反对关系数据库的大辩论， 辩论促进了关系数据库的发展。2 0 世 纪7 0 年代是关系数据库理论研究和原型开发的时代，其典型代表是i b ms a nj o s e 研究室开发的s y s t e mr 和b e r k e l e y 大学研制的i n g r e s 。它们研究了关系数据语 言，攻克了系统实现中查询优化、并发控制、故障恢复等一系列关键技术，奠定 了关系模型的理论基础，使关系数据库最终从实验室走向社会，成为计算机科学 中的一个重要分支。到了8 0 年代，关系数据库成为发展的主流，随着微机的出现 和计算机网络的广泛应用，分布式处理系统在8 0 年代得到很大的发展，与此相适 应，分布式数据库系统也成为8 0 年代数据库研究的重点，日趋成熟。2 0 世纪8 0 年代是关系数据库的全盛时期。 ( 3 1 第三代数据库系统。从2 0 世纪8 0 年代以来，数据库技术在商业领域的巨 大成功刺激了其它领域对数据库技术需求的迅速增长。这些新的领域一方面为数 据库应用开辟了新的天地，另一方面在应用中提出的一些新的数据管理的需求也 直接推动了数据库技术的研究与发展。新一代数据库技术的研究和发展导致了众 多不同于第一、二代数据库的系统诞生，构成了当今数据库系统的大家族。 1 1 2 数据库的研究领域 数据库学科的研究范围是十分广泛的，概括地讲，包括以下三个领域： 数据库管理系统软件的研制。 数据库设计。 数据库理论。 1 1 3 数据库新技术 数据厍技术自从2 0 世纪6 0 年代产生以来，无论是理论还是应用一直是热门 研究课题。随着计算机的广泛应用，新的应用又提出了新的要求。人们开始发现 关系数据库的许多限制和不足，这又推动了数据库技术新的一轮的研究，其研究 包括三个方面：一是数据模型的发展；二是将数据库技术与其它相关技术相结合： 三是将数据库技术应用到特定的领域中。目前，这三方面都取得了可喜的成果， 出现了下列新的数据库技术卜6 1 。 1 1 3 1 第三代数据模型 1 9 9 0 年高级d b m s 功能委员会发表了“第三代数据库系统宣言”的文章， 提出了第三代d b m s 应具有的三个基本特征【4 _ 5 】：第j 代数据库系统应该支持 数据管理、对象管理和知识管理；第三代数据库系统必须保持或继承第二代数 据库系统的技术；第三代数据库系统必须对其它系统开放。 第三代数据库系统是支持面向对象数据模型的数据库系统。面向对象的数据 博士学位论文 模型吸收了面向对象程序设计方法学的核心概念和基本思想，它是用面向对象观 点来描述现实世界实体( 对象) 的逻辑组织、对象间限制和联系等的模型。 一个数据库系统可称为o o d b s ，必须满足两个条件： 支持一核心的面向对象数据模型； 支持传统数据库系统所有的数据库特征。 面向对象数据库( o o d b ) 的实现一般有两种方式：一种是在面向对象的设 计环境中加入数据库功能，如o r i e n ，c l o s 等：另一种则是对传统数据库系统 进行改进，使其支持面向对象的数据模型，如o r a c l e 8 0 ，i n f o r m i x 9 0 等。 与传统数据模型比较，面向对象数据模型具有下列优势： 具有表示和构造复杂对象的能力。 通过封装和消息隐藏技术提供了程序的模块化机制。 继承和类层次技术提供了软件的重用机制。 通过滞后连编等概念提供系统扩展能力。 然而，面向对象数据库还只是一种新兴的技术，它的发展远不如关系数据库 成熟。它的数据模型并不是建立在完美的数学基础之上，数据库语言缺乏形式化 基础，也不象关系数据库那样有一个统一的标准，它的导航式的计算模式也一直 受到传统数据库学者的批评。因此，面向对象数据库还有待于进一步的研究。但 可以肯定，它是一项具有重大理论意义和应用前景的数据库技术，是第三代数据 库系统的核心概念和技术基础。 1 1 3 2 数据库技术与其他相关技术相结合 数据库技术与其他学科相结合，是新一代数据库技术的一个显著特征，在结 合中涌现出各种新型的数据库，例如：数据库技术与分布处理技术相结合，出现 了分布数据库；数据库技术与并行处理技术相结合，出现了并行数据库：数据库 技术与人工智能相结合，出现了演绎数据库、知识库和主动数据库等等i l 。j 。 1 1 3 3 面向应用领域的数据库新技术 由于传统数据库系统的局限性，无法直接使用当前市场上销售的通用d b m s 来管理和处理某些领域内的数据对象，因而广大数据库工作者针对各个领域的数 据库特征探索和研制了各种特定的数据库系统。比如，工程数据库、统计数据库、 空间数据库、科学数据库、地理数据库、数据仓库、w e b 数据库等【“1 “。 1 2 数据挖掘的有关概念 1 2 1 数据挖掘的诞生 随着人们认识和管理水平的提高，对客观世界的描述愈来愈伞面，存储的数 数据库中数据挖掘理论方法及应用研究 据量愈来愈大。此外，相当数量的数据具有很强的时效性，数据的价值随着时间 的推移而迅速降低。 数据收集与维护的最终目的是供人们使用。简单的数据查询或统汁虽然可以 满足某些低层次的需要，但人们更为需要的是从大量数据资源中挖掘出对各类决 策有指导意义的一般知识，这些知识是对大量数据的高度概括和抽象。 大量的数据未能充分利用这一现象常常被描述为“数据丰富，但信息贫乏”。 数据的急剧增长和时效性、复杂性远远超出了人们的手工处理能力，迫切需要高 性能的数据分析工具来高速、全面、深入、有效地处理数据。数据挖掘技术正是 为满足上述要求而产生的。 数据挖掘( d a t am i n i n g ，简称d m ) 一词是在1 9 8 9 年8 月于美国底特律市召 开的第十一界国际联合人工智能学术会议上正式形成的，常常与k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 混用 “。从1 9 9 5 年开始，每年主办一次k d d 国际学术 会议，将k d d 和d m 方面的研究推向了高潮，从此，“数据挖掘”一词开始流行。 在中文文献中，d m 有时还被翻译为“数据采掘”、“数据开采”、“数据发掘”等。 还有很多和这一术语相近的术语，如数据库中知识发现，数据分析，知识抽取， 模式分析，数据采集，商业智能，数据融合，决策支持等。 1 2 2 什么是数据挖掘 数据挖掘是数据库技术、人工智能、机器学习和统计学等学科相结合的产物 7 - 1 1 】。简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。数据挖掘有广 义和狭义之分，广义的数据挖掘是指从数据库的大量数据中揭示出隐含的、先前 末知的、潜在有用的信息的非平凡过程，它是由g p i a t e t s k y s h a p i o r ，w j f r a w l e y 等人提出的。狭义的数据挖掘则把数据挖掘作为k d d 的一个基本步骤。数据库 中知识发现的过程如图1 1 所示，它由下列步骤组成。 图1 1k d d 过程 数据清理：消除噪声或不一致数据。 数据集成：将多种数据库中的数据组合在一起。 数据选择：从数据库中检索与分析任务相关的数据。 数据变换：将数据变换或统一成适合挖掘的形式。比如，通过汇总等操作。 数据挖掘：它是基本步骤，使用智能方法提取数据模式。 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 博士学位论文 从上述步骤可以看出，数据挖掘只是整个过程中的一个步骤。然而，在大多 数场合，人们采用广义的数据挖掘观点，即把数据挖掘与k d d 视为同义词。 基于广义的数据挖掘观点，典型的数据挖掘系统具有以下主要成分，如图1 2 所示。 清理 图1 2 典型的数据挖掘系统结构 数据库、数据仓库或其它信息库：这是一个或一组数据库、数据仓库、电 子表格或其它类型的信息库，可以对其进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，服务器负责提取相 关数据。 知识库：领域知识用于指导搜索，或评估结果模式的兴趣度。 数据挖掘引擎：它是数据挖掘系统的基本部分，由一组数据挖掘模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，它使用兴趣度度量，并与数据挖掘模块交互，以便 将搜索聚焦在有趣的模式上。 图形用户界面：此模块在用户和数据挖掘系统之间通信，允许用户与系统 交互，指定数据挖掘查询，提供提示信息，帮助搜索聚焦。此外，它允许用户浏 览数据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式可 视化。 数据挖掘从一开始就是面向应用的。它不仅仅是面向特定数据库的简单检索 查询，而且要对这些数据进行微观或宏观的统计、分析、综合和推理，以指导实 际问题的求解，甚至利用各种数据分析工具在数据中发现模式和数据问的关系， 对未来的活动进行预测。 数据挖掘得到的知识会告诉人们“怎样做”，而不会告诉人们“为什么这样做”， 数据厍中数据挖掘理论方法及应用研究 至于“为什么这样做”需要人们去思考。 需要指出的是，数据挖掘所发现的知识不要求是放之四海而皆准的真理。它 所发现的知识是相对的，有特定前提和约束条件的，面向特定领域的，同时还要 求易于被用户理解。 1 2 3 数据挖掘的对象 原则上讲，数据挖掘可以在任何类型的信息存储上进行，包括关系数据库、 事务数据库、数据仓库、高级数据库系统和面向特殊应用的数据库系统( 如：面 向对象数据库、对象关系数据库、空问数据库、时间数据库、时间序列数据库、 文本数据库、多媒体数据库、w w w 等) 。 1 2 4 数据挖掘系统的分类 数据挖掘是一个交叉学科领域，受多个学科的影响。因此，产生了许多不同 类型的数据挖掘系统，根据不同的标准可以分类如下【7 1 ： 根据挖掘的数据库类型分类。由于数据库系统本身可以根据不同的标准分 类，因此，数据挖掘系统可以相应分类。如果根据数据模型分类，可以分为关系 的、事务的、面向对象的、对象关系的或数据仓库的数据挖掘系统；如果根据所 处理数据的特定类型分类，可以分为空间的、时间序列的、文本的、多媒体的或 w w w 的数据挖掘系统。 根据挖掘的知识类型分类。知识的类型包括特征化、区分、关联、分类、 聚类、孤立点分析、演变分析、偏差分析或类似性分析等。一个完整的数据挖掘 系统应当提供多种和集成的数据挖掘功能。 此外，数据挖掘系统可以根据所挖掘的知识的粒度或抽象层来进行分类。包 括概化知识( 在高抽象层) 、原始层知识( 在原始数据层) 或多层知识，一个高级 的数据挖掘系统应当支持多层的知识发现。 根据所用的技术分类。这些技术可以根据用户交互程度( 例如自动系统、 交互查询系统、查询驱动系统) ，或所用的数据分析方法( 例如面向数据库或数据 仓库的技术、机器学习、统计学、可视化、模式识别、神经网络、模糊集、粗糙 集、遗传算法、决策树、最近邻技术等) 描述。复杂的数据挖掘系统通常采用多 种数据挖掘技术。 根据应用分类。小同的应用通常需要集成对于该应用特别有效的方法。比 如，金融、电信、d n a 、股票市场等等。通用的数据挖掘系统可能并不适合特定 领域的挖掘任务。 1 3 数据挖掘技术和方法 博士学位论文 数据挖掘的方法大部分来自于机器学习、人工智能、统计学等领域，他们分 别从不同的角度进行数据挖掘，大致可分为下列几种【7 叫： 1 3 1 统计方法 统计方法是从事物外在数量上的表现去推断该事物可能的规律性。通常是先 通过统计从其数量表现上分析出一些线索，然后提出一定的假说或学说，再作进 一步深入的理论研究。当理论研究得出一些结论时，往往还需要在实践中加以验 证。统计方法的优点是精确、易理解，并且已广泛使用。其缺点是很难有效使用。 统计方法主要考虑预想的假设是否与数据模型拟合。它依赖于显式的基本概 率模型。统计方法处理过程可以分为三个阶段：搜集数据阶段；分析数据阶 段：进行推理阶段。 常见的统计方法有回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、 费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类) 以及探索性分析 ( 主元分析法、相关分析法等) 。目前流行的统计软件有s a s ( s t a t i s t i c s a n a l y s i s s y s t e m ) 和s p s s ( s t a t i s t i c a lp a c k a g ef o rt h es o c i a ls c i e n c e ) 等，其中美国的s a s 软件以其强大的数据管理能力，全面的统计方法、高精度的计算和独特的多平台 自适应技术被国内外许多学者誉为最权威的统计软件包。 1 3 2 模糊集 模糊集是表示和处理不确定性数据的重要方法。模糊集不仅可以处理不完全 数据、噪声或不精确数据，而且在开发数据的不确定性模型方面是很有用的，它 能提供比传统方法更灵巧、更平滑的性能。 1 3 3 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 建立在计算学习理论的结构风险 最小化原则之上。其主要思想是针对两类分类问题，在高维空间中寻找一个超平 面作为两类的分割，以保证最小的分类错误率。支持向量机的个重要优点是可 以处理线性不可分的情况。 1 3 4 粗糙集 粗糙集( r o u g hs e t ) 理论由波兰数学家z p a w l a k 在1 9 8 2 年提出。它是一种 新的处理模糊和不确定信息的数学工具，在数据挖掘中发挥着重要作用。粗糙集 是由集合的下近似、上近似来定义的。下近似中的每一个成员都是该集合的确定 成员，不是上近似中的成员肯定不是该集合的成员。粗糙集的上近似包含下近似 和边界区域。边界区域的成员可能是该集合的成员，但不是确定的成员。可以认 为粗糙集是具有三值隶属函数的模糊集即：是、不是、也许。与模糊集一样， 数据序中数据挖掘理论方法及应州研究 它是一种处理数据不确定性的数学工具，常与规则归纳、分类和聚类方法结合使 用，很少单独使用。 1 3 5 规则归纳 规则归纳反映数据项中某些属性或数据集合中某些数据项之间的统计相关 性。a o 算法是著名的规则归纳算法。利用覆盖所有正例、排斥所有反例的思想 来寻找规则，比较典型的有r s m i c h a l s k i 提出的a q l l 方法和洪家荣改进的a q l 5 方法等。 1 3 6 决策树 决策树的每一个非终节点表示所考虑的字段的测试或决策。一个确定分枝的 选择取决于测试的结果。它利用信息论中的信息增益寻找数据库中具有最大信息 量的字段，建立决策树的一个节点，再根据字段的不同取值建立树的分支；在每 个分支子集中重复建树的下层节点和分支，即可建立决策树。国际上最有影响和 最早的决策树方法是由j r q u i n l a n 研制的i d 3 方法，后人又发展了多种决策树方 法。 决策树方法的最大优点是直观。其缺点是随着数据复杂性的提高，分支数将 增加，管理的难度越来越大。此外，该方法也存在数据的缺值处理问题。 1 3 7 范例推理 范例推理是直接使用过去的经验或解法来求解给定的问题。范例常常是一种 已经遇到过并且有解法的具体问题。当给定一个特定问题，范例推理就检索范例 库，寻找相似的范例。如果存在相似的范例，它们的解法就可以用来求解新的问 题。目前，将范例推理与最近邻原理( n e a r e s tn e i g h b o r ) 、格子机( 1 a t t i c em a c h i n e ) 相结合是一种发展趋势。 1 3 8 贝叶斯信念网络 贝叶斯信念网络用概率分布图表示。它是一种直接的、非循环的图，节点表 示属性变量，边表示属性变量之间的概率依赖关系。与每个节点相关的是条件概 率分布，用于描述该节点与它的父节点之间的关系。 贝叶斯信念网络的优点是易于理解，预测效果好。也就是说，它同时具有决 策树和神经网络的优点。其缺点是，在真讵的概率网络中，发生频率很低的结果 的概率也非常小，这使得它倾向于发生频率高的结果。 1 3 9 公式发现 公式发现就是在实验环境下发现科学定理。在工程和科学数据库中，对著干 数据项( 变量) 进行一定的数学运算，求得相应的数学公式。比较典型的b a c o n 博士学位论文 发现系统完成了对物理学中大数定理的重新发现。 1 3 1 0 遗传算法 遗传算法是按照自然进化原理提出的一种优化策略。它是模拟生物进化过程 的算法，由三个基本算子组成：繁殖( 选择) 是从一个旧种群( 父代) 选出生 命力强的个体，产生新种群( 后代) 的过程；交叉( 重组) 选择两个不同个体 ( 染色体) 的部分( 基因) 进行交换，形成新个体；变异( 突变) 对某些个体 的某些基因进行变异。这种遗传算法可起到产生优良后代的作用。这些后代需满 足适应值，经过若干代的遗传，将得到满足要求的后代( 问题的解) 。在求解过程 中，通过最优解的选择和彼此组合，则可以期望解的集合将会越来越好。遗传算 法已在优化计算和机器学习等方面发挥了显著作用。 遗传算法擅长于数据聚类，能够解决其它技术难以解决的问题。然而，它是 一种难于理解的方法。遗传算法通常与神经网络结合起来使用，以在较高的层次 上提高模型的可理解性。 1 3 1 1 神经网络 神经网络是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模 型。这种计算模型的特点是，利用大量的简单计算单元( 即神经元) 连成网络， 来实现大规模并行计算。神经网络的工作原理是通过学习来改变神经元之间的连 接强度。 神经网络以m p 模型和h e b b 学习规则为基础，建立了三大类( 前馈式网络、 反馈式网络和白组织网络) 多种神经网络模型。神经网络的知识体现在网络连接 的权值上，是一种分布式矩阵结构。神经网络的学习体现在神经网络的权值的逐 步计算上( 包括反复叠代或累加计算) 。 神经网络的最大优点是它能对复杂问题进行精确的预测。但也存在下列不足： 神经网络难于理解：神经网络易受训练过度的影响；神经网络的训练时间 较长。 1 3 1 2 可视化 可视化( v i s u a l i z a t i o n ) 就是把数据、信息和知识转化为可视的表示形式的过 程。可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清晰。 可视化技术为人类与计算机之间提供了一个接口。快速图形处理器和高分辨率彩 色显示器的发展进一步提高了人们对信息可视化的兴趣和信心。 随着i n t e r n e t 的爆炸式成长，商业和政府机构的普遍计算机化，以及数据仓 库的发展，使得可视化技术成为众多商业和信息技术领域的基本工具。可视化技 术帮助人们发现信息中的模式、聚类、趋势、区别，联系等等。 数据厍中数据挖掘理论方法及应用珂 i 1 4 数据挖掘发现的知识类型 数据挖掘任务一般可以分为两大类：描述和预测。描述类挖掘刻划数据库中 数据的一般特性。预测类挖掘在当前数据上进行推断，以进行预测。数据挖掘可 以发现的知识类型如下1 7 。9 】： 1 4 1 概念类描述：特征化和区分 概念或类的描述称为概念类描述，它可以通过下列方法实现。 数据特征化。 数据区分。 数据特征化是目标类数据的一般特征或特性的汇总。比如，为研究上一年销 售增加1 0 的软件产品的特征，可以通过执行一条s q l 查询收集关于这些产品的 数据。数据特征化的输出可以用多种形式提供，包括饼图、条图、曲线、多维数 据立方体、含交叉表的多维表。结果描述也可以用概化关系或规则形式提供。 数据区分是将目标类对象的一般特性与一个或多个对比类对象的般特性比 较。比如，用户可能希望将上一年销售增加1 0 的产品与同期销