Apriori算法详解

3.2节中已对Apriori算法的基本思想及过程进行了一定的介绍，下面介绍详细算法（图3-12）。

图3-12　Apriori算法

apriori-gen函数将频繁k—1项集Lk—1和最小支持度阈值作为输入参数，返回所有频繁k-项集的超集。该函数做两个动作：连接和剪枝。

实现步骤如下，首先对Lk-1中的频繁项集进行自连接（图3-13）：

图3-13　apriori-gen函数——自连接

连接条件p［k—1］＜q［k—1］保证不产生重复。(www.xing528.com)

接下来进行剪枝。显然，任何频繁项集的子集一定满足最小支持度阈值。因此根据Apriori性质，如果先扩展Lk—1中的每一个项集，再删除那些（k—1）-子项集不在Lk-1中的项集，剩下的就是Lk中项集的超集，即CkLk。因此，剪枝过程可以删除这样的项集c，c∈Ck，但c中存在长度为（k—1）的子集不属于Lk—1中，如图3-14所示。

图3-14　apriori-gen函数——剪枝

下面再来看一个例子。假设L3=｛｛I1， I2， I3｝，｛I1， I2， I4｝，｛I1， I3， I4｝，｛I1， I3，I5｝，｛I2， I3， I4｝｝，连接完成后，C4=｛｛II， I2， I3， I4｝，｛I1， I3， I4， I5｝｝，那么剪枝过程将会删除项集｛I1， I3， I4， I5｝，因为项集｛I1， I3， I4， I5｝的长度为3的子集｛I1， I4， I5）没有出现在L3中，因此只有｛I1， I2， I3， I4｝保留在C4中。

subset函数用于确定在一个给定的交易T中包含了哪些Ck中的项：

候选k-项集Ck被存放在一棵哈希树中，哈希树中的结点分为两类：一类包含一个项集列表（叶结点），另一类包含一张哈希表（内部结点）。在内部结点上，哈希表中的每一个桶都指向另一个结点。假定哈希树的根结点的深度等于1，则一个深度为d的内部结点指向深度为d+1的结点。项集都存放在叶子结点，当需要添加一个项集c的时候，就从根结点出发直到叶子结点。在一个深度为d的内部结点，对该项集的第d项应用哈希函数来确定下一步遍历的分支。所有的结点最初都被创建为叶子结点。当一个叶子结点的项集数目超出某一个阈值时，该结点将会转化为一个内部结点。

从根结点开始，subset函数按照如下的方式找出包含在交易T中的所有的候选集。如果在叶子结点，找出该叶子结点中所有包含在交易T中的项集，并且为它们添加一个指向结果集的索引；如果通过散列第i项到达某个内部结点，则散列交易T中第i项后的每一项，并且将这个过程递归地应用于相应的桶。对于根结点，则散列交易T中的每一项。

subset函数能够返回所需要的候选集的索引，对于任何交易T中包含的项集c，c的第一个项一定出现在T中。在根结点，通过散列交易T中的每一项，我们能够确定只忽略那些不是从T中的某一项开始的项集。同样的结论也适用于哈希树中位于其他层次的结点。由于在每一个项集中的项都经过排序，如果通过散列项i到达当前的结点，则以后只需要考虑交易T中出现在项i后的项。