（计算机应用技术专业论文）基于关联规则的数据挖掘算法研究.pdf

摘要 摘要 数据挖掘是当今人工智能和数据库研究方面最富活力的领域。关联规则是数 据挖掘的一个主要研究内容。关联规则描述了给定数据项集之间的有趣联系。目 前，已经提出了许多挖掘关联规则的算法，其中最著名的是a p r i o r i 算法及其变 形。针对a p f i o f i 算法中频繁项集产生效率低和产生无用规则、丢失有用规则两 个核心问题，本文提出了两种改进的a p f i o f i 算法，它们能有效提高频繁集的产 生效率和产生更为合理的关联规则。本文主要工作包括以下几个方面。 1 、本文首先概述了数据挖掘理论和发展，以及主要的数据挖掘技术；然后 研究了关联规则挖掘的步骤。对经典的a p r i o r i 算法做了全面的分析并指出算法 的不足。 2 、 针对a p r i o r i 算法的不足，提出了一种基于事务标号集的a p r i o r i 改进 算法b t a ( b a s e do nt i d s e t sa p r i o r i ) 算法。b t a 算法的特点在于：在首次扫描 数据库生成候选卜项集的同时，记住包含每一个项集的事务标识符t i d 集合。 这样，只要统计候选项集所对应的t i d 集合的元素个数，就可以得到该候选项 集的支持度计数，从而找到频繁项集。生成下一级候选项集时，只需将用于相连 接的两个频繁项集的t i d 集合相交，就得到了该候选项集的t i d 集合。依次类 推，直到找到所有的频繁项集。与a p r i o r i 算法不同的是，b t a 算法只在产生候 选卜项集时需要遍历一次数据库，其他候选项集的支持度计算只需统计相应t i d 集合的元素个数即可，而不必象a p f i o f i 算法那样反复地遍历数据库，从而大大 节省了运行时间。相同条件下的实验结果表明，优化后的算法能有效地提高关联 规则挖掘的效率。 3 、a p f i o f i 算法认为每个数据对规则的重要性相同。但在实际应用中，用户 会比较倾向于自己最感兴趣或认为最重要的那部分项目，因此有必要加强这些项 目对规则的影响。为此，论文提出了一种基于兴趣集和权值的挖掘算法 i w a ( i n t e r e s t s e t。首先，用户提出他们感兴趣的项目，然后在数据weightapfiofi) 库中找出与该项目相关联的项目组成兴趣项扩展集，后面的挖掘工作将针对该项 目集进行。这样，利用用户的约束有效地缩小了挖掘范围。其次，通过给每个项 目赋予不同的权值来标识数据库中项目不同的重要性，使算法更切合现实，从而 发现用户需要的关联规则。 关键词数据挖掘；关联规则；a p f i o f i 算法；算法改进；加权 a b s t r a c t 曼曼! ! 詈曼! 曼皇詈鼍! 皇! 皇詈鼍i l l 一 m ；。! ! 鼍! ! 暑! 曼詈! 苎皇曼皇皇曼詈鼍皇曼曼曼皇! 曼! 曼暑曼皇詈曼詈曼曹 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 ta c t i v er e s e a r c hf i e l d s ，e s p e c i a l l yi nt h ef i e l d so f a r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s e t h ea s s o c i a t i o nr u l em i n i n gi sam a i nr e s e a r c h a s p e c to fd a t am i n i n g a s s o c i a t i o nr u l e sd e s c r i b e st h ei n t e r e s t i n gr e l a t i o n so ft h ei t e m s i nt h eg i v e ni t e m s e t s a tp r e s e n t ，l o t so fa l g o r i t h m sf o rm i n i n ga s s o c i a t i o nr u l e sh a v e b e e nb r o u g h tf o r w a r d t h em o s tf a m o u sa l g o r i g h m sa r ea p r i o r ia n di t st r a n s f i g u r a t i o n i nt h i sp a p e r , ip r e s e n tt w oi m p r o v e da p r i o r ia l g o r i t h m sa i ma tl o we f f i c i e n c yo f m i n i n gf r e q u e n ti t e m s e t sa n dc r e a t i n gu s e l e s sr u l e s ，l o s i n gu s e f u lr u l e s b a s eo nm y n e wm e t h o d ，m i n i n gf r e q u e n ti t e m s e t si sm o r ee f f e c t i v ea n d c r e a t i n ga s s o c i a t i o nr u l e s i sm o r er e a s o n a b l e t h em a i nw o r ko ft h i sp a p e ri sf o l l o w e d 1 、t h i st h e s i sf i r s ts u m m a r i z e sd a t am i n i n gt h e o r y , i t se v o l u t i o na n di t sp r i m a r y d a t am i n i n gt e c h n o l o g y ；t h e nt h es t e po fa s s o c i a t i o nr u l em i n i n gi ss t u d i e d a no v e r a l l a n a l y s i so ft h ec l a s s i c a la p r i o r ia l g o r i t h mi sm a d ea n dt h ed e f i c i e n c yo ft h ea l g o r i t h m i sp o i n t e do u t 2 、a ni m p r o v e da p r i o r ia l g o r i t h mb a s e do nt i d s e t s ，b t a ( b a s e do nt i d s e t s a p r i o r i ) ，i sp u tf o r w a r di nt h i sp a p e r , w h i c hc a l lm a k eu pt h ea b o v e m e n t i o n e df l a wo f a p r i o r iv e r yw e l l b t aa l g o r i t h mc h a r a c t e r i s t i cl i e si n ：t h et i d s e t sh a v eb e e n r e c o r d e dw h i l es c a n n i n gt h ed a t a b a s et og e n e r a t ec a n d i d a t e - 1i t e m s e t s t h u s ，t h e c o u n to fc a n d i d a t ei t e m s e t sm e m b e r si sa d d e du po n l yb yc o u n t i n gt h en u m b e ro f c o r r e s p o n d i n gt i d s e t s t h et i d s e t so ft h en e x tr a n ko fc a n d i d a t ei t e m s e t sa r eg o t o n l yb yi n t e r s e c t i n gt h et i d s e t so ft h et w of r e q u e n ti t e m s e t sw h i c ha r eu s e dt ob e l i n k e d t h er e s tm a yb ed e d u c e d b ya n a l o g y , u n t i l a l l f r e q u e n ti t e m s e t s a r e f o u n d d i f f e r i n gf r o ma p r i o r i ，b t an e e d so n l yo n ed a t a b a s es c a n ，a n dt h ec o u n to f c a n d i d a t ei t e m s e t sm e m b e r si sa d d e d u po n l yb yc o u n t i n g t h en u m b e ro f c o r r e s p o n d i n gt i d s e t s ，e x c e p t f o r t h ef i r s tt i m es c a nt oc r e a t ec a n d i d a t e 一1 i t e m s e t s t h u s ，t h et i m es p e n d i n gi sc u td o w ng r e a t l y u n d e rt h es a m ec o n d i t i o n s ，t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eo p t i m i z e da l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h e e f f i c i e n c yo fm i n i n ga s s o c i a t i o nr u l e s 3 、a p r i o r ia l g o r i t h mt r e a t se a c hi t e ma su n i f o r m i t y h o w e v e ri nr e a la p p l i c a t i o n s ， u s e r sa r em o r ei n c l i n e dt os u c hi t e m sa st h e ya r em o s ti n t e r e s t e di no rf e e lm o s t i m p o r t a n ta b o u t s o ，i t sn e c e s s a r y t o e m p h a s i z et h ea f f e c t i o no fs u c hi t e m st o r u l e s t h e r e f o r e ，t h i sp a p e rp r o p o s e so n ek i n dm i n i n ga l g o r i t h mb a s e do ni n t e r e s t s e t s a n dw e i g h t ，i w a ( i n t e r e s t s e t - w e i g h ta p r i o r i ) f i r s t l y , t h eu s e r sp r o p o s et h ei t e m 1 1 1 北京t 业大学t 学硕l ? 学位论文 w h i c ht h e ya r ei n t e r e s t e di n t h e nf i n do u tt h ei t e m sr e l a t e dt oi tf r o mt h ed a t a b a s et o c o m p o s ee x p a n s i o ns e t s o ft h ei n t e r e s t e d i t e m ，t h ef o l l o w i n gm i n i n gw o r ki s p r o c e s s e da g a i n s tt h ei t e m s e t s t h u s ，i tc a nr e d u c et h em i n i n gs c o p ee f f e c t i v e l yu s i n g u s e r sc o n s t r a i n t s e c o n d l y , i no r d e rt om a k et h ea l g o r i t h mc o r r e s p o n dw i t ht h er e a l i t y , w eo f f e re a c hi t e mad i f f e r e n tw e i g h tv a l u es ot h a ti tc a nr e p r e s e n tt h ei m p o r t a n c eo f i n d i v i d u a li t e m sf r o md a t a b a s e s i nt h i sw a y , w em a yd i s c o v e rt h eu s e f u la s s o c i a t i o n r u l e sf o ru s e r s k o w o r d sd a t am i n i n g ；a s s o c i a t i o nr u l e s ；a p r i o r i ；a l g o r i t h mi m p r o v e m e n t ；w e i g h t i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：专颏 导师签名：二鲤日期： 第1 奄 绪论 第1 章绪论 1 1 数据挖掘产生与发展 科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。 随着计算机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域越 来越广泛。大量的数据被搜集和存储在各种数据库中，并成指数性增长。让我们 来看些身边俯拾即是的现象：w a lm a r t 公司( 美国最大的零售连锁店) 每天产 生两千万个事务；又如美国航天局1 9 9 9 年发射的地球观测系统每天要产生 1 2 0 0 g b 的图像数据；还有生物学领域中数以百万计的遗传基因，世界各国定期 进行的人口普查，国土资源地理信息，铁路动态调度控制，公安司法部门的案件 处理等等都是海量数据。但是对如此众多的数据的利用还主要是检索查询，效率 很低，而且相当数量的数据具有很强的时效性，往往很多数据还没来得及分析就 已经过时，数据的价值没有得到充分利用【l 】。 面对数据的急剧膨胀和高度时效性，一方面，人们苦于不能及时得到科学决 策所必须的可靠知识，另一方面，大量宝贵的数据资源甚至还没有得到利用就已 经过时，这导致了一个新的问题，即所谓的“数据丰富，知识贫乏”问题，结果 是数据库往往变成了“数据的坟墓”，很少被人访问，决策更多地不是依赖信息， 而是依赖决策者的直觉。“我们淹没在信息之中，但仍处于知识的饥渴中 j o h e n a i s b e t t 说。我们迫切需要研究新一代数据处理技术，以提高数据的利用率。数 据挖掘技术就是在这样的背景下产生的。它的宗旨就是分析处理海量数据，以发 现有用的知识，为用户提供所需问题的答案，将“数据的坟墓”变成隐藏着知识 的“金矿”。 数据挖掘技术的产生也不是一蹴而就的，它的产生和发展其实是一个逐渐演 变的过程。电子数据处理的初期，人们就试图通过某些方法来实现自动决策支持， 当时机器学习成为人们关注的焦点。机器学习的过程就是将一些已知的并已被成 功解决的问题作为范例输入计算机，机器通过学习这些范例总结并生成相应的规 则，这些规则具有通用性，使用它们可以解决某一类的问题。随后，由于神经网 络技术的形成和发展，人们的注意力转向知识工程，知识工程不同于机器学习之 处就是直接给计算机输入已被代码化的规则，专家系统就是这种方法所得到的成 果，但由于它投资大、效果不甚理想。8 0 年代人们又在新的神经网络理论的指 导下，重新回到机器学习的方法上，并将其成果应用于处理海量商业数据。直到 1 9 8 9 年在美国底特律举行了第十一届国际人工智能学术会议，在这次会议上定 北京t 一业大学 二学坝i ：掌佗论文 义了一个新的术语，它就是数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，简称k d d 。人们接受了这个术语，并用k d d 来描述整个发现知识的 过程，包括最开始的制定业务目标到最终的结果分析，而用数据挖掘( d a t a m i n i n g ，d m ) 来描述使用挖掘方法进行数据挖掘的子过程。随后，知识发现与数 据挖掘流行起来了，大量学者及产业界参与进来，取得长足的进展。数据挖掘是 一个众多学科诸如人工智能、机器学习、模式识别、统计学、数据库和知识库、 数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前景的领域。从数 据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许 多方面【2 】1 3 【4 】。 所以，数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。从早 期的数据搜索到现在的数据挖掘大约可以分为四个阶段，如表1 1 【5 1 所示： 表1 1数据挖掘的进化历程 t a b l e1 - 1t h ee v o l u t i o no fd a t am i n i n g 发展阶段提出问题 支持技术产品厂家产品特点 数据搜索“在过去五年中我的总计算机，磁带和 提供历史性 i b m ，c d c的、静态的数 ( 6 0 年代)收入是多少?磁盘 据信息 关系数据库 o r a c l e ， 在记录级提供 数据访问 “在上海地区去年三月( r d b m s ) ，结 s y b a s e ， 历史性的、动 ( 8 0 年代)份销售额是多少?构化查询语言i n f o r m i x ， 态的数据信息 ( s q l ) ，o d b ci b m m i c r o s o f t “在上海地区去年三月联机分析处理p i l o t , 数据仓库，在各层次上回 决策支持 份销售额是多少? 老板 ( o l a p ) ，多维c o m s h a r e ， 溯的、动态的 根据此数据可以得出什数据库、数据仓a r b o t ，c o g n o s ， ( 9 0 年代)数据信息 么结论? ” 库 m i c r o s t r a t e g y p i l o t ， 数据挖掘“下个月上海地区销售 高级算法、多处 理器计算机、海 l o c k h e e d ，i b m提供预测性的 ( 正在流行)额是多少? 为什么? ” s g i 信息 量数据库 其他初创公司 从表中我们可以看到，第四步进化是革命性的，因为从用户的角度来看，这 一阶段的数据库技术已经可以快速地回答商业上的很多问题了。 1 2 传统分析方法与数据挖掘的区别 传统分析方法包括查询、报表、联机应用分析等，它与数据挖掘的本质区别 第1 荦 绪论 是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到 的信息应具有先前未知性、有效性和可实用性三个特征。先前未知性是指挖掘出 的信息是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或 知识，甚至是违背直觉的信息或知识。挖掘出的信息越是出乎意料，就可能越有 价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布 和啤酒之间有着惊人的联系。有效性是指挖掘出的信息必须是有效信息，无效信 息对我们是没有任何价值的。可实用性是指挖掘出的信息必须能应用于实际的操 作，指导实际的决策。 1 3 数据挖掘的研究现状 从出现数据挖掘至今，由美国人工智能协会主办的k d d 国际研讨会已经召 开了1 8 次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从 发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的 相互渗透。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把 数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。 除此之外，在i n t e m e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威( h t t p ：w w w k d n u g g e t s c o r n s u b s c r i b e h t m l ) 。在网上 还有许多自由论坛，如d me m a i lc l u b 等。至于d m k d ( d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y ) 书籍，可以在任意一家计算机书店找到十多本。目前，世 界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公 司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、还有c o v e r s 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 b m i n e r 、q u e s t 等。 h t t p ：w w w d a t a m i n i n g l a b c o m 网站为用户提供了许多数据挖掘系统和工具的性能 测试报告。 我国的数据挖掘研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了知 识发现和数据挖掘的的基本框架。自9 0 年代中期一批研究成果( 学术论文) 逐渐 发表计算机学报、计算机研究与发展、软件学报、人工智能与模式识别 等刊物上，研究重点也正在从发现方法转向系统应用，并且注重多种发现策略和 技术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术研究为主， 实际应用上处于起步阶段。1 9 9 3 年国家自然科学基金首次支持对该领域的研究 项目目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应 用研究，研究涉及的领域很多，一般集中于算法的研究，数据挖掘的实际应用以 及有关数据挖掘理论方面的研究，如北京系统工程研究所对模糊方法在知识发现 中的应用进行了较深入的研究；北京大学也在开展对数据立方体代数的研究；华 北京t 业大学t 学硕l j 学位论迂 中科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大 学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川大学和上海 交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 挖掘。但是到 目前为止还没有商用工具问世，像复旦大学设计的基于关联规则的数据挖掘工具 a r m i n e r 等也只是处于实验室研究阶段。与国外相比，国内对d m k d 的研究还 没有形成整体力量【6 】o 1 4 数据挖掘中的关联规则 数据挖掘可以采用多种技术对数据进行分析处理，其中，关联分析是最重要 的技术之一。关联规则是由i b m 研究中心的r a g r a w a l 等人于9 0 年代初期提出 的1 7 1 ，它主要用来发现数据项之间的关联关系，如购买面包和黄油的人有9 0 的 可能性购买牛奶。发现这些项目之间的关联关系，则可以用来指导超市管理人员 的决策，如对于刚才发现的关联规则，超市人员就可以有针对性地进行货物的摆 放，可以把面包、黄油和牛奶摆放在一起，或者将面包、黄油和牛奶分别放在货 物架的两端。这样，对于前者，顾客一进入超市，就能很快地购买到他们需要的 东西，为顾客购物提供方便；而对于后者，顾客在购买的过程中会途经一些地方， 顺便会购买一些其他东西，带动了其他商品的销售。 关联规则已经成功地应用到市场购物分析中，至今已提出了很多的关联规则 挖掘算法，如a p r i o r i 引、d h p 们、f p g r o w t h 1 0 】等算法，这些算法从不同角度来 挖掘关联规则，有的从深度，有的从广度进行挖掘，取得了一定的成效。目前， 挖掘关联规则的技术正处在一个不断发展的过程中，有着很好的发展前景。对关 联规则的应用也已从最初的商业指导到生活中其他领域，如教育、科研、医学等。 1 5 本文的主要工作 数据挖掘是数据库研究、开发和应用最活跃的分支之一，同时也逐渐成为整 个计算机科学中的一个重要领域。关联规则挖掘是数据挖掘最重要的研究方向之 一，也是一个处于不断发展过程中的研究方向。正是出于对这项技术的兴趣，我 选择了这个命题作为自己的研究课题。 本文的研究工作源于上述的背景，经过一段时间的资料查阅、理论研究和与 指导教师及同学的讨论后，我对关联规则挖掘这一技术有了自己的一些心得与体 会。在总结这些心得的基础上，我撰写了“基于关联规则的数据挖掘算法研究” 的毕业论文。目的是对数据挖掘进行深入的研究，针对数据挖掘中的关联规则经 典算法a p r i o r i 算法的缺陷，探讨优化问题，以提高算法的挖掘效率和挖掘 质量，本文主要做了以下几方面的工作： 1 、数据挖掘背景与现状研究。在介绍数据挖掘研究背景的基础上，分析了数据 挖掘的现状并引出了关联规则研究的现实意义。 2 、数据挖掘技术的研究。对数据挖掘的基本概念、挖掘过程、系统总体结构、 任务、常用技术及实际应用做了简单介绍，并指出数据挖掘的研究方向。 3 、关联规则分析与研究。在介绍关联规则基本概念的基础上，对概念所涉及的 术语及性能进行了说明，对关联规则的性质做了详细的介绍，对关联规则发现任 务和价值衡量标准进行简单概括，对关联规则典型算法做了总结。 4 、关联规则挖掘经典算法a p r i o r i 算法的分析与研究。在介绍a p r i o r i 算法思想 的基础上，给出了算法的流程及算法的伪代码，并通过个具体实例来演示算法 的挖掘过程，然后分析a p r i o r i 算法的优缺点，提出该算法的性能瓶颈。 5 、a p r i o r i 算法的改进。首先，研究了a p r i o r i 优化算法的现状，然后针对a p f i o d 算法的不足，本文提出了一种高效的关联规则挖掘算法b t a ( b a s e do nt i ds e t a p r i o r i ) ，通过候选集项目的事务标识符集做交运算的方法计算支持度，而不必 每次计算支持度时都要扫描整个数据库，通过实验对b t a 算法与a p r i o r i 算法的 效率进行比较，证明b t a 算法提高了运行效率。 此外，为改善a p r i o r i 算法挖掘质量，从数据约束角度考虑改进算法，提出 i w a ( i n t e r e s t s e t 目找出数据库中的相关项组成兴趣项扩展集，这样会减小挖掘规模，提高算法效 率。然后对兴趣项扩展集中的项目根据重要程度分别赋以不同的权值，区别对待 每个项目，从而可以挖掘出用户关心的具有价值的关联规则，提高挖掘的质量。 第2 章 数据挖掘技术 第2 章数据挖掘技术 2 1 数据挖掘的定义和特点 数据挖掘是一类深层次的数据分析方法，被认为是解决“数据爆炸知识贫乏 的有效方法之一，在最近几年里已被数据库界广泛研究。 从广义上讲，数据挖掘( d a t am i n i n g d m ) 是指从大量的、不完全的、有 噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程。这个定义包括以下四个层次的含义： 1 、数据源必须是真实的、大量的、含噪声的； 2 、发现的是用户感兴趣的知识； 3 、发现的知识要可接受、可理解、可运用，最好能用自然语言表达结果； 4 、并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学 定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是 有特定前提和约束条件、面向特定领域的。 数据挖掘是一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数 据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 通过数据挖掘，有价值的知识、规则、高层次的信息就能从数据库的相关数据集 合中抽取出来，并从不同角度显示。这些挖掘出来的规则蕴涵了数据库中一组对 象之间的特定关系，揭示出一些有用的信息，为经营决策、市场策划、金融预测 等提供依据。 数据挖掘的特点如下： 1 、处理对象为大规模数据库，数据规模十分巨大； 2 、信息查询一般是由决策指定者( 用户) 提出的即时随机查询，往往没有 精确的查询要求，需要靠数据挖掘技术寻找用户可能感兴趣的东西： 3 、在一些应用中，某些行为并没有实际发生或者很少发生，因而它们对输 出所造成的影响没有在数据库中体现出来，需要利用数据挖掘技术从数据库中提 取有用的规则，为这种情况提出预测； 4 、在一些应用中，由于变化迅速，数据可能很快过时，因此要求数据挖掘 技术能很快对数据变化作出反应以提供决策支持，数据挖掘既要发现潜在的规 则，还要管理和维护规则，而规则是动态的，当前的规则只能反应当前状态的数 据库特征，随着新数据的不断加入，规则需要随之更新； 5 、数据挖掘中规则的发现主要基于大样本的统计规律，发现的规则不必适 用于所有的数据，当达到某一个阀值时便可认为有此规律。 22 数据挖掘的过程 从知识发现的角度，可以把数据挖掘视为数据库中知识发现过程的一个基本 步骤。一般知识发现的过程山以下几个步骤组成，如图2 1 所示： r * 1 1 , 图2 一i 数据挖掘的过程 f i g u r e2 - 】t h ep r o c e s so f d a t a m i n i n g l 、数据清理与集成：消除噪声或不一致的数据，将多种数据源可以组合在 一起； 2 、数据选择与变换：从数据库中检索与分析任务相关的数据，将数据变换 或统一成适合挖掘的形式，如通过汇总或聚类操作： 3 、数据挖掘：基本步骤，使用智能方法提取数据模式； 4 、模式评估与表示：根据某种兴趣度量识别表示知识的真正有趣的模式， 使用可视化和知识表现技术，向用户提供挖掘知识。 23 数据挖掘系统总体结构 数据挖掘步骤町以与用户或知识库交互。有趣的模式提供给用户，或作为新 的知识存取放在知识库中。从数据挖掘的广义观点来看，数据挖掘是从存放在数 据库、数据仓库、或其他信息库中的大量数据中挖掘有趣知识的过程。基于图 2 - 1 所示的数据挖掘过程，一个典型的数据挖掘系统应具有以下主要结构，如图 2 - 2 所示。 第2 章数据挖掘技术 图2 - 2 典型的数据挖掘系统 f i g u r e2 - 2t h et y p i c a ld a t am i n i n gs y s t e m 根据文献【l l 】可知，典型的数据挖掘系统具有以下主要部分： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、 电子表格或者其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓 库服务器负责提取相关数据。 知识库：这是领域知识，用于指导搜索或评估结果模式的兴趣度。这种 知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户确信的 知识也可以包含在内。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此部分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式 评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 对于有效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中，以便将 搜索限制在有兴趣的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系 统交互，指定数据挖掘任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结 果进行探索式数据挖掘。此外，此部分还允许用户浏览数据库和数据仓库模式或 者数据结构，评估挖掘的模式。 北京t 业大学工学硕士学位论文 2 4 数据挖掘的任务 数据挖掘技术来自应用的需要，要对这些数据进行微观、中观乃至宏观的统 计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联， 利用已有的数据对未来的活动进行预测。所以数据挖掘任务一般可以分为两类： 描述和预测。描述性挖掘是刻画数据库中数据的一般特性。预测性挖掘任务是对 当前数据进行推断，以进行预测。数据挖掘的任务主要包括( 1 2 1 ： l 、分类( c l a s s i f i c a t i o n ) 。其目的是得到一个分类函数或分类模型( c l a s s i f i c a t i o f m o d e l ，也称为分类器) ，该模型能按照事先定义的分类标准，把数据库的数 据项映射到给定类别中的某一个，即对数据进行归类，而且能够把分类模型，对 其他未分类的或是新的数据做出预测。使用的技术有决策树( d e c i s i o nt r e e ) ，记 忆基础推理( m e m o 巧b a s e dr e a s o n i n g ) 等。例如：可以根据已有的个人住房贷款 的历史数据，来建立一个借款人信用风险等级分类模型，把贷款申请人的风险等 级划分高、中、低三级，以后就可以利用这个模型来对数据库的其他申请者或是 新的申请者做出预测。 2 、聚类( c l u s t e r i n g ) 。是把一组个体按照相似性归纳成若干类别，即“物以 类聚”。它的目的是使属于同一类别的个体之间的距离尽可能的小，而不同类别 的个体间的距离尽可能的大。例如，一些特定症状的聚集可能预示了一个特定的 疾病；租借图书类型不相似的客户聚集，可能暗示成员属于不同的文化群。 3 、关联和序列发现( c o r r e l a t i o nd i s c o v e r y ) 。决定哪些事情将一起发生。是形 式如下的一种规则，“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶” ( 面包+ 黄油+ 牛奶) 。关联规则发现的思路还可以用于序列模式发现。用户在购买 物品时，除了具有上述关联规律，还有时间或序列上的规律。例：超市中客户 在购买a 的同时，经常会购买b ，即a = b ( 关联规则) 。客户在购买a 后，隔 一段时间，会购买b ( 序列分析) 。 4 、估计和预钡j j ( e s t i m a t i o na n dp r e d i c t i o n ) 。估计是根据已有的长期累积的资 料来推测某一属性未知的真值。例如按照贷款申请人的教育程度、年龄及收入来 推估贷款的金额。使用的技术有回归分析和人工神经网络等。预测是根据对象属 性过去观察值来估计该属性未来的值。例如由借款人的过去还贷款情况来预测其 未来的还贷款情况( 及时还贷款还是拖欠贷款) 。使用的技术有回归分析、时间序 列分析及人工神经网络等。 5 、描述( d e s c r i p t i o n ) 。描述的功能是对复杂的数据库提供简要的描述，提供 诸如汇总，均值，方差等。这个功能的主要目的是当未来使用别的功能时对数据 先有较好的了解。在建立任何模型之前先做数据描述的工作是十分重要的，将会 指导如何去建模。 第2 章数据挖掘技术 6 、偏差分析和异常检验( d e v i a t i o na n df r a u dd e t e c t i o n ) 。数据库中的数据常 有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识， 如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值 随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的 差别。例如：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经营， 就要发现这5 0 0 例的内在因素，减小以后经营的风险。 2 5 数据挖掘的技术及其应用 根据数据挖掘的任务和模型，通常采用的技术是贝叶斯网络、决策树、遗传 算法、神经网络和统计分析、粗糙集方法、关联规则分析。 贝叶斯网络i l 列是用来表示变量集合的连接概率分布的模型，它提供了一种 自然的表示因果关系的方法。贝叶斯网络本身并没有输入和输出的概念，各结点 的计算是独立的，因此，贝叶斯网络的学习既可以由上级结点向下级结点推理， 也可以是由下级结点向上级结点推理。 贝叶斯网络最初是由rh o w a r d 和j m a t h e s o n 于1 9 8 1 年提出，后来c o o p e r g 与h e r s k o v i t s e 给出了b d ( b a y e s i a nd i r c h l e t ) 度量模型【l4 1 ，h e c k e r m a n d 等扩展 了b d 的思想【1 5 1 。贝叶斯网络其它方向的研究也层出不穷，例如非线性动态模型 的g i b b s 抽样模型【1 6 】，贝叶斯分类剁1 7 】0 8 1 等等。 决策树f 1 9 】方法首先选择训练样本的一个子集以形成一个决策树，如果此树 没有为所有的对象给出一个正确的答案，则将例外情况加入树中，不断重复这一 个过程，直到发现正确的决策集。最终形成这样一颗树：每一个叶子代表一个类 名，每一个内部节点描述一个属性，节点的每一个分支代表对应于该属性的每一 个可能的值。i d 3 t 2 0 1 算法是一个决策树中最基本的算法，c 4 5 【2 1 】也是一个非常经 典的算法。 遗传算法【2 2 】是模拟生物进化过程的算法。由3 个基本算子组成。繁殖( 选择) ： 是从1 个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过程。交 叉( 重组) ：选择2 个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个体。 变异( 突变) ：对某些个体的某些基因进行变异( 1 变0 ，0 变1 ) 。这种遗传算法 可以起到产生优良后代的作用。这些后代满足适应度值，经过若干代的遗传，将 得到满足要求的后代( 问题的解) 。遗传算法已在优化计算和分类机器学习方法 方面显示了明显的优势。 神经网络方法【2 3 】是基于生物神经系统的结构和功能而建立起来的，模拟人 脑神经元的方法。以m p 模型和h e b b 学习规则为基础，可以建立三大类神经 网络模型：前溃式网络( 以感知机、反向传播模型、函数型网络为代表，可用于 预测、模式识别等方面) ，反馈式网络( 以h o p f i e l d 的离散模型和连续模型为代 北京工业人学t 学硕 二学位论文 表，分别用于联想记忆和优化计算) ，自组织网络( 它以a r t 模型、k o h o l o n 模型 为代表，用于聚类) 。利用神经网络所固有的并行结构、并行处理、自适应性、 知识的分布存储、较强的容错性、本质的非线性系统等特性，通过网络训练，可 以建立数据库信息的非线性模型，并从中提取相应的规则。 粗糙集方法 2 4 1 是利用模糊集理论对实际i a j 题进行模糊评判、模糊决策、模 糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确能 力就越低，即模糊性就越强。 关联规则1 25 j 是由r a k e s ha g r a w a l 等人首先提出的。两个或两个以上变量的 取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、 可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是 找出数据库中隐藏的关联网。一般用支持度和置信度两个阀值来度量关联规则的 相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。关 联规则是本文重点讨论的内容，我们将在后面章节展开讨论。 近年来随着数据库和网络技术的广泛使用，加上使用先进的自动数据采集工 具，人们所拥有的数据量急剧增加，使得数据挖掘技术得到广泛的应用。如零售、 金融保险、产品制造、电信、科学研究等行业。文献【2 6 】列举了数据挖掘技术的 一些应用领域，见表2 1 。 表2 1 数据挖掘的应用领域表 t a b l e2 ld a t am i n i n ga p p l i c a t i o nf i e l d s 技术方法主要功能和特点主要应用领域 关联分析分类、聚类零售业、保险业和制造业 决策树归类分类，可理解性制造业、医学和零售业等 遗传算法聚类、优化、高效性金融业、保险业和农业等 贝叶斯网络分类、聚类和预测，易理解医学、制造业和电信业 粗糙集方法不确定分类零售业、金融业和制造业 神经网络预测、分类、聚类、解