机器学习实战

本章内容

发现事务数据中的公共模式

FP-growth算法

发现Twitter源中的共现词

你用过搜索引擎吗？输入一个单词或者单词的一部分，搜索引擎就会自动补全查询词项。用户甚至事先都不知道搜索引擎推荐的东西是否存在，反而会去查找推荐词项。我也有过这样的经历，当我输入以“为什么”开始的查询时，有时会出现一些十分滑稽的推荐结果。为了给出这些推荐查询词项，搜索引擎公司的研究人员使用了本章将要介绍的一个算法。他们通过查看互联网上的用词来找出经常在一块出现的词对1。这需要一种高效发现频繁集的方法。

1. J. Han, J. Pei, Y. Yin, R. Mao, “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,” Data Mining and Knowledge Discovery 8 (2004), 53–87.

本章会在上一章讨论话题的基础上进行扩展，将给出一个非常好的频繁项集发现算法。该算法称作FP-growth，它比上一章讨论的Apriori算法要快。它基于Apriori构建，但在完成相同任务时采用了一些不同的技术。这里的任务是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或者频繁项对，即常在一块出现的元素项的集合FP树。这种做法使得算法的执行速度要快于Apriori，通常性能要好两个数量级以上。

上一章我们讨论了从数据集中获取有趣信息的方法，最常用的两种分别是频繁项集与关联规则。第11章中介绍了发现频繁项集与关键规则的算法，本章将继续关注发现频繁项集这一任务。我们会深入探索该任务的解决方法，并应用FP-growth算法进行处理，该算法能够更有效地挖掘数据。这种算法虽然能更为高效地发现频繁项集，但不能用于发现关联规则。

FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。在小规模数据集上，这不是什么问题，但当处理更大数据集时，就会产生较大问题。FP-growth只会扫描数据集两次，它发现频繁项集的基本过程如下：

1. 构建FP树；

2. 从FP树中挖掘频繁项集。

下面先讨论FP树的数据结构，然后看一下如何用该结构对数据集编码。最后，我们会介绍两个例子：一个是从Twitter文本流中挖掘常用词，另一个从网民网页浏览行为中挖掘常见模式。

本章内容