导图社区 FP-growth算法项集效率提升方法总结

FP-growth算法项集效率提升方法总结

FP-growth算法项集效率提升方法总结：FP树：用于编码数据集的有效方式：树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。

编辑于2022-12-23 11:26:16 广东

FP-growth

凝

他的近期作品查看更多>>

FP-growth算法项集效率提升方法总结

社区模板帮助中心，点此进入>>

凝

他的近期作品查看更多>>

相似推荐
大纲

英语词性
- 62.9k
- 6.5k
- 2.4k
- 577
- 0
Ethan
互联网9大思维
- 39.1k
- 974
- 2.4k
- 401
- 0
MindMaster
组织架构-单商户商城webAPP 思维导图。
- 18.0k
- 3
- 186
- 9
- 1
Kacyun
法理
- 28.5k
- 67
- 376
- 49
- 1
Dasein
刑法总则
- 38.5k
- 148
- 966
- 156
- 0
Dasein
【华政插班生】文学常识-先秦
- 4.8k
- 4
- 70
- 2
- 0
Dasein
【华政插班生】文学常识-秦汉
- 2.9k
- 0
- 54
- 10
- 0
Dasein
文学常识：魏晋南北朝
- 4.0k
- 3
- 90
- 20
- 0
Dasein
【华政插班生】文学常识-隋唐五代
- 4.4k
- 8
- 98
- 6
- 0
Dasein
【华政插班生】文学常识-两宋
- 2.6k
- 5
- 70
- 8
- 0
Dasein

FP-growth算法项集效率提升方法总结

引言

FP-growth特点

更高效地发现频繁项集

不能用于发现关联规则

只需要对数据库进行两次扫描

发现频繁集的基本过程

构建FP树

从FP树中挖掘频繁项集

FP树：用于编码数据集的有效方式

优点

一般要快于Apriori

缺点

实现比较困难

在某些数据集上性能会下降

适用数据类型

标称型

Frequent Pattern（频繁模式）

FP树

通过链接来连接相似元素

一个元素项可以在一棵FP树中出现多次

FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中

存在相似元素的集合会共享树的一部分

只有当集合之间完全不同时，树才会分叉

树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数

节点链接

相似项之间的链接

用于快速发现相似项的位置

一般流程

收集数据

任意方法

准备数据

由于存储的是集合，所以需要离散数据

如果要处理连续数据，需要量化为离散值

分析数据

任意方法

训练算法

构建一个FP树，并对树进行挖掘

测试算法

无

使用算法

可用于识别经常出现的元素项，从而用于制定决策、推荐元素或进行预测

构建FP树

创建FP树的数据结构

name

count

nodeLink

parent

通常不需要

后续章节上溯时会用到

children

构建FP树

除FP树外，还需要一个头指针来指向给定类型的第一个实例

过程

第一次遍历数据集会获得每个元素项的出现频率

去掉不满足最小支持度的元素项，并排序

构建FP树

从空集开始

读入每个项集

路径不存在则创建

路径存在则增加现有元素的值

从一棵FP树中挖掘频繁项集

基本步骤

从FP树中获得条件模式基

利用条件模式基，构建一个条件FP树

迭代重复前两个步骤，直到树包含一个元素项位置

抽取条件模式基

条件模式基

以所查找元素项为结尾的路径集合

每一条路径都是一条前缀路径

即，一条前缀路径是介于所查找元素项和树根节点之间的所有内容

每一条前缀路径都与一个计数值关联

创建条件FP树

对于每个频繁项，都要创建一个条件FP树

过程

最初树以空集为根节点

把条件模式基中满足最小支持度的集合添加进来

对新的集合挖掘对应的条件树

直到条件树没有元素

示例：在Twitter源中发现一些共现词

python-twitter库