- .
不在 Lk-1 中,为了说明这个产生过程为什么能保持完全性,要注意对于 Lk 中的任何
有最小支持度的工程集,任何大小为 k-1 的子集也必须有最小支持度。因此,如果我
们用所有可能的工程扩大 Lk-1 中的每个工程集,然后删除所有 k-1 子集不在 Lk-1 中
的工程集,那么我们就能得到 Lk 中工程集的一个超集。
上面的合并运算相当于用数据库中所有工程来扩展 Lk-1;如果删除扩展工程集的第 k-
1 个工程后得到的 k-1 工程集不在 Lk-1 中,那么删除该扩展工程集。条件 p[k-1]<q
[k-1]保证不会出现一样的扩展项。因此,经过合并运算,Ck>Lk。类似原因在删除运
算中,删除 Ck 中其 k-1 子工程集不在 Lk-1 中的工程集,同样没有删除包含在 Lk 中的
工程集。
(1)for所有工程集 c∈Ckdo
(2) for所有 c 的 (k-1)子集 sdo
(3) if(s¢Lk-1)then
(4) 从 Ck 中删除 c
例如:L3 为{{123},{124},{134},{135},{234}}。Jion 步骤之
后,C4 为{{1234},{1345}}。Prune 步骤将删除项集{1345},因为项集
{145}不在 L3 中。
Subset 函数:
候选工程集 Ck 存储在一棵 Hash 树中。Hash 树的一个节点包含了项集的一个链表(一
个叶节点)或包含了一个 Hash 表(一个节点)。在节点中,Hash 表的每个 Bucket 都指
向另一个节点。Hash 树的根的深度定义为 1。在深度 d 的一个节点指向深度 d+1 的
节点。工程集存储在叶子中。要加载一个工程集 c 时,从根开场向下直到一个叶子。
在深度为 d 的一个节点上,要决定选取哪个分枝,可以对此工程集的第 d 个工程使用
一个 Hash 函数,然后跟随相应 Bucket 中的指针。所有的节点最初都创立成叶节点。
当一个叶节点中项集数量超过某个指定的阈值时,此叶节点就转为一个节点。
从根节点开场,Subset 函数寻找所有包含在某个事务 t 中的候选,方法如下:假设处
于一个叶子,就寻找此叶子中的哪些工程集是包括在 t 中的,并对它们附加引用指向答
案集合。假设处于一个节点,而且是通过 Hash 工程 i 从而到达此节点的,那么就对 t
中 i 之后的每个工程进展 Hash,并对相应 Bucket 中的节点递归地应用这个过程。对
于根节点,就对 t 中的每个工程进展 Hash。
尽管 Apriori 算法已经可以压缩候选数据项集 Ck,但是对于频繁项集尤其是 2 维的候
选数据项集产生仍然需要大量的存储空间。也就是说对于 2 维的候选数据项
集,Apriori 算法的剪枝操作几乎不起任何作用。例如:1 维高频数据项集 L1 的规模
是 O(n),那么 2 维候选数据项集的规模将到达 O(n2)。如果我们考虑一般情况,即在
没有支持度的情况下 1 维高频数据项集 L1 的规模是 103,那么 2 维候选数据项集的规
模 C2 将到达 C1000≈5×105.这种空间复杂度以指数形式的增长,使得这个经典的
算法的执行效率很难让人满意.Apriori 算法的两大缺点就是产生大量的候选集,以及
需重复扫描数据库。
- .word.zl.