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

硕士学位论文 摘要 本文主要研究关联规则挖掘理论及其算法模型在粗糙集知识表中的应用。首 先，在文中系统介绍了数据挖掘的定义、方法、发展方向，针对其中的关联规则 挖掘，讨论了各类关联规则算法。由于关联规则挖掘方法会产生大量规则，为了 挖掘出用户感兴趣的规则，本文提出一种利润约束的关联规则挖掘算法。此外， 借鉴关联规则算法模型的思想，提出一种获取缺省规则的新方法m d r b a p r i o r i ， 从决策表中提取具有一定支持度和可信度阈值的不确定规则。在本文中，主要做 了以下工作： ( 1 ) 给出了关联规则的定义，说明了挖掘关联规则的意义，研究了关联规 则挖掘的步骤，并且探讨了关联规则挖掘存在的问题及发展方向。 ( 2 ) 针对关联规则算法存在的一些问题，详细分析了目前提出的有关关联 规则兴趣度的各种主观和客观评价方法。本文引入企业关注的领域知识一一利 润，提出基于利润约束的关联规则挖掘方法，以增强规则的有趣性，提高规则挖 掘的针对性。 挖掘出的关联舰则，加上利润度量，就可以分析出哪些商品的搭配可以获得 最大的利益。一般的关联规则只是单纯的项目与项目之间的一种关系，典型的就 是买彳的同时会买b 的可能性的一种趋势分析。而我们加入量化参数利润分析 关联规则，拓宽了关联规则的表达能力，让决策者对于关联规则的意义有更进一 步的认识，并从中找出能使销售利润最大化的最佳商品促销方案。 在关联规则算法的“支持度一一置信度”框架中，是从“大处”着眼，关注 的是出现频数较高的项目集，要挖掘符合用户预期的利润要求的模式，不得不从 “小处”着眼，这是因为存在着“2 0 的业务带来8 0 的利润”这样的领域知识。 本文利用相对支持度的概念来挖掘稀有数据，再进一步结合利润量参数作为约束 条件，这样就可以求出零售事务数据库中所有满足用户利润要求的关联规则，不 论其支持度的高低，都可以运用本文的算法挖掘出来。 ( 3 ) 简要介绍了粗糙集的基本概念以及一般的属性约简方法，着重分析了 m o l l e s t a d 和s k o w r o n 提出的缺省规则的发现算法一一投影算法的算法框架及性 能。 ( 4 ) 针对投影算法的一些不足，扩展了缺省规则的定义，提出一种获取缺 省规则的新算法一一m d r b a p r i o r i 算法。本文通过对投影算法和关联规则算法模 型的详细分析，发现它们求解问题的实质是相同的，因而具有一种方法被另一种 方法替代的可能性。因此，基于a p r i or i 算法提出缺省规则挖掘的新算法 m d r b a p “o r i 算法，它是独立于粗糙集方法但可以获取大致相同的规则的一种方 数据挖掘中关联规则及应用的研究 提出的方法有很强的操作性和可实现性。 最后，对全文进行了概括性总结，并指出了有待进一步研究和完善的问题。 关键词：数据挖掘；关联规则；a p r i o “算法； 利润约束；粗糙集；缺省规则 硕士学位论文 a b s t r a c t t h i sp a p e rc o n c e n t r a t e so nr e s e a r c h i n ga s s o c i a t i o nr u l e sm i n i gt h e o r ya n di t s a l g o r i t h mm o d e la p p l i e di ni n f b r m a t i o nt a b l e sb a s e do nr o u g hs e tt h e o r y f i r s t l yi t g i v e sad e t a i l e di n t r o d u c t i o nt ot h ed e f i n i t i o n ，t e c h n 0 1 0 9 i e sa n ds t u d yo r i e n t a t i o n so f d 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 so n eo ft h em o s ts t u d yb r a n c h e sa n di t s m i n i n gm e t h o d sa r ed i s c u s s e d a i m i n ga tl a r g ea m o u n t so fr u l e si ng e n e r a lm e t h o d s ， t h i sp a p e rp l a c e sa ne n l p h a s i so nq u a l i t ym e a s u r e sa b o u ta s s o c i a t i o nr u l e s ，a n d p r o p o s e sa ni m p r o v e da l g o r i t h mb a s e do np r o n tc o n s t r a i n t f u r t h e rm o r e ，am e t h o d c a l l e dm d r b a p r i o r ia l g o r i t h mi sp r o d u c e dt oo b t a i nd e f a u l tr u l e sw i t ht h es p e c i n e d s u p p o r ta n d c o n 仃d e n c et h r e s h o l d si nd e c i s i o nt a b l e s ，a n di n t h i s a j g o r i t h m a s s o c i a t i o nr u l e sm o d e li su s e df o rf e f e r e n c e t h em a i nr e s e a r c ho ft h i sp a p e ri sa s f o l l o w s ： i nt h en r s tp l a c e ，t h i sp a p e rg i v e st h ed e n n i t i o na n ds i g n i n c a n c eo fa s s o c i a t i o n r u l e s m i n i n ga n di n v e s t i g a t e s i t s m i n i n gp r o c e s s t h ee x i s t i n gp r o b l e m sa n di t s d i r e c t i o n sa r ea l s od i s c u s s e dh e r e i nt h es e c o n dp l a c e ，a l ls u b je c ta n do b je c tm e t h o d sa b o u tr u l eq u a l i t ym e a s u r e s h a v eb e e np r o p o s e db ys c h 0 1 a r st od e a lw i t hs o m ep r o b l e m si na 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 i nt h i sp a p e r ，t h ei n d u s t r i a li n f o r m a t i o n 一一p r o f i tc o n c e r n e db ya n e n t e r p “s e i si n t r o d u c e dt o b eac o n s t r a i n ts ot h a tt h er e d u n d a n tr u l e sc a nb e f u r t h e re l i m i n a t e da n dt h o s em o r ei n t e r e s t i n gr u l e sc a nb es h o w nu s e r s a d d i t i o n a l l y ， t h ep a r a m e t e ri i k ep r o 疗te x t e n d st h ec o n t a i n i n gp o w e ro fa s s o c i a t i o nr u l e s ，w h i c h w i l ln o t s i m p l yr e n e c tt h e t r e n db e t w e e nc o m m o d i t i e s ，a n d f r o mw h i c ht h e d e c i s i o n - m a k e rc a na c q u i r em o r ei n f o r m a t i o n t h em o d e lo fs u p p o r t c o n f i d e n c ei sa d o p t e di na 1 1 e x i s t i n ga l g o r i t h m s ，w h i c h e m p h a s i z e so nl a r g ei t e ms e t sa n du s u a l l yi g n o r e st h es m a l lo n e s h o w e v e r ，t om i n e a l la s s o c i a t i o nr u l e sm e e t i n gt h ep r o n tc o n s t r a i n to n e se x p e c t e db yu s e r s ，t h er a r e d a t an e 9 1 e c t e dp r e v i o u s l yw i l l p r o b a b l y b e i n t e r e s t i n g b e c a u s eo fi n d u s t r i a l i n f o r m a t i o n an e wa l g o r i t h mi sp r o p o s e d ，i nw h i c hr a r ed a t aa r ec a nb em i n e dw i t h r e l a t i v es u p p o r ta n dt h e np r o n tw i l lb eac o n s t r a i n ti nt h em i n i n gp r o c e s s s ot h e a l g o r i t h mc a nm i n ea l l s u c ha s s o c i a t i o np a t t e r n sm e e t i n gt h er e q u i r e m e n to fp r o f i t w h e t h e rt h e i rs u p p o r t sa r eh i g ho rn o t t h i r d l y ，t h eb a s i cc o n c e p t sa b o u tr o u g hs e tt h e o r ya n dr e d u c t i o nm e t h o d sf o r a t t r i b u t e sa r eg i v e nt oab “e fi n t r o d u c t i o n a na p p r o a c hc a l l e dp r o j e c t i o na l g o r i t h m ， i sp r o p o s e db ym o l l e s t a da n da s k o w r o nt oo b t a i nd e f a u l tr u l e s i t st y a m e w o r ka n d p e r f b r m a n c ei sa n a l y z e di nd e t a i l t l i 数据挖掘中关联规则及应用的研究 p r e s e n t san e wa p p r o a c h ，c a l l e dm d r b a p r i o r ia l g o r i t h m ，i nw h i c hd e f a u l tr u l e s e x t e n d e dc a nb ea b s t r a c t e di nd e c i s j o nt a b l e s a f t e ra n a l y z i n gb o t hp r o j e c t i o na l g o r i t h ma n da s s o c i a t i o nr u l e sa l g o r “h m m o d e l s ，w ef l n dt h e yh a v et h es a m ee s s e n c eo fs e e k i n gs o l u t i o n s ；t h a ti st os a y ，t h e y s e e ka l lt h ep o s s i b l ec o m b i n a t i o np a t t e r n sf o ra l lt h ea t t r i b u t ev a l u e s a sar e s u l t ，t h e s o l u t i o n sp r o d u c e db yb o t hm e t h o d sa r ea p p r o x i m a t e l yi d e n t i c a lw i t hr e s p e c tt ot h e s a m ec o n s t r a i n t s i nt e r m so fs i g n i n c a n c ei ns t a t i s t i c s ，t h i sa l g o r i t h mi sp r o v e dt h a t i tc a nb er e p l a c e db yc e r t a i na s s o c i a t i o nr u l em i n i n gm e t h o d s n e v e r t h e l e s san e w a p p r o a c hc a l l e dm d r b 印r i o r i ，b a s e do na p r i o r ja l g o r i t h mi sp r o p o s e dt og e n e r a t e d e f a u l tr u l e si nt h ep l a c eo ft h ep r o j e c t i o na l g o r i t h m ，a n dh a ss o m ep a r t i c u l a r a d v a n t a g e s t h i sm e t h o dd o e sn o tn e e dr e d u c t i o n ，a n di tc a na c q u i r ec o m p l e t er u l e s f b rt h ed e c i s i o n - m a k e rt om a k ear e a s o n a b l ec h o i c e t h ev a l i d i t yo ft h ep r o p o s e d a l g o r i t h mm o d e li sp r o v e db yt h ee x p e “m e n t a id a t a i na d d i t i o n ，t h eo p e r a t i o no f t h i sa l g o r i t h mm o d e li sc o n v e n i e n tb e c a u s eo ft h em a t u “t yo fa s s o c i a t i o nr u l e s m i n i n gt e c h n i q u e s s o m ep o p u l a rd a t am i n i n gt o o l ss u c ha sd b m i n e r 2 oc a nb eu s e d t og e td e f a u l tr u i e sb yt h ec o r r e s p o n d i n gf u n c t i o no nj t sa s s o c i a t i o nt u l e sm i n i n g f i n a l l y ，ar e c a p i t u l a t i v ec o n c l u s i o ni sg i v e n ，a n dt h ef u t u r er e s e a r c hd i r e c t i o n s a r ep r o p o s e d k e yw o r d s ： d a t a m i n i n g ； a s s o c i a t i o n r u i e s ；a p r i o r i a l g o “t h m ；p r o f i t c o n s t r a i n t ；r o u g hs e t ；d e f a u i tr u l e s 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 储签名：质越是 日期加年争月硼 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 稚霞 1 舌扣 日期：夕w f 年华月扩日 日期：如i 年4 月2 伊日 硕士学位论文 第1 章绪论 1 1 论文研究背景及选题意义 近年来，随着现代信息科学技术的发展，人们利用信息技术生产和搜集数据 的能力大幅度提高，成千上万的数据库被用于商业管理、政府办公、科学研究和 工程开发等等，并且这一势头仍将持续发展下去。于是，一个新的挑战被提了出 来：在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如 何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率 呢? 只有使数据真正成为一个公司的资源，并且充分利用它为公司自身的业务决策 和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面 对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现( d a t a m i n g a n dk n o w l e d g ed i s c o v e r y ) 技术应运而牛，并得以蓬勃发展，越来越显示出其强大 的生命力。 数据挖掘( d a t a m i n i n g ) 就是从大量的、4 i 完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数据 分析、数据融合( d a t a f u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的 源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数 据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的， 也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过 程控制等，还可以用于数据自身的维护。因此，数据挖掘是人工智能、数据库技 术和统计学等多学科结合的产物，它融合了数据库、人工智能、数理统计、可视 化、并行计算等方面的知识和技术。 数据挖掘技术从一开始就是面向应用的。它不仅仅是面向特定数据库的简单 检索、查询、调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件问的相互关联，甚至利用已 有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大 s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提 出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。这样 一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营决 策者提供决策支持。这种需求驱动力，比数据库查询更为强大。需要强调的是， 数据挖掘中关联规则及应用的研究 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭 新的自然科学定理和纯数学公式，更不是什么机器定理证明。所有发现的知识都 是相对的，是有特定前提和约束条件、面向特定领域的。 从功能上可将数据挖掘分析方法分为：关联分析( a s s o c i a t i o n a n a l y s i s ) 、序列 模式分析( s e q u e n t i a lp a t t e r n s ) 、分类分析( c l a s s i f y i n g ) 、聚类分析( c l u s t e r i n g ) 、 孤立点分析( o u t l i e r a n a l y s i s ) 等，其中关联规则挖掘算法在商业界中备受关注， 且被各领域广泛应用。 什么是关联规则? 关联规则是描述在大型数据库中数据项之间的关联性如何。 关联规则挖掘是指从巨量的信息资源中寻找隐含在数据项集间的有趣联系或关联 关系，这是每个商业决策者的迫切要求。最简单的例子就是购物篮分析( m a r k e t b a s k e ta n a l y s i s ) ，通过顾客购买的交易记录找出商品之间的关联性，作为商品项 目之间如何搭配促销或是考虑商品在商品储存柜的摆放位置，甚至成为仓库管理 的参考依据。 目前关联规则的研究主要集中在如何提高挖掘算法的效率上，并且已经有许多 成熟的算法。其巾最经典的关联规则挖掘算法主要分为以卜三种：a p r i or i 算法、 d i c 算法、抽样算法等。比较著名的算法有r a k e s h a g r a w a l 和r a m a k r i s h n a ns k r i k a n t 提出的a p r i o r i 算法，加拿大西蒙弗雷泽大学教授j i a w e ih a n ( 韩家炜) 提出的 f p 。g r o 、v t h 算法。为了提高关联规则挖掘的应用价值，研究方向有了诸多拓展，如 多层多维关联规则、规则价值衡量方法、规则的可视化表示、与其他理论技术的 结合、与领域知识的结合研究等都成为研究的热点问题。 本文对关联规则的研究着重于最后两个方面： ( 1 ) 结合领域知识一一利润( p r o f i t ) 进行关联规则的挖掘。加入利润属性的 关联规则，进一步地扩展了关联规则的表达能力，使得挖掘出的关联规则突破传 统的趋势分析，可以提供给决策者有关的量化信息。通过对商品利润的评估，对 所挖掘出的关联规则加以分析，以满足不同决策者不同角度的需求。 ( 2 ) 与粗糙集理论结合，运用关联规则挖掘算法的模型提取广义决策规则( 缺 省规则) 。由于关联规则提取是现实中已经成功应用的技术，因而所提出的方法操 作简单，实现方便。 1 2 关联规则挖掘算法的研究现状 关联规则的概念由r a g r a w a l 等人于1 9 9 3 年在对市场购物篮( m a r k e tb a s k e t a n a l y s i s ) 进行分析时首次提出舶，用来发现交易数据库中不同商品( 项) 之间的联 系。这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响， 发现的规则可以指导商品货架设计、货存安排以及根据购买模式对用户进行分类。 如今对关联规则的应用已经推广到许多领域，只要涉及到从大型的数据集中获取 2 硕士学位论文 知识的问题，关联规则都可能成为有力的工具。概括起来，关联规则的应用领域 也就是数据挖掘的应用领域包括：商业与金融、人口普查数据分析、工程技术数 据分析、医疗、财政、宏观决策支持、电子商务、网站设计、通信和互联网等。 从大型数据库中以及从其它不同应用领域的数据中进行高效关联规则挖掘方 法的研究一直很受重视，努力提高各种算法的准确性、可伸缩性等性能是各研究 机构的核心课题。他们的工作包括对原有的算法进行优化，如引入随机采样、并 行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广等。 主要有以下几个方面的工作： 1 、基于a p r i o r i 框架和f p 一增长方法进行各种改进算法的研究 许多改进算法都是以a p r i o r i 算法为核心，或是其变体或是其扩展。a p r i o r i 算法尽管自身进行了一定的优化，但一些固有的缺陷还是无法克服： ( 1 ) 可能产生大量的候选集。当长度为1 的频繁项集有l0 0 0 0 个的时候，长 度为2 的候选集个数将会超过1 0 m 。还有就是如果要生成一个很长的规则的时候， 要产生的中间元素也是巨量的。 ( 2 ) 无法对稀有信息进行分析。由于频繁项集使用了参数聊f n s 即，所以就无 法对小于掰j s “p 的事件进行分析，而如果将m 加s “p 设成一个很低的值，那么算法 的效率就成了一个很难处理的问题。 对于第一个问题，改进算法一般是从两方面着手，其一是减少算法扫描数据 库的次数，其二是减少候选项集的数量，从而达到提高效率的目的。除了几种经 典的改进算法 ”6 】如：基于划分( p a r t i t i o n ) 的方法、基于哈希( h a s h ) 的方法、 基于采样( s a m p l e ) 的方法外，在文献 7 中提到一种方法，称为f p g r o w t h 。他们 采用了分而治之的策略：在经过了第一次的扫描之后，把数据库中的频繁项集压缩 进一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，随后我们再将 f p t r e e 分化成一些条件库，每个库和一个长度为1 的频繁项集相关，然后再对这 些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使 得一个f p t r e e 可以放入主存中。实验表明，f p g r o w t h 对不同长度的规则都有很 好的适应性，同时在效率上较之a p r i o r i 算法有巨大的提高。 我国的许多研究者也积极地进行着这方面工作 卜“ ，在a p r i o “算法或类算法 和f p g r o w t h 算法的基础上改进算法的效率。像文献 1 0 提出的关联规则频繁集 快速生成算法，在算法中采用了一种有效组织存放项目集( i t e m s e t ) 的数据结构 ( 优化结构) ，只需对事务数据库进行两边扫描即可得出频繁项目集。该算法是一 种典型的以空间代价换取时间策略，在最小支持度较小时有着较明显的优势。文 献 1 1 提出一种将a p r i o r i 算法与散列技术和事务压缩技术相结合的改进算法，通 过减小存储空间提高算法的效率。 第二个问题是基于这样的一个想法：a p r i o r i 算法得出的关系都是频繁出现的， 但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不 数据挖掘中关联规则及应用的研究 是频繁出现的。在a 口r i o r i 算法中，起决定作用的是支持度，而我们现在将把可信 度放在第一位，挖掘一些具有非常高可信度的规则。在 8 】中介绍了对于这个问题 的一个解决方法，整个算法基本上分成三个步骤：计算特征、生成候选集、过滤 候选集。在三个步骤中，关键的地方就是在计算特征时h a s h 方法的使用。在考虑 方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方法有 两类：m i i l h a s h i n g ( m h ) 和l o c a l i t y s e n s i t i v c h a s h i n g ( l s h ) 。m i i lh a s h i n g 的基 本想法是：将一条记录中的头个为1 的字段的位置作为一个h a s h 函数， l o c a l i t ys e n s i t i v eh a s h i n g 的基本想法是：将整个数据库用一种基于概率的方法 进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。 我们再对这两个方法比较一下：m h 的遗漏率为零，错误率可以由女严格控制，但 是时空效率相对的较差；l s h 的遗漏率和错误率是无法同时降低的，但是它的时 空效率却相对的好很多，所以应该视具体的情况而定。最后的实验数据也说明这 种方法的确能产生一些有用的规则。 2 、可增量更新的关联规则挖掘算法 当数据库或支持度发生变化时如何更新、维护和管理已挖掘出来的关联规则是 i ，分重要的研究课题【n “”，关联规则的增量式更新是提高关联规则挖掘效率和实 用性的重要方法。 增量式更新算法主要涉及到两个问题： 第一，在给定的最小支持度和最小可信度下，当一个新的事务数据库d b 添加 到旧的事务数据库d b 中时如何生成d b u d b 的关联规则； 第一，给定事务数据库d b ，在最小支持度和最小可信度发生变化时，如何生 成数据库d b 中的关联规则。 算法f u p 的基本思想为：对任意一个( 女1 ) 项集，若其在d b 和d b 巾都是 频繁项集则其必定为频繁项集；若其在d b 和d b 中都是弱项集，则其一定是弱项 集；若其仅在d b ( d b ) 中是频繁项集，则其支持数应加上其在d b ( d b ) 中的支持数以 确定它是否为频繁项集。 3 、并行挖掘算法； 由于单处理器系统的计算能力是有限的，串行数据挖掘算法对于大型数据库 来说效率仍然很低，为此，研究并行数据挖掘算法是十分必要的。另外，随着 i n t e r n e t 的广泛使用和高性能工作站的不断普及，对关联规则采用并行挖掘也是数 据挖掘发展的趋势。 目前已经提出的并行挖掘关联规则的算法有a g r a w a l 等人提出的 c d ( c o u n t d i s t r i b u t i o n ) 、d d ( d a t ad i s t r i b u t i o n ) 、c a d ( c a n d i d a t ed i s t r i b u t i o n ) ，p a r k 等 人提出的p d m ，c h u e n g 等人提出的算法d m a 和f d m 【18 铷 。这些算法都是基于 无共享体系结构，即并行计算的n 台计算机间除了用网络连接起来外，其他都是 4 硕士学位论文 完全独立的，每台计算机p 1 ( i _ 1 ，2 ，n ) 上都有自己的分事务数据库d b ， 总的事务数据库d b = u 鲁d b l 。c d 算法是通过a p r i o r i 算法得到各计算机上得到相 同模式长度的频繁项集，然后通过传播的方式，进行相同频繁项集的支持度相加， 再利用a p r i o n g e n 算法得到候选项集，如此循环验证得到最终的频繁项集。算法 d m a 是基于“若项集x 在d b 中为频繁项集则其必在某一个d b l 上为频繁项集” 在算法中采用了局部剪枝技术，从而使其生成的候选项比算法c d 要小。 我国研究者也积极地进行了这方面的研刘2 卜2 ”。文献 2 3 】提出了一种在微机 集群上实现的高效并行算法，大大提高关联规则的挖掘效率，并具有良好的可扩 展性。 4 、多层、多值属性的关联规则算法的研究 对于很多应用来说，由于数据分布的分散性，所以很难在数据最细节的层次 上发现一些强关联规则，当我们引入概念层次后，就可以在较高的层次上进行挖 掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是 普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多 个层次上进行挖掘的功能。 多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同 层关联规则和层问关联规则。多层关联规则的挖掘基本上可以沿用“支持度一一 可信度”的框架，不过，在支持度设置的问题上有一些要考虑的东西。 多层关联规则可以采用两种支持度策略：( 1 ) 统一的最小支持度。对于不同 的层次，都使用同一个最小支持度。这样对于用户和算法实现来说都比较的容易， 但是弊端也是显然的。( 2 ) 递减的最小支持度。每个层次都有不同的最小支持度， 较低层次的最小支持度相对较小，同时还可以利用上层挖掘得到的信息进行一些 过滤的工作。 h a n 等人在面向属性归纳( a t t r i b u t e 0 “e n t e di n d u c t i o n ) 的基础上，提出了多 层次关联规则的挖掘算法m lt 2 l l 等，先求出高概括层的频繁模式( f r e q u e n t i t e m s e t ) ，逐渐具体化，挖掘低概括层的频繁模式，最后由频繁模式求解关联规则。 其他主要算法还有r s m a t 等人的c u m u l a t e 、s t r a t i f y 及其变种e s t i m a t e 、e s t m e r 2 e 等。在文献 2 5 】中施鹏飞等人提出了多层次关联规则的挖掘算法一一a rs e t ，利 用集合“或”、“与”运算求解频繁模式( f r e q u e n ti t e m s e t ) ，提高了挖掘的效率和速 度。实验结果表明，算法a rs e t 是有效的，并对a rs e t 算法的几个变种进 行了讨论。 多值关联规则：关联规则可分为布尔型关联和多值属性关联。目前提出的挖 掘多值属性关联规则的算法大多是将多值属性关联规则挖掘问题转化为布尔型关 联规则问题，即将多值属性的值划分为多个区问，每个区间作为一个属性。在这 数据挖掘中关联规则及应用的研究 里如何有效划分区间段是很关键的，为了克服传统的等深、等宽划分方法的不足， 文 2 6 】采用聚集的方法确定多值属性的划分，文【2 7 】 4 6 】利用模糊概念来表示量化 属性间的关联关系，使得规则的表示更自然、易于理解。 5 、关联规则的价值衡量方法的研究 很多的算法都使用“支持度一一可信度”的框架，这样的结构有时会产生一 些错误的结果。于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成错误 的关联规则。一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期 望的强度之比，然而在许多应用中己发现，只要人们仍把支持度作为最初的项集 产生的主要决定因素，那么要么把支持度设得足够低以使得不丢失任何有意义的 规则，或者冒丢失些重要规则的风险。对前一种情形计算效率是个问题，而后 一种情形则有可能丢失从用户观点来看是有意义的规则的问题。 许多研究者迸一步寻找更有效的方法来衡量规则的价值，以去除虚假的和冗余 的规则。目前对规则的度量主要是感兴趣度，它是规则的合法性、有用性、新奇 性和简洁性的综合度量。在文献 2 8 中作者给出了感兴趣的规则的定义 ( r j n t e f e s t i n g ) ，在文献 3 2 】中把事件依赖性的统计定义扩展到兴趣度的定义上柬， 文【3 3 】中给出一个规则新奇性度量的表达式1 一p ( y ) ( 1 一p ( x ) ) + ( 1 一p ( y u x ) ) 。 除了把兴趣度作为修剪无价值规则的工具，现在已有许多其它的工作【2 9 3 l j 末 重新认识项集。如b r i n 等【29 j 考虑的相关规则，这是一种通过数据的相关性分析来 清除一些无用的规则的方法。定义规则a = b 的相关性c o 盯a b = p ( a u b ) p ( a ) p ( b ) ， 如果c o r r a b 1 则项集a 和b 是正向相关的；c o r r a b y ，其中c ，y ，且 朋卜巾。一般用两个参数来描述一个关联规则的属性1 8 】： ( 1 ) 支持度( s u p p o r t ) 蕴含式肛 ，的支持度是指数据库中同时支持项集x 和】，的记录数与总记录数 之比，描述了石和y 同时发生的概率，它表明了规则的重要程度。关联规则弘 y 的支持度定义为： s u p p o r t ( 。y 兰 d = s u p p ( u l ，) = i7 1 _ da n d ( ( u y ) 7 ) l ，l di( 31 ) 其中“ll ”示集合中的元素个数。 例如：如果某天共有1 0 0 0 个顾客到商场购买商品，其中有1 0 0 个顾客同时买 了面包与黄油，那么f 二述的关联规则的支持度就是l o ( 1 0 0 1 0 0 0 ) 。 ( 2 ) 可信度( c o n f i d e n c e ) 硕士学位论文 蕴含式弘 ，的可信度是指数据库中同时支持肼口j ，的记录数与支持爿的记录数之 比，可理解为在x 发生的情况下】，发生的概率，它表明规则的正确程度。关联规则 舴 y 的可信度可用以下公式来表示： c o 九f i d e n c e ( 胎 y ) = s u p p ( 并u y ) s u p p 乙r ) ( 3 2 ) 如上所述的面包与黄油的例子，该参数就回答了这样一个问题，如果一个用 户买了面包则他同时可能买黄油的可能性有多大。即有7 5 的用户在买了面包的同 时买了黄油，所以可信度为7 5 。 如果蕴含式j ，_ ，的支持度和可信度分别达到用户指定的最小支持度仰j 即s 印) 和最小可信度伽j c o ”n ，则称爿- _ j ，为关联规则( s t r o n gr u l e s ) 。 关联规则挖掘主要是在事务数据库d 中挖掘出满足用户要求的最小支持度与 最小可信度的关联规则的过程。 挖掘关联规则问题可以分解为以下两个子问题： l 、找出存在于事务数据库中的所有频繁项集，即找出的所有项集的支持度满 足用户所规定的最小支持度。 2 、利用频繁项集生成关联规则。对于每个频繁项集l ，若一c 三，4 中，且 c o n n d e n c e ( 爿= 犯卅) ) = s u p p ( l ) s u p p a ) 2 朋m ，矿则称构成关联规则爿= ( 三“) 。 第一个子问题是求问题的关键，故目前的大多数关联规则算法主要集中在对第 一个子问题的解决上，即挖掘频繁项集上。 3 2 关联规则的经典算法 自a g r a w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的 工作包括对原有算法进行优化，如引入随机采样、并行思想等，以提高算法挖掘 规则的效率i 对关联规则的应用进行推广等。也有一些研究工作独立于a g r a w a l 的挖掘频集方法【7 ，5 ，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。 还有一些工作注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一 些值得考虑的研究方向。下面对一些经典的算法作以简单的介绍。 3 2 1a p rio ri 算法 a p r i o r i 算法是著名的关联规则挖掘算法，利用了频繁项集向下封闭性，即： 一个频繁项目集的任一子集必定也是频繁项目集，一个非频繁项目集的任一超集 必定也是非频繁项目集，达到频繁项集候选项的剪枝目的。 a p r i o r i 是一种宽度优先算法，通过对数据库d 的多次扫描来发现所有的频繁 项目集，在每一次扫描中只考虑具有同一长度( 即项目集中所含项目的个数) 的所 有项目集。在第一次扫描中，a p r i o r i 算法计算d 中所有单个项目的支持度，生 数据挖掘中关联规则及应用的研究 成所有长度为l 的频繁项日集。在后续的每一次扫描中，首先以j i 一1 次扫描所生 成的所有频繁项f 1 集为基础产生新的侯选项目集，然后扫描数据库d ，计算这砦 侯选项目集的支持度，删除其支持度低于用户给定的最小支持度的项目集，最后， 生成所有长度为七的频繁项目集。重复e 述过程直到再也发现不了新的频繁项目 集为止。所以a p r i o r i 算法主要是通过两个过程组成，即由连接和剪枝组成。 ( 1 ) 连接步：通过三k - l 的连接产生候选项集c k ，从而找到k 。设氏一一啪为k _ 1 的第，项，假设事务或项集中的项按字典顺序排列，并设，1 与，2 为三“中的项集且 有相同的前后一2 项集，则可以把，1 与，2 二项集连接，l 。2 产生候选女一项集c k ，则 ，1 与，：产生的候选女一项集为，( 1 ) ，( 2 ) ，- ( 女一1 ) ，2 ( j 】 i ) 。由于c k 规模可能很大， 可以利用a p r i o r i 算法的性质“任何非频繁七一1 项集的超集不可能是频繁项集”，实 现剪枝压缩c k 。 ( 2 ) 剪枝步：由于候选项集c k 是频繁项集厶的超集，即侯选项集的成员中 可以有非频繁项集。为验汪候选项集的频繁性，需对数据库进行扫描，确定每一 候选项集的支持数，然后根据最小支持度卅加s “p ，确定频繁项集上。 下面是有关a d r i o “算法流程图： 图3 1a p r i o r i 算法流程罔 a p r i o r i 算法描述如下： 输入：事务数据库d ；最小支持度埘