机器学习之手把手实现，第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现-3

look_w

代码下载 (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    所列的论文。由于篇幅有限，这部分内容不在本次内容中展开，预计后期会对这部分内容进行专门介绍。