算法采用FPTree的紧凑数据结构组织数据,并直接从该结构中提取频繁项集,而不是Apriori算法的产生-测试范型。

1 FP树生成

树中每个节点都包括一个项的标记和一个计数,计数显示映射到给定路径的transaction个数。初始,FP树仅包含一个root节点,用NULL表示;随后,用如下方法扩充FP树

  • 扫描一次数据集,确定每个项的支持度计数,丢弃非频繁项,而将频繁项按照支持度的递减排序;
  • 算法第二次扫描数据集,构建FP树,读入第一个事物{a,b}之后,创建标记为a和b的节点,形成null—>a—>b的路径,对该事物进行编码,该路径上所有节点的频度计数为1;
  • 读入第二个事物{b,c,d}之后,为项b、c和d创建新的节点集,然哦户连接节点null->b->c->d,形成一条代表该事物的路径,该路径上每个节点频度计数等于1.尽管前两个事物具有一个共同项b,但路径不相交,因为两个事物没有共同前缀
  • 第三个事物{a,c,d,e} 与第一个事物共享前缀a,所以第三个事物的路径与第一个事物的路径有部分重叠,所以节点a的频度计数增长为2
  • 继续该过程,直到每个事物都映射到FP树的一条路径。

1.png

FP树包括以下特性

  1. 通常FP树的大小比未压缩的数据小
  2. FP树的大小也取决于项的排序方式
  3. FP树还包含一个连接具有相同项的节点的指针列表,这些指针在图中用虚线表示,有助于方便快速访问树中的项。

2 FP-Growth算法的频繁项集产生

FP-growth是一种以自底向上方式搜索树,由FP树产生频繁项集的算法。首先查找以e结尾的频繁项集,然后查找以d、c、b、a结尾的频繁项集。

  1. 第一步收集包含e节点的所有路径,这些初始的路径称为前缀路径,prefix path
  2. 通过把与节点e相关联的支持度计数相加得到e的支持度计数,假定最小支持度为2,则e的支持度是3所以它是频繁项集
  3. 由于{e}是频繁的,因此算法必须解决发现以de、ce、be、和ae结尾的频繁项集的子问题。在解决这些子问题之前,必须先将前缀路径转化为条件FP树。除了用于发现以某特定后缀结尾的频繁项集之外,条件FP树的结构与FP树类似,条件FP树通过以下步骤得到
    • 首先更新前缀路径上的支持度计数,因为某些计数包括那些不含项e的事物
    • 删除e的节点,修改前缀路径。删除这些节点是因为沿这些前缀路径的支持度计数已经更新,以反映包含e的那些事物,并且发现以de、ce、be和ae结尾的频繁项集的子问题不再需要节点e的信息
    • 更新演前缀路径上的支持度计数之后,某些项可能不再是频繁的,例如节点b只出现了1次,他的支持度计数等于1,这意味着只有一个事务同时包含b和e,因为所有以be结尾的项集一定是非频繁的(我们之前假定了最小支持度是2),所以在其后的分析中可以安全地忽略b
  4. FP-growth使用e的条件FP树来解决发现以de、ce、be和ae结尾的频繁项集的子问题。为了发现以de结尾的频繁项集,从项e的条件FP树收集d的所有前缀路径。通过将与节点d相关联的频度计数求和,得到项集{d, e}的支持度计数。因为项集「d,e」的支持度计数等于2,所以是频繁项集。接下来,算法采用第三步介绍的方法构建de的条件FP树。更新了支持度并删除了非频繁项c之后,de的条件FP树得到。因为该条件FP树只包含一个支持度等于最小支持度的项a,算法提取出频繁项集{a, d, e}并转到下一个子问题,产生以ce结尾的频繁项集。处理c的前缀路径后,只发现项集{c,e}是频繁的,接下来,算法急需解决下一个子问题并发现项集{a, e}是剩下唯一的频繁项集。

2.png

登录发表评论 注册

反馈意见