6.3 FP-growth算法在线视频

Apriori算法原理简单、易于理解

所以广为使用

但是Apriori算法

在挖掘过程中产生大量候选项集

而且需要多次扫描整个数据库

从而产生较大的开销

而FP-growth算法

能够避免Apriori算法候选过程的

巨大开销

有效地提高了效率

本节首先介绍

FP-growth算法的原理和应用

从Apriori算法的运行过程中

可以看出

该算法在每一步产生候选项目集时

循环产生的组合过多

产生大量候选项集

并且没有排除无用的候选项集

时间开销和空间开销都比较大

同时

每次计算项集支持度时

Apriori算法都会对

全部数据进行一次扫描比较

如果扫描一个大型数据库的话

会大大增加计算机系统的I/O开销

而这种代价是随着数据库的规模的增加

呈现出几何级数的增加态势

FP-growth算法采用

完全不同的方法

来发现频繁项集

该算法不同于Apriori算法的

“产生-测试”泛型

由于避免了不断生成候选项目队列

和不断扫描整个数据库进行比对的操作

FP-growth算法

大大降低了Aproir挖掘算法的

空间和时间的资源消耗

为了达到这样的效果

FP-growth算法

采用一种简洁的数据结构

叫做频繁模式树

即 FP-tree

FP-tree是事务数据集的

一种压缩表示方法

如图所示

它通过逐个读入事务

并把每个事务映射为

FP-树中的一条路径

且路径中的每个结点对应事务中的一个项

不同的事务如果有若干个相同的项

则它们在FP-tree中

用重叠的路径表示

用结点旁的数字标明该项的重复次数

作为项的支持度

因此

路径相互重叠越多

使用FP-树结构

表示事务数据集的压缩效果就越好

如果FP-tree足够小

且能够在内存中存储

则可以从这个内存的树结构中

直接提取频繁项集

而不必再重复地扫描

存放在硬盘上的事务数据集

FP-growth算法的原理是

首先扫描整个事务数据库

生成1项集的频繁集

并把它们按降序排列

排除支持度计数值

小于最小支持度阈值的项

产生结果集L

然后按照项集构造一棵FP-tree

同时依然保留其中的关联信息

最后再扫描事务数据库一次

由下往上循序进行挖掘

删除FP-tree 中的子节点

即可产生所需要的频繁模式

FP-growth算法是一种分治法

将提供频繁项集的数据库

压缩到FP-tree

但仍保持项集关联信息

压缩后的数据库分成一组条件数据库

每个数据库关联一个频繁项

并分别挖掘每个条件数据库

FP-growth算法的实现步骤如下

①第一次扫描事务数据集D

确定每个1项集的支持度计数

将频繁1项集按照支持度计数降序排序

得到排序后的频繁1项集集合L

②第二次扫描事务数据集D

读出每个事务并构建根结点为

null的FP-tree

i 创建FP-tree的根结点

用null标记

ii 将事务数据集D中的

每个事务中的集删除非频繁项

将频繁项按照L中的顺序

重新排列事务中项的顺序

并对每个事务创建一个分支

iii 当为一个事务考虑增加分支时

沿共同前缀上的每个结点的计数加1

为跟随前缀后的项创建结点并连接

iv 创建一个项头表

以方便遍历

每个项通过一个结点链

指向它在树中的出现

③从1项集的频繁项集中

支持度最低的项开始

从项头表的结点链头指针

沿循每个频繁项的链接

来遍历FP-tree

找出该频繁项的所有前缀路径

构造该频繁项的条件模式基

并计算这些条件模式基中每一项的支持度

④通过条件模式基

构造条件FP-tree

删除其中支持度低于

最小支持度阈值的部分

满足最小支持度阈值的部分则是频繁项集

⑤递归地挖掘每个条件FP-tree

直到找到FP-tree为空

或者FP-tree只有一条路径

该路径上的所有项的组合都是频繁项集

例 FP-growth算法

此例使用表中的事务数据

挖掘事务数据中的频繁项集

该数据集具有9个事务

设最小支持度为2

试使用FP-growth算法

挖掘表的事务数据中的频繁项集

① 首先找出所有频繁1项集

并计算其支持度计数

并按支持度计数逆序排列

得到频繁1项集L

此例中

L={{面包}：7

{牛奶}：6

{可乐}：6

{麦片}：4

{鸡蛋}：2}

按照L顺序并去掉非频繁项的事务数据集

如表中所示

并构造项头表

如图中左侧的表

包括项集 支持度计数及结点链头指针

建立树的根结点

用null表示

然后依次处理每个事务的数据

② TID=1的事务

“面包 可乐 麦片”

按照L的支持度计数从大到小排序

此事务包括 {面包：1}

{可乐：1} {麦片：1}

在FP-tree的根结点

null下产生一个分支

分支上依次产生新结点

“面包“ “可乐” “麦片”

将FP-tree的根结点null

连接到“面包”结点

“面包”结点连接到“可乐”结点

“可乐”结点连接到“麦片”结点

更新所有结点的支持度加1

③ 处理TID=2的事务

“牛奶 可乐”

按照L的支持度计数从大到小排序

此事务包括{牛奶：1} {可乐：1}

由于此时FP-tree

并不包含该事务的共同前缀

因此FP-tree需要产生一个新分支

分支上依次产生新结点

“牛奶“ “可乐”

根结点null与新产生的

“牛奶”结点相连

“牛奶”结点连接到“可乐”结点

并更新相关结点的支持度加1

④ 对于TID=3的事务

“牛奶 面包 麦片”

按照L的支持度计数从大到小排序

此事务包括{面包：1}

{牛奶：1} {麦片：1}

此时FP-tree中包含前缀{面包}

在“面包”结点下新建分支

分支上依次产生新结点“牛奶”和“麦片”

将“面包”结点连接到“牛奶”结点

将“牛奶”结点连接到“麦片”结点

并更新相关结点的支持度加1

⑤对于TID=4的事务“牛奶 可乐”

按照L的支持度计数从大到小排序

此事务包括{牛奶：1} {可乐：1}

此时FP-tree中

已经包含前缀{牛奶 可乐}

因此仅更新相关结点的支持度加1

⑥ 对于TID=5的事务

“面包 鸡蛋 麦片”

按照L的支持度计数从大到小排序

此事务包括{面包：1}

{麦片：1} {鸡蛋：1}

此时FP-tree中已有前缀{面包}

在“面包”结点下新建分支

分支上依次产生新结点

“麦片”和“鸡蛋”

将“面包”结点连接到“麦片”结点

将“麦片”结点连接到“鸡蛋”结点

并更新相关结点的支持度加1

⑦对于TID=6的事务

“牛奶 面包 可乐”

按照L的支持度计数从大到小排序

此事务包括{面包：1}

{牛奶：1} {可乐：1}

此时FP-tree中已经包含

前缀{面包 牛奶}

在此前缀路径中的

“牛奶”结点下新建分支

分支上新建一个结点“可乐”

将“牛奶”结点连接到“可乐”结点

并更新相关结点的支持度加1

⑧对于TID=7的事务

“牛奶 面包 鸡蛋 麦片”

按照L的支持度计数从大到小排序

此事务包括{面包：1} {牛奶：1}

{麦片：1} {鸡蛋：1}

此时FP-tree中已经包含

前缀{面包 牛奶 麦片}

在此前缀路径中的“麦片”结点下新建分支

分支上新建一个结点“鸡蛋”

将“麦片”结点连接到“鸡蛋”结点

并更新相关结点的支持度加1

⑨对于TID=8的事务

“牛奶 面包 可乐”

按照L的支持度计数从大到小排序

此事务包括{面包：1}

{牛奶：1} {可乐：1}

此时FP-tree中已经包含

前缀{面包、牛奶、可乐}

因此仅更新相关结点的支持度加1

⑩对于TID=9的事务“面包 可乐”

按照L的支持度计数从大到小排序

此事务包括{面包：1} {可乐：1}

此时FP-tree中已经包含

前缀{面包 可乐}

因此仅更新相关结点的支持度加1

至此

FP-tree创建完成

如图所示

图中项头表中的“结点链头指针”

指向该项在FP-tree中的第一个位置

在树中所有该项结点都有指针链接

从频繁1项集的集合中

支持度最低的项{鸡蛋}开始

向上找出所有前缀路径

从图中可以看出

项{鸡蛋}的前缀路径有

{面包 牛奶 麦片：1}

{面包 麦片：1}

而条件模式基由FP-tree中

项的前缀路径集组成

因此项{鸡蛋}的条件模式基为

{{面包 牛奶 麦片：1}

{面包 麦片：1}}

此处牛奶的支持度计数

对于项{鸡蛋}来说为1

小于最小支持度阈值

因此项{鸡蛋}的条件模式基中

包含路径{面包：2 麦片：2}

而不包含牛奶

得到项{鸡蛋}的条件FP-tree为

如图所示

根据项{鸡蛋}的条件FP-tree产生的

频繁项集的所有组合为

{{面包 鸡蛋：2}

{麦片 鸡蛋：2}

{面包 麦片 鸡蛋：2}}

对于项{麦片}的前缀路径有

{面包 可乐：1}

{面包 牛奶：2}和{面包：1}

条件模式基为{{面包 可乐：1}

{面包 牛奶：2} {面包：1}}

此处可乐的支持度计数

对于项{麦片}来说为1

小于最小支持度阈值

因此项{麦片}的条件FP-tree中

包含路径{面包：4 牛奶：2}

而不包含可乐

得到项{麦片}的条件FP-tree为

根据项{麦片}的条件

FP-tree产生的

频繁项集的所有组合为

{{面包 麦片：4}

{牛奶 麦片：2}

{面包 牛奶 麦片：2}}

对于项{可乐}的前缀路径有

{面包：2}

{面包 牛奶：2} {牛奶：2}

条件模式基为{{面包：2}

{面包 牛奶：2} {牛奶：2}}

此处每个项的支持度计数

都大于最小支持度阈值

因此项{可乐}的条件FP-tree中

包含路径

{面包：4 牛奶：2}和{牛奶：2}

根据项{可乐}的条件

FP-tree产生的

频繁项集的所有组合为

{{面包 可乐：4}

{牛奶 可乐：4}

{面包 牛奶 可乐：2}}

对于项{牛奶}的前缀路径有

{面包：4}

条件模式基为{{面包：4}}

此处面包项的支持度计数

大于最小支持度阈值

因此项{牛奶}的条件FP-tree中

包含路径{面包：4}

得到项{牛奶}的条件FP-tree

为

根据项{牛奶}的条件

FP-tree产生的

频繁项集的所有组合为

{{面包 牛奶：4}}

挖掘过程中形成的条件模式基

条件FP-tree

以及可以挖掘的频繁模式

如表所示

不论挖掘长的或短的频繁模式

FP-growth算法都是有效的

并且可伸缩的

相比于Apriori算法

运行速度要快一个数量级

FP-growth算法的优点是

减少没有候选集的产生

没有候选测试

使用简洁的数据结构

不需多次扫描数据库

节省了运行时间

采用分治方法

递归实现

但是FP-growth算法

在建立FP-tree时会占用大量空间

并且处理产生的条件树时占用很多资源