【机器学习算法应用和学习_4_应用篇】关联分析/频繁项集挖掘_FP-growth算法

大纲

一、背景

二、算法目标

三、算法原理

1.术语

2.优缺点

2.算法原理(伪代码)

(本文不解释FP树和条件模式基等的构建过程，此类图解在很多博文中已经介绍得很清楚，可以参见参考资料)

1.输入数据预处理：loadSimpDat()函数创建输入数据或输入数据并createInitSet(dataSet)初始化成后续函数需要的形式；

2.创建存储FP树的数据结构：这里用类treeNode的方式创建可以迭代的节点的存储结构，便于后面函数调用该类并最终存储下整个FP树；

3.构建输入数据集的只包含频繁元素项的FP树的主函数：createTree(dataSet, minSup=1)就是对输入数据集创建FP树的函数；

4.寻找某个元素项的所有条件模式基：findPrefixPath(basePat, treeNode)；

5.创建发现频繁项集的主函数：mineTree(inTree, headerTable, minSup, preFix, freqItemList)，该函数会调用前面所有组件函数。

四、源代码

五、应用实践

一、背景

　　为什么会学习FP-growth算法？起因是在工作中有两个场景想知道哪些组合比较频繁，分析频繁出现的原因，并以此分类给用户贴上标签或根据频繁组合场景发现是否有必要增改场景。以往一般是直接SQL跑出不同组合的频次分布，但遗憾的是长尾非常多，眼看着某几个组合出现频次很大，但Excel处理就得穷举出所有组合再去汇总，特别麻烦。

　　于是在《机器学习实战》一书中找到了这个算法，称为是“频繁模式挖掘”的一种算法。经过一周断断续续的学习，由于算法实现过程由不同的人写出来有不同的组织逻辑，不同水平的人并不能一下子完整接受，所以期间也经过反复的推敲和调试，甚至专门搜该算法以期获取不同角度的讲解，最终终于算是有些理解。

　　理解完算法后发现，终于知道为啥后期卡在不理解所谓的输出结果上了，因为根本无法相信结果就是列出所有高于支持度的组合来而已。期间是有一篇文章的话点醒了我，

在实践中，关联规则挖掘可能并不像人们期望的那么有用。一方面是因为支持度置信度框架会产生过多的规则，并不是每一个规则都是有用的。另一方面大部分的关联规则并不像“啤酒与尿布”这种经典故事这么普遍。关联规则分析是需要技巧的，有时需要用更严格的统计学知识来控制规则的增殖。

博客园（华夏35度）

　　事实上，这个算法做的事情是将大于一定频次(给定支持度)的所有组合给你列出来。在元素项比较少的情况下，完全可以通过穷举所有元素项组合，算出其频率并丢弃尾部频次低的组合即可。

　　我也曾今给人做过利用SQL count(distinct if())的方式穷举所有组合算频次的事，虽然看起来也没啥用。不管怎么说，在元素项很多，低频次元素项的噪声影响比较麻烦的时候可以用这个算法，至于如何控制不必要的组合生成，目前还没有办法实践。

二、算法目标

　　 FP-growth算法是2000年韩嘉炜等人在关联分析apriori算法的基础上提出的一种操作更简单的频繁项集挖掘的算法。apriori算法在产生频繁模式全集时需要多次扫描数据集，这使得其时间复杂度和空间复杂度都较大。而FP-growth算法通过一种FP-tree的概念只需要扫描数据集两次即可。

　　首先我们先回到宏观上关联分析存在的原理。关联分析的经典案例就是“啤酒和尿布”，其过程是收集用户每一次的购买清单，

牛奶,鸡蛋,面包,尿布
鸡蛋,爆米花,尿布,啤酒
鸡蛋,面包,尿布
牛奶,鸡蛋,面包,爆米花,尿布,啤酒
牛奶,面包,啤酒
鸡蛋,面包,啤酒
牛奶,面包,尿布
牛奶,鸡蛋,面包,黄油,尿布
牛奶,鸡蛋,黄油,尿布

这里的每一行代表一位顾客一次买的商品清单，也称为一个事务。其中“牛奶”、“鸡蛋”等等这些称为元素项，“牛奶,鸡蛋,面包,薯片”这种任意个元素项的组合称为元素项集。总行数设为N，元素项的任意组合(包括单个元素项)在事务中出现的频次除以N称为该元素项集的支持度(support)。当某些元素项集的支持度比较高(例如大于20%——称为设定的最小支持度）则称为是频繁项集。

　　比如总事务数10000条，包含[“啤酒”,"尿布"]这个元素项集的有4000条，其支持度是40%，已经很高了。那么包含[“啤酒”]的如果有4500条，包含[“尿布”]的有5500条，那么买啤酒再买尿布的概率是4000/4500=89%，买尿布再买啤酒的概率是4000/5500=73%，这种称为置信度(confidence)。

【机器学习算法应用和学习_4_应用篇】关联分析/频繁项集挖掘_FP-growth算法

　　而关联规则指的是发现形如X—>Y（比如啤酒—>尿布）的规则，其所依赖的是支持度s(X—>Y)足够大，否则只是偶然出现的或者应用面太小也没有意义。且置信度c(X—>Y)足够大，足以表明X出现时，Y大概率就会出现。至于为什么X出现时，Y会有这么大的概率出现，可以再往对象特征去套去猜测，算法当然不会告诉你因果。比如“啤酒和尿布”就是发现这样的人群是年轻父亲比较多，再通过调研就可能容易知道是所谓的“在美国有婴儿的家庭中，一般是母亲在家中照看婴儿，年轻的父亲去超市买尿布。父亲在购买尿布的同时，往往会顺便为自己购买啤酒。”了。为什么说所谓的，，只是因为没这种感知，倒是觉着可能沃尔玛通过这种事件做营销的可能性更大。

所以关联规则的策略就是两步骤：

（1）计算支持度找出所有频繁项集：即找到所有大于最小支持度的所有项集，这些项集称为频繁项集。Apriori算法的一个很重要的性质——频繁项集的所有非空子集也是频繁的。反过来说就是，如果一个项集是非频繁的，那么它的所有超集也是非频繁的。所以可以先去掉那些非频繁的元素项。

（2）计算置信度找到关联规则：也就是从上一步得到的频繁项集中，计算其中各元素项或项集之间的置信度，从而找到置信度较高的那些规则，称为强规则。

而FP-growth要做的就是第一步，并不做第二步，所以算法目标只是“频繁项集挖掘”。

三、算法原理

【机器学习算法应用和学习_4_应用篇】关联分析/频繁项集挖掘_FP-growth算法

1.术语

除了上面出现的术语，该算法的其他术语如下：

最小支持度：就是人为给定和输入的一个最小的支持度阈值，大于这个支持度的元素项集称为频繁项集。实际支持度是百分比，但在给定的数据集中，总事务数是固定的，所以习惯不除以N而直接用频次。

FP树：FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP树与其他如搜索数结构类似，但有两个不同：一是一个元素项可以在一棵FP数中出现多次；二是通过链接来链接相似元素，被连起来的元素项可以看成一个链表。

头指针表：存的是所有频繁元素项及其频数的一个字典，另外还存了该元素项在FP树的第一个节点（第一个的意思是在事务中从上到下遍历第一次碰到的该元素项，“第几个”这本身没啥意义，只是为了在遍历寻找该元素项的所有条件模式基时能方便地从头指针表开始遍历到所有该元素项所在的节点而已）。

【机器学习算法应用和学习_4_应用篇】关联分析/频繁项集挖掘_FP-growth算法

上面就是一个带有头指针表的FP树。左边的是头指针表，存的就是形如{ 元素项:(频数,指向该元素项在FP树的第一个节点的指针)}的这样一个字典。右边就是FP树，事务顺序不同，构造出来的FP树不太一样，但这并不重要，FP树只是一种便于遍历的数据结构，遍历结果都是一样的。每个节点存除了该元素项、频数、父节点、子节点之外，还存了该元素项在FP数的下一个节点（带箭头的线）。

某元素项的条件模式基：指的是该元素项在FP树的结点的前缀路径，例如元素项t的前缀路径就有两条z-x-y-s，z-x-y-r。FP-growth算法后续会遍历所有频繁元素项的所有条件模式基，这里为了遍历到FP树上该元素项的所有节点，就是从上面头指针表存的指向该元素项在FP树第一个节点的指针开始，沿着节点存的下一个节点遍历到最后的。

2.优缺点

优点：

1.基于Apriori构建，一般比Apriori快；

缺点：

1.实现比较困难，在某些数据集上性能会下降。

2.算法原理(伪代码)

1.输入数据预处理：loadSimpDat()函数创建输入数据或输入数据并createInitSet(dataSet)初始化成后续函数需要的形式；

输入数据：

simpDat = [['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']]

初始化后数据：

{frozenset({'h', 'z', 'r', 'j', 'p'}): 1,
 frozenset({'w', 'z', 'v', 'u', 'y', 's', 't', 'x'}): 1,
 frozenset({'z'}): 1, frozenset({'n', 'r', 'x', 's', 'o'}): 1,
 frozenset({'q', 'z', 'r', 'p', 'y', 't', 'x'}): 1, 
 frozenset({'q', 't', 'z', 'm', 'y', 'e', 's', 'x'}): 1}

输入数据是类似最上面这样的结构，也可以从文档读取。但基于重复元素项集还需要遍历几次这种浪费时间的事，后续函数接受的输入数据集是统计好各元素项集频数的字典格式，这样就方便只遍历一次直接加上对应频数即可。

2.创建存储FP树的数据结构：这里用类treeNode的方式创建可以迭代的节点的存储结构，便于后面函数调用该类并最终存储下整个FP树；

其中定义了类的几个属性，name节点元素项名称、count 频数、nodeLink 一个链接指向该节点元素项的下一个同元素项节点、parent 父节点（便于后续寻找条件模式基时上溯前缀路径）、children 子节点；

定义了两个方法，inc(self, numOccur)是当在该节点下创建子节点时，对该节点的频数进行加上新频数的操作；disp(self, ind=1)则是以文字形式显示出整个FP-树（注意并没有像之前的图那么直观，只是以缩进代替链接，因为FP树只是一种数据结构，并不是输出结果，所以并没有那么重要。当然你可以改呀。。）。

3.构建输入数据集的只包含频繁元素项的FP树的主函数：createTree(dataSet, minSup=1)就是对输入数据集创建FP树的函数；

输入参数dataSet就是前面初始化后的数据集，minSup=1就是人为给定的最小支持度，不传时默认为1。

在该函数中，对数据集进行了两次遍历，

第一次遍历，计算每个元素项的频次，取得频次大于最小支持度的频繁项集；

第二次遍历，从数据集的每行元素项集中，去除不频繁项集，并对元素项集内按元素项的频次降序排列，最后调用updateTree(items, inTree, headerTable, count)递归构建FP树，其中updateTree函数中调用了updateHeader(nodeToTest, targetNode)更新头指针表。

该函数返回的是只包含频繁元素项的FP树retTree,和只包含频繁元素项的头指针表headerTable。可以输出一下看看，比如下面的headerTable就是一个字典，存储的每个键-值结构是

'z': [5, <__main__.treeNode object at 0x0000000004F9A940>]
这样的结构，键是元素项，值是频数和在FP树该元素项所在的第一个节点的指针。

【机器学习算法应用和学习_4_应用篇】关联分析/频繁项集挖掘_FP-growth算法

4.寻找某个元素项的所有条件模式基：findPrefixPath(basePat, treeNode)；

输入参数basePat是要寻找的某个元素项，treeNode就是头指针表存的该元素项在FP树的第一个节点；

其中，在findPrefixPath函数内遍历该元素项在FP树的所有节点，并调用ascendTree(leafNode, prefixPath)函数返回该节点的前缀路径；

在ascendTree(leafNode, prefixPath)函数中，输入参数是该元素项所在的某个节点leafNode和一个空的前缀路径列表prefixPath，该函数循环取节点的父节点，将父节点添加进prefixPath中，并递归调用自己以实现循环取完所有的前缀节点，最后prefixPath就是一个节点的前缀路径列表；

最后将该元素项所有节点的所有前缀路径添上频数，形成字典condPats。

返回的是该元素项的所有条件模式基condPats。

5.创建发现频繁项集的主函数：mineTree(inTree, headerTable, minSup, preFix, freqItemList)，该函数会调用前面所有组件函数。

输入参数inTree是3中返回的只包含频繁元素项的FP树retTree，headerTable是3中返回的只包含频繁元素项的头指针表headerTable，minSup是最小支持度，preFix是空集合（为啥要传入空集合呢，是因为函数内再递归调用时是有值要传入的，这个参数的实际作用是在不断递归中保存前几层递归的元素项——后面讲），freqItemList是空列表（这个初始也是空列表，是在函数内递归中逐渐有值添加，最后作为要输出的所有频繁项集的列表）。

在主函数中经历的过程是，

　　首先将头指针表降序排列(是啥顺序没啥影响)，然后循环遍历，寻找每一个元素项的条件模式基——其中，该元素项会作为一个频繁项集添加到freqItemList；

如果该元素项的条件模式基作为一个新的数据集，经过去除小于最小支持度的元素项后，头指针表还有频繁元素项存在，那么需要递归调用mineTree函数，且将该元素项作为preFix传入——之后就会将该元素项和新的头指针表的每个元素分别组合同样会作为一个频繁项集添加到freqItemList，当然如果其中某元素项新的头指针还有元素，仍会继续递归。

返回的是所有的频繁项集freqItemList。后面代码设置了断点输出看看循环的过程：

r  #遍历原始FP-树频数最低的元素r，其前缀路径有3条，{z:1},{z:1,x:1,y:1},{x:1,y:1}，其中没有元素项>=3,所以只将{'r'}加入freqItemList
y  #遍历倒数第二低的元素y，其前缀路径有1条，{z:3,x:3}，频繁元素项有值，递归调用，先将{'y'}加入freqItemList
conditional tree for:  {'y'}  #此时y的条件模式基的频繁元素项头指针表中有俩元素项，z和x
   Null Set   1
     z   3
       x   3
z  #先遍历y条件模式基里的z，z没有前缀路径，所以只将{'y','z'}加入freqItemList
x  #再遍历y条件模式基里的x，x有前缀路径{'z':3}，所以再此递归，先将{'y','x'}加入freqItemList
conditional tree for:  {'y', 'x'} #此时{'y','x'}的条件模式基里满足条件的只有z
   Null Set   1
     z   3
z  #遍历{'y','x'}条件模式基里的z，z没有了前缀路径，所以只将{'y','x','z'}加入freqItemList
s  #以此类推，遍地倒数第三低的元素s...
conditional tree for:  {'s'}
   Null Set   1
     x   3
x
t
conditional tree for:  {'t'}
   Null Set   1
     z   3
       x   3
z
x
conditional tree for:  {'t', 'x'}
   Null Set   1
     z   3
z
x
conditional tree for:  {'x'}
   Null Set   1
     z   3
z
z
[{'r'}, {'y'}, {'y', 'z'}, {'y', 'x'}, {'z', 'y', 'x'}, {'s'}, {'s', 'x'}, {'t'}, {'t', 'z'}, {'t', 'x'}, {'z', 't', 'x'}, {'x'}, {'z', 'x'}, {'z'}]

　　看完这个过程就会发现，FP-growth只是用更简单有效的遍历FP-tree的办法将存在于事务中的所有支持度大于最小支持度的元素项集找出来了。本质上，如果穷举所有元素项集，计算其频率，再将小于最小支持度的剔除就是了。但在非常多的元素项的数据集中，这个计算会很耗费时间。

四、源代码

#1.创建原始输入数据集
def loadSimpDat():
    simpDat = [['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 simpDat
#后续函数输入的是元素项集:频数的集合，所以需要初始化一下输入的数据集
def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] =retDict.get(frozenset(trans),0)+1
    return retDict

#测试代码1，并创建供后续使用的输入数据集
simpDat=loadSimpDat()
initSet=createInitSet(simpDat)
print(initSet)

#2.创建FP树的存储结构
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue
        self.count = numOccur
        self.nodeLink = None
        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)

#测试代码2
rootNode = treeNode('pyramid',9,None)
rootNode.children['phoenix']=treeNode('phoenix',3,None)
rootNode.children['eye']=treeNode('eye',3,None)
rootNode.disp()

#,3.创建FP树
def createTree(dataSet, minSup=1): 
    headerTable = {}
    #-----第一次遍历，计算每个元素项的频次，取得频次大于最小支持度的频繁项集------------
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    headerTable = {k:v for k,v in headerTable.items() if v >= minSup}
    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)
    #----第二次遍历，构建FP树，FP树只含频繁项------------------------------------------
    for tranSet, count in dataSet.items():
        localD = {}
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][0]
        if len(localD) > 0:
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable

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:
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    if len(items) > 1:
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)

def updateHeader(nodeToTest, targetNode): 
    while (nodeToTest.nodeLink != None): 
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode

#测试代码3
myFPtree, myHeaderTab=createTree(initSet, 3)
myFPtree.disp()
print(myHeaderTab)

#4.找到某个给定元素项的条件模式基
def ascendTree(leafNode, prefixPath):
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)
    
def findPrefixPath(basePat, treeNode):
    condPats = {}
    while treeNode != None:
        prefixPath = []
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 1: 
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.nodeLink
    return condPats

#5.整合代码，寻找频繁模式
'''
这里加了一个freqItemDict，原先输出的是freqItemList即所有频繁项集，我想按频数降序看频繁项集
'''
def mineTree(inTree, headerTable, minSup, preFix, freqItemList,freqItemDict):
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]
    for basePat in bigL:  
        print(basePat)
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)
        freqItemList.append(newFreqSet)
　　　　 freqItemDict[frozenset(newFreqSet)]=headerTable[basePat][0]
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        myCondTree, myHead = createTree(condPattBases, minSup)
        if myHead != None:
            print ('conditional tree for: ',newFreqSet)
            myCondTree.disp(1)            
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList,freqItemDict)
    return freqItemList,freqItemDict

#测试代码5
freqItems=[]
freqItemDict={}
mineTree(myFPtree,myHeaderTab,3,set([]),freqItems,freqItemDict)
print(freqItemDict)

无注释版代码下载

注释版代码下载

五、应用实践

　　在进行寻找用户一次使用多个形式的频繁组合用以重构场景的实例中发现，562个原始元素项集，21个元素项，按20%的最小支持度，给我输出了49个频繁项集。项集确实不多，但本身用户使用多个形式是有使用场景的，而生成一些拆出来的组合可能并没有实际意义，所以这个应用目前来说不太可信。

　　这个实例中，我其实我想要的是：1.去掉支持度小的噪声元素项；2.尽可能形成可解释的场景（原本是想说取到最佳的组合，但算法并不知道什么是最佳组合，所以只要元素项集尽可能少再去推可能的场景）。

　　于是不去使用FP-growth，而是只修改和使用createTree函数内的算法。先遍历原始数据集计算所有频繁元素项的频数，然后去掉原始元素项集内非频繁元素项的频数，重复元素项集合并即可。在这个过程中，最需要的是调整minSup的值。

　　按照这个思路，最后设计出来的参数是三个，dataSet,minItemSup,minSetSup，分别是输入数据集，元素项最小支持度，元素项集最小支持度。元素项最小支持度会看所有元素项的频数，取与后面断档较大的前几项，比如取5%啥的；元素项集最小支持度根据现有元素项集排序，取前二十左右所在的最小支持度。

　　最后结果是筛选出二十个左右频繁元素项集，除后面几个排序跟元素排序略有不同，各个元素项集频数可能略有提高之外，实际跟不处理没有太大区别。。

　　所以最后也只是根据筛选出来的频繁元素项集猜测可能场景，并扩入其他特征重复执行以验证确认真实场景。忽然感觉没太大意义了，太麻烦了，就拖着慢慢做吧，开始做别的项目。

参考资料：

[1] FP-Tree算法的实现. Orisun. 华夏35度. 2011

[2]关联分析：FP-Growth算法.datahunter.2014

2019-05-16 20:17:11

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：【机器学习算法应用和学习_4_应用篇】关联分析/频繁项集挖掘_FP-growth算法 - Python技术站