本章主要对挖掘频繁模式进行讲解。 频繁模式是指频繁地出现在数据集中的模式，具体包括频繁项集、频繁序列模式、频繁结构模式。具体的解释书上写得很详细，我们也在第一章的时候进行了讲解，这里就不多提了。 前面的诱发例子也不多说了，都很好理解。 这里，假设我们分析的是超市的数据仓库。 OK，那我们可以把全域想象成商品的集合，而每种商品购买与否就可以用布尔型变量来表示了。比如全域商品是这样的一个集合

那么，一个顾客的菜篮子就可以用布尔型变量来表示，如下

那分析这个布尔型变量，我们就可以知道，这位顾客买了西瓜，鱼，衬衣，鞋子；没有买桃子，鸡，牛肉，面包。 我们把销售数据转换成这种之后，便于我们对数据进行处理。我们可以分析布尔型变量，得到反映商品频繁关联或同时购买的购买模式。 而购买模式就可以用关联规则来表示，如下所示。

这个式子表示，我们所分析的所有记录的2%显示计算机和杀毒软件被同时购买及在购买计算机的顾客中有60%的人同时也购买了杀毒软件。 其中的support即表示规则的支持度，confidence则表示规则的置信度。 而最小支持度阀值和最小置信度阀值是由人设定的。 通常的，我们把同时满足最小支持度阀值和最小置信度阀值的规则认作是强规则。

其他的一些诸如项集，k项集，项集的出现频度书上P159都有，不多说了。

而由于关联规则很容易通过支持度和置信度推导出来。因此挖掘关联规则实质上可以归结为挖掘频繁项集。 一般而言，关联规则的挖掘是一个 两步的过程：

其中，挖掘的整体性能由第一步决定。

频繁项集的挖掘方法 关联分析是一种在大规模数据集中寻找有趣关系的任务。Apriori是解决这一问题的基本算法。这个算法也是数据挖掘的入门算法。 这是一种最有影响的挖掘布尔关联规则频繁项集的算法。 该算法的主要方法就是使用一种被称为逐层搜索的迭代方法，并且为了提高效率，一种被称为先验性质（Apriori property）的重要性质被用于压缩搜索空间。

其中，先验性质其实我们在第5章已经了解了。这里再介绍一下先验性质。

其实，意思都是一个意思，也很好理解。 那么，我们如何在实现这个算法呢？ 书上P161的例6.3写的非常详细，仔细看下，应该能理解的。 从例6.3我们可以看到，实际上整个Apriori算法就是在迭代的使用连接和剪枝。在看例子的时候，我们要注意如何剪枝，以及算法的终止条件。

有频繁项集产生关联规则 我们上面说了，联规则很容易通过支持度和置信度推导出来。因此挖掘关联规则实质上可以归结为挖掘频繁项集。我们已经使用Apirori算法，挖掘出了频繁项集。那么如何通过频繁项集产生关联规则呢？ 6.2.2节说明了这一问题，且例6.4给出了实例。

OK，在上面我们提到了Apriori算法。但实际上，这个算法是非常古老的算法了。因为Apriori算法是宽度优先的算法，它有两个非常显著的缺点

在6.2.3节，我们看到了提升Apriori算法效率的几种方法，前面的几种都很好理解，只有最后一个”动态项集计数”我不是很理解。这里暂且放下。 纵观这里提到的几种方法，我们可以看到。这几种方法都只是在没有改变其核心思想上做的一个效率提升的工作，即旨在提升原生Apriori算法的效率。但事实上，KDD发展至今，对于频繁项集的挖掘已经有了很多种方法，其中广泛使用的是类Apriori算法

类Apriori算法之FP-growth 上面我们说了，原Apriori算法的性能在某些情况下，仍然会受到很大的影响。这里我们引入一种类Apriori算法——频繁模式增长（FP-growth） 首先，我要批评的是，书上关于这个算法的讲解真是太烂了！！！好像这个算法还是2000年，韩家炜（本书的作者之一）自己搞出来的吧？那为啥不好好讲讲=。= 言归正传，我们继续来讲FP-growth算法。 首先，我们要知道的是下面这几点。 FP-growth算法是基于Apriori构建的，但采用了高级的数据结构减少了扫描次数，因此大大加快了算法速度。

FP-growth算法发现频繁项集的基本过程如下：

OK，下面我们就来详细讲解一下。大家就不要在去看书上的那个图了，免得把自己搞混。

构建FP树 上面我们谈到，FP-growth算法的优点是采用了高级的数据结构。那么这种高级的数据结构是什么呢？实际上就是FP树。 FP树是一种输入数据的压缩表示。他通过把事务映射到FP树上来构造一条路径。这样如果不同事务之间的重叠路径越多，那么就有理由认为他们是频繁项集。由于不同的事务可能会有若干个相同的项，因此它们的路径相互重叠越多，则使用FP树结构获得的压缩效果越好。 那么，接下来，我们来一步一步地构造FP树 。 假设我们有这样一组数据 首先，同Apriori算法一样。数据库第一次扫描，得到频繁项集的集合（1项集，滤掉了不满足阀值的。），并按逆序排序。于是我们就有

然后，我们就可以构造FP树了：首先，创建树的根节点，用null表示 接着，我们进行第二次扫描数据库，对数据库中的每个事务按照先前的逆序进行处理，并对每个事务创建一个分枝。 例如，对数据库中的第一条记录｛a，b｝按逆序进行处理，还是｛a，b｝ 第二条记录｛b,c,d｝按逆序处理，还是｛b，c，d｝ 第三条记录｛a,c,d,e｝按逆序处理，还是｛a，c，d，e｝ 接下来依次进行这种操作，直至最后

由于这个实例选取的数据直接就是OK的，没有体现出过滤和逆序的操作。不清楚的同学，建议再看下这两张图，想一下，应该能理清整个流程。 （PS：阀值为3）

OK，到这里应该流程理清了。在图中，我们可以看到一些虚线的箭头，可能有些同学还不清楚它是什么。 实际上FP-growth算法还有一个被称为头指针表的数据结构，用来记录各个元素项的总出现次数的数组。然后再附带一个指针指向FP树中该元素项的第一个节点。这样每个元素项都构成一条单链表，有助于快速访问树中的项。 下面，我们进行第二步。

从FP树中挖掘频繁项集 从FP树中挖掘频繁项集的步骤如下

这里出现了一个新的名次——条件模式基（condition pattern base）。它的定义是这样的：条件模式基是以所查找元素项为结尾的路径集合。 概念挺绕的，其实很简单 ，就是前缀路径。直接看示例 则每一个频繁元素项的所有条件模式基（前缀路径）为 。 发现规律了吗，z存在于路径{z}中，因此前缀路径为空，另添加一项该路径中z节点的计数值5构成其条件模式基；r存在于路径{r, z}、{r, y, x, z}、{r, s, x}中，分别获得前缀路径{z}、{y, x, z}、{s, x}，另添加对应路径中r节点的计数值（均为1）构成r的条件模式基；

OK，我们按照上面的思路，从FP树中获得了每一个频繁项的条件模式基。接下来，我们就要利用条件模式基来构造FP条件树了。

首先要明白的是，对于每一个频繁项，都要创建一棵条件FP树。 那么怎样通过条件模式基创建条件FP树呢？ 直接看示例。

同样的，统计一下，过滤并按逆序排序

在这里，注意到元素项s以及r是条件模式基的一部分，但是它们并不属于条件FP树。因为在当前的输入中，s和r不满足最小支持度的条件。

其他几个也是这样操作。

最后，结合项与其对应的条件FP树进行分析过滤，就能够得出了频繁项集了。

大家直接看书上的看不懂，很可能跟我一样。就是这本书一上来就一阵噼里啪啦的大讲特讲，直接把人搞懵了。 实际上，FP-growth算法中，最重要的就是FP树的构造和FP条件树的构造。只要搞清了这两棵树怎么构造的，再去看书上就应该能看懂了 。 OK，现在回头再看书167-168页，发现就是这么回事儿了。

FP增长是一个有趣的算法，它是深度优先的算法。它展示了如何使用事务数据集的压缩表示来有效的产生频繁项集，此外对于某些事务数据集，FP增长算法比标准的Apriori算法要快几个数量级，FP增长算法的运行性能取决于数据集的“压缩因子”。如果生成的FP树非常茂盛（在最坏的情况下，是一颗完全二叉树）则算法的性能显著下降，因为算法必须产生大量的子问题，并且需要合并每个子问题返回的结果。

接下来，书上讲了使用垂直数据合适挖掘频繁项集及挖掘闭模式和极大模式，都挺好理解的，这里不多说了。 只特别说一下闭项集和最大频繁项集，很多同学体会不到这两个概念是干什么用的。本章主要讲的是挖掘频繁项集啊，但是数据集基本上都很大，所以我们需要寻求一种能够减小计算负担的方法。 为此，人们引入了频繁项集和最大频繁项集的概念。 借用下这篇文章阐述的观点。点击这里查看

频繁闭项集（Closed Patterns）： 当项集X是频繁项集，且数据集D中不存在X的真超集Y，使得X和Y的支持度相等，则X是闭频繁项集。闭频繁项集的表示是无损压缩，不会丢失支持度的信息。通过闭频繁项集可以反推出所有的频繁项集以及相应的支持度。 完全看不懂吧，还是来举个栗子。 因为项集{Beer,Diaper}出现在TID为10,20,30的事务中，所以{Beer,Diaper}的绝对支持度为3。而{Beer,Diaper}的直接超集：{Beer,Nuts,Diaper},{Beer,Coffee,Diaper},{Beer,Diaper,Eggs}的支持度计数分别为1,1,1，都不等于{Beer,Diaper}的支持度计数3，所以{Beer,Diaper}为闭项集，如果其支持度超过阈值，则{Beer,Diaper}为闭频繁项集。

最大频繁项集（Max-Patterns）： 当项集X是频繁项集，且数据集D中不存在X的真超集Y，使得Y是频繁项集，则X是最大频繁项集。极大频繁项集的表示是有损压缩，失去了频繁项集的支持度信息，我们可以根据极大频繁项集判断任意项集是否是频繁的，但无法得到相应的支持度。 理论什么的看着就头大，还是来举个栗子吧。 如果，{Beer,Nuts,Diaper}大于最小阀值（别看支持度什么的都很低，但是阀值是人定的，讲不定就大于阀值呢。），那{Beer,Nuts,Diaper}就是个最大频繁项集，因为没有包含{Beer,Nuts,Diaper}并且比它更大的集合了。

在P160，例6.2也进行了说明。 而在实际中，挖掘闭模式和极大模式确实能有效地减少频繁模式挖掘所产生的模式数量，这点在P170，例6.2.6做了简要阐述。为什么是简要呢？原因有两点：一是因为实际上对数据进行压缩只是一种优化技术而已，又因为本书或者说我们目前的阶段还不需要考虑这么多。二是目前的很多频繁项集挖掘算法已经集成了数据压缩的技术，最典型的莫过于剪枝了。

6.3节，讲到了模式的评估方法，这个以后会比较实用。 在这里，我想多说一句，关于关联规则的误导问题。我觉得，不能简单的以没规则，概率75%；有规则，概率66%来认定这个规则就是误导的。 我们在最开始就说了，进行KDD的目的是为了为决策提供数据支持。如果是这是商业决策的话，那么是否采用这么一个策略，我想很大程度上会受收益的影响。即，我采用了这个策略，是不是我获利能够更多？因此，即便有9%（75-66=9）的概率下降，但假如说，66%这一规则能够产生比75%无规则更多的收益呢？那我作为决策者肯定会采纳66%的啊。因此，在实际进行分析的时候，我们的指标还需要更多才行，我们对数据的挖掘还需要更深才行。 这让我想到了一句话：数据是不会骗人的，骗人的只有人而已。 也不知道这句话到底是对还是错，暂且放在心上吧。

本文参考文章 判断关联规则是否可靠 FP-growth 使用Apriori算法和FP-growth算法进行关联分析 什么是闭项集