从item-freq数据构建FP Tree

假设我们目前有如下数据,假设Threshold为3:

image-20250515000908804

首先统计频率

image-20250515000947616

筛选掉小于threshold的item,按照frequency倒序和alphabet顺序进行排序

image-20250515001030776

根据该顺序重新对原数据进行排列

image-20250515001145603

随后构建FP-tree。一开始只有一个root节点,然后根据节点到来的顺序,构建FP-tree,对于第一条数据,其结果如下:

image-20250515001307889

对于后续的数据,如果前缀相同,则对于元素加1,如果不同,则分叉。最终如下:

image-20250515002006481

我们需要一个Horizontal link来连接所有分支中的相同元素(如上图所示)

FP-growth Algorithm

  1. 构建FP Tree
  2. 对于每个Item,构建conditional FP Tree,具体而言就是对于前缀为当前元素的所有序列构建FP Tree,这个conditional FP Tree以前缀元素作为根节点
  3. 如果conditional FP Tree不是只有一个分支,那么对于所有节点,继续构建conditional FP Tree,直到只有一个分支
  4. 根据所有的conditional FP Tree,生成frequent item set。具体而言,如果只有一个分支,那么要列出所有组合,如果有多个分支,只列出根节点。

Example

Page1

Page2