关联规则挖掘举例.ppt

关联规则挖掘举例 对于规则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 Apriori算法举例 产生频繁项集 Apriori算法举例 产生关联规则 对于频繁项集 B C E 它的非空子集有 B C E B C B E C E 以下就是据此获得的关联规则及其置信度 置信度 50 最小置信度 都是强关联规则 Apriori算法弊端 需要多次扫描数据表如果频繁集最多包含10个项 那么就需要扫描交易数据表10遍 这需要很大的I O负载产生大量频繁集若有100个项目 可能产生候选项数目 FP growth算法 JiaweiHan等人在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 6Lift 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 3Confidence A C 0 2Support B 0 5Support C 300 100000 关联规则的价值衡量 主观上 一个规则的有用与否最终取决于用户的感觉 只有用户才能决定规则的有效性 可