Python实现FP-growth算法寻找关联规则（含原理+代码）

（原创作者：陈玓玏）

一、FP-growth应用场景


FP-growth和Apriori一样，可以用于挖掘频繁项，常用于购物篮的规则提取，也就是挖掘客户购买商品时的关联程度，比如共有一万个客户购买商品，其中会同时购买牛奶和面包的客户有九千个，那就认为牛奶和面包关联性很大，适合打包销售。

二 、FP-growth原理


FP-growth是Apriori的改进版，只不过Apriori是每查找一个量级的频繁项集，都需要遍历整个dataset，而FP-growth直接将各频繁一项集统计出来，并且把它们之间的关系以树结构进行存储，从而只通过遍历两次dataset就找出所有的频繁项。两次遍历第一次是建立头指针，第二次是建立FP树，从这之后，数据量就大大缩小，只需要不停重复建树过程来查找频繁项了。

算法步骤如下：

1. 处理数据集：因为数据集传进来之后没有任何统计信息，所以先对数据集做一个合并，统计相同数据集的个数；
2. 建立头指针：遍历数据集，找出所有的频繁一项集，构成头指针，并根据支持度对一项集排序；
3. 建立FP树：
定义根节点，遍历数据集，对于每条记录，根据头指针的顺序向树中添加节点。如果记录中上一个节点的子节点中，当前节点已存在，则节点支持度+记录支持度，如果节点不存在，则在上一节点中添加当前子节点，并设置支持度为记录支持度。
4. 查找条件模式基：根据头指针查找每个一项集的前缀路径，作为条件模式基，且当前一项集作为频繁项基。
5. 查找频繁项：
深度遍历，重复步骤2、3、4。每次查找完成后，将每一层遍历的频繁项基+新的头指针中的频繁一项集作为频繁项，重复此步骤直到FP树的头指针为空。（查找频繁项的嵌套过程还是有些些麻烦的，而且会涉及Python中深复制浅复制的问题，直接看代码可能更明白。）

三、FP-growth代码

奉上我亲手一点点码出的代码！！！原理其实在代码注释里都写了的，没有画出FP树的结构，感兴趣的可以自己在FPtreeNode class里面写上输出结构的方法。
# -*- coding: utf-8 -*- """ Created on Tue Jun 26 17:27:42 2018 @author:
chendile """ import pandas as pd import numpy as np from pandas import Series,
DataFrameimport matplotlib.pyplot as plt from sklearn import datasets # 机器学习库
from sklearn.preprocessing import LabelEncoder from sklearn import tree from
sklearn.cross_validationimport train_test_split import gc import time from
sklearn.metricsimport roc_auc_score
#===============================定义FP树类========================== '''
#FP树需要的信息：子节点位置、父节点位置、计数、节点的一项集名称 ''' class FPtreeNode: def __init__(self,
nameValue, numOccur, parentNode): self.nameValue = nameValue self.numOccur =
numOccur self.parentNode = parentNode self.sonNode = []
#因为创建节点时，很可能还没有子节点，所以要先把子节点设置成空 #==========读取数据 def read_data
(table_str,col_name): data = pd.read_csv(table_str,encoding='gbk') data.fillna(-
1) data = data[col_name] data = data.iloc[0:100,:] for i in col_name: data[i] =
data[i].apply(lambda x:str(i)+str(x)) return data #==========找出频繁1项集，建立头指针表 '''
过程：1. 计算每个集合出现的频率 2. 计算每个1项集出现的频率 ''' #用于读取DataFrame型的数据 def initFreq(data):
initFreq = {}for i in range(data.shape[0]): if frozenset(data.iloc[i,:]) in
list(initFreq.keys()):# 这样每次都要将字典key组装成列表，字典可以直接 if key_obj in dict
initFreq[frozenset(data.iloc[i,:])] = initFreq[frozenset(data.iloc[i,:])]+1 else
: initFreq[frozenset(data.iloc[i,:])] =1
#为什么这里用list不行，用frozenset就可以？因为key值必须是不可修改类型。 return initFreq def initFreq_list
(data): initFreq = {} for i in data: if frozenset(i) in initFreq.keys(): #
这样每次都要将字典key组装成列表，字典可以直接 if key_obj in dict initFreq[frozenset(i)] =
initFreq[frozenset(i)]+1 else: initFreq[frozenset(i)] = 1
#为什么这里用list不行，用frozenset就可以？因为key值必须是不可修改类型。 return initFreq def buildHeader
(initFreq,minSup): headerTable = {}
#print('!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!',initFreq) for i in initFreq:
#print('i',i) for j in i: if j in list(headerTable.keys()): # 直接in dict就可以。
headerTable[j] = [headerTable[j][0]+initFreq[i],None] else: headerTable[j] =
[initFreq[i],None] #取满足最小支持度的频繁一项集 #这个部分比较棘手，如果直接用列表推导式，总是只能生成多个列表或字典组合成的列表
keys = list(headerTable.keys())#如果不加这句话，就会出现迭代过程中字典大小改变的错误 for i in keys: if
headerTable[i][0] < minSup: del(headerTable[i]) headerTable =
dict(sorted(headerTable.items(),key=(lambda x:x[1]),reverse=True)) return
headerTable#=============================更新头指针，这样找条件模式基的时候才方便================
def updateHeader(headerTable,FPtreeNode):
headerTable[FPtreeNode.nameValue].append(FPtreeNode)def UpdateTree
(treeNodeListTotal,headerTable,parentNode,currentNodeName,initNodeNum):
sonNodeList = {}#先把key对应的节点的子节点取出来 for i in parentNode.sonNode:
sonNodeList[i.nameValue] = i#判断是否已经存在了相邻的子节点，如果有，则直接把numOccur+1 if
currentNodeNamein sonNodeList.keys(): sonNodeList[currentNodeName].numOccur =
sonNodeList[currentNodeName].numOccur+1 tempNode = sonNodeList[currentNodeName]
#如果没有，则新增一个节点 else: tempNode =
FPtreeNode(currentNodeName,initNodeNum,parentNode)
#这里必须注意initNodeNum不能直接设为1，不然当出现多个重复节点需要创建时，计数就会不对
parentNode.sonNode.append(tempNode) treeNodeListTotal.append(tempNode)
updateHeader(headerTable,tempNode)return tempNode def buildFptree
(headerTable,data): #rootSon = [] ''' #建FP树的过程： 1.
逐行读取输入的数据，在头指针表中把这些项集对应的支持度找出来 2. 根据支持度进行排序，依次建立节点 ''' treeNodeListTotal = []
#记录整个FP树的结构 rootNode = FPtreeNode('Null', 1, []) #定义FP树的根节点 #print(headerTable)
for item in data: treeNodeList = {} #用来记录本item中每个节点的指针 treeTable = {}
#因为对于每个item，都应该是一个新的table，所以不在for循环外面定义 for i in headerTable.keys(): if i in
item: treeTable[i] = headerTable[i][0] #print(treeTable)
#对于treeTable中的每个节点，逐步建立树，先判断是否为首个节点，再判断是否需要新建节点，还是+1。
#如果是首个节点，则判断根节点的子节点中是否有它，如果不是，则判断上一个节点的子节点中是否有它 for i in
range(len(treeTable.keys())): keyList = list(treeTable.keys())if i==0:
treeNodeList[keyList[i]] =
UpdateTree(treeNodeListTotal,headerTable,rootNode,keyList[i],data[item])else:
treeNodeList[keyList[i]] =
UpdateTree(treeNodeListTotal,headerTable,treeNodeList[keyList[i-1
]],keyList[i],data[item])#检查建树过程： #print(treeNodeList) # for i in
treeNodeList.keys(): #
print('打印建树过程',data,item,treeNodeList[i].nameValue,treeNodeList[i].numOccur,treeNodeList[i].parentNode)
# for i in treeNodeListTotal: #
print('FP树节点打印',i.nameValue,i.numOccur,i.parentNode) return treeNodeListTotal
#寻找前缀路径 def findParent(node,path): if node.parentNode!=None and
node.parentNode.nameValue!='Null': path.append(node.parentNode.nameValue)
findParent(node.parentNode,path)elif node.parentNode.nameValue=='Null' and
len(path)==0: path.append([]) #print(node.nameValue,path) return path
#==========找出条件模式基，创建条件FP树================================= def findModeBase
(headerTable): prePath = {} #新建一个字典记录所有一项集的前缀路径 for i in headerTable.keys():
prePathNode = {}#记录单个一项集的前缀路径 for item in headerTable[i][2:]: path = [] path =
findParent(item,path)if [] not in path and len(path)>0:
prePathNode[frozenset(path)] = item.numOccurelse: prePathNode[frozenset([])] =
item.numOccur#print(prePathNode,i,'------------------------------开始建条件FP树')
tempHeader = buildHeader(prePathNode,1) #print('条件FP头',tempHeader)
treeNodeListTotal = buildFptree(tempHeader,prePathNode) prePath[i] = prePathNode
#print('前缀路径',prePath) return tempHeader,prePath,treeNodeListTotal def
findBaseFreq(baseFreq,tempHeader,minSup,freqList): print('tempHeader'
,tempHeader,baseFreq) tempHeader_1,prePath,treeNodeListTotal =
findModeBase(tempHeader) print('tempHeader_1',tempHeader_1) if
len(tempHeader_1.keys()) >0: print('aaaaaaa') for i in tempHeader_1: tempFreq =
baseFreq.copy()if tempHeader_1[i][0] >= minSup: if i not in tempFreq:
tempFreq.append(i) tempFreq_1 = tempFreq.copy()if not tempFreq in freqList:
freqList.append(tempFreq_1) print(tempFreq) print('freqList', freqList)
tempHeader_2 = {i: tempHeader_1[i]} print('tempHeader_2',tempHeader_2)
findBaseFreq(tempFreq.copy(),tempHeader_2,minSup,freqList) print(
'!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!',baseFreq) def findFreq
(headerTable,minSup,freqList): tempHeader = {} for i in headerTable.keys(): if i
not in freqList and headerTable[i][0]>=minSup: freqList.append(i) print(
'========================================',freqList) print(headerTable,
'\n\n\n\n') for i in headerTable: tempHeader[i] = headerTable[i] # 列表引用复制
baseFreq = [i] print('\n\n\n\n\n\n\n\n\n开始递归查找这个一项集的所有条件模式基',i,tempHeader[i])
findBaseFreq(baseFreq,tempHeader,minSup,freqList) tempHeader = {} print('频繁项列表'
,freqList)return freqList if __name__=='__main__': minSup = 3 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']] initFreq = initFreq_list(data) headerTable =
buildHeader(initFreq,minSup) print('---------------------',headerTable)
buildFptree(headerTable,initFreq) print(headerTable)#findModeBase(headerTable)
freqList = []#print('Fp树头指针',headerTable) freqList =
findFreq(headerTable,minSup,freqList) print(freqList)

• « 上一篇：我的自学编程之路
• » 下一篇：BT 磁力搜索引擎torrent search engine推荐