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

    2020-04-01 17:52:33
    FP-growth算法python实现含数据集,FP-growth算法是将数据集存储在一个特定的FP树结构之后挖掘其中的频繁项集,即常在一块出现的元素项的集合FP树。
  • Fp-Growth算法通过构造一个树结构来压缩数据记录,使得挖掘频繁项集只需要扫描两次数据记录,而且该算法不需要生成候选集合,所以效率会比较高。
  • 关联规则挖掘中有几个经典算法,Apriori算法因为其效率比较低,时间复杂度很高,因此韩佳伟改进了该算法,附件是fp-growth的python实现。
  • FP-growth算法是不产生候选集的关联规则挖掘算法,在许多领域中具有很高的实际应用价值。然而经典的FP-growth算法是内存驻留算法,只能处理小数据集,在面对海量数据集时显得无能为力。对经典FP-growth算法FP-tree...
  • FP-Growth算法python实现

    2017-08-11 16:49:50
    python实现FP-Growth 频繁模式算法
  • FP-growth算法

    2017-11-20 15:10:30
    本代码是对原有代码的bug进行修改,只要修改数据就可以正常使用
  • FP-Growth算法python实现(完整代码)

    热门讨论 2015-07-04 00:40:44
    包含两个文件,一个是刚构造好FP-tree的代码,另一个是FP-Growth算法python实现的完全代码。更多的介绍请见博客:http://blog.csdn.net/bone_ace/article/details/46746727
  • 通过对两个有代表性的算法Apriori和FP-Growth的剖析,说明频集模式挖掘的过程,比较有候选项集产生和无候选项集产生算法的特点,并给出FP-tree结构的构造方法以及对挖掘关联规则的影响,提出了对算法的改进方法。
  • FP-Growth-算法 该存储库包含用于(市场篮子)数据集中规则挖掘的 FP-Growth-Algorithm 的 C/C++ 实现。 描述 主文件 - 这是驱动程序。 它从用户输入数据集、最小支持度 (0-100) 和最小置信度 (0-1) FP_TREE_GEN.c ...
  • 关联分析:FP-Growth算法
  • 用法将其添加到您的Cargo.toml中:[dependencies] fp-growth =“ 0.1”示例使用fp_growth :: algorithm :: FPGrowth; fn main(){让交易= vec![vec![“ e”,“ c”,“ a”,“ b”,“ f”,“ h”],vec![“ ...
  • FP-GROWTH算法的实现

    2016-10-26 09:28:12
    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算法 FP-Growth(Frequent Patterns)相比于Apriori是一种更加有效的频繁项集挖掘算法,FP-Growth算法只需要对数据库进行两次扫描,而Apriori算法对于每次产生的候选项集都会扫描一次...

    频繁项集挖掘(二)FP-Growth算法

    FP-Growth(Frequent Patterns)相比于Apriori是一种更加有效的频繁项集挖掘算法,FP-Growth算法只需要对数据库进行两次扫描,而Apriori算法对于每次产生的候选项集都会扫描一次数据集来判断是否频繁,因此当数据量特别巨大,且扫描数据库的成本比较高时,FP-Growth的速度要比Apriori快。

    但是FP-Growth只能用于发现频繁项集,不能用于发现关联规则。

    FP-Growth原理分析

    FP-Growth算法实现步骤

    • 构建FP树
    • 从FP树中挖掘频繁项集

    FP-Growth算法将数据存储在一种被称为FP树的紧凑数据结构中。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hS0tzglA-1614269591504)(/img/fp-growth2.png)]

    下图就是利用上面的数据构建的一棵FP树(最小支持度为3):

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OHTe9xEW-1614269591507)(/img/fp-growth1.png)]

    • FP树中最小支持度指项集总共出现的次数
    • 一个元素项可以在一棵FP树中出现多次
    • FP树存储项集的出现频率,且每个项集会以路径的方式存储在树中
    • 存在相似元素的集合会共享树的一部分
    • 只有当集合之间完全不同时,树才会分叉
    • 树节点上给出集合中的单个元素及其在序列中的出现次数,路径会给出该序列的出现次数

    FP-Growth算法工作流程:

    • 扫描数据集两遍
    • 第一遍对所有元素项的出现次数进行计数
    • 根据前面的结论,如果某元素是不频繁的,那么包含该元素的超集也是不频繁的
    • 第二遍扫描,只考虑那些频繁元素,并且第二遍扫描开始构建FP树

    算法实现

    class treeNode(object):
        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 createTree(dataSet, minSup=1):  # create FP-tree from dataset but don't mine
        '''遍历数据集两遍'''
        # 第一遍对元素计数
        originHeaderTable = {}    # headerTable用于记录树的结构情况
        for trans in dataSet:
            for item in trans:
                originHeaderTable[item] = originHeaderTable.get(item, 0) + dataSet[trans]
    
        popKeys = []
        # 过滤掉非频繁项集
        for k in originHeaderTable.keys():
            # 记录非频繁项
            if originHeaderTable[k] < minSup:
                popKeys.append(k)
    
        freqItemSet = set(originHeaderTable.keys()) - set(popKeys)
    
        # headerTable用于记录树的结构情况
        headerTable = {}
        if len(freqItemSet) == 0:   # 如果初选没有频繁项集,那么直接退出
            return None, None
    
        # 重新构建headerTable
        for k in freqItemSet:
            headerTable[k] = [originHeaderTable[k], None]  # reformat headerTable to use Node link
        del originHeaderTable
    
        # 构建空树,根节点为空集
        root_node = treeNode('Null Set', 1, None)
        # 第二遍扫描,开始构建FP树
        for tranSet, count in dataSet.items():  # go through dataset 2nd time
            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, root_node, headerTable, count)  # populate tree with ordered freq itemset
        return root_node, headerTable  # return tree and header table
    
    def updateTree(items, parentNode, headerTable, count):
        # 判断第一个项集是已经是当前节点的子节点
        if items[0] in parentNode.children:  # check if orderedItems[0] in retTree.children
            # 如果是,那么直接count + 1
            parentNode.children[items[0]].inc(count)  # incrament count
        else:  # add items[0] to inTree.children
            # 如果不是,那么新建节点,并存储为当前节点的子节点
            parentNode.children[items[0]] = treeNode(items[0], count, parentNode)
            # 更新headerTable
    
            # 判断当前item是否是第一次记录
            if headerTable[items[0]][1] == None:
                # 如果是第一次,那么把新建的节点直接记录到头表中
                headerTable[items[0]][1] = parentNode.children[items[0]]
            else:
                # 如果不是第一次,那么说明新节点是当前item的节点的子节点,因此将它记录到当前分支的末位去,即设置为当前分支的叶子节点
                updateHeader(headerTable[items[0]][1], parentNode.children[items[0]])
        # 如果还有第二个元素,那么递归执行以上操作
        if len(items) > 1:
            updateTree(items[1::], parentNode.children[items[0]], headerTable, count)
    
    def updateHeader(lastNode, newLeafNode):
        # 判断上一节点是否有连接节点,如果没有,那么说明上一节点就是叶子节点,那么直接将新节点设为叶子节点
        while (lastNode.nodeLink != None):
            # 如果上一节点已经有连接节点,那么循环知道遍历到叶子节点,再设置新叶子节点
            lastNode = lastNode.nodeLink
        # 将新的叶子节点设置为旧叶子节点的连接节点
        lastNode.nodeLink = newLeafNode
    
    
    def loadTestDataset():
        dataset = [['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 dataset
    
    def createInitDataset(dataSet):
        dictDataset = {}
        for trans in dataSet:
            dictDataset[frozenset(trans)] = 1
        return dictDataset
    
    def buildCombinedItems(leafNode, combinedItems):
        if leafNode.parent != None:
            combinedItems.append(leafNode.name)
            buildCombinedItems(leafNode.parent, combinedItems)
    
    def buildCombinedDataset(nodeObject):
        # 根据节点名称,组合出新的项集节点
        combinedDataset = {}
        while nodeObject != None:
            combinedItems = []
            buildCombinedItems(nodeObject, combinedItems)
            if len(combinedItems) > 1:
                combinedDataset[frozenset(combinedItems[1:])] = nodeObject.count
            nodeObject = nodeObject.nodeLink
        return combinedDataset
    
    def scanFPTree(headerTable, minSup, parentNodeNames, freqItemList):
    
        # 遍历排序后的headerTable,(节点名称,节点信息)
        for baseNode, nodeInfo in headerTable.items():
            # 根据prefix
            newFreqSet = parentNodeNames.copy()
            newFreqSet.add(baseNode)
            # 节点计数值
            nodeCount = nodeInfo[0]
            # 节点对象
            nodeObject = nodeInfo[1]
            # 记录下频繁项集以及计数
            freqItemList.append((newFreqSet, nodeCount))
    
            # 根据当前节点的子节点,构建出新的项集组合
            combinedDataset = buildCombinedDataset(nodeObject)
    
            # 根据新的项集组合,重合构建子FP树
            subFPTree, subFPTreeHeaderTable = createTree(combinedDataset, minSup)
            # 如果头表不为空,那么递归新树的头表
            if subFPTreeHeaderTable != None:
                print('conditional tree for: ', newFreqSet)
                subFPTree.disp(1)
                # 根据新的头表 扫描FP-Tree
                scanFPTree(subFPTreeHeaderTable, minSup, newFreqSet, freqItemList)
    
    if __name__ == '__main__':
    
        from pprint import pprint
        simpDat = loadTestDataset()
        initSet = createInitDataset(simpDat)
        # 构建初始的FP-Tree
        initFPtree, initFPtreeHeaderTable = createTree(initSet, 3)
        initFPtree.disp(1)
    
        freqItems = []    # 存储频繁项集
        # 扫描FP树,找出所有符合条件的频繁项集
    
        root_node_names = set([])    # 从根路径空集开始扫描
        scanFPTree(initFPtreeHeaderTable, 3, root_node_names, freqItems)
        pprint(freqItems)
    
    展开全文
  •   本文讲解fp-growth算法的原理,梳理了fp-growth算法的实现流程,并使用Java实现fp-growth算法,通过面向对象的思想使算法更加结构化,并使其更加通俗易懂。 二、绪论   在之前的博客中我们详细介绍了Apriori...

    一、摘要

      本文讲解fp-growth算法的原理,梳理了fp-growth算法的实现流程,并使用Java实现fp-growth算法,通过面向对象的思想使算法更加结构化,并使其更加通俗易懂。

    二、绪论

      在之前的博客中我们详细介绍了Apriori算法的实现(要是不知道,可以自行百度或看我之前的博客),但大家应该可以发现,Apriori算法在求得频繁项集的时候会对数据集进行多次扫描,很大程度上降低算法执行的效率。实际上Apriori算法只是一类关联算法的试探,其效率较低,很难使用在实际环境中。于是韩家炜教授等人提了出FP-growth(Frequent Pattern growth)算法,该算法是频繁模式(Frequent Pattern, FP)挖掘领域的经典算法,它实现频繁项集的收集只需要扫描两遍数据集,降低了IO次数,大大提高了算法的效率,同时,该算法是可以在实际生产环境中使用的。

    三、算法介绍

      FP-growth算法性能强大是因为它将数据集化为了FPTree这一数据结构,寻找频繁项集的过程便是对这颗数进行操作的过程。
      由于这个算法的数据结构比较多,概念也不好用生涩的语言来描述,这里我们不再列举FP-growth算法的各个数据结构概念,而是在实际操作中进行讲解。
      首先我们先将算法的整个流程进行描述:
      (1)第一次扫描数据集统计每个项目出现的次数,并在头指针表中进行计数,然后删除不满足支持度要求的表项;
      (2)第二次扫描数据集删除每条记录中不满足支持度的项目,然后对每条记录中的项目按照其出现次数进行降序排序;
      (3)第三次扫描数据集建立FPTree并完善头指针表;
      (4)迭代(1)至(3)收集频繁项集;
      在这里我将两次扫描数据集给拆分成了三次,是因为这样代码的结构比较清晰,实际上可以将(2)和(3)合为一次扫描。而步骤(4)会在后面进行详细介绍。
      下面我们详细讲解算法过程。对于数据集:
    在这里插入图片描述
      在第一遍扫描数据集的时候,创建头指针表,利用头指针表记录每个项目出现的次数,然后删掉支持度没达到要求的项目对应的头指针表项。
    在这里插入图片描述
      第二次扫描数据集通过头指针表(判断项目对应的表项是否为空)删除每条记录中不满足支持度的项目,然后对每条记录中的项目按照其出现次数进行降序排序。
    在这里插入图片描述
      排序的时候需要注意一点,当两个项目的支持度一样时,需要对其按照一个新的规则再进行排序(如项目的ascii码),保证相同支持度的项目也是有序排列的,不然在构建FPTree的时候会出现误差。(后面举例说明)
      然后在第三次扫描的时候创建FPTree并完善头指针表。树中的每一条路径对应着一种相互关联项目组合(如购物篮分析中小票中的商品组合),每一个结点不光保存项目名称,还保存其出现的次数。
      开始时FPTree只有一个空的根节点,建立FPTree时我们遍历读取数据集中的每一条记录按排好序的顺序插入FP树,如果有对应结点则计数+1;没有的话创建新结点。直到所有的数据都插入到FP树后,FP树的建立完成。在建树过程中,还要利用头指针表连接相同的项目结点(头指针连接第一次出现的项目结点)。这样形容难以理解,下面直接给出例子。
      图中黑实线是树结点之间的连接;蓝色箭头是从头指针表发出的同项目结点链表。
      插入第一条记录 {A C E B F}:
    在这里插入图片描述
      插入第二条记录 {A C G}:
    在这里插入图片描述
      插入第三条记录 {E}:
    在这里插入图片描述
      这里就不继续展示插入记录的图了,直接给出最终的FPTree:在这里插入图片描述
      至此我们就得到了一颗完整的FPTree。之后我们便可以迭代建树收集频繁项集了。
      首先我们定义每一轮迭代为epoch,每一次的迭代我们都需要经历创建条件FPTree的过程,创建条件FPTree的步骤和创建FPTree是一样的,只不过我们的数据集是某一项目所有条件模式基的集合。
      在FPTree中,每一个项目都对应着一个或数个(取决于该项目对应的结点个数)条件模式基。条件模式基是该项目的一个结点到根节点的路径,而该条件模式基对应的记数为该节点的记数,而条件模式基的集合便是该项目所有结点对应的条件模式基的集合。
      比如项目F的条件模式基集合只有一个条件模式基,因为该FPTree中只有一个F结点(最左下角的)。
    在这里插入图片描述
      该条件模式基(不包含F结点)为{A C E B, 2}。同理我们可以得到所有项目的条件模式基。不过我们一般获取条件模式基的集合的步骤是:
      先对头指针表的所有表项根据项目出现的次数(即头指针表中的记数)进行降序排序(也需要保证相同记数的表项也是有序排序(如记数相同时按项目名称的ascii码再排一次)),然后从记数最少的表项对应的头指针指向的结点开始,根据蓝色箭头连成的链表依次寻找条件模式基,直到所有该项目对应的结点的条件模式基都被找到。便找到了一个项目对应的所有条件模式基。
      找到一个项目对应的所有条件模式基之后,我们便可以利用条件模式基的集合创建条件FPTree迭代收集频繁项集。在迭代收集频繁k项集的epoch,我们需要上一次迭代的频繁k-1项集。(注意第一次创建的FPTree对应的头指针表的每个表项对应的项目便是一项集,因为它们都满足最小支持度)
      这里用语言难以理解,我们这里直接给出迭代收集频繁项集的代码(但在段落五中讲解了迭代建树寻找频繁项集的原因,希望仔细了解):

    /**
    * 递归收集频繁项集
    *
    * @param headPointerTable   头指针表
    * @param preFrequentItemSet 递归前的频繁项集
    */
    private static void collectFrequentItemSet(Map<String, HeadPointer> headPointerTable, List<String> preFrequentItemSet) {
            // 把 Map 转为 List
            List<Map.Entry<String, HeadPointer>> headPointerList = new ArrayList<>(headPointerTable.entrySet());
            headPointerList.sort((i1, i2) -> {
                if (i2.getValue().getCount() > i1.getValue().getCount()) {
                    return -1;
                } else if (i2.getValue().getCount() < i1.getValue().getCount()) {
                    return 1;
                } else {
                    // 当两个项目出现次数一样时,需要再按ascii码排一次,保证相同支持度的项目也是有序排列的
                    return i2.getKey().compareTo(i1.getKey());
                }
            });
            // 从头指针表尾开始
            for (Map.Entry<String, HeadPointer> entry : headPointerList) {
                // 添加频繁项集(需要深复制一个新的List)
                List<String> newFrequentItemSet = new ArrayList<>(preFrequentItemSet);
                newFrequentItemSet.add(entry.getKey());
                addFrequentItemSet(newFrequentItemSet);
                // 获取条件模式基
                List<ConditionalPatternBase> conditionalPatternBases = getConditionalPatternBases(entry.getValue());
                // 创建fp树(将条件模式基集合作为新的数据集)
                Map<String, HeadPointer> nextHeadPointerTable = new HashMap<>();
                TreeNode root = new TreeNode();
                epoch(conditionalPatternBases, nextHeadPointerTable, root);
                // 递归获取频繁项集
                collectFrequentItemSet(nextHeadPointerTable, newFrequentItemSet);
            }
        }
    

      其中,倒数第二行的epoch()方法便是创建一颗FPTree的全部过程(三次扫描);方法collectFrequentItemSet()的参数preFrequentItemSet是频繁k-1项集。
      当所有的迭代完成之后,频繁项集也便都收集完了。
      之前我说过,需要保证相同支持度的项目也要是有序排序,这里给出一个例子。
      假设项目支持度A > B = C > D,且这些项目都满足最小支持度,我们删除不满足最小支持度的项目后,数据集有三条记录{C B A}{D B C A}{B C A},假设我们使用的是稳定的排序算法进行降序排序,则排序完的新记录为{A C B}{A B C D}{A B C},虽然看起来没有什么问题,我们画一下FPTree。
    在这里插入图片描述
      我们都知道,使用fp-growth算法获取频繁项集是为了求出满足置信度的关联规则来探求不同项目之间的关联,也就是同时出现的可能性,很明显,探求小票中不同商品间的关联关系跟商品在小票上出现的次序是没有关系的,也就是说记录是没有顺序的。虽然上面的三条记录ABC都同时出现了,但我们采用稳定的排序算法来排序,会导致即使ABC同时出现,但却被分到了不同的路径,也就是暗中给记录中的项目赋予了顺序这一属性,会导致最后的结果有误差。为了解决这个问题我们需要对相同支持度的项目也设置一个排序规则,如ascii码,这样我们排序后的记录会是这样的{A B C}{A B C D}{A B C},得到的FPTree是:
    在这里插入图片描述
      这才是我们想要的FPTree。
      至此,算法讲解部分就结束了。

    四、算法实现

      这里我们使用Java实现。
      (1)条件模式基类:

    public class ConditionalPatternBase {
        // 数据库项目集
        private List<String> record;
        // 出现次数
        private int count;
    
        public ConditionalPatternBase() {
            this.count = 1;
        }
    
        public ConditionalPatternBase(int count) {
            this.count = count;
        }
    
        public List<String> getRecord() {
            return record;
        }
    
        public void setRecord(List<String> record) {
            this.record = record;
        }
    
        public int getCount() {
            return count;
        }
    
        public void setCount(int count) {
            this.count = count;
        }
    }
    

      (2)头指针表项类:

    public class HeadPointer {
        // 项目出现次数
        private int count;
        // 头指针
        private TreeNode head;
        // 尾指针
        private TreeNode tail;
    
        public HeadPointer() {
            this.count = 1;
        }
    
        public HeadPointer(int count) {
            this.count = count;
        }
    
        /**
         * 计数增加
         */
        public void increase(int num) {
            count = count + num;
        }
    
        /**
         * 连接链表
         * @param node
         */
        public void connect(TreeNode node) {
            if (head == null) {
                head = node;
                tail = head;
            } else {
                tail.setNextSameItemNode(node);
                tail = node;
            }
        }
    
        public int getCount() {
            return count;
        }
    
        public void setCount(int count) {
            this.count = count;
        }
    
        public TreeNode getHead() {
            return head;
        }
    
        public void setHead(TreeNode head) {
            this.head = head;
        }
    
        public TreeNode getTail() {
            return tail;
        }
    
        public void setTail(TreeNode tail) {
            this.tail = tail;
        }
    }
    

      (3)FPTree结点类:

    public class TreeNode {
        // 项目名
        private String item;
        // 路径经过次数
        private int count;
        // 父节点
        private TreeNode parent;
        // 子节点
        private Map<String, TreeNode> children;
        // 链表下一节点(头指针表)
        private TreeNode nextSameItemNode;
    
        public TreeNode() {
            this.count = 0;
            this.children = new HashMap<>();
        }
    
        /**
         * 计数增加
         */
        public void increase(int num){
            count = count + num;
        }
    
        public String getItem() {
            return item;
        }
    
        public void setItem(String item) {
            this.item = item;
        }
    
        public int getCount() {
            return count;
        }
    
        public void setCount(int count) {
            this.count = count;
        }
    
        public TreeNode getParent() {
            return parent;
        }
    
        public void setParent(TreeNode parent) {
            this.parent = parent;
        }
    
        public Map<String, TreeNode> getChildren() {
            return children;
        }
    
        public void setChildren(Map<String, TreeNode> children) {
            this.children = children;
        }
    
        public TreeNode getNextSameItemNode() {
            return nextSameItemNode;
        }
    
        public void setNextSameItemNode(TreeNode nextSameItemNode) {
            this.nextSameItemNode = nextSameItemNode;
        }
    }
    

      (4)算法实体:

    public class FPGrowth {
        // 最小支持度
        private static double MIN_SUPPORT = 0.05;
        // 最小出现次数
        private static Integer MIN_APPEAR;
        // 频繁项集
        private static Map<Integer, Set<List<String>>> FREQUENT_ITEM_SET_TABLE;
    
        public static void main(String[] args) {
            // 加载数据集
            List<ConditionalPatternBase> dataset = loadData("E:\\data_mining_lab\\src\\data\\OnlineRetailZZ.txt");
            // 计算最小出现次数
            //MIN_APPEAR = (int) (MIN_SUPPORT * dataset.size());
            MIN_APPEAR = 1500;
            // 创建fp树
            Map<String, HeadPointer> headPointerTable = new HashMap<>();
            TreeNode root = new TreeNode();
            epoch(dataset, headPointerTable, root);
            // 获取频繁项集
            FREQUENT_ITEM_SET_TABLE = new HashMap<>();
            List<String> preFrequentItemSet = new ArrayList<>();
            collectFrequentItemSet(headPointerTable, preFrequentItemSet);
    
            System.out.println();
        }
    
        /**
         * 递归收集频繁项集
         *
         * @param headPointerTable   头指针表
         * @param preFrequentItemSet 递归前的频繁项集
         */
        private static void collectFrequentItemSet(Map<String, HeadPointer> headPointerTable, List<String> preFrequentItemSet) {
            // 把 Map 转为 List
            List<Map.Entry<String, HeadPointer>> headPointerList = new ArrayList<>(headPointerTable.entrySet());
            headPointerList.sort((i1, i2) -> {
                if (i2.getValue().getCount() > i1.getValue().getCount()) {
                    return -1;
                } else if (i2.getValue().getCount() < i1.getValue().getCount()) {
                    return 1;
                } else {
                    // 当两个项目出现次数一样时,需要再按ascii码排一次,保证相同支持度的项目也是有序排列的
                    return i2.getKey().compareTo(i1.getKey());
                }
            });
            // 从头指针表尾开始
            for (Map.Entry<String, HeadPointer> entry : headPointerList) {
                // 添加频繁项集(需要深复制一个新的List)
                List<String> newFrequentItemSet = new ArrayList<>(preFrequentItemSet);
                newFrequentItemSet.add(entry.getKey());
                addFrequentItemSet(newFrequentItemSet);
                // 获取条件模式基
                List<ConditionalPatternBase> conditionalPatternBases = getConditionalPatternBases(entry.getValue());
                // 创建fp树(将条件模式基集合作为新的数据集)
                Map<String, HeadPointer> nextHeadPointerTable = new HashMap<>();
                TreeNode root = new TreeNode();
                epoch(conditionalPatternBases, nextHeadPointerTable, root);
                // 递归获取频繁项集
                collectFrequentItemSet(nextHeadPointerTable, newFrequentItemSet);
            }
        }
    
        /**
         * 获取条件模式基集合
         *
         * @param ptr 头指针
         * @return 条件模式基集合
         */
        private static List<ConditionalPatternBase> getConditionalPatternBases(HeadPointer ptr) {
            List<ConditionalPatternBase> conditionalPatternBases = new ArrayList<>();
            // 遍历同项目链表
            TreeNode currentNode = ptr.getHead();
            while (currentNode != null) {
                // 获取从根节点到该节点的路径
                List<String> record = new ArrayList<>();
                TreeNode leafNode = currentNode;
                // 创建条件模式基
                ConditionalPatternBase cpb = new ConditionalPatternBase(leafNode.getCount());
                // 条件模式基不包括该节点
                leafNode = leafNode.getParent();
                while (leafNode.getItem() != null) {
                    record.add(leafNode.getItem());
                    leafNode = leafNode.getParent();
                }
                currentNode = currentNode.getNextSameItemNode();
                // 添加路径记录
                cpb.setRecord(record);
                conditionalPatternBases.add(cpb);
            }
    
            return conditionalPatternBases;
        }
    
        /**
         * 添加频繁项集
         *
         * @param frequentItemSet 频繁项集
         */
        private static void addFrequentItemSet(List<String> frequentItemSet) {
            // 要是频繁 k 项集没有实例化Set,实例化Set
            Set<List<String>> set = FREQUENT_ITEM_SET_TABLE.computeIfAbsent(frequentItemSet.size(), k -> new HashSet<>());
            set.add(frequentItemSet);
        }
    
        /**
         * 修剪数据集、创建头指针表以及创建fp树
         *
         * @param dataset          数据集
         * @param headPointerTable 头指针表
         * @param root             fp树根节点
         */
        private static void epoch(List<ConditionalPatternBase> dataset, Map<String, HeadPointer> headPointerTable, TreeNode root) {
            // 创建头指针表
            createHeadPointerTable(dataset, headPointerTable);
            // 对数据集进行枝剪和排序
            pruningAndSort(dataset, headPointerTable);
            // 创建fp树
            crateFPTree(dataset, headPointerTable, root);
        }
    
        /**
         * 加载数据
         *
         * @param filePath 文件路径
         */
        private static List<ConditionalPatternBase> loadData(String filePath) {
            Scanner scanner;
            List<ConditionalPatternBase> dataset = new ArrayList<>();
            try {
                scanner = new Scanner(new File(filePath));
                while (scanner.hasNext()) {
                    ConditionalPatternBase record = new ConditionalPatternBase();
                    record.setRecord(new ArrayList<>(Arrays.asList(scanner.nextLine().split(" "))));
                    dataset.add(record);
                }
                scanner.close();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
    
            return dataset;
        }
    
        /**
         * 创建头指针表
         *
         * @param dataset        数据集
         * @param headPointerMap 头指针表
         */
        private static void createHeadPointerTable(List<ConditionalPatternBase> dataset, Map<String, HeadPointer> headPointerMap) {
            // 遍历数据集,记录1项集出现的次数
            for (ConditionalPatternBase record : dataset) {
                for (String item : record.getRecord()) {
                    if (headPointerMap.containsKey(item)) {
                        // 增加计数
                        headPointerMap.get(item).increase(record.getCount());
                    } else {
                        // 添加一项集表头
                        headPointerMap.put(item, new HeadPointer(record.getCount()));
                    }
                }
            }
            // 枝剪表头中小于最小出现次数的一项集
            headPointerMap.values().removeIf(value -> value.getCount() < MIN_APPEAR);
        }
    
        /**
         * 删除数据集中不满足要求的项目并且对每条记录进行降序排序
         *
         * @param dataset        数据集
         * @param headPointerMap 头指针表
         */
        private static void pruningAndSort(List<ConditionalPatternBase> dataset, Map<String, HeadPointer> headPointerMap) {
            for (ConditionalPatternBase record : dataset) {
                // 删除小于最小出现次数的项目
                record.getRecord().removeIf(item -> headPointerMap.get(item) == null);
                // 每条记录中的项目按出现次数降序排序
                //record.sort((i1, i2) -> Integer.compare(HEAD_POINTER_TABLE.get(i2).getCount(), HEAD_POINTER_TABLE.get(i1).getCount()));
                record.getRecord().sort((i1, i2) -> {
                    if (headPointerMap.get(i2).getCount() < headPointerMap.get(i1).getCount()) {
                        return -1;
                    } else if (headPointerMap.get(i2).getCount() > headPointerMap.get(i1).getCount()) {
                        return 1;
                    } else {
                        // 当两个项目出现次数一样时,需要再按ascii码排一次,保证相同支持度的项目也是有序排列的
                        return i1.compareTo(i2);
                    }
                });
            }
        }
    
        /**
         * 创建 FP 树,完善头指针表
         *
         * @param dataset        数据集
         * @param headPointerMap 头指针表
         * @param root           fp数根节点
         */
        private static void crateFPTree(List<ConditionalPatternBase> dataset, Map<String, HeadPointer> headPointerMap, TreeNode root) {
            for (ConditionalPatternBase record : dataset) {
                // 从根节点开始
                TreeNode currentNode = root;
                for (String item : record.getRecord()) {
                    TreeNode child = currentNode.getChildren().get(item);
                    // 如果该路径节点不存在,新建一个
                    if (child == null) {
                        child = new TreeNode();
                        child.setItem(item);
                        child.setParent(currentNode);
                        // 添加节点
                        currentNode.getChildren().put(item, child);
                        // 连接头指针链表
                        headPointerMap.get(item).connect(child);
                    }
                    // 增加出现次数
                    child.increase(record.getCount());
    
                    currentNode = child;
                }
            }
        }
    }
    

    五、为什么要迭代建树寻找频繁项集

      为什么要以这样的方式迭代收集频繁项集,在网上实际上没有一个比较清晰的说法,这里我说一下我的理解。按照频繁项集的概念-“频繁项集的子集一定是频繁项集”,我们可以知道,频繁k项集一定是由频繁一项集中的项目组成的,这是前提。
      我们以小票和商品作比喻来对这个过程进行解释。频繁项集说白了就是一些商品总是一起出现在小票上,所以我们认为这些商品有明显的或者隐含的关系。对于上面的例子,我们将每个项目理解为一种商品。首先在第一次扫描数据集后会把头指针表中不满足最小支持度的项目对应的表项删除,这就意味着此时头指针表中剩下的项目都是频繁一项集(满足最小支持度),也就是说这些单品卖的最火,由“频繁项集的子集一定是频繁项集”我们可以得知,卖的最火的商品组合一定是由卖的最火的这些单品组成的(比如肯德基的套餐的食品组合可能就是通过这类算法得到的),那我们获取频繁k项集为什么不从这些最火的单品(频繁一项集)开始呢?反正最火的商品组合(频繁k项集)一定包含这些最火的单品
      为了分析卖的最火的单品之一F与什么商品最容易一起出现,我们只需要从和单品F一起出现过的商品中筛选即可,而大家仔细品品,单品F的条件模式基不就是和单品F一起出现过的小票记录吗?对于F的条件模式基{A C E B, 2},我们也就很容易理解为什么F的条件模式基的记数为F节点的记数了,因为虽然单品A在所有小票中出现了8次,但与单品F一起出现了2次,所以该条件模式基的含义就是A、C、E、B与F同时出现了2次,而我们寻找与单品F有关的最火商品组合(包含F的频繁k项集),就要在A、C、E、B中找(在F的条件模式基中找)
      虽然F的条件模式基只有一个,但仍然可以推广到多个条件模式基,因为要是F有好几个节点,就代表着包含F的小票分布在FP树中的不同路径中罢了。
      综上我们把F的条件模式基作为数据集重新筛选并建成FP树的过程,其实就是找与F同时出现次数更多的单品的过程。不同的是,树中的所有项目是在F出现的情况下出现的,可以理解为条件概率,这也是为什么以条件模式基建起的数被称为条件FP树。我们建立起以F的条件模式基为基础的条件FP树。
    在这里插入图片描述
      建树之后,我们还是找条件模式基,然后继续建树,直到无法建树为止。按照代码,我们在找B的条件模式基的同时,会将{F B}作为频繁2项集进行保存,实际上,B满足最小支持度,就意味着单品B即使在与单品F一起出现的情况下仍然是火爆的,所以{F B}显然也是包含单品F的情况下最火爆的商品组合之一,依次类推,我们再次创建在这棵条件FP树中以B的条件模式基为基础的条件FP树。
    在这里插入图片描述

      按照代码,我们在找E的条件模式基的同时,会将{F B E}作为频繁3项集进行保存。E满足最小支持度,就意味着单品E即使在与商品组合{F B}一起出现的情况下仍然是火爆的,所以{F B E}显然也是包含商品组合{F B}的情况下最火爆的商品组合之一
      这样,大家就能理解收集频繁项集的实际意义了吧。所以在第一次创建FP树后,对项目N(在迭代过程中可能就是项目集了)的条件模式基进行迭代建树过程,实际上就是寻找包含项目N的频繁项集的过程

    六、总结

      抽空总结了一下fp-growth算法,如果发现了什么问题,可以评论区回复或者私信我,以及我还是比较建议大家着重看看第五段的,因为网上没几乎没有材料说明白这个问题,虽然第五段的内容只是我自己的理解,但应该还是有一定可信度的,如果大家发现了问题,也可以和我说。
      算法演示数据集参考推荐系统实践(二)FPGrowth感谢博主的辛勤付出!

    展开全文
  • 大数据环境下,传统的串行FP-Growth算法在处理海量数据时,占用内存过大、频繁项多,适用于大数据情况的PFP(parallel FP-Growth)算法存在数据量增大无法处理的缺陷。针对这些问题,提出了基于Hadoop的负载均衡数据分割FP...
  • 1. FP-Growth算法弊端 FP-Growth算法是挖掘频繁项集最常用的算法之一,其是基于迭代FP-Tree生成频繁项集的关联规则算法。此算法仅进行两次数据集扫描,递归迭代构建FP-Tree(FP条件树),当FP-Tree中只有一个单分支时...

    1. FP-Growth算法弊端

    FP-Growth算法是挖掘频繁项集最常用的算法之一,其是基于迭代FP-Tree生成频繁项集的关联规则算法。此算法仅进行两次数据集扫描,递归迭代构建FP-Tree(FP条件树),当FP-Tree中只有一个单分支时,递归迭代构建结束,最终得到频繁项集,FP-Growth算法在时间、空间复杂度和数据挖掘的效率上相比Apriori都有明显改善,对于数据量较小的数据挖掘,FP-Growth改进算法具有一定优势。

    但随着数据量呈指数级增长时,该算法存在以下问题:①如果事务数据库的数据达到海量级别,FP-Growth算法把所有事务数据中的频繁项都压缩至内存中的频繁模式树,树的高度或宽度将达到内存无法接受的规模,可能导致过程失败;②在挖掘频繁模式过程中,每次递归计算都生成一棵FP-tree,每次遍历时都会产生条件频繁模式树,并消耗大量时间和存储空间。对于大规模的数据集时,传统的Apriori算法和FP-Growth算法都是基于串行计算,其计算时间和空间复杂度较高

    2. Hadoop与MapReduce简介

    Hadoop平台是适合大数据的分布式存储和计算的平台,有2个核心组件,分别为分布式存储系统(HDFS)和分布式计算框架(MapReduce): HDFS为分布式计算存储提供底层支持,可实现超大文件的容错和存储;MapReduce是一种分布式编程模式,能够实现对大规模数据进行并行运算。

    3. MapReduce改造FP-Growth算法

    使用MapReduce改造FP-Growth算法,是采用分而治之的思想,通过负载均衡的分组策略,在Hadoop平台实现FP-Growth算法的并行化,使FP-Growth算法能适应大规模数据的处理要求,同时借助Hadoop平台在分布式处理方面的优势,从而提升计算处理能力。

    FP-Growth算法主要分为2个步骤:FP-Tree的构建和从FP-Tree中递归挖掘频繁项集;

    用MapReduce任务完成频繁项集的挖掘。其中,结合分布式缓存机制存储F_List表提高访问效率,降低I/O操作,通过负载均衡分组策略,平衡各个节点的压力,充分利用各个节点的计算能力,从而提高该算法的整体性能。

    基本思想:FP-Growth算法并行化的基本思想。首先,统计事务数据库中每个项的频繁项集F,并删除小于最小支持度的项,再将剩余的项进行降序排序,得到集合F_List;然后,通过Map过程读入事务项,按负载均衡分组策略分发到不同的Reduce节点上;接着,各节点同步 Reduce过程构造FP-Tree,并对FP-Tree进行FP-Growth挖掘得到局部频繁项集,由局部频繁项集合并成全局频繁项集;最后,由全局频繁项集得到最大频繁项集。

    FP-Growth并行化算法的输入输出和 传统的FP-Growth算法相同,输入事务集和最小支持度计数,输出所有支持度计数大于最小支持度计数阈值的频繁项集。该算法包括几个MapReduce任务、2次扫描事务数据库。

       第1阶段,挖掘事务数据库的1项频繁集。首先,从分布式文件系统中读入事务数据集,将事务数据集分成M个数据集并行分发至M个Map节点上。然后,进行第1次事务数据库扫描,在各个Map节点中并行计算每个节点上的支持度计数,根据设定的最小支持度阈值,删除小于最小支持度的项。最后,将剩余的项进行降序排序,将所有节点的结果合并得到全局频繁1项集;

    F_List全局频繁1项集挖掘模型如下图1所示。

                                                                                                             图1  基于MapReduce的并行化全局频繁1项集挖掘模型

       第2阶段,负载均衡划分F_List,得到长度为Q的均衡化分组表G_List,即将G_List中的项划分为Q组,为每一组分配一个组号gidi(1≤i≤Q),gidi对应的组记作G_Listgidi,G_Listgidi中的每一项记作αk∈G_Listgidi,1≤k≤G_Listgidi.length。这样每条事务集的组号与G_List的组号相对应

       第3阶段,并行FP-Growth进行第2次事务数据库扫描。

       Map阶段:第2次扫描事务数据库,将事务所对应的部分发送到组号为gidi的事务组DB(gidi)中,实现对事务数据库进行分组,得到一组彼此相互独立的事务组。Map函数的输入键值对<key=RowNo,value=s>,根据G_List生成一个HashMap,该函数输出键值对为<key=gidi,value = {itemi...itemj}> ,即把以组号gidi为键、事务itemi...itemj为值的键值对发送到Reduce节点。这样所有包含G_Listgidi项的事务,所对应的部分都被发送到组号为gidi的分组事务集DB(gidi)中。

       Reduce阶段:对本地事务集按接收的键值对构造局部FP-Tree,递归挖掘局部频繁项集。   频繁项集挖掘模型如下图2所示。

                                                                                                             图2  基于MapReduce的并行化频繁项集挖掘模型

       第4阶段,合并局部频繁项集生成全局频繁项集。读取HDFS文件中的局部频繁项集,得到全局支持度,再根据全局支持度进行判断,最后由全局频繁项集得到最大频繁项集。

    FP-Growth算法在Hadoop平台上实现并行化的流程见图3。

                                                                                                             图3  基于MapReduce的FP-Growth算法并行化实现模型

    以上就是使用MapReduce改造Fp-Growth算法以适应大规模数据的算法过程。

    展开全文
  • 提出一种基于FP-growth算法的大电网关键线路辨识方法。利用FP-growth算法对基于电网运行可靠性模型进行连锁故障模拟生成的连锁故障事故链集合进行数据挖掘,发掘事故链集隐藏的关联规则,辨识连锁故障发展过程中的...
  • 1.加强对Apriori 算法与FP-growth算法的理解; 2.锻炼分析问题、解决问题并动手实践的能力。 二. 实验任务 用一种你熟悉的程序设计语,实现Apriori算法与FP-growth,在数据集上比较算法的性能。 三. 实验背景 ...
  • 针对FP-Growth算法中频繁模式树的遍历低效问题,提出了一种无项头表的频繁模式增长算法。该算法利用递归回溯的方式遍历频繁模式树以求取条件模式基,解决了对同一树路径多次重复遍历的问题。从理论分析和实际挖掘...
  • FP-growth算法通俗讲解

    2020-11-29 13:29:21
    FP-growth算法是一种高效发现频繁集的方法。例如你在搜索引擎中搜索一个词,它会自从补全查询词项,该处用到了FP-growth算法,通过查看互联网上的用词来找出经常在一块出现的词。【FP(Frequent Pattern)】 FP-...
  • 基于关联规则的Apriori和FP-growth算法 一、算法/思路说明 1、 Apriori算法 Apriori算法:使用支持度来作为判断频繁项集的标准。 Apriori算法的目标是找到最大的K项频繁集。这里有两层意思,首先,要找到符合支持度...
  • FP-Growth算法实现

    2020-08-30 23:25:49
    频繁项集挖掘(二)FP-Growth算法 FP-Growth(Frequent Patterns)相比于Apriori是一种更加有效的频繁项集挖掘算法,FP-Growth算法只需要对数据库进行两次扫描,而Apriori算法对于每次产生的候选项集都会扫描一次...
  • 比较简单的一种实现方式,算法容易理解,关键在数据结构的设计。
  • 并行FP-growth算法

    2020-03-01 20:59:07
    产生原因:由于无论数据集规模大小,使用的频繁项集挖掘算法所占内存的使用和计算成本代价过大,因此产生了并行式FP-Growth算法,该算法将挖掘数据集的任务分配在多个计算机上,每个计算机相互独立并行的计算与通信...
  • 基于FP-Growth算法的P2P业务流量特征自动识别机制,李娜,何刚,本文提出一种基于FP-Growth算法的P2P业务流量特征自动识别机制,该机制将流量特征识别设计为一种正反馈结构,在识别过程中强化并扩展
  • 算法为数据挖掘之关联规则挖掘的其中一种方法,可以此方法为基本进行算法的优化操作。
  • 挖掘DBLP作者合作关系,FP-Growth算法实践 包括三个代码,一堆结果文件

空空如也

空空如也

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

fp-growth算法