fpgrowth: 通过 FP-growth 算法发现频繁项集

实现 FP-Growth 函数以提取用于关联规则挖掘的频繁项集

from mlxtend.frequent_patterns import fpgrowth

概述

FP-Growth [1] 是一种用于提取频繁项集的算法，应用于关联规则学习，是已有的 Apriori 算法 [2] 的流行替代方法。

一般来说，该算法被设计用于处理包含事务的数据库，例如商店的顾客购买记录。如果一个项集满足用户指定的支持度阈值，则被认为是“频繁的”。例如，如果支持度阈值设置为 0.5 (50%)，则频繁项集定义为在数据库中至少 50% 的所有事务中同时出现的项的集合。

特别地，与 Apriori 频繁模式挖掘算法不同的是，FP-Growth 是一种不需要生成候选集的频繁模式挖掘算法。在内部，它使用一种称为 FP-tree（频繁模式树）的数据结构，而无需显式生成候选集，这使得它对于大型数据集特别有吸引力。

参考文献

[1] Han, Jiawei, Jian Pei, Yiwen Yin, and Runying Mao. "Mining frequent patterns without candidate generation. "一种频繁模式树方法。" Data mining and knowledge discovery 8, no. 1 (2004): 53-87.

[2] Agrawal, Rakesh, and Ramakrishnan Srikant. "快速挖掘关联规则的算法。" Proc. 20th int. conf. very large data bases, VLDB. Vol. 1215. 1994.

相关

• FP-Max
• Apriori

示例 1 -- 生成频繁项集

fpgrowth 函数期望数据采用独热编码的 pandas DataFrame 格式。假设我们有以下事务数据

dataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
           ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
           ['Milk', 'Apple', 'Kidney Beans', 'Eggs'],
           ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'],
           ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs']]

我们可以通过 TransactionEncoder 将其转换为正确的格式，如下所示

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder

te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)
df

现在，让我们返回支持度至少为 60% 的项和项集

from mlxtend.frequent_patterns import fpgrowth

fpgrowth(df, min_support=0.6)

默认情况下，fpgrowth 返回项的列索引，这在关联规则挖掘等下游操作中可能很有用。为了提高可读性，我们可以设置 use_colnames=True 将这些整数值转换为相应的项名称

fpgrowth(df, min_support=0.6, use_colnames=True)

示例 2 -- Apriori 与 FPGrowth 的比较

由于 FP-Growth 不需要显式创建候选集，因此它比替代的 Apriori 算法快得多。例如，以下单元格比较了 Apriori 算法与 FP-Growth 的性能——即使在这个非常简单的玩具数据集场景中，FP-Growth 也快了大约 5 倍。

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder

te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

from mlxtend.frequent_patterns import apriori

%timeit -n 100 -r 10 apriori(df, min_support=0.6)

850 µs ± 39.3 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)

%timeit -n 100 -r 10 apriori(df, min_support=0.6, low_memory=True)

941 µs ± 30.6 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)

from mlxtend.frequent_patterns import fpgrowth

%timeit -n 100 -r 10 fpgrowth(df, min_support=0.6)

320 µs ± 9.21 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)

更多示例

请注意，由于 fpgrowth 函数是 apriori 的直接替代品，它具有相同的函数参数和返回值。因此，更多示例请参阅 apriori 文档。

API

fpgrowth(df, min_support=0.5, use_colnames=False, max_len=None, verbose=0)

从独热编码的 DataFrame 中获取频繁项集

参数

• df : pandas DataFrame

  独热编码格式的 pandas DataFrame。也支持稀疏数据的 DataFrame；更多信息请参阅 https://pandas.ac.cn/pandas-docs/stable/user_guide/sparse.html#sparse-data-structures。

  请注意，mlxtend >= 0.17.2 不再支持旧的 pandas SparseDataFrame 格式。

  允许的值为 0/1 或 True/False。例如，

  Apple Bananas Beer Chicken Milk Rice 0 True False True True False True 1 True False True False False True 2 True False True False False False 3 True True False False False False 4 False False True True True True 5 False False True False True True 6 False False True False True False 7 True True False False False False

• min_support : 浮点数 (默认值: 0.5)

  一个介于 0 到 1 之间的浮点数，表示返回项集的最小支持度。支持度计算公式为：项集出现的事务数 / 总事务数。

• use_colnames : 布尔值 (默认值: False)

  如果为 True，则在返回的 DataFrame 中使用 DataFrame 的列名而不是列索引。

• max_len : 整数 (默认值: None)

  生成的项集的最大长度。如果为 None（默认值），则评估所有可能的项集长度。

• verbose : 整数 (默认值: 0)

  显示条件树生成的阶段。

返回值

pandas DataFrame，包含所有大于等于 min_support 且小于 max_len（如果 max_len 不为 None）的项集。DataFrame 的列为 ['support', 'itemsets']。'itemsets' 列中的每个项集都是 frozenset 类型，这是一种 Python 内置类型，行为类似于 set，但它是不可变的（更多信息请参阅 https://docs.pythonlang.cn/3.6/library/stdtypes.html#frozenset）。

示例

有关使用示例，请参阅 https://mlxtend.cn/mlxtend/user_guide/frequent_patterns/fpgrowth/