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

look_w

本文将介绍机器学习领域经典的 FP-growth（Frequent Pattern Growth）模型，它是目前业界经典的频繁项集和关联规则挖掘的算法。相比于 Apriori    模型，FP-growth 模型只需要扫描数据库两次，极大得减少了数据读取次数并显著得提升了算法效率。您将看到 FP-growth 的原理介绍、FP-growth    实现步骤和详解、FP-growth 实现代码以及用 FP-growth 解决实际的频繁项集和关联规则挖掘问题。通过阅读本文，您会对 FP-growth 的原理了如指掌，并可以自己开发出    FP-growth 的实现代码。
从啤酒和尿布引出的频繁项集在机器学习系列文章中，主要介绍了支持向量机 SVM 模型的原理和实现。在文章一开始，笔者提到机器学习主要分为四大类，分别是分类，聚类，回归和关联分析。第一篇中的 SVM    就属于分类。那么下面笔者开始介绍关联分析。关联分析分为频繁项集挖掘和关联规则挖掘。
生活中的数据本身包含着各种规律，机器学习模型可以从数据中挖掘出这些规律，啤酒与尿布就是一个典型的例子。有研究发现，在超市的订单记录中，啤酒和尿布总是频繁共同出现在同一条订单记录里。换句话说，买尿布的人，往往会顺手买啤酒。这就引出了本文的主题之一，即频繁项集。频繁项集是在数据库中大量频繁出现的数据集合。那么发现这些频繁项集有什么意义呢？

• 用于制定营销策略。如同啤酒与尿布的例子，超市如果将啤酒和尿布放在相邻的位置，会增加两者的销量。还可用于制定打折促销活动，给买了啤酒和尿布的客户打折，也可以增加销量。
• 用于发现共现词。这种场景其实我们经常会遇到。当我们在浏览器中输入"频繁项集"时，浏览器自动弹出如"频繁项集 置信度"，"频繁项集     关联规则"等备选记录，我们每每都会感叹浏览器的智能，其实这里的秘诀就是频繁项集。也就是说，在大量的用户搜索记录中，"频繁项集"和"置信度"共同出现在了大多数的搜索记录中。同理，"频繁项集"和"关联规则"也频繁得共同出现在搜索记录中。
• 用于发现事物的热点信息。从新闻报道和微博中获取关于某事物的相关文档，然后应用频繁项集挖掘算法可以得到该事物的热点新闻。

主流的频繁项集挖掘算法有 Apriori 和 FP-growth。其中 Apriori 算法需要多次扫描数据库，这就使得该算法本身不适合大数据量。FP-growth，即 Frequent    Pattern Growth，它通过构建 FP 树(即 Frequent Pattern Tree)这样的数据结构，巧妙得将数据存储在 FP 树中，只需要在构建 FP    树时扫描数据库两次，后续处理就不需要再访问数据库了。这种特性使得 FP-growth 算法比 Apriori 算法速度快。FP    树是一种前缀树，由频繁项的前缀构成，具体细节会在频繁项集挖掘原理一节介绍。挖掘出频繁项集后，可以从频繁项集中进一步挖掘关联规则。
关联规则简介关联规则是在频繁项集的基础上得到的。关联规则指由集合 A，可以在某置信度下推出集合 B。通俗来说，就是如果 A 发生了，那么 B    也很有可能会发生。举个例子，有关联规则如：{'鸡蛋', '面包'} -> {'牛奶'}，该规则的置信度是 0.9，意味着在所有买了鸡蛋和面包的客户中，有    90%的客户还买了牛奶。关联规则可以用来发现很多有趣的规律。这其中需要先阐明两个概念：支持度和置信度。
支持度 Support支持度指某频繁项集在整个数据集中的比例。假设数据集有 10 条记录，包含{'鸡蛋', '面包'}的有 5 条记录，那么{'鸡蛋', '面包'}的支持度就是    5/10 = 0.5。
置信度 Confidence置信度是针对某个关联规则定义的。有关联规则如{'鸡蛋', '面包'} -> {'牛奶'}，它的置信度计算公式为{'鸡蛋', '面包',    '牛奶'}的支持度/{'鸡蛋', '面包'}的支持度。假设{'鸡蛋', '面包', '牛奶'}的支持度为 0.45，{'鸡蛋', '面包'}的支持度为 0.5，则{'鸡蛋', '面包'}    -> {'牛奶'}的置信度为 0.45 / 0.5 = 0.9。
关联规则用于发现 if -> then    这样的规则，并可以给出这条规则的可信度（即置信度）。现实场景中可以用来发现很多规律，下面举个例子。在信息安全领域，需要根据已有流量数据制定规则，来判断是否触发安全报警。如规则{'数据包大'，'多个    ip 地址同时发送数据'} -> {'异常'}，该规则的置信度为 0.85。这条规则表示，当流量数据包大，并有多个 ip 地址同时向目标 ip 发送数据时，则有    85%的概率存在异常，需要触发报警。
频繁项集挖掘原理频繁项集挖掘分为构建 FP 树，和从 FP 树中挖掘频繁项集两步。本节用如下表所示的数据集作为例子展开，该示例数据集共四条数据。
表 1. 示例数据集数据集 a,b,c  c,d,b,a  d,e,a b,a
构建 FP 树构建 FP    树时，首先统计数据集中各个元素出现的频数，将频数小于最小支持度的元素删除，然后将数据集中的各条记录按出现频数排序，剩下的这些元素称为频繁项；接着，用更新后的数据集中的每条记录构建 FP    树，同时更新头指针表。头指针表包含所有频繁项及它们的频数，还有每个频繁项指向下一个相同元素的指针，该指针主要在挖掘 FP 树时使用。下面用上文提到的数据集展开说明，假设最小支持度为    2。
首先，统计数据集中各元素出现的次数，得 a 出现 4 次, b 出现 3 次, c 出现 2 次, d 出现 2 次, e 出现 1 次。
接着，将出现次数小于最小支持度 2 的元素（即 e）在数据集中删除，并将数据集按出现次数由高到低排序，得表 2。
表 2. 更新后的数据集数据集 a,b,c  a,b,c,d  a,d  a,b
然后，用更新后的数据集中的记录创建 FP 树，并同时更新头指针表。创建 FP 树时，当待添加的记录与 FP 树中的路径相同，则只需更新元素对应的频数；如果待添加的记录与 FP    树存在不一致，则在不一致的地方分叉，创建新的结点。如图 1-4 所示。注意，FP 树的根节点是 null。
图 1. 向 FP 树添加第一条记录{a,b,c}图 2. 向 FP 树添加第二条记录{a,b,c,d}图 3. 向 FP 树添加第三条记录{a,d}图 4. 向 FP 树添加第四条记录{a,b}