Data Ming 笔记频繁项之FP-growth

一、概述

Apriori 算法一个Breadth-first (i.e., level-wise) search,需要产生大量的candidates的项集。而FPGrowth Approach (J. Han, J. Pei, and Y. Yin, SIGMOD’ 00)是一个Depth-first search,可以避免产生大量的项集。
主要思路是:从局部的频繁项中从短的频繁项得到长的频繁项。
比如,在数据集DB中发现,“abc”是一个频繁项,即DB|abc,考察含有该频繁项的子项时发现d是该频繁项中的一个局部频繁项,则abcd也是一个频繁项。

二、算法步骤

基本思想 (分治):用FP-tree递归增长频繁集
方法
  1. 对每个项,生成它的 条件模式库, 然后是它的 条件 FP-tree
  2. 每个新生成的条件FP-tree,重复这个步骤
  3. 直到结果FP-tree为空, 或只含唯一的一个路径 (此路径的每个子路径对应的项集都是频繁集)
fp-growth-construct
步骤一
1.扫描数据库一次,得到只有一个项的项集,只是过滤出满足支持度阈值的项集。
2.把项按支持度递减排序。
3.再一次扫描数据库,建立FP-tree。
对DB中每个需要考察的记录,每个项集都是按照拍好序的顺序, f, c, a,b, m, p的顺序。
步骤二、查找每个项的条件模式库
  1. 从FP-tree的头表开始
  2. 按照每个频繁项的连接遍历 FP-tree
  3. 列出能够到达此项的所有前缀路径,得到条件模式库。

实例解释:

  • 如c,从根节点开始只有f,则项c的条件模式库是f,后面的数字表示有3次f出现的情况下出现了c
  • 同理,有3次fc出现的情况下出现了a
  • 而对于m,有2次fca出现的情况下出现了m,有一次出现fcab的情况下出现了m。
P-conditional Database

步骤2: 建立条件 FP-tree

对每个模式库
  1. 计算库中每个项的支持度
  2. 用条件模式库中的频繁项建立条件FP-tree

实例解释:如上一步骤中m的条件模式库未fca:2, fcab:1。表示有2次fca出现的时候出现了m,有1次fcab出现的时候出现了m。即f,c,a对于m的支持度分别都是3.构造m的频繁项fp-tree如下红色部分,去除了b因为support不够。得到右侧的m的fp-tree。则m相关的频繁项即:一元的m,二元的fm,cm,am,三元的fcm,fam,cam,和四元的fcam。

表示

  • 3次f出现的时候出现了m,3次m出现的时候出现了m,3次a出现的时候出现了m。
  • 3次fc出现的时候出现了m,三次fa出现的时候出现了m,三次ca出现的时候出现了m
  • 3次fca出现的时候出现了m

Conditional FP-trees

步骤三:同样递归的构造每个项的条件FP-tree。

构造m的,am,cm,cam的条件FP-tree下。

recurcive Conditional FP-trees

  • m的条件条件fp树在上面介绍过,对应的m的条件模式库也生成了。
  • am的的条件fp树如上例子,对应am的条件模式库为fc:3, 和am想过的频繁项为cam, fam, fcam
  • cm的的条件fp树如上例子,对应cm的条件模式库为f:3,和cm相关的频繁项为fcm
  • cam的的条件fp树如上例子,对应acm的条件模式库为f:3,和cm相关的频繁项为fcam

我理解的为什么cm的模式库为f:3, 而没有fa:3和a:3, 或者说第三个cm的条件fp树枝上为什么没有a是因为,构造fp树枝都是按照frequency倒排的,因此只有上面的推出下面,置信度才可能小于1,上面推出上面,全部是1,没有意义。虽然这个解释不是很准确看着,但是表达了那个意思,帮助理解。f=>cm的置信度是3/4=0.75?? a=>cm的置信度是3/3=1.0? fa=>cm的置信度是3/3=1.0

完。

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Data Ming 笔记频繁项之FP-growth


, ,

No comments yet.

发表评论