FP-growth算法高效发现频繁项集

灰太狼 2022-06-01 06:20 199阅读 0赞

FP-growth与Apriori比较，

优点：性能要比Apriori好两个数量级以上，可以高效地发现频繁项集。

缺点：不能用于发现关联规则。

FP代表频繁模式（FrequentPattern），搜索引擎公司的研究人员使用了FP-growth算法，他们通过查看互联网上的用词来找出经常在一块出现的词对。

FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快

FP-growth发现频繁项集的基本过程分为两部分：

(1) 构建FP树

(2) 从FP树中挖掘频繁项集

构建FP树：

直接上数据集和FP树，再回头讲解理解下吧。

模拟数据集：

#模拟简单数据集
    def loadData() :
        simpData = [['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 simpData

最终的FP树：

![20180122200252230][]

树分为两部分，左边是头指针表，右边是FP的分路树。

头指针表维护了单元素的name和总共出现的个数，并通过链表的方式讲元素的出现的节点串接起来。

FP分路树有点像Apriori树，树又节点和出现次数来组成的，后面会给个推演的过程。

数据集中有p、h元素，但是在FP树中没有体现，是因为这里也引入了最小支持度的概念，图中的最小支持度是3，p、h分别出线了2次和1次，未达到最小支持度，所以被抛弃了。利用最小支持度删除数据的意义与Apriori是一样的，简化数据减少运算量。

代码容器：

class treeNode :
        def __init__(self, nameValue, numOccur, parentNode):
            self.name = nameValue
            self.nodeLink = None
            self.count = numOccur
            self.parent = parentNode
            self.children = {}
    
        def inc(self, numOccur) :
            self.count +=numOccur
    
        def disp(self, ind=1):
            print('   ' * ind, self.name, ' ', self.count)
            for child in self.children.values():
                child.disp(ind + 1)

头指针表维护：

#头指针的维护，找到该元素最后一链，尾巴上挂上targetNode这一环
    def updateHeader(nodeToTest, targetNode):
        while(nodeToTest.nodeLink != None):
            nodeToTest = nodeToTest.nodeLink
        nodeToTest.nodeLink = targetNode

FP 树维护：

#FP树的生长
    def updateTree(items, inTree, headerTable, count) :
        if items[0] in inTree.children :
            #如果已有这个子，只需要增加值
            inTree.children[items[0]].inc(count)
        else :
            #创建子分支
            inTree.children[items[0]] = treeNode(items[0],count,inTree)
            #维护头指针
            if headerTable[items[0]][1] == None:
                #保存的是tree类型，头指针，指向第一个出现的该元素的地方
                headerTable[items[0]][1] = inTree.children[items[0]]
            else :
                updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
        if len(items) > 1:
            #如果有多个元素，需要挂在后面的元素到当前元素上，把当前的元素作为下一个元素的parent
            #递归
            updateTree(items[1::], inTree.children[items[0]],headerTable,count)

构建树主函数：

def createTree(dataSet, minSup=1):
        #headerTable统计项集的出现次数，头指针
        headerTable = {}
        #第一次遍历数据集
        for trans in dataSet :
            for item in trans :
                headerTable[item] = headerTable.get(item,0) + dataSet[trans]
        #过滤频繁项集
        deletedKey = []
        for k in headerTable.keys():
            if headerTable[k] < minSup:
                deletedKey.append(k)
                #del(headerTable[k])
        for dk in deletedKey:
            del (headerTable[dk])
        freqItemSet = set(headerTable.keys())
        if len(freqItemSet)==0:
            return None,None
        for k in headerTable:
            #变形
            headerTable[k] = [headerTable[k], None]
        retTree = treeNode('Null Set', 1, None)
    
        #第二次遍历数据集
        for tranSet, count in dataSet.items():
            localD = {}
            for item in tranSet:
                #只关心频繁的
                if item in freqItemSet:
                    localD[item] = headerTable[item][0]
            if len(localD) > 0:
                #print('Insert into tree after filter: ',localD)
                #localD根据出现次数倒序排列
                orderedItems = [v[0] for v in sorted(localD.items(),key=lambda p:p[1],reverse=True)]
                #插入到retTree树中
                updateTree(orderedItems, retTree, headerTable, count)
        return retTree,headerTable

简单测试：

simpData = loadData()
    retDict = createInitSet(simpData)
    retTree,headerTable = createTree(retDict,3)
    print('Tree is :')
    retTree.disp()

演示图配合上面代码，来展示FP树的构建：

1：![20180122201150042][]

2：![20180122201205770][]

3：![20180122201218572][]

4：![20180122201234401][]

5：![20180122201248864][]

6：![20180122201301244][]

测试结果：

Tree is :
        Null Set   1
           z   5
              r   1
              x   3
                 s   2
                    t   2
                       y   2
                 t   1
                    y   1
                       r   1
           x   1
              s   1
                 r   1

结果与示意图中的树略有差别，是由于同等支持度的排序规则不同引起的，队实际效果没影响。

从FP树中挖掘频繁项集

首先从上一节发现的已经保存在头指针表中的单个频繁元素项开始。对于每一个元素项，获得其对应的条件模式基（conditional pattern base）。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径（prefix path）

例如图中获取t的条件模式基：

在头指针表中找到第一环t2，这里的t2通过上面推演应该理解了不是标号t2，而是t出现了2次，t2往上一直找到根，这一条线\[z,x,y,s\]就是t的一条前缀路径，支持度为2；t2的尾巴指向了t1，t1网上寻跟求出另一条前缀路径是\[r,y,x,z\]，支持度为1。所有的t的前缀支持路径合并\[z,x,y,s\]\*2+\[r,y,x,z\]\*1=\[‘z’:3,’x’:3,’y’:3,’s’:2,’r’:1\]，求和的结果就是条件模式基。

基于条件模式基创建的FP树被称为条件FP树，创建树的过程与前面一样，为了减小复杂度，仍然需要引入最小支持度，上面例子中t的条件FP树创建结果是：

![20180122201926649][]

PS：s和r难道不是频繁的么？他们在第一次求FP树的时候已经通过最小支持度的考验为什么这里又被干掉了么？因为s、r独立时虽然是频繁的，但是对于t来说并不是条件频繁的，所以要干掉。

求前缀路径和条件模式基的辅助代码是：

#一条前置路径，从叶子到根递归构建
    def ascendTree(leafNode, prefixPath) :
        if leafNode.parent != None :
            prefixPath.append(leafNode.name)
            ascendTree(leafNode.parent,prefixPath)
    
    #寻找treeNode的条件模式基
    def findPrefixPath(basePat, treeNode) :
        condPats = {}
        while treeNode !=None :
            prefixPath = []
            #向前寻找前置路径
            ascendTree(treeNode, prefixPath)
            if len(prefixPath) > 1:
                #我们是要找前置路径，所以剔除当前节点，本次前置路径出现次数为treeNode.count
                condPats[frozenset(prefixPath[1:])] = treeNode.count
            #treeNode跳转到nodeLink所指的下一个该元素节点的treeNode
            treeNode = treeNode.nodeLink
        return condPats

主迭代函数：

#inTree FP树 #headerTable 头指针表 #minSup 最小支持度 #preFix #freqItemList 频繁项集列表 def mineTree(inTree, headerTable, minSup, preFix, freqItemList): #对头指针元素按照支持度正序排序 bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p:p[1][0])] for basePat in bigL: newFreqSet = preFix.copy() newFreqSet.add(basePat) freqItemList.append(newFreqSet) #找到元素basePat的前置路径condPattBases，含有支持度 condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) #基于条件模式基来重新创建一次FP树，该树叫“条件FP树” myCondTree, myHead = createTree(condPattBases, minSup) if myHead!=None: mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) print('condition tree for: ',newFreqSet) myCondTree.disp

实际案例

100W数据，验证下效率，在海量数据中筛选出经常一起出现的元素。

测试数据上传到git（https://github.com/yejingtao/forblog/blob/master/MachineLearning/trainingSet/kosarak.dat）上

D = [line.split() for line in open('C:\\2017\\提高\\机器学习\\训练样本\\FP\\kosarak.dat').readlines()]
    retDict = createInitSet(D)
    retTree,headerTable = createTree(retDict,100000)
    freqItems = []
    mineTree(retTree,headerTable,100000,set([]),freqItems )
    print(freqItems)

大约十几秒内便可以得出结果：

[{'1'}, {'1', '6'}, {'3'}, {'3', '11'}, {'3', '11', '6'}, {'3', '6'}, {'11'}, {'6', '11'}, {'6'}]

[20180122200252230]: /images/20220601/d444651b56f94be0bc8e52edbc3733bb.png
[20180122201150042]: /images/20220601/068a55fe2c084ca18237ad2834ef3675.png
[20180122201205770]: /images/20220601/c95c555031554e809960264120ccba50.png
[20180122201218572]: /images/20220601/7427efd7459b4d90ac88499e9409c2a7.png
[20180122201234401]: /images/20220601/3861c9a192f642c1a5ee012131dfef38.png
[20180122201248864]: /images/20220601/dd64781017f74659bccb8d858545d0b8.png
[20180122201301244]: /images/20220601/bd1e322806554443bfcf6c9bf6b6be58.png
[20180122201926649]: /images/20220601/38b40599cebe4a2aa8c0ca5606d47fbe.png