《第三章关联规则挖掘理论和算法课件.ppt》由会员分享，可在线阅读，更多相关《第三章关联规则挖掘理论和算法课件.ppt（89页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、驾甄黎歹臆戍愿秧辽饵导悬哩攒番严即撬是雇独亚蚤典趟鹤酗矗邀祭椅替第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法1主讲：赵宏庆主讲：赵宏庆数据挖掘原理与算法数据挖掘原理与算法数据挖掘原理与算法数据挖掘原理与算法斜蠕膳耽丰许疗鞭詹藻腋饰持蠕初揉泉擎度怖级楷敖鞘赃窟讫艺沫权先占第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法1第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法连泥憨茎士梦釉煽具铆才耳雷撑古梆飘凋杆酗颅瞒迟掇购逛必苔种亨包泄第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法12Chinese Academy of Science第三章第三章 关联规
2、则挖掘理论和算法关联规则挖掘理论和算法v3.1 基本概念与解决方法基本概念与解决方法 v3.2 经典的频繁项目集生成算法分析经典的频繁项目集生成算法分析 v3.3 Apriori算法的性能瓶颈问题算法的性能瓶颈问题v3.4 Apriori的改进算法的改进算法v3.5 对项目集格空间理论的发展对项目集格空间理论的发展v3.6 项目集格空间和它的操作项目集格空间和它的操作v3.7 基于项目序列集操作的关联规则挖掘算法基于项目序列集操作的关联规则挖掘算法v3.8 改善关联规则挖掘质量问题改善关联规则挖掘质量问题v3.9 约束数据挖掘问题约束数据挖掘问题v3.10 关联规则挖掘中的一些更深入的问题关联
3、规则挖掘中的一些更深入的问题v3.11数量关联规则挖掘方法数量关联规则挖掘方法伯防辖靡醋垒以码装猩您摧攻耿晓启绩搀捶少厄讫品塌孙迟刃犀庇寸餐同第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法13Chinese Academy of Science关联规则挖掘是数据挖掘研究的基础关联规则挖掘是数据挖掘研究的基础v关联规则挖掘（关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。而且至今仍活跃的研究方法之一。v最早是由最早是由Agrawal等人提出的（等人提出的（1993）。最初提出的动机是针对购物）。最初
4、提出的动机是针对购物篮分析（篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数）问题提出的，其目的是为了发现交易数据库（据库（Transaction Database）中不同商品之间的联系规则。）中不同商品之间的联系规则。v关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（）以及数量关联规则挖掘（Quantitive Ass
5、ociation Rule Mining）等。）等。v关联规则挖掘是数据挖掘的其他研究分支的基础。关联规则挖掘是数据挖掘的其他研究分支的基础。收您钉惩懈现荫飘各矗逆泼刽厦况涧趟袜砷稳蚌煮宗钙致绢渍跌篆秃哄出第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法14Chinese Academy of Science3.1 基本概念与解决方法基本概念与解决方法v事务数据库事务数据库设设I=i1，i2，im 是一个项目集合，事务数据库是一个项目集合，事务数据库D=t1，t2，tn 是由一系列具有唯一标识是由一系列具有唯一标识TID的事务的事务组成，每个事务组成，每个事务ti（i=1，2，n）都
6、对应）都对应I上的一个上的一个子集。子集。一个事务数据库可以用来刻画：一个事务数据库可以用来刻画：购物记录：购物记录：I I是全部物品集合，是全部物品集合，D D是购物清单，每个元组是购物清单，每个元组t ti i是一次购买物品的集合（它当然是是一次购买物品的集合（它当然是I I的一个子集）。的一个子集）。其它应用问题其它应用问题凿讶大纳垛柏吾孔似浚埔超碱诵蔽痘笑止祥哗吟驶怯督彤邱涧灸射椿服苦第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法15Chinese Academy of Science支持度与频繁项目集支持度与频繁项目集 v定义（项目集的支持度）定义（项目集的支持度）.给定
7、一个全局项目集给定一个全局项目集I和数据库和数据库D，一个项目集，一个项目集I1 I在在D上的上的支持度支持度（Support）是是包含包含I1的事务在的事务在D中所占的百分比中所占的百分比：support（I1）=|t D|I1 t|/|D|。佩毋汰霄醇盾翼烹誓析咏甄特扫省则琵婉嗡芹距韦藻捻肪身雇隙息篆匿躬第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法16Chinese Academy of Science支持度与频繁项目集支持度与频繁项目集 v定义（频繁项目集）定义（频繁项目集）.给定全局项目集给定全局项目集I和数据库和数据库D，D中所有满足用户指定的最小中所有满足用户指定的最
8、小支持度（支持度（Minsupport）的项目集，即大于或等于）的项目集，即大于或等于minsupport的的I的非空子集，称为的非空子集，称为频繁项目集（频集：频繁项目集（频集：Frequent Itemsets）或者大项目集（或者大项目集（Large Iitemsets）。）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为称为最大频繁项目集（最大频集：最大频繁项目集（最大频集：Maximum Frequent Itemsets）或最大大项目集（或最大大项目集（Maximum Large Iitemsets）。嫉礼涩拷古鸦陕鲁似旅
9、匝帧饵报羡霍词摇腿魔雅糖阜均替凋适峨蛊诉辰嫩第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法17Chinese Academy of Science可信度与关联规则可信度与关联规则v定义（关联规则与可信度）定义（关联规则与可信度）.给定一个全局项目集给定一个全局项目集I和数据库和数据库D，一个定义在，一个定义在I和和D上的关联上的关联规则形如规则形如I1I2，并且它的，并且它的可信度可信度或或信任度信任度或或置信度置信度（Confidence）是指包含是指包含I1和和I2的事务数与包含的事务数与包含I1的事务数的事务数之比，之比，即即Confidence（I1I2）=support（
10、I1I2）/support（I1），），其中其中I1，I2 I，I1I2=。v定义（强关联规则）定义（强关联规则）.D在在I上满足最小支持度和最小信任度（上满足最小支持度和最小信任度（Minconfidence）的）的关联规则称为关联规则称为强关联规则（强关联规则（Strong Association Rule）。拷丑册贝檄频契尹岔用卡颧费叉滤摧赁韶绍拖蝗蔼灾鼠叮测畜途耍嗽然瘟第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法18Chinese Academy of Science关联规则挖掘基本过程关联规则挖掘基本过程v关联规则挖掘问题可以划分成两个子问题：关联规则挖掘问题可以划分成
11、两个子问题：1.发现频繁项目集发现频繁项目集:通过用户给定通过用户给定Minsupport，寻找，寻找所有频繁项目集或者最大频繁项目集。所有频繁项目集或者最大频繁项目集。2.生成关联规则生成关联规则:通过用户给定通过用户给定Minconfidence，在，在频繁项目集中，寻找关联规则。频繁项目集中，寻找关联规则。v第第1个子问题是近年来关联规则挖掘算法研究的重点。个子问题是近年来关联规则挖掘算法研究的重点。镑熙汗缴财锄惭帝殉粕咳兄绽咱沾誉枢场祥撒溯扇祥贡缨倘炭仲吵左姐民第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法19Chinese Academy of Science第三章第三章
12、 关联规则挖掘理论和算法关联规则挖掘理论和算法v3.1 基本概念与解决方法基本概念与解决方法 v3.2 经典的频繁项目集生成算法分析经典的频繁项目集生成算法分析 v3.3 Apriori算法的性能瓶颈问题算法的性能瓶颈问题v3.4 Apriori的改进算法的改进算法v3.5 对项目集格空间理论的发展对项目集格空间理论的发展v3.6 项目集格空间和它的操作项目集格空间和它的操作v3.7 基于项目序列集操作的关联规则挖掘算法基于项目序列集操作的关联规则挖掘算法v3.8 改善关联规则挖掘质量问题改善关联规则挖掘质量问题v3.9 约束数据挖掘问题约束数据挖掘问题v3.10 关联规则挖掘中的一些更深入的
13、问题关联规则挖掘中的一些更深入的问题v3.11数量关联规则挖掘方法数量关联规则挖掘方法错踊雾稳申兹咆罗编诊脯尼晋戚蓉麻扁掷哄猎左陌府函贩塌悉凝徊枕韩笑第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法110Chinese Academy of Science项目集格空间理论项目集格空间理论 vAgrawal等人建立了用于事务数据库挖掘的项目集格空等人建立了用于事务数据库挖掘的项目集格空间理论（间理论（1993,Apriori 属性）。属性）。v定理（定理（Apriori 属性属性1）.如果项目集如果项目集X 是频繁项目集，是频繁项目集，那么它的所有非空子集都是频繁项目集。那么它的所有非
14、空子集都是频繁项目集。v证明证明:设设X X是一个项目集，事务数据库是一个项目集，事务数据库T T 中支持中支持X X 的元组数为的元组数为s s。对。对X X的任的任一非空子集为一非空子集为Y Y，设，设T T中支持中支持Y Y的元组数为的元组数为s s1 1。根据项目集支持数的定义，很容易知道支持根据项目集支持数的定义，很容易知道支持X X 的元组一定支持的元组一定支持Y Y，所以所以s s1 1 s s，即，即supportsupport（Y Y）support support（X X）。）。按假设：项目集按假设：项目集X X 是频繁项目集，即是频繁项目集，即support(X)mins
15、upportsupport(X)minsupport，所以所以supportsupport（Y Y）support support（X X）minsupport minsupport，因此，因此Y Y是频繁是频繁项目集。项目集。抹黄镰效妻玩锨席虫腕奶涣涛再厢讫堕凿民玩管薛嵌嗅李掩仲茎嚣塌付后第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法111Chinese Academy of Science项目集格空间理论项目集格空间理论 v定理（定理（Apriori 属性属性2）.如果项目集如果项目集X 是非频繁项目集，是非频繁项目集，那么它的所有超集都是非频繁项目集。那么它的所有超集都是非频
16、繁项目集。证明证明 （略）（略）躇生谷患苔帮是沂规悬凰汤数怒字寅常勤伦拒翁琼闭箕楷克临羡讣还盈极第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法112Chinese Academy of Science经典的发现频繁项目集算法v1994年，年，Agrawal 等人提出了著名的等人提出了著名的Apriori 算法。算法。v算法算法3-1 Apriori（发现频繁项目集）（发现频繁项目集）输入：数据集输入：数据集D；最小支持数；最小支持数 minsup_count.输出：频繁项目集输出：频繁项目集L。（1）L1=large 1-itemsets;/所有所有1-项目频集项目频集（2）FOR
17、（k=2;Lk-1;k+）DO BEGIN（3）Ck=apriori-gen（Lk-1）;/Ck是是k-候选集候选集（4）FOR all transactions t D DO BEGIN（5）Ct=subset（Ck，t）;/Ct是所有是所有t包含的候选集元包含的候选集元素素（6）FOR all candidates c Ct DO（7）c.count+;（8）END（9）Lk=c Ck|c.count minsup_count（10）END（11）L=Lk;宠洽摩识啊沈榷瓮识饵邀罢礼栽蛾蘑军诸孰访第赛治林兜箕布杯廷绒淡驳第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法113Chi
18、nese Academy of Scienceapriori-gen过程过程v算法算法apriori中调用了中调用了apriori-gen（Lk-1），是为），是为了通过（了通过（k-1）-频集产生频集产生K-侯选集。侯选集。输入输入(k-1)-频繁项目集频繁项目集Lk-1输出输出k-候选项目集候选项目集Ckhas_infrequent_subset（c，Lk-1），判断），判断c是否加入是否加入到到k-侯选集中。侯选集中。（1）FOR all itemset p Lk-1 DO（2）FOR all itemset q Lk-1 DO（3）IF p.item1=q.item1，p.itemk-
19、2=q.itemk-2，p.itemk-1 1）THEN/generate rules with subsets of xm-1 as antecedents（7）genrules（lk，xm-1）;（8）END（9）END；铺实岩响墟纸擅寸荡交份琵西干履怖卢禁巡阐卢菠词汇酞枯尤嘱锗流剂绞第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法118Chinese Academy of ScienceRule-generate算法例子算法例子序号lkxm-1confidencesupport规则（是否是强规则）123523100%50%235（是）2235267%50%235（否）32353
20、67%50%325（否）42352567%50%253（否）5235567%50%523（否）623535100%50%352（是）Database D前面的例子最大频繁项目集为前面的例子最大频繁项目集为2 3 5conf=support（lk）/support（xm-1）Minconfidence=80%售研碑赠得啸葡永上搪灼楼度卑彤虱羡疚汝俗肥难撒缴蝎豁升练蛾桔寸服第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法119Chinese Academy of Science第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法v3.1 基本概念与解决方法基本概念与解决方法 v3.
21、2 经典的频繁项目集生成算法分析经典的频繁项目集生成算法分析 v3.3 Apriori算法的性能瓶颈问题算法的性能瓶颈问题v3.4 Apriori的改进算法的改进算法v3.5 对项目集格空间理论的发展对项目集格空间理论的发展v3.6 项目集格空间和它的操作项目集格空间和它的操作v3.7 基于项目序列集操作的关联规则挖掘算法基于项目序列集操作的关联规则挖掘算法v3.8 改善关联规则挖掘质量问题改善关联规则挖掘质量问题v3.9 约束数据挖掘问题约束数据挖掘问题v3.10 关联规则挖掘中的一些更深入的问题关联规则挖掘中的一些更深入的问题v3.11数量关联规则挖掘方法数量关联规则挖掘方法代侗乃鹿优难兄
22、续泉茎萌惯沪瘟婉籽药桓膊梁惑赘攒纵晴颤胀滇绦铀双模第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法120Chinese Academy of ScienceApriori算法的性能瓶颈算法的性能瓶颈 vApriori作为经典的频繁项目集生成算法，在数据作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。挖掘中具有里程碑的作用。vApriori算法有两个致命的性能瓶颈算法有两个致命的性能瓶颈:1多次扫描事务数据库，需要很大的多次扫描事务数据库，需要很大的I/O负载负载n 对每次对每次k循环，侯选集循环，侯选集Ck中的每个元素都必须通过扫中的每个元素都必须通过扫描数据库一次来验证
23、其是否加入描数据库一次来验证其是否加入Lk。n 假如有一个频繁大项目集包含假如有一个频繁大项目集包含10个项的话，那么就至个项的话，那么就至少需要扫描事务数据库少需要扫描事务数据库10遍。遍。邻伺涣害据滔礁春辅珐牌膏穷镭估豪娟验好败障足闻陆喘申群停溃型蔗校第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法121Chinese Academy of ScienceApriori算法的性能瓶颈算法的性能瓶颈 vApriori算法有两个致命的性能瓶颈算法有两个致命的性能瓶颈:2可能产生庞大的侯选集可能产生庞大的侯选集n 由由Lk-1产生产生k-侯选集侯选集Ck是指数增长的，例如是指数增长的，
24、例如104个个1-频繁项目集就有可能产生接近频繁项目集就有可能产生接近107个元素的个元素的2-侯选集。侯选集。n 如此大的侯选集对时间和主存空间都是一种挑战。如此大的侯选集对时间和主存空间都是一种挑战。提胡蹬恬鞋氛曾凉操据绎秒番碱力律剐绪膳记咳孜恤级涧判空刁吠巍蝉篱第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法122Chinese Academy of Science第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法v3.1 基本概念与解决方法基本概念与解决方法 v3.2 经典的频繁项目集生成算法分析经典的频繁项目集生成算法分析 v3.3 Apriori算法的性能瓶颈问题
25、算法的性能瓶颈问题v3.4 Apriori的改进算法的改进算法v3.5 对项目集格空间理论的发展对项目集格空间理论的发展v3.6 项目集格空间和它的操作项目集格空间和它的操作v3.7 基于项目序列集操作的关联规则挖掘算法基于项目序列集操作的关联规则挖掘算法v3.8 改善关联规则挖掘质量问题改善关联规则挖掘质量问题v3.9 约束数据挖掘问题约束数据挖掘问题v3.10 关联规则挖掘中的一些更深入的问题关联规则挖掘中的一些更深入的问题v3.11数量关联规则挖掘方法数量关联规则挖掘方法奎抒赫疑施钨咙娃波锡希桥舟耪积瓢钧淫缀坤榆捡逃圭味口居姑亢洼敖滇第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和
26、算法123Chinese Academy of Science提高提高Apriori算法效率的技术算法效率的技术v一些算法虽然仍然遵循一些算法虽然仍然遵循Apriori 属性，但是由于引入了相属性，但是由于引入了相关技术，在一定程度上改善了关技术，在一定程度上改善了Apriori算法适应性和效率。算法适应性和效率。淑既狄舍机菏引缀熄媚狞扁绝童燃较暗姚泅稠硫杆烩俺梦羹昆横腾泊贤病第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法124Chinese Academy of Science提高提高Apriori算法效率的技术算法效率的技术主要的改进方法有：主要的改进方法有：基于数据分割（基于
27、数据分割（Partition）的方法：基本原理是）的方法：基本原理是“在一个划在一个划分中的支持度小于最小支持度的分中的支持度小于最小支持度的k-项集不可能是全局频繁的项集不可能是全局频繁的”。基于散列（基于散列（Hash）的方法：基本原理是）的方法：基本原理是“在一个在一个hash桶内桶内支持度小于最小支持度的支持度小于最小支持度的k-项集不可能是全局频繁的项集不可能是全局频繁的”。基于采样（基于采样（Sampling）的方法：基本思想是先使用数据库）的方法：基本思想是先使用数据库的抽样数据得到一些可能成立的规则，然后利用数据库的剩的抽样数据得到一些可能成立的规则，然后利用数据库的剩余部分验
28、证这些关联规则是否正确。余部分验证这些关联规则是否正确。其他：动态删除没有用的事务：其他：动态删除没有用的事务：“不包含任何不包含任何Lk的事务对未的事务对未来的扫描结果不会产生影响，因而可以删除来的扫描结果不会产生影响，因而可以删除”。棵翟懒梆舱钉捞源惊陋送台膘痉普谭墅酒棍雨惦挺淬腮促搭稿槛骚嫩骤幌第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法125Chinese Academy of Science基于数据分割的方法v定理定理3-5 v 设数据集设数据集D被分割成分块被分割成分块D1，D2，Dn，全局最小，全局最小支持数为支持数为minsup_count。如果一个数据分块。如果
29、一个数据分块Di 的局部最的局部最小支持数小支持数minsup_counti（i=1，2，n），按着如下），按着如下方法生成：方法生成：minsup_counti=minsup_count*|Di|/|D|则所有的局部频繁项目集涵盖全局频繁项目集。则所有的局部频繁项目集涵盖全局频繁项目集。辱淋跌缩纵辙巫窟砸虱沉雏职近音胞洗延号舱暇颁促原概己续怨宋墅清暴第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法126Chinese Academy of Science基于数据分割的方法v作用：作用：1合理利用主存空间：合理利用主存空间：数据分割将大数据集分成小的数据分割将大数据集分成小的块，为块
30、内数据一次性导入主存提供机会。块，为块内数据一次性导入主存提供机会。2支持并行挖掘算法：支持并行挖掘算法：每个分块的局部频繁项目集是每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良独立生成的，因此提供了开发并行数据挖掘算法的良好机制。好机制。呢雇畴岁输嘲嚏嗜娟惜塞许拖沏砰柏泌浆婚牲炮哲力受强悍魔痴先唾裹刽第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法127Chinese Academy of Science基于散列的方法v1995，Park等发现寻找频繁项目集的主要计算是等发现寻找频繁项目集的主要计算是在生成在生成2-频繁项目集上。频繁项目集上。v因此，因此
31、，Park等利用了这个性质引入杂凑技术来改等利用了这个性质引入杂凑技术来改进产生进产生2-频繁项目集的方法。频繁项目集的方法。庶艺万姥陋介矫崖勾翁擎厄恢谊酮枝瑚伯蚊柯诅秀钳跃山膛肿螟旋槐败厦第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法128Chinese Academy of Science基于散列的方法v例子：桶地址桶地址=（10 x+y）mod 7；minsupport_count=3 TID Items1 I1，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2，I3桶地址桶地址 0
32、1 2 3 4 5 6桶计数桶计数TID=1,取取(x=1,y=2),得到桶地址得到桶地址=5，即在地址即在地址5下列出下列出I1，I2 I1，I2I1，I5I1，I5桶内桶内同理取同理取(x=1,y=5),(x=2,y=5),得的地址得的地址1和和4列出列出I1，I5,I2，I5银舅逞质羔嘱瓦挚飞蝶馏苞墒捅篮心姆覆桨奄舌扔吻伏潮猎煽颤匀修侮冰第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法129Chinese Academy of Science基于散列的方法v例子：桶地址桶地址=（10 x+y）mod 7；minsupport_count=3 TID Items1 I1，I2，I
33、52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2，I3桶地址桶地址 0 1 2 3 4 5 6桶计数桶计数 2 2 4 2 2 4 4桶内桶内 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I3，I5 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3L2=I2，I3，I1，I2，I1，I3 后面的方法的步骤与后面的方法的步骤与Apriori算法相同算法相同所以当所以当TID=1，2
34、.,9 可以得到下面的内容可以得到下面的内容邑老码注怯奸何范洪扯压尾范击讲羊蛇时搬慕非蜘凹巳关俐遂蹿讯级魔势第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法130Chinese Academy of Science第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法v3.1 基本概念与解决方法基本概念与解决方法 v3.2 经典的频繁项目集生成算法分析经典的频繁项目集生成算法分析 v3.3 Apriori算法的性能瓶颈问题算法的性能瓶颈问题v3.4 Apriori的改进算法的改进算法v3.5 对项目集格空间理论的发展对项目集格空间理论的发展v3.6 项目集格空间和它的操作项目集格
35、空间和它的操作v3.7 基于项目序列集操作的关联规则挖掘算法基于项目序列集操作的关联规则挖掘算法v3.8 改善关联规则挖掘质量问题改善关联规则挖掘质量问题v3.9 约束数据挖掘问题约束数据挖掘问题v3.10 关联规则挖掘中的一些更深入的问题关联规则挖掘中的一些更深入的问题v3.11数量关联规则挖掘方法数量关联规则挖掘方法绦湿涝蒂殿宁氨距养创瞄成抨津饱妥睛怔吭功高脆譬刨拨渭遥岿栏欺饭譬第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法131Chinese Academy of Science探索新的理论探索新的理论v随着数据库容量的增大，重复访问数据库（外存）将导致随着数据库容量的增大，
36、重复访问数据库（外存）将导致性能低下。性能低下。v因此，探索新的理论和算法来减少数据库的扫描次数和侯因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点选集空间占用，已经成为近年来关联规则挖掘研究的热点之一。之一。v两个典型的方法：两个典型的方法：Close算法算法 FP-tree算法算法 祷萌笺润衅渺账滑视等矩斥垃介车搅笆平氏傍甜浦斥琢睡奶妹籽冯安撅县第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法132Chinese Academy of ScienceClose算法对应的原理v一个频繁闭合项目集的所有闭合子集一定是频繁的；一个频繁
37、闭合项目集的所有闭合子集一定是频繁的；v一个非频繁闭合项目集的所有闭合超集一定是非频繁的。一个非频繁闭合项目集的所有闭合超集一定是非频繁的。v什么是一个闭合的项目集？什么是一个闭合的项目集？一个项目集一个项目集C是闭合的，当且仅当对于在是闭合的，当且仅当对于在C中的任何元中的任何元素，不可能在素，不可能在C中存在小于或等于它的支持度的子集。中存在小于或等于它的支持度的子集。例如，例如，C1=AB3，ABC2是闭合的；是闭合的；C2=AB2，ABC2不是闭合的；不是闭合的；伯舷育炉诺桃耙蠕迭厨唆逸粒打庙企颤涅韵勉嗣院商呸芳逼务影化别屹叔第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法1
38、33Chinese Academy of ScienceClose算法对应的原理vClose 算法最终需要通过频繁闭合项目集得到频繁项目集。算法最终需要通过频繁闭合项目集得到频繁项目集。v首先对频繁闭合项目集首先对频繁闭合项目集FC中的每个闭合项目集，计算它中的每个闭合项目集，计算它的项目个数，把所有项目个数相同的归入相应的的项目个数，把所有项目个数相同的归入相应的i-频繁项频繁项目集目集Li中。中。v例如，闭合项目集例如，闭合项目集AB,它的个数为它的个数为2(ABC它的个数为它的个数为3)，则把它加入则把它加入L2中。中。依此类推，将所有闭合项目集分配到相应的依此类推，将所有闭合项目集分配
39、到相应的Li中，同时得到最大中，同时得到最大的个数记为的个数记为k。然后从然后从k开始，对每个开始，对每个Li中的所以项目集进行分解，找到它的所有中的所以项目集进行分解，找到它的所有的的(i-1)-项子集。项子集。对每个子集，如果它不属于对每个子集，如果它不属于Li-1，则把它加入到，则把它加入到Li-1，直到，直到i=2，就，就找到所有的频繁项目集。找到所有的频繁项目集。烫蒂孝刚宏比歼肤篷髓巷娥痞疥净汐驼坑订榷攫枉梧急鄙宿况审换辫适伏第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法134Chinese Academy of ScienceClose算法的例子v例子：minsup=2
40、 TID Itemset TID Itemset 1 ABE 6 BC 2 BD 7 AC 3 BC 8 ABCE 4 ABD 9 ABC 5 AC署盲班休妹估重座锰顺委闯沉社淋雪坛软滋尚闷耘戎糕鼎角蕴中袒粥宝格第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法135Chinese Academy of ScienceClose算法的例子v(1)计算计算FCC1各个产生式的闭合和支持度各个产生式的闭合和支持度首先得到首先得到FCC1的产生式：的产生式：A、B、C、D、E。然后计算闭集合：然后计算闭集合：如计算如计算A的闭集合，的闭集合，取含取含A的的Itemset 每行每行的交集可得到
41、的交集可得到closure A=A,supprot=6得到得到FCC1的所有闭集合的所有闭集合GeneratorclosureSupportAA6BB7CC6DBD2EABE2左绥惠褪顾盔掣臭伟往黔田招贵拆气书诊籽悠坦砾拟膝腐孜谈狂格验狂科第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法136Chinese Academy of ScienceClose算法的例子v(2)进行修剪进行修剪将支持度小于最小支持度将支持度小于最小支持度(minsup=2)候选闭合项删除，候选闭合项删除，得到得到FC1。本例。本例FCC1=FC1犹痪挤哟豪估剃级檀属谣蛊咖僧态梆尧宝捞帖宏姑哎瞪刨膊废篷刽崭孺
42、卯第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法137Chinese Academy of ScienceClose算法的例子v(3)利用利用FC1的的generator生成生成FCC2先用先用Apriori相同的方法生成相同的方法生成2-项目集。然后将项目集。然后将FC1中是中是FCC2中的某个候选项的子集项选出来，记为中的某个候选项的子集项选出来，记为Sp。如果。如果FCC1的这的这一项是一项是Sp的字母的闭合项则删除，得到的字母的闭合项则删除，得到FCC2。对于本例，对于本例，FC1自身连接后得到的候选项为：自身连接后得到的候选项为：ABACADAEBCBDBECDCEDE,
43、均不含有非均不含有非频繁子集频繁子集(即把他们分别拆开后各个项都能在前一步中找到即把他们分别拆开后各个项都能在前一步中找到)。在利用在利用FC1筛选：由于筛选：由于AE是子集是子集E的闭合的闭合ABE的子集，的子集，BE是子集是子集E的闭合的闭合ABE的子集，所以将这两项删除，得的子集，所以将这两项删除，得到的候选项到的候选项FCC2=AB,AC,AD,BC,BD,CD,CE,DE。值得注意的是在值得注意的是在FCC2的元素中我们简单地用的元素中我们简单地用AB来代替上面来代替上面的的AB，主要的目的是在不会引起混淆的情况下表达简洁。，主要的目的是在不会引起混淆的情况下表达简洁。寂裸透懈勉颧像
44、坷沾痊岔拭虏幸盘疽华壁巧思戊涛游才秘狡得残酮乖良挞第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法138Chinese Academy of ScienceClose算法的例子v(4)计算各产生式的闭合和支持度计算各产生式的闭合和支持度由于由于FCC2不空，不空，CD和和DE的闭合为空，所以将它们从的闭合为空，所以将它们从FCC2中删除，且得到各产生式的支持度。中删除，且得到各产生式的支持度。GeneratorclosureSupportABAB4ACAC4ADABD1BCBC4BDBD2CEABCE1惊吴虚蜗木胶床谬瞪冰碟亏痹游樊彝斥店堂卿扬语半吭雀俐洪移恬使庸荒第三章关联规则挖掘
45、理论和算法1第三章关联规则挖掘理论和算法139Chinese Academy of ScienceClose算法的例子v(5)进行修剪进行修剪将支持度小于最小支持度将支持度小于最小支持度(minsup=2)候选闭合项删除，候选闭合项删除，得到得到FC2。这时候。这时候ADCE的支持度为的支持度为1被删除。被删除。FC2=AB,AC,BC,BDv(6)利用利用FC2的的generator生成生成FCC3,并进行剪裁并进行剪裁FC2连接后得到：连接后得到：ABC,BCD,其中其中BCD有非频繁子集有非频繁子集CD,所以将这两项删除。剩下为所以将这两项删除。剩下为ABC，得到的候选，得到的候选项项F
46、CC3=ABC.麦非蹭昏揖唇苍痈道御恬妇绣柴叹阎叛警三敏洲碟手桨智丛柯寿鼠强扇灿第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法140Chinese Academy of ScienceClose算法的例子v(7)FCC3不为空，计算各产生式的闭合和支持度不为空，计算各产生式的闭合和支持度ABC的闭合为的闭合为ABC，支持度为支持度为2v(8)进行修剪进行修剪将支持度小于最小支持度将支持度小于最小支持度(minsup=2)候选闭合项删除，候选闭合项删除，得到得到FC3。对本例。对本例FC3只有一项，支持度为只有一项，支持度为2，保留。，保留。v(9)利用利用FC3生成生成FCC4。为
47、空，算法结束。为空，算法结束。糜卧风砂隐枝坦矢况咏富凡议缅堪乖荣矛嘘壮晰伺控忧咐真溺匠截饲瑚吴第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法141Chinese Academy of ScienceClose算法的例子v将所有的不重复的闭合加入到将所有的不重复的闭合加入到FC中，得到中，得到FC=A,B,ABE,BD,C,AB,AC,BC,ABCv以下生成频繁项目集以下生成频繁项目集v(10)统计项目集元素数统计项目集元素数将所有的闭合项目集将所有的闭合项目集(上面的上面的FC)按元素的个数统计，按元素的个数统计，得到得到L3=ABC,ABE；L2=AB,AC,BC,BD；L1=A
48、,B,C。最大个数为最大个数为3稳卢嫌邻这殴庆虾莹摩感别夯系持诊贰牲甸舍涌酗辅扔先挪冷赂口蚁味拿第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法142Chinese Academy of ScienceClose算法的例子v(11)将将L3频繁项分解频繁项分解先分解先分解ABC的所有的所有2-项子集为项子集为ABAC和和BC这这3项均项均在在L2中。中。再分解再分解ABE，所有，所有2-项子集为项子集为ABAE和和BE,后两项后两项不存在，将它们加入到不存在，将它们加入到L2中，他们的支持度等于中，他们的支持度等于ABE的支持度。最后的支持度。最后L2为为BD,AB,AC,BC,AE
49、,BEv(12)将将L2频繁项分解频繁项分解方法同上，得到方法同上，得到L1=A,B,C,D,E豌匙额但骂鄂顺杀史类辫捞排茄原辙兴承埃奎蝗拓胖瞥纵蜒叙烬慧遍观房第三章关联规则挖掘理论和算法1第三章关联规则挖掘理论和算法143Chinese Academy of ScienceFP-tree算法的基本原理算法的基本原理v进行进行2次数据库扫描：一次对所有次数据库扫描：一次对所有1-项目的频度排序；一项目的频度排序；一次将数据库信息转变成紧缩内存结构。次将数据库信息转变成紧缩内存结构。v不使用侯选集，直接压缩数据库成一个频繁模式树，通不使用侯选集，直接压缩数据库成一个频繁模式树，通过频繁模式树可以
50、直接得到频集过频繁模式树可以直接得到频集。v基本步骤是：基本步骤是：两次扫描数据库，生成频繁模式树两次扫描数据库，生成频繁模式树FP-Tree：扫描数据库一次，得到所有扫描数据库一次，得到所有1-项目的频度排序表项目的频度排序表T；依照依照T，再扫描数据库，得到，再扫描数据库，得到FP-Tree。使用使用FP-Tree，生成频集：，生成频集：为为FP-tree中的每个节点生成条件模式库；中的每个节点生成条件模式库；用条件模式库构造对应的条件用条件模式库构造对应的条件FP-tree；递归挖掘条件递归挖掘条件FP-trees同时增长其包含的频繁集：同时增长其包含的频繁集：如果条件如果条件FP-tr