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

本是古典何须时尚 2022-05-21 05:48 356阅读 0赞

**（原创作者：陈玓玏）**

## 一、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, DataFrame  
    import matplotlib.pyplot as plt
    from sklearn import datasets # 机器学习库
    from sklearn.preprocessing import LabelEncoder
    from sklearn import tree
    from sklearn.cross_validation import train_test_split
    import gc
    import time
    from sklearn.metrics import 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 currentNodeName in 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.numOccur
                else:
                    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)