精华内容
下载资源
问答
  • WAP-Tree算法和PLWAP-Tree算法是针对于序列模式进行挖掘的两种

        WAP-Tree(Web Access Pattern Tree)算法和PLWAP-Tree(Pre-Order Linked WAP-Tree)算法是针对于序列模式进行挖掘的两种算法,其中PLWAP-Tree是对WAP-Tree算法的一个改进。

        WAP-Tree算法是一种挖掘web访问日志的序列模式的算法,该算法首先把web访问的序列存储到一棵前缀树中(类似与FP-Tree),然后再基于WAP-Tree通过递归的构造中间书进行序列模式挖掘。

    WAP-Tree算法概述:

        ①.扫描数据库,找出所有的频繁项目

        ②.再次扫描数据库,根据①中所得到的频繁项目找出每个事务的频繁序列,然后构造WAP-Tree

        ③.找条件后缀模式

        ④.利用③中得到的后缀模式进行构造中间条件WAP-Tree

        ⑤.重复③、④步骤,直到构造的条件WAP-Tree只有一个分支或者为空时为止

    WAP-Tree算法示例(数据如表一,最小支持度为3,即要求支持度〉3):


    图1:示例数据​

    步骤:

    1、扫描原始数据,得到频繁项目:

        扫描DB,得到各个项目的支持度  a:4  b:4  c:4  d:1  e:2  f:3 ,因为d、e、f 的支持度均<=3,所以将其剔除,故得到频繁项目:

          a:4  b:4  c:4

    2、再次扫描数据库,得到频繁序列,然后构造WAP-Tree

        2.1 得到的频繁序列如图1的第三列所示

        2.2 构造WAP-Tree的过程如图2所示


    图2:构造WAP-Tree过程(其中每个节点的数字代表该节点出现的次数)

    Header table:存储了每个频繁项目,每个频繁项目后面是一个链表,该链表中存储了该项目在WAP-Tree中出现的位置(以每个项目插入的顺序进行存储【注意这与PLWAP-Tree中Header table存储的方式不一样】

    3、找到条件后缀模式

    在Head table中找到出现频度最低的项目进行挖掘:即选取C进行挖掘

        3.1 找出C的前缀条件序列如下:(因为Header table中项目C的链表存储了C出现的位置,顺着链表既可以找到每个C在树中的位置,而不用遍历整棵树)

        aba:2; ab:1; abca:1; ab:−1; baba:1; abac:1; aba:−1.

       注:在WAP-Tree分支中,若某一项目的条件前缀序列中含有一个子序列(该子序列也是同一项目的条件前缀序列),则需要将同等数量子序列提取出来,因为其之前已经贡献过一次计数了。

        例:在abcac中,第二个c的前缀序列是abca:1,但是由于其中ab是第一个c的前缀序列,所以为了避免ab序列的数量计数两次,所以便有了ab:-1序列

        3.2 统计c的前缀序列中每个项目的支持度,得到如下:

         a:4    b:4    c:2  (c的支持度小于等于3,故剔除)

       3.3根据上一步得到的结果构造频繁序列

        则频繁序列为:aba:2; ab:1; aba:1; ab:−1; baba:1; aba:1; aba:−1

    4、利用上一步中得到的结果构造条件WAP-Tree树(如图3的(a)所示)

    图3:基于项目c构造的WAP-Tree

    然后重复算法的第 ③、④步,

        根据图3(a),选择最小支持度的项目b,然后构造bc的条件WAP-Tree,如图3(b),然后图3(b)只有一个分支,则计算支持度后返回,然后构造ac的条件WAP-Tree如图3(c)所示,接着构造bac和aac的条件WAP-Tree,如图3(d)和如图3(e)所示。。。依次递归重复下去,最终得到的频繁模式项目集结果如下所示: 

    {c, aac, bac, abac, ac, abc, bc, b, ab, a, aa,ba, aba}


    PLWAP-Tree算法:

       其他算法存在的问题:

        ①类Apriori算法会产生大量的候选模式集合(特别是频繁序列模式很长的时候)

        ②WAP-Tree算法中递归的构造条件WAP-Tree将会十分费时

    故因为WAP-Tree构造条件WAP-Tree费时的特点,提出了PLWAP-Tree算法,该算法将会避免条件WAP-Tree的构造。PLWAP-Tree算法是基于某个项目的后缀树进行挖掘(WAP-Tree算法是基于某个项目的前缀树进行挖掘)且PLWAP-Tree中的每个节点都有一个独一无二的编码,由于编码的存在,避免了构造条件WAP-Tree.

    PLWAP-Tree算法伪代码如图4、5、6所示:

    图4:算法整体流程图

    图5:PLWAP-Tree构造算法

    (从算法可以看出,其先构造PLWAP-Tree,然后以先序遍历的方式遍历该树构造先序链【WAP-Tree是在构造树的过成功,以节点插入的先后顺序构造先序链】)


    图6:PLWAP-Tree的挖掘算法


    PLWAP-Tree算法示例(同理利用图1所示数据,然后最小支持度同样为3):

    1、扫描原始数据,得到频繁项目:

        扫描DB,得到各个项目的支持度  a:4  b:4  c:4  d:1  e:2  f:3 ,因为d、e、f 的支持度均<=3,所以将其剔除,故得到频繁项目:

          a:4  b:4  c:4

    2、再次扫描数据库,得到频繁序列,然后构造PLWAP-Tree

        2.1 得到的频繁序列如图1的第三列所示

        2.2 构造的PLWAP-Tree如图7所示


    图7:PLWAP-Tree的构造结果(已经插入先序链)

    注:

    节点命名规则:节点名:节点所对应项目出现的次数:节点的编码

    编码规则:(1).根节点的编码为空 (2).root子节点的最左端节点编码为1,其他的子节点的最左端节点(左边第一个节点)为其父节点编码后增加1位1, (3). 其他节点,若该节点是其父节点的左边第二个节点,则在其父节点的编码后加上10,若是左边第三个节点则在其父节点上增加100,若是左边第四个节点,则在其父节点的后边增加1000,依次类推......

    3、递归挖掘频繁序列

        此步骤的挖掘按照图6,所示的算法。

        3.1.挖掘以aa为开头的频繁序列的的过程如下图8所示:  



    图8:挖掘以aa开头的频繁序列的过程示意图

           第一步调用R={Root}  F=NULL  

    过程解析:   ①找出先序表的L中每个事件找出后缀树,如图8(a)所示,

                         ②把a序列(即a:{1,111,11101,101,10111})记为ei-sequence,把ei-sequence中的第一个节点(a:1)存入S

                         ③遍历ei-sequence,如果ei-sequence的节点eiR 的后代并且不是S的后代,则  【根据节点的位置编码可以轻松判定某个节点是否是另一个节点的后代,而不用遍历树去判断】

                                   则把该节点ei加入后缀树头节点集合R’

                                   ei的数量加入C

                                   用ei 代替S

                         ④ 如果C 大于λ 【判断是否大于支持度】

                                  把 ei 添加到F 后形成F  并输出F (输出频繁模式)

                对调用本身,传入参数R’F

    Q:如何判断节点B是否是节点A的后代?

    A:在节点A的编码后面加上1,判断节点B的编码的前N位是否与节点A后面加上1后的编码相同,相同则为后代,不同则不是。

    例如:节点a:3:1、节点c:2:1111、节点b:1:1011

    节点a:3:1编码后面加上1变成11,

        节点c:2:1111的前两位与节点a:3:1变化后的编码相同,故节点c:2:1111节点a:3:1的后代;

        节点b:1:1011的前两位与节点a:3:1变化后的编码不同,故节点b:1:1011不是节点a:3:1的后代。

    3.2. 挖掘以ab和ac为开头的频繁序列,如图9所示:

    图9:挖掘以ab和ac为开头的频繁序列的过程示意图

    过程解析如图8的过程解析


    然后按照图8和图9的过程挖掘以b和c开头的频繁序列

    最终挖掘出的结果是:{c, aac, bac, abac, ac, abc, bc, b, ab, a, aa,ba, aba}


    注:本文的算法和插图来源于文章《MiningWeb Log Sequential Patterns with Position Coded Pre-Order LinkedWAP-Tree∗》

    展开全文
  • Apriori算法和FP-Tree算法简介 本节主要描述了基于 Apriori 算法的关联分析方法为了克服 Apriori 算法在复杂度和效率方面的缺陷本节还进一步的介绍了基于 FP-Tree 的频繁模式挖掘方法 Apriori关联分析算法 Apriori ...
  • Apriori 算法和 FPTree 算法都是数据挖掘中的关联规则挖掘算法处理的都是最简单的单层单维布尔关联规则 Apriori 算法 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法是基于这样的事实算法使用频繁项集...
  • FP Tree算法原理

    千次阅读 多人点赞 2019-06-17 09:59:57
    为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。 1. FP Tree数据结构 为了减少 I/O ...

    作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶颈。为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。


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

    转载

    展开全文
  • 本ppt是关于讲解关联规则,以及关联规则中apriori算法和fptree算法,以及fptree算法实现的解释
  • FPTree算法笔记

    千次阅读 2017-07-20 23:54:12
    FPTree算法笔记

    FPTree算法笔记:

    FPTree算法引入一些数据结构来临时的存储数据
    数据结构分为三个部分
    第一部分是一个项头表:记录所有1项频繁项集出现的次数,按照次数降序排列
    第二部分是FP Tree: 将原始数据映射到一颗FP树。
    第三部分是节点链表: 所有项头表里的1项频繁集都是一个节点链头的表,它依次指向FP
    树中该1频繁项集出现的位置。(是一根线)方便项头表和FP Tree之间的联系查找和
    更新。

    项头表的建立:
    第一次扫描:统计所有频繁1项集,支持度降序排列将其放入项头表中
    第二次扫描:将源数据的每条数据中的非频繁1项集剔除,并将该数据中的元素按支持度
    大小进行排序,存放回源数据中(可以尽可能的共用祖先节点)

    FP Tree的建立
    开始时FP树无数据,即根节点为空,建立FP树时我们一条一条的读入排序后的数据集
    ,插入FP树,插入时按排序后的顺序插入,排序靠前的是祖先节点,靠后的是子孙节点
    。(源数据在第二次扫描的时候,已经将排序考前的节点放在了前面,因此祖先节点
    排序考前,而子孙节点排序靠后)。如果有共用的祖先节点,则祖先节点数加1。如果
    有新节点出现,则项头表对应的节点会通过节点链接上新的节点。
    所有数据都插入到FP树后,FP树建立完成。

    FPTree的挖掘
    得到了FP树和项头表以及节点链表
    首先从项头表的底部向上一次挖掘,对于项头表对应FP树的每一项,我们要找到条件
    模式基。条件模式基是以我们要挖掘的节点作为叶子节点所对应的FP子树。
    其次将得到的FP子树的每个节点的计数设置为叶子节点的而计数,并删除计数低于
    支持度的节点。我们就可以得到频繁项集。

    FPTree算法归纳
    1) 扫描数据,得到所有频繁1项集的计数。然后删除支持度低于阈值的项,将频繁1项
    集放入项头表,并按照支持度降序排列。
    2)扫描数据,将读到的数据剔除非频繁1项集,并按支持度降序排列
    3)读入排序后的数据集,插入FP树,序靠前的节点是祖先节点,而靠后的是子孙节点。
    如果有共用的祖先,则对应的公用祖先节点计数加1。插入后,如果有新节点出现,则
    项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后,
    FP树的建立完成。
    4)从项头表的底部项依次向上寻找条件模式基。从条件模式基递归挖掘得到项头表
    项项的频繁项集。
    5)如果不限制频繁项集的项数,则返回步骤4所有的频繁项集,否则只返回满足
    项数要求的频繁项集。

    参考链接:http://www.cnblogs.com/aeexiaoqiang/p/6531789.html———-

    展开全文
  • 为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。1.FP Tree数据结构为了减少I/O次数,FP Tr...

    在Apriori算法原理总结中,我们对Apriori算法的原理做了总结。作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶颈。为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。下面我们就对FP Tree算法做一个总结。

    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)从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集(可以参见第4节对F的条件模式基的频繁二项集到频繁5五项集的挖掘)。

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

    6. FP tree算法总结

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

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

    (欢迎转载,转载请注明出处。欢迎沟通交流: liujianping-ok@163.com)

    展开全文
  • Apriori算法与FPtree算法的探讨
  • FP Tree算法原理总结

    2018-07-26 06:57:19
    FP Tree算法原理总结  在Apriori算法原理总结中,我们对Apriori算法的原理做了总结。作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶颈。为了解决这个问题,FP Tree算法(也称FP Growth...
  • 数据挖掘 FP-tree 算法

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

    2012-07-03 15:11:38
    fp-tree算法
  • FP Tree算法原理总结 转自: https://www.cnblogs.com/zhengxingpeng/p/6679280.html 总结得太好了。 FP Tree算法原理总结  在Apriori算法原理总结中,我们对Apriori算法的原理做了总结。作为一个挖掘频繁项集的...
  • Kd-Tree算法原理

    2019-05-11 14:22:22
    Kd-Tree算法原理和开源实现代码 本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——Kd-Tree(Kd树)。Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间...
  • KD-TREE 算法原理

    2018-11-28 11:50:10
    KD-TREE 算法原理 http://www.oneie.com/index.php/qyjs/47-txcl/1532-kd-tree   本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——Kd- Tree(Kd树)。Kd-Tree,即K-dimensional tree,是一种...
  • 为了克服 Apriori 算法在复杂度和效率方面的缺陷,本节还进一步的介绍了基于 FP-Tree 的频繁模式挖掘方法。 Apriori关联分析算法 Apriori 算法是挖掘产生关联规则所需频繁项集的基本算法,也是最著名的关联分析算法...
  • k-d tree 算法实现

    2019-04-07 20:47:12
    k-d tree 算法 k-d 树(k-dimensional 树的简称),是一种分割 k 维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。 应用背景 过程 k-d tree 算法主要分为两部分: k-d 树的...
  • FP-tree算法介绍及python实现 FP-tree算法原理可参考刘建平老师的的FP-tree原理介绍,非常详细 https://www.cnblogs.com/pinard/p/6307064.html 总结起来,FP-tree算法实现需要完成三个步骤: (1)两次扫描...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,308
精华内容 6,923
关键字:

tree算法