




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、关联规则简介关联规则关联规则(Association Rules)反映一个事物与 其他事物之间的相互依存性和关联性。如果两个或 者多个事物之间存在一定的关联关系,那么,其中 一个事物就能够通过其他事物预测到。首先被 Agrawal, Imielinski and Swami在 1993年的 SIGMOD会议上提出.关联规则挖掘是数据挖掘中最活跃的研究方法之一 。典型的关联规则发现问题是对超市中的购物篮数 据(Market Basket)进行分析。通过发现顾客放 入购物篮中的不同商品之间的关系来分析顾客的购 头习惯。案例“尿布与啤酒”的故事。美国的沃尔玛超市对一年多的原始交易数据进行了详细的 分
2、析,得到一个意外发现:与尿布一起被购买最多的商品竟然是啤酒。借助于数据仓库和关联规则,商家发现了这个隐藏在背后的事实:美国的妇女们经常会嘱咐她们的丈 夫下班以后要为孩子买尿布,而30%40%的丈夫在买完尿布之后又要顺便购买自己爱喝的啤酒。有了这个发现后 ,超市调整了货架的设置,把尿布和啤酒摆放在一起销售 ,从而大大增加了销售额。 70%购买了牛奶的顾客将倾向于同时购买面包。 某网上书店向用户推荐相关书籍。案例案例购买本商品的顾客还买过数字化生存-盘数宇化生存导读-互联网:碎片化生存众声喧哗一一网络时代的公众舆论注薄:互联网如何毒化了长尾理论zo (超级财经世界是平的一一21世纪简-失控:全人类
3、的最终命运商业的常识(李开 复、牛文文¥22.80更多Nim!(数字化生存案例在买了一台PC之后下一步会购买?辰吕(Acer ) VX275台式电脑(E67案例案例浏费了该曲品的用户还浏贤了案例K10U立怎臣至列漫步古Udif: &r)咅福B101V入i強系列VOLEl-PAD)黒色比 标垫专洪)环宇飞扬Hying) V6无瓯:呱您头硕关科(SWUC)耳机M-2102飞利浦(FI订gs) SPA1312罢色案例在保险业务方面,如果出现了不常见的索赔要求组 合,则可能为欺诈,需要作进一步的调查;在医疗方面,可找出可能的治疗组合;在银行方面,对顾客进行分析,可以推荐感兴趣的 服务
4、等等。关联规则基本模型什么是规则?规则形如”如果那么(lf.Thg.J,前者为条件,后者 为结果。例如一个顾客,如果买了可乐,那么他也会购买 果汁。如何来度量一个规则是否够好?有两个量,置信度(Confidence)支持度(Support) 假设有如下表的购买记录。关联规则基本模型一置信度顾客项目1橙汁,可乐2牛奶,橙汁,空气清洁器3橙汁,洗洁精4橙汁,洗洁精,可乐5空气清洁器置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为代结果的集合为B。置信度计算在A中,同时也含有B的概率醱:if A,then B的概率。即Co n fide nee (A B)=P(B/A)。例如计算如果 O
5、range 则Coke”的置信度。由于在含有“橙汁”的4条交易中,仅有2条交易含有“可乐” o其置信度为0.5。关联规则基本模型支持度顾客项目1橙汁,可乐2牛奶,橙汁,空气清洁器3橙汁,洗洁精4橙汁,洗洁精,可乐5空气清洁器支持度计算在所有的交易集中,既有A又有B的概率。例 如在5条记录中,既有橙汁又有可乐的记录有2条。则此 条规则的支持度为 2/5=0.4, Support(AB)=P(AB).现在这条规则可表述为,如果一个顾客购买了橙汁,则有 50%(置信度)的可能购买可乐。而这样的情况(即买了橙 汁会再买可乐)会有40%(支持度)的可能发生。关联规则的相关概念定义1项目与项集设l=il是
6、m个不同项目的集合,每个ik(k=l, 2, ,m)称为一个项目(Item)。项目的集合I称为项目集合(Itemset),简称为项集 。其元素个数称为项集的长度,长度为k的项集称 为 k-项集(k-ltemset)o关联规则的相关概念定义2交易每笔交易丁仃ransaction)是项集I上的一个子集, 即Td,但通常Tul。对应每交易有唯一的标识交易号,记作TID交易的全体构成了交易数据库D,或称交易记录 集D,简称交易集D。交易集D中包含交易的个数记为|D|。关联规则的相关概念定义3项集的支持度对于项集X, Xul,设定count(XcT)为交易集D中 包含X的交易的数量support(X)=
7、count(X 匸 T)IDI项集X的支持度support(X)就是项集X出现的概率, 从而描述了 X的重要性。定义4项集的最小支持度与频繁集发现关联规则要求项集必须满足的最小支持阈值,称为项集的最小支持度(Minimum Support),记为 Slipmino支持度大于或等于SUpmin的项集称为频繁项集,简 称频繁集,反之则称为非频繁集。適常kJ贡集如果满足Slipmin?称为k频繁集,记作Lk。关联规则的相关概念定义5关联规则关联规WJ(Association Rule)可以表示为一个蕴含式: R: XnY其中:Xul, Yul,并且XcY=。例如:R:牛奶面包关联规则的相关概念定义6
8、关联规则的支持度对于关联规则R: XnY,其中Xul, Yul,并且 XcY=。规则R的的支持度(Support)是交易集中同时包含X 和Y的交易数与所有交易数之比。support (X=> Y)=count(XoY)IDI关联规则的相关概念定义7关联规则的置信度对于关联规则R: XnY,其中Xul,Yul,并且XcY=。规则R的置信度(Confidence)是指包含X和丫的交易 数与包含X的交易数之比confidence (X => Y)=support(X<j Y) support(X)一般来说,只有支持度和置信度均较高的关联规则 才是用户感兴趣的、有用的关联规则。定义8
9、关联规则的最小支持度和最小置信度关联规则的最小支持度也就是衡量频繁集的最小支 持度(Minimum Support),记为supmin,它用于衡 量规则需要满足的最低重要性。关联规则的最小置信度(Minimum Confidence)记为 confmin,它表示关联规则需要满足的最低可靠性。关联规则的相关概念定义9强关联规则如果规则 R:XnY 满足 support(X=>Y)>supmin 且 confidence(X=>Y)>confmin ,称关联规则XnY为 强关联规则,否则称关联规则XnY为弱关联规则。 在挖掘关联规则时,产生的关联规则要经过 supmin和c
10、onfmin的衡量,筛选出来的强关联规则 才能用于指导商家的决策。关联规则挖掘举例交易ID购买商品频繁项集支持度2000ABCA75%1000AQ1850%4000AQ©50%5000b5e5fA3C50%假设最小值支持度为50% ,最小置信度为50%对于规则A>C:支持度=support(/l,C) = 50%卜置信度=support(4,C)/support(/)二 66.6%规则4=懾 足最小支持度和最小置信 度,所以它是强关联规则关联规则挖掘的步骤关联规则挖掘是一个两步的过程:找出所有频繁项集大于或者等于最小支持度 的项集Fa由频繁项集产生强关联规则,这些规则必须大于
11、或者等于最小支持度和最小置信度Apriori 算法Apriori算法是一种经典的生成布尔型关联规则的频 繁项集挖掘算法。Apriori算法将发现关联规则的过程分为两个步骤:通过迭代,检索出事务数据库中的所有频繁项集, 即支持度不低于用户设定的阈值的项集;利用频繁项集构造岀满足用户最小置信度的规则。挖掘或识别岀所有频繁项集是该算法的核心,占整 个计算量的大部分。Apriori算法的重要性质假设项集A,C是频繁项集,则A和C也为频繁项集性质1:频繁项集的子集必为频繁项集性质2:非频繁项集的超集一定是非频繁的设项集D不是频繁项集,则A,D?nC,Dtfe不是频繁项集Apriori算法举例现有A、B.
12、 C、D、E五种商品的交易记录表,找出所 有频繁项集,假设最小支持度>二50%,最小置信度 >=50%交易号商品代码T1A、C、DT2B、C、ET3A、 B、 C、 ET4B、EApriori算法举例_产生频繁项集项集支持度ClA50%B75%©75%支持度50E75%L2A,C50%B,C50%B,E75%C,E50%ftLlA50%B75%C75%E75%VK=2C2项集支持度支持度50A.C150%支持度50B,C50%B,E75%C,E50%AprioriM法举例_产生频繁项集L2A,C50%B,C50%B,E75%C,E50%从K2中求可用来计算的的三项集A,C
13、 +B,CA,B,CA,C +B,E超过三项A,C +C,EA,C, EB,C +B,EB,C, EB,C +C,EB,C, E.B,E +C,EB,C, EL3 B, C, E 50%C3支持度v501 支持度50B,C, E50%Apriori算法举例_产生关联规则对于频繁项集B,C,E,它的非空子集有B、C、E 、B,C、B,E、C,EO以下就是据此获得的关联 规则及其置信度。规则置信度 ConfidenceBTCE66.7%CTBE66.7%ETBC66.7%CETB1BETC66.7%BCTE1置信度 5 0%(最小置信度), 都是强关联规则FP-growth 算法Jiawei Ha
14、n等人在2000年提出了一种基于FP-树的 关联规则挖掘算法FP_growth,它采取“分而治之” 的策略,将提供频繁项目集的数据库压缩成一棵频 繁模式树(FP-树)o仅两次扫描数据库。理论和实验表明该算法优于Apriori算法。FP-growth 算法其他关联规则挖掘算法约束性关联规则挖掘算法仅设置支持度和置信度阈值,缺乏用户控制,可能产生过多的规则,实际 效果可能并不好。用户关心的是某些特定的关联规则,这需要把一些约束 条件引入到挖掘算法中,从而筛选出符合约束条件的有用规则,提高算法 的运行效率和用户满意度。»增量式关联规则挖掘算法数据集不断增长,有新的数据加入后,重新挖掘很费时
15、。增量式关联规则 挖掘算法是当数据库变化后,在原挖掘结果的基础上生成新的关联规则, 删除过时的关联规则。多层关联规则挖掘关联规则的价值衡量客观上 使用“支持度和置信度”框架可能会产生 一些不正确的规则。只凭支持度和置信度阈值未必 总能找出符合实际的规则。例:歌曲A、歌曲C为小众歌曲,歌曲B为口水歌,共有10万个用户,有200个人听过歌曲A,这200个人里面有60个听过口水歌B,有40个人听过歌曲C。听过歌曲C的人数是300,听过口水歌B的人为50000o貌似A和B更相关Confidence(A->B) = 0.3, Confidence(A->C) = 0.2听过歌曲A的 不喜欢歌
16、曲 B但是10W人里面有5W听过歌曲B,有一半的用户都喜欢歌曲B,但听过歌曲A的人里面只有30%的人喜欢歌曲B矛盾的规则,如何评价?关联规则价值衡量Co n fi d e n c e (A-B073Con fide nce(AC) = 0.2 Support(B)=0.5 Support(C)=300/l 00000提升度n(ABLift(A9 B)=Confidence(A B)/Support(B)=_H 丿_ p(A)p(B)引入提升度Lift,以度量此规则是否可用。它描述的是:相对 于不用规则,使用规则可以提高多少。Lift(AB) =Confidence(A->B)/Suppo
17、rt(B)=0.3/0.5=0.6Lift(A->C)=Confidence(AC)/Support(C)=0.2/(300/100000)=66.7歌曲A与B负相关,A与C正相关。Lift大于1,表示使用这条规则进行推荐能提升用户听歌曲C的 概率。Lift小于1,则表示使用这条规则来进行推荐,还不如不推荐, 盛1行选择好了。关联规则的价值衡量主观上,一个规则的有用与否最终取决于用户的感 觉,只有用户才能决定规则的有效性、可行性。所以, 应该将需求和关联规则挖掘方法紧密地结合起来。例 如使用“约束性关联规则挖掘算法”,将约束条件与 算法紧密结合,既能提高数据挖掘效率,又能明确数 据挖掘的目标。参考文献:高明关联规则挖掘算法的研究及其应用
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 从教育改革视角探索创新人才培养的新方法
- 那个温暖的背影写人7篇范文
- 乡村绿色生态与健康生活方式推广
- 汽车维修技术实操训练题
- 2025年医学影像技术考试试题及答案
- 2025年环境法学专业考研复习试卷及答案
- 2025年基础教育与教育改革的呼应能力的测试试卷及答案
- 2025年法学专业实习考核试卷及答案
- 2025年大数据与人工智能相关知识考试试卷
- 2025年甘肃省民航机场集团校园招聘45人笔试备考试题带答案详解
- GB/T 21446-2008用标准孔板流量计测量天然气流量
- 无领导小组面试评分表
- 大学语文-第四讲魏晋风度和魏晋文学-课件
- 我们毕业啦毕业季通用模板课件
- 小升初数学复习八(平面图形)讲义课件
- (完整版)基建建设工程流程图
- 公司金融课件(完整版)
- 墙体开槽技术交底及记录
- 国家开放大学《调剂学(本)》形考任务1-4参考答案
- 公务员工资套改和运行案例
- 哥尼斯堡七桥问题PPT课件
评论
0/150
提交评论