（系统工程专业论文）关联规则的挖掘及其在商业决策中的应用研究.pdf

摘要 数据挖掘是一个融合了数据库技术、人工智能、机器学习、统计学、 知识工程、面向对象方法、信息检索、高性能计算、以及数据可视化等最新技术 的研究成果的多学科交叉研究领域，经过十几年的研究，产生了许多新概念和方 法，特别是最近几年一些基本概念和方法趋于清晰，它的研究正向着更深入的方 向发展。关联规则作为数据挖掘研究的一个重要分支，由于关联规则形式简洁、 易于解释和理解并可以有效的捕捉数据间的重要关系，从大型数据库中挖掘关联 规则的问题已经成为近年来数据挖掘研究领域中的一个热点，也取得了可喜的进 步，探索出了许多独具特色的理论体系。但是，这决不意味着关联挖掘理论的探 索已经结束，恰恰相反它留给了研究者丰富的理论课题。一方面，在这些大的理 论框架下有许多面向实际应用目标的关联规则挖掘理论等待探索和创新：另一方 面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理论的诞生是必然的， 而且可能对特定的应用产生推动作用，可能融合特定的应用目标，如市场营销、 c r m 、电子商务等。 本文首先介绍了数据挖掘的定义及主要的数据挖掘技术，并给出数据挖掘的 体系结构和运行过程。接着详细描述了关联规则挖掘的基本理论和经典关联规则 挖掘算法a p r i o r i 算法，其中也包括了规则生成的算法，并对a p r i o r i 算法及其改 进算法a p 五嘶骶d 算法和a p r i o r i h y 晡d 算法进行了效率上的分析比较，也提供了 关联规则算法改进的7 个方向以及适用于关联规则挖掘的部分平台工具的选择， 如o r a c l e9 id a t am i n i n g 。最后从商场购物分析领域对关联规则的挖掘在商业决策 中的应用做了一定的研究，这个研究主要就是通过分析顾客的购买行为，从顾客 购买的商品与商品之间、顾客与商品之间两个方面来挖掘关联关系，再对挖掘出 来的规则做解释并为商业决策提供一些指导性建议。 关键字：数据挖掘，关联规则，a p r i o r i 算法，支持度，置信度 a b s t r a c t d a t am i n i i l gi sam u l t i - s c i c n c er 髂c a r c hd o m a i n ，w h i c hm c r g c dm a n ys t i l d y o u t c o m e so fn e w t e c l l n o l o 西c s ：d a t a b 鹳ct c c h n o l o g y 、a n i f i c i a li n t c m g c n c e 、m a c l l i n c l e a m i n g 、s t a t i s t i c s 、l m o w l e d g ce n 西n c c r i n g 、o b j c c t 帕r i c n t o dm e t h o d 、i i l f 0 肋a t i o n r e 仃i c v a l 、h i g l l p e r f o 肌a n c cc o m p u t i n g 蛆dd a t av i s u a l i z a t i o n f 0 rd e c a d c sy e 硒 s t u d y ，g c f a t el o t so f n e w c o n c c p t sa n dm c t h o d s ，鸽p c c i a l l yl a t c l yy c a f ss o m cb a s i c n o t i o n sa n dm c 也o d o l o g i c st c n dt od e a r ，i t ss t l i d yi sd e v e l o p i n gt od i r t i o n sm o r e d c c p l y a s s o c i a t i m l e s 勰ai m p 0 吐柚t b r a n c ho f d a t a m i i n g t h cp r o b l c mo fm i i n g a 鹞o c i a t i o nm l c s r o mh u g cd a t a b 瑟ch 雒b c c o m eah o ts p o t ，s 诅c e 也eb r i e n y 、 e x p l a i n a m e 、u n d e 碍扭n d a b l c a n d c 氆饼c n c y o f c a t c h j h gi m p o r t 如tr c l a t i o n s 岫a m o n g d a t ao fa s s o c i a t i o nm l c s ，i th 鹤g r a t i 置y i n gp m 乒c 鹤i nc 】【i s t e d o u t c o m e s ，c x p l o r c d m 姐yi n d i v i d u a lt h c o r yf h c l l l t i e s b u tt h i s d o e s n tm c 缸t h cc x p l 鲥n go fm i 血g t h c o r yo fa 骚o c i a t i o nm l c sh 鹊e n d e d i n v c r s d yi tl e a v c sr c s e a r c h e r sa b 吼d a n “c s s o n s o n 也co n eh a n d ，t h e r ea r cl o t so fa 鹃o d a t i o nm l e st h c o r yo fa p p i i c a t i o n - o r i c m c di s w a i t i n g f o re x p l o r ea n dc r e a t i v ci nt h e s cb 远t h c o r y 胁l m e w o r k ；o nt h eo t h c rh a n d ， w i t ht h ed e v c l o p m c n to fd a t am i n i ga n dr c l e v a c et e c h n o l o g y ，i tm u s tw i ub i r t hn c w m i n i n gt h e o r y a n di tw m h a v ei m p e t l l st os o m c p a n i c u l 盯a p p l i c a t i o n i tm a ym c r g c p a n i c u l a ra p p l i c a t i o nt a r g e t ，s u c ha sm a r k e t i n g 、c u s t o mr c l a t i o n s h i pm a n a g e m e n t 、 e j c c n 伽j cb u s i n e s s ht h j sp 印c r 6 r s u y i n 廿o d u dt h ed c 丘n i t i o n 趾ds c v c m lt y p i c a lt c c h n o l o g i c so f d a t am i n i n g ，t t l e n 酉v e si t sf 她u l t ys t n l c t i i r ea n d 兀l nc o u r s e s e c o d l y m a i l l l y d c s c r i b c b a s i ct h c o r y0 f 船s o c i a t i o nm l cm i n j 由g 柚dc l a s s i c “血ga 1 9 0 r i t h 】 i l a p r i o r i ， i n c i u d i n gt h ca l g o r i t h mo fg c n c r a t cm l c s ，t h e n 柚a l y z ct 1 1 cc 硒c i c yo fa l g o r i m m a p o r i i i n p r 0 v e da 1 9 0 r i t h ma p r i o f i 砸d a n d a p d o f i h y b r i d ，h e r e a l s op r o v i d c ds e v c n d i r c c t i o n so fm o d i 丘e da l g o r i t h mo fa s s o d a t i o nn l l ca n dt h cc h o i c eo fs o m e p l a t f o t 0 0 l sw h i c hi ss u i t a b l cf o rm i l l i l l ga s s o c i a t i o nm l e ，s u c h 鹋o r a c l c9 id a t am i n i n g a t l 罄td os o m c 咒s e a r c h0 nt h ca p p t i o no f 髂s o c i a t i o nm i i n gi nb u s i n c s sd e d s i o n 丘o m s u p c r n l a r k e tb u y i n g f o o d sa n a l y s i sr e a l m ，t h i sr c s c a 曲m a i n l yt h r o u g h a n a l y z i n gp u r c h a s eb c h a v i o ro fc u s t o m s ，m 蛐g 勰s o c i a t i o nr c l a t i o n s h j p 的m 俩o s i d c s ：b e m e e ng o o d sa n dg o o d s 、c u s t o m sa n d9 0 0 d s ，a f t c rt h cc x p l 锄a t i o 船0 ft h 鸽c 躯s o c i a “o nm l c s ，g i v es o m e g i l i d 柚c co nb 璐i 北豁d c c i s i o n k e y w o r d s ：d a t am i i n g ，舡s o c i a t i n i i 髂，a p r i o r ia l g o r n l 血，s u p p o r t ，c o n 丘d c n c e n 武汉理工大学硕士论文 第1 章绪论 数据挖掘d a t am i n j n g 是一个多学科交叉研究领域，它融合了数据库 d a t a b 勰c 技术、人工智能a n i f i c i a l i n t e l l i g c n c c 、机器学习m a c h j n e k a r i l i n g 、统计学s t 础t i c s 、知识工程k o w l c d g ee l l g i n e c r i n g 、面向对象方 法o b i c d o r i e n t c dm c t h o d 、信息检索i n f o m a 6 0 nr c t i i c v a l 、高性能计算 h i g h p c 面i m 衄c 0 m p u 血g 、以及数据可视化d a t a s u a l i z a t i o n 等最新技术的 研究成果，经过十几年的研究，产生了许多新概念和方法，特别是最近几年一些 基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。数据挖掘之所以 被称为未来信息处理的骨干技术之一，主要在于它以一种全新的概念改变着人类 利用数据的方式。二十世纪，数据库技术取得了决定性的成果并且已经得到广泛 的应用，但是，数据库技术作为一种基本的信息存储和管理方式，仍然以联机事 务处理o u 甲( o n _ l 缸et r 强s 枷o np r o c e s s i n g ) 为核心应用，缺少对决策、分 析、预测等高级功能的支持机制。众所周知，随着数据库容量的膨胀特别是数据 仓库d a t aw 打e h o u s e 以及w 曲等新型数据源的日益普及，联机分析处理o l a p o n l 血ea n a l y t i cp r o c c s s i n g 、决策支持d c d s i o ns u p p o r t 以及分类a a s s i 丘c a t i o n 、 聚类a u s t e r i n g 等复杂应用成为必然。面对这一挑战，数据挖掘和知识发现 k n o w l c d g cd i s c o v c r y 技术应运而生，并显示出强大的生命力。数据挖掘和知识 发现使数据处理技术进入了一个更高级的阶段，它不仅能对过去的数据进行查 询，并且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地 做出理想的决策，预测未来的发展趋势等。 1 1 研究背景 随着计算机和自动化数据采集工具的广泛应用，在各种应用领域里的数据库 中存储了大量的数据，这使得人们对这些数据进行分析并转化为有用知识的需求 变得越来越迫切。于是知识发现与数据挖掘( 趾o w l c d g cd i s c o v c r y 柚d d a t a m n g ，) d ) 自然成为近年来人们从大型数据库中获取信息的一个重要的研究 领域一般地，数据挖掘就是指从数据库或数据仓库中发现隐藏的、预先未知的、 有趣的信息的过程，该过程可以看作是知识发现过程中的一个核心的步骤。据挖 掘的主要功能包括，聚类( c l u s t c 咖曲、分类( c l a s s i 丘c a t j o ) 、预测( p r c d i 砸o n ) 、关 联分析( 舡s o c i a 哟na n a l y s i s ) 、时间序列分析皿c s e f i e sa n a l y s i s ) 等。 关联规则挖掘( ( a s s o c i a t i o n r u l em i n j n 曲是数据挖掘研究的一个重要分支，关 联规则是数据挖掘的众多知识类型中最为典型的一种。在1 9 9 3 年r a i c s h a g r a w a l 武汉理工大学硕士论文 等首次提出了关联规则挖掘的概念并给出了基于数据库多趟扫描的s 算法，此 后关联规则由于其可用性和易于理解的优点获得了广泛的关注和深入的研究，提 高获取的关联规则的精确度和执行效率成为研究的中心议题。a g r a w a l 其后提出 了改进的朋s 算法a p r i o r i ，a p 血r i l l d 及a p r i o r i h y b r i d ，成为众多关联规则算 法的基础。获取高效率的主要方法是在不牺牲或者很少牺牲大项集产生精确度的 前提下尽量减少数据库数据的扫描次数。最近也有独立于a 擎a w a l 的频集方法的 工作，以避免大项集方法的一些缺陷，探索挖掘关联规则的新方法同时随着 o u 垤技术的成熟和应用，将o u 心和关联规则结合也成了一个重要的方向。也 有一些工作注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些 值得考虑的研究方向而在我国，许多单位也已开始进行数据挖掘技术的研究， 但从目前资料来看多还局限于基础技术和算法的研究。 目前，关联规则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、 可视化及信息科学等诸多领域里的广大学者和研究机构的格外重视，并取得了不 少的研究成果。由于关联规则形式简洁、易于解释和理解并可以有效的捕捉数据 间的重要关系，从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘研 究领域中的一个热点。 分析目前的研究和应用现状，应该在如下几个方面需要重点开展工作： ( 1 ) 缺乏对关联规则的主、客观评价标准进行进一步的研究工作，特别是 从统计学的角度对其进行研究。有趣的关联规则是用户想要的规则，因此对于有 趣度的研究非常重要，现有的支持度、信任度及其它标准往往仅能适合其各自的 场合。 ( 2 ) 可视化要求已经成为目前信息处理系统的必不可少技术，对于一个数 据挖掘系统来说，它更是重要的，可视化挖掘除了要和良好的交互式技术结合外， 还必须在挖掘结果或知识模式的可视化挖掘过程以及可视化指导用户挖掘等方 面进行探索和实践。 ( 3 ) 数据挖掘理论与算法研究经过十几年的研究，数据挖掘已经在继承和 发展相关基础学科，如机器学习、统计学等，已有成果方面取得了可喜的进步， 探索出了许多独具特色的理论体系。但是，这决不意味著挖掘理论的探索已经结 束，恰恰相反它留给了研究者丰富的理论课题。一方面，在这些大的理论框架下 有许多面向实际应用目标的关联挖掘理论等待探索和创新；另一方面，随着数据 挖掘技术本身和相关技术的发展，新的挖掘理论的诞生是必然的。而且可能对特 定的应用产生推动作用，新理论的发展必然促进新的挖掘算法的产生，这些算法 可能扩展挖掘的有效性，如针对数据挖掘的某些阶段、某些数据类型、大容量源 数据集等更有效，可能提高挖掘的精度或效率，可能融合特定的应用目标，如市 2 武汉理工大学硬士论文 场营销、c r m 、电子商务等。因此，对关联挖掘理论和算法的探讨将是长期而 艰巨的任务。 从上面的叙述，可以看出数据挖掘研究和探索的内容是及其丰富和具有挑战 性的，正是在这样的背景下，在以往的研究的支持下，我选择本课题开展相关研 究工作的。 1 2 拟解决的问题 作为毕业论文，在收集和整理大量的相关资料，弄清相关的理论、方法、算 法、体系结构、原型系统等基础上，集中选取了下面两个问题开展相关工作： ( 1 ) 关联规则挖掘的研究和应用。关联规则挖掘是数据挖掘中研究较早而 且至今仍最活跃的研究分支之一，影响关联规则的挖掘效率的因素主要有数据库 扫描的i o 代价、内存的需求、c p u 的时间花费等。目前的关联规则挖掘算法 仍然需要在这些方面加以创新或改进，因此，本人选取丁关联规则挖掘算法进行 了集中研究。 ( 2 ) 从大量的数据中发现其关联知识在市场定位、决策分析和商业管理等领 域是极为有用的。本文重点讨论的应用领域是市场购物( 袋) 分析，它通过搜索 常一起购买的商品集来了解顾客的购物习惯，从而挖掘出顾客购买的商品与商品 之间、商品与顾客之间的潜在关系，以次来探讨关联规则挖掘在商业决策中的应 用。 1 3 国内对关联规则挖掘算法的研究现状 关于知识发现和数据挖掘的研究，国内尚处于开始阶段，国外己是热门研 究方向，并已经达到一定的水平并投入应用领域。国内对关联规则挖掘的研究 还处于起步阶段，中科院计算所的欧阳为民首先引入国外关联规则挖掘的概念 和思想，并在基于a p r i o r i 算法的基础上提出了时态约束的关联规则。近两年， 国内的部分学者对关联规则挖掘进行了大量的研究，但提出的算法也都是基于 国外所提出算法的改进算法。 目蘸国内从事数据关联规则挖掘研究的人员主要在大学，也有部分在研究所 或公司。所涉及的研究领域很多，一般集中于学习算法的研究以及关联规则挖掘 理论方面的研究。对于关联规则挖掘算法一般都是基于a p f i o r i 的改进算法，虽 然已经取得了相当的成功，但目前在处理极大量的数据时，如何提高算法效率的 问题：对于挖掘迅速更新数据的挖掘算法的进一步研究；在挖掘的过程中，提供 一种与用户进行交互的方法，将用户的领域知识结合在其中等都是尚待研究和解 决的问题。 3 武汉理工大学硪b 论文 1 4 关联规则挖掘算法研究的目的和意义 1 4 1 研究的目的 在过去的研究中，每笔交易中的不同商品都只能被视为发生一次，也就是 说每个商品都被视为独立且平等的个体，并未真正考虑实际交易数量等显著性 的问题。然而在真实的交易数据库中，每个商品所被交易的数量都各有差异， 所以除了考虑发生频率之外，每个商品的交易数量也应是很重要的评价指标。 不同的商品组合所产生的利润也是一个值得探讨的因素，在真实情况中不同商 品的消费一定会产生不同的获利情况，而以往的研究均较少讨论到此。如何将 提出的算法很好地应用的具体的实际系统中，以达到关联规则挖掘的目的，如 在庞大的数据库中寻找出有价值的隐藏事件，加以分析，并将这些有意义的信 息归纳成结构模式，作为企业在进行决策时的参考。 1 4 2 研究的意义 有助于从商务信息系统的大型数据库中提取对企业决策者有价值的信息， 在制订销售配货、商店陈列设计、产品目录设计、产品定价和促销以及根据顾 客的购买行为模式对客户进行分类等商业决策时给企业决策者予以指导，使企 业具有更强的竞争优势。 1 5 本章小结 本章介绍了数据挖掘研究的意义和技术背景，论文的选题依据，研究背景以 及主要研究内容等，数据挖掘作为二十世纪信息处理的骨干技术之一，正以一种 全新的概念改变着我们利用数据的方式，经过十几年的研究和实践，数据挖掘技 术已经融合了许多学科的最新研究成果而形成独具特色的研究分支。目前的数据 挖掘研究正处于蓬勃发展时期，有许多具有挑战性的课题被提出，数据挖掘的研 究内容是极其丰富的。作为硕士论文，在充分了解基本概念和主要技术发展状况 以及现实应用的前提下，有选择地研究了关联规则挖掘的理论和经典算法及其在 挖掘数据库中商品与商品、顾客与商品之间关联关系时的商业应用。 4 武汉理工大学硕士论文 第2 章数据挖掘技术 随着数据库和数据仓库技术的普遍运用，企业中积累的数据已经达到了t b 的量级。在这些大量数据的背后隐藏了很多具有决策意义的信息。数据挖掘就是 要在“数据矿山”中找到蕴藏的“知识金块”，帮助企业减少不必要投资的同时 提高资金回报。数据挖掘给企业带来的潜在的投资回报几乎是无止境的。世界范 围那具有创新性的公司都开始采用数据挖掘技术来判断哪些是他们的最有价值 客户，以便重新制定他们的产品推广策略( 把产品推广给最需要它们的人) ，用 最小的花费得到最好的销售 2 1 数据挖掘的定义 数据挖掘( d m ，d a t a m i n i l l g ) 是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程。还有很多和这一术语相近的术语，如从数据库中发现 知识( k d d ) 、数据分析、知识抽取、模式分析、数据考古、数据采集、信息收 割、商业智能、数据融合以及决策支持等。国内的学者也把d a t am i n i n g 译为数 据采掘或数据开采。 数据挖掘发现的知识可以被用于信息管理、查询优化、决策支持、过程控制 等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学科，它 汇聚了不通领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行 计算等方面的学者和工程技术人员。 数据挖掘利用各种分析工具在海量数据中发现模型和数据间关系，这些模型 和关系可以用来做出预测。数据挖掘是一个工具，而不是有魔力的权杖。它不会 坐在数据库上一直监视数据库，然后当它发现有意义的模型时发一封电子邮件。 它仍然需要了解业务，理解数据，弄清分析方法，数据挖掘只是帮助商业人士更 深入、更容易地分析数据，它无法告诉某个模型对企业的实际价值，而且数据挖 掘中得到的模型必须要在现实生活中进行验证。 2 2 数据挖掘的分类 数据挖掘系统利用的技术越多，得出的结果精确性就越商。原因很简单，对 于某一种技术不适应的问题，其他方法却可能奏效。这主要取决于问题的类型以 及数据的类型和规模 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务，可分 武汉理工大学硕士论文 为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖 关系或依赖模型发现、异常和趋势发现等。根据挖掘对象分，有关系数据库、面 向对象数据库、空间数据库、时态数据库、文本数据库、多媒体数据库、异构数 据库、遗产数据库阻及w 曲。根据挖掘方法，可分为机器学习方法、统计方法、 神经网络方法和数据库方法。机器学习包含归纳学习方法、基于案例学习、遗传 算法等。统计方法包含回归分析、判别分析、聚类分析、探索性分析等。神经网 络方法包含前向神经网络、自组织神经网络等。数据库方法主要时多维数据分析 方法，另外还有面向属性的归纳方法。 2 2 1 分类分析 预言模型以通过数据库中的某些数据得到另外的数据为目标，若预测的变量 是离散的( 如批准或者否决一项贷款) ，这类问题就称为分类( a a 蟠i 6 臼曲n ) ； 如果预测的变量是连续的( 如预测盈亏情况) ，这种问题称之为回归( r e f 骼s i o n ) 。 分类一直为人们所关注，数据挖掘广泛使用的方法有决策树、神经网络、径向基 础函数( r a d i a lb 硒i sf u n c t i o n ) 等。 2 2 2 聚类分析 聚类用于从数据集中找出相似的数据并组成不同的组。与预测模型不同，聚 类中没有明显的目标变量作为数据的属性存在。聚类算法通过检测数据判断“隐 藏属性”。这些案例将客户数据库分成若干相似的组，每组包含若干相似的客户， 针对每个不同的组刻制定不同的销售策略。有很多方法可使数据分类，公认的常 用方法包括k m e a n s 算法、分层凝聚法( h i e r a r c h i c a la 鸥l o m c r a t i v cm e t h o d s ) 及采 用估算最大值法( 】邑s t i m a t i o nm a x 血i z a t i o na 1 9 0 f i t h m ) 使适应数据可能的混合模 型。一条记录有可能属于若干不同的类。 2 2 3 关联分析 关联分析描述了这样一种方法，它的目的在于生成部分数据的概要。例如寻 找数据子集间的关联关系或者一些数据与其数据之间的派生关系。本领域最常见 的技术使利用关联规则。有些时候如商场销售分析，关联规则的计算依赖于识别 在相关数据中频繁出现的数据集。频繁出现的数据由在某事务中同时出现的数据 组成。 频繁出现的数据组可用于描述在超级商场中客户有意同时购买的商品名称。 例如，如想了解清楚某网站被用户访问的情况，经常出现的数据组也可表示为在 武汉理工大学硕士论文 某次站点访问事件中的页面集。这样，零售商可通过关联技术将相关商品摆在一 起进行组合销售。通过规定一个最小支持度( 由分析者指定) ，数据挖掘算法能 够从数据集中找出同时销售的商品。 一旦关联数据被推导出，即可用于生产关联规则。关联规则是这样产生的： 选定关联数据中的某一类为预测目标，给其他类赋值作为预测规则的条件。 2 2 4 序列分析及时间序列 序列分析和时闻序列说明数据中的序列信息和时间相关的序列分析。 前面所讲的三种数据挖掘技术分类与回归模型、聚类和关联分析中，事 件产生的序列信息被忽略或简单的被作为一条记录对待举例来说，在一组统计 用户访问网站信息的数据中，假设用户u 7 7 4 访问网页顺序如下： p m p 2 p 1 3 p 1 7 。这一事件简单的被记录如下： c a s e ：u s c r u 7 7 4 ：v i s i t c d p a g c 0 ，p a g c 2 ，p a g c l 3 ，p a g c l 7 另外一种做法，它可以很好的被表示为序列信息，这意味着其他用户依照不 同顺序访问同样的网页，将与u 7 7 4 区别开来。 这类方法关注于下述几个方面之一： ( 1 ) 总结数据的序列或者事件。 ( 2 ) 检测数据随时间变化的变化。 ( 3 ) 检测知识( 模型或特征曲线) 随时间变化的变化。 2 3 数据挖掘的体系结构 如上所述，数据挖掘的核心技术是人工智能、机器学习、统计学等，但一 个数据挖掘系统不是多项技术的简单组合，两是一个完整的整体，它还需要辅助 技术的支持，才能完成数据采集、预处理、数据分析、结果表述这一系列任务， 最后将结果呈现在用户面前。 根据数据挖掘与数据库及数据仓库系统的耦合程度可以分为零耦合、松散耦 合、半紧密耦合及紧密耦合四种结构。目前的发展趋势是紧密耦合的系统结构。 管理信息系统和数据挖掘之间的借口，可以作为如何标记合适的数据挖掘原语的 一个研究问题数据挖掘原语能够在数据仓库或者数据库内部执行以改善数据挖 掘系统的性能。p m m 【妲r e d i c t “cm o d c lm 缸l 【i l pl a n g i l a g c ，可预测模型标记预言) 是数据挖掘系统与预言模型系统之间的一个标准接口。 按特征划分的数据挖掘的系统结构如表2 1 所列。 第一代数据挖掘系统支持一个或少数几个数据挖掘算法，这些算法涉及用来 挖掘向量数据，挖掘的时候一般一次性调进内存进行处理，系统的成功依赖于数 7 武汉理工大学硕士论文 据的质量。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接 口，具有搞的可扩展性。第三代的特征是能够挖掘1 】n e m 删王k t r 柚e t 的分布式和 高度异质的数据，并且能够有效地和操作型系统中的预言模块相联合提供决策支 持的功能。第四代数据挖掘系统能够挖掘嵌入式系统、移动系统和普遍存在计算 设各产生的各种类型的数据。将数据挖掘和移动计算相结合是当前的一个研究领 域。 表2 1 按特征划分的数据挖掘的系统结构 代特征数据挖掘算集成分布计算模型数据模型 法 第一代数据挖掘支持一个或独立的系统单个机器向量数据 作为一个者多个算法 独立的应 用 第二代和数据库多个算法：能数据管理系同质，局部区域有些系统 以及数据够挖掘一次统，包括数据的计算机群集支持对象、 仓库集成不能放进内库和数据仓文本和连 存的数据库续的媒体 数据 第三代和预言模多个算法数据管理和 i n t e m e t e x 拄a n c t支持半结 型系统集预言模型系网络计算构化数据 成统和w 曲数 据 第四代和移动数多个算法数据管理、预移动和各种计普遍存在 据各种言模型、移动算设备的计算模 计算数据系统 型 联合 第一代数据挖掘系统仍然未发展完全，第二代、第三代数据挖掘系统已经 出现。目前未见到任何第匹代数据挖掘系统的报导。第二代、第三代，以及第四 代数据挖掘和语言模型系统将与数据仓库合并，以提供一个集成的系统来管理日 常的商业过程。另一方面，第二、三、四代数据挖掘技术将不断发展和成熟，能 够和各种应用集成，成为一种嵌入式的技术( e m b c d d c dt e c h n o l o 盱) 。 2 4 数据挖掘的过程 由以上所述可知，数据挖掘的核心技术是人工智能、机器学习、统计等，但 8 武汉理工大学硕士论文 它并非多种技术的简单组合，而是一个不可分割的整体，还需要其它技术的支持， 才能挖掘出令用户满意的结果 数据库中的数据挖掘是个多步骤的处理过程，粗略可分为： 问题定义( 佻kd e 丘n i t i o n ) ，了解相关领域的有关情况，熟悉背景知识，弄 清用户要求。 数据收集和预处理( d a t a p r c p 缸a t i o na n dp r c p m c e s s i n g ) ，根据要求从数据库 中收集相关的数据。然后，对前一阶段产生的数据进行再加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 数据挖掘( d a t am 洫n g ) 算法执行，运用选定的数据挖掘算法，从数据中提 取用户所需要的知识，这些知识可以用一种特定的方式表示或使用一些常用的表 示方式。 知识的解释和评估( i n t e r p r c t 蚯0 n 柚de v a l u a 晒n ) ，将发现的知识以用户能理 解的方式呈现，如某种规则，再根据实际情况对知识发现过程中的具体处理阶段 进行优化，直到满足用户要求。 数据挖掘算法执行，仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有 两个影响因素：一是所采用的数据挖掘技术的有效性：二是用于挖掘的数据的质 量和数量( 数据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据 进行了不适当的转换，则挖掘的结果不会好的。 整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数 据不太好，或使用的挖掘技术产生不了期望的结果，这时，用户需要重复先前的 过程，甚至重新开始。 可视化在数据挖掘的各个阶段多扮演着重要的作用。特别是在数据准备阶 段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以期对 数据有一个初步的了解，从而为更好地选取数据打下基础。在挖掘阶段，用户则 要使用与领域问题有关地可视化工具。在表示结果阶段，则可能要用到可视化技 术以使得发现的知识更易于理解。 2 5 数据挖掘的应用 数据挖掘的应用十分广泛，各个领域在k d d 应用上既有相同之处，又有各 自不同的独特地方。以下是数据挖掘技术的一些典型应用领域： 1 科学应用 在科学研究( 特别是实验科学和计算科学的研究) 中，需要分析各种大量的实 验或观测数据，掘观测卫星、遥感器、d n a 分子技术等，传统的数据分析工具 效率较低甚至无能为力，因此必须有强大的智能型自动数据分析工具才行。 9 武汉理工大学硬士论文 2 市场销售 是数据挖掘技术应用最早也是最重要的领域。主要功能是：市场定位，消费者 分析，预测销售趋势，优化营销策略，分析库存需求，识别顾客的购买行为模式， 协助货架布置，制定促销活动时间，促销商品组合以及了解滞销和畅销商品状况 等商业活动。 3 金融 典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般采用模 型预测法( 如神经网络或统计回归技术) 。这方面的系统有f i d c m y s t o c ks d c c t o r ， 任务是使用神经网络模型选择投资；l b sc a p i t a lm 跹a g c m 姐t 使用了专家系统、神 经网络和基因算法技术辅助管理多达6 亿美元的有价证券。 4 欺诈甄别 分析银行或保险客户的要求和信誉，识别欺诈行为，如恶性透支等。这方面 应用非常成功的系统有：f a l c o n 系统和e a j s 系统。彤正c o n 是h n c 公司的开 发的信用卡欺诈估测系统，它已被相当数量的零售银行用于探测可疑的信用卡交 易。f a j s 是一个用于识别与洗钱有关的金融交易的系统，它使用的是一般的政 府数据表单。 5 i n t c m e t 的应用 目前这方面的研究主要有两个方面：研制新的更好的索引系统、利用已有索引 系统或搜索引擎开发高层次的搜索或发现系统。相比之下，后者的研究更为活跃。 从技术上看，自动文档分类或归类方法将对这方面的研究有很大作用。 总之，数据挖掘可广泛应用于银行金融、零售与批发、制造、保险、公共设 旌、政府、教育、远程通讯、软件开发、运输等各个企事业单位及国防科研上。 2 6 本章小结 本章先是简单探讨了数据挖掘的定义：然后具体讨论了几种不同的数据挖掘 的分类，虽然分类、聚类、关联分析、序列分析及时间分析等方法都汇集在数据 挖掘媛下，但它们的确存在很大的区别。数据挖掘从人工智能领域借鉴了很多东 西，既然人工智能技术的种类繁多，我们也就不难理解存在众多不同数据挖掘方 法的原因了接着全面描述了数据挖掘的体系结构和运行过程，这里不仅描述了 支持数据挖掘技术的辅助技术和发展过程，还给出了数据挖掘过程中要经历的各 个阶段，包括问题定义，数据收集与预处理，数据挖掘算法执行以及结果的解释 和评估等。最后从科学应用、市场营销挖掘等方面代表的各自不同的应用领域总 结了数据挖掘的应用。 1 0 武汉型j ：人学颂l 论文 第3 章关联规则挖掘的基本理论及经典挖掘算法 关联规则最早是由a 罩a w a l 等人提出的，最初提出的动机是针对购物篮分 析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则，这些 规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以及货 架设计等。之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究，他们 的工作涉及到关联规则的挖掘理论的探索、原有的算法的改进和新算法的设计、 并行关联规则挖掘p 盯a l l c la s s o d a t i o nr u l em i n i i l g 以及数量关联规则挖掘 q u a n t i t i c sa s s o c i a t i o nr u i em i n i i l g 等问题。在提高挖掘规则算法的效率、适应 性、可用性以及应用推广等方面，许多学者进行了不懈的努力。关联规则的数据 挖掘在商业等领域的成功应用，使它成为数据挖掘中最成熟、最主要、最活跃的 研究内容之一。这也正是我选择这一课题进行研究的主要原因。 3 1 关联规则的基本概念和问题描述 关联规则挖掘的数据集记为d ( 一般为事务数据库) ，d = t l ，t 2 ，t 。) ， t k = i 1 ，i 2 ，i 。，i p ) ，皿= 1 ，2 ，n ) 称为事务t ( t r a n s a c t i o n ) ，i 。( m = l ，2 ，p ) 称 为项目( i t e m ) 。 设i = i l i 2 ，i 。 是d 中全体项目的集合，i 的任何子集x 称为d 中的项目集 ( i t e m s e t ) ，若| x i = k ，则称j x i 为集合x 的k 项目集( k - i t e m s e t ) 。设t k 和x 分别 为d 中的事务和项目集，如果x k ，称事务t k 包含项目集x 。每一个事务都有 一个唯一的标识符，记作1 1 d 。 数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记为s 。项目 集x 的支持度记为s u p p o r t ( x ) ： s u p p 。r t ( x ) = 兰三一亍：寄坚 ( 其中吲是数据集。的事务数) 若s u p p o r t ( x ) 不小于用户指定的最小支持度( m i n s u p p ) ，则称x 为频繁 项目集，简称频集( 或大项目集) ，否则称x 为非频繁项目集，简称非频繁集( 或 小项目集) 。 若x 、y 为项目集，且x n y = o ，蕴涵式x y 称为关联规则，x 、y 分别 称为关联规则x y 的前提和结论。项目集x u y 的支持度称为关联规则x y 的支持度，记作s u p p o n ( x y ) ：s u p p o r t ( x j y ) = s u p p o n ( x u y ) 关联规则x j y 的置信度记作，c o n f i d e n c e f x ： c o n f i d e n c e ( x 辛y ) = s u p p o r t ( x uy ) s u p p o r t ( x ) 1 0 0 武汉理工大学硕士论文 通常用户根据挖掘需要指定的最小置信度记为i n ：m c 0 1 l f 。置信度是对关i 陕规 则可信程度的衡量，支持度是对关联规则在整个数据集中的统计重要性的衡量。 一般来说，只有支持度和置信度均较高的关联规则才可能是用户感兴趣的、f r 用 的关联规则。 支持度说明了这条规则在所有事务中有着多大的代表性，显然，支持度越大， 关联规则就越重要。有些关联规则置信度虽然很高，但支持度却很低，说明孩关 联规则实用的机会很小，一般而言不重要，但在某些情况下可能会很重要。 若s u p p o n ( x y ) m i n s u p p ，且n 王i d e n c c 岱j y ) m i n c o n f ，称关联 规则x y 为强规则，否则称关联规则x y 为弱规则。 关联规则挖掘的任务就是要挖掘出d 中所有的强规则。强规则x y 对应 的项目集( x u y ) 必定是频集，而频集( x u y ) 导出的关联规则x y 的置信 度可由频集x 和x u y 的支持度计算。因此，可以把关联规则挖掘划分为以下两 个子问题： ( 1 ) 根据最小支持度找出数据集d 中的所有频集。 ( 2 ) 根据频繁项目集和最小置信度产出关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频集，是关联规则挖掘地 中心问题，是衡量关联规则挖掘算法的标准：第二个子问题的求解是比较容易、 直接的，目前所有的关联规则挖掘算法都是针对第一个子问题而提出的，关联规 则挖掘的基本模型如图3 1 所示。 图3 1 关联规则挖掘的基本模型 图3 1 中d 为数据集，g o r i t h m 1 为频繁项目集的搜索算法，伽鼬r i t h m 2 为关联规则的产生算法，r 为挖掘出的关联规则集合。用户通过指定m i n s u p p 、 m i l l c o n f 分别与算法9 0 i i t l 髓一1 、舢g o 咖瑚2 交互，并通过与r 的交互对挖掘 结果进行解释和评价。 关联规则挖掘算法主要考虑的问题由以下两个： ( i ) 减少i 0 操作。关联规则的数据集有时可达g b 甚至t b 数量级，频繁 的i o 操作必将影响关联规则的挖掘效率，减少i ，o 操作的方法主要是减少i 描 数据集d 的次数。 ( 2 ) 降低需要计算支持度的项目集( 常称之为候选项目集) 的数量，使其 与频繁项目集的数量接近候选项目数量的降低可以节省为处理部分候选项目集 1 2 武汉理工大学母! l j 论文 所需的计算时n - j 和存储空间。 3 2 经典关联规则挖掘算法( a p r i o ri 算法) r a k c s ha g r a w a l 和r 锄a 妞s h i i 蛆s 蛹k a i l t 提出的a p r i o r i 算法是最经典的关 联规则挖掘算法。这是一个基于两阶段频集思想的方法。发现所有的有充分支持 度和置信度的关联规则，可以将这个问题分解为两个子问题： ( 1 ) 寻找那些事务的支持度超过最小支持度的项目的所有组合，把这些组 合称为大的项目集，也即频繁项目集，而其他组合称为小的项目集。在这里描述 了算法a p r ! i o i ：i 和a p r i o 栅d 来解决这个问题。 ( 2 ) 用频繁项目集产生需要的规则。一般的想法是，如果说a b c d 和a b 是大项目集，那么我们能计算比率r = 支持数( a b c d ) 支持数( a b