FP-tree 频繁树模式算法

xiaoxiao2021-02-28  48

  步骤总结:

一.构造FP 树,规则:按照支持度降序顺着根节点排下,以便于频繁项的共享

二.对构造好的fp—tree 进行投影,投影过程:从底层p节点开始递归,遍历所有候选项,删除非频繁项,如定阈值为1,从、删除支持度小于1的项。

 

一、FP-tree的生成方法

        第二步根据支持度对频繁项进行排序是本算法的关键。第一点,通过将支持度高的项排在前面,使得生成的FP-tree中,出现频繁的项更可能被共享,从而有效地节省算法运行所需要的空间。第二点,通过这种排序,可以对FP-tree所包含的频繁模式进行互斥的空间拆分,得到相互独立的子集,而这些子集又组成了完整的信息。

 

二、FP-tree子集分割方法

        如上图,求p为前缀的投影数据库:根据头表的指针找到FP-tree的两个p节点,搜索出从这两个节点到树的根节点路径节点信息(包含支持度)。然后累加路径节点信息的支持度,删除非频繁项。对剩下的频繁项按照上一节的方法构建FP-tree。过程如下图所示:

三、FP-Growth算法流程

        基本思路是:不断地迭代FP-tree的构造和投影过程。

        对于每个频繁项,构造它的条件投影数据库投影FP-tree。对每个新构建的FP-tree重复这个过程,直到构造的新FP-tree为空,或者只包含一条路径。当构造的FP-tree为空时,其前缀即为频繁模式;当只包含一条路径时,通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式。

---------------------------------------------------------------------------------------------------

要点:

  FP Growth是一种比Apriori更高效的频繁项挖掘方法,它只需要扫描项目表2次。其中第1次扫描获得当个项目的频率,去掉不符合支持度要求的项,并对剩下的项排序。第2遍扫描是建立一颗FP-Tree(frequent-patten tree)。

  接下来的工作就是在FP-Tree上进行挖掘。

  比如说有下表:

它所对应的FP_Tree如下:

  然后从频率最小的单项P开始,找出P的条件模式基,用构造FP_Tree同样的方法来构造P的条件模式基的FP_Tree,在这棵树上找出包含P的频繁项集。

依次从m,b,a,c,f的条件模式基上挖掘频繁项集,有些项需要递归的去挖掘,比较麻烦,比如m节点,具体的过程可以参考博客:FrequentPattern 挖掘之二(FP Growth算法),里面讲得很详细。

参考文章:https://www.cnblogs.com/DianaCody/p/5425630.html

转载请注明原文地址: https://www.6miu.com/read-2600134.html

最新回复(0)