logo资料库

The Top Ten Algorithms in Data Mining中第四章Apriori的中文版.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.70M 资料格式：docx 举报 版权申诉
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
资料共24页，剩余部分请下载后查看
    《The Top Ten Algorithms in Data Mining》
    算法描述
    挖掘频繁模式和关联规则
    Apriori
    AprioriTid
    挖掘序列模式
    AprioriAll
    讨论
    关于可用软件实现的讨论
    两个解释示例
    频繁谓词集和关联规则挖掘
    Apriori
    AprioriTid
    关联规则Association rules（算法4.2）
    序列模式挖掘
    性能评价
    高级主题
    改善Apriori类型的频繁模式挖掘
    不生成候选集的频繁模式挖掘
    增量方法
    浓缩表示法：封闭模式和最大模式
    定量关联规则
    使用其他度量重要性/兴趣度的指标
    分类关联规则
    使用更加丰富的表达：序列、树和图
    总结
    《The Top Ten Algorithms in Data Mining》 Apriori 算法是十大数据挖掘算法之一。决策树法、分类归纳法和数据聚类法这几个常用的数 据挖掘方法都是从机器学习领域发展而来。Apriori、AprioriTid[1]、AprioriAll[2]（扩展到连续 模式挖掘的 Apriori 算法）。由于 Apriori 是一种非常基础性的算法并且数据库的格式受到市 场交易数据的限制，已经由很多工作对于提高计算机效率、寻找更紧凑的表达、拓展可以处 理的数据类型等方面进行了研究。一些相当重要的工作可以认为是高级主题。 算法描述 挖掘频繁模式和关联规则 数据挖掘中最常用的一种方法就是发现事务数据集中的频繁谓词集并导出关联规则。该问题 可描述如下：定义I={1,2,⋯,}为一组谓词集合，D 为一组事务集，其中每个事务 t 都是 一个满足t⊆I 谓词集。每个事务都有一个称之为 TID 的唯一标识符。如果 I 中的一些谓词 组成的集合 X 满足X⊆t，则称事务 t 包含 X。一个关联规则是形式如X⟹Y 含义表达式， 其中X⊂I,Y⊂I, 且X∩Y=∅。如果在 D 中包含 X 的事务有 c 比例的事务同时包含 Y，则规 则X⟹Y 在 D 中的置信度为 c（0≤c≤1）。如果 D 中包含X∪Y 的事务的比例为 s 则称规 则X⟹Y 在 D 中的支持度为 s（0≤s≤1）。在给定一组事务集 D 的情况下，挖掘关联规则 的问题就是生成支持度和置信度分别不低于用户定义的最小支持度和最小置信度的所有关 联规则。 鉴于组合爆炸带来的计算复杂性，寻找频繁谓词集（其支持度不低于最小支持度）并不是一 项微不足道的工作。一旦获得频繁谓词集，就能直接生成置信度不低于最小置信度的关联规 则。R. Agrawal and R. Srikant 提出的 Apriori 和 AprioriTid 是适用于大型事务数据集中数据挖 掘的开创性算法[1]。 Apriori Apriori 是一种寻找所有满足最小支持度的谓词集的算法。一个谓词集的支持度是包含有该谓 词集的事务数量占事务总数量的比例。满足最小支持度条件的谓词集被称之为频繁谓词集。 Apriori 是一种逐层搜索（广度优先搜索）算法，利用谓词集向下封闭属性的反单调特性：“如 果一个谓词集是非频繁的，则其任一超集也是非频繁的”。该算法需要多次扫描数据库，在 第一次遍历数据库时计算得到单个谓词的支持度并确定频繁的谓词。在之后每次遍历中，以 前一次遍历发现的频繁谓词集为种子集合生成新的潜在的频繁谓词集，即候选谓词集，并在 遍历数据时计算他们的实际支持度。在遍历结束时获得那些满足最小支持度条件的谓词集， 也就是确定频繁谓词集，进而他们成为下一次遍历的种子。这个过程重复进行直到无法发现 新的频繁谓词集。 通常，Apriori 假设事务或者谓词集中的谓词是按照词典顺序排列的。一个谓词集中谓词的数 量成为它的大小，一个大小为 k 的谓词集称为一个 k-谓词集。大小为 k 的频繁谓词集的集合
    记为 Fk，其候选集集合记为 Ck。Fk 和 Ck 都包含支持度字段。算法 4.1 给出了 Apriori 算法流 程。第一步简单的计算谓词出现概率以确定频繁 1-谓词集。此后的每一步则包含两个阶段： 首先利用在第 k-1 步中发现的频繁谓词集集合 Fk-1 使用 apriori-gen 函数产生候选谓词集集合 Ck；接着遍历数据库计算 Ck 中候选集的支持度。subset 函数就是用于该计算的。 apriori-gen 函数以所有（k-1）-谓词集的集合 Fk-1 为参数，范围一个所有频繁 k-谓词集集合的 超集。首先，在连接步骤中，Fk-1 和 Fk-1 连接。 插入 Ck 选择 p.fitemset1,p.fitemset2,…,p.fitemsetk-1,q.fitemsetk-1 从 Fk-1p，Fk-1q 其中 p.fitemset1= q.fitemset1，…，p.fitemsetk-2= q.fitemsetk-2，p.fitemsetk-1< q.fitemsetk-1 这里 Fkp 指一个频繁 k-谓词集 p，p.fitemsetk 是频繁谓词集 p 的第 k 项。 --------------------------------------------------------------------------------------------------------------------------------- 算法 4.1 Apriori 算法 然后，在枝剪步骤中，所有谓词集c∈删除那些（k-1）-子集不在 Fk-1 中的谓词集。 for (k = 2; Fk−1 =∅; k ++) do begin F1 = {频繁1-itemsets}; Ck = apriori-gen(Fk−1); //新候选集 foreach 事务t ∈ D do begin Ct = subset(Ck , t); // t中包含候选集 foreach 候选集c ∈ Ct do c.count ++; end Fk = {c ∈ Ck |c.count ≥ minsup }; end 结果= ∪k Fk ; -------------------------------------------------------------------------------------------------------------------------------- subset 函数以 Ck 和一个事务 t 为参数，返回事务 t 中包含的所有候选的谓词集。为了快速计 算，Apriori 采用一个哈希树来存放候选谓词集 Ck。所有谓词集被存放在叶节点中。每个结 点初始都是叶节点，根节点的深度定义为 1.当一个叶节点中的谓词集数量超过特定阈值时， 叶节点变为内部节点。一个深度为 d 的内部节点指向深度为 d+1 的节点。树枝的指向通过 为谓词集的第 d 个谓词应用哈希函数来确定。因此，每个叶节点被确定至多包含某一数量的 谓词集（确切的说，仅当在深度 d 小于 k 创建一个内部节点时为真）。叶节点中的一个谓词 集可以被这个谓词集中先后散列的每一项从根节点依次到达。一旦构建了散列树，subset 函数就能从根节点开始发现一个事务 t 中包含的所有候选集。在根节点，t 中的每个谓词都 要被散列，每个确定的分支都跟随着一个更深的节点。如果到达一个叶节点，该叶节点中存 在于事务 t 中的谓词集被搜索到并将这些找到的谓词集和结果集合关联。如果散列谓词 i 到 达一个内部节点，则 t 中位于 i 后面的谓词将依次被散列知道散列结果访问到一个叶节点。 有一点很明显，那就是无法访问到的叶节点中的谓词集不包含在 t 中。 显而易见，一个频繁谓词集的任一子集都满足最小支持度条件。连接操作等价于用数据库中 的每一个谓词来扩展 Fk-1，然后对于通过删除第（k-1）个谓词获得的（k-1）-谓词集删除那 些不在 Fk-1 中的谓词集。条件 p.fitemsetk-1< q.fitemsetk-1 确保谓词集中不会有重复的谓词出 现。在枝剪步骤中，所有那些（k-1）-子集不在 Fk-1 中的谓词集被从 Ck 中剔除，但并没有删 除任何一个有可能在 Fk 中的谓词集。因此，⊇，Apriori 算法是恰当的。
    剩下的任务是从频繁谓词集中产生想要的关联规则。一个直接的算法如下。为了生成规则， 每一个频繁谓词集 f 的所有非空子集都被列举出来，对于每一个子集 a，如果 support（f） 用这一特征，生成关联规则的算法如算法 4.2 所示。 --------------------------------------------------------------------------------------------------------------- Algorithm 4.2 Association Rule Generation Algorithm 和 support（a）的比率至少是最小置信度则产生形如a⟹(f−a)的规则。在这里要注意， 对于任意⊂a，规则a⟹(f−a)的置信度都不可能大于规则a⟹(f−a)的置信度。这也就 意味着若规则(f−a)⟹a 得到支持则所有格式为(f−a)⟹a的规则也都必须得到支持。利 H1 =∅ //初始化 A = (k − 1)-谓词集ak−1 的集合，其中满足ak−1⊂ fk ; output the rule ak−1⇒ ( fk − ak−1) with confidence = conf and support = support( fk ); con f = support( fk)/support(ak−1); if (con f ≥ mincon f ) then begin foreach; 频繁k-谓词集 fk , k ≥ 2 do begin foreach ak−1 ∈ A do begin add ( fk − ak−1) to H1; end end call ap-genrules( fk , H1); end Procedure ap-genrules( fk : 频繁 k-谓词集, Hm: m-谓词后项的集合) if (k > m + 1) then begin Hm+1 = apriori-gen(Hm); foreach hm+1 ∈ Hm+1 do begin con f = support( fk)/support( fk − hm+1); if (con f ≥ mincon f ) then output the rule fk − hm+1⇒ hm+1 with confidence = conf and support = support( fk ); else delete hm+1 from Hm+1; end call ap-genrules( fk , Hm+1); end ------------------------------------------------------------------------------------------------- 通过减少候选集合的大小 Apriori 算法能够达到很好的性能。然而，在拥有很多频繁谓词集 或者最小支持度非常低的时候，依旧有产生大量候选集和为大量的候选谓词集重复遍历数据 库的高昂代价。 AprioriTid AprioriTid 算法是 Apriori 算法的变体。它既不减少候选集的数量，也不在第一次遍历数据库 后为了计算支持度而使用数据库 D。它使用一个新的数据集。集合中的每一个成员的格 的标识符。对于 k=1，1相当于数据库 D，虽然在概念上每个谓词 i 被谓词集{i}代替。的 式为，其中 ID 是一个出现在标识符为 TID 的事务中的潜在频繁 k-谓词集（k 不为 1）
    每个对应于事务 t 成员就是。 使用的直观感觉就是对于 k 值非常大时它将小于数据库 D，因为一些事务可能不包含任何 候选 k-谓词集，在中也就不会有涉及该事务的实例，或者事务中包含非常少的候选集并且 每个实例可能小于相应事务中谓词的数量。算法 4.3 给出 AprioriTid 算法。这里 c[i]代表 k 谓 词集 c 中第 i 个谓词。 ------------------------------------------------------------------------------------------------------------------------------ Algorithm 4.3 AprioriTid Algorithm F1 = {频繁1-谓词集}; = database D; for (k = 2; Fk−1 ≠∅; k ++) do begin =∅; foreach 实例 t∈−1 do begin Ck = apriori-gen(Fk−1); //产生新的候选集 // 确定包含在标识为t.TID的事务中且在Ck中的候选谓词集 // Ct = {c ∈ Ck |(c − c[k]) ∈ t.set-of-itemsets ∧(c − c[k − 1]) ∈ t.set-of-itemsets}; foreach 候选集 c ∈ Ct do c.count ++; if (Ct ≠∅) then+ =< t.TID,Ct >; end Fk = {c ∈ Ck |c.count ≥ 最小支持度 }; end 结果= ∪k Fk ; ----------------------------------------------------------------------------------------------------------------------- 额外的字段，即产生器和扩展器。产生器字段存储连接产生 ck 的两个频繁（k-1）-谓词集的 对于每一个这样的 ck-1 其扩展字段给出了所有由 ck-1 扩展的候选 k-谓词集的 ID 的集合 Tk。对 于 Tk 中 的 每 一 个 ck ， 其 生 成 器 字 段 给 出 了 产 生 ck 的 两 个 谓 词 集 的 ID 。 如 果 对 于 t.set-of-itemsets 这些谓词集出现在实例中，可以得出 ck 出现在事务 t.TID 中，将 ck 添加进 Ct 中。 每一个都存储在一个顺序结构中。在 Ck 中一个候选 k-谓词集 ck 除了支持度字段外有两个 ID。扩展器字段存储所有由 ck 扩展得到的（k+1）-候选集的 ID。当一个候选集 ck 由−11 和−12 连接产生时，他们的 ID 被存储在 ck 的生成器字段中，ck 的 ID 则添加进−11 的扩展器字段中。 −1中一个实例 t 的 t.set-of-itemsets 字段给出了 t.TID 中包含的所有（k-1）-候选集的 ID。 AprioriTid 在计算是会花费一些代价，但其优势在于当 k 非常大时可以存储在内存中。 在预料到该遍历结束集合能够放入内存中时转而使用 AprioriTid。 因此可以预料，在早期遍历（k 较小）中 Apriori 优于 AprioriTid，而 AprioriTid 在后期遍历（k 较大）中优于 Apriori。由于 Apriori 和 AprioriTid 采用同样的候选集生成过程以及计算同样的 谓词集，依次结合使用这两种算法成为可能。AprioriHybrid 在初始遍历中使用 Apriori 算法， 挖掘序列模式 Agrawal and Srikant 将 Apriori 算法扩展到序列模式挖掘的问题上[2]。在 Apriori 中没有注意到
    序列，因此发现那些共同出现的谓词可以看做是发现事务内部模式。这里序列事务以及发现 序列模式可以看作是发现事务交互模式。 每个事务由序列 id、交易时间和一组谓词构成。相同的序列 id 仅仅只有一个具有相同的交 易时间。一个序列是一个按顺序排列的谓词集列表。因此一个序列由一组特征（谓词）集合 的列表构成，而不是简单的特征列表。一个序列的长度就是该序列中包含谓词集的数量。一 个长度为 k 的序列成为 k-序列。不失通用性地，谓词的集合假设为表达一组连续整数的集合， 一个谓词集 i 记为(12⋯)其中 ij 是一个谓词。一个序列 s 记为<12⋯>。如果存在一 组整数1<2<⋯<使得1⊆1,2⊆2,⋯,⊆，则序列<12⋯>被包含于另 一序列<12⋯>(n≤m)。所有具有相同序列 id 的事务由于交易时间连续而存储在一 起构成一个序列（事务序列）。如果序列 s 被它的事务序列所包含则该序列 id 支持这个序列 s。对于一个序列来说，支持度被定义为所有支持该序列的序列 id 在总的序列 id 数量中的比 例。同样地，一个谓词集 i 的支持度定义为存在一个包含 i 中所有谓词的事务的序列 id 的比 例。注意这个定义不同于 Apriori 中的用法。因此谓词集 i 和它的 1-序列具有相同的支持 度。 给定一个事务数据库 D，挖掘序列模式问题就是在所有满足某一用户定义的最小支持度条件 的序列中寻找最全的序列。每一个这样的最全序列代表一个序列模式。一个满足最小支持度 条件的序列成为频繁序列（不一定是最全的），而满足最小支持度条件的谓词集成为一个频 繁谓词集，简写为 fitemset。任何一个频繁序列必须是一组频繁谓词集的列表。 该算法由 5 个阶段构成：1）排序阶段，2）获取频繁谓词集阶段，3）转换阶段，4）获得序 列阶段，5）寻找最全序列阶段。前三步是预处理阶段，最后一步是后处理阶段。 在排序阶段，数据库 D 以序列 id 为主码，交易时间为次主码进行排序。在获取频繁谓词集 阶段，所有频繁谓词集的集合利用修改了支持度计算的 Apriori 算法获得，用来刻画一组连 续整数集合。这将比较两个频繁谓词集在一个常数时间是否相等。需要注意所有频繁 1-序 列的集合在这个阶段也同时获得。在转换阶段，每个事务被一个由该事务所包含的所有频繁 谓词集组成的集合代替。如果一个事务不包含任何频繁谓词集，它就不会保留在转换序列中。 如果一个事务序列不包含任何频繁谓词集，则该序列从转换数据库中移除，但是该事务序列 仍被计入到序列 id 总数中。在转换之后，一个事务序列代表一组谓词集集合的列表。每一 个谓词集集合用{1,2,⋯,3}表示，其中 fi 是一个谓词集。设计这个转换是用来高效检测给 出的频繁序列是否包含在一个事务序列中的。转换的数据库记为 DT。 序列阶段是该过程的核心部分，列举频繁序列。有两种算法：全局计数和局部计数。它们的 差别在于频繁序列计数的方式不同。全局计数算法对所有频繁序列进行计数，包括那些稍后 会被枝剪的非最全序列，而局部计数算法则避免对那些包含在一个更长序列中的序列进行计 数，因为最终的目的只是获得最全序列。Agrawal and Srikant 提出了一种称为 AprioriAll 的全 局计数算法以及两个分别称为 AprioriSome 和 DynamicSome 的局部计数算法。由于篇幅有限 这里仅介绍 AprioriAll 算法。 在最后的最全序列阶段，最全序列从所有频繁序列的集合中提取出来。利用哈希树（和 Apriori 算法中 subset 寒素中所用的相似）可以快速找到一个给定序列的所有子序列。 AprioriAll 算法 4.4 给出该算法的流程。在每次遍历中使用从前一次遍历得到的频繁序列生成候选序列， 然后通过遍历整个数据库测量它们的支持度。在一次遍历结束时，候选序列的支持度用来确 定频繁序列。
    apriori-gen-2 函数以所有频繁（k-1）-序列的集合 Fk-1 为参数。首先进行连接操作 插入 Ck 中 选择 p.fitemset1,p.fitemset2,…,p.fitemsetk-1,q.fitemsetk-1 从 Fk-1p, Fk-1q 其中 p.fitemset1= q.fitemset1, …, p.fitemsetk-2= q.fitemsetk-2, p.fitemsetk-1≠q.fitemsetk-1 --------------------------------------------------------------------------------------------------------------------------------- 算法 4.4 AprioriAll Algorithm F1 = {频繁 1-序列}; // 从频繁谓词集阶段获得的结果 for (k = 2; Fk−1 ≠∅; k ++) do begin Ck = apriori-gen-2(Fk−1); //获得新的候选序列 foreach 事务序列 t ∈ DT do begin Ct = subseq(Ck , t); //t中包含的候选序列 foreach 候选序列 c ∈ Ct do c.count ++; end Fk = {c ∈ Ck |c.count ≥ minsup }; end 结果 = maximal sequences in ∪k Fk; --------------------------------------------------------------------------------------------------------------------------------- 删除所有（k-1）-子序列不在 Fk-1 中且满足c∈的的序列。subseq 函数和 Apriori 中的 subset 函数相似。像 Apriori 中那样，候选序列集 Ck 存储在一个哈希树中以便快速找到包含一个事 务序列中的所有候选序列。注意转换后的事务序列是一组频繁谓词集集合的列表，而一个集 合中所有的频繁谓词集有相同的交易时间，对于相同的序列 id 具有相同交易时间的事务仅 有一个。subseq 函数中沿用这个条件。 讨论 Apriori 和 AprioriTid 算法都需要预先指定最小支持度和最小置信度。每当这些值发生变化时， 算法必须抛弃之前运行获得的所有结果重新运行。如果这些阈值没有合适的已知先验值，想 要在不重复运行该算法的情况下了解结果如何随着这些阈值发生变化，最好的办法就是用一 种高效的方法生成并计算所有曾经在数据库中出现的谓词集并存储。注意 Apriori 会生成一 些在数据库中没有出现过的候选集。 Apriori 和 AprioriTid 利用哈希散列树存储候选谓词集。另一种经常使用的数据结构是 trie 结 构[3-5]。在 trie 的 k 深度上的每个节点对应一个候选 k-谓词集，并存储第 k 个谓词及谓词集 的支持度。两个拥有相同的前（k-1）-谓词集的频繁 k-谓词集是兄弟节点，在 trie 中位于它 们在第 k-1 深度的父母节点的下方，候选集则简单的连接两个兄弟并在枝剪后将树扩展到第 一个频繁 k-谓词集下方更深一层的位置。为了找到事务 t 中包含的候选 k-谓词集，事务中的 每一个谓词都从根节点延伸，分支方向按照顺序直到到达一个第 k 个谓词。许多 Apriori 的 实际实现使用这种 trie 结构存储候选集和交易[4, 5]。 如果进一步我们可以完全摆脱生成候选谓词集。甚至没有必要列举出所有的频繁谓词集。这 些主题将在 4.5 部分中讨论。 Apriori 和几乎所有其他关联规则挖掘算法都采用两步策略：先挖掘频繁模式，再生成关联规 则。这并不是唯一的方法。Webb 的 MagnumOpus 采用另一种策略，直接生成一个大的所 有关联规则的子集[6]。
    有一些从原始 Apriori 家族直接扩展而来的算法。利用分类学方法和增加特定约束条件就是 两个例子。泛化关联规则[7]利用一组用户定义的分类集合使得在使用底层概念仅能产生非频 繁谓词集时提取由更高级概念表达的频繁谓词集成为可能。基本的算法就是在事务中对每一 个谓词添加其所有祖先，然后运行 Apriori 算法。有几个优化可以用来提高效率，一个是对 于一个同时包含谓词 x 和它的祖先的谓词集 X，其支持度和谓词集 X-的支持度相同，因此 不需要进行计算。泛化序列模式[8]除了引入分类外还引入了指定在邻近元素（谓词集）之间 的最小和/或最大时间段的时间约束，放松了一个序列模式中一个元素的谓词必须来自同一 个事物的限制，即允许这些谓词出现在交易时间位于用于指定时间窗口内的具有相同序列 id 的事务集合中。 它也能发现所有频繁序列模式（而不限于最全频繁序列模式）。GSP 算法较 AprioriAll 算法运行效率快 20 倍左右，原因是 GSP 比 AprioriAll 计算更少的候选。 关于可用软件实现的讨论 从免费软件到商业产品有许多 Apriori 的有效实现。此处仅列举三个可以从因特网免费下载 的著名的实现。 第一个是嵌入到怀卡托大学提供的著名开源机器学习与数据挖掘工具包 Weka 中的实现[9]。 Weka 中的 Apriori 可以通过 Weka 的通用图形用户界面和其他许多在 Weka 中可用的算法一 起使用。该实现包括 Weka 自身的扩展。例如最小支持度可以在区间内从上届 向下界为依次递减。甚至，除了置信度外还有度量指标作用度 life，leverage，conviction 可以用来评价关联规则。作用度和 leverage 将在 4.5 中讨论。确信度[10]是一个用来衡量背离 一个考虑某种含义的关联规则的独立性的程度。当使用这些度量指标时，必须给定一个临界 值作为其最小值。 第二个是 Christian Borgelt 实现的，该实现需要 GNU Lesser (Library)通用公共许可。这个实现 基本上是一个命令行应用程序，也有一些单独的图形用户界面可用。本质上它遵从原始 Apriori 流程，但是它也有自己的扩展从而使其运行更快，占用内存更少。它利用一个称谓前 缀树的字母树来存储事务和谓词集从而高效进行支持度计数[5]。前缀树和 4.2.3 中解释字母 树只有很小的差别。视情况而定，用户可以选择使用简单列表代替前缀树存储事务。甚至， 该实现不仅可以寻找频繁谓词集和关联规则，还可以寻找封闭谓词集和最全谓词集。封闭和 最大谓词集将在 4.5 中讨论。另外，除了置信度还有几个度量值，比如信息增益，可以在这 个实现评估和选择关联规则时使用。 第三个实现是有 Fence Bodon 完成的，以研究目的可以免费得到。和 Borgelt 的实现类似， 这个实现也是基于字母树的，但是采用一种简单结构的字母树，并且仅计算频繁谓词集和关 联规则。它以命令行应用程序的方式运行，接受四个参数。前三个参数是强制的：一个包括 事务的输入文件，一个输出文件和最小支持度。第四个参数是最小置信度，该参数是可选的。 如果给定最小置信度，则挖掘出频繁谓词集和关联规则，否则它只能输出频繁谓词集。这是 实现是在提供了易于在开发其他基于 Apriori 的算法中重用的面向对象组件的 C++中编写的。 两个解释示例 运行示例 我们将使用表 4.1 中显示的小型数据库来解释上述算法的详细操作，表中 SID 和 TT 分别代 表序列 id 和交易时间。在关联规则（频繁谓词集）挖掘和最大序列模式挖掘中用的都是这 个数据。在前者中忽略 SID 和 TT 字段。
    频繁谓词集和关联规则挖掘 假设寻找最小支持度为 0.2 情况下的频繁谓词集和最小置信度为 0.6 的关联规则。 Apriori SID 1 1 4 3 2 3 4 4 3 1 2 3 1 3 TT May 03 May 05 May 05 May 05 May 05 May 06 May 06 May 07 May 08 May 08 May 08 May 09 May 09 May 10 Items c, d f a, c c, d, f b, c, f d, f, g a a, c, d c, d, f, g d, e b, d d, g e, f c, d, f Apriori 首 先 遍 历 整 个 数 据 库 并 得 到 至 少 出 现 在 三 个 事 务 中 的 频 繁 1- 谓 词 集 的 集 合 ， F1={a,c,d,f,g} 。 从 F1 中 利 用 apriori-gen 函 数 得 出 候 选 频 繁 2- 谓 词 集 的 结 合 C2={ac,ad,af,ag,cd,cf,cg,df,dg,fg}。此时由于还没有进行枝剪，C2 由所有可能的 F1 中的元素对 构成。 表 4.1 A Transaction Database of the Working Example 演示示例的一个事务数据 TID 001 002 003 004 005 006 007 008 009 010 011 012 013 014 下一步，Apriori 使用采用一个哈希散列树的 subset 函数通过遍历数据库计算它们的支持度。 图 4.1 简单的解释了哈希散列树是如何构建及使用的。假设 C2 的元素按照词典顺序被添加 进哈希散列树中，叶节点中允许的最大谓词集数量为 4。因此，当第五个谓词集 cd 被添加 进去时，根（叶）节点中的谓词集数量将超过该阈值。此时，该节点将转变为内部节点，每 一个谓词集按照函数 h(x)给出的哈希值分配到相应的新叶节点中，其中 x 是一个谓词，在本 例中是每一个谓词集中的第一个谓词。假设预先给定 h(x)并对所有点都通用。由于前 4 个谓 词集都使用相同的第一个谓词 a，它们都落入同一个叶节点中，此时 cd 却落入到一个不同 的叶节点中。当检验一个事务中包含哪些候选集时，例如事务 004，事务中的每一个谓词都 在根节点进行哈希。例如在 cdf 中利用 c 哈希，它到达第二个叶节点，如图 4.1（b）左边的
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料