样，在此后扫描D确定L3时就不必再求它们的计数值。注意，Apriori算法使用逐层搜索技术，给定k-项集，我们只需要检查它们的(k-1)-子集是否频繁。
7. 扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成（图6.3）。 8. 算法使用L3?L3产生候选4-项集的集合C4。尽管连接产生结果{{I1,I2,I3,I5}}，这个项集被剪
去，因为它的子集{I1,I3,I5}不是频繁的。这样，C4 = ?，因此算法终止，找出了所有的频繁项集。? 图6.5给出Apriori算法和它的相关过程的伪代码。Apriori的第1步找出频繁1-项集的集合L1。在2-10步，Lk - 1用于产生候选C k，以找出L k。Apriori_gen过程产生候选，然后使用Apriori性质删除那些具有非频繁子集的候选（步骤3）。该过程在下面描述。一旦产生了所有的候选，就扫描数据库（步骤4）。对于每个事务，使用subset函数找出事务中是候选的所有子集（步骤5），并对每个这样的候选累加计数（步骤6和7）。最后，所有满足最小支持度的候选形成频繁项集L。然后，调用一个过程，由频繁项集产生关联规则。该过程在6.2.2小节介绍。 算法6.2.1 (Apriori) 使用逐层迭代找出频繁项集 输入：事务数据库D；最小支持度阈值。 输出：D中的频繁项集L。
方法：
1) L1 = find_frequent_1_itemsets(D); 2) for (k = 2; Lk-1 ? ?; k++) {
3) Ck = aproiri_gen(Lk-1,min_sup);
4) for each transaction t?D{ //scan D for count 5) Ct = subset(Ck,t); //get subsets of t that are candidates 6) for each candidate c?Ct 7) c.count++; 8) }
9) Lk={c?Ck | c.count ? min_sup} 10) }
11) return L = ?kLk；
procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support) 1) for each itemset l1?Lk-1 2) for each itemset l2?Lk-1 3) if (l1[1]=l2[1])?...?(l1[k-2]=l2[k-2])?(l1[k-1] procedure has_infrequent_subset(c:candidate k-itemset; L k-1:frequent (k-1)-itemset) // use priori knowledge 1) for each (k-1)-subset s of c 2) if c?Lk-1 then 3) return TRUE; 4) return FALSE; 图6.5 对于布尔关联规则发现频繁项集的Apriori算法 如上所述，Apriori_gen做两个动作：连接和剪枝。在连接部分，Lk - 1与L k - 1连接产生可能的候选（步骤1-4）。剪枝部分（步骤5-7）使用Apriori性质删除具有非频繁子集的候选。非频繁子集的测试在过程has_infrequent_subset中。 6.2.2 由频繁项集产生关联规则 一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直接了当的（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。 support_count(A?B)confidence(A?B)?P(A|B)? (6.8) support_count(A)其中，support_count(A?B)是包含项集A?B的事务数，support_count(A)是包含项集A的事务数。根据该式，关联规则可以产生如下： ? 对于每个频繁项集l，产生l的所有非空子集。 ? 对于l的每个非空子集s，如果 support_count(l)?min_conf，则输出规则“s ? (l-s)”。其 support_count(s)中，min_conf是最小置信度阈值。 由于规则由频繁项集产生，每个规则都自动满足最小支持度。频繁项集连同它们的支持度预先存放在hash表中，使得它们可以快速被访问。 例6.2 让我们试一个例子，它基于图6.2中 AllElectronics事务数据库。假定数据包含频繁项集l = {I1, I2, I5}，可以由l产生哪些关联规则？l的非空子集有{I1,I2}, {I1,I5}, {I2,I5}, {I1}, {I2}和{I5}。结果关联规则如下，每个都列出置信度。 I1?I2 ? I5, I1?I5 ? I2, I2?I5 ? I1, I1 ? I2?I5, I2 ? I1?I5, I5 ? I1?I2, confidence = 2/4 = 50% confidence = 2/2 = 100% confidence = 2/2 = 100% confidence = 2/6 = 33% confidence = 2/7 = 29% confidence = 2/2 = 100% 如果最小置信度阈值为70%，则只有2、3和最后一个规则可以输出，因为只有这些是强的。? 6.2.3 提高Apriori的有效性 “怎样能够提高Apriori的有效性？”已经提出了许多Apriori算法的变形，旨在提高原算法的效率。其中一些变形列举如下。 图6.6 候选2-项集的散列表H2：该散列表在由C1确定L1时通过扫描图5.2的事 务数据库产生。如果最小支持度为3，在桶0, 1，3和4中的项集不可能是频繁的，因而它们不包含在C2中 基于散列的技术（散列项集计数）：一种基于散列的技术可以用于压缩候选k-项集Ck (k >1)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，我们可以对每个事务产生所有的2-项集，将它们散列（即，映射）到散列表结构的不同桶中，并增加对应的桶计数 （图6.6）。在散列表中对应的桶计数低于支持度阈值的2-项集不可能是频繁2-项集，因而应当由候选项集中删除。这种基于散列的技术可以大大压缩要考察的k-项集（特别是当k = 2时）。 事务压缩（压缩进一步迭代扫描的事务数）：不包含任何k-项集的事务不可能包含任何(k+1)-项集。这样，这种事务在其后的考虑时，可以加上标记或删除，因为为产生j-项集(j > k)，扫描数据库时不再需要它们。 划分（为找候选项集划分数据）：可以使用划分技术，它只需要两次数据库扫描，以挖掘频繁项集（图6.7）。它包含两遍。在第I遍，算法将D中的事务划分成n个非重叠的部分。如果D中事务的最小支持度阈值为min_sup，则每个部分的最小支持度计数为min_sup?该部分中事务数。对每一部分，找出该部分内的频繁项集。这些称作局部频繁项集。该过程使用一种特殊的数据结构，对于每个项集，记录包含项集中项的事务的TID。这使得对于k = 1,2,..，找出所有的局部频繁k-项集只需要扫描一次数据库。 局部频繁项集可能不是整个数据库D的频繁项集。D的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，所有的局部频繁项集作为D的候选项集。所有部分的频繁项集的集合形成D的全局候选项集。在第II遍，第二次扫描D，评估每个候选的实际支持度，以确定全局频繁项集。每一部分的大小和划分的数目这样确定，使得每一部分能够放入内存，这样每遍只需要读一次。 图6.7 通过划分挖掘 选样（在给定数据的一个子集挖掘）：选样方法的基本思想是：选取给定数据库D的随机样本S，然后，在S而不是在D中搜索频繁项集。用这种方法，我们牺牲了一些精度换取了有效性。样本S的大小这样选取，使得可以在内存搜索S中频繁项集；这样，总共只需要扫描一次S中的事务。由于我们搜索S 中而不是D中的频繁项集，我们可能丢失一些全局频繁项集。为减少这种可能性，我们使用比最小支持度低的支持度阈值来找出局部于S的频繁项集（记作LS）。然后，数据库的其余部分用于计算LS中每个项集的实际频繁度。有一种机制可以用来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，只需要扫描一次D。否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须在不同的数据上运行时，选样方法特别合适。 动态项集计数（在扫描的不同点添加候选项集）：动态项集计数技术将数据库划分为标记开始点的块。不象Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。 其它变形涉及多层和多维关联规则挖掘，在本章的其余部分讨论。涉及空间数据、时间序列数据和多媒体数据的关联挖掘在第9章讨论。 6.2.4 不产生候选挖掘频繁项集 正如我们已经看到的，在许多情况下，Apriori的候选产生-检查方法大幅度压缩了候选项集的大小，并导致很好的性能。然而，它有两种开销可能并非微不足道的。 ? 它可能需要产生大量候选项集。例如，如果有104个频繁1-项集，则Apriori算法需要产生多达107个候选2-项集，累计并检查它们的频繁性。此外，为发现长度为100的频繁模式，如{a1 ,..., a100}，它必须产生多达2100 ? 1030个候选。 它可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。对于挖掘长模式尤其如此。 ? “可以设计一种方法，挖掘全部频繁项集，而不产生候选吗？”一种有趣的方法称作频繁模式增长，或简单地，FP-增长，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（或FP-树），但仍保留项集关联信息；然后，将这种压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个关联一个频繁项，并分别挖掘每个数据库。让我们看一个例子。 例6.3 使用频繁模式增长方法，我们重新考察例6.1中图6.2事务数据库D的挖掘。 数据库的第一次扫描与Apriori相同，它导出频繁项（1-项集）的集合，并得到它们的支持度计数（频繁性）。设最小支持度计数为2。频繁项的集合按支持度计数的递减序排序。结果集或表记作L。这样，我们有L = [I2:7, I1:6, I3:6, I4:2, I5:2]。 然后，FP-树构造如下：首先，创建树的根结点，用“null”标记。二次扫描数据库D。每个事务中的项按L中的次序处理（即，根据递减支持度计数排序）并对每个事务创建一个分枝。例如，第一个事务“T100: I1, I2, I5”按L的次序包含三个项{ I2, I1, I5}，导致构造树的第一个分枝<(I2:1), (I1:1), (I5:1)>。该分枝具有三个结点，其中，I2作为根的子女链接，I1链接到I2，I5链接到I1。第二个事务T200按L的次序包含项I2和I4，它导致一个分枝，其中，I2链接到根，I4链接到I2。然而，该分枝应当与T100已存在的路径共享前缀 为方便树遍历，创建一个项头表，使得每个项通过一个结点链指向它在树中的出现。扫描所有的事务之后得到的树展示在图6.8中，附上相关的结点链。这样，数据库频繁模式的挖掘问题就转换成挖掘FP-树问题。 图6.8 存放压缩的频繁模式信息的FP-树 FP-树挖掘处理如下。由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”， 由FP-树中与后缀模式一起出现的前缀路径集组成）。然后，构造它的（条件）FP-树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-树产生的频繁模式连接实现。 FP-树的挖掘总结在表6.1中，细节如下。让我们首先考虑I5，它是L中的最后一个项，而不是第一个。其原因随着我们解释FP-树挖掘过程就会清楚。I5出现在图6.8 的FP-树的两个分枝。（I5的出现容易通过沿它的结点链找到。）这些路径由分枝<(I2 I1 I5:1)>和<(I2 I1 I3 I5:1)>形成。这样，考虑I5为后缀，它的两个对应前缀路径是<(I2 I1:1)>和<(I2 I1 I3:1)>，它们形成I5的条件模式基。它的条件FP-树只包含单个路径<(I2:2 I1:2)>；不包含I3，因为它的支持度计数为1，小于最小支持度计数。该单个路径产生频繁模式的所有组合：I2 I5:2, I1 I5:2, I2 I1 I5:2。 表6.1 通过创建条件（子）模式基挖掘FP-树 item I5 I4 I3 I1 条件模式基 {(I2 I1:1), (I2 I1 I3:1)) {(I2 I1:1), (I2:1)} {(I2 I1:2), (I2:2), (I1:2)} {(I2:4)} 条件FP-树 产生的频繁模式 I2 I5:2, I1 I5:2, I2 I1 I5:2 I2 I4:2 I2 I3:4, I1 I3:4, I2 I1 I3:2 I2 I1:4 对于I4，它的两个前缀形成条件模式基{(I2 I1:1), (I2:1)，产生一个单结点的条件FP-树 与以上分析类似，I3的条件模式基是{(I2 I1:2), (I2:2), (I1:2)}。它的条件FP-树有两个分枝 图6.9 具有条件结点I3的条件FP-树 算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。 输入：事务数据库D；最小支持度阈值min_sup。 输出：频繁模式的完全集。 方法： 1．按以下步骤构造FP-树： (a) 扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度 降序排序，结果为频繁项表L。 (b) 创建FP-树的根结点，以“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)。 2．FP-树的挖掘通过调用FP_growth(FP_tree, null)实现。该过程实现如下： procedure FP_growth(Tree, ?) (1) if Tree 含单个路径P then (2) for 路径P中结点的每个组合（记作?） (3) 产生模式? ? ?，其支持度support = ?中结点的最小支持度； (4) else for each a i 在Tree的头部 { (5) 产生一个模式? = a i ? ?，其支持度support = a i .support； (6) 构造?的条件模式基，然后构造?的条件FP-树Tree?； (7) if Tree? ? ? then (8) 调用 FP_growth (Tree?, ?)；} 图6.10 不产生候选，发现频繁项集的FP-增长算法 FP-增长方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后与后缀连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据挖掘CHAPTER6挖掘大型数据库中的关联规则(2)在线全文阅读。
相关推荐：