（计算机软件与理论专业论文）关联规则挖掘算法的研究及其应用.pdf

出东师范大学硬士学位论文 关联规则挖掘算法的辑究及其应用 摘要 遮若数攒痒应溺瓣不甄深入，数援瘴的瓶攘惫巅彩浆，入们需要对这些数据 进行分析，从中发现有价值的信息。数据挖掘致力于数据分析和理解、揭示数据 内部蕴藏的知识。近年来，它的发震已经弓 藤了信息产韭界的极大关注，毒鬻广 阔的应用前娥，并成为当今研究的热点。关联规则是数据挖掘领域中的一个非常 重要的研究课题，广泛应用于各个领域，既可以检验行业内长期形成的知识模式 也能够发现隐藏的规律。有效地发现、理解、运翅关联趣则是完成数握挖掘 鼍务 的重爱手段，因此对关联规则的研究具有重要的理论价值和现实意义。 本瀑题印黯数攥挖摅中的关联援粼送行系统磅究，主要镪括以下内容： i 、数据挖掘技术的分析与研究。对数据挖掘技术的产生进行了简要的回顾， 在爨鑫数据挖穗基本概念静鏊疆上，对数蠢撼据静对象、可发瑷静模式耱经常使 用的技术进行了详细的分类和总结。分析了数据挖掘技术的研究现状，对数据挖 掘技术的热点研究领域进行了探讨，为本课题的全磷开展奠定了基确。 2 、关联规则的研究与分橱。在对现有的关联规则文献磷究的基础上：本文 对关联规则的种类进行了全面地分类和总结，详细地介绍了关联规则的基本概念 窝基本性曩，对关联媲列豹蹙墼挖掘龚法及葵基本思想送行了分辑秘薹艿究，讨论 了提高该算法效率的各种优化技术，并且客观地分析了它们的优缺点。 3 、在传统兹关联麓翻擒疆算法中，广泛采焉了“支持发餮铸发”韵谮侩 标猴。然而在很多时候，挖掘出来的关联规则其支持度和置信度都很高，却没有 实际意义。针对上述问题，本文弓l 入了关联戒则的一个兴趣废的度量相关支 持瘦s 。) ，将支持躞、置信发秘掘关支持度起终为有效关联翅则的谔侩探准。 4 、分析经典频繁项集挖掘算法a p r i o r i 算法，针对该算法中存在的效率瓶颈 问憨，提岛了个改进静挖瓣算法- - m ma p r i o r i ( m u l t i p l y _ m a t r i x a p r i o r i ) ，并 实现了该算法。改进后的算法通过频繁l 一项袋生成矩阵的转置m 1 与矩阵m 相 乘来获得频繁2 项檠，从而减少了a p r i o r i 鲜法生成频繁2 ，项集的时间开销。理 论积实验证明，改进豹算法具有良好的性能。 山东师范大学硕士学位论文 5 、对关联规则挖掘在商业决策中的应用做了一定的研究。我们选取一个实 际的超市销售数据库做为挖掘对象，采用v c + + 6 0 作为开发工具，在m i c r o s o f t w i n d o w s2 0 0 0s e r v e r 、m i c r o s o f ts q ls e r v e r2 0 0 0 系统环境的基础上，构造了一 个简单的关联规则挖掘系统，利用m ma p r i o r i 算法挖掘出顾客购买的商品与商 品之间的潜在联系，使理论研究上升到了实际应用。 关键词：数据挖掘；关联规则；频繁项集；m m _ a p r i o r i 算法 分类号；t p 3 1 1 山东师范大学硕士学位论文 t h er e s e a r c ha n d a p p l i c a t i o no nt h ea l g o r i t h m so fm i n i n g a s s o c i a t i o nr u l e s a b s t r a c t w i t ht h ee x t e n s i v eu s eo fd a t a b a s e ，t h es c a l eo fi te x p a n d sq u i c k l y i ti sn e c e s s a r y t oa n a l y z et h e s ed a t aa n de x p l o r ev a l u a b l ei n f o r m a t i o nf r o mt h e m d a t am i n i n gi sa t e c h n i q u et h a ta i m sa ta n a l y z i n gd a t aa n dc o m p r e h e n d i n ga n dd i s c o v e r i n gt h eh i d d e n k n o w l e d g eo fd a t a d a t am i n i n gh a sa k e a d ya r o u s e dt h ei n f o r m a t i o ni n d u s t r i a lf i e l d e n o r m o u si n t e r e s ta n dw i l lh a v eaw i d ea p p l i c a t i o np r o s p e c ti nt h ef u t u r e b e i n ga n e x t r e m e l ye s s e n t i a lr e s e a r c ht o p i ci nd a t am i n i n g ，a s s o c i a t i o nr u l e sm i n i n gi sw i d e l y a p p l i e di nv a r i o u sf i e l d s a s s o c i a t i o nr u l e sm a yb o t he x a m i n et h ek n o w l e d g ep a t t e r n f o r m e df o ral o n gt i m ei nt h ep r o f e s s i o na n dd i s c o v e rt h es e c r e tn e wr u l e s t h e d i s c o v e r y , c o m p r e h e n s i o na n da p p l i c a t i o no fa s s o c i a t i o nr u l e sa r ei m p o r t a n tm e a n so f a c c o m p l i s h i n gt h et a s ko fd a t am i n i n g t h e r e f o r e ，t h er e s e a r c ho fa s s o c i a t i o nr u l e s m i n i n gi so fg r e a ti m p o r t a n c ei nb o t ht h e o r e t i c a lr e a l ma n dr e a l i s t i cr e a l m t h i sp a p e rc o n d u c t sas y s t e m a t i cr e s e a r c ho nt h ea s s o c i a t i o nr u l e sm i n i n gm a i n l y i n c l u d i n gt h ec o n t e n ta sf o l l o w s ： 1 t h ea n a l y s i sa n ds t u d yo fd a t am i n i n gt e c h n o l o g y t h i sp a p e rg i v e sab r i e f r e t r o s p e c to nt h eh i s t o r yo fd a t am i n i n gt e c h n o l o g y b a s e do nt h ef u n d a m e n t a l c o n c e p t so fd a t am i n i n gt e c h n o l o g y ，ad e t a i l e dc l a s s i f i c a t i o na n ds u m m a r yo nt h e o b j e c t so fd a t am i n i n g ，d e t e c t a b l ep a t t e r n sa n df r e q u e n t l yu s e dt e c h n i q u e sh a v eb e e n t a x i e do u t i ns u c c e s s i o n ，t h i sp a p e ra n a l y s e sa n ds t u d i e st h ec u r r e n ts t a t u so fd a t a m i n i n gt e c h n i q u ea n dd i s c u s s e si t sh o tr e s e a r c hf i e l d s a l lo ft h ea b o v ep r o v i d eab a s e f o rt h eo v e r a l le x p a n d i n go ft h i sp a p e r , 2 t h es t u d ya n da n a l y s i so fa s s o c i a t i o nr u l e s ac e r t a i ne x t e n ti n t r o d u c t i o no n a s s o c i a t i o nr u l e sm i n i n ga n di t sa l g o r i t h m sa sw e l la si t ss l i e c i e sa r eg i v e no nt h e g r o u n do fc u r r e n tr e s e a r c ho fa s s o c i a t i o nr o l e sd o c u m e n t s a n dt h ef u n d a m e n t a l c o n c e p t sm a de s s e n t i a lp r o p e r t i e so fa s s o c i a t i o nr u l e sa r ee x p l a i n e di nd e t a i l i n 山东师范大学硕士学位论文 a d d i t i o n ，t h et y p i c a lm i n i n ga l g o r i t h ma n di t sf u n d a m e n t a li d e a so fa s s o c i a t i o nr u l e s a r ea n a l y z e da n ds t u d i e di nt h i sp a p e r a l lk i n d so fo p t i m i z e dt e c h n i q u e sd e s i g n e dt o p r o m o t et h ea l g o r i t h mse f f i c i e n c ya r ea l s os t u d i e da n dd i s c u s s e di nd e t a i lh e r ea n da t t h es a m et i m et h e i rm e r i t sa n dd e f e c t sa r ea n a l y s e do b j e c t i v e l y 、 3 t h ee v a l u a t i o nc r i t e r i ao fa s s o c i a t i o nr u l e sa l eb a s e do ns u p p o r ta n d c o n f i d e n c ei n e x i s t i n g a s s o c i a t i o nr u l e m i n i n ga l g o r i t h m s h o w e v e r , t h e m i n e d a s s o c i a t i o nr u l e sw i t hh i g hs u p p o r ta n dc o n f i d e n c ea r eu s e l e s ss o m e t i m e s t h i sp a p e r i n v e s t i g a t e st h el i m i t a t i o no ft h ep r e s e n tc r i t e r i o no ft h ee v a l u a t i o no fa s s o c i a t i o nr u l e a n di n t r o d u c e sa n o t h e rm e a s u r e m e n ts t a n d a r do fa s s o c i a t i o nm l e r e l a t i v e s u p p o r t ( 品) ，m a k i n gs u p p o r t ，c o n f i d e n c ea n dr e l a t i v es u p p o r tt o g e t h e r a st h e e v a l u a t i o nc r i t e r i ao f v a l i da s s o c i a t i o nm l e s 4 t h ec l a s s i c a la l g o r i t h mo fa s s o c i a t i o nr u l e sm i n i n 磬a p r i o r ii sa n a l y z e di n t h i sp a p e r a ni m p r o v e da n df a s t e rm i n i n ga l g o r i t h mi sp u tf o r w a r d - - m m a p r i o r i ( m u l t i p l ym a t r i xa p r i o r i ) i n t h i sa l g o r i t h m ，w ec a ng e tt h ef r e q u e n t2 - i t e m s e t sb y m u l t i p l y i n gt w om a t r i x e s b o t ht h et h e o r y a n dt e s t s p r o v et h a t t h i s i m p r o v e d a l g o r i t t u nh a sf a v o r a b l ep e r f o r m a n c e 5 as t u d yo fa s s o c i a t i o nr u l em i n i n gu s e di nc o m m e r c ei sc o n d u c t e d as a l e d a t a b a s eo fas u p e r m a r k e ti nl i f eh a sb e e nc h o s e na sam i n i n go b j e c t b yu s i n g m i c r o s o f tv c + + o nm i c r o s o f tw i n d o w s2 0 0 0s e r v e r , m i c r o s o f ts q ls e r v e r2 0 0 0a n d t h em m _ a p r i o r ia l g o r i t h m ，t h ep o t e n t i a lr e l a t i o n sb e t w e e nt h ec o m m o d i t i e sa l e w o r k e do u t ，m a k i n gt h e o r e t i c a lr e s e a r c hm o v i n gu pt ot h ep r a c t i c a la p p l i c a t i o n k e y w o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e ；f r e q u e n ti t e m s e t ；m ma p r i o r ia l g o r i t h m c l a s s i f i c a t i o n ：7 f p 3ll 4 独创声明 本人声明所呈交的学位论文是本人在导师指导_ 进行的研究工作及取得的 研究成果。掘我所知除_ ，文：p 特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究战果也不包含为获得( 泣：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我闹工作的同志对本研究所做的任何贡献均己任论文中作了明确的说明 并表示谢意。 学位论艾作笛簦名：高日a 导师签亨 学位论文版权使用授权书 本学位论文作者完全r 解一兰鱼有关保留、使用学位论文的舰定有权保 留并向凶家有关部门或机构送交论文的复印件和磁盘，允询- 论文被查阅和借阅。 本人授权学撞可以将学位论文的令部或部分内容编入有芙数掘库进行检索，可 以采序影印、缩印域扫描笔复制手段倪存、f 编学位论文。( 保密的学f 口沦文在 解密后适用小授权 s ) 学位论义作：肯签名：高日r 签字卜 期：2 0 0 占年；月门r 导师签字 签字n 期：2 0 06 年期7 r f l b 东师范大学硕士学位沦x 第一章绪论 数据挖掘之所以被称为未束信息处理的骨干技术之，：卜爱在j 。它以一利，个 新的概念改变着人类利用数据的方式。二十1 l ： = 纪，数据库技术l ) ( 得了决定性的成 果片且得到了厂泛的应川，但作为种基本的信息存储和管理力式，数据库技术 缺少刈决策、分析、预测等高级功能的支持机制。众所周矢，随着数拼库容圩 的 膨胀，特别足数= i ) l i 仓j t i ( d a t aw a r e h o u s e ) 以及w e b 等新型数据濒的| 益普及，联 机分析处i po l a p 、决策支持以及分类、聚类等复杂心用成为必然。m 】对这挑 战，数| l ! ：挖掘年1 l 知识发现( k n o w l e d g ed i s c o v e r y ) 3 术j 通运m 生井显示出强大的 生命，j 。数掘挖掘用1 知i i = ! = 发现使数掂处理技术进入j ，一个史高级的阶段，它小仪 能刘过上的数掘进行直咖，并且能够找出数扔：之m 的潜在联系，进行史r 岛层次的 分析，以便更好地做i j 理想的决策，预测未来的发展趋辨等。 1 i 数据挖掘简介 我们现仃。t 活往一个网络化的时代，通信、计算机和网络技术i e 改变着整个 人类社会，最明移的是存这些技术的_ ! f 【i 助f 、人们产：尘和收集数掘的能力迅速提 岛。随着人们获取数据_ f 段的多样化，人们积累的数抛越来越多。数据的背后隐 减甜订：多互受信息，人们葡颦能够埘其进行更高层次的分 j ，以便史盘了地秘川这 些数掘。例如，股票经纪人需要从f i 平j 月累的人最股票行情变化的历史也录巾发 现其变化规律以预测未来趋势；超市的经理人奠希望能够从过女j i j l z 的销售记 录中分析出膨! 客的消费习惯和 j ：为，以便及时变换营销策略：电话公刊通过研究 提供多项服务，以实现捆绑销售；地质学家想通过分析地球资源卫星发挥的大量 数j l 一：和照片来发现有j - t 采价值的矿物资源等。然而，多数数据库系统一叮以高效地 史现数抛的录入、修改、查i f 】、统计等功能，仙无法发现数揠j ：中存在的关系和规 则，_ 尢法根抛现自的数掘颅测未来的发展趋势。， 一门新兴的自动信息提j 双技术一数掘挖掘技术t i ：是存这样的需求背景卜 应运而生，并得以蓬勃发展，越来越显示出其盟大的生命力。1 9 8 9 年8 月f j l ： 的第l l 届幽际人i2 智能联合会议卜苒次提 也了k d l ) ( 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 ，数掘库中的知识发i 见) 的概念，随后引起了国际人上智能和数扒库等领 l l j 寐师范火学节! 士学位沦文 域专家的广泛哭泣。| i 前，数掘挖执的研究l 经取得了 硕的成果。从技术办面 水石，数掘挖掘是描从数拥席或数抛仓库中的数抛非平儿地提取隐含的、以拍未 知的、具自潜在麻川价值的信息的过程，“非、r 儿”的意思是采用一定的技术和工 具进行挖掘。数掘挖掘作为。新兴的边缘学科，礼：集厂来自数据库技术、统 计学、机器学习、高性能计算、校式识别、神经嘲络以及管理信息系统等各学科 的研究成果。其发现的知识可以刖于决策、过程控制、1 矗息管理、查询处理等方 面f 具有熏耍的实践意义。 数据挖赫l 从八十年代提出到现在，小过短短寸多年的时问但其应用已非 常广泛4 i 仅用j ：科研领域，在商业领域的应用也毫不逊色，尤其足用于银行、 电信、保险、交通、零岱( 如超级市场) 等领域。数抛挖掘所能解决的典型商g k 问 题包括：敛就c 库营 ! f i ( d a t a b a s em a r k e t i n g ) 、客户 f _ 体e q s ) ( c u s t o m e rs e g m c n t a t i n n c l a s s f i c a t i o n ) 、背擐分析( p r 0 6 l ca n a l y s i s ) 、交义销售( ( ：r o s s s c l l i n g ) ! q 市场分析 行为，以及客户信用i 己3 ) ( c r e d i ts c o r i n g ) 、欺计发现( f r a u dd e t e c t i o n ) 等等。山于 数据挖掘在决策支持、市场营销、零售产、l p 及会融预测等领域只自广阔的应f j 前 景，数掘挖掘已经成为了数据库及相关领域的+ 个研究热点。 1 2 关联规则挖掘简介 笑联规则是数掘挖掘的众多知识类型中最为典型的种。，关联规则挖_ 拄i i ( a s s o c i a t i o nr u l e sm i n i n g ) 是数掘挖掘的一个蓖耍分支。该 日题于1 9 9 3 年刚 a g r a w a l “等人在对市场9 1 f ；j 物篮问题( m a r k e t b a s k e t a n a l y s i s ) 进行分析时苗次提 j l ；，川以发现商 销售中顾客的购炙形， 仆么足关联姚9 1 ? 关联规! i l | j 就是为了挖掘m 隐臧在数欹f ：问的十n 互灭系。从一 组给定的数抛项以及交易集合中，分析m 数抛项集在交易集合中h ：玑的频度关 系。著名的“啤酒和尿和”就是一个父联规则的例了，啤酒和尿布分别是一个数抛 项集通过关联分析，发现这两个数据项集之间潜住的灭系，以指导销售实践。 通过关联规则的挖掘可以发现数据库项目叫定的内在联系，能有效的提高 j 越j 卡】系统的决策支持能力。在客户关系管理、零售、i p 等方而，关联规则挖掘能找 出产品销售模式、客、的! i ! j 涎习惯、客户特性等，从而制定相应的商业决策，如促 销方案的制定、客户服务决策的分丰i 等。 山东师范大学硕士学位论文 对芙联规则挖掘的研究t 要足对关联舰则挖掘算法的研究，挖掘算法的效率 和健壮性自接影响着关联规! i ! i j 挖掘的应用。 1 3 关联规则挖掘算法的研究现状 天于知识发脱和数掘挖扭m f 究，幽内尚处 二起步阶段，l 卅外则l 足热门研 究方向，达至i j 了一定的水、f ，m 1 1 很多研究成果都已经投入j 实际应用领域。 天联规则挖掘的概念及其算法最早是由i b ma l m a d e nr e s e a r c hc e n t e r 的 a g r a w a l 等人提；l 的。自从1 9 9 3 i 以来，数 l ! ：挖掘领域的研究者住哭联规则挖 掘的 i j f ：究上作了大量的工作，使之成为- - + t 具有实际意义的数据挖掘技术，其中 i 要的工作有：经典f f ja p r i o r i 算泌：3 及其衍生算法“、并行挖掘算法”“”“、 黄化关联规! i ! | j 挖掘算法：”以及增量挖掘算法“3 。”1 等。挖掘方式主要有：自j 氐 向i ：型( 典型的有a p r i o r i 算法及其扩展算法) 、白顾向卜型( 舆型的有f p g r o w t h 算法93 ) 。日i m ，一般关联规则挖掘算法足从人嚣的数掘中挖掘天联胤则，以体现 。个数j ；：库中数掘项m 联系的舰律。a p r i o r i 箅法通过对数掘库进彳r 多次j 1 描， 反复迭代at 产，i ：数抛i 口! 集的全部频繁项集。挖掘基于约束的关联规则”3 是 关l 爻规则挖掘发腱的”一个重要方向。数据项存概念上可以有多个层次“， 例如笳克、西服等“j 以酱遍化为外农，衬衫、衬裤u j 以普遍化为内衣，外农、内 衣t j j 以普遍化为服装。刁i 同概念辰次数掘l 贞问的关联规则转化为普遍化关联规 则，这也是研究的热点问题。另外，引入各种评测参数( 比如兴趣度) “”的天联 规则挖掘算法，以及随着o l a p 技术的成熟和应用，将o l a p 技术和关联规则 挖掘桐宝 ；合，也成为近年来人们研究的重要的方向。 这些关联 | ! l ! ! j ! | j 挖掘算法在实际数掘挖掘系统中得到了很盘了_ 的心用。例如， i b m 公亓ja l m a d e n 石j f 究中心丌发的q u e s t 系统，s g i 公剐开发的m i n e s e t 系统， 以及d b m i n e r i e t h n o l o g y 公n j 丌发的d b m i n e r 系统，备系统均提供多种数扼 挖掘方法。其中，著名的d b m i n e r 足堆于数掘、) 方体的联机分析挖箍l i t 具，包 含多种有效的频繁丰炱式挖掘功能和集成的i f 视化分类方法。 目前幽内对关联舭则挖掘所涉及的研究领域很多，一股集叶1 于算法的研究、 关联规则挖掘的实际应川以及关联规则挖掘理论方而的研究。大多数研究项日足 由政府资助进行的，具体的研究项h 有中科院汁算机研究所的智能信息处理匿j _ l l j 东师蕾天学硕上学位沦文 实验守研制丌发的多策略数据挖掘、f 台m s m i n c r 系统”，此系统集成了关联规 则挖掘算法：复旦大学研制7 r 发的a r m i n e r 系统”，陔系统采用的关联规则挖 掘算法是基于a p r i o r i 的改进算法。虽然已经取得了相的成功，但目i 讨在处理极 火规模的数掘h 、j ，如何提高算法效二缸，如何提供一种吁川o 交h 的方法以及如何 将用广- 的领域知识结合住其中等都是尚待解决的l i u j 题。 1 4 关联规则挖掘研究中存在的问题 几前灭联舰则的研究i ：要有如下几个川题： ( 1 ) 算泼的效率问题。在数据挖掘c h 算法的效率是个非常重要的题。现 有的数掘挖掘方法大都足基十宽度优先的自序馊索策略。这种搜索方法的效；# 和 问题字i r j 的大小有直接的关系。传统a p r i o r i 算法把整个数掘席作为n 根窄i r j ， 通过多遍扫描数据库的力浊发现隐藏在数据库巾的频繁项集。山于数抛库的规模 越来越大，应用传统的多遍 1 捕数据库的方法算效牢越来越低，动辄十几个或 儿r 个小阡寸的计算无法满足用户数据分析的：精求。一些争家提出基于树结构的挖 掘算法，将数据库址缩刮一个树结构中，树结构保存菥数抛j 年中的l 二要信息，然 后存树结构的基础l ? 进行灭i 跌规则的挖掘。m 于树结构远远小r 数掘库奉身，所 以提高r 计算效率。 ( 2 ) 天联舰则的衡黾标准不足。hl m ，+ 成灭联舰则的标准主要有如下两个： 即支持度和苒：信度。但如果仪使用用户给定的最小支持度和最小胃t ；，。t tr 来! l ：成关 联规则，待i t 会，+ 成人员的、冗余的、虚假的和用户小感兴趣的天联舰则。目i 珀 人们引入了兴趣度、蕴含强度和收集强度等衡量标准米修剪这螳无用的规则，但 仍在探索研究阶段。 ( 3 ) 关联规则的即时性不足。现实应用中，衡量标准和数据库不断更新，如 何挖扣 迅速史新的数扔；并将用户的领域知识及时的结合存其中，也是一个研究 的难点。 山东师范大学硕士学| 立论文 1 5 本课题的研究内容及意义 1 5 i 研究内容 木谍题在数据挖掘研究和关联规则挖掘研究的背最卜，展丌了对芙联规则挖 掘力法的研究及心用i 。作。对父联规则挖捌知识进行_ r 全面地p 1 纳和总结，针对 已有评价标准巾存在的问题和传统频繁项集挖掘算法中存在的不足，提出了新的 倒决力。案。研究内容主要以下四个方面： i 、对关联规则的种类进行厂拿l l i 地分类、1 纳和总结，对关联舰9 1 , 1 j 的舆型 挖掘算法及奠接奉j 山、想进行r 详细地分析和研究。 2 、对 蓟基于史持度置信度椎架的关联规则挖掘算法进行j ，分析和研究。 发玑仅仅利用支持度、酣信度这两个标准柬衡贷：天i 隈舰则经常会使用户挖捌到虚 假的、无效的规则。为j 解决这个n u 题，引入了相关支持度这个新的度量丰，j i 准， 将支持度、置信度和相爻支持度起作为囱效关联规则的评价标准。当挖掘一 i 条关联舰则的支持度、置信皮、相关支持度同时满足最小支抖度、最小胃信度、 最小年同火支持度的时候，j 被认为是有意义的规则。 3 、经典a p r i o r i 算法会严。l j 庞人的候选项集，并儿算法存每个阶段循环都 需要重复迸jj ：数掘库存取。这对系统i n j 苦足一个沉重的负担。为了解决a p r i o r i 算法的瓶颁问题提高算法的效；钲我们提了种新的频繁项集牛成算法 m ma p r i o r i ，本文刈m ma p r i o r i 算法的原理、箅法和实现迸彳j 了洋细的介绍， 井f ：构造合成数把的基础i 埘馋浊- ja p r i o r i 算法的执行效率进行r 比较。实 验证明，改进矗的m ma p r i o r i 算法其自良好的性能。 4 、从火撼的数掘一 i 发现关联规则彳i ：市场定位、决策分析和商业管理等领域 是极为有用的。本课题选取一个实际的超n 心肖岱数据库做为挖掘对象，利用 m ma p r i o r i 算法挖掘出顾客购买的商品与商品之间的潜存联系，达到指导实践 的甘的。 奉论文的组织如一f ： 第一章介绍了数抛挖掘与关联规则的研究背景，分析了【刈内外刈关联规则 挖扣i 算法的研究现状及研究中存存的】u 题，指出j 本课题的研究内容及研究意 义。 山东师范大学硕j ：学位论文 第章，对数据挖掘技术的产生进行r 简要的【u l 顾，在提出数就- ：挖掘基本概 念的旗础上，对数据挖掘的刈象、可发现的模式和常使用的技术进行了详细地分 类、归纳和总结。对数抛挖掘技术的热点研究领域进行了客观地总结和探讨，为 本文的个m 腱3 1 。作好 ! f l j 够。 第二章，往提出关联规则基本概念的基础f ，刈关联规! j l 【j 的种类进行r 全i 丽 的总结，刈关联规! 【l | j 的绎腆挖扣i 算法及其琏本思想进彳rj 详细的分析和研究。提 商算法效率的各种优化技术也侄这单进行了讨论。 第叫擎，存对传统关联规则评价标准进行分析的基础之j ：，引入j ，相关支持 度( s 。) 这个新的度量丰，j ；准，将支持度、冒信度和相关支持度起作为有效关联规 则的评价柏i 准，柬限制无效关联规则的产生。 第五幸，针对经舆频繁项集挖掘算法的1 i 足，提出了m ma p r i o r i 算法。该 算法矗0 窆掘频繁2 一项集的过租中，利川个杯识频繁1 项集的矩阶的转芥与矩 阶自身斗1 l 乘得到频繁2 一负集。解决了a p r i o r i 算法在啦成频繁2 】页集时的效罐瓶 预i i u j 题。 第六章，本系统采用v c + + 6 o 程序设计语言f 1 ：为丌发i 只_ ，在m i c r o s o f t w i n d o w s2 0 0 0s e r v e r 、m i c r o s o f ts q ls e r v e r2 0 0 0 系统环境的綦础h 构造j ，一 个简单的关联规则挖掘系统，利i jm ma p r i o r i 算法及“支持一置信一桐天支持度” 的标准束挖掬：数据库q ，潜在的有效关联规则，为销售活动提供决策支持。 最后足列全文的总结，_ 并指出r 奉文的工作需进步完善和深入研究的地 力。 1 5 2 研究意义 关联规则是数掘挖掘领域中的个非常审要f j 勺研究课题，广泛应川于各个 领域e 要包括顾客购物分析、同录设训、【 i t 协广告邮寄分析、追加销售、仓储 规划、网络故障分析等。灭联舰! i ! | j 挖掘既可以检验行业内长期形成的知识模式， 也能够发现隐减的新规律。有效地发现、i 星解、运j j 关联规则是完成数据挖掘仃 务的重要手段。 本文通过对关联规则挖掘算法及应用的研究，提出一个改进的关联规则挖掘 算法，较好地改善了经典a p r i o r i 算法在数据库处理过程。 i 存在的效；棼瓶颈问题， l h 束师范大学硕士学位论文 提高j ，频繁项集的挖扣；效；笨。针刈现有关联规则评价标准的局限性。采用“支持 置信干天支持度”标准来约束无效关联j | ! i ! 则的产t e 。最后，选取一个超市销售 数据库做为挖掘刈缘，利用改进的m m a p r i o r i 算法挖掘出有效的芙联规则，从 而为销售| ；i 进行目标销售提供了依抛。冈此木课题的研究具有较人的理论价值和 现实意义。 l b 象师范丈掌碜_ l 学位论文 第二章数据挖掘技术 随着现代信息科学技术的发展，数据库管理系统在牛产乍活中的应用越来 越广泛，数搀i 库的j ；1 5 l 模也在不断地扩大。人们积累r 海吊的| ；i 业数据，存这些人 最的数拥7 卧j 隐藏r l 多具有决策意义的信息。数据挖掘就是要在“数据矿山” 巾找到蕴减的“，i l l 口5 金块”，帮助企、l p 减少f i 必要投资的同时提高资金同报。它不 满足j ，刈数据进行简单的青询，而是想从人量的数据t t ，找出更多有用的知识，冈 此，数据挖掘的过程义称为知识发现的过程。为了更加深入的研究基r 关联舰则 的数据挖掘并澎i ，侄本章巾对数抛挖掘的定义、功能以及数抛挖掘的过程和其应 用领域作个较为全面的介绍，为本文的个t f i t 是丌做好铺垫。 2 1 数据挖掘的定义 数揣挖掘( d a t am i n i n g ) 技术就是使人们从火型数据库或数抛仓库q | 提取感 必趣的、事先未知的、潜在有川的隐含知识的过程。提取的知识表：为概念 ( c o n c e p t s ) 、规, n ! l j ( r u l e s ) 、舰律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式现已成为数 掘库及信息处理领域零要的研究方向。 数掘挖掘的披术基础是人工智能，它利用了人l 鹤1 能中的 峰已纶成熟的剪 江i 年技术。数掘 g 越t i + u 数掘库知u ! 发现k d d ( k n o w l e d g cd i s c o v e r yi nd a t a b a s e ) 实际【? 是等价的概念，人t 智f i ( a i ) 领域习惯称k d d ，而数据库领域习喷称数 据挖掘。也有学，l i i 把k i ) d 看作发现知识的完整过程，而数掂挖掘只是这个过程 的个闭j 分。 与数据挖掘天系密切的研究领域包括归纳学( i n d u c t i v el e a r n i n g ) 、机器学 ) j ( m a c h i n ei e a m i n g ) l l 统计5 j + j i ( s t a t i s t i ca n a l y s i s ) ，特别足机器学爿被认为和 数据挖掘的灭系最密切。二者的手要区别在丁：数据挖掘的仟务是发现u j 以理解 的知识，而机器学习关心的是提高系统的1 h ：能：数据挖掘的对缘是大，叫的数据库， 而机器学习处理的数抛库要小得彩。 从上述数据挖掘的定义，我们t 可以看m 数据挖掘自以下三个基奉特点： 1 数据挖掘足对数据库进行的种操作。 数掘库足数掘挖掘的 要操作对象。数抛住数据库中按。定的规则进行存 l b 东师范大学硕1 - 学佃论文 储，数掘所反映信息的结构、组织与特点也体现在数据库的结构卜。对丁，1 ib d 类 型的数掘库结构，管明! 人员希茸! r 解的信息往往是刁j h 的因而采川的处理方法 也彳j 尽干日。 2 数据挖扣i 是要发现隐含的，先前未知的信息。， 有价值信息的一个重要特傩就足具有“新鲜”平“使人震惊”的感觉，住决 策系统中，先前未知亿息的引入降低，该系统的熵值，从而降低了刈决策执行 粜了解的4 i 确定代，凼此也就降低了决策的风险。j l 仃新颖的信息彳能够为决策 嚣的决策提供新的依据，注意知识的j 凡余性与层次忭足提高新颖性的种方澎i 。 ：j 数抛挖掘产乍的信息戍该足只有潜在价值的。 一先，数据挖掘的对象应该有潜在的价值。其次，数据挖拍：的过程应该能够 过滤掉数据中没有价值的信息。最后数孰! ：挖掘产乍的信息j 衄该贝：f j 潜在价值， 能够为决策、推理提供支持，同时还应该注意剑数掘的合法性以及时效性。 2 2 数据挖掘的功能 在计：多情况f ，用户并不圭通数掘存住哪批有价值的信息知u 。因此，对r 个数据挖掘系统m 。0 它应该能够同时搜索发现多种模式的知识，以满足用，o 的期亡f ! 和实际需要。数据挖掘能够实现的功能 要有以下五利一： ( 1 ) 关联分析 从。义上讲，关联分j ! ) r ( a s s o c i a t i o na n a l y s i s ) 是数掘挖掘的本质。既然数抛挖 抛的h 的足发现潜减存数据背后的知u ，那么这种知i ： 一定是反映不h 对象之间 的天联。它刻画了数据j 车中对象之川的灭联及其关联的 仝度。 天联：l i 识反映一个事件和其他事件之问的依赖或关联。数引库中的数掘- 般 邰存在着关联芙系，也就足说，两个或多个变景的取值之间存往某利，舰律r ；：。数 据库中的数掘关联是现实1 l i ：界l | 1 事物联系的表i 见。数据库作为种结构化的数抓 组织形式，利用其依附的数据模，弘可能刻丽了某些数掘问的灭联。但数就；：之问的 关联足复杂的、钉时足隐含的，关联分析的目的就是耍找出数据库巾隐藏的关联 信息。这些关联并不总是t j 【先知道的，而是通过数掘库中数掘的关联分析获得的， 冈而对商业决策具有新价值。 关联规则挖掘”足关联知泌发现的最常用方法，最著名的是a g r a w a l 镭提 l l j 束师范大学硕_ 上学位论文 出的a p r i o r i 筇浊及奠改进算法”。为r 发现有意义的关联规则，需要给定两个 闽值：最小艾持度( m i n i m u ms u p p o a ) 和最小黄信度( m i n i m u mc o n f i d e n c e ) 。挖掘 l 出的关联规则必须满足用，、规定的最小支持度，它表j 了组项目关联存一起需 要满足的最低联系程度。挖掘出的关联规则也必须满足h j 户规定的最小嚣信度， 它反映了个天联规! j ! | j 的最低“j 靠度。在这个意义上，关联规! i ! | j 挖搔i i 系统的目的 就是从数抛库中挖掘 l j 满足最小支持度和最小w 信度的父联规m 0 。父联规则的研 究和心用是数据挖扣：l t 最活跃的分支之一，已经提出了许多关联规则挖拥 的理论 和算法。 ( 2 ) 分类和预测 分类( c l a s s f i c a t i o n ) 是对数：| i ! ：的过滤、抽取、压缩以及概念提取，是数据挖掘 t ，的一个重要的目物i 和任务，在：萄业上应川较多。分类的h 的足学会一个分类函 数或分类模型( 也常称作分类器) 。n 1 _ r 数据挖掬；足从数据中挖掘知识的过程，凶 此要构造这样一个分类器，这种知u 也必须来自】i 数据，即需要有个训练样小 数圭( i ：作为输入。分类器的作川就是能够根抛数据的j | f | j 忙将数据分派刘小同的组 中，即分j j | 了数抛的符种属性并找出数抓的属性模掣，确定哪些数掘属于哪些目i 。 分类通常用1 i 预测未知数啦i ：实例的归属类别( 有限离散值) ，但在些情况卜，需 要预测某数值属性的值( 连续数值) ，这样的分类称为预i l ) ! | j ( p r e d i c a t i o n ) 。分类模式 j 以采川多种形式表示，如分类规贝f l ( i f - i 、i i e n ) 、判定树、数学公式或神经刚络 等。应用于分类， 识挖掘的代表竹i 技术有：决策树、贝叶斯分类、神经网络分类、 遗传算法、类比学习和案例学习，以及相糙集和模糊集等方法。 ( 3 ) 聚类分析 一般把学习算法分成有导师( 或雌督) 学爿和无导师学j j 两种方，手要区别 是有没干彳类信息作为指导。聚炎：( c l u s t e r i n g ) 足媳型的无写师学习锋法，一般用 j 二自动分类。聚类就足将数掘对象分为多个类或簇，i - d 一个类中的对象只有较商 的相似度i n j 不同类t ，的x t 象筹别较火。聚类按照某个特定标准( 通常足某种距 离) 形成每个类，所形成的类在卒问上是一个稠密的k