一、FP-growth介绍
从大规模的数据集中，寻找不同特征或者物品之间的隐含关系，称为关联分析（association analysis），或者关联规则学习（association rule learning）。
在 Apriori 算法中，寻找频繁项集，需要对每一个可能的频繁项扫描一遍数据集计算支持度，计算量庞大。
在 FP-growth 算法中，寻找频繁项集，只需要扫描两遍数据集，将数据存储在FP树的结构上，然后在FP树上挖掘频繁项集。
- 优点：速度一般要快于 Apriori。
- 缺点：实现比较困难，在某些数据集上性能会下降。
- 适用数据类型：标称型数据。
例如在下述例子中，下图是一颗FP树：
FP代表频繁模式（Frequent Pattern），一个元素项可以在一颗FP树上出现多次。
树节点上给出了当前节点的路径在数据集中的出现次数，例如｛z:5｝表示元素｛z｝在数据集中出现了5次；｛y:3｝表示路径｛y, x, z｝在数据集中出现了3次；｛s:2｝表示路径｛s, y, x, z｝在数据集中出现了2次。
左侧为头指针表，给出了每个元素在数据集中出现的次数，并由链表通过节点链接（node link）依次链接每个元素。部分元素因为不满足最小支持度的要求，所以不储存在FP树中。
在 FP-growth 算法中，同样采用了 Apriori 算法的思想，如果某个项是非频繁的，那么这个项的所有超集也是非频繁的。
二、构建FP树
构建FP树的过程只需要扫描两遍数据集。
第一遍扫描，计算每个单个元素的频率，并根据最小支持度，滤除不满足的元素。
第二遍扫描，首先对数据集进行处理，每一条数据按照元素的绝对出现频率排序，并滤除不满足最小支持度的元素。
例如根据上述的头指针表，元素排序为｛z:5, x:4, y:3, s:3, r:3, t:3｝，所以处理后的数据为：
处理后，遍历数据集，将每一条数据插入FP树中，从根节点开始递归添加路径，存在则将数值增加，不存在则创建新的节点。
例如下图所示，① 根节点不存在子节点｛z｝，所以创建新的子节点｛z｝，递归节点｛z｝，因不存在子节点｛r｝，所以创建新的子节点｛r｝，② 根节点存在子节点｛z｝，所以数值增加，递归节点｛z｝，因不存在子节点｛x｝，所以创建新的子节点｛x｝，递归节点｛x｝，......，如此递归。
三、从FP树中挖掘频繁项集
全文代码：
from numpy import *
from time import *
def load_simple_data():
"""
Function:
创建加载简单数据集
Parameters:
无
Returns:
simple_data - 简单数据集
Modify:
2018-12-27
"""
simple_data = [['r', 'z', 'h', 'j', 'p'],
['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
['z'],
['r', 'x', 'n', 'o', 's'],
['y', 'r', 'x', 'z', 'q', 't', 'p'],
['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
return simple_data
def create_init_set(data_set):
"""
Function:
计算项集在数据集的出现次数
Parameters:
data_set - 数据集
Returns:
ret_dict - 包含出现次数的项集字典
Modify:
2018-12-27
"""
ret_dict = {}
for trans in data_set:
ret_dict[frozenset(trans)] = 1
return ret_dict
def update_tree(items, in_tree, header_table, count):
"""
Function:
更新树节点，让FP树生长
Parameters:
items - 项集
in_tree - 当前FP树
header_table - 头指针表
count - 次数
Returns:
无
Modify:
2018-12-27
"""
# 判断排序后列表的第一个元素是否已经是根节点的子节点
if items[0] in in_tree.children:
# 添加出现次数
# children = {}
in_tree.children[items[0]].inc(count)
else:
# 创建根节点的子节点
in_tree.children[items[0]] = TreeNode(items[0], count, in_tree)
# 如果该元素的后继节点不存在，则直接加入。如果有后继节点，则遍历链表尾部将其加入
if header_table[items[0]][1] == None:
header_table[items[0]][1] = in_tree.children[items[0]]
else:
update_header(header_table[items[0]][1], in_tree.children[items[0]])
# 列表元素长度大于1，递归调用更新FP树函数
if len(items) > 1:
update_tree(items[1::], in_tree.children[items[0]], header_table, count)
def update_header(node_to_test, target_node):
"""
Function:
更新头指针表的节点链接
Parameters:
node_to_test - 遍历节点
target_node - 目标节点
Returns:
无
Modify:
2018-12-27
"""
# 遍历到链表尾节点
while (node_to_test.node_link != None):
node_to_test = node_to_test.node_link
# 将刚添加的树节点加入链表的尾部
node_to_test.node_link = target_node
def create_tree(data_set, min_sup=1):
"""
Function:
遍历数据集两次构建FP树
Parameters:
data_set - 包含项集出现次数的数据集字典
min_sup - 最小支持度
Returns:
ret_tree - FP树
hearder_table - 头指针表
Modify:
2018-12-27
"""
hearder_table = {}
# 第一次遍历数据集，获取单个元素的次数
for trans in data_set:
for item in trans:
hearder_table[item] = hearder_table.get(item, 0) + data_set[trans]
# 去除不满足最小支持度的单个元素
for k in list(hearder_table.keys()):
if hearder_table[k] < min_sup:
del (hearder_table[k])
freq_item_set = set(hearder_table.keys())
# 无频繁项就直接返回
if len(freq_item_set) == 0:
return None, None
# 扩展头指针表，添加指向每种类型第一个元素的指针（节点链接）
for k in hearder_table:
hearder_table[k] = [hearder_table[k], None]
# 创建根节点
ret_tree = TreeNode('Null Set', 1, None)
# 第二次遍历数据集，构建FP树
for tran_set, count in data_set.items():
# tran_set: frozenset({'h', 'p', 'z', 'j', 'r'})
# count: 1
local_d = {}
# 如果单个元素是频繁项，则加入localD列表
for item in tran_set:
if item in freq_item_set:
# hearder_table:{'b': [3, None]}
local_d[item] = hearder_table[item][0]
# localD: {'r': 3, 'j': 1, 'z': 5, 'h': 1, 'p': 2}
if len(local_d) > 0:
# 元素按出现次数排序
ordered_items = [v[0] for v in sorted(local_d.items(), key=lambda p: p[1], reverse=True)]
# 更新FP树，让FP树生长
update_tree(ordered_items, ret_tree, hearder_table, count)
return ret_tree, hearder_table
class TreeNode:
# name：节点元素名称，在构造时初始化为给定值
# count：出现次数，在构造时初始化为给定值
# node_link：指向下一个相似节点的指针，默认为None
# parent：指向父节点的指针，在构造时初始化为给定值
# children：指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值，初始化为空字典
def __init__(self, name_value, num_occur, parent_node):
self.name = name_value
self.count = num_occur
self.node_link = None
self.parent = parent_node
self.children = {}
def inc(self, num_occur):
# 增加节点出现次数
self.count += num_occur
def disp(self, ind=1):
# 用于将树以文本形式显示
print(' ' * ind, self.name, ' ', self.count)
for child in self.children.values():
child.disp(ind + 1)
def ascend_tree(leaf_node, prefix_path):
"""
Function:
根据当前节点向前追溯至根节点，记录前缀路径
Parameters:
leaf_node - 给定元素项节点
prefix_path - 前缀路径列表
Returns:
无
Modify:
2019-1-6
"""
# 如果节点有父节点，则将当前节点添加至前缀路径中，之后再递归向上追溯
if leaf_node.parent != None:
prefix_path.append(leaf_node.name)
ascend_tree(leaf_node.parent, prefix_path)
def find_prefix_path(base_pat, tree_node):
"""
Function:
发现以给定元素项结尾的所有前缀路径
Parameters:
base_pat - 元素项
tree_node - 需遍历节点
Returns:
cond_pats - 所有条件模式基字典
Modify:
2019-1-6
"""
# 所有条件模式基字典
cond_pats = {}
# 遍历该节点的整个链表节点，记录每个节点的前缀路径，并将其添加至条件模式基当中
while tree_node != None:
prefix_path = []
ascend_tree(tree_node, prefix_path)
# 因为该节点也被加进了路径当中，所以需要路径的长度大于1
if len(prefix_path) > 1:
# 如果有前缀路径，则将前缀路径加入条件模式基集合中，并且将该元素在该前缀路径中出现的次数也添加进去
cond_pats[frozenset(prefix_path[1:])] = tree_node.count
# 当前节点的条件模式基查找完毕后，继续查找头指针链表中下一个节点的条件模式基
tree_node = tree_node.node_link
return cond_pats
def mine_tree(in_tree, header_table, min_sup, pre_fix, freq_item_list):
"""
Function:
创建条件模式树
Parameters:
in_tree - FP树
header_table - 头指针表
min_sup - 最小支持度
pre_fix - 上一次递归的频繁项集合的前缀
freq_item_list - 频繁项集列表
Returns:
无
Modify:
2019-1-6
"""
# 对头指针表中的元素项按照其出现频率从小到大进行排序
big_l = [v[0] for v in sorted(header_table.items(), key=lambda p:p[1][0])]
# 遍历单元素频繁集
for base_pat in big_l:
new_freq_set = pre_fix.copy()
new_freq_set.add(base_pat)
freq_item_list.append(new_freq_set)
# 获得该元素的所有条件模式基，相当于一个事务集合
cond_patt_bases = find_prefix_path(base_pat, header_table[base_pat][1])
# 根据所有条件模式基集合来构建条件模式树
my_cond_tree, my_head = create_tree(cond_patt_bases, min_sup)
# 如果条件模式树的头指针表不空(每次建树时对元素支持度有要求
# 如果小于支持度则该元素不参与建树过程，所以在建树时，条件模式基中的元素会越来越少，最后会是空树)，则递归建树
if my_head != None:
print('conditional tree for:', new_freq_set)
my_cond_tree.disp(1)
mine_tree(my_cond_tree, my_head, min_sup, new_freq_set, freq_item_list)
if __name__ == '__main__':
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# print(simple_data)
# print(init_data)
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# my_fp_tree, my_header_tab = create_tree(init_data, 3)
# my_fp_tree.disp()
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# my_fp_tree, my_header_tab = create_tree(init_data, 3)
# cond_pats_1 = find_prefix_path('x', my_header_tab['x'][1])
# print(cond_pats_1)
# cond_pats_2 = find_prefix_path('z', my_header_tab['z'][1])
# print(cond_pats_2)
# cond_pats_3 = find_prefix_path('r', my_header_tab['r'][1])
# print(cond_pats_3)
# simple_data = load_simple_data()
# init_data = create_init_set(simple_data)
# my_fp_tree, my_header_tab = create_tree(init_data, 3)
# freq_items = []
# mine_tree(my_fp_tree, my_header_tab, 3, set([]), freq_items)
# print(freq_items)
start_time = time()
parse_dat = [line.split() for line in open('./machinelearninginaction/Ch12/kosarak.dat').readlines()]
init_set = create_init_set(parse_dat)
my_fp_tree, my_header_tab = create_tree(init_set, 100000)
my_freq_list = []
mine_tree(my_fp_tree, my_header_tab, 100000, set([]), my_freq_list)
end_time = time()
print('被10万或者更多人浏览过的新闻报道或报道集合数:', len(my_freq_list))
print('被10万或者更多人浏览过的新闻报道或报道集合:', my_freq_list)
print('总共执行时间:', end_time - start_time)
一个元素的条件模式基（conditional pattern base），是这个元素所有前缀路径（prefix path）的集合。
前缀路径（prefix path），是当前元素到根节点之间的路径（不包括当前元素和根节点）。
例如下图，｛r｝的条件模式基是｛｛z｝｛z, x, y｝｛x, s｝｝：
从FP树挖掘频繁项集的过程可描述为：
- 对于头指针表中的每一个元素，获取其条件模式基
- 根据条件模式基，构建条件FP树（即，将条件模式基当作新的数据集，按照建树的流程，重新构建一棵FP树）
- 继续对于条件FP树的头指针表中的每一个元素，获取其条件模式基
- 继续根据条件模式基，构建条件FP树
- 如此递归过程，直到无法构建出FP树为止
记录频繁项集的过程在创建一棵新的FP树时记录，伪代码如下表示：
关于此处的理解：
首先构建了一棵FP树，此时FP树中的单个元素均满足最小支持度（假设有｛a｝｛b｝｛c｝｛d｝｛e｝5个元素），遍历其中的每一个元素（假设此时遍历｛a｝），先将元素｛a｝加入总的频繁项集，再寻找元素｛a｝的条件模式基（假设有｛c, b｝｛b, d｝｛b, c, e, d｝），根据这些前缀路径递归构建一棵条件FP树（若这棵树能够构建的起来，说明树中的单个元素也是满足最小支持度的，假设条件FP树中有｛b｝｛c｝｛d｝3个元素，｛e｝不满足最小支持度），说明｛b｝｛c｝｛d｝这三个元素满足最小支持度，遍历其中的每一个元素（假设此时遍历｛b｝），复制上一层递归的频繁项集（即，｛a｝），将当前遍历元素｛b｝加入复制的频繁项集中（即，构成｛a, b｝），然后再将｛a, b｝加入总的频繁项集，再在条件FP树中寻找元素｛b｝的条件模式基，继续递归构建。因为上一层递归中的频繁项集｛a｝是一定满足最小支持度的，由这个元素｛a｝搜寻得到的条件模式基，一定是在数据集中跟｛a｝有组合的，若能据此构建一棵条件FP树，说明这棵树中的元素｛b｝｛c｝｛d｝也一定满足最小支持度，因这元素｛b｝与｛a｝在原始数据集中有组合，且这元素｛b｝与上一层递归频繁项集｛a｝均满足最小支持度，所以这元素｛b｝和｛a｝的组合｛a, b｝一定满足最小支持度，且存在在原始数据集中，所以加入总的频繁项集。
四、实例：从新闻网站点击流中挖掘
现有一个kosarak.dat文件，它包含将近100万条记录。该文件中的每一行包含某个用户浏览过的新闻报道。一些用户只看过一篇报道，而有些用户看过2498篇报道。因为用户和报道被编码成整数，所以查看频繁项集很难得到更多的东西，但是该数据对于展示FP-growth算法的速度十分有效。
从上图可以看出，构建树以及扫描100万行找出频繁项集只要不到8秒钟，这展示了FP-growth算法的强大威力。
五、小结
FP-growth算法是一种用于发现数据集中频繁模式的有效方法。FP-growth算法利用了Apriori原则，并且只对数据集扫描两次，所以执行更快。Apriori算法产生候选项集，然后扫描数据集来检查它们是否频繁。在FP-growth算法中，数据集存储在一个称为FP树的结构中。
FP树构建完成后，可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行，直到FP树只包含一个元素为止。
