在挖掘关联规则的过程中，无可避免要处理海量的数据，也就是事务数据库如此之大，如果采用Apriori算法来挖掘，每次生成频繁k-项集的时候，可能都需要扫描事务数据库一遍，这是非常耗时的操作。那么，可以想尽办法来减少扫描事务数据库的次数，来改进挖掘频繁关联规则的效率。

FP-tree是频繁模式树，它是将整个事务数据库压缩到一棵频繁模式树上。而且，在构造整个事务数据库的的FP-tree的过程中，只需要扫描一次事务数据库就能生成。比AproriGen算法生成候选频繁项集要节省很多时间。

关联规则挖掘FP-growth算法，

FP-tree是频繁模式树，是挖掘频繁关联规则使用到的一种数据结构。

它是将事务数据库中的所有事务对应的项集作为FP-tree结点，压缩到一棵FP-tree上，得到一棵频繁模式树。

FP-tree结点数据结构

FP-tree的结点FPNode的数据结构如下：

一个FPNode由4个域组成：

nodeName：结点的名字，也就是它所能标识的一个项目的名称；

nodeCount：结点统计计数，也就是一个nodeName标识的项目对应的统计计数；

nodeLink：指向FP-tree中具有相同的node

基于Hash技术来产生频繁项集，能够在一定程度上减少由调用aprioriGen方法生成候选频繁项集的开销。Park等人研究发现，候选频繁2-项集生成的过程中，计算量比较大，引入散列（Hash）技术来解决这个问题，以改进Apriori算法。

同时，基于Hash技术生成候选频繁2-项集，能够扩展到生成候选频繁k-项集。对频繁关联规则的挖掘，与Apriori算法执行的过程是相同的。

算法实现

用Java语言实现的基于Hash技术，改进Apriori算法，实现类为AprioriHashAlgorithm ，包含了频繁项

基于Hash技术改进的Apriori算法，也是采用两阶段挖掘的思想：第一阶段挖掘频繁项集，第二阶段挖掘频繁关联规则。

基于Hash技术来产生频繁项集，能够在一定程度上减少由调用aprioriGen方法生成候选频繁项集的开销。

Park等人研究发现，候选频繁2-项集生成的过程中，计算量比较大，引入散列（Hash）技术来解决这个问题，以改进Apriori算法。

同时，基于Hash技术生成候选频繁2-项集，能够扩展到生成候选频繁k-项集。对频繁关联规则的挖掘，与Apriori算法执行的过程是相同的。

基于Hash技术改进的Aprior

AprioriTid算法的思想，是在Apriori算法思想的基础上做了一点改进，就是增加了一个Tid集合，用来代替事务数据库，这样扫描统计支持计数的开销降低了。

在Apriori算法实现的基础上，AprioriTid算法实现还是比较容易的。下面是我使用Java语言实现的AprioriTid算法，实现了AprioriTidAlgorithm 类，包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程。

算法实现

（一）核心类

package org.shirdrn.datamining.association;

AprioriTid算法是一个挖掘关联规则的算法，是在Apriori算法的基础上改进的算法。它也是采用两阶段挖掘的思想，并且同Apriori算法不同的是：

（1）Apriori算法多次扫描事务数据库D；AprioriTid算法只扫描一次事务数据库D，初始化一个所谓的事务集合T1。

（2）Apriori算法生成频繁k-项集，根据候选频繁k-项集Ck，扫描事务数据库统计Ck中项集支持计数；AprioriTid算法生成频繁(k-1)-项集之后，根据候选频繁k-项集Ck与Tk-1集合构造Tk集合，扫描Tk集合统计Ck中项集的支持计数。

T1 = D，此时T1最大，而在k>1

Apriori算法的思想还是很容易理解的，实现起来虽然麻烦，但是还是比较容易的。下面是我使用Java语言实现的Apriori算法，实现了AprioriAlgorithm 类，包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程。

另外，有一个辅助类ProperSubsetCombination用于计算一个频繁项集的真子集，采用组合原理，基于数值编码原理实现的组合求解集合的真子集。

算法实现

（一）核心类

Apriori算法的核心实现类为AprioriAlgorithm，实现的Java代

Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法，这是一个采用两阶段挖掘的思想，并且基于多次扫描事务数据库来执行的。Apriori算法的设计可以分解为两步骤来执行挖掘：

1、从事务数据库（D）中挖掘出所有频繁项集。

支持度大于最小支持度minSup的项集（Itemset）称为频集（Frequent Itemset)。

首先需要挖掘出频繁1-项集；

然后，继续采用递推的方式来挖掘频繁k-项集（k>1），具体做法是：

在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup来筛选，得到频