十九、FPGrowth算法介绍

1. Apriori和FPGrowht算法的特点

FP-Growth算法概述

• FpGrowth算法通过构造一个树结构来压缩数据记录，使得挖掘频繁项集只需要扫描两次数据记录，而且该算法不需要生成候选集合，所以效率会比较高。

FP-Growth算法的特点

• 相比Apriori算法需要多次扫描数据库，FPGrowth只需要对数据库扫描2次。
• 第1次扫描事务数据库获得频繁1项集。
• 第2次扫描建立一颗FP-Tree树。

FP-Growth算法的原理

• 发现频繁项集
  

• 统计频次和降序排序
  

• 重新排序
  Step2:对每一条数据记录，按照F1重新排序。
  

• 建立FP树
  Step3：把第二步重新排序后的记录，插入到fp-tree中
  Step3.1：插入第一条（第一步有一个虚的根节点
  
  Step3.2：插入第二条。根结点不管，然后插入薯片，
  在step3.1的基础上+1，则记为2；同理鸡蛋记为2；啤酒在step3.1的树上是没有的，那么就开一个分支.
  
  Step3.3：插入第三条，
  
  同理，剩余记录依次插入FP-tree
  
  图中左边的一列叫做头指针表，树中相同名称的节点要链接起来，链表的第一个元素就是头指针表里的元素。
  虚线连接起来的表示同一个商品，各个连接的数字加起来就是该商品出现的总次数。
  
  Step4：从FP-Tree中找出频繁项集
  
  对于每一条路径上的节点，其count都设置为牛奶的count（路径中最末尾的商品数）。
  
  因为每一项末尾都是牛奶，可以把牛奶去掉，得到条件模式基，此时的后缀模式是：牛奶。
  
  `

2 代码

# *-* coding:utf-8 *-*

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import fpgrowth
from mlxtend.frequent_patterns import association_rules

data_test = [['A', 'C', 'D'], ['B', 'C', 'E'], ['A', 'B', 'C', 'E'], ['B', 'E']]

def create_data():
    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']]
    return dataset

def main():
    dataset = create_data()
    te = TransactionEncoder()
    te_ary = te.fit(dataset).transform(dataset)
    df = pd.DataFrame(te_ary, columns=te.columns_)
    frequent_itemsets = fpgrowth(df, min_support=0.7, use_colnames=True)

    print(frequent_itemsets)  # 频繁项集

    rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)  # 关联规则
    print(rules)

if __name__ == '__main__':
    main()