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算法详解

    万次阅读 2016-01-15 08:40:35
    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

    展开全文
  •     FP增长(FP-growth)算法是一种高效发现频繁项集的方法,只需要对数据库进行两次扫描。它基于Apriori构建,但在完成相同任务时采用了一些不同的技术。该算法虽然能更为高效地发现频繁项集,但不能用于发现...

    引言

        FP增长(FP-growth)算法是一种高效发现频繁项集的方法,只需要对数据库进行两次扫描。它基于Apriori构建,但在完成相同任务时采用了一些不同的技术。该算法虽然能更为高效地发现频繁项集,但不能用于发现关联规则。
        本文用到的部分术语已在简介中介绍(具体看‘基本概念-关联分析’),这里不再重述。

    一、FP-growth算法

        FP-growth算法发现频繁项集的基本过程如下:
    ① 构建FP树
    ② 从FP树中挖掘频繁项集



    二、构建FP树

        FP树是一种输入数据的压缩表示,它通过逐个读入事务,并把事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠,路径相互重叠越多,使用FP树结构获得的压缩效果越好。
        为构建FP树,需要对原始数据集扫描两遍。
    ① 第一遍对所有元素项的出现次数进行计数,丢弃支持度小于阈值的非频繁项,得到频繁项集,并对频繁项集按照支持度的递减排序。
    ② 第二遍扫描时,构建FP树。从空集开始,依次读入排序好的频繁项集中各条事务。如果树中已存在现有元素,则增加现有元素的值;如果现有元素不存在,则向树添加一个分枝。
    例1
    数据集如下(需满足的最小支持度计数为3):

    事务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

    ① 对数据集进行第一次扫描,丢弃支持度小于3的非频繁项,得到频繁项集,并对频繁项集按照支持度计数的递减排序,得
    (计算支持度计数得要丢弃的非频繁项是:h,j,p,w,v,u,n,o,q,e,m)

    事务ID 过滤后的元素 重排序后的元素
    001 r,z z(5),r(3)
    002 z,y,x,t,s z(5),x(4),y(3),t(3),s(3)
    003 z z(5)
    004 r,x,s x(4),r(3),s(3)
    005 y,r,x,z,t z(5),x(4),y(3),r(3),t(3)
    006 y,z,x,s,t z(5),x(4),y(3),s(3),t(3)

    ② 对数据集进行第二次扫描,构建FP树。
    这里写图片描述



    三、从FP树中挖掘频繁项集

        从FP树中抽取频繁项集的三个基本步骤如下:
    ① 从FP树中获取前缀路径(prefix path)
        一条前缀路径是介于所查找元素项与树根节点之间的所有内容。为了获得这些前缀路径,可以对树进行穷举式搜索,直到获得想要的频繁项为止,或者使用一个更有效的方法来加速搜索过程。可以利用先前创建的头指针表来得到一种更有效的方法,头指针表包含相同类型元素链表的起始指针,一旦到达了每一个元素项,就可以上溯这棵树直到根节点为止。
    ② 将前缀路径转化为条件FP树(conditional FP-tree)
        对于每一个频繁项,都要创建一棵条件FP树,条件FP树的结构与FP树类似。先对单个元素构建条件FP树(即删除前缀路径中支持度计数小于阈值的树),再对剩下的元素与单个元素两两组合构建新的条件FP树,递归直至条件FP树为空。
    例2
    挖掘例1中数据的频繁项集
    ① 获取前缀路径
    先创建头指针表及FP树,得到如下所示数据结构
    这里写图片描述
    以 t 为例,上图从左往右寻找第一个 t ,通过上溯到根节点可以获取第一个前缀路径为{s,y,x,z},接着利用头指针表寻找下一个 t ,再上溯到根节点可以获取第二个前缀路径为{r,y,x,z}。
    每个频繁项的前缀路径如下:

    频繁项 前缀路径(数字为支持度计数)
    z {}5
    r {z}1,{y,x,z}1,{s,x}1
    x {z}3,{}1
    y {x,z}3
    s {y,x,z}2,{x}1
    t {s,y,x,z}2,{r,y,x,z}1

    ② 创建条件FP树
    以 t 为例:
    用{t}为结尾项,先计数各支持度计数,再去掉计数值小于3的项,得到条件FP树如下图最右所示
    这里写图片描述
    用循环分别用{x,t}{y,t}{z,t}为结尾项构建条件FP树,直至构建的条件FP树为空。




    四、代码实现(python)

    以下代码来自Peter Harrington《Machine Learing in Action》
    代码如下(保存为fpGrowth.py):

    # -- coding: utf-8 --
    class treeNode:
        # FP树中节点的类定义,用于构建FP树
        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 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)] = 1
        return retDict
    
    def createTree(dataSet, minSup=1):
        # 该函数用于创建FP树
        # 该函数接收两个参数,分别是格式化后的数据集和需满足的最小支持度计数
        headerTable = {}                                # 存储头指针
        for trans in dataSet:
            # 循环每一个事务
            for item in trans:
                # 循环事务中的每一个元素,存储各元素的支持度计数
                headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
        # 移除不满足最小支持度计数的元素项
        for k in headerTable.keys():
            if headerTable[k] < minSup:
                del(headerTable[k])
        freqItemSet = set(headerTable.keys())           # 存储删除后的元素项,即频繁项
        if len(freqItemSet) == 0: return None, None     # 如果没有元素项满足要求,则退出
        # 对头指针表扩展,以便可以保存计数值及指向每种类型第一个元素项的指针
        for k in headerTable:
            headerTable[k] = [headerTable[k], None]
        retTree = treeNode('Null Set', 1, None)         # 创建只包含空集合的根节点
        for tranSet, count in dataSet.items():          # 第二次遍历数据集,tranSet为各事务,count为初始化的计数值
            localD = {}
            for item in tranSet:
                if item in freqItemSet:                 # 如果该元素项为频繁项,则可继续操作
                    localD[item] = headerTable[item][0] # 将第一次遍历得到的支持度计数赋值給相应元素
            if len(localD) > 0:
                orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 获取元素项,并按支持度计数高到低排序
                updateTree(orderedItems, retTree, headerTable, count)
        return retTree, headerTable
    
    def updateTree(items, inTree, headerTable, count):
        # 该函数接收4个参数,分别为已排序好的元素项、FP树、头指针表、对应计数值
        if items[0] in inTree.children:
            # 如果该元素是作为子节点存在,则更新该元素的计数
            inTree.children[items[0]].inc(count)
        else:
            # 否则,创建一个新的treeNode并将其作为一个字节点添加到树中
            inTree.children[items[0]] = treeNode(items[0], count, inTree)
            if headerTable[items[0]][1] == None:
                # 若头指针为空,更新头指针为树的子节点
                headerTable[items[0]][1] = inTree.children[items[0]]
            else:
                # 若头指针有值,更新头指针的nodeLink
                updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
        if len(items) > 1:
            # 对剩下的元素进行迭代调用自身
            updateTree(items[1::], inTree.children[items[0]], headerTable, count)
    
    def updateHeader(nodeToTest, targetNode):
        # 该函数用于更新头指针
        # 该函数接收2个参数,分别是待更新的位置和需更新的值
        while (nodeToTest.nodeLink != None):
            nodeToTest = nodeToTest.nodeLink           # 循环至链表尾端为None
        nodeToTest.nodeLink = targetNode
    
    def ascendTree(leafNode, prefixPath):
        # 该函数用于递归上溯整颗树
        if leafNode.parent != None:
            prefixPath.append(leafNode.name)
            ascendTree(leafNode.parent, prefixPath)
    
    def findPrefixPath(basePat, treeNode):
        # 该函数用于为给定元素项生成一个前缀路径
        # 该函数接收2个参数,分别是给定元素项和头指针表纪录的该元素的相似项路径
        condPats = {}
        while treeNode != None:
            prefixPath = []
            ascendTree(treeNode, prefixPath)
            if len(prefixPath) > 1:
                condPats[frozenset(prefixPath[1:])] = treeNode.count
            treeNode = treeNode.nodeLink
        return condPats
    
    def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
        # 该函数用于将前缀路径转化为条件FP树
        # 该函数接收5个参数,分别是FP树、头指针表、需满足最小支持度计数、前缀路径、频繁项集
        bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]  # 将频繁1-项集的元素按支持度计数低到高排序
        for basePat in bigL:
            newFreqSet = preFix.copy()
            newFreqSet.add(basePat)
            freqItemList.append(newFreqSet)
            condPattBases = findPrefixPath(basePat, headerTable[basePat][1])    # 获取basePat的前缀路径
            myCondTree, myHead = createTree(condPattBases, minSup)              # 根据给定的前缀路径构建FP树
            if myHead != None:
                # 递归直到该元素的前缀路径为空
                print 'conditonal tree for:', newFreqSet
                myCondTree.disp(1)
                mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
    

    运行命令如下:
    这里写图片描述









    以上全部内容参考书籍如下:
    《数据挖掘导论(完整版)》人民邮电出版社
    Peter Harrington《Machine Learing in Action》

    展开全文
  • 1. FP Tree数据结构  为了减少I/O次数,FP Tree算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分,如下图所示:  第一部分是一个项头表。里面记录了所有的1项频繁集出现的次数,按...
  • Panasonic FP系列编程手册 本手册收集了FP0、FP0R、FP-e 、FPE、FP-X、FP2、FP2SH及FP10SH中可使用的指令、并对存储区的使用、编程时的注意事项进行说明。
  • TP、TN、FP、FN解释说明

    万次阅读 多人点赞 2016-08-22 13:28:06
      首先这几个术语会高频率得出现在论文的实验部分,它是对实验结果的描述,首先我想先解释这几个缩写的含义: precesion:查准率,即在检索后返回的结果中,真正正确的个数占整个结果的比例。...
  • FP-growth 算法与Python实现

    万次阅读 多人点赞 2018-05-23 11:28:50
    FP-growth 算法 介绍   打开你的搜索引擎,输入一个单词或一部分,例如“我”,搜索引擎可能会去统计和“我”一块出现得多的词,然后返回给你。其实就是去找频繁项集,而且需要相当地高效,像Apriori那样的...
  • 深入剖析FP-Growth原理

    千次阅读 2019-04-21 18:40:52
    同步更新公众号:海涛技术漫谈 频繁项挖掘广泛的应用于寻找关联的事物。最经典的就是,电商企业通过分析用户的...接下来介绍并行FP-Growth算法怎么通过3次map-reduce实现了并行化。最后通过分析spark mlib包中PF...
  • FP-growth算法理解和实现

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

    万次阅读 多人点赞 2019-05-23 18:35:49
      预测     P N 实际 P TP FN N FP TN
  • 频繁项集挖掘算法之FPGrowth

    万次阅读 多人点赞 2014-01-01 22:30:24
    背景:  频繁项集挖掘算法用于挖掘经常一起出现的item集合(称为频繁项集),通过挖掘出这些频繁项集,当在一个事务中出现频繁项集的其中一个item,则可以把该频繁项集的其他item作为推荐。比如经典的购物篮分析中...
  • 数据挖掘 FP-tree 算法

    千次阅读 2018-05-15 19:31:05
    学习笔记之数据挖掘 FP-tree 算法 FP-tree 算法和 Apriori 算法都被用作关联规则挖掘。 FP-tree 算法只进行 2 次数据库扫描。相比于 Apriori 算法,她没有候选集,直接压缩数据库成一个频繁模式树,通过这棵树...
  • FP-Growth算法python实现

    万次阅读 热门讨论 2017-05-16 14:15:16
    前言:关于关联分析和FP_Growth的介绍请见:什么是关联分析、FP-Growth算法的介绍。本文主要介绍用 python 语言实现 FP_Growth 算法的代码。 正文:FP_Growth项目目录有四个文件: >FP_Growth ▪ __init__.py ...
  • GPU架构中的半精度与单精度计算 ​ 由于项目原因,我们需要对darknet中卷积层进行优化,然而对于像caffe或者darknet这类深度学习框架来说,都已经将卷积运算转换成了矩阵乘法,从而可以方便调用cublas 库函数和...
  • 一: FP,FN,TP,TN 刚接触这些评价指标时,感觉很难记忆FP,FN,TP,TN,主要还是要理解,理解后就容易记住了 P(Positive)和N(Negative) 代表模型的判断结果 T(True)和F(False) 评价模型的判断结果是否正确 比如FP:模型的...
  • ftell函数用于得到文件位置指针当前位置相对于文件首的偏移字节数,下面给出一个简单的例子: #include ... FILE *fp = fopen("myData.txt", "w"); cout (fp) ; fprintf(fp, "123"); cout << ftel
  • Arm上函数调用的规则在ARM System Developer's Guide文档中的ATPCS部分有详细的定义,这里主要通过函数调用过程中函数栈的情况来说明fp和sp等寄存器的作用。有关ATPCS的详细内容可以去文档中看。 fp叫做frame ...
  • php flock 使用实例

    万次阅读 2015-02-15 23:32:28
    flock() 允许执行一个简单的可以在任何平台中使用的读取/写入模型(包括大部分的Unix派生版和windows) 四个使用flock的实例,介绍LOCK_SH,LOCK_EX,LOCK_UN,LOCK_NB的使用。
  • 经典 《C++视频教程》 全集

    万次阅读 2007-02-14 20:45:00
    来源: 网上收集整理 [中山大学]C++视频教学51讲[csf]http://218.19.175.248/Ncourse/cxsj/cxsj01.csf====中间自己加,注意格式!共51讲!===========http://218.19.175.248/Ncourse/cxsj/cxsj51.csf
1 2 3 4 5 ... 20
收藏数 190,385
精华内容 76,154
关键字:

fp