关联规则挖掘举例课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,6、纪律是自由的第一条件。黑格尔,7、纪律是集体的面貌，集体的声音，集体的动作，集体的表情，集体的信念。马卡连柯,8、我们现在必须完全保持党的纪律，否则一切都会陷入污泥中。马克思,9、学校没有纪律便如磨坊没有水。夸美纽斯,10、一个人应该：活泼而守纪律，天真而不幼稚，勇敢而鲁莽，倔强而有原则，热情而不冲动，乐观而不盲目。马克思,关联规则挖掘举例,关联规则挖掘举例6、纪律是自由的第一条件。黑格尔,7、纪律是集体的面貌，集体的声音，集体的动作，集体的表情，集体的信念。马卡连柯,8、我们现在必须完全保持党的纪律，否则一切都会陷入污泥中。马克思,9、学校没有纪律便如磨坊没有水。夸美纽斯,10、一个人应该：活泼而守纪律，天真而不幼稚，勇敢而鲁莽，倔强而有原则，热情而不冲动，乐观而不盲目。马克思关联规则挖掘举例关联规则挖掘举例对于规则 AC：,支持度 = support(A,C ) = 50%,置信度 = support(A,C )/support(A),= 66.6%假设最小值支持度为50%，最小置信度为50%规则AC满足最小支持度和最小置信度，所以它是强关联规则关联规则挖掘的步骤关联规则挖掘是一个两步的过程：,找出所有频繁项集,由频繁项集产生强关联规则，这些规则必须大于或者等于最小支持度和最小置信度,大于或者等于最小支持度的项集,关联规则挖掘举例,对于规则,A,C,：,支持度,= support(,A,C,) = 50%,置信度,= support(,A,C,)/support(,A,),= 66.6%,假设最小值支持度为,50%,，最小置信度为,50%,规则,A,C,满足最小支持度和最小置信度，所以它是,强关联规则,关联规则挖掘的步骤,关联规则挖掘是一个两步的过程：,找出所有,频繁项集,由频繁项集产生,强关联规则,，这些规则必须大于或者等于最小支持度和最小置信度,大于或者等于最小支持度的项集,Apriori,算法,Apriori,算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。,Apriori,算法将发现关联规则的过程分为两个步骤：,通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；,利用频繁项集构造出满足用户最小置信度的规则。,挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。,Apriori,算法的重要性质,性质,1,：频繁项集的子集必为频繁项集,性质,2,：非频繁项集的超集一定是非频繁的,假设项集,A,C,是频繁项集，则,A,和,C,也为频繁项集,假设项集,D,不是频繁项集，则,A,D,和,C,D,也不是频繁项集,Apriori,算法举例,现有,A,、,B,、,C,、,D,、,E,五种商品的交易记录表，找出所有频繁项集，假设最小支持度,=50%,最小置信度,=50%,Apriori,算法举例,_,产生频繁项集,K=1,支持度,50,K=2,支持度,50,支持度,50,Apriori,算法举例,_,产生频繁项集,支持度,50,支持度,50,Apriori,算法举例,_,产生关联规则,对于频繁项集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是据此获得的关联规则及其置信度。,规则,置信度,Confidence,B,CE,66.7%,C,BE,66.7%,E,BC,66.7%,CE,B,1,BE,C,66.7%,BC,E,1,置信度50%(最小置信度)，,都是强关联规则,Apriori,算法弊端,需要多次扫描数据表,如果频繁集最多包含,10,个项，那么就需要扫描交易数据表,10,遍，这需要很大的,I/O,负载,产生大量频繁集,若有,100,个项目，可能产生候选项数目,FP-growth,算法,Jiawei Han,等人在,2000,年提出了一种基于,FP-,树的关联规则挖掘算法,FP_growth,，它采取“分而治之”的策略，将提供频繁项目集的数据库压缩成一棵频繁模式树（,FP-,树）。,仅两次扫描数据库。,理论和实验表明该算法优于,Apriori,算法。,FP-growth,算法,其他关联规则挖掘算法,约束性关联规则挖掘算法,仅设置支持度和置信度阈值，缺乏用户控制，可能产生过多的规则，实际效果可能并不好。用户关心的是某些特定的关联规则，这需要把一些约束条件引入到挖掘算法中，从而筛选出符合约束条件的有用规则，提高算法的运行效率和用户满意度。,增量式关联规则挖掘算法,数据集不断增长，有新的数据加入后，重新挖掘很费时。增量式关联规则挖掘算法是当数据库变化后，在原挖掘结果的基础上生成新的关联规则，删除过时的关联规则。,多层关联规则挖掘,关联规则的价值衡量,客观上，使用“支持度和置信度”框架可能会产生一些不正确的规则。只凭支持度和置信度阈值未必总能找出符合实际的规则。,例：,歌曲,A,、歌曲,C,为小众歌曲，歌曲,B,为口水歌，共有,10,万个用户，有,200,个人听过歌曲,A,，这,200,个人里面有,60,个听过口水歌,B,，有,40,个人听过歌曲,C,。听过歌曲,C,的人数是,300,，听过口水歌,B,的人为,50000,。,Confidence(A,B) = 0.3,，,Confidence(A,C) = 0.2,但是,10W,人里面有,5W,听过歌曲,B,，有一半的用户都喜欢歌曲,B,，但听过歌曲,A,的人里面只有,30%,的人喜欢歌曲,B,听过歌曲,A,的人不喜欢歌曲,B,貌似,A,和,B,更相关,矛盾的规则，如何评价？,关联规则价值衡量,提升度,Lift(A,B,)=Confidence(A,B)/Support(B)=,引入提升度,Lift,，以度量此规则是否可用。它描述的是：相对于不用规则，使用规则可以提高多少。,Lift(A,B) =Confidence(A,B)/Support(B)=0.3/0.5=0.6,Lift(A,C)=,Confidence(A,C)/Support(C)=0.2/(300/100000)=66.7,歌曲,A,与,B,负相关，,A,与,C,正相关。,Lift,大于,1,，表示使用这条规则进行推荐能提升用户听歌曲,C,的概率。,Lift,小于,1,，则表示使用这条规则来进行推荐，还不如不推荐，让顾客自行选择好了。,Confidence(A,B) = 0.3,Confidence(A,C) = 0.2,Support(B)=0.5,Support(C)=300/100000,关联规则的价值衡量,主观上，,一个规则的有用与否最终取决于用户的感觉，,只有用户才能决定规则的有效性、可行性。所以，应该将需求和关联规则挖掘方法紧密地结合起来。例如使用“约束性关联规则挖掘算法”，将约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。,The end,jingwhale,谢谢你的阅读,知识就是财富,丰富你的人生,71,、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。,康德,72,、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。,西塞罗,73,、坚持意志伟大的事业需要始终不渝的精神。,伏尔泰,74,、路漫漫其修道远，吾将上下而求索。,屈原,75,、内外相应，言行相称。,韩非,