文档介绍：机器学****FP-GROWTH算法
李家豪
.精品课件.
1
目录
2
.精品课件.
回忆Apriori算法
3
项集：项的集合称为项集，即商品的组合。
k项集：k件商品的组合，不关心商品件数，仅商品的种类。
频繁项集：如果项集的相对支持度满足给定的最小支持度阈值，则该项集是频繁项集。
强关联规则:满足给定支持度和置信度阈值的关联规则
支持度：support(A->B) = P(AB)
置信度：confidence(A->B) = P(A|B)
.精品课件.
回忆Apriori算法
4
.精品课件.
回忆Apriori算法
5
.精品课件.
Apriori算法的挑战
6
挑战
多次数据库扫描
巨大数量的候补项集
繁琐的支持度计算
改善Apriori: 基本想法
减少扫描数据库的次数
减少候选项集的数量
简化候选项集的支持度计算
.精品课件.
FP-GROWTH算法优点
相比Apriori算法需要多次扫描数据库，FPGrowth只需要对数据库扫描2次。
第1次扫描事务数据库获得频繁1项集。
第2次扫描建立一颗FP-Tree树。
7
.精品课件.
FP-GROWTH算法原理-实例1
要找总是一起购买的商品，比如[薯片，鸡蛋]就是一条频繁模式(规律)。
8
ID
Items
1
牛奶，鸡蛋，面包，薯片
2
鸡蛋，爆米花，薯片，啤酒
3
牛奶，面包，啤酒
4
牛奶，鸡蛋，面包，爆米花，薯片，啤酒
5
鸡蛋，面包，薯片
6
鸡蛋，面包，啤酒
7
牛奶，面包，薯片
8
牛奶，鸡蛋，面包，黄油，薯片
9
牛奶，鸡蛋，黄油，薯片
.精品课件.
FP-GROWTH算法原理-实例1-统计频次
Step1:先扫描数据库，统计所有商品的出现次数(频数)，然后按照频数递减排序，删除频数小于最小支持度的商品。
设最小支持度数为：minsup=4
统计频数：
牛奶6，鸡蛋7，面包7，薯片7，爆米花2，啤酒4，黄油2.
降序排序：
薯片7,鸡蛋7,面包7,牛奶6,啤酒4（删除小于minsup的商品）
9
ID
Items
1
牛奶，鸡蛋，面包，薯片
2
鸡蛋，爆米花，薯片，啤酒
3
牛奶，面包，啤酒
4
牛奶，鸡蛋，面包，爆米花，薯片，啤酒
5
鸡蛋，面包，薯片
6
鸡蛋，面包，啤酒
7
牛奶，面包，薯片
8
牛奶，鸡蛋，面包，黄油，薯片
9
牛奶，鸡蛋，黄油，薯片
频繁1项集，记为F1
.精品课件.
FP-GROWTH算法原理-实例1-重新排序
10
ID
Items
1
牛奶，鸡蛋，面包，薯片
2
鸡蛋，爆米花，薯片，啤酒
3
牛奶，面包，啤酒
4
牛奶，鸡蛋，面包，爆米花，薯片，啤酒
5
鸡蛋，面包，薯片
6
鸡蛋，面包，啤酒
7
牛奶，面包，薯片
8
牛奶，鸡蛋，面包，黄油，薯片
9
牛奶，鸡蛋，黄油，薯片
ID
Items
1
薯片,鸡蛋,面包,牛奶
2
薯片,鸡蛋,啤酒
3
面包,牛奶,啤酒
4
薯片,鸡蛋,面包,牛奶,啤酒
5
薯片,鸡蛋,面包
6
鸡蛋,面包,啤酒
7
薯片,面包,牛奶
8
薯片,鸡蛋,面包,牛奶
9
薯片,鸡蛋,牛奶
Step2:对每一条数据记录，按照F1重新排序。
.精品课件.