资源预览内容
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
第9页 / 共16页
第10页 / 共16页
亲,该文档总共16页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
关联规则挖掘举例,对于规则 AC: 支持度 = support(A,C ) = 50% 置信度 = support(A,C )/support(A) = 66.6%,假设最小值支持度为50%,最小置信度为50%,规则AC满足最小支持度和最小置信度,所以它是强关联规则,关联规则挖掘的步骤,关联规则挖掘是一个两步的过程: 找出所有频繁项集 由频繁项集产生强关联规则,这些规则必须大于或者等于最小支持度和最小置信度,大于或者等于最小支持度的项集,Apriori算法,Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。 Apriori算法将发现关联规则的过程分为两个步骤: 通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集; 利用频繁项集构造出满足用户最小置信度的规则。 挖掘或识别出所有频繁项集是该算法的核心,占整个计算量的大部分。,Apriori算法的重要性质,性质1:频繁项集的子集必为频繁项集 性质2:非频繁项集的超集一定是非频繁的,假设项集A,C是频繁项集,则A和C也为频繁项集,假设项集D不是频繁项集,则A,D和C,D也不是频繁项集,Apriori算法举例_产生频繁项集,K=1,支持度50,Apriori算法举例_产生频繁项集,Apriori算法举例_产生关联规则,对于频繁项集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是据此获得的关联规则及其置信度。,置信度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(AB) = 0.3,Confidence(AC) = 0.2,但是10W人里面有5W听过歌曲B,有一半的用户都喜欢歌曲B,但听过歌曲A的人里面只有30%的人喜欢歌曲 B,听过歌曲A的人不喜欢歌曲B,貌似A和B更相关,矛盾的规则,如何评价?,关联规则价值衡量,提升度,Lift(AB)=Confidence(AB)/Support(B)=,引入提升度Lift,以度量此规则是否可用。它描述的是:相对于不用规则,使用规则可以提高多少。 Lift(AB) =Confidence(AB)/Support(B)=0.3/0.5=0.6 Lift(AC)= Confidence(AC)/Support(C)=0.2/(300/100000)=66.7 歌曲A与B负相关,A与C正相关。 Lift大于1,表示使用这条规则进行推荐能提升用户听歌曲C的概率。 Lift小于1,则表示使用这条规则来进行推荐,还不如不推荐,让顾客自行选择好了。,Confidence(AB) = 0.3 Confidence(AC) = 0.2 Support(B)=0.5 Support(C)=300/100000,关联规则的价值衡量,主观上,一个规则的有用与否最终取决于用户的感觉,只有用户才能决定规则的有效性、可行性。所以,应该将需求和关联规则挖掘方法紧密地结合起来。例如使用“约束性关联规则挖掘算法”,将约束条件与算法紧密结合,既能提高数据挖掘效率,又能明确数据挖掘的目标。,The end jingwhale,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号