关联规则挖掘——Apriori算法.ppt

关联规则Apriori挖掘 1 1概述 关联规则 AssociationRuleMining 挖掘是数据挖掘中最活跃的研究方法之一最早是由R Agrawal等人提出的其目的是为了发现超市交易数据库中不同商品之间的关联关系 一个典型的关联规则的例子是 70 购买了牛奶的顾客将倾向于同时购买面包 经典的关联规则挖掘算法 Apriori算法和FP growth算法 1 2引例 假定某超市销售的商品包括 bread bear cake cream milk和tea 1 2引例 定义1 1项目与项集设I i1 i2 im 是m个不同项目的集合 每个ik k 1 2 m 称为一个项目 Item 项目的集合I称为项目集合 Itemset 简称为项集 其元素个数称为项集的长度 长度为k的项集称为k 项集 k Itemset 1 2引例 定义1 2交易每笔交易T Transaction 是项集I上的一个子集 即T I 但通常T I 对应每一个交易有一个唯一的标识 交易号 记作TID交易的全体构成了交易数据库D 或称交易记录集D 简称交易集D 交易集D中包含交易的个数记为 D 1 2引例 定义1 3项集的支持度对于项集X X I 设定count X T 为交易集D中包含X的交易的数量项集X的支持度support X 就是项集X出现的概率 从而描述了X的重要性 1 2引例 定义1 5关联规则关联规则 AssociationRule 可以表示为一个蕴含式 R X Y 1 2引例 定义1 6关联规则的支持度对于关联规则R X Y 其中X I Y I 并且X Y 规则R的的支持度 Support 是交易集中同时包含X和Y的交易数与所有交易数之比 1 2引例 定义1 7关联规则的可信度对于关联规则R X Y 其中X I Y I 并且X Y 规则R的可信度 Confidence 是指包含X和Y的交易数与包含X的交易数之比 1 2引例 定义1 8关联规则的最小支持度和最小可信度关联规则的最小支持度也就是衡量频繁集的最小支持度 MinimumSupport 记为supmin 它用于衡量规则需要满足的最低重要性 规则的最小可信度 MinimumConfidence 记为confmin 它表示关联规则需要满足的最低可靠性 1 2引例 定义1 9强关联规则如果规则X Y满足 support X Y supmin且confidence X Y confmin 称关联规则X Y为强关联规则 否则称关联规则X Y为弱关联规则 在挖掘关联规则时 产生的关联规则要经过supmin和confmin的衡量 筛选出来的强关联规则才能用于指导商家的决策 1 Apriori算法 Apriori算法命名源于算法使用了频繁项集性质的先验 Prior 知识 Apriori算法将发现关联规则的过程分为两个步骤 通过迭代 检索出事务数据库中的所有频繁项集 即支持度不低于用户设定的阈值的项集 利用频繁项集构造出满足用户最小信任度的规则 挖掘或识别出所有频繁项集是该算法的核心 占整个计算量的大部分 Apriori的性质 性质1 频繁项集的所有非空子集必为频繁项集 性质2 非频繁项集的超集一定是非频繁的 Apriori的步骤 连接步 为找Lk 通过将Lk 1与自身连接产生候选k项集的集合剪枝步 Ck是Lk的超集 也就是说 Ck的成员可以是也可以不是频繁的 但所有的频繁k项集都包含在Ck中 任何非频繁的 k 1 项集都不是频繁k项集的子集 4 3 1Apriori算法 1 3 1Apriori算法 apriori gen Lk 1 supmin 算法 1 3 1Apriori算法 has infrequent subset c Lk 1 算法 Apriori算法实例 现有A B C D E五种商品的交易记录表 试找出三种商品关联销售情况 k 3 最小支持度 50 实例解答 K 1 支持度 50 Apriori算法的不足 可能产生大量的候选集需要重复扫描数据库 自己对Apriori小改进 在拼接存储时采用前缀树Trie优点 在拼接和剪枝时节约寻找时间 Trie 一个节点的所有子孙节点拥有与该节点相同的字符串前缀 根节点与空字符串相关联 并不是每个节点都与值关联 仅叶节点和部分内部节点与值关联 Trie 性质 根节点不包含字符 除根节点外每一个节点都只包含一个字符 从根节点到某一节点 路径上经过的字符连接起来 为该节点对应的字符串 每个节