Python中的FP Growth算法

在大数据时代，从海量数据集中发掘重要经验是组织、科学家和数据分析师的关键任务。一个主要挑战是在这些数据中寻找模式和关系，这可以为决策、营销策略提供可操作的信息，从而进一步拓展其应用范围。FP-Growth（频繁模式增长）算法由 Han 等人于 2000 年提出，是一个强大而有效的工具，旨在解决这一挑战。

FP-Growth（频繁模式增长）算法特别适用于挖掘频繁项集，即在数据集中经常一起出现的项目或属性集。这些项集是生成关联规则的结构块，关联规则描述了不同项目或属性之间的关系和条件。FP-Growth 已在从零售和网络业务到生物信息学和网络使用挖掘等广泛领域中得到应用。

FP-Growth 算法的原理

FP-Growth（频繁模式增长）算法建立在一组关键原理和信息结构之上，使其能够有效地发现大型数据集中的常规项集。要完全掌握算法的工作原理，理解这些原理至关重要。

1. 频繁项集

FP-Growth 算法的核心是频繁项集。这些是数据集中一起出现的项目（或属性）集，其频率超过预定义的阈值，称为最小支持度。最小支持度是客户定义的边界，它决定了项目应出现的最小次数才能被视为“频繁”。达到此支持度阈值的项集很有趣，因为它们代表了数据中的模式或关系。

2. FP 树（频繁模式树）

FP-Growth 使用的核心数据结构是 FP 树（频繁模式树）。这种树状结构高效地编码事务数据集，使得以最小和高度改进的方式执行频繁项集挖掘成为可能。

FP 树组件

• 节点：FP 树中的每个节点都表示数据集中的一个项目。
• 分支：节点之间的分支表示包含连接节点所表示的项目的交换事件。
• 头表：此表与 FP 树一起，包含有关项目、其频率以及指向它们在树中所在节点的指针的数据。头表对于挖掘过程中在树内进行有效导航非常重要。

3. FP 树构建

构建 FP 树的最常见方法包括几个基本阶段

i. 扫描数据集

首先，过滤数据集以计算每个项目的频率。此步骤识别哪些项目达到或超过最小支持度阈值。

ii. 排序项目

然后将识别出的频繁项目按其频率降序排列。以这种方式排列项目可确保最频繁的项目首先出现。

iii. 构建 FP 树

对于数据集中的每个交换，项目会根据其频率按顺序逐个添加到 FP 树中。如果树中已存在任何项目，则会从表示该项目的当前节点创建另一个分支。

通过这种方式构建 FP 树，算法有效地捕获了数据集中常规项集的设计，从而促进了后续挖掘。

4. 挖掘频繁项集

构建或构造 FP 树后，FP-Growth 算法继续有效地挖掘连续项集。挖掘系统包括以下基本阶段：

i. 挖掘条件 FP 树

从最不连续或最不频繁的项目开始，算法通过递归地从 FP 树中删除该项目及其相关节点来挖掘偶发 FP 树。此过程为每个项目创建频繁项集。

ii. 合并结果

将从偶发 FP 树中获取的连续项集合并以生成整个数据集的最终频繁项集。

通过这种方式，FP-Growth 算法发现了数据中频繁的示例和关系，使其成为各种应用程序的重要工具。

FP-Growth 算法中包含的步骤

FP-Growth 算法采用递归方法来挖掘频繁项集。存在三个步骤，如下所示：

数据预处理

收集事务数据：将信息收集为事务，其中每个事务包含一组项目。这些项目可以表示客户购买的项目、购物篮中的项目或任何类似上下文。

确定最小支持度

设置最小支持度边界，这是项目在事务中出现以被视为“频繁”的最小次数。此限制通常由客户根据数据集和明确要求定义。

检查数据集并计算项目频率

遍历数据集一次并计算事务中每个项目（项集）的频率。此步骤识别哪些项目达到或超过最小支持度边界。

按频率排序项目

按其出现频率的下降请求对频繁项目进行排序。以这种方式排列项目可确保最常规的项目首先出现，这对于算法的有效性至关重要。

构建 FP 树

创建空 FP 树。对于数据集中的每个事务，根据其出现频率确定的顺序，将项目逐个插入 FP 树中。

如果项目已存在于树中，则增加该项目枢轴的计数。如果不存在，则为该项目创建新的枢轴。

此过程导致 FP 树的增长，有效地捕获了数据集中项集的频率和设计。

创建头表

除了 FP 树，还要创建一个头表。此表包含项目列表及其在 FP 树中比较枢轴的指针。头表对于挖掘系统期间树内的有效导航至关重要。

挖掘条件 FP 树

从最不常规的项目开始，递归地挖掘限制性 FP 树。对于每个项目，将其及其相关枢轴从 FP 树中删除以创建限制性 FP 树。

将 FP-Growth 算法递归应用于限制性 FP 树，以找到该项目的连续项集。

为每个常规项目继续此过程，创建限制性 FP 树并挖掘频繁项集。

合并结果

将从限制性 FP 树中获取的连续项集合并，以生成整个数据集的最后排列的频繁项集。

生成关联规则（可选）

如果需要，从常规项集生成关联规则。关联规则通常由两部分组成：前置词（左侧）和后续词（右侧）。

计算每个标准的确定性，这是标准正确性的比例。关联规则有助于揭示项目之间的重要关系。

输出频繁项集和关联规则

最后，向客户呈现频繁项集和关联规则。这些结果提供了对数据集中示例和关系的深刻见解，这对于各种应用程序（如市场购物篮分析、推荐系统等）都非常重要。

示例

对于此示例，我们将利用一个改进的事务数据集，其中每个列表表示包含内容的事务。

步骤 1：导入所需库

我们需要导入 pdf 增长库才能使用 FP-Growth 计算

语法

步骤 2：设置最小支持度阈值

定义最小支持度阈值，该阈值决定项集在事务中显示以被视为“频繁”的最小次数。在此示例中，我们将最小支持度设置为 2。

步骤 3：查找频繁项集

使用 pyfpgrowth.find_frequent_patterns 在事务中查找频繁项集

我们已声明一个变量 pattern，它将返回一个字典（patterns），其中键是频繁项集，值是它们的支持计数。我们将传递 transactions 和 min_support 作为参数。

步骤 4：生成关联规则

使用 pyfpgrowth.generate_association_rules 从频繁项集生成关联规则

我们已声明一个变量 rules，并将传递参数 patterns 和 min_confidence。在此步骤中，我们可以更改 min_confidence 边界，为您的关联规则设置最小确定性阈值。

步骤 5：打印结果

最后，您可以打印连续项集和关联规则，以及它们的支持度和置信度值。

代码

上面的代码将显示在您的数据集中找到的频繁项集和关联规则，以及它们各自的支持度和置信度值。

示例

输出

Here are the Frequent Item sets:
('item2',): 4
('item2', 'item3'): 3
('item2', 'item4'): 2
('item1', 'item2'): 2
('item1', 'item2', 'item3'): 2
('item1', 'item2', 'item4'): 2
Here are the Association Rules:
('item1',) => ('item2', 'item3') (Confidence: 1.0)
('item1', 'item2') => ('item3',) (Confidence: 1.0)
('item1', 'item2') => ('item4',) (Confidence: 1.0)
('item1', 'item2', 'item3') => ('item4',) (Confidence: 1.0)
('item1', 'item2', 'item4') => ('item3',) (Confidence: 1.0)
('item2', 'item3') => ('item4',) (Confidence: 0.6666666666666666)
('item2', 'item4') => ('item3',) (Confidence: 1.0)
('item3',) => ('item2', 'item4') (Confidence: 0.6666666666666666)
('item4',) => ('item2', 'item3') (Confidence: 0.6666666666666666)

说明

FP-Growth 算法的结果揭示了对给定数据集的重大经验。首先，频繁项集显示了哪些项目组合经常一起出现。值得注意的是，“item2”出现在所有交换中，使其成为最常规的项目。项集（“item2”，“item3”）也值得注意，这表明“item3”经常与“item2”一起购买。此外，该算法将（“item2”，“item4”）识别为连续项集，表明“item2”和“item4”之间存在常见关系。

此外，关联规则阐明了这些项目之间的连接。例如，标准（“item1”，）=>（“item2”，“item3”）表示，每当购买“item1”时，“item2”和“item3”都会可靠地包含在交换中。1.0 的确定性表示强大的支持。此外，其他标准，如（“item1”，“item2”）=>（“item3”，）和（“item1”，“item2”）=>（“item4”，）揭示了这些项目之间的一致关系。

FP-Growth 算法的应用

FP-Growth 算法因其高效挖掘频繁项集和发现大型数据集内关系的能力，在各个领域都有应用。以下是该算法的一些有用应用：

• 市场篮子分析

零售商使用 FP-Growth 进行市场购物篮分析，以了解客户的购买行为。通过识别经常共同出现的商品，零售商可以优化商店布局、商品位置，并规划有效的交叉销售和追加销售策略。

• 推荐系统

电子商务和内容推荐平台中的推荐系统利用连续项集来创建个性化商品或内容推荐。FP-Growth 识别商品关联，使系统能够根据客户的偏好向其推荐相关商品或内容。

• 异常检测

在网络安全和欺诈检测中，FP-Growth 可用于识别可能表示可疑活动的异常模式或事件序列。通过识别不一致的项集或序列，可以标记异常以进行进一步调查。

• 生物信息学

在生物信息学中，FP 增长主要用于发现大型数据集中基因、蛋白质或自然过程之间的关系。此数据有助于理解遗传关联、疾病途径和药物发现。

• 网站使用挖掘

分析网站上的客户行为对于进一步改善客户体验和优化内容推荐至关重要。FP-Growth 识别客户导航中的模式，从而增强网页设计和个性化内容概念。

• 文本挖掘

在文本分析中，FP-Growth 可用于发现文档中共同出现的术语或短语。这对于主题建模、文档聚类以及在常规语言处理任务中识别每个现在经常相关的词语很重要。

FP-Growth 算法的优点

FP-Growth 算法具有多项优点，使其成为频繁模式挖掘和关联规则生成的重要工具。

• 效率

FP-Growth 效率高，特别是对于大型数据集，因为它只需对数据进行两次遍历：第一次用于计算项目频率，然后用于构建 FP 树。这种效率使其比许多其他频繁模式挖掘算法（如 Apriori 算法）更快。

• 紧凑数据表示

FP 树结构高效地编码数据集，与传统数据库扫描相比，减少了内存需求。这种保守的表示加速了模式挖掘。

• 减少候选生成

与 Apriori 不同，FP-Growth 不显式创建候选项集，从而降低了计算开销。它直接从 FP 树中挖掘频繁项集，消除了多次迭代的需要。

• 并行化

FP-Growth 可以有效地并行化，因为可以同时对信息的各种子集构建 FP 树，使其成为分布式和并行计算环境。

• 可扩展性

该算法的效率和内存使用量的减少使其能够适应处理巨大的数据集，这在当今的大数据时代至关重要。

• 挖掘稀有模式

FP-Growth 在挖掘连续示例以及稀有或不一致模式方面非常强大，可以提供更全面的信息关联视图。

• 高度可定制

客户可以根据其特定要求调整或自定义最小支持度阈值和最小确定性阈值，从而实现灵活的模式挖掘。

• 关联规则生成

FP-Growth 不仅找到频繁项集，还生成具有相关确定性值的关联规则，从而提供更深入的知识信息关系洞察。

• 应用范围广

该算法在零售、医疗保健、网络挖掘等不同领域都有应用，使其适用于各种用例。

• 对数据噪声的鲁棒性

FP-Growth 通常对信息中的噪声和异常具有鲁棒性，使其适用于可能包含不一致的真实数据集。

• 实时分析

FP-Growth 可用于实时分析，允许企业根据最新的数据（包括所有事务数据）做出及时决策。

FP-Growth 算法的缺点

虽然 FP-Growth 算法具有许多优点，但它也有特定的限制和缺点

• 内存使用

有时，构建 FP 树可能需要大量内存，尤其是在处理非常大的数据集时。这可能导致内存相关问题，并限制其在 RAM 有限的机器上的适用性。

• 初始扫描

尽管 FP-Growth 与 Apriori 相比减少了数据遍历的次数，但它需要进行初始扫描来计算项目频率。对于非常大的数据集，此初始扫描可能很耗时。

• 稀疏数据集

FP-Growth 在非常稀疏的数据集上可能无法有效执行，其中大多数项目的支持度较低。在这种情况下，FP 树可能无法提供优于其他算法的显着优势。

• 处理流数据困难

FP-Growth 通常用于静态数据集的批量处理。使其适应处理具有动态更新的流信息可能具有挑战性，并且可能需要额外的技术。

• 缺少参数调整指导

确定最小支持度和最小置信度阈值的合适值可能是一个挑战。错误地选择这些阈值可能会导致无趣或压倒性的结果。

• 复杂的实现

从头开始实现 FP-Growth 算法可能很复杂，特别是 FP 树和头表的增长和控制。这种复杂性可能成为不熟悉该算法的人的障碍。

• 限于分类数据

FP-Growth 主要用于绝对数据，其中项目是离散而不是连续的。处理连续或数值信息可能需要预处理或分箱。

• 限于单级项集

基本的 FP-Growth 算法侧重于挖掘任意大小的频繁项集，但它可能不直接支持挖掘具有不同级别或渐进系统的频繁项集。对于这种情况可能需要额外的适应。

• 规则的可解释性

虽然 FP-Growth 生成关联规则，但解释这些规则可能具有挑战性，尤其是在处理大量规则或复杂项集时。

• 不适用于所有数据类型

FP-Growth 对于事务数据最有效，其中项目在事务中共同出现。它可能不适用于其他类型的信息，例如序列或时间序列数据。