6.3　FP-Growth算法

6.3.1　FP-Growth算法的步骤

FP-Growth（频繁模式增长）算法是韩家炜于2000年提出的关联分析算法，它采取如下分而治之的策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree）中，但仍保留项集关联信息。该算法和Apriori算法最大的不同之处有如下两点：第一，不产生候选集；第二，只需要遍历数据库两次，大大提高了效率。

算法的具体描述如下。

输入：事务数据库D、最小支持度阈值min_sup。

输出：频繁模式的完全集。

第一步，按如下步骤构造FP-Tree。

（1）扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。

（2）创建FP-Tree的根节点，以“null”标记它。对于D中每个事务Trans，执行：选择Trans中的频繁项，并按L中的次序排序。设排序后的频繁项表为[p|P]，其中，p是第一个元素，而P是剩余元素的表。调用insert_tree([p|P],T)。该过程执行情况如下。如果T有子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链结构将其链接到具有相同item-name的节点。如果P非空，递归地调用insert_tree(P,N)。

第二步，根据FP-Tree挖掘频繁项集，实现过程如下。

6.3.2　FP-Growth算法的实例

第一步，构造FP-Tree。

（1）扫描事务数据库得到频繁1-项集F。

（2）定义min_sup=2，即最小支持度为2，重新排列F。

（3）重新调整事务数据库。

（4）创建根节点和频繁项表。

（5）加入第一个事务（I2,I1,I5）。

（6）依次加入其他事务。

至此，就得到了一个完整的FP-Tree。

第二步，根据FP-Tree挖掘频繁项集。

（1）首先考虑I5，得到条件模式基：<(I2,I1:1)>、<I2,I1,I3:1>，并构造条件FP-Tree。

得到I5频繁项集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}。

（2）同理，依次考虑I4、I3、I1，可以得到如下频繁项集。

I4频繁项集：{{I2,I4:2}}。

I3频繁项集：{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}。

I1频繁项集：{{I2,I1:4}。

上述演示了FP-Growth算法的详细实现过程，可以看出，依据FP-Tree寻找频繁项集更直观、更清晰。当然也可以像6.2.4节那样用MATLAB实现FP-Growth算法的整个过程，读者可以尝试一下，以加深对FP-Growth算法的理解。

6.3.3　FP-Growth算法的优缺点

FP-Growth算法的优点如下：

（1）一个大的数据库能够被有效地压缩成比原数据库小很多的高密度结构，避免了重复扫描数据库的开销。

（2）该算法基于FP-Tree的挖掘，采取增长模式的递归策略，创造性地提出了无候选项集的挖掘方法，在进行大频繁项集的挖掘时效率较好。

（3）挖掘过程中采取了分而治之的策略，将这种压缩后的数据库D分成一组条件数据库Dn，每个条件数据库关联一个频繁项，并分别挖掘每一个条件数据库。而这些条件数据库Dn要远远小于数据库D。

FP-Growth算法的缺点如下：

（1）该算法采取增长模式的递归策略，可避免候选项集的产生。但在挖掘过程中，如果大项集的项目的数量很多，并且由原数据库得到的FP-Tree的分枝很多，分枝长度又很长，该算法需要构造出数量巨大的条件FP-Tree，不仅费时，要占用大量的空间，挖掘效率不好，而且采用递归算法本身效率也较低。

（2）由于海量的事务集合存放在大型数据库中，经典的FP-Growth算法在生成新的FP Tree时每次都要遍历条件模式基两次，导致系统需要反复申请本地服务器及数据库服务器的资源查询相同内容的海量数据，一方面降低了算法的效率，另一方面使数据库服务器高负荷运行，不利于数据库服务器正常运作。