FP-Growth算法详解及应用介绍

3.2节对FP-Growth算法的基本思想进行了介绍，并且给出了一个实例，以下将给出详细的FP-Growth算法。

关于频繁模式树（FP-tree）的设计和构造已在前面介绍了，对应3.1小节中的定义，下面先将FP-Growth算法中涉及的一些符号进行说明：

项集I： I= ｛i1， i2，…，im｝；交易数据库DB: DB =｛T 1 ， T2， …， Tn｝，其中Ti（ i =1， 2，…， n）是一个交易，包含了I中的项集。

1） FP-Tree构造算法

FP-Tree构造过程需要扫描交易数据库DB两遍：第一遍收集频繁项集，第二遍构造FPTree。 FP-tree构造步骤前面已有详细介绍，这里给出构造FP - tree的算法，如图3-15所示。

图3-15　FP-tree构造方法

在FP-Tree中插入一个交易T的代价为O（|freq（T）|），其中freq（T）是交易T中频繁项的集合，称为一个交易Trans的频繁项投影，|freq（T） |表示交易T中包含的频繁项的个数，假设F表示频繁项集，则f req（T） = T∩F 。

2） FP-Tree的性质

FP-Tree具有完备性（completeness）和紧凑性（compactness）。

引理3.1：给定一个交易数据库DB和一个最小支持度阈值ξ。相应的FP树包含了数据库中与频繁模式挖掘相关的所有信息。

基于FP树的构造过程可以知道，交易数据库DB中的每个交易的频繁项投影在FP树中对应一条路径，即每个交易的频繁项集信息完全存储在FP树中。而且，因为每个交易的代表路径都必须从项前缀子树的根结点开始，所以FP树中的一条路径可以代表多个交易的频繁项集，且不产生混乱。

对FP树中每一个从根节点开始的路径a1，a2 ，… ，ak，假设cak是节点标号为ak的项计数值是ak子节点计数之和，则根据FP树构造过程，该路径存储了个交易的频繁项投影。

因此，FP树存储了无重复的频繁项投影的所有信息。

由此得到引理。

引理3.2：给定一个交易数据库DB和一个最小支持度阈值ξ。不考虑根结点，FP树的大小由数据库中出现的所有频繁项（∑T∈DB | freq（T） |）决定，树的高度取决于数据库中含所有交易中最大的频繁项项数（maxT∈DB | freq（T） |） 。

基于FP-Tree的构造可以知道，对DB中的任意交易T，存在一条路径，该路径上的节点集和交易T的频繁项是相同的。因为每个交易的频繁项只能对应一个树节点，只有根结点是唯一一个不由频繁项插入而生成的节点，而且每个节点包含一个节点链和一个计数信息，由此可以得到树的大小边界为∑T∈DB | freq（T） |。

任意一个p前缀子树的高度是指所有频繁项列以p开头的交易中，含频繁项最多的交易所包含的频繁项项数。因此，不考虑根结点这层高度，树的高度由数据库中所有交易中最大的频繁项项数决定，即maxT∈DB | freq（T）| 。

引理3.2表明了FP树的一个重要特点：FP树的大小由它相应的数据库决定，因为每个交易在FP树中最多生成一条路径，它的长度等于该交易的频繁项项数。而且由于交易间通常会有很多共享的频繁项，所以树的大小通常都远小于原来的数据库。而不像类Apriori方法，在最坏情况下可能产生指数级数量的候选集。

综上，FP树是一个高度紧凑的结构，存储了频繁模式挖掘的所有信息，具有完备性和紧凑性。这两个性质是保证FP-Growth算法正确完整挖掘频繁模式的前提和基础。

3）频繁项集列表FList的排序问题

FP树构造过程中，频繁项集中的项以支持度的降序排列：越频繁出现的项更可能被共享，因此将它们安排在更靠近FP树的顶部。这种排序方式进一步提高了FP树结构的紧凑性。然而，这并不意味着采用降序排列频繁项的方法总能够获得最大的紧凑性。根据数据的其他特征，有时可能获得更好的紧凑性，例如有一个交易数据库：｛abef， bdef， cdef， a，a， a， b， b， b， c， c， c｝，最小支持度阈值为3，第一遍扫描数据库得到｛a： 4， b： 4， c： 4， d：3， e： 3， f： 3｝，对其进行排序：a→b→c→d→e→f，于是生成的FP树包含12个节点，如图3-16a所示。然而，按照排序f→d→e→a→b→c，生成的FP树仅包含9个节点，如图3-16b所示。

图3-16　FP树

图3-16说明了基于支持度降序构造的FP树并不是总是最小。

4）使用FP-Tree挖掘频繁模式

构造一个紧凑的FP树能保证在一个紧凑的数据结构上进行挖掘。然而，这并不能保证非常有效的挖掘，因为，如果只简单地使用FP树来生成和检验所有的候选模式，可能会碰到有关候选集生成时的组合问题。在这一部分，将介绍如何利用存储在FP树挖掘频繁模式全集（即所有的模式）的算法FP-growth 。

FP树结构具有一些有利于频繁模式挖掘的性质。

性质3.1（节点链性质，node-link property）：对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。

这个性质基于FP树的构造过程，它方便了通过ai的节点链遍历FP树，并访问与ai相关的模式信息。

性质3.2（前缀路径性质，prefix path property）：为了计算路径p上的一个节点ai的频繁模式，只需要计算p中ai的前缀子树，并且前缀子树中的每个节点的频繁数和节点ai相同。(www.xing528.com)

假设路径p上的节点顺序标记为a1 ， a2，…， an，a1是前缀子树的根节点，an是p路径中子树的叶节点，ai（1≤i≤n）是被参考的节点。根据FP-tree构造算法（图3-15）中构造FP树的过程，对每个前缀节点ak （1≤k≤i），ai的前缀子路径与ak同时出现的次数是ai.count。因此每个这样的前缀节点都和节点ai有相同的计数。需要注意在同一路径上也和ai同时出现的一个后缀节点am（i＜m n）。am的模式将在检验后缀节点a m时生成，在计≤算ai的模式时不用计算，否则会冗余的生成模式。因此，只需检验p中ai的前缀子树。

例3.9：上一节的图3-3中，节点m包含在路径＜f： 4，c： 3，a： 3，m： 2，p： 2＞中，为了计算这条路径上的节点m的频繁模式，则只需要将节点m的前缀子路径＜f： 4，c：3，a： 3＞提取出来，前缀路径的每个节点的频繁数都等于节点m的计数。也就是说，前缀路径的节点计数调整为：＜f： 2，c： 2，a： 2＞。

基于这个性质，节点ai的前缀子树可以被拷贝和转换到一个调整计数的前缀子路径中，调整前缀子树的每个节点的频繁数和ai的相同。这个转换后的前缀路径被称为ai在路径p中的转换前缀路径（transformed prefixed path）。

注意ai的转换前缀路径的集合形成了一个小的模式数据库，这个和ai同时出现的模式数据库称为条件模式库（conditional pattern base），标记为“pattern_base | ai”，然后可以在ai的条件模式库中计算所有和ai相关的频繁模式，创建一个小的FP树，称为条件FP树，表示为FP-Tree | ai，在这个小的条件FP树上作序列挖掘。构造条件模式库和条件FP树的过程和例3.9相同。

这个过程是递归的，基于下面的定理，通过模式增长方法，可以得到频繁模式。

引理3.3（片段增长，fragment growth）：假设α是DB中的一个项集，B是α的一个条件模式库，β是B中的一个项集，那么，α∪β在DB中的支持度和β在B中的支持度是相同的。

根据条件模式库的定义，当α在原始数据库中出现时，B中的每个（子）交易才出现。如果一个项集β在B中出现ψ次，那么它和α在DB中一起出现的次数也为ψ。而且，因为所有这样的项集都是在α的条件模式库中收集的，所以α∪β在DB中出现的次数是ψ。

可以得到以下推论。

推论3.1（模式增长，pattern growth）：假设α是DB中的一个频繁项集，B是α的条件模式库，β是B中的一个项集。当且仅当β在B中是频繁时，α∪β在DB中才是频繁的。

当α是DB中的频繁项集，而且在α的条件模式库B中，当β的支持度不小于最小支持度阈值ξ时，推论成立。

根据推论3.1，挖掘时可以从收集在DB中的频繁1项集α开始，对每个频繁1项集构造条件模式库，然后在条件模式库中挖掘1项集β，依此类推。这表明挖掘频繁模式的过程可以看成是：从挖掘频繁1项集开始，然后挖掘它的条件模式库，进一步增长每个项集，依次作类似的处理。通过一系列的条件模式库，将处理频繁k项集的问题转化为k个处理频繁1项集的问题。这里所作的只是模式的增长，不需要在整个挖掘过程中生成候选项集的组合。

挖掘单路径FP树的所有频繁模式：

引理3.4（单路径FP树的模式生成，single FP-Tree path pattern generation）：假设一个FP树，只有一条路径P，通过列举P的子路径的所有组合，可以得到FP树的频繁模式全集，它们的支持度等价于子路径中的所有项的最小支持度。

假设FP树中的一个单独路径P＜a1： s1→a2： s2→…→ak ： sk ＞，每个项ai的支持度si（ 1≤i≤k）是指ai和它的前缀串同时出现的频率。因此，这条路径上项集的任意组合，比如：＜ai，…， aj＞（for 1≤i，j≤k）是一个频繁模式，它们同时出现的频率等于那些项中的最小支持度。因为路径P的每项都是唯一的，所以在组合生成时不可能生成冗余的模式。而且，在FP树之外不可能再生成频繁模式。由此得到这个引理。

5） FP-Growth算法

基于以上的引理和性质，得到用FP树挖掘频繁模式算法，如图3-17所示。

图3-17　FP-Growth算法

分析：由上面的性质和引理，可以知道，算法能正确地找到交易数据库DB中频繁项集的全集。

如引理3.1，DB的FP树包含了DB在支持度阈值为ξ的条件下，有关频繁模式挖掘的所有信息。如果一个FP树包含单个路径，根据引理3.4，它生成的模式是路径上所有节点的组合，模式的支持度为子路径上所有节点的最小支持度。因此得到程序的1）～3）。否则，对每个频繁项ai构造条件模式库并挖掘它的条件FP树。前缀路径转换的正确性和完备性在性质3.2中说明，因此条件模式库中存储了频繁模式挖掘的所有信息。根据引理3.4和它的推论知道，由条件FP树生成的模式是频繁模式的全集。特别的，根据片段增长性质，组合的片段的支持度和条件模式库生成的频繁项集的支持度相同。因此，得到程序的4）～8）。

6） FP-Growth算法的优点

利用紧凑的数据结构FP树压缩存储频繁模式的关键信息，然后用模式增长方法FP -Growth，有效地对大数据库进行频繁模式挖掘的算法，相对于其他方法的优点在于：

（1）高度压缩的FP树，通常远小于原始数据库，因此减少了模式挖掘时扫描数据库的开销。

（2）用模式增长的方法，组合在（条件）FP树中找到的频繁1项集，避免了生成和检验候选项集的开销：在这个方面，挖掘过程不再是类似Apriori方法的生成和检验，而只是频繁模式的增长。主要的挖掘操作是数量的收集和前缀路径计数的调整，开销远小于大多数类Apriori算法中，对候选集生成和模式匹配操作的开销。

（3）用基于划分的、分而治之的方法，大大减少了条件模式库和条件FP树的大小。

还可以采用一些方法进一步提高FP-Growth的性能和可拓展性：

（1）构造投影数据库的FP树：当数据库很大时，无法在主存中构建FP树，一个可用的办法就是先把数据库分为多个投影数据库，然后对每个投影数据库构造一个FP树并挖掘。

（2）构造驻留磁盘的FP树：另一个处理大数据库的方法就是构造驻留磁盘的FP树。B+树已经在关系数据库中广泛使用，它可以用来作FP树的索引。

（3） FP树的物化（materialization）：尽管FP树具有紧凑性，但它的构造需要两次扫描交易数据库，这可能需要一定的代价，物化FP树将对频繁模式挖掘有利。物化时的一个难题就是如何选择一个好的支持度阈值，因为这个阈值通常是独立于查询的。解决的方法之一是使用一个能满足FP-树的大部分挖掘查询的低的阈值ξ，例如如果发现98%的查询满足阈值ξ≥ 20，则可以选择ξ=20作为FP-tree物化阈值，即仅有2%的查询可能需要建立一棵新的FP-tree。

（4） FP树的增量更新：另一个与FP树物化相关的主题是如何增量更新一个FP树，如当每天往一个已包含多月记录的数据库中加入了新的交易时。如果物化FP树用1作为最小支持度，那么更新不会导致什么问题，因为加入新记录就等于是在构建FP树时扫描额外的交易，但是这样FP树会变得非常大。通常情况下，可以在FP中记录每个项的出现频率，更新时跟踪它们。

鉴于本书的目的是向读者介绍基础和原理知识，这里仅给出基本思路介绍，而关于物化FP-tree的更多细节，可以参考相关文献（例如文献［4］）。