关联规则挖掘举例课件

关联规则挖掘的步骤关联规则挖掘是一个两步的过程：找出所有频繁项集由频繁项集产生强关联规则，这些规则必须大于或者等于最小支持度和最小置信度大于或者等于最小支持度的项集第1页/共16页关联规则挖掘的步骤关联规则挖掘是一个两步的过程：大于或者等于1Apriori算法Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小置信度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。第2页/共16页Apriori算法Apriori算法是一种经典的生成布尔型关2Apriori算法的重要性质性质1：频繁项集的子集必为频繁项集性质2：非频繁项集的超集一定是非频繁的假设项集{A,C}是频繁项集，则{A}和{C}也为频繁项集假设项集{D}不是频繁项集，则{A,D}和{C,D}也不是频繁项集第3页/共16页Apriori算法的重要性质假设项集{A,C}是频繁项集，则3Apriori算法举例现有A、B、C、D、E五种商品的交易记录表，找出所有频繁项集，假设最小支持度>=50%,最小置信度>=50%第4页/共16页Apriori算法举例现有A、B、C、D、E五种商品的交易记4Apriori算法举例_产生频繁项集K=1支持度<50K=2支持度<50支持度<50第5页/共16页Apriori算法举例_产生频繁项集K=1支持度<50K=25Apriori算法举例_产生频繁项集支持度<50支持度<50第6页/共16页Apriori算法举例_产生频繁项集支持度<50支持度<506Apriori算法举例_产生关联规则对于频繁项集{B,C,E},它的非空子集有{B}、{C}、{E}、{B,C}、{B,E}、{C,E}。以下就是据此获得的关联规则及其置信度。规则置信度ConfidenceBCE66.7%CBE66.7%EBC66.7%CEB1BEC66.7%BCE1置信度≥50%(最小置信度)，都是强关联规则第7页/共16页Apriori算法举例_产生关联规则对于频繁项集{B,C,E7Apriori算法弊端需要多次扫描数据表如果频繁集最多包含10个项，那么就需要扫描交易数据表10遍，这需要很大的I/O负载产生大量频繁集若有100个项目，可能产生候选项数目第8页/共16页Apriori算法弊端需要多次扫描数据表第8页/共16页8FP-growth算法JiaweiHan等人在2000年提出了一种基于FP-树的关联规则挖掘算法FP_growth，它采取“分而治之”的策略，将提供频繁项目集的数据库压缩成一棵频繁模式树（FP-树）。仅两次扫描数据库。理论和实验表明该算法优于Apriori算法。第9页/共16页FP-growth算法JiaweiHan等人在2000年提9FP-growth算法第10页/共16页FP-growth算法第10页/共16页10其他关联规则挖掘算法约束性关联规则挖掘算法仅设置支持度和置信度阈值，缺乏用户控制，可能产生过多的规则，实际效果可能并不好。用户关心的是某些特定的关联规则，这需要把一些约束条件引入到挖掘算法中，从而筛选出符合约束条件的有用规则，提高算法的运行效率和用户满意度。增量式关联规则挖掘算法数据集不断增长，有新的数据加入后，重新挖掘很费时。增量式关联规则挖掘算法是当数据库变化后，在原挖掘结果的基础上生成新的关联规则，删除过时的关联规则。多层关联规则挖掘……第11页/共16页其他关联规则挖掘算法约束性关联规则挖掘算法第11页/共16页11关联规则的价值衡量客观上，使用“支持度和置信度”框架可能会产生一些不正确的规则。只凭支持度和置信度阈值未必总能找出符合实际的规则。例：歌曲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更相关矛盾的规则，如何评价？第12页/共16页关联规则的价值衡量客观上，使用“支持度和置信度”框架可能会产12关联规则价值衡量提升度Lift(AB)=Confidence(AB)/Support(B)=引入提升度Lift，以度量此规则是否可用。它描述的是：相对于不用规则，使用规则可以提高多少。Lift(A→B)=Confidence(AB)/Support(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，则表示使用这条规则来进行推荐，还不如不推荐，让顾客自行选择好了。Confidence(A→B)=0.3Confidence(A→C)=0.2Support(B)=0.5Support(C)=300/100000第13页/共16页关联规则价值衡量提升度Lift(AB)=Confidenc13关联规则的价值衡量主观上，一个规则的有用与否最终取决于用户的感觉，只有用户才能决定规则的有效性、可行性。所以，应该将需求和关联规则挖掘方法紧密地结合起来。例如使用“约束性关联规则挖掘算法”，将约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。第14页/共16页关联规则的价值衡量第14页/共16页14Theendjingwhale第15页/共16页Theend第15页/共16页15感谢您的观赏！第16页/共16页感谢您的观赏！第16页/共16页16关联规则挖掘的步骤关联规则挖掘是一个两步的过程：找出所有频繁项集由频繁项集产生强关联规则，这些规则必须大于或者等于最小支持度和最小置信度大于或者等于最小支持度的项集第1页/共16页关联规则挖掘的步骤关联规则挖掘是一个两步的过程：大于或者等于17Apriori算法Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小置信度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。第2页/共16页Apriori算法Apriori算法是一种经典的生成布尔型关18Apriori算法的重要性质性质1：频繁项集的子集必为频繁项集性质2：非频繁项集的超集一定是非频繁的假设项集{A,C}是频繁项集，则{A}和{C}也为频繁项集假设项集{D}不是频繁项集，则{A,D}和{C,D}也不是频繁项集第3页/共16页Apriori算法的重要性质假设项集{A,C}是频繁项集，则19Apriori算法举例现有A、B、C、D、E五种商品的交易记录表，找出所有频繁项集，假设最小支持度>=50%,最小置信度>=50%第4页/共16页Apriori算法举例现有A、B、C、D、E五种商品的交易记20Apriori算法举例_产生频繁项集K=1支持度<50K=2支持度<50支持度<50第5页/共16页Apriori算法举例_产生频繁项集K=1支持度<50K=221Apriori算法举例_产生频繁项集支持度<50支持度<50第6页/共16页Apriori算法举例_产生频繁项集支持度<50支持度<5022Apriori算法举例_产生关联规则对于频繁项集{B,C,E},它的非空子集有{B}、{C}、{E}、{B,C}、{B,E}、{C,E}。以下就是据此获得的关联规则及其置信度。规则置信度ConfidenceBCE66.7%CBE66.7%EBC66.7%CEB1BEC66.7%BCE1置信度≥50%(最小置信度)，都是强关联规则第7页/共16页Apriori算法举例_产生关联规则对于频繁项集{B,C,E23Apriori算法弊端需要多次扫描数据表如果频繁集最多包含10个项，那么就需要扫描交易数据表10遍，这需要很大的I/O负载产生大量频繁集若有100个项目，可能产生候选项数目第8页/共16页Apriori算法弊端需要多次扫描数据表第8页/共16页24FP-growth算法JiaweiHan等人在2000年提出了一种基于FP-树的关联规则挖掘算法FP_growth，它采取“分而治之”的策略，将提供频繁项目集的数据库压缩成一棵频繁模式树（FP-树）。仅两次扫描数据库。理论和实验表明该算法优于Apriori算法。第9页/共16页FP-growth算法JiaweiHan等人在2000年提25FP-growth算法第10页/共16页FP-growth算法第10页/共16页26其他关联规则挖掘算法约束性关联规则挖掘算法仅设置支持度和置信度阈值，缺乏用户控制，可能产生过多的规则，实际效果可能并不好。用户关心的是某些特定的关联规则，这需要把一些约束条件引入到挖掘算法中，从而筛选出符合约束条件的有用规则，提高算法的运行效率和用户满意度。增量式关联规则挖掘算法数据集不断增长，有新的数据加入后，重新挖掘很费时。增量式关联规则挖掘算法是当数据库变化后，在原挖掘结果的基础上生成新的关联规则，删除过时的关联规则。多层关联规则挖掘……第11页/共16页其他关联规则挖掘算法约束性关联规则挖掘算法第11页/共16页27关联规则的价值衡量客观上，使用“支持度和置信度”框架可能会产生一些不正确的规则。只凭支持度和置信度阈值未必总能找出符合实际的规则。例：歌曲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更相关矛盾的规则，如何评价？第12页/共16页关联规则的价值衡量客观上，使用“支持度和置信度”框架可能会产28关联规则价值衡量提升度Lift(AB)=Confidence(AB)/Support(B)=引入提升度Lift，以度量此规则是否可用。它描述的是：相对于不用规则，使用规则可以提高多少。Lift(A→B)=Confidence(AB)/Support(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，则表示使用这条规则来进行推荐，还不如不推荐，让顾客自行选择好了。Confidence(A→B)=0.3Confidence(A→C)=0.2Support(B)=0.5Support(C)=300/100000第13页/共16页关联规