FP-growth算法发现频繁项集——发现频繁项集

什么是频繁项集？

在数据挖掘中，频繁项集（Frequent Itemset）指在一个数据集中经常出现在一起的项的集合，常用于关联规则挖掘。例如，在超市的交易记录中，若苹果和香蕉经常一起被购买，则{苹果，香蕉}是一个频繁项集。

什么是FP-growth算法？

FP-growth算法是一种用于挖掘数据中的频繁项集的算法。它不同于Apriori算法，它在挖掘频繁项集时不需要生成候选项集，因此可以对数据进行高效的处理。该算法通过创建一棵FP树（Frequent Pattern Tree）来存储数据，并使用树的分支来快速计算频繁项集。

FP-growth算法的步骤

以下是FP-growth算法的步骤：

1. 构建FP树

通过遍历数据集，统计每个项的出现次数，并将每个项存储到一个项头表中。然后，根据出现次数从大到小对项头表进行排序。接着，重新遍历数据集，将每个事务按照项头表的顺序进行排序，然后将它们插入到FP树的根节点开始。

1. 挖掘频繁项集

从项头表中选择一个项，然后利用它的链表（即链头）遍历FP树，找出所有包含这个项的频繁项集。探索后，继续选择项头表中的下一个项，直到找到所有频繁项集。

示例1

假设我们有以下交易记录：

	Apple	Banana	Orange
1	1	1	1
2	1	0	1
3	0	1	1
4	1	1	0

为了使用FP-growth算法，我们需要将其转换为一个事务数据库，其中每个事务表示一条交易记录。因此，我们得到以下数据集：

[
    ['Apple', 'Banana', 'Orange'],
    ['Apple', 'Orange'],
    ['Banana', 'Orange'],
    ['Apple', 'Banana']
]

接下来，我们可以使用FP-growth算法来挖掘数据中的频繁项集。首先，我们需要将数据集传递给FP树的构造函数，然后调用FP树的generate_tree方法进行树的构建。最后，我们可以使用FP树的方法来挖掘频繁项集。

from fp_growth import FPTree, find_frequent_itemsets

data = [
    ['Apple', 'Banana', 'Orange'],
    ['Apple', 'Orange'],
    ['Banana', 'Orange'],
    ['Apple', 'Banana']
]

# 构建FP树
fp_tree = FPTree(data)

# 挖掘频繁项集
min_support = 2
frequent_itemsets = find_frequent_itemsets(fp_tree, min_support)
print(frequent_itemsets)

输出：

{('Apple',): 3, ('Orange',): 3, ('Banana',): 2, ('Apple', 'Orange'): 2, ('Banana', 'Orange'): 2, ('Apple', 'Banana'): 3}

这表明，{Apple}和{Orange}是频繁项集，它们分别在3个事务中出现。{Banana}是一个频繁项集，它在2个事务中出现。另外，{Apple, Orange}，{Banana, Orange}和{Apple, Banana}也是频繁项集。

示例2

假设我们有以下交易记录：

	Bread	Butter	Coffee
1	1	1	0
2	1	0	0
3	1	0	1
4	0	1	0

同样，我们需要将其转换为一个事务数据库，得到以下数据集：

[
    ['Bread', 'Butter'],
    ['Bread'],
    ['Bread', 'Coffee'],
    ['Butter']
]

接下来，我们可以按照示例1中的方法使用FP-growth算法挖掘数据中的频繁项集。

from fp_growth import FPTree, find_frequent_itemsets

data = [
    ['Bread', 'Butter'],
    ['Bread'],
    ['Bread', 'Coffee'],
    ['Butter']
]

# 构建FP树
fp_tree = FPTree(data)

# 挖掘频繁项集
min_support = 2
frequent_itemsets = find_frequent_itemsets(fp_tree, min_support)
print(frequent_itemsets)

输出：

{('Bread',): 3, ('Butter',): 2, ('Bread', 'Butter'): 2}

这表明，{Bread}是频繁项集，它在3个事务中出现。{Butter}是一个频繁项集，它在2个事务中出现。另外，{Bread, Butter}也是频繁项集。