FP-Growth算法流程图

4

F:2

C:3

F:1

A，C，D

E

A，C，E，B，F

E:2

G:1

E:1

1

节点G有两个叶子节点，同理，将所有的父节点设置为叶子节点的计数值，G的一个叶子节点的值低于阈值，所以删除

I

A:2

null

TID

假设阈值为20%

2

E:8

E:4

A，C，G

A，C，E，G

A，B，C，E，F

B:2

G:8

A:8

得到C的频繁2-项集：{A:8，C:8}

A:6

3

C:2

7

B:1

C:8

A，C，E，G，L

对于节点G

G:4

设置最小支持度阈值为20%，删除小于最小支持度阈值的项

L

50%

原始事务集

D:1

表头项

8

G:5

B

A，C，D，E，G

得到G的频繁2-项集：{A:5，G:4}，{C:5，G:4}，{E:4，G:4}递归合并，得到G的频繁3-项集：{A:5，C:5，G:4}，{A:5，E:4，G:4}{C:5，E:4，G:4}G的频繁4-项集：{A:5，C:5，E:4，G:4}

10

9

C

E:6

A:5

10%

得到F的频繁2-项集为：{A:2，F:2}，{C:2，F:2}{E:2，F:2}，{B:2，F:2}递归合并2-项集，F的频繁3-项集为：{A:2，C:2，F:2}，{A:2，E:2，F:2}{A:2，B:2，F:2}，{C:2，E:2，F:2}{C:2，B:2，F:2}，{E:2，B:2，F:2}递归合并3-项集，F的频繁4-项集为：{A:2，C:2，E:2，F:2}，{A:2，C:2，B:2，F:2}{A:2，E:2，B:2，F:2}，{C:2，B:2，E:2，F:2}频繁5-项集为：{A:2，C:2，E:2，B:2，F:2}

5

6

对于节点D

G

D:2

F

C:1

事务中的项

得到B的频繁2-项集：{A:2，B:2}，{C:2，B:2}，{E:2，B:2}递归合并，得到B的频繁3-项集：{A:2，C:2，B:2}，{A:2，E:2，B:2}{C:2，E:2，B:2}递归合并，得到B的频繁4-项集：{A:2，C:2，E:2，B:2}

20%

处理之后的事务集

事务集

C:6

J

A，C，E，G，N

A，C，E，G，D

A

将每个事务中的项按照支持度降序排列

E，J

M

A，B，C，E，F，P

80%

得到节点C的条件模式基

得到D的频繁2-项集为：{A:2，D:2}，{C:2，D:2}递归合并，得到D的频繁3-项集：{A:2，C:2，D:2}

A，C，E，G，M

对于节点F

C:5

计算每个项的支持度计数，得到支持度

删除每个事务中的低于最小支持度阈值的项

项

A:1

E的条件模式基

A:3

E，I

得到D的条件模式基

A，B，C，E，F，O

对于节点E

由于节点A的条件模式基为空，所以不用挖掘

支持度

节点D有2个叶子节点，所以将所有的父节点计数设置为叶子节点的计数，由于E和G的支持度低于20%的阈值，所以删除

P

将所有父节点的计数设置为叶子节点的计数。一般条件模式基可以不写叶子节点

对于节点C

N

对于节点B

G的条件模式基

O

支持度计数

得到E的频繁2-项集：{A:6，E:6}，{C:6，E:6}E的频繁3-项集：{A:6，C:6，E:6}

D