（计算机应用技术专业论文）事务间量化关联规则挖掘的研究及应用.pdf

硕士学位论文 m a s l l e r s 1 _ l i e s i s 摘要 世界进入信息时代，在各个领域存在大量数据，人们迫切需要将它们转换 成有用的信息和知识，以应用于商务管理、生产控制和预测等方面。数据挖掘 和知识发现作为从海量数据中提取信息的一种技术，已经成为当前一个具有重 要理论和应用价值的研究课题，在国际学术界引起了广泛关注。本文在充分分 析数据挖掘的基木特点和相关技术的基础上，探讨了事务问量化关联规则挖掘 的理论及其在预测中的应用。 本文首先介绍了国内外关于知识发现和数据挖掘的最新发展动态、数据挖 掘的基本概念和一般处理流程。通过对事务间关联规则理论的分析，发现其适 用对象仪仪为分类属性，因而有所限制，基于原来的事务间关联规则概念和算 法，我们提出了事务阃量化关联规则的概念及挖掘算法，从而将分类属性和量 化属性统一到了一起，扩展了它们的应用范围；然后引入了部分完全性度量和 分箱技术对属性进行动态离散化，在保证信息丢失最小化的前提下，有效地压 缩了算法的搜索空间，对于算法搜索产生的海量规则，采用基于特化的r 兴 趣度度量来剔除冗余规则；再者，因为数据挖掘木质上是一种数据分析技术， 单纯的数据挖掘技术缺少用户的参与，因而不能得到他们的期望结果，据此我 们引入多维数据分析的o l a p 技术，将它与关联规则挖掘技术紧密地集成在一 起，形成了一个对用户友好的、交互式的数据挖掘环境。最后，我们将上述理 论应用到武汉市空气质量预测系统o r p h e u s 中，取得了较好的效果。 本文的主要研究成果如下： 1 ) 深入研究了事务间关联规则挖掘的理论和方法，对它作进一步的扩充， 提出了事务间量化关联规则的概念。 2 ) 提出了事务问量化关联规则的挖掘算法。 3 ) 引入了数据仓库的概念和o l a p 技术，以它们作为基础，结合关联规 则挖掘算法，形成了o l a m 的系统结构，并在空气质量预测系统中初 步地实现。 4 ) 设计了基于关联规则挖掘模型和o l a m 结构的预测系统框架，该框架 的核，小是o l a m 引擎，它实现了一种从数据建模一预测结果一再调整 硕士学位论文 m a s f e r s t i l e s i s 模型的自反馈过程，对于数据挖掘方法在预测领域的应用有着启发性 的意义。 关键词：数据挖掘；事务闻量化关联规则；数据仓库：联机分析挖掘。 硕士学位论文 a b s t r a c t t h ew o r l dh a se n t e r e dt h ee r ao fi n f o r m a t i o n ，t h e r ea r eag r e a td e a lo fd a t ai na l l s o r t so ff i e l d s i ti sv e r yu r g e n tf o rp e o p l et ot r a n s f o r mt h e mi n t ou s e f u li n f o r m a t i o n a n dk n o w l e d g e ，a n da p p l yt h e mi nb u s i n e s sa d m i n i s t r a t i o n ，p r o d u c t i o nc o n t r o la n d f o r e c a s t i n g ，e t c a sak i n do ft e c h n o l o g yf o re x t r a c t i n gi n f o r m a t i o nf r o ml a r g e q u a n t i t yo fd a t a ，d a t am i n i n ga n dk n o w l e d g ed i s c o v e r yh a sb e c o m eas i g n i f i c a n t r e s e a r c hp r o b l e mw h i c hh a si m p o r t a n tt h e o r e t i c a la n dp r a c t i c a lv a l u e s ，a n da t t r a c t s w i d e l y a t t e n t i o ni ni n t e r n a t i o n a l a c a d e m e u p o ni n v e s t i g a t i n g i n t ot h er e s e a r c h a c h i e v e m e n t sa n dd i s a d v a n t a g e so f e x i s t i n gi nk n o w l e d g ed i s c o v e r yi nd a t a b a s ea n d i nd a t am i n i n g ，t h i st h e s i sa d v a n c e dt h er e s e a r c ha n da p p l i c a t i o no fm i n i n gt h e i n t e r t r a n s a c t i o n a lq u a n t i t a t i v ea s s o c i a t i o nr u l e s f i r s to fa l lw ei n t r o d u c e dt h eu p - t o - d a t e d e v e l o p i n gt r e n d so fd o m e s t i ca n d a b r o a d r e g a r d i n gk n o w l e d g e a n dd a t a m i n i n g ，b a s i cc o n c e p t s a n d g e n e r a l p r o c e s s i n go fd a t am i n i n g t h r o u g ht h ea n a l y s i so fi n t e r t r a n s a c t i o n a la s s o c i a t i o n r u l e s ，w ef i n d i tc a no n l ya p p l yt o c a t e g o r i c a la t t r i b u t e s ，t h u s i t s a p p l i c a t i o ni s l i m i t e d ，t h e nw ep r o p o s e dt h ec o n c e p to f i n t e r t r a n s a c t i o n a lq u a n t i t a t i v ea s s o c i a t i o n r u l e sa n dc o r r e s p o n d i n gm i n i n ga l g o r i t h m ，t h u su n i t e dc a t e g o r i c a la n dq u a n t i t a t i v e a t t r i b u t e sa n dg r e a t l ye x p a n d e dt h e i ra p p l i c a t i o nr a n g e a f i e r w a r dw ei n t r o d u c e p a r t i a l c o m p l e t e n e s s m e a s u r ea n d b o x d i v i d i n gt e c h n o l o g y t o d y n a m i c a l l y d i s c r e t i z et h ea t t r i b u t e s t h e ya r ec a p a b l eo fe f f i c i e n t l yr e d u c et h es e a r c hs p a c eo f a l g o r i t h m i nt h ep r e c o n d i t i o no fm i n i m u ml o s ti n f o r m a t i o n f o rt h el a r g eq u a n t i t yo f r e s u l tr u l e s ，w ea d o p tt h er i n t e r e s tm e a s u r et oc u tt h o s eu s e l e s so n e s s i n c ed a t a m i n i n gi se s s e n t i a l l yak i n do f d a t aa n a l y s i st e c h n o l o g y , p u r ed a t am i n i n gp e r h a p s w i l ln o tp r o d u c eu s e r - e x p e c t e dr e s u l t s t h e r e b yw ei n t r o d u c em u l t i d i m e n s i o n a l d a t a o r i e n t e do l a pt e c h n o l o g y , a n dc l o s e l yi n t e g r a t et h e mi n t oau s e rf r i e n d l y , i n t e r a c t i v ed a t am i n i n ge n v i r o n m e n t f i n a l l yt h et h e o r yi sa p p l i e di n t ot h ed e s i g no f w u h a nc i t ya i rq u a l i t yf o r e c a s t i n gs y s t e m - o r p h e u s t h em a i nr e s e a r c hf r u i t sa r ea sf o l l o w i n g ： nt h et h e o r ya n dm e t h o d so fi n t e r t r a n s a c t i o n a la s s o c i a t i o nr u l e sa r es t u d i e d i n t e n s i v e l y , t h ec o n c e p to f i n t e r - t r a n s a c t i o n a lq u a n t i t a t i v ea s s o c i a t i o nr u l e s a r e p r o p o s e dt h r o u g he x p a n d i n go r i g i n a lc o n c e p t s 2 ) t h e a l g o r i t h mo f m i n i n g i n t e r t r a n s a c t i o n a lq u a n t i t a t i v ea s s o c i a t i o nr u l e si s p r o p o s e 硕士学位论文 m a s f e r s 1 i l e s i s 3 ) t h ec o n c e p to f d a t aw a r e h o u s ea n do l a p t e c h n o l o g ya r ei n t r o d u c e d ，a n d t h e s y s t e ms t r u c t u r eo fo l a m i sb u i l to no l a pa n da s s o c i a t i o nr u l e s m i n i n ga l g o r i t h m s ，a n d t h e s y s t e m i s i m p l e m e n t e d i na i r q u a l i t y f o r e c a s t i n gs y s t e m ， 4 ) t h ef r a m e w o r ko ff o r e c a s t i n gs y s t e mi sd e s i g n e db a s e do na s s o c i a t i o n m i n i n ga l g o r i t h m sa n do l a ms t r u c t u r e ，t h ec o r eo fw h i c hi st h eo l a m e n g i n e i ti m p l e m e n t e daa u t o f e e d b a c kp r o c e s sf r o md a t am o d e l i n gt o f o r e c a s t i n g r e s u l t st o a d j u s t t h em o d e l t h e r e f o r ei ti so fi l l u m i n a t i v e s i g n i f i c a n c ef o rd a t am i n i n g i nf o r e c a s t i n gf i e l d k e yw o r d s ：d a t am i n i n g ，i n t e r - t r a n s a c t i o n a lq u a n t i t a t i v e a s s o c i a t i o nr u l e s ，d a t a w a r e h o u s e ，o n l i n ea n a l y t i c a lm i n i n g ( o l a m ) 硕士学位论文 m a s 1c r si i i e s i s 第一章引言 1 1 课题背景和意义 在过去的二十多年，由于数据收集设备曰益广泛的使用，信息或以电子格 式存储的数据已有迅猛的增长，据估计，全世界的信息每过2 0 个月便增加一 倍，同时数据库的规模和数量也在以更快的速度增长。计算机的处理能力越来 越强大，存储的容量在增大，它们的成本却在下降，这使得数据的收集和存储 变得越来越容易，数据也变得越来越“便宜”。数据库界在对数据的收集做出 了大量的工作以后，一个问题很自然地提了出来：如何处理这些数据资源? 虽 然人们认识到信息是商业运作的核心，决策者能够利用存储的数据来对商业做 出有价值的洞察。尽管数据库管理系统( d b m s ) 可以提供数据访问的功能，然 而，在我们能够从数据获得的信息中，这些信息只占很小的一部分，换句话说， 这些操作提供的仪仪是数据库信息的外延。传统的联机交易处理( o n 1 j 1 e t r a n s a c t i o f lp r o c e s s i n g ) 系统可以迅速、安全、有效地将数据存入数据库， 但是不能对数据进行有意义的分析。在商务决策、工程项目和科学研究中，理 解海量的数据却远远超出了人们的能力，重要的决定不能基于数据库中丰富的 数据，而仍然依靠决策者的直觉，由此带来了对强力数据分析工具的需求。由 于分析数据能够提供关于商业的更深层次的知识，数据挖掘( d a t am i n i n g ) ， 或者数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 作为种新 的数据分析技术被研究者提了出来。 关于数据挖掘，有各种各样的定义，w “l i a mjf r a w l e y ，g r e g o r y ， p i a t e t s k ys h a p i r o 等人在他们1 9 9 1 年的论文中对数据挖掘给出的定义是： “数据挖掘是指从数据中非平儿地抽取隐含的、事先未知的、潜在有用的信息 的过程。它包括使用许多不同的方法及技术，如聚类、数据汇兑、分类规则学 习和异常发现等等。”本质上讲，数据挖掘集中于对数据的分析和软件技术的 使用，以期找到数据集的模式或规则，它的分析过程是从个数据集开始，使 用一种方法来发展数据结构的最优表示，在此过程中就获得了知识，一旦获得 知识，可以把此过程扩展至更大的数据集上，它的原理是假设较大的数据集与 l b 雅l a s t e 讹r s t 淑 i e s ! 。 样本数据集具有相似的结构。 如果合适的数据被收集并存储在一个数据仓库里，数据挖掘的潜力可以进 一步提高。数据仓库是一个为事务处理系统需要而特别设计的关系数据库 ( r d b m s ) 。 它可以粗略地定义为一个集中的数据贮藏库( d a t ar e p o s i t o r y ) ， 可以根据决策需要对它进行查询( 详见第四章) 。数据仓库也是一种新的、强 有力的技术，它的出现使得抽取存档的操作型数据变为可能，并且可以克服因 不同的数据格式导致的不一致性问题，以及将整个企业的全部数据集成在一 起，无论它们的位置，格式者通讯需求，甚至还可以与附加信息与专家知识合 并在一起，换句话说，数据仓库提供了经过清理、转换与集成的数据，因此为 更高效的决策支持系统( d s s ) 应用程序提供了一个合适的环境。数据仓库还 提供了o l a p ( 联机分析处理) 工具，根据n i g e lp e n d s e 的定义0 1 ，“o l a p 是 对共享的多维信息( 数据) 的快速分析。”利用切片、切块、旋转和钻取等o l a p 操作，可以对复杂的多维数据进行快速的分析，进而发现数据之间的关联。随 着研究人员丌始将o l a p 技术与d m 技术结合到一起，数据挖掘研究进入了一个 新的阶段一联机分析挖掘( o l a m ) 。3 ，o l a m 技术支持交互式的数据分析，即它 允许用户与系统交互，进行探测式的数据挖掘。 数据挖掘是个融合数据库、机器学习、数理统计、可视化和信息科学技 术为一体的新兴的交叉学科领域。它的发展不仪可以为商务管理、科学研究、 查询优化、过程控制等领域提供决策支持，而且为相关的计算机学科注入新的 活力，从而推进计算机科学向纵深方向发展“1 。一份最近的g a r t n e r 报告中列 举了在今后5 1 0 年内对工业将产生重要影响的五项关键技术，其中k d d 和 人工智能排名第一。同时，这份报告将并行计算机体系结构研究和k d d 列入 今后5 年内公司应该投资的1 0 个新技术领域。毫无疑问，对数据挖掘的深入 研究在计算机理论和应用两个方面都具有十分重大的意义。 硕士学位论文 m a s f r s 川l s i s 1 2 k d d b 勺研究现状和发展方向 12 1k d d 与数据库技术 数据挖掘是人们长期对数据库技术进行研究和开发的结果，数据库技术的 发展经历了四个阶段”：2 0 世纪6 0 年代，数据库和信息技术系统地从原始的 文件处理演化到复杂的、功能强大的数据库系统，数据收集、数据库创建技术 曰趋成熟；自8 0 年代以来，关系数据模型在数据库界被广泛接受，关系数据 库系统得到进一步的改进，同时其它一些数据模型，如扩充关系模型、面向对 象模型、对象一关系模型和演绎模型也陆续被提出来，并且由i b m 实验室发 明了结构化查询语言s q l ；自9 0 年代以来，数据库技术的特点是多维数据库、 数据仓库和联机分析处理的出现，它可以在各层之间提供回溯的动态历史数 据：9 0 年代后期开始对海量数据的处理及预测性信息的需求使得数据库技术的 研究进入数据挖掘的阶段。 12 2k d d 研究现状 在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上，研究者首次 提出k d d 的概念，随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨论会更名为国际会议，在加拿大的蒙特利尔市召开 了第一届k d d 国际学术会议，以后每年召开一次。迄今为止，由美国人工智 能协会( a i i i ) 主办的k d d 国际研讨会已经召开了7 次，人数由最初的二三十 人发展到七八百人，论文收录比例从2 ：1 变为6 ：l ，研究重点也逐渐从发现方 法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的 相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为 当前计算机科学界的最活跃的研究领域之一。 在学术出版界，数据库、人工智能、信息处理、知识工程等领域的国际学 术刊物纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n d d a t ae n g i n e e r i n g 硕士学位论文 m a sf e r s t l e q i s 会刊领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k o d 研究的最新成果和动念，较全面地论述了k d 9 系统方法论、发现结果的评价、 k d d 系统设计的逻辑方法，集中讨论了数据库的动态性冗余、高噪声和不确定 性、空值等问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、 数理统计分析系统的联系和区别，以及相应的基本对策。 近年来，k d d 在研究和应用方面都十分发展迅速，尤其是在商业和银行领 域的应用比研究的发展速度还要快。 目前，国外数据挖掘的研究方面主要有：对知识发现方法的研究进一步发 展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高： 传统的统计学回归法在k d d 中的应用：k d d 与数据库的紧密结合。在应用方 面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统， 而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。 国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应 的研究中心进行这方面的工作，此外，一些公司的相关软件也开始在国内销售， 如p l a t i n u m 、b o 以及i b m 。当前，世界上比较有影响的典型数据挖掘系统有 c o v e rs t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d bh i n e t 、q u e s t 等。 与国外相比，国内对d m k d ( d m 和k d d 的合称) 的研究稍晚，没有形成整 体力量。但是，目前国内的许多科研单位和高等院校正在竞相开展知识发现的 基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空 军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法 在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代 数的研究，复旦大学、浙江大学、中国科技大学、中科院数学研究所、华中科 技大学等单位_ 丌展了对关联规则挖掘算法的优化和改造；南京大学、四川联合 大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数 据挖掘，并且涌现出一批优秀的研究成果。 硕士学位论文 m a s i e r s t i f i i s i s 1 23 发展方向 当前，数据挖掘研究j 下方兴未艾，预计在2 l 世纪还会形成更大的高潮，研 究焦点可能会集中到以下几个方面：研究专门用于知识发现的数据挖掘语言， 也许会像s o l 语言一样走向形式化和标准化；寻求数据挖掘过程中的可视化方 法，使得知识发现的过程能够被用户理解，也便于在知识发现过程中的人机交 互：研究在网络环境下的数据挖掘技术，特别是在i n t e r n e t 上建立d m k d 服务 器，与数据库服务器配合，实现数据挖掘；加强对各种非结构化数据的挖掘，如 文木数据、图形图像数据、多媒体数据。但是，无论怎样，市场需求是最大的 驱动力，d m k d 将首先满足信息时代用户的急需，大量基于d m k d 的决策支持软件 工具产品将会问世。 1 3 课题来源及内容组织 本课题来源于湖北省自然科学基金项目“智能信息不确定性处理的新方法” ( 项目号：j 9 8 0 7 6 ) ，研究内容包括数据挖掘理论和研制一个应用系统，其目 标是为武汉市环境监测中心建立一个智能化的空气质量预测系统，功能是对各 监测站的气象数据和污染物进行分析，综合运用各种数据挖掘技术和算法建立 一个挖掘模型，利用它找出隐藏在污染物数据和气象数据之间的联系规律，即 所谓的关联规则，然后根据规则来对短期内的空气质量做出预报。 引言首先介绍了国际上和国内的数据挖掘研究的最新动态。第二章描述了 数据挖掘的基本概念、功能、研究的主要问题、数据挖掘系统的体系结构及处 理流程。第三章在事务间关联规则和量化规则的基础上，提出了事务间量化关 联规则的概念和算法。第四章介绍数据仓库、o l a p 及联机分析挖掘的理论，描 述了相关的技术，并给出了一个完整的o l a m 结构图。第五章将我们提出的关 联规则挖掘算法及o l a p 技术应用于空气质量预测系统o r p h e u s ，给出了预测结 果。最后一章总结了全文的工作，并对未来的研究做出建议和展望。 m 砒a s t e 张r s t 做ii e s i 。 第二章d a t a m i n i n g 概述 数据挖掘( d a t am i n i n g ) ，指的是从大量、部分、模糊、随机的实际应用数 据中，提取隐含其中、人们事先不知道、但又有用的信息，同时用能被人理解 的模式进行高级处理的过程“1 。它是数据库中知识发现( k n o w l e d g ed i s c o v e r d a t a b a s e ，k d d ) 的核心部分。 2 1 数据挖掘的功能 一般况来，数据挖掘主要可以完成五类功能”1 ：概念类描述、关联分析、 分类和预测、离群挖掘和演变分析。 2 1 1 概念类描述 概念是思维的基本形式之一，反映客观事物的一般的、本质的特征，概念 描述( c o n c e p td e s c r i p t i o n ) 的目的是产生代表概念的数据的特征化和比较 描述，而并非对数据的简单枚举。概念描述也称为类描述( c l a s sd e s c r i p t i o n ) ， 特征化( c h a r a c t e r i z a t i o n ) 提供给定数据汇集的简洁汇总，而概念类的比 较( c o m p a r i s o n ) 提供两个或多个数据的比较拙述。 2 1 2 关联分析 关联分析发现关联规则，形式上讲，关联规则( a s s o c i a t i o nr u l e ) 是形 如j y ，即 a 。i a a 。jb l a 只 的规则，其中 a 。( f l ，m ) ，b ，( ， l ，h ) ) 是属性一值对。关联规则可解释为“满足x 中 条件的数据库多半也满足y 中条件”。 根据不同的标准，关联规则可以分为以下种类： 1 ) 按照规则中所处理的值类型：如果规则考虑的是项的存在与否，则它是布 6 m a s t e r 雠s t ii e 文s i 。 尔关联规则( b o o l e a na s s o c i a t i o nr u e ) 。例如，以下规则： c o m p u t e rjp r i n t e r ( s u p p o r t = 2 ) 意味着销售数据库中的全部顾客中有 2 的人同时购买计算机和打印机，它就是布尔关联规则。如果规则描述的 是量化的项或属性之间的关联，则它是量化关联规则( q u a n t i t a t i v e a s s o c i a t i o n r u l e ) 。在这种规则中，属性的值划分为区间，例如。 a g e ( x , 3 0 3 9 ) i n c o m e x , 4 3 k 一4 8 k ) jb u y s ( x , f i n a n c i a _ s o f t w a r e ”) 就是 量化规则的例子 2 ) 按照数据的维数：如果关联规则中的项或属性每个只涉及一个维，则是单 维关联规则( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) 。如果规则涉及两 个或多个维，如维b u y s ，t i m e o f t r a n s a c t i o n ，则它称为多维关联规则 3 ) 按照规则集的抽象层次：可以在不同的抽象层面表达关联规则，例如挖掘 的关联规则集包含以下规则： a g e ( x , 3 0 3 9 ) b u y s ( x , l a p m p c o m p u t e r ”) a g e ( x , 3 0 3 9 ) ；b u y s ( x , c o m p u t e r ”) 在以上规则中，购买的商品涉及不同的抽象层( 即“c o m p u t e r ”在比 “l a p t o pc o m p u t e r ”更高的抽象层) 。称所挖掘的规则集由多层关联规则 ( m u l t i l e v e la s s o c i a t i o nr u l e ) 组成。如果规则不涉及不同抽象层的项 或属性，则该集合包含单层关联规则( s i n g l e l e v e la s s o c i a t i o nr u l e ) 。 213 分类和预测 数据分类( d a t ac l a s s i f i c a t i o n ) 找出描述并区分数据类或概念的模型， 以便能够使用模型预测类标记未知的对象类。预测( p r e d i c t i o n ) 是构造和使用 模型评估无标号样本类，或评估给定样本可能具有的属性值或值区间。 预测和分类的不同点在于，用预测法预测类标号为分类，用预测法预测连 7 硕士学位论文 n 1 a s e r s | f i f e s i s 续值( 例如用回归分析法) 为预测，这是在数据挖掘界被广泛接受的观点。 2 1 4 离群挖掘 数据库中有可能包含一些数据对象，它们与数据的一般行为或模型不一致。 这些数据对象被称为离群数据( o u t l i e r ) 。大部分数据挖掘方法将它视为噪声 或异常而丢弃。然而，在某些应用中( 如欺骗检测) ，罕见的事件可能比j 下常 出现的事件更有意义。 离群数据可以使用统计试验检测。事先假定一个概率分布模型，并选取合 适的距离度量，到其它聚类的距离很大的数据对象被视为离群数据。基于念头 的方法通过考察一群对象主要特征上的差别识别离群数据，而不是使用统计度 量或距离度量。 2 1 5 演化分析 演化分析描述行为随时间变化的对象的规律或趋势，并对其建模。这包括 时间相关的数据的特征化、区分、关联、分类或聚类，此类分析的典型代表有 时阳j 序列分析、序列或周期模式匹配和基于相似性的数据分析等等。 2 2 数据挖掘系统的分类 因为数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不 同数据挖掘系统。对数据挖掘系统的分类可以帮助用户区分数据挖掘系统，确 定最适合其需要的数据挖掘系统。按照不同的标准，数据挖掘系统可以分类如 下： 根据挖掘的数据库类型分类：数据库系统本身可以根据不同的标准( 数据 模型，或数据或所涉及的应用类型) 分类，每一类可能需要自己的挖掘技术。 例如有空间数据库挖掘系统。1 、时间序列数据挖掘系统。1 、多媒体数据挖掘系 统“”或w e b 数据挖掘系统“。 硕士学位论文 m a s t e r s 1 l s i s 根据挖掘的知识类型分类：根据数据挖掘的功能，如特征化、区分、关联、 分类聚类、离群分析和演变分析、偏差分析、类似性分类。一个全面的数据挖 掘系统应当提供多种或集成的数据挖掘功能。 根据所挖掘的知识的粒度或抽象层分类：包括挖掘泛化知识，原始层知识， 或多层知识。一个高级数据挖掘系统应当支持多抽象层的知识发现。 此外，数据挖掘系统还可以分类为挖掘数据规则性和数据不规则性( 如异 常的数据) 。一般地，概念描述、关联分析、分类、预测和聚类挖掘数据规律， 将离群数据作为噪声排除。 根据所使用的技术分类：这些技术的采用依赖于与用户交互程度或所用的 数据分析方法。复杂的数据挖掘系统通常采用多种挖掘技术，或采用有效的、 集成的技术，结合一些方法的优点。 根据应用分类：数据挖掘系统可以根据应用分类。例如，可能有些数据挖 掘系统特别适合金融、电信、d n a 、股票市场等领域的数据分析，不同的应用 通常需要集成对于该领域特别有效的专家知识和方法，所以普通的数据挖掘系 统有时可能并不适合特定领域的挖掘任务。 2 3 数据挖掘研究的主要问题 现今数据挖掘界集中研究的主要问题分为以下几个主题： ( 1 ) 挖掘方法和用户交互问题 反映所挖掘的知识类型、在多粒度上挖掘知识的能力、领域知识的使用、 特定的挖掘和知识显示。 a ) 在数据库中挖掘不同类型的知识：由于不同的用户可能对不同类型的 知识感兴趣，数据挖掘系统应当覆盖范围很广的数据分析和知识发现 任务，包括数据特征化、区分、关联、分类、聚类、趋势和偏差分析 以及类似性分析。这些任务可能以不同的方式使用相同的数据库，并 需要研究大量的新的数据挖掘技术。 b ) 多个抽象层的知识挖掘：因为预先难以准确地知道在数据库中发现什 9 硕士学位论文 h s f z r s f 马j s 么，数据挖掘过程应当是交互的。对于包含大量数据的数据库，应当 使用适当的抽样技术，进行式的数据探查。交互式的数据探查允许用 户聚集搜索模式，根据返回的结果提出和精炼数据挖掘请求。 c ) 结合领域知识：为了加快挖掘过程，可以使用背景知识或领域知识来 指导发现过程，并使得发现的模式以简洁的形式在不同的抽象层表示。 关于数据库的领域知识，如完整性约束和演绎规则，可以帮助聚集知 识发现过程或评估发现的模式的兴趣度。 d ) 数据挖掘结果的表示和显示( 可视化的挖掘) ：从数据库中发现的知识 应当是易于理解的，能够直接让人们使用，因此必须用高级语言、可 视化表示或其他表示形式表达，如果系统是交互的，这一点尤为重要。 要求系统采用有表达能力的知识表示技术，如树、表、规则、图、图 表或曲线等。 ( 2 ) 性能问题 包括数据挖掘算法的有效性、可伸缩性和并行处理 a ) 数据挖掘算法的有效性和可伸缩性：为了有效地从数据库的大量数据 中提取信息，数据挖掘算法必须是有效的和可伸缩的，即是，对于大 型数据库，数据挖掘算法的运行时间必须是可预计的和可接受的。从 数据库角度来看，有效性和可伸缩性是数据挖掘系统实现的关键问题。 b ) 并行、分布式和增量挖掘算法：许多数据库的大容量、数据的广泛分 布和一些数据挖掘算法的计算复杂性是促使丌发并行和分布式数据挖 掘算法的因素。这些算法将数据划分成多个部分，这些部分可以并行 处理，然后合并第部分的结果。此外，有些挖掘过程的高花费了对增 量数据的需要。增量算法与数据库更新结合在一起，而不必重新挖掘 全部数据。这种算法渐增地进行知识更新，修f 和加强先前业已发现 的知识。 ( 3 ) 数据库类型的多样性问题 a ) 关系的复杂的数据类型的处理：由于关系数据库和数据仓库的广泛使 用，对它们开发有效的数据挖掘系统是很重要的。然而，其他数据库 可能包含复杂的对象、超文本和多媒体数据、空间数据、时间数据或 1 0 硕士学位论文 m a s l e r s t l i e s i s 事务数据。由于数据类型的多样性，数据挖掘的目标不同，期望个 系统挖掘所有类型的是不现实的。为挖掘特定类型的数据，应当构造 特定的数据挖掘系统。这样，对于不同类型的数据，我们可能有不同 的数据挖掘系统。 b ) 由异种数据库和全球信息系统挖掘信息：局域网和广域网连接了许多 数据源，形成了庞大的、分布式的和异质的数据库。从具有不同数据 语义的结构化的、半结构化的和非结构化的不同数据源发现知识，对 数据挖掘提出了巨大挑战。 2 4 数据挖掘系统的结构 典型的数据挖掘系统的结构如图2 i 所示，其主要成分有图形用户接口、 知识库、数据挖掘引擎、模式评估模块、数据库或数据仓库服务器、数据库或 数据仓库。 数据 图2 i 数据挖掘系统结构 各部分功能介绍如下： 图形用户界面：此模块允许系统与用户之间进行交互，指定数据查询任务 提供信息，帮助搜索聚焦，根据数据挖掘的中间结果进行探索式的数据挖掘。 。耻l , s t e r s i fi e 文s i 。 模式评价模块：它可以利用兴趣度度量，与数据挖掘模块交互，以便压缩 搜索空问，而且根据兴趣度阈值能够过滤发现的模式。 数据挖掘引擎：这是数据系统的核心部分，由一组功能模块组成，用于特 征化、关联、分类、聚类分析以及偏差分析。 知识库：这是领域知识，用于指导搜索或评估结果模式的兴趣度。这种知 识可能包括概念分层，用于把属性组织成不同的抽象层。用户确信方面的知识 也可以包含在内。 数据库或数据仓库服务器：它根据用户的数据挖掘请求来提取相关数据。 数据库或数据仓库：这是一个或一组数据库、数据仓库、电子表格或其他 类型的信息库，可以在数据上进行数据清理和集成。 2 5 d m 的应用范围 由于数据挖掘可以从大量数据中提取有用的信息和知识，所以已经被广泛 地应用于各个领域。 ( 1 ) 零售业 零售业是数据挖掘的主要应用领域，这是因为零售业积累了大量的销售资 源，顾客购买历史记录，货物进出，消费与服务记录等等，其数据量在不断地 迅速膨胀，特别是由于日益增长的电子商务的流行，都为数据挖掘提供了丰富 的资源。 零售数据挖掘可有助于识别顾客购买行为，发现顾客购买模式和趋势，改 进服务质量，取得更好的顾客保持满意程度，提高货品销量比率，设计更好的 货品运输与分销策略，减少商业成本，典型的例子包括基于数据挖掘的数据仓 库的设计与构造、销售一顾客一产品一时间和地区的多维分析、促销活动的有 效性分析和顾客保持力等等。 ( 2 ) 金融投资 我国的金融行业信息基础设施建设不断完善，信息资源的开发也得到了重 视，金融企业己开始应用信息技术对资金流、信息流、业务流进行全面的整合， m 硕a s 衅t e r 鼢s t ii e 文s i 。 金融行业进入了“数据大集中”时代。但是，如何从海量的用户信息中分析出个 人用户的投资偏好，然后有针对性地提出投资方案；如何对海量的信息进行科 学的分析处理，推出新业务，以及时为决策者提供决策支持? 这些自然要运用 到数据挖掘工具。银行和金融机构中的数据挖掘的应用主要包括贷款偿还预测 及客户信用政策分析、目标市场客户的分类与聚类、投资决策和金融犯罪的侦 破等，代表性的系统有b e l la t l a n t i c 和f i d e l i t ys t o c ks e l e c t o r 。 ( 3 ) 生物医学 过去的十年里，生物医学有了迅猛发展，从新药物的开发和癌症治疗的突 破，到通过大规模序列模式和基因功能的发现，进行人类基因的识别与研究， 目前生物医学的基因研究的重点集中在d n a 序列的分析上，因为这种序列构 成了所有活的生物体的基因代码的基础。所有的d n a 序列由四个基本的( 核 苷) 组成：腺嘌呤( a ) ，胞核嘧啶( c ) ，鸟嘌呤( g ) ，胸腺嘧啶( t ) ，这四 个核苷组合构成很长的序列或链，类似一个双螺旋。 人类约有1 0 0 ，0 0 0 个基因，个基因约由成百个核苷按一定次序组织而成， 核苷按不同的次序和序列可以形成不同的基因，几乎是不计其数。具有挑战性 的问题是从中找出导致种疾病的特定基因模式，由于数据挖掘中已经有许多有 意义的序列模式分析和相似检索技术，它自然成为d n a 分析中豹强有力工具。 数据挖掘中的数据清理和集成方法有助于基因数据集成和基因数据仓库的构 造，频繁序列模式分析方法可以对分别来自带病和健康组织的基因序列进行比 较以识别两类基因间的主要差异，从而找出导致疾病的基因因素。大部分情况 下，引起疾病的基因可能不止一个，不同基因在疾病的不同阶段起着作用，如 果能找到疾病发展的不同阶段遗传因素序列，就有可能开发针对不同阶段的治 疗药物，数据挖掘中的路径分析在这方面会起到非常重要的作用。 ( 4 ) 电信业中的数据挖掘 电信业已经迅速地从单纯的提供市话和长话服务演变为提供综合电信服 务，如语音、传真、寻呼、移动电话、电子邮件和w e b 数据传输以及其它数 据通信服。电信网络、计算机网络和因特网的融合已是大势所趋，随着许多国 家对电信业的丌放和新兴计算与通信技术的发展，电信市场正在迅速扩张并且 竞争越发激烈。因此利用数据挖掘技术来帮助确定电信模式、捕捉盗用行为和 硕士学位论文 m a s j i r s i f 【e s i s 更好地利用资源来提高服务质量是非常有必要的。 ( 5 ) w e b 挖掘 作为i n t e m e t 的一个重要组成部分，万维网( w e b ) 已经成为一个巨大的、 分郁广泛的和全球性的信息服务中心，它囊括了新闻、广告、消费信息、金融 管理、教育、政府、电子商务和许多其他信息服务。由于w e b 上的信息主要 以文档( h t m l 或经x m l 格式) 存储，它们的结构性较差，所以从w e b 上发 现和提取信息是一个有极大挑战性的课题。大体上，w e b 挖掘主要包括三类： w e b 内容挖掘、w 曲结构挖掘和w e b 使用记录挖掘。 w e b 内容挖掘是指对网上资源的搜索，目前有许多基于索引的搜索引擎， 如o o o g l e ，a l t a v i s t a 等等，利用搜索引擎，用户可以通过提供一组紧密相关的 关键字和词组，快速地定位到他们感兴趣的文档。 w c b 链接结构挖掘的目的是为了识别权威w e b 页面，所谓权