在 第11章 时我们已经介绍了用
算法发现
- Apriori
与
- 频繁项集
。本章将继续关注发现
- 关联规则
这一任务,并使用
- 频繁项集
算法更有效的挖掘
- FP-growth
。
- 频繁项集
的数据结构结构来存储集合。下面我们会介绍这种数据结构。
- FP树
- class treeNode:
- def __init__(self, nameValue, numOccur, parentNode):
- self.name = nameValue # 节点名称
- self.count = numOccur # 节点出现次数
- self.nodeLink = None # 不同项集的相同项通过nodeLink连接在一起
- # needs to be updated
- self.parent = parentNode # 指向父节点
- self.children = {} # 存储叶子节点
基于数据构建FP树
步骤1:
步骤2: 6. 读取每个集合插入FP树中,同时用一个头部链表数据结构维护不同集合的相同项。
最终得到下面这样一棵FP树
从FP树中挖掘出频繁项集
步骤3:
FP-growth 算法优缺点:
- * 优点: 1. 因为 FP-growth 算法只需要对数据集遍历两次,所以速度更快。
- 2. FP树将集合按照支持度降序排序,不同路径如果有相同前缀路径共用存储空间,使得数据得到了压缩。
- 3. 不需要生成候选集。
- 4. 比Apriori更快。
- * 缺点: 1. FP-Tree第二次遍历会存储很多中间过程的值,会占用很多内存。
- 2. 构建FP-Tree是比较昂贵的。
- * 适用数据类型:标称型数据(离散型数据)。
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/12.FrequentPattemTree/fpGrowth.py
main 方法大致步骤:
- if __name__ == "__main__":
- simpDat = loadSimpDat() #加载数据集。
- initSet = createInitSet(simpDat) #对数据集进行整理,相同集合进行合并。
- myFPtree, myHeaderTab = createTree(initSet, 3)#创建FP树。
- freqItemList = []
- mineTree(myFPtree, myHeaderTab, 3, set([]), freqItemList) #递归的从FP树中挖掘出频繁项集。
- print freqItemList
大家看懂原理,再仔细跟踪一下代码。基本就没有问题了。
来源: http://www.cnblogs.com/jiangzhonglian/p/7778830.html