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

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

    2019-08-02 22:00:30
    Usage of the module is very simple. Assuming you have some iterable of ... from fp_growth import find_frequent_itemsets for itemset in find_frequent_itemsets(transactions, minsup): print itemset
  • FP-Growth-算法 该存储库包含用于(市场篮子)数据集中规则挖掘的 FP-Growth-Algorithm 的 C/C++ 实现。 描述 主文件 - 这是驱动程序。 它从用户输入数据集、最小支持度 (0-100) 和最小置信度 (0-1) FP_TREE_GEN.c ...
  • FP-growth python 实现

    2018-12-20 22:48:06
    类似:'ascii' codec can't decode byte 0xe8 in position 0 的报错,请修改fpgrowth.py中的CreatFPtree中的下面两种: orderedItem = [v[0] for v in sorted(localD.iteritems(), key=lambda p:(p[1], -ord(p[0]))...
  • 大数据环境下,传统的串行FP-Growth算法在处理海量数据时,占用内存过大、频繁项多,适用于大数据情况的PFP(parallel FP-Growth)算法存在数据量增大无法处理的缺陷。针对这些问题,提出了基于Hadoop的负载均衡数据分割FP...
  • Fp-Growth算法通过构造一个树结构来压缩数据记录,使得挖掘频繁项集只需要扫描两次数据记录,而且该算法不需要生成候选集合,所以效率会比较高。
  • 关联规则挖掘中有几个经典算法,Apriori算法因为其效率比较低,时间复杂度很高,因此韩佳伟改进了该算法,附件是fp-growth的python实现。
  • java实现FP-Growth

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

    2017-08-11 16:49:50
    python实现FP-Growth 频繁模式算法
  • FP-growth算法是不产生候选集的关联规则挖掘算法,在许多领域中具有很高的实际应用价值。然而经典的FP-growth算法是内存驻留算法,只能处理小数据集,在面对海量数据集时显得无能为力。对经典FP-growth算法中FP-tree...
  • 本代码主要利用Python工具实现FP-growth高效发现频繁项集,简单明了,易于理解
  • 关联分析:FP-Growth算法
  • FP-growth.rar python实现版 构建Fp树,用于高效发现频繁项集。
  • 数据挖掘中关联挖掘算法比较典型的有Apriori和FP-growth算法.实验和研究证明FP-growth算法优于Apriori算法.但是针对大型数据库这两种算法都存在着较大缺陷,不仅要两次或多次扫描数据库,而且很难处理支持度和数据...
  • 通过对两个有代表性的算法Apriori和FP-Growth的剖析,说明频集模式挖掘的过程,比较有候选项集产生和无候选项集产生算法的特点,并给出FP-tree结构的构造方法以及对挖掘关联规则的影响,提出了对算法的改进方法。
  • 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算法在处理海量数据时,占用内存过大、频繁项多,适用于大数据情况的PFP(parallel FP-Growth)算法存在数据量增大无法处理的缺陷。针对这些问题,提出了基于Hadoop的负载均衡数据...
  • FP-growth发现频繁项集python实现(含数据集),结构清晰易懂
  • Algorithm-FP-growth.zip

    2019-09-17 16:51:59
    Algorithm-FP-growth.zip,一种FP-增长算法的C 实现,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
  • 基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘源程序 一、DataMiningApriori程序 用eclipse打开,把三个测试数据mushroom、accidents和T10I4D100K放置 在F:\DataMiningSample\FPmining文件夹下面,即可运行 二、...
  • fp-growth & apriori

    2018-03-27 20:52:57
    包含基本关联规则算法apriori 以及 fp-growth 的具体算法,以及具体实现,简单易懂
  • 基于FP-growth算法的数据挖掘实例研究.pdf
  • 基于FP-growth的音乐推荐算法比较研究,张嘉威,孟祥武,音乐推荐作为社会生活中的一个重要内容已经受到研究者越来越多的关注,基于协同过滤算法的音乐推荐是目前使用最为广泛的推荐算法
  • 基于《机器学习实战》中FP-Growth的代码修改形成的频繁项集挖掘函数FP_Growth(),可显示各频繁项集的支持度;同时,还包括关联规则发现函数findRules()。
  • FP-growth算法

    2017-11-20 15:10:30
    本代码是对原有代码的bug进行修改,只要修改数据就可以正常使用
  • 基于FP-Growth算法的P2P业务流量特征自动识别机制,李娜,何刚,本文提出一种基于FP-Growth算法的P2P业务流量特征自动识别机制,该机制将流量特征识别设计为一种正反馈结构,在识别过程中强化并扩展
  • 挖掘DBLP作者合作关系,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理解及应用

    2021-04-25 14:35:20
    针对餐饮订单数据进行关联规则提取,关联规则的数据量大的时候计算非常耗时,主要是在频繁项集产生的过程中,目前比较经典的两种算法分别是Apriori和Fp-growth(也是基于apriori),两种算法都尝试了,测试fp-growth...

    针对餐饮订单数据进行关联规则提取,关联规则的数据量大的时候计算非常耗时,主要是在频繁项集产生的过程中,目前比较经典的两种算法分别是Apriori和Fp-growth(也是基于apriori),两种算法都尝试了,测试fp-growth的计算速度比apriori的速度要快不少,那么显然选择fp-growth进行操作;

      FP-growth算法主要包括以下步骤(参考:https://www.cnblogs.com/pinard/p/6307064.html,解释的非常通俗易懂,非常棒):

    1. FP Tree数据结构

        为了减少I/O次数,FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分,如下图所示:

        第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数,按照次数降序排列。比如上图中B在所有10组数据中出现了8次,因此排在第一位,这部分好理解。第二部分是FP Tree,它将我们的原始数据集映射到了内存中的一颗FP树,这个FP树比较难理解,它是怎么建立的呢?这个我们后面再讲。第三部分是节点链表。所有项头表里的1项频繁集都是一个节点链表的头,它依次指向FP树中该1项频繁集出现的位置。这样做主要是方便项头表和FP Tree之间的联系查找和更新,也好理解。

        下面我们讲项头表和FP树的建立过程。

    2. 项头表的建立

        FP树的建立需要首先依赖项头表的建立。首先我们看看怎么建立项头表。

        我们第一次扫描数据,得到所有频繁一项集的的计数。然后删除支持度低于阈值的项,将1项频繁集放入项头表,并按照支持度降序排列。接着第二次也是最后一次扫描数据,将读到的原始数据剔除非频繁1项集,并按照支持度降序排列。

        上面这段话很抽象,我们用下面这个例子来具体讲解。我们有10条数据,首先第一次扫描数据并对1项集计数,我们发现O,I,L,J,P,M, N都只出现一次,支持度低于20%的阈值,因此他们不会出现在下面的项头表中。剩下的A,C,E,G,B,D,F按照支持度的大小降序排列,组成了我们的项头表。

        接着我们第二次扫描数据,对于每条数据剔除非频繁1项集,并按照支持度降序排列。比如数据项ABCEFO,里面O是非频繁1项集,因此被剔除,只剩下了ABCEF。按照支持度的顺序排序,它变成了ACEBF。其他的数据项以此类推。为什么要将原始数据集里的频繁1项数据项进行排序呢?这是为了我们后面的FP树的建立时,可以尽可能的共用祖先节点。

        通过两次扫描,项头表已经建立,排序后的数据集也已经得到了,下面我们再看看怎么建立FP树。

    3. FP Tree的建立

        有了项头表和排序后的数据集,我们就可以开始FP树的建立了。开始时FP树没有数据,建立FP树时我们一条条的读入排序后的数据集,插入FP树,插入时按照排序后的顺序,插入FP树中,排序靠前的节点是祖先节点,而靠后的是子孙节点。如果有共用的祖先,则对应的公用祖先节点计数加1。插入后,如果有新节点出现,则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,FP树的建立完成。

        似乎也很抽象,我们还是用第二节的例子来描述。

        首先,我们插入第一条数据ACEBF,如下图所示。此时FP树没有节点,因此ACEBF是一个独立的路径,所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。

        接着我们插入数据ACG,如下图所示。由于ACG和现有的FP树可以有共有的祖先节点序列AC,因此只需要增加一个新节点G,将新节点G的计数记为1。同时A和C的计数加1成为2。当然,对应的G节点的节点链表要更新

        同样的办法可以更新后面8条数据,如下8张图。由于原理类似,这里就不多文字讲解了,大家可以自己去尝试插入并进行理解对比。相信如果大家自己可以独立的插入这10条数据,那么FP树建立的过程就没有什么难度了。

     

     

     

     

     

     

     

     

     

    4. FP Tree的挖掘

        我们辛辛苦苦,终于把FP树建立起来了,那么怎么去挖掘频繁项集呢?看着这个FP树,似乎还是不知道怎么下手。下面我们讲如何从FP树里挖掘频繁项集。得到了FP树和项头表以及节点链表,我们首先要从项头表的底部项依次向上挖掘。对于项头表对应于FP树的每一项,我们要找到它的条件模式基。所谓条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。得到这个FP子树,我们将子树中每个节点的的计数设置为叶子节点的计数,并删除计数低于支持度的节点。从这个条件模式基,我们就可以递归挖掘得到频繁项集了。

        实在太抽象了,之前我看到这也是一团雾水。还是以上面的例子来讲解。我们看看先从最底下的F节点开始,我们先来寻找F节点的条件模式基,由于F在FP树中只有一个节点,因此候选就只有下图左所示的一条路径,对应{A:8,C:8,E:6,B:2, F:2}。我们接着将所有的祖先节点计数设置为叶子节点的计数,即FP子树变成{A:2,C:2,E:2,B:2, F:2}。一般我们的条件模式基可以不写叶子节点,因此最终的F的条件模式基如下图右所示。

        通过它,我们很容易得到F的频繁2项集为{A:2,F:2}, {C:2,F:2}, {E:2,F:2}, {B:2,F:2}。递归合并二项集,得到频繁三项集为{A:2,C:2,F:2},{A:2,E:2,F:2},...还有一些频繁三项集,就不写了。当然一直递归下去,最大的频繁项集为频繁5项集,为{A:2,C:2,E:2,B:2,F:2}

        F挖掘完了,我们开始挖掘D节点。D节点比F节点复杂一些,因为它有两个叶子节点,因此首先得到的FP子树如下图左。我们接着将所有的祖先节点计数设置为叶子节点的计数,即变成{A:2, C:2,E:1 G:1,D:1, D:1}此时E节点和G节点由于在条件模式基里面的支持度低于阈值,被我们删除,最终在去除低支持度节点并不包括叶子节点后D的条件模式基为{A:2, C:2}。通过它,我们很容易得到D的频繁2项集为{A:2,D:2}, {C:2,D:2}。递归合并二项集,得到频繁三项集为{A:2,C:2,D:2}。D对应的最大的频繁项集为频繁3项集。

        同样的方法可以得到B的条件模式基如下图右边,递归挖掘到B的最大频繁项集为频繁4项集{A:2, C:2, E:2,B:2}。

        继续挖掘G的频繁项集,挖掘到的G的条件模式基如下图右边,递归挖掘到G的最大频繁项集为频繁4项集{A:5, C:5, E:4,G:4}。

        E的条件模式基如下图右边,递归挖掘到E的最大频繁项集为频繁3项集{A:6, C:6, E:6}。

        C的条件模式基如下图右边,递归挖掘到C的最大频繁项集为频繁2项集{A:8, C:8}。

        至于A,由于它的条件模式基为空,因此可以不用去挖掘了。

        至此我们得到了所有的频繁项集,如果我们只是要最大的频繁K项集,从上面的分析可以看到,最大的频繁项集为5项集。包括{A:2, C:2, E:2,B:2,F:2}。

        通过上面的流程,相信大家对FP Tree的挖掘频繁项集的过程也很熟悉了。

    5. FP Tree算法归纳

        这里我们对FP Tree算法流程做一个归纳。FP Tree算法包括三步:

        1)扫描数据,得到所有频繁一项集的的计数。然后删除支持度低于阈值的项,将1项频繁集放入项头表,并按照支持度降序排列。

        2)扫描数据,将读到的原始数据剔除非频繁1项集,并按照支持度降序排列。

        3)读入排序后的数据集,插入FP树,插入时按照排序后的顺序,插入FP树中,排序靠前的节点是祖先节点,而靠后的是子孙节点。如果有共用的祖先,则对应的公用祖先节点计数加1。插入后,如果有新节点出现,则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,FP树的建立完成。

        4)从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集。

        5)如果不限制频繁项集的项数,则返回步骤4所有的频繁项集,否则只返回满足项数要求的频繁项集。

    6. FP tree算法总结

        FP Tree算法改进了Apriori算法的I/O瓶颈,巧妙的利用了树结构,这让我们想起了BIRCH聚类,BIRCH聚类也是巧妙的利用了树结构来提高算法运行速度。利用内存数据结构以空间换时间是常用的提高算法运行时间瓶颈的办法。

        在实践中,FP Tree算法是可以用于生产环境的关联算法,而Apriori算法则做为先驱,起着关联算法指明灯的作用。除了FP Tree,像GSP,CBA之类的算法都是Apriori派系的。

     

    fp-growth.py:

    # encoding: utf-8
    
    """
    fp-growth算法是一个生成频繁项集的算法,其主要利用了FP树的数据结构,
    整个生成过程只需要遍历数据集2次
    """
    from collections import defaultdict, namedtuple
    """
    collections模块中的defaultdict继承自dict,namedtuple继承自tuple
    defaultdict会构建一个类似dict的对象,该对象具有默认值
    当dict不存在的key时会报KeyError错误,调用defaultdict时遇到KeyError错误会用默认值填充
    namedtuple主要用来产生可以使用名称来访问元素的数据对象,通常用来增强代码的可读性
    """
    
    
    def find_frequent_itemsets(transactions, minimum_support, include_support=False):
        """
        挖掘频繁项集,生成频繁项集和对应支持度(频数)
        """
        items = defaultdict(lambda: 0)  # mapping from items to their supports
    
        # Load the passed-in transactions and count the support that individual
        # items have.
        for transaction in transactions:
            for item in transaction:
                items[item] += 1
    
        # Remove infrequent items from the item support dictionary.
        items = dict((item, support) for item, support in items.items()
            if support >= minimum_support)
    
        # Build our FP-tree. Before any transactions can be added to the tree, they
        # must be stripped of infrequent items and their surviving items must be
        # sorted in decreasing order of frequency.
        def clean_transaction(transaction):
            transaction = filter(lambda v: v in items, transaction)
            transaction_list = list(transaction)   # 为了防止变量在其他部分调用,这里引入临时变量transaction_list
            transaction_list.sort(key=lambda v: items[v], reverse=True)
            return transaction_list
    
        master = FPTree()
        for transaction in map(clean_transaction, transactions):
            master.add(transaction)
    
        def find_with_suffix(tree, suffix):
            for item, nodes in tree.items():
                support = sum(n.count for n in nodes)
                if support >= minimum_support and item not in suffix:
                    # New winner!
                    found_set = [item] + suffix
                    yield (found_set, support) if include_support else found_set
    
                    # Build a conditional tree and recursively search for frequent
                    # itemsets within it.
                    cond_tree = conditional_tree_from_paths(tree.prefix_paths(item))
                    for s in find_with_suffix(cond_tree, found_set):
                        yield s # pass along the good news to our caller
    
        # Search for frequent itemsets, and yield the results we find.
        for itemset in find_with_suffix(master, []):
            yield itemset
    
    class FPTree(object):
        """
        构建FP树
        所有的项必须作为字典的键或集合成员
        """
    
        Route = namedtuple('Route', 'head tail')
    
        def __init__(self):
            # The root node of the tree.
            self._root = FPNode(self, None, None)
    
            # A dictionary mapping items to the head and tail of a path of
            # "neighbors" that will hit every node containing that item.
            self._routes = {}
    
        @property
        def root(self):
            """The root node of the tree."""
            return self._root
    
        def add(self, transaction):
            """Add a transaction to the tree."""
            point = self._root
    
            for item in transaction:
                next_point = point.search(item)
                if next_point:
                    # There is already a node in this tree for the current
                    # transaction item; reuse it.
                    next_point.increment()
                else:
                    # Create a new point and add it as a child of the point we're
                    # currently looking at.
                    next_point = FPNode(self, item)
                    point.add(next_point)
    
                    # Update the route of nodes that contain this item to include
                    # our new node.
                    self._update_route(next_point)
    
                point = next_point
    
        def _update_route(self, point):
            """Add the given node to the route through all nodes for its item."""
            assert self is point.tree
    
            try:
                route = self._routes[point.item]
                route[1].neighbor = point # route[1] is the tail
                self._routes[point.item] = self.Route(route[0], point)
            except KeyError:
                # First node for this item; start a new route.
                self._routes[point.item] = self.Route(point, point)
    
        def items(self):
            """
            Generate one 2-tuples for each item represented in the tree. The first
            element of the tuple is the item itself, and the second element is a
            generator that will yield the nodes in the tree that belong to the item.
            """
            for item in self._routes.keys():
                yield (item, self.nodes(item))
    
        def nodes(self, item):
            """
            Generate the sequence of nodes that contain the given item.
            """
    
            try:
                node = self._routes[item][0]
            except KeyError:
                return
    
            while node:
                yield node
                node = node.neighbor
    
        def prefix_paths(self, item):
            """Generate the prefix paths that end with the given item."""
    
            def collect_path(node):
                path = []
                while node and not node.root:
                    path.append(node)
                    node = node.parent
                path.reverse()
                return path
    
            return (collect_path(node) for node in self.nodes(item))
    
        def inspect(self):
            print('Tree:')
            self.root.inspect(1)
    
            print('Routes:')
            for item, nodes in self.items():
                print('  %r' % item)
                for node in nodes:
                    print('    %r' % node)
    
    def conditional_tree_from_paths(paths):
        """从给定的前缀路径构建一个条件fp树."""
        tree = FPTree()
        condition_item = None
        items = set()
    
        # Import the nodes in the paths into the new tree. Only the counts of the
        # leaf notes matter; the remaining counts will be reconstructed from the
        # leaf counts.
        for path in paths:
            if condition_item is None:
                condition_item = path[-1].item
    
            point = tree.root
            for node in path:
                next_point = point.search(node.item)
                if not next_point:
                    # Add a new node to the tree.
                    items.add(node.item)
                    count = node.count if node.item == condition_item else 0
                    next_point = FPNode(tree, node.item, count)
                    point.add(next_point)
                    tree._update_route(next_point)
                point = next_point
    
        assert condition_item is not None
    
        # Calculate the counts of the non-leaf nodes.
        for path in tree.prefix_paths(condition_item):
            count = path[-1].count
            for node in reversed(path[:-1]):
                node._count += count
    
        return tree
    
    class FPNode(object):
        """FP树节点"""
    
        def __init__(self, tree, item, count=1):
            self._tree = tree
            self._item = item
            self._count = count
            self._parent = None
            self._children = {}
            self._neighbor = None
    
        def add(self, child):
            """Add the given FPNode `child` as a child of this node."""
    
            if not isinstance(child, FPNode):
                raise TypeError("Can only add other FPNodes as children")
    
            if not child.item in self._children:
                self._children[child.item] = child
                child.parent = self
    
        def search(self, item):
            """
            Check whether this node contains a child node for the given item.
            If so, that node is returned; otherwise, `None` is returned.
            """
            try:
                return self._children[item]
            except KeyError:
                return None
    
        def __contains__(self, item):
            return item in self._children
    
        @property
        def tree(self):
            """The tree in which this node appears."""
            return self._tree
    
        @property
        def item(self):
            """The item contained in this node."""
            return self._item
    
        @property
        def count(self):
            """The count associated with this node's item."""
            return self._count
    
        def increment(self):
            """Increment the count associated with this node's item."""
            if self._count is None:
                raise ValueError("Root nodes have no associated count.")
            self._count += 1
    
        @property
        def root(self):
            """True if this node is the root of a tree; false if otherwise."""
            return self._item is None and self._count is None
    
        @property
        def leaf(self):
            """True if this node is a leaf in the tree; false if otherwise."""
            return len(self._children) == 0
    
        @property
        def parent(self):
            """The node's parent"""
            return self._parent
    
        @parent.setter
        def parent(self, value):
            if value is not None and not isinstance(value, FPNode):
                raise TypeError("A node must have an FPNode as a parent.")
            if value and value.tree is not self.tree:
                raise ValueError("Cannot have a parent from another tree.")
            self._parent = value
    
        @property
        def neighbor(self):
            """
            The node's neighbor; the one with the same value that is "to the right"
            of it in the tree.
            """
            return self._neighbor
    
        @neighbor.setter
        def neighbor(self, value):
            if value is not None and not isinstance(value, FPNode):
                raise TypeError("A node must have an FPNode as a neighbor.")
            if value and value.tree is not self.tree:
                raise ValueError("Cannot have a neighbor from another tree.")
            self._neighbor = value
    
        @property
        def children(self):
            """The nodes that are children of this node."""
            return tuple(self._children.itervalues())
    
        def inspect(self, depth=0):
            print(('  ' * depth) + repr(self))
            for child in self.children:
                child.inspect(depth + 1)
    
        def __repr__(self):
            if self.root:
                return "<%s (root)>" % type(self).__name__
            return "<%s %r (%r)>" % (type(self).__name__, self.item, self.count)
    # 主函数:
    def generate_association_rules(patterns, total, min_confidence):
        """
        生成关联规则,计算支持度、置信度和提升度
        """
        antecedent_list = []
        consequent_list = []
    
        support_list = []
        confidence_list = []
        lift_list = []
    
        count_antecedent = []
        p_antecedent = []
        count_consequent = []
        p_consequent = []
        count_ant_con = []
    
        num = len(patterns)
        for idx, itemset in enumerate(patterns.keys(), 1):
            print('总共有{}个频繁项集,开始处理第{}个频繁项集'.format(num, idx))
            upper_support = patterns[itemset]  # A & B
    
            for i in range(1, len(itemset)):
                for antecedent in itertools.combinations(itemset, i):
                    """
                    itertools.combinations()用于创建一个迭代器,
                    返回iterable中所有长度为r的子序列,
                    返回的子序列中的项按输入iterable中的顺序排序
                    """
                    antecedent = tuple(sorted(antecedent))
                    consequent = tuple(sorted(set(itemset) - set(antecedent)))
    
                    if antecedent in patterns and consequent in patterns:
                        lower_support = patterns[antecedent]  # A
                        consequent_support = patterns[consequent]  # B
    
                        p_lower_support = lower_support / total  # P(A)
                        p_consequent_support = consequent_support / total  # P(B)
                        support = round(float(upper_support) / total, 6)  # 支持度Support = P(A & B)
                        confidence = float(upper_support) / lower_support  # 置信度Confidence = P(A & B)/ P(A)
                        lift = confidence / p_consequent_support  # 提升度Lift = ( P(A & B)/ P(A) ) / P(B) = P(A & B)/ P(A) / P(B)
    
                        if confidence >= min_confidence:
                            antecedent_list.append(list(antecedent))
                            consequent_list.append(list(consequent))
                            support_list.append(support)
                            confidence_list.append(confidence)
                            lift_list.append(lift)
    
                            count_antecedent.append(lower_support)  # count(A)
                            p_antecedent.append(p_lower_support)  # P(A)
                            count_consequent.append(consequent_support)  # count(B)
                            p_consequent.append(p_consequent_support)  # P(B)
                            count_ant_con.append(upper_support)  # count(AB)
    
        rules_col = {'antecedent': antecedent_list,
                     'consequent': consequent_list,
                     'count_antecedent': count_antecedent,
                     'antecedent_support': p_antecedent,
                     'count_consequent': count_consequent,
                     'consequent_support': p_consequent,
                     'count_ant_con': count_ant_con,
                     'support': support_list,
                     'confidence': confidence_list,
                     'lift': lift_list}
    
        rules = pd.DataFrame(rules_col)
        #    col = ['antecedent','consequent','count_antecedent','antecedent_support',
        #           'count_consequent','consequent_support','count_ant_con','support',
        #           'confidence','lift']
        col = ['antecedent', 'consequent', 'support', 'confidence', 'lift']
        rules = rules[col]
        rules.sort_values(by=['support', 'confidence'], ascending=False, inplace=True)
        return rules
    
    
    if __name__ == '__main__':
        min_sup = 10
        min_conf = 0.8
        delta_days = -100
        df, lst = connect_mongodb_get_meituan_huitiao_task_data(delta_days)
        order_name_list_dict = get_order_dict(lst, arg=2)
        dataset = list(order_name_list_dict.values())
        total = len(dataset)
        print('总订单数:', total)
    
        '''
        find_frequent_itemsets()调用函数生成频繁项集和频数
        minimum_support表示设置最小支持度(频数),即频数大于等于minimum_support,保存此频繁项,否则删除
        include_support表示返回结果是否包含支持度(频数),若include_support=True,返回结果中包含itemset和support,否则只返回itemset
        '''
        frequent_itemsets = fpg.find_frequent_itemsets(dataset, minimum_support=min_sup, include_support=True)
    
        result = []
        for itemset, support in frequent_itemsets:  # 将generator结果存入list
            result.append((itemset, support))
    
        result = sorted(result, key=lambda i: i[0])  # 排序后输出
    
        item_list = []
        itemset_list = []
        support_list = []
        for itemset, support in result:
            #        print(str(itemset) + ' ' + str(support)) #频繁项集和出现次数
            item_list.append(itemset)  # 保存为列表,用于输出频繁项集结果
    
            itemset = tuple(sorted(itemset))  # 先转换为元组,用于后续生成关联规则
            itemset_list.append(itemset)
            support_list.append(support)
    
        # 构建字典
        patterns = dict(zip(itemset_list, support_list))
    
        # 生成关联规则,计算支持度、置信度和提升度
        # min_confidence代表最小置信度
        rules = generate_association_rules(patterns, total, min_confidence=min_conf)
        print('关联规则:\n', rules.head())
        print('结果总数:', len(rules))
    
        rules = rules[(rules.antecedent.apply(lambda x:len(x) >= 1)) & (rules.consequent.apply(lambda x:len(x) >= 1))]
    
        ## 输出结果,输出到同一份excel文件不同的工作表中
        # 输出频繁集
        sup = {'item_id': item_list, 'frequency': support_list}
        sup = pd.DataFrame(sup)
        sup['support'] = round(sup['frequency'] / float(total), 6)
        sup.sort_values(by=['support'], ascending=False, inplace=True)
        sup_col = ['item_id', 'frequency', 'support']
        sup = sup[sup_col]
    
        print(type(rules))
        writer = pd.ExcelWriter('tmp_data/fp-growth-result.xlsx')
        print(type(writer))
        sup.to_excel(excel_writer=writer, sheet_name='support', encoding="utf-8", index=False)
        # 输出关联规则
        rules.to_excel(excel_writer=writer, sheet_name='rules', encoding="utf-8", index=False)
        writer.save()
        writer.close()
    
        # sup.to_csv('tmp_data/fp-sup.txt', index=None)
        # rules.to_csv('tmp_data/fp-rules.txt', index=None)
    
        end = time.time()
        print('Running time: %s Seconds' % (end - start))

    这里面有个问题,就是使用fp算出来的结果居然和apriori算法得到的结果是不一致的(同一支持度和置信度),并且计算得到的置信度会大于1,然后最终排查出来是因为fp-growth用到的原始数据中一个事务中的物品是要删除重复商品的,切记啊

    结果:

    参考:https://zhuanlan.zhihu.com/p/76357500https://www.cnblogs.com/pinard/p/6307064.html

     

    展开全文
  • 此算法仅进行两次数据集扫描,递归迭代构建FP-Tree(FP条件树),当FP-Tree中只有一个单分支时,递归迭代构建结束,最终得到频繁项集,FP-Growth算法在时间、空间复杂度和数据挖掘的效率上相比Apriori都有明显改善,...

    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算法以适应大规模数据的算法过程。

    展开全文

空空如也

空空如也

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

FP-growth