前言：
关于 FP-Growth 算法介绍请见：FP-Growth算法的介绍。 本文主要介绍 FP-tree 的构造算法，关于伪代码请查看上面的文章。
上接：FP-Growth算法python实现；下接：FP-Growth算法之频繁项集的挖掘（python）。
正文：
文件：
#coding=utf-8import tree_building:, counts=[], headerTable={}):”””类的初始化。 routines:事务数据集; min_sup:最小支持度及数; counts:每个事务出现的次数,默认为1; headerTable:头结点表,建造的FP_tree各结点的索引表。”””self.routines = routinesself.counts = countsself.min_sup = min_supself.items = self.getItems(self.routines)#获取所有项self.sortedItems = self.getSortedItems(self.items)#对所有项进行并排序,把计数小于min_sup的项移除，生成有序的频繁1-项集self.itemsTable = self.initItemsTable(headerTable)self.tree = self.treeBuilding(self.counts):”””功能:扫描事务数据集,返回它的项集即各项的计数”””items = {}for routine in routines:for elem in routine:items.setdefault(elem,0)items[elem] += 1return items:”””功能:对项集进行排序,并删去非频繁项,得到频繁1-项集”””sortedItems = []temp = sorted(items.iteritems(), key=lambda asd:asd[1], reverse=True)#对字典items进行排序for elem in temp:if elem[1] >= self.min_sup:#只取计数大于等于最小支持度及数的项sortedItems.append(elem[0])return sortedItems:”””功能:根据排序好的频繁1-项集对某一条事务routine进行排序”””sortedRoutine = []for elem in self.sortedItems:if elem in routine:sortedRoutine.append(elem)return sortedRoutine:”””功能:头结点表的初始化”””for item in self.sortedItems:itemsTable.setdefault(item,[])return itemsTable:”””功能:逐条取出事务,控制FP_Tree树的构造”””tree = tree_building.Tree(itemTable=self.itemsTable)#生成一个树对象for routine in self.routines:#对事物数据集中的事务，逐条进行构造树sortedRoutine = self.getSortedRoutine(routine)#用一条事务构造树之前先进行排序if counts:#如果counts不为空，，即是在用模式基在构造条件树，此时需要考虑模式基的计数count = counts.pop(0)else:count =1tree.addRoutine(routine=sortedRoutine, Rroot=tree.root, count=count)#用排序好的事务构造树return tree
tree_builder.py 文件主要实现两个动作：
数据预处理（包括项的搜索和排序、头结点表的初始化、事务的排序等）根据事务，调用 Tree.addRoutine() 构造树。
文件：
:, count=0, parent=None):”””Node类的初始化, 一个节点信息包括:项的值,计数,父亲节点,所有孩子节点”””self.data = dataself.count = countself.parent = parentself.children = {}:, parent=None, itemTable=None):”””tree_growth类的初始化,开辟一个树根”””self.root = Node(data=’null’, parent=self)self.itemTable = itemTable:elem = routine.pop(0)if elem in Rroot.children:#如果事务中的元素在树的已有路径上nextNode = Rroot.children[elem]#如果事务中的元素在树的已有路径上 ，则不用新建路径 else:#否则，新建一条路径newNode = Node(data=elem, parent=Rroot)#新建一个节点Rroot.children.setdefault(elem,newNode)#新节点的路径放在当前节点的孩子列表中nextNode = newNodenextNode.count += countself.itemTable[elem]:#如果下一个节点是新建的，则把它压入头结点表中self.itemTable[elem].append(nextNode)self.addRoutine(routine=routine, Rroot=nextNode, count=count)#递归构造树return
tree_building.py文件主要包含两个类：
Node类用来存放树节点信息。Tree类主要实现树的构造。addRoutine() 方法根据事务 routine 中的项递归构造树。
FP-Growth算法python实现（完整代码）。 备注：该代码是在 Python2.7+eclipse 环境下编写的。可在eclipse中导入项目，也可在命令行窗口用python命令执行“__init__.py”文件。
有时我们选择改变，并非经过深思熟虑，
