第11章 FP-growth算法-【千锋教育】Python快乐编程——机器学习从入门到实战同步教案

课程名称 第11章 FP-growth算法 计划学时 4学时 内容分析 本章主要介绍FP-growth算法简介、构建FP树、通过FP-growth算法提取频繁项集、实战：从超市购物清单中发掘信息 教学目标 与教学要求 要求学生了解FP-growth算法的基本概念、掌握通过FP-growth算法发现事务数据中的公共模式的方法、掌握构建FP树的方法、掌握通过Python实现FP-growth算法的方法 教学重点 构建FP树、通过FP-growth算法提取频繁项集、实战：从超市购物清单中发掘信息 教学难点 构建FP树、通过FP-growth算法提取频繁项集、实战：从超市购物清单中发掘信息 教学方式 课堂讲解及ppt演示 教 学 过 程 第一课时 （FP-growth算法简介、构建FP树） 了解Python机器学习知识 1.介绍本书，引出本课时的主题 读者应该对搜索引擎并不陌生, 在搜索栏中输入一个短语时, 搜索引擎往往会自动罗列一些与之相关的推荐查询项。 搜索引擎所给出的这些推荐查询项便用到了发现频繁项集的方法。 第10章所介绍的 Apriori 算法通过不断地构造候选项集、 筛选候选项集挖掘出频繁项集, 该过程需要多次扫描原始数据, 在处理大量数据时, 效率比较低下, 这显然难以满足搜索引擎的需求, 本章将要介绍的 FP-growth 算法可以帮助提升发现频繁项集的效率。 FP是 Frequent Pattern 的缩写, 表示频繁模式。 FP-growth 算法基于 Apriori 算法构建而成, 但在完成相同任务时采用了不同的处理方法, 该算法将数据集存储在FP树的结构中。 FP-growth 算法的执行效率往往比 Apriori 算法高两个数量级。 2.明确学习目标 （1） 能够掌握FP-growth算法简介 （2） 能够掌握创建FP树的数据结构 （3） 能够掌握通过Python构建FP树 知识讲解 · FP-growth算法简介 既然 Apriori 算法每次构造出一种组合都要遍历一遍数据集, 那么是否可以考虑将数据集压缩从而提高算法的效率呢? 假设现有一个超市购物单数据集, 这些数据很可能存在大量公共商品组合, 如果将这些公共商品作为前缀, 便有可能对数据集进行压缩。 通过压缩数据集可以有效减少统计某种组合出现次数时扫描整个数据集所花费的时间。 FP-growth算法便是通过这样的方法来提升发现频繁项集的效率的, 通常情况下,FP-growth 算法只需要对数据集进行两次扫描。 FP-growth 算法通过构造一颗 FP 树, 将相同商品保存在上层结点, 并且每个结点记录了当前结点重复利用的次数, 从而实现频繁项集的挖掘。 接下来通过一个简单的例子来演示 FP-growth 算法是如何构建 FP 树的。 假设, 有以下三条超市购物清单数据。 { 牛奶 尿布 面包 啤酒} { 啤酒 尿布 鸡蛋 面包 } { 牛奶 西瓜 面包 白酒 剃须刀} 首先, 对上述各类商品进行编号, 具体如下所示。 通过编号的形式来表示之前提到的那三条购物清单, 具体如下所示。 · 创建FP树的数据结构 可以通过逐个读入元素, 并把元素映射到 FP 树中的各路径来构造 FP 树。 由于不同的元素可能会有若干个相同的项, 因此它们的路径可能部分重叠。 路径相互重叠越多, 使用FP 树结构获得的压缩效果越好; 如果FP 树足够小, 能够存放在内存中, 就可以直接从这个内存中的结构提取频繁项集, 而不必重复地扫描存放在硬盘上的数据。 一般情况下, 由于经过了压缩处理, 通过 FP 树结构压缩后的数据集要比原始数据集小。 如果所有的数据都具有相同的项集, 那么这棵 FP 树将只包含一条结点路径; 如果每个数据都具有唯一项集, 那么 FP 树的大小将与原数据的大小相同。 关于构建 FP 树的文字表述可能比较空洞, 接下来, 根据表中的数据集构建一棵最小支持度为3 的 FP 树, 具体如图所示。 图中的ϕ 表示 FP 树的根结点, 其余结点包括一个数据项和该数据项在本路径上的支持度; 每条路径都是一条训练数据中满足最小支持度的数据项集; FP 树还将所有相同项连接成链表, 即图中被无箭头的线连接的各项。 为了能够高效地访问 FP 树中的相同项,需要构建一个连接具有相同项结点的头指针列表(headTable), 头指针列表中包含三类元素: 数据项、 该项所对应的全局最小支持度和指向 FP 树中该项链表的表头的指针。 加入了头指针列表的 FP 树如图所示。 · 通过Python构建FP树 11.2.1 节介绍了构建 FP 树的原理, 本节将介绍通过 Python 构建 FP 树的方法, 一般流程如下所示。