FP-tree算法介绍及python实现

FP-tree算法原理可参考刘建平老师的的FP-tree原理介绍，非常详细

总结起来，FP-tree算法实现需要完成三个步骤：

（1）两次扫描数据库，建立项头表

（2）建立FP-tree树形结构

（3）频繁项集的挖掘

FP-tree实例及python实现：

python代码实现

import fp_growth as fpg

# 数据集
dataset = [[11,12,15], [11,12], [12,14], [11,12,14], [11,13], [11,12,13,15], [11,12,13], [12,15], [12,13,14], [13,14]]
if __name__ == __main__:
 
    调用find_frequent_itemsets()生成频繁项
    minimum_support表示设置的最小支持度，即若支持度大于等于inimum_support，保存此频繁项，否则删除
    include_support表示返回结果是否包含支持度，若include_support=True，返回结果中包含itemset和support，否则只返回itemset
frequent_itemsets=fpg.find_frequent_itemsets(dataset,minimum_support=2,include_support=True)
    print(type(frequent_itemsets))   # print type 类型为<type generator>
    result = []
    for itemset, support in frequent_itemsets:    # 将generator结果存入list
        result.append((itemset, support))
    result = sorted(result, key=lambda i: i[0])   # 排序后输出
    for itemset, support in result:
    print(str(itemset) +   + str(support))       # 打印最后的结果

实验结果：

[11] 6

[11, 13] 3

[11, 15] 2

[12] 8

[12, 11] 5

[12, 11, 13] 2

[12, 11, 15] 2

[12, 13] 3

[12, 14] 3

[12, 15] 3

[13] 5

[13, 14] 2

[14] 4

[15] 3

算法总结：

FP-Growth算法比Apriori算法快一个数量级, 也比树-投影算法快

原因：

（1）没有候选集的产生，没有候选测试

（2）使用简洁的数据结构

（3）除去了重复的数据库扫描