`
liyonghui160com
  • 浏览: 777125 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Frequent Pattern 挖掘之二(FP Growth算法)

阅读更多

 

Frequent Pattern 挖掘之二(FP Growth算法)

FP树构造

FP Growth算法利用了巧妙的数据结构,大大降低了Aproir挖掘算法的代价,他不需要不断得生成候选项目队列和不断得扫描整个数据库进行比对。为了达 到这样的效果,它采用了一种简洁的数据结构,叫做frequent-pattern tree(频繁模式树)。下面就详细谈谈如何构造这个树,举例是最好的方法。请看下面这个例子:



 

 

这 张表描述了一张商品交易清单,abcdefg代表商品,(ordered)frequent items这一列是把商品按照降序重新进行了排列,这个排序很重要,我们操作的所有项目必须按照这个顺序来,这个顺序的确定非常简单,只要对数据库进行一 次扫描就可以得到这个顺序。由于那些非频繁的项目在整个挖掘中不起任何作用,因此在这一列中排除了这些非频繁项目。我们在这个例子中设置最小支持阈值 (minimum support threshold)为3。

我们的目标是为整个商品交易清单构造一颗树。我们首先定义这颗树的根节点为null,然后我们开始扫描整个数据库的每一条记录开始构造FP树。

第一步:扫描数据库的第一个交易,也就是TID为100的交易。那么就会得到这颗树的第一个分支<(f:1),(c:1),(a:1),(m:1),(p:1)>。注意这个分支一定是要按照降频排列的。

 
 

第 二步:扫描第二条交易记录(TID=200),我们会有这么一个频繁项目集合<f,c,a,b,m>。仔细观察这个队列,你会发现这个集合的 前3项<f,c,a>与第一步产生的路径<f,c,a,m,p>的前三项是相同的,也就是说他们可以共享一个前缀。于是我们在第 一步产生的路径的基础上,把<f,c,a>三个节点的数目加1,然后将<(b:1),(m:1)>作为一个分支加在(a:2)节 点的后面,成为它的子节点。看下图



 

 

第三步:接着扫描第三条交易记录(TID=300),你会看到这条记录的集合是<f, b>,与已存在的路径相比,只有f是共有的前缀,那么f节点加1,同时再为f节点生成一个新的字节点(b:1).就会有下图:



 

第四步:继续看第四条交易记录,它的集合是<c,b,p>,哦,这回不一样了。你会发现这个集合的第一个元素是c,与现存的已知路径的第一个节点f不一样,那就不用往下比了,没有任何公共前缀。直接将该集合作为根节点的子路径附加上去。就得到了下图(图1):



 

第五步:最后一条交易记录来了,你看到了一条集合<f,c,a,m,p>。你惊喜得发现这条路径和树现有最左边的路径竟然完全一样。那么,这整条路径都是公共前缀,那么这条路径上的所有点都加1好了。就得到了最终的图(图2)。



 

好了,一颗FP树就已经基本构建完成了。等等,还差一点。上述的树还差一点点就可以称之为一个完整的FP树啦。为了便于后边的树的遍历,我们为这棵树又增加了一个结构-头表,头表保存了所有的频繁项目,并且按照频率的降序排列,表中的每个项目包含一个节点链表,指向树中和它同名的节点。罗嗦了半天,可能还是不清楚,好吧直接上图,一看你就明白:



 

以上就是整个FP树构造的完整过程。聪明的读者一定不难根据上述例子归纳总结出FP树的构造算法。这里就不再赘述。详细的算法参考文献1。

 

FP树的挖掘

 

下面就是最关键的了。我们已经有了一个非常简洁的数据结构,下一步的任务就是从这棵树里挖掘出我们所需要的频繁项目集合而不需要再访问数据库了。还是看上面的例子。

 

第 一步:我们的挖掘从头表的最后一项p开始,那么一个明显的直接频繁集是(p:3)了。根据p的节点链表,它的2个节点存在于2条路径当中:路 径<f:4,c:3,a:3,m:2,p:2>和路径<c:1,b:1,p:1>.从路 径<f:4,c:3,a:3,m:2,p:2>我们可以看出包含p的路径<f,c,a,m,p>出现了2次,同时也会 有<f,c,a>出现了3次,<f>出现了4次。但是我们只关注<f,c,a,m,p>,因为我们的目的是找出包含 p的所有频繁集合。同样的道理我们可以得出<c,b,p>在数据库中出现了1次。于是,p就有2个前缀路径{(fcam:2), (cb:1)}。这两条前缀路径称之为p的子模式基(subpattern-base),也叫做p的条件模式基(之所以称之为条件模式基是因为这个子模式 基是在p存在的前提条件下)。接下来我们再为这个条件子模式基构造一个p的条件FP树。再回忆一下上面FP树的构造算法,很容易得到下面这棵树:



 

 

但是由于频繁集的阈值是3。那么实际上这棵树经过剪枝之后只剩下一个分支(c:3),所以从这棵条件FP树上只能派生出一个频繁项目集{cp:3}.加上直接频繁集(p:3)就是最后的结果.

第 二步:我们接下来开始挖掘头表中的倒数第二项m,同第一步一样,显然有一个直接的频繁集(m:3).再查看它在FP树中存在的两条路 径<f:4,c:3,a:3,m:2>和<f:4,c:3,a:3,b1,m:1>.那么它的频繁条件子模式基就是{ (fca:2),(fcab:1)}.为这个子模式基构造FP树,同时舍弃不满足最小频繁阈值的分支b,那么其实在这棵FP树中只存在唯一的一个频繁路 径<f:3,c:3,a:3>.既然这颗子FP树是存在的,并且不是一颗只有一个节点的特殊的树,我们就继续递归得挖掘这棵树.这棵子树是单 路径的子树,我们可以简化写成mine(FP tree|m)=mine(<f:3,c:3,a:3>|m:3).

下面来阐述如何挖掘这颗FP子树,我们需要递归.递归子树也需要这么几个步骤:

1 这颗FP子树的头表最后一个节点是a,结合递归前的节点m,那么我们就得到am的条件子模式基{(fc:3)},那么此子模式基构造的FP树(我们称之为 m的子子树)实际上也是一颗单路径的树<f:3,c:3>,接下也继续继续递归挖掘子子树 mine(<f:3,c:3>|am:3). (子子树的递归分析暂时打住.因为再分析子子树的递归的话文字就会显得太混乱)

2同样,FP子树头表的倒数第二个节点是c,结合递归前节点m,就有我们需要递归挖掘mine(<f:3>|cm:3).

3 FP子树的倒数第三个节点也是最后一个节点是f,结合递归前的m节点,实际上需要递归挖掘mine(null|fm:3),实际上呢这种情况下的递归就可以终止了,因为子树已经为空了.因此此情况下就可以返回频繁集合<fm:3>

注意:这三步其实还包含了它们直接的频繁子模式<am:3>,<cm:3>,<fm:3>,这在每一步递归调用mine<FPtree>都是一样的,就不再罗嗦得一一重新指明了.

实际上这就是一个很简单的递归过程,就不继续往下分析了,聪明的读者一定会根据上面的分析继续往下推导递归,就会得到下面的结果.

mine(<f:3,c:3>|am:3)=><cam:3>,<fam:3>,<fcam:3>

mine(<f:3>|cm:3)=><fcm:3>

mine(null|fm:3)=><fm:3>

这三步还都包含了各自直接的频繁子模式<am:3>,<cm:3>,<fm:3>.

最后再加上m的直接频繁子模式<m:3>,就是整个第二步挖掘m的最后的结果。请看下图



 

第 三步:来看看头表倒数第三位<b:3>的挖掘,它有三条路 径<f:4,c:3,a:3,b:1>,<f:4,b:1>,<c:1,b:1>,形成的频繁条件子模式基为 {(fca:1),(f:1),(c:1)},构建成的FP树中的所有节点的频率均小于3,那么FP树为空,结束递归.这一步得到的频繁集就只有直接频繁 集合<b:3>

第四步:头表倒数第四位<a:3>,它有一条路径<f:4,c:3>,频繁条件子模式 基为{(fc:3)},构成一个单路径的FP树.实际上可能有人早已经发现了,这种单路径的FP树挖掘其实根本不用递归这么麻烦,只要进行排列组合就可以 直接组成最后的结果.实际上也确实如此.那么这一步最后的结果根据排列组合就有:{(fa:3),(ca:3),(fca:3),(a:3)}

第五步:头表的倒数第五位<c:4>,它只有一条路径<f:4>,频繁条件子模式基为{(f:3)},那么这一步的频繁集也就很明显了:{(fc:3),(c:4)}

第六步:头表的最后一位<f:4>,没有条件子模式基,那么只有一个直接频繁集{(f:4)}

这6步的结果加在一起,就得到我们所需要的所有频繁集.下图给出了每一步频繁条件模式基.



 

其 实,通过上面的例子,估计早有人看出来了,这种单路径的FP树挖掘其实是有规律的,根本不用递归这么复杂的方法,通过排列组合可以直接生成.的确如 此,Han Jiawei针对这种单路径的情况作了优化.如果一颗FP树有一个很长的单路径,我们将这棵FP树分成两个子树:一个子树是由原FP树的单路径部分组成, 另外一颗子树由原FP树的除单路径之外的其余部分组成.对这两个子树分别进行FP Growth算法,然后对最后的结果进行组合就可可以了.

通 过上面博主不厌其烦,孜孜不倦,略显罗嗦的分析,相信大家已经知道FP Growth算法的最终奥义.实际上该算法的背后的思想很简单,用一个简洁的数据结构把整个数据库进行FP挖掘所需要的信息都包含了进去,通过对数据结构 的递归就可以完成整个频繁模式的挖掘.由于这个数据结构的size远远小于数据库,因此可以保存在内存中,那么挖掘速度就可以大大提高.

也 许有人会问?如果这个数据库足够大,以至于构造的FP树大到无法完全保存在内存中,这该如何是好.这的确是个问题. Han Jiawei在论文中也给出了一种思路,就是通过将原来的大的数据库分区成几个小的数据库(这种小的数据库称之为投射数据库),对这几个小的数据库分别进 行FP Growth算法.

还是拿上面的例子来说事,我们把包含p的所有数据库记录都单独存成一个数据库,我们称之为p-投射数据库,类似的m,b,a,c,f我们都可以生成相应的投射数据库,这些投射数据库构成的FP树相对而言大小就小得多,完全可以放在内存里.

在现代数据挖掘任务中,数据量越来越大,因此并行化的需求越来越大,上面提出的问题也越来越迫切.下一篇博客,博主将分析一下,FP Growth如何在MapReduce的框架下并行化.

 

      无论怎么个算法都是求的排列组合出现的次数,在实际应用中订单每天增加,我们采用增量的方式计算,去掉支持度的限制。

 

 

  • 大小: 25.5 KB
  • 大小: 8.8 KB
  • 大小: 11.7 KB
  • 大小: 12.8 KB
  • 大小: 17.8 KB
  • 大小: 18.3 KB
  • 大小: 30.8 KB
  • 大小: 10.9 KB
  • 大小: 44.8 KB
  • 大小: 31.8 KB
分享到:
评论

相关推荐

    FPGrowth的代码

    二、FPGrowth算法原理 1. **构建FP树**:首先,对交易数据进行预处理,生成一个无序的频繁项集列表。然后,根据这些频繁项集构建一棵倒置的前缀树,即FP树。在FP树中,每个节点代表一个项,根节点为空,每个非叶...

    机器学习-FPGROWTH算法(PPT56页).ppt

    FPGrowth算法,全称为Frequent Pattern Growth算法,是一种用于发现数据集中频繁项集的算法。频繁项集是指在数据集中频繁出现的项组合,而这些项组合的相关支持度超过了预先设定的最小支持度阈值。关联规则则是在...

    关联规则挖掘之FP-growth算法实现

    相比之下,FP-growth算法通过构建一种特殊的树结构——FP树(Frequent Pattern Tree)来大幅减少数据扫描次数。 FP-growth算法主要包括以下三个步骤: 1. 构建FP树:首先,对原始交易数据进行预处理,将所有项按照...

    C++版的fp-growth算法

    FP-Growth算法是一种高效的数据挖掘技术,主要用于关联规则学习,即在大规模数据集中发现频繁项集。这个算法在处理大数据量时表现出了较高的性能,因为它避免了构建和搜索全频繁项集的候选集。在C++中实现FP-Growth...

    FP-Growth算法代码

    FP-Growth算法是一种在数据挖掘领域广泛使用的关联规则学习算法,尤其适用于处理大规模交易数据集。这个算法的主要优点是高效性和内存效率,它避免了频繁的全数据库扫描,通过构建一个高效的FP树(Frequent Pattern ...

    fpgrowth的python实现

    总之,Python中的FPGrowth算法提供了一种实用的方式来挖掘数据中的频繁项集,进而发现潜在的关联规则。通过结合实际的交易数据,我们可以更好地理解消费者的购买行为,为企业决策提供有价值的洞察。在实践中,根据...

    基于FP-growth算法的数据挖掘实例研究.pdf

    FP-growth算法的核心思想是利用一种称为FP树(Frequent Pattern Tree)的数据结构来存储数据集中的频繁项集信息。在构建FP树的过程中,第一次扫描数据库用于统计各项项集的支持度计数,并根据最小支持度阈值筛选出...

    fpgrowth算法java源码

    **FPGrowth算法原理:** `FPGrowth`(Frequent Pattern Growth)算法由Hao Chen和Jiawei Han等人于2000年提出,它的主要创新在于避免了频繁项集生成过程中大量的候选集生成和测试,从而提高了效率。`FPGrowth`通过...

    C++实现FP-Growth算法

    FP-Growth的核心思想是通过构建一个FP树(Frequent Pattern tree)来存储频繁项集,并利用这个树结构来挖掘出所有的关联规则。FP树是一种压缩的数据结构,它将所有交易中的频繁项按照项的出现频率排序,并且只存储一...

    FP-Growth算法从新闻网站点击流中挖掘频繁项.rar

    这个算法的核心思想是构建一个特殊的树形结构——FP树(Frequent Pattern Tree),以此来存储和挖掘频繁项集。它在处理大量数据时表现出色,因为它避免了生成庞大的候选集,并且只需两次遍历原始数据。 首先,我们...

    fpgrowth的java实现

    FPGrowth算法的核心思想是通过构建FP树(Frequent Pattern Tree)来避免对所有可能的项集进行全集扫描,从而大大提高了效率。该算法分为两个主要步骤:1)构建FP树;2)基于FP树进行剪枝挖掘。 1. 构建FP树:首先,...

    基于FP-growth算法的用电异常数据挖掘方法.pdf

    在数据挖掘领域,FP-growth算法是一种用于发现数据集中频繁项集的高效算法,它基于一个被称为FP树(Frequent Pattern Tree)的数据结构。FP-growth算法的核心优势在于它不需要生成候选集,从而可以高效地挖掘频繁项...

    Fuzzy-TD-FPgrowth 算法

    总的来说,Fuzzy-TD-FPgrowth算法是针对模糊数据的关联规则挖掘方法,它继承了FPgrowth的高效性,同时利用模糊集理论处理不确定性,使得在实际应用中能够更好地适应复杂的数据环境。通过FuzzyTDFP_V2这样的实现,...

    关联规则FP-Growth算法

    **二、FP-Growth算法步骤** 1. **预处理**:首先,计算每个项的支持度,找出频繁项集。通常设定一个最小支持度阈值,只保留支持度高于此阈值的项。 2. **构建FP树**:将频繁项集按照降序排列,并构建FP树。在树的...

    fPGrowth相关词

    fPGrowth算法采用了完全不同的思路,它首先构建一个“项集树”(Frequent Pattern Tree,简称FP树)。在这个树结构中,每个节点代表一个项,每条边代表一个事务。所有频繁项集都在这棵树的子树中,大大减少了搜索...

    基于FP-growth算法与分层线性模型交互的招生数据挖掘.pdf

    FP-growth算法的核心优势在于它只需要两次数据库扫描,并采用一种称为FP树(Frequent Pattern Tree)的压缩数据结构来存储频繁项集,从而极大地提高了频繁项集的挖掘效率。在招生数据挖掘中,利用FP-growth算法可以...

    FP-Growth 关联规则挖掘方法 Matlab 频繁项集挖掘

    与Apriori算法一样,FP-Growth 是一种关联规则挖掘方法。该方法名称中的术语 FP 是频繁模式 (Frequent Pattern) 的缩写。FP-Growth采用频繁模式挖掘技术构建频繁模式树(FP-Tree),可用于提取关联规则。与 Apriori ...

    fpgrowth C++.rar

    fpgrowth算法的c语言实现例子,包含word编写使用心得。频繁模式挖掘,fpgrowth算法,c++编写,附带文档说明 (Frequent pattern mining, fpgrowth algorithm, c++ writing, with documentation)

Global site tag (gtag.js) - Google Analytics