机器学习之手把手实现,第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现-3
- UID
- 1066743
|
机器学习之手把手实现,第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现-3
代码下载 (code downloads)本文所有 FP-growth 实现代码可在文末下载。
本文数据集简介图 7. 数据集样例数据集是购物车数据。每一条代表了一条购物车信息。目的是要挖掘出在购物车中频繁共同出现的集合,并根据此频繁项集挖掘出关联规则。关联规则暗示频繁项集之间存在的关系,如购买了面包的人,有很高的可能性会同时购买牛奶。
应用示例: 应用实现的 FP-growth 解决实际问题清单 7. 用 FP-growth 解决实际问题1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| if __name__=='__main__':
print("fptree:")
dataSet = loadDataSet()
frozenDataSet = transfer2FrozenDataSet(dataSet)
minSupport = 3
fptree, headPointTable = createFPTree(frozenDataSet, minSupport)
fptree.disp()
frequentPatterns = {}
prefix = set([])
mineFPTree(headPointTable, prefix, frequentPatterns, minSupport)
print("frequent patterns:")
print(frequentPatterns)
minConf = 0.6
rules = []
rulesGenerator(frequentPatterns, minConf, rules)
print("association rules:")
print(rules)
|
清单 5 中的代码首先加载数据集,然后通过调用前面实现的 FP-growth 代码,先是构造 FP 树,接着从 FP 树中挖掘频繁项集,最后从频繁项集中产生关联规则,并输出置信度。
表 4. 频繁项集的结果示例频繁项集支持度 (Support) {'gloves'}
0.5 {'shoes', 'socks'}
0.5 {'milk', 'eggs', 'bread'}
0.5 {'bread'}
0.5 {'milk', 'bread'}
0.5 {'gloves', 'socks'}
0.5 {'shoes'}
0.5 {'eggs', 'bread'}
0.5 {'eggs'}
0.5 {'milk'}
0.67 {'socks'}
0.67 {'milk', 'eggs'}
0.5
从表 4 中可以看出,鞋子与袜子,牛奶与面包,面包与鸡蛋,牛奶与鸡蛋,手套与袜子,牛奶、鸡蛋与面包等项在数据集中共同出现得很频繁。
表 5. 关联规则的结果示例关联规则置信度 (Confidence) {'socks' }-> {'shoes'}
0.75 {'shoes'} -> {'socks'}
1.0 {'eggs', 'bread'} -> {'milk'}
1.0 {'bread'} -> {'milk', 'eggs'}
1.0 {'eggs'} -> {'milk', 'bread'}
1.0 {'milk', 'bread'} -> {'eggs'}
1.0 {'milk'} -> {'eggs', 'bread'}
0.75 {'milk', 'eggs'} -> {'bread'}
1.0 {'bread'} -> {'milk'}
1.0 {'milk'} -> {'bread'}
0.75 {'socks'} -> {'gloves'}
0.75 {'gloves'} -> {'socks'}
1.0 {'bread'} -> {'eggs'}
1.0 {'eggs'} -> {'bread'}
1.0 {'eggs'} -> {'milk'}
1.0 {'milk'} -> {'eggs'}
0.75
从表 5 中可以看出某人购买了鞋子,极有可能会同时购买袜子;某人购买了鸡蛋与面包,极有可能会购买牛奶;某人购买了手套,极有可能会购买袜子。但是需注意,关联规则反过来不一定同样成立,拿第一条和第二条结果为例,由鞋子推出袜子的置信度是 1.0,但是反过来,由袜子推出鞋子的置信度只有 0.75,而并不是 1.0。
总结本文首先介绍了频繁项集和关联规则在现实场景中的应用,接着介绍了频繁项集和关联规则挖掘的原理,然后通过代码样例,介绍了在自己动手实现 FP-growth 模型时的思路。最后,用购物车数据展示了如何应用 FP-growth 解决实际问题。需要注意的是,FP-growth 算法本身对于海量数据仍然会很慢,虽然其只需要扫描数据库两次,但是对于海量数据在内存中建立一份统一的 FP 树结构是不大现实的。这就需要考虑采用并行计算的思路来并发实现 FP-growth,利用多台电脑并行执行 FP-growth,从而加速运算。并行 FP-growth 的具体实现方法可以参考文献 2 所列的论文。由于篇幅有限,这部分内容不在本次内容中展开,预计后期会对这部分内容进行专门介绍。 |
|
|
|
|
|