《(6.3.1)--6.3FP-growth算法.pdf》由会员分享，可在线阅读，更多相关《(6.3.1)--6.3FP-growth算法.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 6.3FP-growth算法286.3 FP-growth算法Apriori算法的优缺点 优点 算法原理简单，易于理解。缺点：需要多次扫描数据集 如果频繁项集最多包含10个项，需要扫描事务数据集10次，这需要很大的I/O负载 产生大量频繁项集 如数据集有100项，可能产生的候选项个数为1.27*1030296.3 FP-growth算法频繁模式增长(frequent-pattern growth FP-Growth)将提供频繁项集的数据库压缩到FP-树，但仍保持项集关联信息;压缩后的数据库分成一组条件数据库，每个数据库关联一个频繁项，并分别挖掘每个条件数据库;f:4c:1b:1
2、p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p330FP-growth算法实现步骤第一次扫描事务数据集D，确定每个1项集的支持度计数，将频繁1项集按照支持度计数降序排序，得到排序后的频繁1项集集合L。第二次扫描事务数据集D，读出每个事务并构建根结点为null的FP-tree。i.创建FP-tree的根结点，用null标记；ii.将事务数据集D中的每个事务中的集，删除非频繁项，将频繁项按照L中的顺序重新排列事务中项的顺序，并对每个事务创建一个分支；iii.当为一个事务考虑增加分支时，沿共同前缀上的每个结点的计
3、数加1，为跟随前缀后的项创建结点并连接；iv.创建一个项头表，以方便遍历，每个项通过一个结点链指向它在树中的出现。6.3 FP-growth算法31FP-growth算法实现步骤从1项集的频繁项集中支持度最低的项开始，从项头表的结点链头指针，沿循每个频繁项的链接来遍历FP-tree，找出该频繁项的所有前缀路径，构造该频繁项的条件模式基，并计算这些条件模式基中每一项的支持度；通过条件模式基构造条件FP-tree，删除其中支持度低于最小支持度阈值的部分，满足最小支持度阈值的部分则是频繁项集；递归地挖掘每个条件FP-tree，直到找到FP-tree为空或者FP-tree只有一条路径，该路径上的所有项
4、的组合都是频繁项集。6.3 FP-growth算法测试数据集32TIDItems1面包、可乐、麦片2牛奶、可乐3牛奶、面包、麦片4牛奶、可乐5面包、鸡蛋、麦片6牛奶、面包、可乐7牛奶、面包、鸡蛋、麦片8牛奶、面包、可乐9面包、可乐6.3 FP-growth算法例6.8 FP-growth算法该数据集具有9个事务，设最小支持度为2，频繁项集的极大长度为3。试使用FP-growth算法挖掘表6-2的事务数据中的频繁项集。336.3 FP-growth算法null面包面包：7 7牛奶牛奶：2 2牛奶牛奶：4 4可乐可乐：2 2麦片麦片：2 2可乐可乐：2 2鸡蛋鸡蛋：1 1麦片麦片：1 1鸡蛋鸡蛋：
5、1 1可乐可乐：2 2麦片麦片：1 1项集 支持度计数 结点链头指针面包7牛奶6可乐6麦片4鸡蛋2图6-11 FP-tree34对于项集鸡蛋，开始向上找出所有前缀路径，找出其中的频繁模式：面包，鸡蛋：2面包，麦片，鸡蛋：2面包，麦片，鸡蛋：2NULL项集支持度记数面包7牛奶6可乐6麦片4鸡蛋2面包面包：7牛奶牛奶：2牛奶牛奶：4可乐可乐：2麦片麦片：2 可乐可乐：2鸡蛋鸡蛋：1麦片麦片：1鸡蛋鸡蛋：1可乐可乐：2麦片麦片：16.3 FP-growth算法null面包：2 2麦片：2 2图6-12 鸡蛋的条件FP-tree35对于项集麦片，开始向上找出所有前缀路径，找出其中的频繁模式：面包，麦片
6、：4牛奶，麦片：2面包，牛奶，麦片：2NULL项集支持度记数面包7牛奶6可乐6麦片4鸡蛋2面包面包：7牛奶牛奶：2牛奶牛奶：4可乐可乐：2麦片麦片：2 可乐可乐：2鸡蛋鸡蛋：1麦片麦片：1鸡蛋鸡蛋：1可乐可乐：2麦片麦片：16.3 FP-growth算法36对于项集可乐，开始向上找出所有前缀路径，找出其中的频繁模式：面包，可乐：4牛奶，可乐：4面包，牛奶，可乐：2NULL项集支持度记数面包7牛奶6可乐6麦片4鸡蛋2面包面包：7牛奶牛奶：2牛奶牛奶：4可乐可乐：2麦片麦片：2 可乐可乐：2鸡蛋鸡蛋：1麦片麦片：1鸡蛋鸡蛋：1可乐可乐：2麦片麦片：16.3 FP-growth算法37对于项集牛奶，
7、开始向上找出所有前缀路径，找出其中的频繁模式：面包，牛奶：4NULL项集支持度记数面包7牛奶6可乐6麦片4鸡蛋2面包面包：7牛奶牛奶：2牛奶牛奶：4可乐可乐：2麦片麦片：2 可乐可乐：2鸡蛋鸡蛋：1麦片麦片：1鸡蛋鸡蛋：1可乐可乐：2麦片麦片：16.3 FP-growth算法386.3 FP-growth算法null面包：2 2麦片：2 2图6-12 鸡蛋的条件FP-tree表6-5 FP-tree 挖掘过程项集项集条件模式基条件模式基条件条件FP-tree频繁模式频繁模式鸡蛋鸡蛋面包，牛奶，麦片：1，面包，麦片：1面包，鸡蛋：2，麦片，鸡蛋：2，面包，麦片，鸡蛋：2麦片麦片面包，可乐：1，面包，牛奶：2，面包：1 面包，麦片：4，牛奶，麦片：2，面包，牛奶，麦片：2可乐可乐面包：2，面包，牛奶：2，牛奶：2，面包，可乐：4，牛奶，可乐：4，面包，牛奶，可乐：2牛奶牛奶面包：4面包，牛奶：439 性能研究表明 FP-树比Apriori算法快一个数量级 原因 减少没有候选集的产生，没有候选测试 使用简洁的数据结构 除去了重复的数据库扫描6.3 FP-growth算法