从零实现机器学习算法（十四）FP-growth

本文主要是介绍从零实现机器学习算法（十四）FP-growth，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1. FP-growth简介

2. FP-growth模型

2.1 FP-growth数据结构

2.2 频繁项集

2.3 关联规则

3. 总结与分析

---

1. FP-growth简介

FP-growth也是一种经典的频繁项集和关联规则的挖掘算法，在较大数据集上Apriori需要花费大量的运算开销，而FP-growth却不会有这个问题。因为FP-growth只扫描整个数据库两次。由于FP-growth算法比较复杂，本文有遗漏之处敬请希望见谅。

2. FP-growth模型

2.1 FP-growth数据结构

FP-growth算法需要使用FP树和一个头结点链表。FP树与普通的树类似，但是它通过指针链接相同的元素。这里采用 Machine Learning IN ACTION 里面的例子作为讲解，数据集对应的头结点表链表FP树如下所示。

• 数据集

• 数据集对应FP树

 

 

首先我们会发现数据集中的有些元素，在头结点链表和FP树中并没有出现，如o, n, m等。这是因为它们不满足大于最小支持度的要求（这里最小支持度设为3，在Apriori中最小支持度是个比值，这里和它不一样）。因此我们可以得出构建FP树的第一步：

1. 遍历数据集，统计每个元素出现的频数，删除频数小于最小支持度的元素并将剩余元素和其频数写入头结点链表。

        initial_header = {}# 1. the first scan, get singleton setfor record in train_data:for item in record:initial_header[item] = initial_header.get(item, 0) + train_data[record]# get singleton set whose support is greater than min_support. If there is no set meeting the condition,  return noneheader = {}for k in initial_header.keys():if initial_header[k] >= self.min_support:header[k] = initial_header[k]frequent_set = set(header.keys())if len(frequent_set) == 0:return None, Nonefor k in header:header[k] = [header[k], None]

从图中可以看到头结点链表包含两部分，一部分是单元素集合的频数，另一部分是一个指针，指向FP树中对应的元素。因此在上述代码中我们采用字典存储头结点链表，并且在最后两行，我们对头结点链表的值进行扩充，添加用于存储指针的部分。接下来就可以进行第二遍遍历，构建FP树。首先定义FP树的数据结构，其中item是指结点所对应的元素项，count是其对应的频数，parent是其双亲结点，children是其孩子结点。

class FPNode:def __init__(self, item, count, parent):self.item = itemself.count = count              # supportself.parent = parentself.next = None                # the same elementsself.children = {}

构建FP的第二步：

2. 遍历数据集，当待添加的记录与 FP 树中的路径相同只需要更新元素对应的频数，否则，在路径不同的地方产生分支，创建新的结点。代码首先定义了根节点，然后遍历数据集。每次读入一个数据集中的记录，将该记录中的频繁项集支持度存入头结点链表的第一个域。如果该记录的频繁项集存在，则将其中的数据按出现次数由高到低排序，然后更新树。

        FP_tree = FPNode('root', 1, None)        # root nodefor record, count in train_data.items():frequent_item = {}for item in record:                # if item is a frequent set， add itif item in frequent_set:       # 2.1 filter infrequent_itemfrequent_item[item] = header[item][0]if len(frequent_item) > 0:ordered_frequent_item = [val[0] for val in sorted(frequent_item.items(), key=lambda val:val[1], reverse=True)]  # 2.1 sort all the elements in descending order according to countself.updataTree(ordered_frequent_item, FP_tree, header, count) # 2.2 insert frequent_item in FP-Tree， share the path with the same prefix

更新树的代码为如下。首先获取排序后的频繁项集的第一个元素，如果该元素在FP树中，则其对应结点支持度加上该元素对应的频数。如果该元素不在FP树中，建立该元素的新结点。如果头结点链表中没有指向改元素的指针，则头结点链表指针域添加对应的指针。否则，更新头结点指针。

    def updataTree(self, data, FP_tree, header, count):frequent_item = data[0]if frequent_item in FP_tree.children:FP_tree.children[frequent_item].count += countelse:FP_tree.children[frequent_item] = FPNode(frequent_item, count, FP_tree)if header[frequent_item][1] is None:header[frequent_item][1] = FP_tree.children[frequent_item]else:self.updateHeader(header[frequent_item][1], FP_tree.children[frequent_item]) # share the same pathif len(data) > 1:self.updataTree(data[1::], FP_tree.children[frequent_item], header, count)  # recurrently update FP tree

更新头结点指针代码如下。head_node为起始结点，tail_node为末尾结点，即从头指针开始一直往相同元素方向走，知道走到头，将其next域指向tail_node。我们看下传入的参数

self.updateHeader(header[frequent_item][1], FP_tree.children[frequent_item]) 就好理解了，就是将头结点的指针，指向FP树中相同的元素。

    def updateHeader(self, head_node, tail_node):while head_node.next is not None:head_node = head_node.nexthead_node.next = tail_node

以上就是构建FP树的完整流程，下面用实例来说明强化理解。我们首先看下过滤和排序后的数据。

• 过滤和排序后的数据

• 首先读入第一条记录（z,r）由于树初始为空，直接添加即可

 

• 读入第二条记录（z,x,y,s,t）,首元素z在FP树中，FP树中的结点z，count值增加，然后进行递归每次从当前的下一个元素开始访问。由于第二个元素x不在FP树中，在FP树中创建对应的结点，然后在header中创建相应的指针。后续结点在x的结点分支后进行。指的注意的是r在访问（z,r）时已经存在了，因此第一个r结点的next域指向这次的r结点。后续记录以此类推知道构成完成的FP树。

 

2.2 频繁项集

在得到FP树的基础之上，就可以挖掘频繁项集了。首先获得频繁项的前缀路径，然后将前缀路径作为新的数据集构建条件FP树。然后在新的FP树中获得频繁项并以此构建条件FP树。如此反复，直到条件FP树中只有一个频繁项为止。

 def findFrequentItem(self, header, prefix, frequent_set):# for each item in header, then iterate until there is only one element in conditional fptreeheader_items = [val[0] for val in sorted(header.items(), key=lambda val: val[1][0])]if len(header_items) == 0:returnfor base in header_items:new_prefix = prefix.copy()new_prefix.add(base)support = header[base][0]frequent_set[frozenset(new_prefix)] = supportprefix_path = self.getPrefixPath(base, header)if len(prefix_path) != 0:conditonal_tree, conditional_header = self.createFPTree(prefix_path)if conditional_header is not None:self.findFrequentItem(conditional_header, new_prefix, frequent_set)

举个例子，我们以y元素为例，由它的前缀路径构成条件FP树如图所示。值得注意的是z,x的频数都是3，这是因为它们与y同时出现的频数是3。此时，频繁项集的规则为

• 对于元素z来说，其前缀路径为{}，则返回频繁项集{y, z}
• 对于元素x来说，其前缀路径为{z}, 对{z}构建条件FP树，如图所示。由于此时条件FP树只有一个元素，故返回频繁项集{y,x,z}。因为元素y本身也是频繁项集，因此{y,x}也是频繁项
• 故y对应的频繁项集有{y}, {y, z}, {y, x}, {y, x, z}

 

• FP树

 

• y的前缀路径生成的条件FP树

 

• 前缀路径为{z}的条件FP树

2.3 关联规则

由FP树挖掘关联规则,较为简单，首先由频繁项集构建所有可能的规则，然后计算每个规则的置信度，满足大于最小置信度的条件的规则为合理的关联规则。

    def generateRules(self, frequent_set, rules):for frequent_item in frequent_set:if len(frequent_item) > 1:self.getRules(frequent_item, frequent_item, frequent_set, rules)def getRules(self, frequent_item, current_item, frequent_set, rules):for item in current_item:subset = self.removeItem(current_item, item)confidence = frequent_set[frequent_item]/frequent_set[subset]if confidence >= self.min_confidence:flag = Falsefor rule in rules:if (rule[0] == subset) and (rule[1] == frequent_item - subset):flag = Trueif flag == False:rules.append((subset, frequent_item - subset, confidence))if (len(subset) >= 2):self.getRules(frequent_item, subset, frequent_set, rules)

3. 总结与分析

FP-growth由于只遍历数据集两遍，因此其时间复杂度不会很高。但是对于海量数据在内存中建立一份统一的 FP 树结构是不大现实的。这就需要考虑采用并行计算的思路来并发实现 FP-growth。使用和Apriori一样的数据集

其结果为

 

本文相关代码和数据集：https://github.com/DandelionLau/MachineLearning

[1] Peter Harrington,Machine Learning IN ACTION

这篇关于从零实现机器学习算法（十四）FP-growth的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---