FP-Growth Algorithm
从item-freq数据构建FP Tree
假设我们目前有如下数据,假设Threshold为3:

首先统计频率

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

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

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

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

我们需要一个Horizontal link来连接所有分支中的相同元素(如上图所示)
FP-growth Algorithm
- 构建FP Tree
- 对于每个Item,构建conditional FP Tree,具体而言就是对于前缀为当前元素的所有序列构建FP Tree,这个conditional FP Tree以前缀元素作为根节点
- 如果conditional FP Tree不是只有一个分支,那么对于所有节点,继续构建conditional FP Tree,直到只有一个分支
- 根据所有的conditional FP Tree,生成frequent item set。具体而言,如果只有一个分支,那么要列出所有组合,如果有多个分支,只列出根节点。
Example
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Li Zhenghao🚴!