精华内容
下载资源
问答
  • FP-growth算法python实现

    2020-04-01 17:52:33
    FP-growth算法python实现含数据集,FP-growth算法是将数据集存储在一个特定的FP树结构之后挖掘其中的频繁项集,即常在一块出现的元素项的集合FP树。
  • FP-Growth算法python实现(完整代码

    热门讨论 2015-07-04 00:40:44
    包含两个文件,一个是刚构造好FP-tree的代码,另一个是FP-Growth算法python实现的完全代码。更多的介绍请见博客:http://blog.csdn.net/bone_ace/article/details/46746727
  • Fp-Growth算法通过构造一个树结构来压缩数据记录,使得挖掘频繁项集只需要扫描两次数据记录,而且该算法不需要生成候选集合,所以效率会比较高。
  • 关联规则挖掘中有几个经典算法,Apriori算法因为其效率比较低,时间复杂度很高,因此韩佳伟改进了该算法,附件是fp-growth的python实现。
  • FP-Growth算法python实现

    2017-08-11 16:49:50
    python实现FP-Growth 频繁模式算法
  • FP-growth算法是不产生候选集的关联规则挖掘算法,在许多领域中具有很高的实际应用价值。然而经典的FP-growth算法是内存驻留算法,只能处理小数据集,在面对海量数据集时显得无能为力。对经典FP-growth算法FP-tree...
  • FP-Growth-算法 该存储库包含用于(市场篮子)数据集中规则挖掘的 FP-Growth-Algorithm 的 C/C++ 实现。 描述 主文件 - 这是驱动程序。 它从用户输入数据集、最小支持度 (0-100) 和最小置信度 (0-1) FP_TREE_GEN.c ...
  • FP-growth算法以及代码实现

    千次阅读 2019-11-25 19:01:46
    FP-growth算法以及代码实现 FP-growth算法介绍 FP-growth算法,它被用于挖掘频繁项集,它把数据集存储为一个叫FP树的数据结构里,这样可以更高效地发现频繁项集或频繁项对。 FPFP即Frequent Pattern,FP树看...

    FP-growth算法以及代码实现

    FP-growth算法介绍
    FP-growth算法,它被用于挖掘频繁项集,它把数据集存储为一个叫FP树的数据结构里,这样可以更高效地发现频繁项集或频繁项对。

    FP树
    FP即Frequent Pattern,FP树看上去就是一棵前缀树,根节点是空集,结点上是单个元素,保存了它在数据集中的出现次数,出现次数越多的元素越接近根。此外,结点之间通过链接(link)相连,只有相似元素会被连起来,连起来的元素又可以看成链表。同一个元素可以在FP树中多次出现,根据位置不同,对应着不同的频繁项集。可以为FP树设置最小支持度,过滤掉出现次数太少的元素。
    FP树每个结点上都是一个单独的元素,及其在路径中的出现次数。

    构建FP树
    1.遍历一次数据集,统计每个元素出现的次数,然后把出现次数较小的滤掉,然后对每个样本按照元素出现次数重排序
    2.构造FP树。从根节点∅开始,将过滤并排序后的样本一个个加入树中,若FP树不存在现有元素则添加分支,若存在则增加相应的值。

    每个样本都是排序过的,频数高的频繁项集在前面,它总是更接近根结点,所以也可以把每个样本看成一棵子树,而我们要做的就是把子树添加到FP树里

    FP树构建实例
    在这里插入图片描述
    根据此数据集构造的FP树为:
    在这里插入图片描述
    从FP树挖掘频繁项集
    步骤如下:
    1.从FP树提取条件模式基
    2.用条件模式基构造FP树
    3.重复1和2直到树只包含一个元素
    提取条件模式基
    条件模式基(conditional pattern base)定义为以所查找元素为结尾的所有前缀路径(prefix path)的集合。我们要做的就是从header列表开始,针对每一个频繁项,都查找其对应的条件模式基。
    上述实例路径:
    在这里插入图片描述
    频繁项集:
    在这里插入图片描述
    代码实现

    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)
    
    # 当出现两个或两个以上的相似项时,找到最后一个相似项的实例,让该实例的self.nodeLink属性保存新出现的相似项
    # 效果如同是在一条链的最后一个节点后再接入一个节点,这些链就是self.nodeLink
    def updateHeader(nodeToTest, targetNode):
        while nodeToTest.nodeLink != None:
            nodeToTest = nodeToTest.nodeLink
        nodeToTest.nodeLink = targetNode
    
    # 接收处理好的事务列表,画出FP树
    def updateFPtree(items, inTree, headerTable, count):
        if items[0] in inTree.children:
            # 判断items的第一个结点是否已作为子结点
            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:
            updateFPtree(items[1::], inTree.children[items[0]], headerTable, count)
    
    # 输入字典格式的事务和最小支持度,返回FP树和项头表
    def createFPtree(dataSet, minSup=3):
        headerTable = {}
        for trans in dataSet:
            for item in trans:
                headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
        for k in list(headerTable.keys()):
            if headerTable[k] < minSup:
                del (headerTable[k])  # 删除不满足最小支持度的元素
        freqItemSet = set(headerTable.keys())  # 满足最小支持度的频繁项集
        if len(freqItemSet) == 0:
            return None, None
        for k in headerTable:
            headerTable[k] = [headerTable[k], None]  # element: [count, node]
        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]  # element : count
            if len(localD) > 0:
                # 根据全局频数从大到小对单样本排序
                orderedItem = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]
                #print('orderItems=', orderedItem)
                # 用过滤且排序后的样本更新树
                updateFPtree(orderedItem, retTree, headerTable, count)
        return retTree, headerTable
    
    # 构造成 element : count 的形式,以字典形式输出
    def createInitSet(dataSet):
        retDict = {}
        for trans in dataSet:
            trans = "".join(trans).split(',')
            key = frozenset(trans)
            if key in retDict:
                retDict[frozenset(trans)] += 1
            else:
                retDict[frozenset(trans)] = 1
        return retDict
    
    # 递归回溯,找到给定节点往上回溯到根节点的路径,并把路径存到列表中
    def ascendFPtree(leafNode, prefixPath):
        if leafNode.parent != None:
            prefixPath.append(leafNode.name)
            ascendFPtree(leafNode.parent, prefixPath)
    
    # 找到给定元素名称的条件模式基,以字典格式存贮
    def findPrefixPath(basePat, myHeaderTab):
        treeNode = myHeaderTab[basePat][1]  # basePat在FP树中的第一个结点
        condPats = {}
        while treeNode != None:
            prefixPath = []
            ascendFPtree(treeNode, prefixPath)  # prefixPath是倒过来的,从treeNode开始到根
            if len(prefixPath) > 1:
                condPats[frozenset(prefixPath[1:])] = treeNode.count  # 关联treeNode的计数
            treeNode = treeNode.nodeLink  # 下一个basePat结点
        return condPats
    def mineFPtree(inTree, headerTable, minSup, preFix, freqItemList):
        # 最开始的频繁项集是headerTable中的各元素
        bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]  # 根据频繁项的总频次排序
        #print("bigL:  ",bigL)
        for basePat in bigL:  # 对每个频繁项
            newFreqSet = preFix.copy()
            newFreqSet.add(basePat)
            freqItemList.append(newFreqSet)
            condPattBases = findPrefixPath(basePat, headerTable)  # 当前频繁项集的条件模式基
            myCondTree, myHead = createFPtree(condPattBases, minSup)  # 构造当前频繁项的条件FP树
            if myHead != None:
                mineFPtree(myCondTree, myHead, minSup, newFreqSet, freqItemList)  # 递归挖掘条件FP树
    if __name__ == '__main__':
        parsedDat = [line.split() for line in open('FPGrowth_datasets/shopping_cart.csv').readlines()]
        initSet = createInitSet(parsedDat)
        myFPtree, myHeaderTab = createFPtree(initSet)
        myFPtree.disp()
        myFreqList = []
        mineFPtree(myFPtree, myHeaderTab, 3, set([]), myFreqList)
        print("频繁项集的数量是: %s" % len(myFreqList))
        for item in myFreqList:
            print(item)
    
    展开全文
  • 通过对两个有代表性的算法Apriori和FP-Growth的剖析,说明频集模式挖掘的过程,比较有候选项集产生和无候选项集产生算法的特点,并给出FP-tree结构的构造方法以及对挖掘关联规则的影响,提出了对算法的改进方法。
  • 大数据环境下,传统的串行FP-Growth算法在处理海量数据时,占用内存过大、频繁项多,适用于大数据情况的PFP(parallel FP-Growth)算法存在数据量增大无法处理的缺陷。针对这些问题,提出了基于Hadoop的负载均衡数据分割FP...
  • 关联分析:FP-Growth算法
  • FP-growth算法

    2017-11-20 15:10:30
    代码是对原有代码的bug进行修改,只要修改数据就可以正常使用
  • fpGrowth算法

    2018-05-16 16:21:54
    FPGrowth算法主要分为两个步骤:FP-tree构建、递归挖掘FP-tree。FP-tree构建通过两次数据扫描,将原始数据中的事务压缩到一个FP-tree树,该FP-tree类似于前缀树,相同前缀的路径可以共用,从而达到压缩数据的目的。...
  • FP-Growth算法代码

    热门讨论 2008-02-29 12:45:33
    FP-Growth算法代码
  • FP-growth算法原理解析

    2020-10-15 16:33:26
    FP-growth算法(FP, Frequent Pattern) FP-growth算法只需要对数据库进行两次扫描。而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定的模式是否频繁,因此FP-growth算法要比Apriori算法快。 FP-growth...

    FP-growth算法(FP, Frequent Pattern)

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

    FP-growth算法只需要扫描两次数据集,第一遍对所有数据元素出现次数进行计数,第二遍只需考虑那些频繁的元素。发现频繁项集的基本过程分为两步,构建FP树和从FP树中挖掘频繁项集。

    简单来说,算法的目的就是在多个出现的数据项中找到出现次数最多的数据项或者数据项集合,这里的最多指的是出现次数大于等于给定的阈值(最小支持度)。找到单个数据项的次数较为简单,只需要遍历计数即可,但是对于数据项的组合即数据项集的出现次数较难确定,比如,某个数据项A与数据项B的出现次数都是频繁的,但是他们的组合也就是说他们同时出现的次数却不频繁。数据集中出现较为频繁的数据项组合我们成为频繁项集,该频繁项集的大小大于等于1。FP-growth算法就是挖掘数据中的频繁项集算法中的一种。

    在介绍FP-growth算法之前先介绍一些概念。

    • 数据挖掘算法中的数据是按照组(条)分的,一组数据是一个事务(这里解释不严谨,读者就理解为数据是一条一条输进算法里的,每条数据中包含一些数据项,一条数据就是一个事务)。
    • FP树,FP树是FP-growth算法中构建的树形数据结构,用于组织数据。该树中每个叶结点到根节点的路径中所有数据项就是与该叶结点同时出现的数据们,不同叶结点到根节点的路径中共同的部分是大家共同的数据。
    • CPB(Conditional pattern base)条件模式基,CPB是指FP树中叶结点到根节点这条路径中,不包含跟结点和叶结点的其他所有数据的集合(或者说是这些结点组成的路径,即前缀路径)。算法会对每个频繁项用其所有的CPB构建条件FP树。这棵树还是FP树,只不过所用的数据是某个频繁项的CPB。条件FP树是整个算法的难点,因为频繁项集通过该树挖掘,挖掘的过程是递归的。这里简单理解就是对于频繁项T的条件FP树中所有的数据项是可以与频繁项T进行组合形成频繁项集的元素的集合。

     

    FP-growth算法运行过程

    对于FP-growth算法的介绍,本文打算通过一个例子来解释。

    假设某个超市想通过分析用户的购买习惯来改变进货数量以实现获利最大化。现在给出了某天的购物记录,为了理解方便假设所有商品的每个用户只买了一件,也就是对于一条交易记录只在乎商品的种类,数量不予考虑。再者,为了方便书写这里把商品名用字母表示。

    记录ID

    记录中的商品名

    001

    r,z,h,j,p

    002

    z,y,x,w,v,u,t,s

    003

    z

    004

    r,x,n,o,s

    005

    y,r,x,z,q,t,p

    006

    y,z,x,e,q,s,t,m

    • 遍历数据集,统计所有元素出现次数

    r

    z

    h

    j

    p

    y

    x

    w

    v

    u

    t

    s

    n

    o

    q

    e

    m

    3

    5

    1

    1

    2

    3

    4

    1

    1

    1

    3

    3

    1

    1

    2

    1

    1

    此处设置最小支持度为3,也就是所出现次数大于等于3的即为频繁。在构建FP树时,为了使各个事务(记录)的公共部分在同一路径上,因此创建树时,各个事务应该一定顺序排列,此处按照商品出现次数的倒序排序。所以经过筛选得

    记录ID

    记录中的商品名

    筛选且排序后的商品

    001

    r,z,h,j,p

    z,r

    002

    z,y,x,w,v,u,t,s

    z,x,y,s,t

    003

    z

    z

    004

    r,x,n,o,s

    x,s,r

    005

    y,r,x,z,q,t,p

    z,x,y,r,t

    006

    y,z,x,e,q,s,t,m

    z,x,y,s,t

    • 构建FP树

    FP树的根节点是空结点,逐条将排序筛选后的记录插入树中。如果记录中的结点在树的该路径中有则该结点计数加一,否则分支。

    1. 初始时,FP树只有一个结点即∅
    2. 将{z,r}记录插入后得

    1. 将{z,x,y,s,t}记录插入后得

    1. 将{z}将入

    1. 将{x,s,r}

    1. 将{z,x,y,r,t}

    1. 将{z,x,y,s,t}

    此时FP树已经构建的差不多了,为了在找频繁项集时方便找到树中相同的数据,需要把相同的数据项连接起来(结点链接)

    • 从FP树中挖掘频繁项集

    创建了FP树之后,就可以抽取频繁项集了。与Apriori算法类似,首先从单个元素集合开始,然后在此基础上逐步构建更大的集合。FP-growth算法中的频繁项集是递归挖掘的,其过程简单解释就是在集合中每次加入一个新元素a后得频繁项集S,在此基础上继续创建a的条件FP树把对应不满足的元素删除得到对应的头表H,然后在以此递归创建H中所有元素的条件FP树得其头表,直到某递归层H为空。有些复杂,具体看示例演示过程。

    首先,查找每个频繁项的条件模式基

    频繁项

    条件模式基

    z

    {}5

    r

    {x, s}1, {z, x, y}1, {z}1

    x

    {z}3, {}1

    y

    {z, x}3

    s

    {z, x, y}2, {x}1

    t

    {z, x, y, s}2, {z, x, y, r}1

    找到所有频繁项的CPB后就是创建条件FP树,递归的挖掘频繁项集。

    计算过程如下:

    找到所有元素的CPB之后(编程时不用把所有元素CPB都找出再进行下一步,直接递归操作),创建对应的条件FP树,将各个CPB中的元素的出现次数进行统计,剔除不满足最小支持度的集合,得到的就是该元素对应条件FP树。比如对于元素t,经过计数后得{z:3, x:3, y:3, s:2, r:1}。将s与r剔除因为不满足最小支持度3。对应的含义是{t, s}, {t, r}两个项集不频繁,注意此处元素t是频繁的,但是与s,r的组合不频繁。

    频繁项

    筛选后的条件模式基

    z

    {}5

    r

    {}0

    x

    {z}3, {}1

    y

    {z, x}3

    s

    {x}2,{x}1

    t

    {z, x, y,}3

    然后开始创建频繁项集。频繁项集的产生过程其实就是不断组合元素得到不同长度的集合,找到出现频数高的集合。接下来对每个元素分别创建包含它们且长度不同的集合。我们为了方便介绍将各个元素条件FP树产生的头指针表记为H。

     

    这里挑选元素的顺序是按照每个条件FP树中频繁项频数的逆序选择的。

    1. 对于z来说,z本身是频繁的,所以包含单个元素的项集频繁即{z},又因为H为空所以最终Z的频繁项集为{z}
    2. 对于r来说,r本身是频繁的,所以包含单个元素的项集频繁即{r},又因为H为空所以最终r的频繁项集为{r}
    3. 对于x来说,x本身是频繁的,所以包含单个元素的项集频繁即{x},又因为H为{{z}3, {}},对应的条件FP树如图

    所以x与z的组合频繁,而z的H为空,也就是z对应的条件FP树为空,所以含x的频繁项集为{{x},{x,z}}

       

        4. 对于y来说,y本身是频繁的,所以包含单个元素的项集频繁即{y},又因为H为{{z, x}3},对应的条件FP树如图

    所以z与y组合的集合频繁。而z的H为空即z的条件FP树为空,所以y与z的组合只有{y, z}。

     

    而y与x的组合也频繁,所以{y,x}频繁,然后x的条件FP树如左图。注意此处,x的条件FP树是在y的FP树的基础上创建的,也就是说,该条件FP树中与x频繁的元素也与y频繁,因为该元素也出现在y的FP树中。x的H包含z,z的FP树为空,所以不在递归下去,故{y,x,z}也频繁。所以包含y的频繁项集为{{y},{y, z},{y,x,z},{y,x}}。

        5. 对于s来说,s本身是频繁的,所以包含单个元素的项集频繁即{s},又因为H为{{x}2,{x}1},条件FP树为

    同理{s,x}频繁,将x加入后继续生成x的条件FP树为空,不在继续寻找。得包含s的频繁项集为{{s}, {s,x}}

       6. 对于t来说,t本身是频繁的,所以包含单个元素的项集频繁即{t},又因为H为{{z, x, y,}3},条件FP树为

    然后,将z加入集合{t},z的条件FP树为空不在继续遍历得频繁项集{t,z}。

     

    然后,将x加入集合{t},因为x的条件FP 树为下图,故在{t,x}中加入z得

    {t,x,z},由于z的条件FP树为空,不在继续遍历。故此次过程得到的频繁项集为{{t,x},{t,x,z}}。

     

    然后,将y加入集合{t},y对应的条件FP树为下图,故在{t,y}中加入z,由于z的条件FP树为空,不在继续遍历。得{t,y,z}。故此次递归得到的频繁项集为{{t,y,z},{t,y}}

     

    然后,将x加入{t,y},生成x的条件FP树为左图,故在{t,y,x}中加入z得{t,y,x,z}。由于z的条件FP树为空,不在继续遍历。故此次递归得到的频繁项集为

    {{t,y,x,z},{t,y,x} }

    最终结果为

    频繁项

    频繁项集

    z

    {z}

    r

    {r}

    x

    {{x},{x,z}}

    y

    {{y},{y, z},{y,x,z},{y,x}}

    s

    {{s},{s,x}}

    t

    {{t},{t,z},{t,x,z},{t,x},{t,y,z},{t,y,x,z},{ t,y,x },{ t,y}}

           总结一下过程,对于每个元素a的FP树的H中的每个元素b都与a的组合频繁,而在a元素对应的H中,有与b频繁的元素c,那么{a,b,c}也频繁。同理可以处理c及其他元素。之所以可以这样做是应为元素a与其对应的H中的所有元素都频繁出现,而在该H中,b又与c频繁出现,c在该H中,所以a,b,c频繁。每一个元素对应不同的H,每一次递归时,对应的频繁项集的长度就会增加,H范围会在上一递归层H_old的范围的基础上缩小。

     

    如果上面的过程没懂,下面手写推到一遍方便理解

    Refenence

    J.Han, J.Pei, Y.Yin, R.Mao, “Mining Frequent Patterns without Candidate Generations: A Frequent-Pattern Tree Approach,” Data Mining and Knowledge Discovery 8 (2004), 53-87

    《机器学习实战》

     

    展开全文
  • FP-growth算法理解和实现

    万次阅读 多人点赞 2018-05-16 17:18:58
    FP-growth算法理解 FP-growth(Frequent Pattern Tree, 频繁模式树),是韩家炜老师提出的挖掘频繁项集的方法,是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或频繁项对,即常在一块出现的元素项的集合FP...

    FP-growth算法理解

    FP-growth(Frequent Pattern Tree, 频繁模式树),是韩家炜老师提出的挖掘频繁项集的方法,是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或频繁项对,即常在一块出现的元素项的集合FP树。
    FP-growth算法比Apriori算法效率更高,在整个算法执行过程中,只需遍历数据集2次,就能够完成频繁模式发现,其发现频繁项集的基本过程如下:
    (1)构建FP树
    (2)从FP树中挖掘频繁项集

    FP-growth的一般流程如下:
    1:先扫描一遍数据集,得到频繁项为1的项目集,定义最小支持度(项目出现最少次数),删除那些小于最小支持度的项目,然后将原始数据集中的条目按项目集中降序进行排列。
    2:第二次扫描,创建项头表(从上往下降序),以及FP树。
    3:对于每个项目(可以按照从下往上的顺序)找到其条件模式基(CPB,conditional patten base),递归调用树结构,删除小于最小支持度的项。如果最终呈现单一路径的树结构,则直接列举所有组合;非单一路径的则继续调用树结构,直到形成单一路径即可。
    示例说明
    如下表所示数据清单(第一列为购买id,第二列为物品项目):

    TidItems
    1I1, I2, I5
    2I2, I4
    3I2, I3
    4I1, I2, I4
    5I1, I3
    6I2, I3
    7I1, I3
    8I1, I2, I3, I5
    9I1, I2, I3

    第一步:构建FP树
    1. 扫描数据集,对每个物品进行计数:

    I1I2I3I4I5
    67622

    2. 设定最小支持度(即物品最少出现的次数)为2
    3. 按降序重新排列物品集(如果出现计数小于2的物品则需删除)

    I2I1I3I4I5
    76622

    4. 根据项目(物品)出现的次数重新调整物品清单

    TidItems
    1I2, I1, I5
    2I2, I4
    3I2, I3
    4I2, I1, I4
    5I1, I3
    6I2, I3
    7I1, I3
    8I2, I1, I3, I5
    9I2, I1, I3

    5. 构建FP树
    加入第一条清单(I2, I1, I5):
    这里写图片描述
    加入第二条清单(I2, I4):
    出现相同的节点进行累加(I2)
    这里写图片描述
    下面依次加入第3-9条清单,得到FP树:
    这里写图片描述
    第二步:挖掘频繁项集
    对于每一个元素项,获取其对应的条件模式基(conditional pattern base)。条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径。
    按照从下往上的顺序,考虑两个例子。
    (1)考虑I5,得到条件模式基{(I2 I1:1), (I2 I1 I3)}, 构造条件FP树如下,然后递归调用FP-growth,模式后缀为I5。这个条件FP树是单路径的,在FP-growth中直接列举{I2:2,I1:2,I3:1}的所有组合,之后和模式后缀I5取并集得到支持度大于2的所有模式:{ I2 I5:2, I1 I5:2, I2 I1 I5:2}。
    I5对应的条件FP树
    (2)I5的情况是比较简单的,因为I5对应的条件FP-树是单路径的。下面考虑I3,I3的条件模式基是{(I2 I1:2), (I2:2), (I1:2)},生成的条件FP-树如左下图,然后递归调用FP-growth,模式前缀为I3。I3的条件FP-树仍然是一个多路径树,首先把模式后缀I3和条件FP树中的项头表中的每一项取并集,得到一组模式{I2 I3:4, I1 I3:4},但是这一组模式不是后缀为I3的所有模式。还需要递归调用FP-growth,模式后缀为{I1,I3},{I1,I3}的条件模式基为{I2:2},其生成的条件FP-树如右下图所示。这是一个单路径的条件FP-树,在FP-growth中把I2和模式后缀{I1,I3}取并得到模式{I1 I2 I3:2}。理论上还应该计算一下模式后缀为{I2,I3}的模式集,但是{I2,I3}的条件模式基为空,递归调用结束。最终模式后缀I3的支持度大于2的所有模式为:{ I2 I3:4, I1 I3:4, I1 I2 I3:2}
    I3的条件FP树
    {I1,I3}的条件FP树
    根据FP-growth算法,最终得到的支持度大于2频繁模式如下:

    item条件模式基条件FP树产生的频繁模式
    I5{(I2 I1:1),(I2 I1 I3:1)}(I2:2, I1:2)I2 I5:2, I1 I5:2, I2 I1 I5:2
    I4{(I2 I1:1), (I2:1)}(I2:2)I2 I4:2
    I3{(I2 I1:2), (I2:2), (I1:2)}(I2:4, I1:2), (I1:2)I2 I3:4, I1 I3:4, I2 I1 I3:2
    I1{(I2:4)}(I2:4)I2 I1:4

    FP-growth算法实现

    1. FP树的类定义

    class treeNode:
        def __init__(self, nameValue, numOccur, parentNode):
            self.name = nameValue #节点名字
            self.count = numOccur #节点计数值
            self.nodeLink = None #用于链接相似的元素项
            self.parent = parentNode      #needs to be updated
            self.children = {} #子节点
    
        def inc(self, numOccur):
            '''
            对count变量增加给定值
            '''
            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. FP树构建函数

    def createTree(dataSet, minSup=1):
        '''
        创建FP树
        '''
        headerTable = {}
        #第一次扫描数据集
        for trans in dataSet:#计算item出现频数
            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())
        #print ('freqItemSet: ',freqItemSet)
        if len(freqItemSet) == 0: return None, None  #如果没有元素项满足要求,则退出
        for k in headerTable:
            headerTable[k] = [headerTable[k], None] #初始化headerTable
        #print ('headerTable: ',headerTable)
        #第二次扫描数据集
        retTree = treeNode('Null Set', 1, None) #创建树
        for tranSet, count in dataSet.items():  
            localD = {}
            for item in tranSet:  #put transaction items in order
                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)#将排序后的item集合填充的树中
        return retTree, headerTable #返回树型结构和头指针表
    
    def updateTree(items, inTree, headerTable, count):
        if items[0] in inTree.children:#检查第一个元素项是否作为子节点存在
            inTree.children[items[0]].inc(count) #存在,更新计数
        else:   #不存在,创建一个新的treeNode,将其作为一个新的子节点加入其中
            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):
        '''
        this version does not use recursion
        Do not use recursion to traverse a linked list!
        更新头指针表,确保节点链接指向树中该元素项的每一个实例
        '''
        while (nodeToTest.nodeLink != None):    
            nodeToTest = nodeToTest.nodeLink
        nodeToTest.nodeLink = targetNode

    3. 抽取条件模式基

    def ascendTree(leafNode, prefixPath): #迭代上溯整棵树
        if leafNode.parent != None:
            prefixPath.append(leafNode.name)
            ascendTree(leafNode.parent, prefixPath)
    
    def findPrefixPath(basePat, treeNode): #treeNode comes from header table
        condPats = {}
        while treeNode != None:
            prefixPath = []
            ascendTree(treeNode, prefixPath)
            if len(prefixPath) > 1: 
                condPats[frozenset(prefixPath[1:])] = treeNode.count
            treeNode = treeNode.nodeLink
        return condPats

    4. 递归查找频繁项集

    def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
        bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]# 1.排序头指针表
        for basePat in bigL:  #从头指针表的底端开始
            newFreqSet = preFix.copy()
            newFreqSet.add(basePat)
            print ('finalFrequent Item: ',newFreqSet)    #添加的频繁项列表
            freqItemList.append(newFreqSet)
            condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
            print ('condPattBases :',basePat, condPattBases)
            # 2.从条件模式基创建条件FP树
            myCondTree, myHead = createTree(condPattBases, minSup)
    #         print ('head from conditional tree: ', myHead)
            if myHead != None: # 3.挖掘条件FP树
                print ('conditional tree for: ',newFreqSet)
                myCondTree.disp(1)            
                mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

    5. 测试结果

    def loadSimpDat():
        simpDat = [
                    ['I1','I2','I5'],
                    ['I2','I4'],
                    ['I2','I3'],
                    ['I1','I2','I4'],
                    ['I1','I3'],
                    ['I2','I3'],
                    ['I1','I3'],
                    ['I1','I2','I3','I5'],
                    ['I1','I2','I3']
                  ]
        return simpDat
    
    def createInitSet(dataSet):  
        retDict = {}  
        for trans in dataSet:  
            retDict[frozenset(trans)] = retDict.get(frozenset(trans), 0) + 1 #若没有相同事项,则为1;若有相同事项,则加1  
        return retDict
    minSup = 2
    simpDat = loadSimpDat()
    initSet = createInitSet(simpDat)
    myFPtree, myHeaderTab = createTree(initSet, minSup)
    myFPtree.disp()
    myFreqList = []
    mineTree(myFPtree, myHeaderTab, minSup, set([]), myFreqList)
       Null Set   1
         I2   7
           I1   4
             I5   1
             I4   1
             I3   2
               I5   1
           I4   1
           I3   2
         I1   2
           I3   2
    finalFrequent Item:  {'I5'}
    condPattBases : I5 {frozenset({'I1', 'I2'}): 1, frozenset({'I1', 'I2', 'I3'}): 1}
    conditional tree for:  {'I5'}
       Null Set   1
         I1   2
           I2   2
    finalFrequent Item:  {'I1', 'I5'}
    condPattBases : I1 {}
    finalFrequent Item:  {'I2', 'I5'}
    condPattBases : I2 {frozenset({'I1'}): 2}
    conditional tree for:  {'I2', 'I5'}
       Null Set   1
         I1   2
    finalFrequent Item:  {'I1', 'I2', 'I5'}
    condPattBases : I1 {}
    finalFrequent Item:  {'I4'}
    condPattBases : I4 {frozenset({'I2'}): 1, frozenset({'I1', 'I2'}): 1}
    conditional tree for:  {'I4'}
       Null Set   1
         I2   2
    finalFrequent Item:  {'I2', 'I4'}
    condPattBases : I2 {}
    finalFrequent Item:  {'I1'}
    condPattBases : I1 {frozenset({'I2'}): 4}
    conditional tree for:  {'I1'}
       Null Set   1
         I2   4
    finalFrequent Item:  {'I1', 'I2'}
    condPattBases : I2 {}
    finalFrequent Item:  {'I3'}
    condPattBases : I3 {frozenset({'I2'}): 2, frozenset({'I1'}): 2, frozenset({'I1', 'I2'}): 2}
    conditional tree for:  {'I3'}
       Null Set   1
         I2   2
         I1   4
           I2   2
    finalFrequent Item:  {'I2', 'I3'}
    condPattBases : I2 {frozenset({'I1'}): 2}
    conditional tree for:  {'I2', 'I3'}
       Null Set   1
         I1   2
    finalFrequent Item:  {'I1', 'I2', 'I3'}
    condPattBases : I1 {}
    finalFrequent Item:  {'I1', 'I3'}
    condPattBases : I1 {}
    finalFrequent Item:  {'I2'}
    condPattBases : I2 {}
    
    myFreqList
    [{'I5'},
     {'I1', 'I5'},
     {'I2', 'I5'},
     {'I1', 'I2', 'I5'},
     {'I4'},
     {'I2', 'I4'},
     {'I1'},
     {'I1', 'I2'},
     {'I3'},
     {'I2', 'I3'},
     {'I1', 'I2', 'I3'},
     {'I1', 'I3'},
     {'I2'}]
    

    参考文献:
    1. 机器学习实战
    2. https://blog.csdn.net/sealyao/article/details/6460578
    3. https://blog.csdn.net/chem0527/article/details/51775007

    展开全文
  • FP-growth算法原理及python实现(详细代码解释)

    万次阅读 多人点赞 2018-11-02 17:11:28
    目录 算法简介 ... FP-growth算法被用来挖掘频繁项集,也就是说从已给的多条数据记录中挖掘出哪些项是频繁一起出现的。该算法适用于标称型数据,即离散型数据。它比Apriori算法更高效,因为该算...

    目录

    算法简介

    构建FP树

    挖掘频繁项集


    算法简介

    FP-growth算法的应用我们经常接触到。比如,你在百度的搜索框内输入某个字或词,搜索引擎会自动补全查询词项,而这些词项都是和搜索词经常一起出现的。

     FP-growth算法被用来挖掘频繁项集,也就是说从已给的多条数据记录中挖掘出哪些项是频繁一起出现的。该算法适用于标称型数据,即离散型数据。它比Apriori算法更高效,因为该算法只需要对数据库进行两次扫描,而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁。

    注:最后有python代码汇总。

    举个例子说明什么是项,项集,频繁项集,以及支持度。

    有下面这样一份数据记录。

    事务ID事务中的元素项
    001r,z,h,j,p
    002z,y,x,w,v,u,t,s
    003z
    004r,x,n,o,s
    005y,r,x,z,q,t,p
    006y,z,x,e,q,s,t,m

    这份数据一共有6条记录,每条记录中的元素就是项,第1条记录中有5个项,分别为:r,z,h,j,p。项的集合就是项集,比如,[r]是一个项集,[r,z]是一个项集,[r,z,h,j,p]也是一个项集,项集是指项的任意组合。而频繁项集是指,那些在记录中经常一起出现的项组合成的集合。那么,“经常”是怎么衡量的呢?这里就涉及到支持度的概念。支持度是说出现的次数,它可以针对单个项,也可以针对项的组合,在这6条数据记录中,r 一共出现了3次,所以 r 的支持度是3,项集(r,x)出现了2次,所以(r,x)的支持度是2。

     FP-growth算法挖掘频繁项集的基本过程如下:

    (1)构建FP树。

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

    构建FP树

    FP代表频繁模式(Frequent Pattern)。

    我们先看看FP树长什么样子。以下这棵FP树是根据上面那份数据记录建立的。

    可以看出,一棵FP树看上去与计算机科学中的其他树结构类似,但是它包含着连接相似节点的链接(图中的红色虚线部分)。 相似节点是指前缀路径不同的项,如在上面的FP树中 r 的前缀路径有3个,分别为(z),(z,x,y),(x,s),于是,这些 r 们就叫做相似节点。后面用python构建FP树时会创建一个字典结构存储这些相似元素。

    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) #打印时,子节点的缩进比父节点更深一级

    运行下面这段代码:

    rootNode=treeNode('pyramid',9,None) #创建节点
    rootNode.children['eye']=treeNode('eye',13,None) #增加子节点
    rootNode.children['phoenix']=treeNode('phoenix',3,None) #增加另一个子节点
    rootNode.disp() #展示树

    运行结果:

     由于“eye”和“phoenix”都是”pyramid“,所以在展示树的结构时,“eye”和“phoenix”的缩进深度相同,都比”pyramid“的缩进深度更深一级。

    除此之外,我们还需要把原始事务数据集处理成字典的形式,方面后面的函数调用。

    定义两个函数,如下:

    from collections import OrderedDict
    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=OrderedDict()
        for trans in dataSet:
            retDict[frozenset(trans)]=1
        return retDict

    函数loadSimpDat()把多条数据记录存储成列表的形式,函数createInitSet(dataSet)把每条数据记录冻结(frozenset函数)后作为字典的键,而每个键对应的值都是1。

    我们运行一下看看结果。

    simpDat=loadSimpDat()
    simpDat

    initSet=createInitSet(simpDat)
    initSet

    下面开始构建FP树。(主要从解读实现代码的角度来介绍这个过程)

    FP树第一次扫描数据库是为了获得每个元素项的出现频率。实现这一步的代码如下(注:代码中的dataSet 是经过上面所说的createInitSet(dataSet)函数处理后的数据结果,即一个字典结构):

    headerTable={}#用来存储每项元素及其出现次数
    for trans in dataSet:#遍历每条记录
        for item in trans:#遍历每条记录的每项元素
            headerTable[item]=headerTable.get(item,0)+dataSet[trans]#计算每项元素的出现次数
    print headerTable
    print ("headerTable's length: %s" % len(headerTable))

    这时headerTable包含17个元素:

    接下来,去掉不满足最小支持度的元素项。

    for k in headerTable.keys():
        if headerTable[k]<3:#这里的3是指最小支持度的取值,可根据实际情况改变
            del(headerTable[k])#如果某项元素的支持度小于最小支持度,从headerTable中删掉该元素
    freqItemSet=set(headerTable.keys())#freqItemSet中的每一项元素的支持度均大于或等于最小支持度
    print headerTable
    print ("headerTable's length: %s" % len(headerTable))

    去掉不满足最小支持度的元素项后,headerTable已由原来的17个元素减少为6个:

    再下一步构建FP树。

    freqItemSet存储的都是符合条件的元素。如果freqItemSet非空,证明确实有符合条件的元素。从前面的运行结果可以知道,headerTable里面每一个键对应的值是该元素在所有的事务数据记录中出现的次数。现在,我们在每个键对应的值中增加一个“None”,为后面的存储相似元素做准备。

    if len(freqItemSet)!=0:
        for k in headerTable:
            headerTable[k]=[headerTable[k],None]
    headerTable

    headerTable调整后结果如下:

    构建FP树的思路是这样的:读入每个项集也就是每条记录,并将其添加到一条已经存在的路径中。如果该路径不存在,则创建一条新路径。假设有集合{z,x,y}和{y,z,r},为了保证相同项只出现一次,需要对每条记录里的元素项进行排序。在每条记录中,这种排序是根据每个元素出现的次数进行的,也就是说出现次数越多,排位越前。

    for tranSet,count in dataSet.items():#遍历每一条事务数据
        localD={}
        for item in tranSet:#遍历这条数据中的每个元素
            if item in freqItemSet:#过滤每条记录中支持度小于最小支持度的元素
                localD[item]=headerTable[item][0]#把headerTable中记录的该元素的出现次数赋值给localD中的对应键
        if len(localD)>0:#如果该条记录有符合条件的元素
            orderedItems=[v[0] for v in sorted(localD.items(),key=lambda p:p[1],reverse=True)]#元素按照支持度排序,支持度越大,排位越靠前
            print orderedItems

    每条数据过滤掉不符合条件的元素并重新排序后结果如下:

     对比着原始事务数据来看:

    在对事务数据过滤和排序之后,就可以构建FP树了。

    从空集(符号为Φ)开始,依次遍历过滤,排序后的每一条记录,如果树中已经存在记录中的某个元素,那么已存在的元素增加值即可,如果树中不存在记录中的元素,那么增加一个分支。我们通过添加前两条事务为例,加深对建树的过程理解。

    下面的代码用于实现FP树的构建过程,其中一部分的代码在前面已经解释过了。

    def createTree(dataSet,minSup=1):
        headerTable={}#用来存储每项元素及其出现次数
        for trans in dataSet:#遍历每条记录
            for item in trans:#遍历每条记录的每项元素
                headerTable[item]=headerTable.get(item,0)+dataSet[trans]#计算每项元素的出现次数
        for k in headerTable.keys():
            if headerTable[k]<minSup:
                del(headerTable[k])#如果某项元素的支持度小于最小支持度,从headerTable中删掉该元素
        freqItemSet=set(headerTable.keys())#freqItemSet中的每一项元素的支持度均大于或等于最小支持度
        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]#把headerTable中记录的该元素的出现次数赋值给localD中的对应键
            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的子节点中已经存在该元素
            inTree.children[items[0]].inc(count)#树中该元素增加值,增加的值为该元素所在记录的出现次数
        else:
            inTree.children[items[0]]=treeNode(items[0],count,inTree)#如果树中不存在该元素,重新创建一个节点
            if headerTable[items[0]][1]==None:#如果在相似元素的字典headerTable中,该元素键对应的列表值中,起始元素为None
                headerTable[items[0]][1]=inTree.children[items[0]]#把新创建的这个节点赋值给起始元素
            else:
                updateHeader(headerTable[items[0]][1],inTree.children[items[0]])#如果在相似元素字典headerTable中,该元素键对应的值列表中已经有了起始元素,那么把这个新建的节点放到值列表的最后
        if len(items)>1:#如果在这条记录中,符合条件的元素个数大于1
            updateTree(items[1::],inTree.children[items[0]],headerTable,count)#从第二个元素开始,递归调用updateTree函数。
    def updateHeader(nodeToTest,targetNode):#该函数实现把targetNode放到链接的末端
        while (nodeToTest.nodeLink!=None):
            nodeToTest=nodeToTest.nodeLink
        nodeToTest.nodeLink=targetNode

    可以看出,以上这段代码中,函数updateHeader和函数updateTree都是为了给函数createTree调用的。

    既然知道怎么构建FP树了,我们运行试试。

    和前面说的一样,先处理数据集,再调用createTree函数。

    simpDat=loadSimpDat()
    initSet=createInitSet(simpDat)
    myFPtree,myHeaderTab=createTree(initSet,3)
    myFPtree.disp()

    结果如下:

    这个结果与刚开始展示的FP树结果一致。

    挖掘频繁项集

    从一棵FP树中挖掘频繁项集的三个基本步骤如下:

    (1)从FP树中获得条件模式基;

    (2)利用条件模式基,构建一个条件FP树;

    (3)迭代重复步骤(1)和(2),直到树包含一个元素项为止。

    先介绍条件模式基的概念。条件模式基是相对于树中的某个元素来说的,它指的是该元素在树中的前缀路径,是介于该元素与树根节点之间的所有内容。

    比如,在我们构建好的FP树中:

    每个元素的前缀路径如下表:

    频繁项前缀路径 
    z{} 5
    r{x,s} 1,{z,x,y} 1,{z} 1
    x{z} 3,{} 1
    y{z,x} 3
    s{z,x,y} 2,{x} 1
    t{z,x,y,s} 2,{z,x,y,r} 1

    以下的代码实现查找一棵FP树中某个元素节点及其全部相似元素节点的前缀路径。把前缀路径冻结作为字典的键,前缀路径的计数取值与该元素节点的计数一样。

    def ascendTree(leafNode,prefixPath):#该函数找出元素节点leafNode的所有前缀路径,并把包括该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#condPats存储的是元素节点treeNode及其所有相似元素节点的前缀路径和它的计数

    把FP树中所有元素的前缀路径都找出来:

    for item in freqItemSet:
        condPats=findPrefixPath(item,myHeaderTab[item][1])
        print item
        print condPats

    结果:

    这些元素的前缀路径与前面总结的一样,区别是当该元素的前缀路径为空时不显示,当然,还有一点,前缀路径的元素没有按顺序排列,但是不会影响后面的构建条件FP树。

    t 的条件FP树如下图:

    在构建条件FP树的过程中,每加入一条记录,都会调用createTree函数,这样的作用之一是可以过滤掉非频繁项,如上面的s和r。频繁项集在这个过程中就逐渐出来了。

    挖掘频繁项集的代码如下:

    def mineTree(inTree,headerTable,minSup,preFix,freqItemList):
        bigL=[v[0] for v in sorted(headerTable.items(),key=lambda p:p[1])]#排序,从频率低到频率高排列树中的元素
        for basePat in bigL:#遍历inTree中的所有元素
            newFreqSet=preFix.copy()
            newFreqSet.add(basePat)
            freqItemList.append(newFreqSet)
            conPattBases=findPrefixPath(basePat,headerTable[basePat][1])#寻找元素basePat及其相似元素的所有前缀路径,并以字典的形式存储它们
            myCondTree,myHead=createTree(conPattBases,minSup)
            if myHead!=None:#只要FP树中还有元素,递归调用mineTree函数
                mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)

    运行以下代码:

    freqItems=[]
    mineTree(myFPtree,myHeaderTab,3,set([]),freqItems)
    freqItems

    结果:

     以上的结果就是基于已构建的FP树通过mineTree函数挖掘得到的频繁项集。

    python代码汇总如下:

    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)
    def updateHeader(nodeToTest, targetNode):
        while nodeToTest.nodeLink != None:
            nodeToTest = nodeToTest.nodeLink
        nodeToTest.nodeLink = targetNode
    def updateFPtree(items, inTree, headerTable, count):
        if items[0] in inTree.children:
            # 判断items的第一个结点是否已作为子结点
            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:
            updateFPtree(items[1::], inTree.children[items[0]], headerTable, count)
    
    def createFPtree(dataSet, minSup=1):
        headerTable = {}
        for trans in dataSet:
            for item in trans:
                headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
        for k in headerTable.keys():
            if headerTable[k] < minSup:
                del(headerTable[k]) # 删除不满足最小支持度的元素
        freqItemSet = set(headerTable.keys()) # 满足最小支持度的频繁项集
        if len(freqItemSet) == 0:
            return None, None
        for k in headerTable:
            headerTable[k] = [headerTable[k], None] # element: [count, node]
    
        retTree = treeNode('Null Set', 1, None)
        for tranSet, count in dataSet.items():
            # dataSet:[element, count]
            localD = {}
            for item in tranSet:
                if item in freqItemSet: # 过滤,只取该样本中满足最小支持度的频繁项
                    localD[item] = headerTable[item][0] # element : count
            if len(localD) > 0:
                # 根据全局频数从大到小对单样本排序
                orderedItem = [v[0] for v in sorted(localD.items(), key=lambda p:p[1], reverse=True)]
                # 用过滤且排序后的样本更新树
                updateFPtree(orderedItem, retTree, headerTable, count)
        return retTree, headerTable
    def loadSimpDat():
        simDat = [['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 simDat
    # 构造成 element : count 的形式
    def createInitSet(dataSet):
        retDict={}
        for trans in dataSet:
            key = frozenset(trans)
            if retDict.has_key(key):
                retDict[frozenset(trans)] += 1
            else:
                retDict[frozenset(trans)] = 1
        return retDict
    # 数据集
    def loadSimpDat():
        simDat = [['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 simDat
    # 构造成 element : count 的形式
    def createInitSet(dataSet):
        retDict={}
        for trans in dataSet:
            key = frozenset(trans)
            if retDict.has_key(key):
                retDict[frozenset(trans)] += 1
            else:
                retDict[frozenset(trans)] = 1
        return retDict
    # 递归回溯
    def ascendFPtree(leafNode, prefixPath):
        if leafNode.parent != None:
            prefixPath.append(leafNode.name)
            ascendFPtree(leafNode.parent, prefixPath)
    # 条件模式基
    def findPrefixPath(basePat, myHeaderTab):
        treeNode = myHeaderTab[basePat][1] # basePat在FP树中的第一个结点
        condPats = {}
        while treeNode != None:
            prefixPath = []
            ascendFPtree(treeNode, prefixPath) # prefixPath是倒过来的,从treeNode开始到根
            if len(prefixPath) > 1:
                condPats[frozenset(prefixPath[1:])] = treeNode.count # 关联treeNode的计数
            treeNode = treeNode.nodeLink # 下一个basePat结点
        return condPats
    def mineFPtree(inTree, headerTable, minSup, preFix, freqItemList):
        # 最开始的频繁项集是headerTable中的各元素
        bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p:p[1])] # 根据频繁项的总频次排序
        for basePat in bigL: # 对每个频繁项
            newFreqSet = preFix.copy()
            newFreqSet.add(basePat)
            freqItemList.append(newFreqSet)
            condPattBases = findPrefixPath(basePat, headerTable) # 当前频繁项集的条件模式基
            myCondTree, myHead = createFPtree(condPattBases, minSup) # 构造当前频繁项的条件FP树
            if myHead != None:
                # print 'conditional tree for: ', newFreqSet
                # myCondTree.disp(1)
                mineFPtree(myCondTree, myHead, minSup, newFreqSet, freqItemList) # 递归挖掘条件FP树

     

     

    展开全文
  • java实现FP-Growth

    2017-08-11 21:04:35
    java 实现FP-Growth算法
  • FP-GROWTH算法的实现

    2016-10-26 09:28:12
    FP-GROWTH算法的实现
  • 1. FP-Growth算法弊端 FP-Growth算法是挖掘频繁项集最常用的算法之一,其是基于迭代FP-Tree生成频繁项集的关联规则算法。此算法仅进行两次数据集扫描,递归迭代构建FP-Tree(FP条件树),当FP-Tree中只有一个单分支时...
  • 代码主要利用Python工具实现FP-growth高效发现频繁项集,简单明了,易于理解
  •   本文讲解fp-growth算法的原理,梳理了fp-growth算法的实现流程,并使用Java实现fp-growth算法,通过面向对象的思想使算法更加结构化,并使其更加通俗易懂。 二、绪论   在之前的博客中我们详细介绍了Apriori...
  • 比较简单的一种实现方式,算法容易理解,关键在数据结构的设计。
  • FP-growth算法通俗讲解

    2020-11-29 13:29:21
    FP-growth算法是一种高效发现频繁集的方法。例如你在搜索引擎中搜索一个词,它会自从补全查询词项,该处用到了FP-growth算法,通过查看互联网上的用词来找出经常在一块出现的词。【FP(Frequent Pattern)】 FP-...
  • 数据挖掘中关联挖掘算法比较典型的有Apriori和FP-growth算法.实验和研究证明FP-growth算法优于Apriori算法.但是针对大型数据库这两种算法都存在着较大缺陷,不仅要两次或多次扫描数据库,而且很难处理支持度和数据...
  • 频繁项集挖掘(二)FP-Growth算法 FP-Growth(Frequent Patterns)相比于Apriori是一种更加有效的频繁项集挖掘算法,FP-Growth算法只需要对数据库进行两次扫描,而Apriori算法对于每次产生的候选项集都会扫描一次...
  • fp-growth-rs FP-Growth算法在纯Rust中的实现。
  • 用法将其添加到您的Cargo.toml中:[dependencies] fp-growth =“ 0.1”示例使用fp_growth :: algorithm :: FPGrowth; fn main(){让交易= vec![vec![“ e”,“ c”,“ a”,“ b”,“ f”,“ h”],vec![“ ...
  • 并行FP-growth算法

    2020-03-01 20:59:07
    产生原因:由于无论数据集规模大小,使用的频繁项集挖掘算法所占内存的使用和计算成本代价过大,因此产生了并行式FP-Growth算法,该算法将挖掘数据集的任务分配在多个计算机上,每个计算机相互独立并行的计算与通信...
  • FP-GROWTH 算法的应用

    2010-04-24 20:48:09
    关于数据挖掘中 FP-GROWTH算法的应用 An Implementation of the FPgrowth Algorithm

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,044
精华内容 1,617
关键字:

fp-growth算法的代码