在数据挖掘中，关联分析旨在发现数据项之间的有趣关系。请说明 FP-Growth 算法的基本原理，并解释它是如何在不生成候选集的情况下发现频繁项集的。
考察说明
考察对关联分析概念及 FP-Growth 算法核心机制的理解程度。
回答思路
- 【回答框架 1】关联分析用于发现数据集中项之间的频繁共现模式，核心指标包括支持度、置信度和提升度。支持度表示项集出现的概率，置信度表示在包含 X 的事务中也包含 Y 的条件概率，提升度则衡量 X 对 Y 的促进程度。
- 【回答框架 2】FP-Growth 算法分两步：首先扫描数据库，统计每个项的支持度，过滤非频繁项，并按支持度降序排列；然后第二次扫描数据库，构建 FP-tree。FP-tree 是一种压缩的前缀树结构，每个节点代表一个项，包含计数，并保留项之间的关联。
- 【回答框架 3】从 FP-tree 中挖掘频繁项集时，采用递归方式：对每个频繁项，找到其条件模式基（即以该项为后缀的前缀路径集合），构建条件 FP-tree，再递归地在条件树上挖掘，直到树为空或仅含单路径。整个过程不产生候选集，避免了 Apriori 算法的候选生成与多次扫描开销。
- 【回答框架 4】FP-Growth 的关键优势是效率高，只需两次数据库扫描，且基于分治策略，将大问题分解为小问题，适合处理长频繁项集的挖掘。
- 【关键点 1】关联分析以支持度、置信度等指标衡量项间关联。
- 【关键点 2】FP-Growth 构建 FP-tree 压缩事务数据。
- 【关键点 3】通过条件模式基递归挖掘频繁项集，无需生成候选集。
- 【关键点 4】算法仅需扫描数据库两次，效率较高。
- 【易错点 1】支持度和置信度阈值设置不当可能导致大量无效规则或遗漏重要规则。
- 【易错点 2】FP-tree 在内存中存储，若数据集庞大可能占用较多内存。
- 【易错点 3】容易忽略提升度等指标，导致错误关联。