fp_fpga - CSDN
  • FP算法

    2011-10-22 11:47:48
    Apriori算法和FPTree算法都是数据挖掘中的关联规则挖掘算法,处理的都是最简单的单层单维布尔关联规则。 转自http://blog.csdn.net/sealyao/article/details/6460578 Apriori算法 Apriori算法是一种最有影响的...

    Apriori算法和FPTree算法都是数据挖掘中的关联规则挖掘算法,处理的都是最简单的单层单维布尔关联规则。

    转自http://blog.csdn.net/sealyao/article/details/6460578

    Apriori算法

    Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。是基于这样的事实:算法使用频繁项集性质的先验知识。Apriori使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。首先,找出频繁1-项集的集合。该集合记作L1L1用于找频繁2-项集的集合L2,而L2用于找L3,如此下去,直到不能找到频繁k-项集。找每个Lk需要一次数据库扫描。

    这个算法的思路,简单的说就是如果集合I不是频繁项集,那么所有包含集合I的更大的集合也不可能是频繁项集。

    算法原始数据如下:

    TID

    List of item_ID’s

    T100

    T200

    T300

    T400

    T500

    T600

    T700

    T800

    T900

    I1,I2,I5

    I2,I4

    I2,I3

    I1,I2,I4

    I1,I3

    I2,I3

    I1,I3

    I1,I2,I3,I5

    I1,I2,I3

    算法的基本过程如下图:

    image

    首先扫描所有事务,得到1-项集C1,根据支持度要求滤去不满足条件项集,得到频繁1-项集。

    下面进行递归运算:

    已知频繁k-项集(频繁1-项集已知),根据频繁k-项集中的项,连接得到所有可能的K+1_项,并进行剪枝(如果该k+1_项集的所有k项子集不都能满足支持度条件,那么该k+1_项集被剪掉),得到clip_image002项集,然后滤去该clip_image002[1]项集中不满足支持度条件的项得到频繁k+1-项集。如果得到的clip_image002[2]项集为空,则算法结束。

    连接的方法:假设clip_image004项集中的所有项都是按照相同的顺序排列的,那么如果clip_image004[1][i]和clip_image004[2][j]中的前k-1项都是完全相同的,而第k项不同,则clip_image004[3][i]和clip_image004[4][j]是可连接的。比如clip_image006中的{I1,I2}和{I1,I3}就是可连接的,连接之后得到{I1,I2,I3},但是{I1,I2}和{I2,I3}是不可连接的,否则将导致项集中出现重复项。

    关于剪枝再举例说明一下,如在由clip_image006[1]生成clip_image008的过程中,列举得到的3_项集包括{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5},但是由于{I3,I4}和{I4,I5}没有出现在clip_image006[2]中,所以{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。

    海量数据下,Apriori算法的时空复杂度都不容忽视。

    空间复杂度:如果clip_image010数量达到clip_image012的量级,那么clip_image014中的候选项将达到clip_image016的量级。

    时间复杂度:每计算一次clip_image018就需要扫描一遍数据库。

    FP-Tree算法

    FPTree算法:在不生成候选项的情况下,完成Apriori算法的功能。

    FPTree算法的基本数据结构,包含一个一棵FP树和一个项头表,每个项通过一个结点链指向它在树中出现的位置。基本结构如下所示。需要注意的是项头表需要按照支持度递减排序,在FPTree中高支持度的节点只能是低支持度节点的祖先节点。

    image

    另外还要交代一下FPTree算法中几个基本的概念:

    FP-Tree:就是上面的那棵树,是把事务数据表中的各个事务数据项按照支持度排序后,把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中,同时在每个结点处记录该结点出现的支持度。

    条件模式基:包含FP-Tree中与后缀模式一起出现的前缀路径的集合。也就是同一个频繁项在PF树中的所有节点的祖先路径的集合。比如I3在FP树中一共出现了3次,其祖先路径分别是{I2,I1:2(频度为2)},{I2:2}和{I1:2}。这3个祖先路径的集合就是频繁项I3的条件模式基。

    条件树:将条件模式基按照FP-Tree的构造原则形成的一个新的FP-Tree。比如上图中I3的条件树就是:

    image

     

    1、 构造项头表:扫描数据库一遍,得到频繁项的集合F和每个频繁项的支持度。把F按支持度递降排序,记为L。

    2、 构造原始FPTree:把数据库中每个事物的频繁项按照L中的顺序进行重排。并按照重排之后的顺序把每个事物的每个频繁项插入以null为根的FPTree中。如果插入时频繁项节点已经存在了,则把该频繁项节点支持度加1;如果该节点不存在,则创建支持度为1的节点,并把该节点链接到项头表中。

    3、 调用FP-growth(Tree,null)开始进行挖掘。伪代码如下:

    procedure FP_growth(Treea)

    if Tree 含单个路径then{

             for 路径P中结点的每个组合(记作b

             产生模式b U a,其支持度support = 中结点的最小支持度;

    } else {

             for each i 在Tree的头部(按照支持度由低到高顺序进行扫描){

                      产生一个模式b = i U a,其支持度support .support

                      构造b的条件模式基,然后构造b的条件FP-树Treeb;

                      if Treeb 不为空 then

                                调用 FP_growth (Treeb, b);

               }

    }

    FP-growth是整个算法的核心,再多啰嗦几句。

    FP-growth函数的输入:tree是指原始的FPTree或者是某个模式的条件FPTree,a是指模式的后缀(在第一次调用时a=NULL,在之后的递归调用中a是模式后缀)

    FP-growth函数的输出:在递归调用过程中输出所有的模式及其支持度(比如{I1,I2,I3}的支持度为2)。每一次调用FP_growth输出结果的模式中一定包含FP_growth函数输入的模式后缀。

    我们来模拟一下FP-growth的执行过程。

    1、 在FP-growth递归调用的第一层,模式前后a=NULL,得到的其实就是频繁1-项集。

    2、 对每一个频繁1-项,进行递归调用FP-growth()获得多元频繁项集。

    下面举两个例子说明FP-growth的执行过程。

    1、I5的条件模式基是(I2 I1:1), (I2 I1 I3:1),I5构造得到的条件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}。

    绘图1

    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}

          image         绘图2




                                             图1                                                                     图2

     

    根据FP-growth算法,最终得到的支持度>2频繁模式如下:

    item

    条件模式基

    条件FP-树

    产生的频繁模式

    I5

    I4

    I3

    I1

    {(I2 I1:1),(I2 I1 I3:1)

    {(I2 I1:1), (I2:1)}

    {(I2 I1:2), (I2:2), (I1:2)}

    {(I2:4)}

    <I2:2, I1:2>

    <I2:2>

    <I2:4, I1:2>, <I1:2>

    <I2:4>

    I2 I5:2, I1 I5:2, I2 I1 I5:2

    I2 I4:2

    I2 I3:4, I1 I3:4, I2 I1 I3:2

    I2 I1:4

    FP-growth算法比Apriori算法快一个数量级,在空间复杂度方面也比Apriori也有数量级级别的优化。但是对于海量数据,FP-growth的时空复杂度仍然很高,可以采用的改进方法包括数据库划分,数据采样等等。

    展开全文
  • FP-growth算法,fpgrowth算法详解 使用FP-growth算法来高效发现频繁项集 前言 你用过搜索引擎挥发现这样一个功能:输入一个单词或者单词的一部分,搜索引擎酒会自动补全查询词项,用户甚至实现都不知道搜索引擎...

    FP-growth算法,fpgrowth算法详解


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

    前言

    你用过搜索引擎挥发现这样一个功能:输入一个单词或者单词的一部分,搜索引擎酒会自动补全查询词项,用户甚至实现都不知道搜索引擎推荐的东西是否存在,反而会去查找推荐词项,比如在百度输入“为什么”开始查询时,会出现诸如“为什么我有了变身器却不能变身奥特曼”之类滑稽的推荐结果,为了给出这些推荐查询慈祥,搜索引擎公司的研究人员使用了本文要介绍的一个算法,他们通过查看互联网上的用词来找出经常在一块出现的词对,这需要一种高效发现频繁集的方法。该算法称作FP-growth,又称为FP-增长算法,它比Apriori算法要快,它基于Apriori构建,但在完成相同任务时采用了一些不同的技术。不同于Apriori算法的”产生-测试”,这里的任务是将数据集存储在一个特定的称做FP树的结构之后发现频繁项集或者频繁项对,即常在一块出现的元素项的集合FP树,这种做法是的算法的执行速度要快于apriori,通常性能要好两个数量级以上。

    FP树表示法

    FP树时一种输入数据的压缩表示,它通过逐个读入事务,并把事务映射到FP树中的一条路径来构造,由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠越多,使用FP树结构获得的压缩效果越好,如果FP树足够小,能够存放在内存中,就可以直接从这个内存中的结构提取频繁项集,而不必重复地扫描存放在硬盘上的数据。

    下图显示了一个数据集,它包含10个事务和5个项。(可以把一条事务都直观理解为超市的顾客购物记录,我们利用算法来发掘那些物品或物品组合频繁的被顾客所购买。)

    图1

    下图绘制了读入三个事务之后的FP树的结构以及最终完成构建的FP树,初始,FP树仅包含一个根节点,用符号null标记,随后,用如下方法扩充FP树:

    图1
    图2
    图3
    图4

    通常,FP树的大小比未压缩的数据小,因为购物篮数据的事务常常共享一些共同项,在最好的情况下,所有的事务都具有相同的项集,FP树只包含一条节点路径,当每个事务都具有唯一项集时,导致最坏情况发生,由于事务不包含任何共同项,FP树的大小实际上与原数据的大小一样,然而,由于需要附加的空间为每个项存放节点间的指针和技术,FP树的存储需求增大。

    FP树还包含一个连接具有相同项的节点的指针列表,这些指针再上图中用虚线表示,有助于快速访问树中的项。

    FP增长算法的频繁项集产生

    FP-growth是一种以自底向上方式探索树,由FP树产生频繁项集的算法,给定上面构建的FP树,算法首先查找以e结尾的频繁项集,接下来是b,c,d,最后是a,由于每一个事务都映射到FP树中的一条路径,因为通过仅考察包含特定节点(例如e)的路径,就可以发现以e结尾的频繁项集,使用与节点e相关联的指针,可以快速访问这些路径,下图显示了所提取的路径,后面详细解释如何处理这些路径,以得到频繁项集。

    图五
    图六
    图七
    图八
    图九

    上面的图演示了讲频繁项集产生的问题分解成多个子问题,其中每个子问题分别涉及发现以e,d,c,b和a结尾的频繁项集

    发现以e结尾的频繁项集之后,算法通过处理与节点d相关联的路径,进一步寻找以d为结尾的频繁项集,继续该过程,直到处理了所有与节点c,b和a相关联的路径为止,上面的图分别显示了这些项的路径,而他们对应的频繁项集汇总在下表中

    图十

    FP增长采用分治策略将一个问题分解为较小的子问题,从而发现以某个特定后缀结尾的所有频繁项集。例如,假设对发现所有以e结尾的频繁项集感兴趣,为了实现这个目的,必须首先检查项集{e}本身是否频繁,如果它是平凡的,则考虑发现以de结尾的频繁项集子问题,接下来是ce和ae,依次,每一个子问题可以进一步划分为更小的子问题,通过合并这些子问题的结果,就可以找到所有以e结尾的频繁项集,这种分治策略是FP增长算法采用的关键策略。

    为了更具体地说明如何解决这些子问题,考虑发现所有以e结尾的频繁项集的任务。

    图十一
    图十二
    图十三
    图十四
    图十五
    图十六

    这个例子解释了FP增长算法中使用的分治方法,每一次递归,都要通过更新前缀路径中的支持度计数和删除非频繁的项来构建条件FP树,由于子问题时不相交的,因此FP增长不会产生任何重复的项集,此外,与节点相关联的支持度计数允许算法在产生相同的后缀项时进行支持度计数。

    FP增长是一个有趣的算法,它展示了如何使用事务数据集的压缩表示来有效的产生频繁项集,此外对于某些事务数据集,FP增长算法比标准的Apriori算法要快几个数量级,FP增长算法的运行性能取决于数据集的“压缩因子”。如果生成的FP树非常茂盛(在最坏的情况下,是一颗完全二叉树)则算法的性能显著下降,因为算法必须产生大量的子问题,并且需要合并每个子问题返回的结果

    展开全文
  • FP成功命令

    2015-09-28 11:19:01
    fp init fp data create OffsetBase=PacketStart offset=0 length=4 fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=none mpls=any fp qset add data 1

    ok
    fp init
    fp data create OffsetBase=PacketStart offset=0 length=4
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=none mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x99887766 0xffffffff
    fp action add 1 drop
    fp entry install 1


    ok


    fp init
    fp data create OffsetBase=PacketStart offset=19 length=3
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=any mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x123456 0xffffff
    fp action add 1 drop
    fp entry install 1


    ok

    fp init
    fp data create OffsetBase=PacketStart offset=4 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=none mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x0016 0xffff
    fp action add 1 drop
    fp entry install 1

    ok
    fp init
    fp data create OffsetBase=PacketStart offset=10 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=none mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x0001 0xffff
    fp action add 1 drop
    fp entry install 1


    识别 0x0800 
    OK

    fp init
    fp data create OffsetBase=PacketStart offset=12 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=none mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x0800 0xffff
    fp action add 1 drop
    fp entry install 1


    识别 vlan 0x8100 
    OK

    fp init
    fp data create OffsetBase=PacketStart offset=12 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any


    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x8100 0xffff
    fp action add 1 drop
    fp entry install 1

    识别特定VLAN ID


    这个行 匹配 0x0015
    fp init
    fp data create OffsetBase=PacketStart offset=14 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any

    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x0015 0xffff
    fp action add 1 drop
    fp entry install 1


    这个 匹配 0x15  也可以
    fp init
    fp data create OffsetBase=PacketStart offset=15 length=1
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any


    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x15 0xff
    fp action add 1 drop
    fp entry install 1


    识别 mpls 0x8847 


    OK


    带VLAN
    fp init
    fp data create OffsetBase=PacketStart offset=16 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x8847 0xffff
    fp action add 1 drop
    fp entry install 1


    不带VLAN


    fp init
    fp data create OffsetBase=PacketStart offset=12 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x8847 0xffff
    fp action add 1 drop
    fp entry install 1






    将mpls报文重定向到某个端口


    重定向失败
    fp init




    fp data create OffsetBase=PacketStart offset=16 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 3
    fp group create 0 2
    fp entry create 2 6
    fp qual 6 data 3 0x8847 0xffff
    fp action add 6 RedirectPbmp  0x10
    fp entry install 5




    将mpls报文映像到某个端口 


    带VLAN  ok


    fp init
    fp data create OffsetBase=PacketStart offset=16 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 data 1 0x8847 0xffff


    fp action add 1 MirrorIngress  0 4
    fp entry install 0




    不带VLAN  ok
    fp init
    fp data create OffsetBase=PacketStart offset=12 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 data 1 0x8847 0xffff


    fp action add 1 MirrorIngress  0 4  // 这句用函数代替
    fp entry install 0




    OK 
    fp init
    fp data create OffsetBase=PacketStart offset=20 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x1040  0xffff
    fp action add 1 drop
    fp entry install 1






    重定向
    fp init
    fp data create OffsetBase=PacketStart offset=20 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x1040  0xffff
    fp action add 1 RedirectPbmp  0x4000
    fp entry install 1


    fp init
    fp data create OffsetBase=PacketStart offset=20 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp group create 0 1
    fp entry create 1 1
    fp qual 1 data 1 0x1040  0xffff
    fp action add 1 RedirectPort  0 14  [提示输入错误]
    fp entry install 1


    old 重定向
     OK


    fp qset add ethertype
    fp qset add inport
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inport 0 ge9
    fp qual 0 ethertype 0x8847 0xffff
    fp action add 0 RedirectPort 0 4
    fp entry install 0


    将MPLS报文重定向到某个端口
    不带VLAN
    fp init
    fp data create OffsetBase=PacketStart offset=12 length=4
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 data 1 0x8847  0xffff


    fp action add 1 MirrorIngress  0 4  // 这句用函数代替
    fp entry install 0




    匹配第二层标签
    fp init
    fp data create OffsetBase=PacketStart offset=18 length=3
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 data 1 0x123456  0xffffff


    fp init
    fp data create OffsetBase=PacketStart offset=18 length=3
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 data 1 0x123456  0xfffff0  
    [20bit 的掩码不被允许,后面必须加0,凑成24bit ,字节整数倍]


    带VLAN


    fp init
    fp data create OffsetBase=PacketStart offset=16 length=2
    fp data format add QualId=1 RelativeOffset=0 L2=any VlanTag=any OuterIp=any InnerIp=any Tunnel=Any mpls=any
    fp qset add data 1
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 data 1 0x8847 0xffff


    fp action add 1 MirrorIngress  0 4  // 这句用函数代替
    fp entry install 0






    入口映像 【老的ACL】
    fp init
    fp qset add ethertype
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 ethertype 0x8847 0xffff
    fp action add 0 MirrorIngress  0 4   //  这一行有问题,无法实现预期目的
    fp entry install 0


    fp init
    fp qset add ethertype
    fp qset add inports
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inports 0x800 0x3ffffffd
    fp qual 0 ethertype 0x8847 0xffff
    fp action add 0 42  0 4
    fp entry install 0


    丢弃MPLS 报文
    OK


    fp qset add ethertype
    fp qset add inport
    fp group create 0 0
    fp entry create 0 0
    fp qual 0 inport 0 ge9
    fp qual 0 ethertype 0x8847 0xffff
    fp action add 0 Drop
    fp entry install 0

    展开全文
  • 1. FP Tree数据结构  为了减少I/O次数,FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分,如下图所示:  第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数,按...

    第一部分为我看到的一篇文章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派系的。

    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派系的。

    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派系的。

    7. FP tree算法代码详解

    import matplotlib.pyplot as plt
    import twitter
    from time import sleep
    import re
    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):#对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)#将树以文本形式显示
    
    
    def createTree(dataSet, minSup=1):  # create FP-tree from dataset but don't mine数据集和最下支持度
        headerTable = {}#建FP树都是从空集开始
        # go over dataSet twice
        for trans in dataSet:  # first pass counts frequency of occurance遍历一遍扫描数据集并统计每个元素项出现的频度
            for item in trans:
                headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
        for k in list(headerTable.keys()):  # remove items not meeting minSup,每个项中的元素是key,
            if headerTable[k] < minSup:#移除小于最小支持度的项
                del (headerTable[k])
        freqItemSet = set(headerTable.keys())#set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集、差集、并集等。
        # print 'freqItemSet: ',freqItemSet
        if len(freqItemSet) == 0: return None, None  # if no items meet min support -->get out  #如果频繁项集为空,则退出
        for k in headerTable: #扩展头指针表,每个项中的元素是key,第一个元素保存计数,第二个元素指向第一个元素项
            # 字典值中添加每个元素的指针,初始化为None
            #FP - growth算法还需要一个称为头指针表的数据结构,
            #其实很简单,就是用来记录各个元素项的总出现次数的数组,再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表
            headerTable[k] = [headerTable[k], None]  # reformat headerTable to use Node link
        # print 'headerTable: ',headerTable
        retTree = treeNode('Null Set', 1, None)  # create tree开始构建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, retTree, headerTable, count)  # populate tree with ordered freq itemset
        return retTree, headerTable  # return tree and header table
    
       #更新节点
       #items是处理过后的只含频繁元素的按频度排序的一组数据
        #inTree是要更新的节点,count是此组数据的频度
    def updateTree(items, inTree, headerTable, count):
        #每次循环都只测试第一个元素项是否作在原来的树中,以下程序都只是针对第一个元素的
        #因为每次第一个元素处理完之后,都调用后面的updateHeader(去除第一个元素函数),
        # 所以每次循环相当于遍历items中的每个元素
        if items[0] in inTree.children:  # check if orderedItems[0] in retTree.children
            inTree.children[items[0]].inc(count)  # incrament count如果该子节点存在,则更新该元素的计数,如果不存在,则创建一个新的treeNode,并将其作为子节点添加到树中
        else:  # add items[0] to inTree.children#否则生成子节点并更新头指针表
            inTree.children[items[0]] = treeNode(items[0], count, inTree)#判断inTree的孩子节点中没有第一个项,那么创建一个子节点,
            # 输入是第一个项,第一个项的数和第一个项的父节点
            if headerTable[items[0]][1] == None:  # update header table #如果添加的元素的没有指向它的指针,headerTable[items[0]][1]存储的是指向items[0]的指针
                # 也就是每一个元素都有一个指向它的指针,对于重合的元素,会从上一个同样的元素指向这儿
                headerTable[items[0]][1] = inTree.children[items[0]]#便将树中的元素存到指向它元素的位置
            else:#去掉第一个元素
                updateHeader(headerTable[items[0]][1], inTree.children[items[0]])#更新头指针
        if len(items) > 1:  # call updateTree() with remaining ordered items
            updateTree(items[1::], inTree.children[items[0]], headerTable, count)#去掉第一个元素
    
    
    
    
    #确保节点链接指向树中该元素项的每一个实例
    #更新头指针表
    def updateHeader(nodeToTest, targetNode):  # this version does not use recursion
        # 指针一路向下,直到最末尾
        while (nodeToTest.nodeLink != None):  # Do not use recursion to traverse a linked list!
            nodeToTest = nodeToTest.nodeLink
            # 将目标节点接在最末尾
        nodeToTest.nodeLink = targetNode
    
    
    def loadSimpDat():
        simpDat = [['r', 'z', 'h', 'j', 'p'],
                   ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
                   ['z'],
                   ['r', 'x', 'n', 'o', 's'],
                   ['y', 'r', 'x', 'z', 'q', 't', 'p'],
                   ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
        return simpDat
    
    
    def createInitSet(dataSet):#对数据进行标记
        retDict = {}
        for trans in dataSet:
            retDict[frozenset(trans)] = retDict.get([frozenset(trans)], 0) + 1
        return retDict
    
    
    #从leafNode节点一路向上开始找它的前缀路径
    #为给定元素项生成一个条件模式基
    def ascendTree(leafNode, prefixPath):  # ascends from leaf node to root
        if leafNode.parent != None:
            prefixPath.append(leafNode.name)
            ascendTree(leafNode.parent, prefixPath)
    
    #找treeNode及其相似节点的前缀路径集合即条件模式基并存入返回
    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
    
    #挖掘FP树中的频繁项集,minSup为阈值,和之前的阈值不一样
    #prefix为当前的前缀,freqItemList用来记录频繁项集
    def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
        # 首先将头指针表中的频繁元素从小到大排序
        bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]  # (sort header table)
        # 遍历每个频繁元素
        for basePat in bigL:  # start from bottom of header table
            # newFreqSet记录加了当前节点的前缀
            newFreqSet = preFix.copy()
            newFreqSet.add(basePat)
            # print 'finalFrequent Item: ',newFreqSet    #append to set
            # 将当前前缀加入到频繁项集列表中
            freqItemList.append(newFreqSet)
            # 求当前元素的前缀路径集及条件模式基
            condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
            # print 'condPattBases :',basePat, condPattBases
            # 2. construct cond FP-tree from cond. pattern base
            # 对此条件模式基构造FP树
            myCondTree, myHead = createTree(condPattBases, minSup)
    
            # print 'head from conditional tree: ', myHead
            # 若树不为空,即此条件模式基中含有频繁元素
            # 则递归地挖掘此FP树中的频繁项集
            if myHead != None:  # 3. mine cond. FP-tree
                print ('conditional tree for: ',newFreqSet)
                myCondTree.disp(1)
                mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
    
    

    命令行:

    import fpGrowth
    rootNode=fpGrowth.treeNode('pyramid',9,None)
    rootNode.children['eye']=fpGrowth.treeNode('eye',13,None)
    #rootNode.disp()
    rootNode.children['phoenix']=fpGrowth.treeNode('phoenix',3,None)
    #rootNode.disp()
    simpDat=fpGrowth.loadSimpDat()
    initSet=fpGrowth.createInitSet(simpDat)
    myFPtree,myHeaderTab=fpGrowth.createTree(initSet,3)
    #myFPtree.disp()
    #print(fpGrowth.findPrefixPath('x',myHeaderTab['x'][1]))
    #print(fpGrowth.findPrefixPath('z',myHeaderTab['z'][1]))
    #print(fpGrowth.findPrefixPath('r',myHeaderTab['r'][1]))
    freqItems=[]
    fpGrowth.mineTree(myFPtree,myHeaderTab,3,set([]),freqItems)
    parseDat=[line.split for line in open('kosarak.dat').readlines()]
    initSet=fpGrowth.createInitSet(parseDat)
    myFPtree,myHeaderTab=fpGrowth.createTree(initSet,100000)
    myFreqList=[]
    fpGrowth.mineTree(myFPtree,myHeaderTab,100000,set([]),myFreqList)

    最后一个从新闻网站中点击流中挖掘,在retDict[frozenset(trans)] = retDict.get([frozenset(trans)], 0) + 1出现不可哈西状况,还未解决,有解决的小伙伴可以留言哦!

    展开全文
  • fp16与fp32简介与试验

    2020-05-02 01:53:36
    一、fp16和fp32介绍 fp16是指采用2字节(16位)进行编码存储的一种数据类型;同理fp32是指采用4字节(32位); 如上图,fp16第一位表示+-符号,接着5位表示指数,最后10位表示分数; 公式: 其中,sign位...

     

    目录

    一、fp16和fp32介绍

    二、为什么应用fp16训练:

    三、应用fp16存在问题

    四、实践对比

    引用:


    一、fp16和fp32介绍

    • fp16是指采用2字节(16位)进行编码存储的一种数据类型;同理fp32是指采用4字节(32位);

    • 如上图,fp16第一位表示+-符号,接着5位表示指数,最后10位表示分数;
      • 公式:

      • 其中,sign位表示正负,exponent位表示指数(  ),fraction位表示的是分数(  )。其中当指数为零的时候,下图加号左边为0,其他情况为1。
      • 具体计算情况可分为下面三种:

      • Exp:

      • 所以可以计算出,fp16值动态区间:精度其实为

         

         

      • fp32值动态区间:

    二、为什么应用fp16训练:

    • fp16和fp32相比对训练的优化:
      • 1.内存占用减少:很明显,应用fp16内存占用比原来更小,可以设置更大的batch_size
      • 2.加速计算:加速计算只在最近的一些新gpu中,这一块我还没有体验到好处...有论文指出fp16训练速度可以是fp32的2-8倍

    三、应用fp16存在问题

    • 由于fp16的值区间比fp32的值区间小很多,所以在计算过程中很容易出现上溢出(Overflow,>65504 )和下溢出(Underflow,<6x10^-8  )的错误,溢出之后就会出现“Nan”的问题
    • 借用别人例子:

    • 解决办法:
      • 1.混合精度加速:简单的讲就是使用fp16进行乘法和存储,只使用fp32进行加法操作,避免累加误差;
      • 2.损失放大化:
        • 反向传播前,将损失变化(dLoss)手动增大  倍,因此反向传播时得到的中间变量(激活函数梯度)则不会溢出;
        • 反向传播后,将权重梯度缩  倍,恢复正常值。

    四、实践对比

    实践代码:

    from apex import amp
    model, optimizer = amp.initialize(model, optimizer, opt_level="O1") # 这里是“欧一”,不是“零一”
    with amp.scale_loss(loss, optimizer) as scaled_loss:
        scaled_loss.backward()
    • 这里我直接应用fairseq代码的fp16参数:gpu用1080Ti简单试验了下
      • fp16:

      • fp32:

      • 总结:1080Ti应用fp16确实可以省内存,但是理论上是不能加速的啊,这里小朋友有比较多问号???
    • 混合精度加速,需要用到 Volta 结构的GPU,只有V100 和 TITAN V 系列是支持 TensorCore 加速计算

    引用:

     

    展开全文
  • fp

    2020-06-18 19:32:37
  •   首先这几个术语会高频率得出现在论文的实验部分,它是对实验结果的描述,首先我想先解释这几个缩写的含义: precesion:查准率,即在检索后返回的结果中,真正正确的个数占整个结果的比例。...
  • FP-growth 算法 介绍   打开你的搜索引擎,输入一个单词或一部分,例如“我”,搜索引擎可能会去统计和“我”一块出现得多的词,然后返回给你。其实就是去找频繁项集,而且需要相当地高效,像Apriori那样的...
  • 深入剖析FP-Growth原理

    2019-04-21 18:40:52
    同步更新公众号:海涛技术漫谈 频繁项挖掘广泛的应用于寻找关联的事物。最经典的就是,电商企业通过分析用户的...接下来介绍并行FP-Growth算法怎么通过3次map-reduce实现了并行化。最后通过分析spark mlib包中PF...
  • FP-growth算法理解 FP-growth(Frequent Pattern Tree, 频繁模式树),是韩家炜老师提出的挖掘频繁项集的方法,是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或频繁项对,即常在一块出现的元素项的集合FP...
  • fp16和fp32

    2019-10-07 13:23:24
    1)TensorRT的FP16与FP32相比能有接近一倍的速度提升168,前提是GPU支持FP16(如最新的2070,2080,2080ti等) 2)减少显存。 缺点: 1) 会造成溢出 因此,在日常使用过程中,常使用双混合精度训练。如图: ...
  • Python实现FP

    2019-04-27 11:12:41
    FP树是用来挖掘最大频繁k项集的一种数据结构,相对来说难度较大,因为在前辈们的博客中,对于FP树的实现讲的是比较清楚了,但是对于FP的编程思路却提的很少。在这里做一个简单的梳理。 FP树的基础知识 首先请花...
  • FP-Growth算法的介绍

    2017-05-16 14:18:12
    引言:在关联分析中,频繁项集的挖掘最常用到的就是Apriori算法。Apriori算法是一种先产生候...它的思路是把数据集中的事务映射到一棵FP-Tree上面,再根据这棵树找出频繁项集。FP-Tree的构建过程只需要扫描两次数据集。
  • 数据挖掘进阶之关联规则挖掘FP-Growth算法 绪 近期在写论文方面涉及到了数据挖掘,需要通过数据挖掘方法实现软件与用户间交互模式的获取、分析与分类研究。主要涉及到关联规则与序列模式挖掘两块。关联规则挖掘使用...
  •     FP增长(FP-growth)算法是一种高效发现频繁项集的方法,只需要对数据库进行两次扫描。它基于Apriori构建,但在完成相同任务时采用了一些不同的技术。该算法虽然能更为高效地发现频繁项集,但不能用于发现...
  • FP-Tree算法 FPTree算法:在不生成候选项的情况下,完成Apriori算法的功能。 FPTree算法的基本数据结构,包含一个一棵FP树和一个项头表,每个项通过一个结点链指向它在树中出现的位置。基本结构如下所示。需要...
  • FP-growth算法基于Apriori构建,但采用了高级的数据结构减少扫描次数,大大加快了算法速度。FP-growth算法只需要对数据库进行两次扫描,而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁,...
  • FP Tree算法原理

    2019-06-17 10:00:59
    为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。 1. FP Tree数据结构 为了减少 I/O ...
  • 今天看NVIDIA的帕斯卡架构介绍时,看到了fp16浮点数格式,以前没见过,想弄清楚他的格式和表示范围,几经查找,终于搞懂了。主要参考:fp16-wiki  如图,一个fp16数据占据两个字节,其中1位符号位,5位指数位,10...
  • 基于Apriori、FP-Growth及Eclat算法的频繁模式挖掘源程序 一、DataMiningApriori程序 用eclipse打开,把三个测试数据mushroom、accidents和T10I4D100K放置 在F:\DataMiningSample\FPmining文件夹下面,即可运行 二、...
1 2 3 4 5 ... 20
收藏数 183,009
精华内容 73,203
关键字:

fp