机器学习-FPGROWTH算法 PPT课件

机器学习 FP GROWTH算法 李家豪 目录 2 回忆Apriori算法 3 项集 项的集合称为项集 即商品的组合 k项集 k件商品的组合 不关心商品件数 仅商品的种类 频繁项集 如果项集的相对支持度满足给定的最小支持度阈值 则该项集是频繁项集 强关联规则 满足给定支持度和置信度阈值的关联规则支持度 support A B P AB 置信度 confidence A B P A B 回忆Apriori算法 4 回忆Apriori算法 5 Apriori算法的挑战 6 挑战多次数据库扫描巨大数量的候补项集繁琐的支持度计算改善Apriori 基本想法减少扫描数据库的次数减少候选项集的数量简化候选项集的支持度计算 FP GROWTH算法优点 相比Apriori算法需要多次扫描数据库 FPGrowth只需要对数据库扫描2次 第1次扫描事务数据库获得频繁1项集 第2次扫描建立一颗FP Tree树 7 FP GROWTH算法原理 实例1 要找总是一起购买的商品 比如 薯片 鸡蛋 就是一条频繁模式 规律 8 FP GROWTH算法原理 实例1 统计频次 Step1 先扫描数据库 统计所有商品的出现次数 频数 然后按照频数递减排序 删除频数小于最小支持度的商品 设最小支持度数为 minsup 4统计频数 牛奶6 鸡蛋7 面包7 薯片7 爆米花2 啤酒4 黄油2 降序排序 薯片7 鸡蛋7 面包7 牛奶6 啤酒4 删除小于minsup的商品 9 频繁1项集 记为F1 FP GROWTH算法原理 实例1 重新排序 10 Step2 对每一条数据记录 按照F1重新排序 FP GROWTH算法原理 实例1 建立FP树 11 Step3 把第二步重新排序后的记录 插入到fp tree中Step3 1 插入第一条 第一步有一个虚的根节点 FP GROWTH算法原理 实例1 建立FP树 12 Step3 2 插入第二条 根结点不管 然后插入薯片 在step3 1的基础上 1 则记为2 同理鸡蛋记为2 啤酒在step3 1的树上是没有的 那么就开一个分支 FP GROWTH算法原理 实例1 建立FP树 13 Step3 3 插入第三条 FP GROWTH算法原理 实例1 建立FP树 14 同理 剩余记录依次插入fp tree中 FP GROWTH算法原理 实例1 建立FP树 15 图中左边的一列叫做头指针表 树中相同名称的节点要链接起来 链表的第一个元素就是头指针表里的元素 虚线连接起来的表示同一个商品 各个连接的数字加起来就是该商品出现的总次数 FP GROWTH算法原理 实例1 挖掘频繁项集 Step4 从FP Tree中找出频繁项集 遍历表头项中的每一项 以 牛奶 6 为例 从FP Tree中找到所有的 牛奶 结点 向上遍历它的祖先结点 得到4条路径 如表所示 16 FP GROWTH算法原理 实例1 挖掘频繁项集 Step4 从FP Tree中找出频繁项集 对于每一条路径上的节点 其count都设置为牛奶的count 路径中最末尾的商品数 17 FP GROWTH算法原理 实例1 挖掘频繁项集 Step4 从FP Tree中找出频繁项集 因为每一项末尾都是牛奶 可以把牛奶去掉 得到条件模式基 此时的后缀模式是 牛奶 18 FP GROWTH算法原理 实例2 把例子简化一下 请看以下实例2 19 FP GROWTH算法原理 实例2 统计频次 先扫描数据库 统计所有商品的出现次数 频数 定义min sup 2 按照频数递减排序 删除频数小于最小支持度的商品 重新排列得到频繁1 项目集F 20 FP GROWTH算法原理 实例2 重新排序 21 FP GROWTH算法原理 实例2 创建根结点和频繁项目表 22 Null FP GROWTH算法原理 实例2 加入第一个事务 I2 I1 I5 23 FP GROWTH算法原理 实例2 加入第二个事务 I2 I4 24 FP GROWTH算法原理 实例2 加入第三个事务 I2 I3 25 FP GROWTH算法原理 实例2 加入第四个事务 I2 I1 I4 26 FP GROWTH算法原理 实例2 加入第五个事务 I1 I3 27 FP GROWTH算法原理 实例2 加入第六个事务 I2 I3 28 FP GROWTH算法原理 实例2 加入第七个事务 I1 I3 29 FP GROWTH算法原理 实例2 加入第八个事务 I2 I1 I3 I5 30 FP GROWTH算法原理 实例2 加入第九个事务 I2 I1 I3 31 FP GROWTH算法原理 实例2 挖掘频繁项集 首先考虑I5 得到条件模式基 构造条件FP Tree 32 得到I5频繁项集 I2 I5 I1 I5 I2 I1 I5 FP GROWTH算法原理 实例2 挖掘频繁项集 接着考虑I4 得到条件模式基 构造条件FP Tree 33 得到I4频繁项集 I2 I4 FP GROWTH算法原理 实例2 挖掘频繁项集 然后考虑I3 得到条件模式基 构造条件FP Tree 34 由于此树不是单分支路径 因此需要递归挖掘I3 FP GROWTH算法原理 实例2 挖掘频繁项集 递归考虑I3 此时得到I1条件模式基 即I1 I3的条件模式基为构造条件FP Tree 35 得到I3的频繁项目集 I2 I3 I1 I3 I2 I1 I3 FP GROWTH算法原理 实例2 挖掘频繁项集 最后考虑I1 得到条件模式基 构造条件FP Tree 36 得到I1的频繁项目集 I2 I1 FP GROWTH算法实现 数据处理 37 格式化处理 代码实现 FP树数据结构 38 代码实现 构造FP树步骤 39 代码实现 构造FP树 40 代码实现 构造FP树 41 代码实现 构造FP树 updateTree函数 42 代码实现 构造FP树 updateHeader函数 43 代码实现 构造FP树 验证 44 代码实现 挖掘频繁项集步骤 从构建好的FP树中抽取频繁项集的步骤如下 1 从FP树中获取条件模式基 2 利用条件模式基 构建一个条件FP树 3 迭代重复 1 2 直到树包含一个元素项为止 45 条件模式基定义 条件模式基是以所查找元素项为结尾的路径集合 每一条路径其实都是一条前缀路径 简而言之 一条前缀路径就是介于所查找元素项与树根节点之间的所有内容 每一个频繁项的所有前缀路径 条件模式基 46 代码实现 抽取条件模式基 47 eg t的第1条前缀路径prefixPath t s y x z 代码实现 抽取条件模式基 48 代码实现 抽取条件模式基 验证 49 代码实现 创建条件FP树 50 代码实现 创建条件FP树 51 代码实现 运行 52 示例 从新闻网站点击流中挖掘新闻