一、写在前面

fp-growth算法是一个生成频繁项集的算法,其主要利用了FP树的数据结构,整个生成过程只需要遍历数据集2次。

本fp-growth代码是基于开源代码fp-growth的实现(github代码:
https://github.com/enaeseth/python-fp-growth
<https://github.com/enaeseth/python-fp-growth>
),但是Eric的代码只支持python2.x,由于python3的变动,代码无法提供支持。本文也是因为本人的使用时,python3不支持,所以更改了一些代码,在此说明代码改动点,希望可以方便需要使用的人。

二、代码改动

1、itertools.imap的改动

python2中提供了itertools.imap和map,两个函数都是根据提供的函数对指定序列做映射。下面看下在python2和python3中需要的变动:
(1)python2中
先来看在python2中itertools.imap的代码:
def imap(function, *iterables): # imap(pow, (2,3,10), (5,2,3)) --> 32 9 1000
iterables = map(iter, iterables)while True: args = [next(it) for it in
iterables]if function is None: yield tuple(args) else: yield function(*args)
其中,function为功能函数 *iterables为可迭代序列
imap()返回一个iterator,其对于iterables的每一个元素都调用function函数。
map()函数返回一个list。
(2)python3中
①在python3中,itertools.imap()不再提供使用,可以用map()来代替其功能。
②在python3中,map()的返回值不再是list,而是返回一个iterator。
(3)改动点
①将开头部分from itertools import imap去掉。
②将第55行imap(clean_transaction, transactions)改为map(clean_transaction,
transactions)

2、filter()函数
def clean_transaction(transaction): transaction = filter(lambda v: v in items,
transaction) transaction.sort(key=lambda v: items[v], reverse=True) return
transaction
上述代码是针对Python2的代码。在python2中filter返回一个list,所以可以直接调用sort,但是在python3中,
filter返回一个iterator
,因此需要使用list(iterator)转化为list转化,再调用sort()函数,因此,在python3中,将clean_transaction(transaction)代码修改如下:
def clean_transaction(transaction): transaction = filter(lambda v: v in items,
transaction) transaction_list = list(transaction)#
为了防止变量在其他部分调用,这里引入临时变量transaction_list transaction_list.sort(key=lambda v:
items[v], reverse=True) return transaction_list
三、测试运行

(1)测试代码如下:
# python3 # -*- coding: utf-8 -*- # @Author : lina # @Time : 2018/5/13 11:40
import fp_growth_py3 as fpg # 数据集 dataset = [ ['啤酒', '牛奶', '可乐'], ['尿不湿', '啤酒',
'牛奶', '橙汁'], ['啤酒', '尿不湿'], ['啤酒', '可乐', '尿不湿'], ['啤酒', '牛奶', '可乐'] ] if
__name__ =='__main__': ''' 调用find_frequent_itemsets()生成频繁项 @:param
minimum_support表示设置的最小支持度,即若支持度大于等于inimum_support,保存此频繁项,否则删除 @:param
include_support表示返回结果是否包含支持度,若include_support=True,返回结果中包含itemset和support,否则只返回itemset
''' frequent_itemsets = fpg.find_frequent_itemsets(dataset, minimum_support=1,
include_support=True) print(type(frequent_itemsets)) # print type 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))
(2)输出结果如下:
<class 'generator'> ['可乐'] 3 ['可乐', '尿不湿'] 1 ['啤酒'] 5 ['啤酒', '可乐'] 3 ['啤酒',
'可乐', '尿不湿'] 1 ['啤酒', '尿不湿'] 3 ['啤酒', '尿不湿', '橙汁'] 1 ['啤酒', '尿不湿', '牛奶'] 1 ['啤酒'
,'尿不湿', '牛奶', '橙汁'] 1 ['啤酒', '橙汁'] 1 ['啤酒', '牛奶'] 3 ['啤酒', '牛奶', '可乐'] 2 ['啤酒',
'牛奶', '橙汁'] 1 ['尿不湿'] 3 ['尿不湿', '橙汁'] 1 ['尿不湿', '牛奶'] 1 ['尿不湿', '牛奶', '橙汁'] 1 [
'橙汁'] 1 ['牛奶'] 3 ['牛奶', '可乐'] 2 ['牛奶', '橙汁'] 1
四、Github地址:

https://github.com/Nana0606/python3-fp-growth
<https://github.com/Nana0606/python3-fp-growth>

五、个性化需求之性能提升方案

在实际使用FP-Growth时,有时候根据我们自身的需求,不需要将所有的频繁项求出,
这时候如果对频繁项算法不做限制,只在频繁项结果中进行筛选,这会导致效率非常低,所以我们需要对频繁项算法进行修改。

(1)只提取项数长度为2的频繁项
def find_with_suffix(tree, suffix): if len(suffix) <= 1: #
修改内容!!!设置后缀长度<=1,即生成的频繁项长度<=2 # print("fp_growth_py3 -- suffix is: ", suffix)
for item, nodes in tree.items(): support = sum(n.count for n in nodes) if
support >= minimum_supportand item not in suffix: # New winner! found_set =
[item] + suffixyield (found_set, support) if include_support else found_set #
Build a conditional tree and recursively search for frequent # itemsets within
it. cond_tree = conditional_tree_from_paths(tree.prefix_paths(item)) for s in
find_with_suffix(cond_tree, found_set):yield s # pass along the good news to
our caller

因为在查找的时候是基于后缀进行,即先抽取项数为1的频繁项,再在频繁项长度为1的基础上抽取项数为2的频繁项,因此我们只需要在抽取后续长度上做出限制即可。[这里定义的频繁项长度]
只需要在find_with_suffix中加入if len(suffix) <= 1:
,这句代码表示当后缀长度小于等于1时,继续往下不断抽取频繁项,即可以抽取出频繁项长度小于等于2的频繁项。
若想要抽取出频繁项长度为n的频繁项,则在find_with_suffix中加入if len(suffix) <= (n-1):
即可。因为长度为n的频繁项是在长度为(n-1)的频繁项的基础上进行抽取的,所以这里只能限制长度if len(suffix) <= (n-1),而不能直接设置为
if len(suffix) = (n-1)。


感谢贺大大提供的帮助~~

参考文献:
https://blog.csdn.net/daizongxue/article/details/77504158
<https://blog.csdn.net/daizongxue/article/details/77504158>
https://yq.aliyun.com/ziliao/102478 <https://yq.aliyun.com/ziliao/102478>

http://www.wklken.me/posts/2013/08/20/python-extra-itertools.html#itertoolsimapfunction-iterables

<http://www.wklken.me/posts/2013/08/20/python-extra-itertools.html#itertoolsimapfunction-iterables>
https://blog.csdn.net/xiaocaiju/article/details/6968123
<https://blog.csdn.net/xiaocaiju/article/details/6968123>

https://www.baidu.com/link?url=GW7XEklr2RQnyKozS4WAi6E71jtbsXOAlUZH_1yp978fm1lVw-lTTw72b2uaGI5y2IL2xz5abX-b2Ock5hYhra&wd=&eqid=ab955ecb00012564000000035af7f3ff

<https://www.baidu.com/link?url=GW7XEklr2RQnyKozS4WAi6E71jtbsXOAlUZH_1yp978fm1lVw-lTTw72b2uaGI5y2IL2xz5abX-b2Ock5hYhra&wd=&eqid=ab955ecb00012564000000035af7f3ff>
https://www.cnblogs.com/kendrick/p/7478304.html
<https://www.cnblogs.com/kendrick/p/7478304.html>